Сancelable/async regexp

💡 Ideas
1

Regular expressions have exponential time worst case complexity and its usage are blocking operations. This provides the ability of ReDoS attack.

time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCX")'
// real    0.529s

time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
// real    3.809s

My suggestion is to make regexp asynchronous and cancellable. This will allow us to reliably protect ourselves from such attacks in production, because we always (almost) know how complex the string is expected to be for a given matcher, and the other cases are most likely an attack and do not need to check them.

1 Like
2

Possible usage like this:

...
/regex/.test("string", 100) // Operations more than 100ms returns false
...

or:

/regex/.test("string", 100) // Operations more than 100ms throws error
        .catch(() => false)

maybe even:

function check(str) {
    const re = new RegExp('regex');

    return new Promise(function (resolve, reject) {
        re.onDone(resolve);
        re.onCancel(reject);

        setTimeout(function () {
            re.cancel();
        }, 100);

        re.test(str)
    });
}
3

I agree that with thier current semantics, RegExps are not safe to use in production. I proposed an alternative recently that got support from @jridgewell, but didn't get any traction with implementers (the Chrome and Safari team).

They are instead working on preventing backtracking when possible.

I don't think it is the safest way forward though. Either what you propose or possessive RegExps give the ultimate power to users and both options can be tested exhaustively.

OTOH, engine optimizations can fail or regress in corner cases that escape testing.

4

I just want to have possibility to avoid event loop blocking, besides it doesn't contradicts to yours proposal :)

5

Indeed, I wanted to give you what seems like relevant information on the topic