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

  > Regolith attempts to be a drop-in replacement for RegExp and requires minimal (to no) changes to be used instead

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

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?

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

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?

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.

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

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 

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

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?