5 ms·

Show HN: Regolith – Regex library that prevents ReDoS CVEs in TypeScript

27 points by roggenbuck 1y ago

I wanted a safer alternative to RegExp for TypeScript that uses a linear-time engine, so I built Regolith. Why: Many CVEs happen because TypeScript libraries are vulnerable to Regular Expression Denial of Service attacks. I learned about this problem while doing undergraduate research and found that languages like Rust have built-in protection but languages like JavaScript, TypeScript, and Python do not. This library attempts to mitigate these vulnerabilities for TypeScript and JavaScript. How: Regolith uses Rust's Regex library under the hood to prevent ReDoS attacks. The Rust Regex library implements a linear-time Regex engine that guarantees linear complexity for execution. A ReDoS attack occurs when a malicious input is provided that causes a normal Regex engine to check for a matching string in too many overlapping configurations. This causes the engine to take an extremely long time to compute the Regex, which could cause latency or downtime for a service. By designing the engine to take at most a linear amount of time, we can prevent these attacks at the library level and have software inherit these safety properties. I'm really fascinated by making programming languages safer and I would love to hear any feedback on how to improve this project. I'll try to answer all questions posted in the comments. Thanks! - Jake Roggenbuck

spankalee 1y ago
It's very, very weird to speak of TypeScript and JavaScript as two separate languages here. There is no TypeScript RegExp, there is only the JavaScript RegExp as implemented in various VMs. There is no TypeScript VM, only JavaScript VMs. And there are no TypeScript CVEs unless it's against the TypeScript compiler, language server, etc.
- serial_dev 1y ago
  I was also confused first, I thought it is against the TypeScript compiler, too.
- maxloh 1y ago
  Deno and Node use V8 under the hood, so the code should essentially run on the same VM regardless.
- DemocracyFTW2 1y ago
  This bothered me too; I think it should be re-framed as a difference between different JS engines (NodeJS vs Deno) because that's what happening. TS is just a fancy way to write JavaScript after all and a lot of TS source code gets literally erased in order to obtain runnable JS. Deno has been able to execute pure JavaScript from day one while NodeJS can now also execute a subset of TS without a visible translation step, all of which makes framing NodeJS vs Deno as "JavaScript vs TypeScript" even weirder.
xyzzy123 1y ago
It's great to have a safe options - and it would have been great if the default had been safe. I think many people are annoyed with ReDos as a bug class. It seems like mostly noise in the CVE trackers, library churn and badge collecting for "researchers". It'd be less of a problem if people stuck to filing CVEs against libraries that might remotely see untrusted input rather than scrambling to collect pointless "scalps" from every tool under the sun that accepts a configuration regex - build tools, very commonly :( Perhaps you can stop this madness... :)
- bawolff 1y ago
  Even in cases where malicious input could be hit, this bug class is stupid on the client side where the attacker can only attack themselves.
  - xyzzy123 1y ago
    Stored... ReDoS, reflected... ReDoS(??)... [it pained me to type those] (╯°□°)╯︵ ┻━┻
- roggenbuck 1y ago
  > and it would have been great if the default had been safe. I totally agree here. Safety can and should be from the language itself.
semiquaver 1y ago
> Regolith attempts to be a drop-in replacement for RegExp and requires minimal (to no) changes to be used instead vs > Since Regolith uses Rust bindings to implement the Rust Regex library to achieve linear time worst case, this means that backreferences and look-around aren't available in Regolith either. Obviously it cannot be a drop-in replacement if the regex dialect differs. That it has a compatible API is not the only relevant factor. I’d recommend removing the top part from the readme. Another thought: since backreferences and lookaround are the features in JS regexes which _cause_ ReDOS, why not just wrap vanilla JS regex, rejecting patterns including them? Wouldn’t that achieve the same result in a simpler way?
- bawolff 1y ago
  > Another thought: since backreferences and lookaround are the features in JS regexes which _cause_ ReDOS, This is incorrect. Other features can cause ReDOS. The other problematic features have linear time algorithms that could be used, but generally are not used (i assume for better average case performance)
  - roggenbuck 1y ago
    Yea, I can expand the description to include other features that may cause issues. Here is an example of how counting can cause latency too: https://www.usenix.org/system/files/sec22fall_turonova.pdf https://www.usenix.org/system/files/sec22fall_turonova.pdf
    - thomasmg 1y ago
      A static analysis of the regular expression has the advantage that many problematic cases can be caught at compile time. Not all: the expression is sometimes generated at runtime. There's also a risk that too many cases might be rejected. Did you consider a hybrid approach, where static analysis is used to get compiler warnings / errors, combined with limiting the number of operations at runtime? An API change might be needed, so instead of just "matches(regex)" a new method might be needed with a limit "matches(regex, opCountLimit)" and a different return type (true / false / timeout).
dwoldrich 1y ago
Perhaps regex is just a bad little language for pattern matching. I have a foggy recollection of compute times exploding for me on a large regex in .Net code and I used a feature I hadn't seen in JavaScript's RegExp that allowed me to mark off sections of already matched parts of the regular expression that prevented it from backtracking. Perhaps the answer isn't removing features for linear regex, but adding more features to make it more expressive and tunable?
DemocracyFTW2 1y ago
FWIW there's also https://github.com/slevithan/regex https://github.com/slevithan/regex "JS regexes future. A template tag for readable, high-performance, native JS regexes with extended syntax, context-aware interpolation, and always-on best practices". From the docs: Highlights include support for insignificant whitespace and comments, atomic groups and possessive quantifiers (that can help you avoid ReDoS), subroutines and subroutine definition groups (that enable powerful subpattern composition), and context-aware interpolation of regexes, escaped strings, and partial patterns.
deleted 1y ago
[deleted]
DemocracyFTW2 1y ago
I have another nitpick and I hope it's a constructive one. You provide some performance figures; unfortunately they are caught in an image, no doubt to enable color-coding the results. IMHO that's not ideal, tables should be pure text, even if only for accessibility with screen readers. There are other means to provide guiding highlights, like red and green Unicode code points. GitHub is somewhat unique in its strict policy to remove almost any kind of user-side styling from the READMEs, but providing a "photo snapshot" of parts of the README just to get some colors does not feel like the right solution. Next thing are the actual figures you provide: those range from 11.822µs (best) to 56.534s (worst). They are displayed as 11.822µs 56.534s making them look almost like the worst performer took around five times as long as the best performer—until you realize there's a mu in there. I must say that personally I remove this so-called "human-readable" format almost wherever I can because I find it not human-readable at all. To me a good numerical display should try and keep the decimal points on top of each other, avoid too many non-significant digits, use digit grouping, and, crucially, use a single unit throughout. With those constraints, the two figures become 11.8µs 56,534,000.0µs which incidentally obviates much of the need to color code anything. One could discuss what unit—ns, µs, ms, s—is the most appropriate in the given context but, generally, I feel that big numbers should stand out as having many digits. Nobody will pick this up because it's much too elaborate and idiosyncratic for this conformist world, but I just love the 'Japanese' way of formatting where you do digit grouping with the SI prefixes, so one hundred and twenty-five meters is 125m, but one thousand one hundred and twenty-five meters doesn't become 1,125m, nor is it 1.125km, but rather 1k125m (preferrably with a thin space as in 1k_125m—imagine a thin non-breakable space there that HN wouldn't let me render). 1G 255M 368k 799B, what's not to like?
truth_seeker 1y ago
Magic-RegExp aims to create a compiled away, type-safe, readable RegEx alternative that makes the process a lot easier. https://blog.logrocket.com/understanding-magic-regexp-regexp https://blog.logrocket.com/understanding-magic-regexp-regexp... example from blog: import { createRegExp, exactly, wordChar, oneOrMore, anyOf, } from "magic-regexp"; const regExp = createRegExp( exactly("http") .and(exactly("s").optionally()) .and("://") .optionally() .and(exactly("www.").optionally()) .and(oneOrMore(wordChar)) .and(exactly(".")) .and(anyOf("com", "org", "io")), ["g", "m", "i"] ); console.log(regExp); /(https?:\/\/)?(www\.)?\w+\.(com|org|io)/gmi
conartist6 1y ago
FWIW JS has a library-layer non-backtracking regex implementation in @bablr/regex. It's still a slightly different dialect of regex than native JS regex which (currently) lacks lookahead and lookbehind support. It's not going to have Rust-y perf, but it shouldn't get ReDoS'd either.

27 points by roggenbuck 1y ago

spankalee 1y ago

It's very, very weird to speak of TypeScript and JavaScript as two separate languages here. There is no TypeScript RegExp, there is only the JavaScript RegExp as implemented in various VMs. There is no TypeScript VM, only JavaScript VMs. And there are no TypeScript CVEs unless it's against the TypeScript compiler, language server, etc.

serial_dev 1y ago
I was also confused first, I thought it is against the TypeScript compiler, too.
maxloh 1y ago
Deno and Node use V8 under the hood, so the code should essentially run on the same VM regardless.
DemocracyFTW2 1y ago
This bothered me too; I think it should be re-framed as a difference between different JS engines (NodeJS vs Deno) because that's what happening. TS is just a fancy way to write JavaScript after all and a lot of TS source code gets literally erased in order to obtain runnable JS. Deno has been able to execute pure JavaScript from day one while NodeJS can now also execute a subset of TS without a visible translation step, all of which makes framing NodeJS vs Deno as "JavaScript vs TypeScript" even weirder.

xyzzy123 1y ago

It's great to have a safe options - and it would have been great if the default had been safe. I think many people are annoyed with ReDos as a bug class. It seems like mostly noise in the CVE trackers, library churn and badge collecting for "researchers". It'd be less of a problem if people stuck to filing CVEs against libraries that might remotely see untrusted input rather than scrambling to collect pointless "scalps" from every tool under the sun that accepts a configuration regex - build tools, very commonly :( Perhaps you can stop this madness... :)

bawolff 1y ago
Even in cases where malicious input could be hit, this bug class is stupid on the client side where the attacker can only attack themselves.
- xyzzy123 1y ago
  Stored... ReDoS, reflected... ReDoS(??)... [it pained me to type those] (╯°□°)╯︵ ┻━┻
roggenbuck 1y ago
> and it would have been great if the default had been safe. I totally agree here. Safety can and should be from the language itself.

semiquaver 1y ago

> Regolith attempts to be a drop-in replacement for RegExp and requires minimal (to no) changes to be used instead vs > Since Regolith uses Rust bindings to implement the Rust Regex library to achieve linear time worst case, this means that backreferences and look-around aren't available in Regolith either. Obviously it cannot be a drop-in replacement if the regex dialect differs. That it has a compatible API is not the only relevant factor. I’d recommend removing the top part from the readme. Another thought: since backreferences and lookaround are the features in JS regexes which _cause_ ReDOS, why not just wrap vanilla JS regex, rejecting patterns including them? Wouldn’t that achieve the same result in a simpler way?

bawolff 1y ago
> Another thought: since backreferences and lookaround are the features in JS regexes which _cause_ ReDOS, This is incorrect. Other features can cause ReDOS. The other problematic features have linear time algorithms that could be used, but generally are not used (i assume for better average case performance)
- roggenbuck 1y ago
  Yea, I can expand the description to include other features that may cause issues. Here is an example of how counting can cause latency too: https://www.usenix.org/system/files/sec22fall_turonova.pdf https://www.usenix.org/system/files/sec22fall_turonova.pdf
  - thomasmg 1y ago
    A static analysis of the regular expression has the advantage that many problematic cases can be caught at compile time. Not all: the expression is sometimes generated at runtime. There's also a risk that too many cases might be rejected. Did you consider a hybrid approach, where static analysis is used to get compiler warnings / errors, combined with limiting the number of operations at runtime? An API change might be needed, so instead of just "matches(regex)" a new method might be needed with a limit "matches(regex, opCountLimit)" and a different return type (true / false / timeout).

dwoldrich 1y ago

Perhaps regex is just a bad little language for pattern matching. I have a foggy recollection of compute times exploding for me on a large regex in .Net code and I used a feature I hadn't seen in JavaScript's RegExp that allowed me to mark off sections of already matched parts of the regular expression that prevented it from backtracking. Perhaps the answer isn't removing features for linear regex, but adding more features to make it more expressive and tunable?

DemocracyFTW2 1y ago

FWIW there's also https://github.com/slevithan/regex https://github.com/slevithan/regex "JS regexes future. A template tag for readable, high-performance, native JS regexes with extended syntax, context-aware interpolation, and always-on best practices". From the docs: Highlights include support for insignificant whitespace and comments, atomic groups and possessive quantifiers (that can help you avoid ReDoS), subroutines and subroutine definition groups (that enable powerful subpattern composition), and context-aware interpolation of regexes, escaped strings, and partial patterns.

deleted 1y ago

[deleted]

DemocracyFTW2 1y ago

I have another nitpick and I hope it's a constructive one. You provide some performance figures; unfortunately they are caught in an image, no doubt to enable color-coding the results. IMHO that's not ideal, tables should be pure text, even if only for accessibility with screen readers. There are other means to provide guiding highlights, like red and green Unicode code points. GitHub is somewhat unique in its strict policy to remove almost any kind of user-side styling from the READMEs, but providing a "photo snapshot" of parts of the README just to get some colors does not feel like the right solution. Next thing are the actual figures you provide: those range from 11.822µs (best) to 56.534s (worst). They are displayed as 11.822µs 56.534s making them look almost like the worst performer took around five times as long as the best performer—until you realize there's a mu in there. I must say that personally I remove this so-called "human-readable" format almost wherever I can because I find it not human-readable at all. To me a good numerical display should try and keep the decimal points on top of each other, avoid too many non-significant digits, use digit grouping, and, crucially, use a single unit throughout. With those constraints, the two figures become 11.8µs 56,534,000.0µs which incidentally obviates much of the need to color code anything. One could discuss what unit—ns, µs, ms, s—is the most appropriate in the given context but, generally, I feel that big numbers should stand out as having many digits. Nobody will pick this up because it's much too elaborate and idiosyncratic for this conformist world, but I just love the 'Japanese' way of formatting where you do digit grouping with the SI prefixes, so one hundred and twenty-five meters is 125m, but one thousand one hundred and twenty-five meters doesn't become 1,125m, nor is it 1.125km, but rather 1k125m (preferrably with a thin space as in 1k_125m—imagine a thin non-breakable space there that HN wouldn't let me render). 1G 255M 368k 799B, what's not to like?

truth_seeker 1y ago

Magic-RegExp aims to create a compiled away, type-safe, readable RegEx alternative that makes the process a lot easier. https://blog.logrocket.com/understanding-magic-regexp-regexp https://blog.logrocket.com/understanding-magic-regexp-regexp... example from blog: import { createRegExp, exactly, wordChar, oneOrMore, anyOf, } from "magic-regexp"; const regExp = createRegExp( exactly("http") .and(exactly("s").optionally()) .and("://") .optionally() .and(exactly("www.").optionally()) .and(oneOrMore(wordChar)) .and(exactly(".")) .and(anyOf("com", "org", "io")), ["g", "m", "i"] ); console.log(regExp); /(https?:\/\/)?(www\.)?\w+\.(com|org|io)/gmi

conartist6 1y ago

FWIW JS has a library-layer non-backtracking regex implementation in @bablr/regex. It's still a slightly different dialect of regex than native JS regex which (currently) lacks lookahead and lookbehind support. It's not going to have Rust-y perf, but it shouldn't get ReDoS'd either.