Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

github.com

Post reply on HN
Print view View original

1–10 of 27 posts

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

#1

Post by roggenbuck »

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

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

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

#2

Post by spankalee »

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.

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

#3

Post by xyzzy123 »

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... :)

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

#4

Post by semiquaver » 

  > 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?

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

#5

Post by bawolff »

semiquaver wrote: post #4

> 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…

> 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)

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

#6

Post by roggenbuck »

semiquaver wrote: post #4

> 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…

Thanks for the feedback! Yea, you're totally right. I'll update the docs to reflect this.

> why not just wrap vanilla JS regex, rejecting patterns including them?

Yea! I was thinking about this too actually. And this would solve the problem of being server side only. I'm thinking about making a new version to do just this.

For a pattern rejecting wrapper, how would you want it to communicate that an unsafe pattern has been created.

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

#7

Post by bawolff »

xyzzy123 wrote: post #3

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 "scal…

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.

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

#8

Post by serial_dev »

spankalee wrote: post #2

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.

I was also confused first, I thought it is against the TypeScript compiler, too.

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

#9

Post by roggenbuck »

xyzzy123 wrote: post #3

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 "scal…

> 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.

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

#10

Post by roggenbuck »

bawolff wrote: post #5
semiquaver wrote: post #4

> 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…

> 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)

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
Post reply on HN