The trustworthy ReDoS checker
MIT License.
2020-2024 (C) TSUYUSATO "MakeNowJust" Kitsune
The trustworthy ReDoS checker
Home Page: https://makenowjust-labs.github.io/recheck/
License: MIT License
import { check } from 'recheck';
await check('^(a|a)*$', '');
gives:
[Running] node "/home/userA/code/projectA/regexTest.js"
node:events:491
throw er; // Unhandled 'error' event
^
Error: write EPIPE
at afterWriteDispatched (node:internal/stream_base_commons:160:15)
at writeGeneric (node:internal/stream_base_commons:151:3)
at Socket._writeGeneric (node:net:917:11)
at Socket._write (node:net:929:8)
at writeOrBuffer (node:internal/streams/writable:392:12)
at _write (node:internal/streams/writable:333:10)
at Writable.write (node:internal/streams/writable:337:10)
at /home/userA/code/projectA/node_modules/recheck/lib/main.js:2:20
at new Promise (<anonymous>)
at FA.request (/home/userA/code/projectA/node_modules/recheck/lib/main.js:1:1513)
Emitted 'error' event on Socket instance at:
at emitErrorNT (node:internal/streams/destroy:151:8)
at emitErrorCloseNT (node:internal/streams/destroy:116:3)
at process.processTicksAndRejections (node:internal/process/task_queues:82:21) {
errno: -32,
code: 'EPIPE',
syscall: 'write'
}
Node.js v18.12.1
It is like this in 4.4.2 and 4.4.3 but in 4.4.1 it works.
No idea.
None.
The old check
function is synchronous, but the current check
function has been asynchronous since 4.0.0.
To implement the ESLint plugin, we should support the synchronous version of check
, which is named checkSync
.
I'm considering how to implement checkSync
.
Node.js has spawnSync
, so we can implement it by spawning recheck
CLI.
However, it may be slow when it spawns a new process on each checking, and it is hard to keep the implementation simple if it supports async/sync implementation in the same code base.
For now, implementing it by using Scala.js build looks better to me. It is simple and fast enough.
Since the revision bump from 4.4.1 to 4.4.2 the library fails on Node 14, due to a:
SyntaxError: Unexpected token '||='
The ||=
logical or statement was only introduced in Node 15, see [1]. After downgrading to 4.4.1, the library started to work fine again.
Downgrade to 4.4.1.
Simply stated, the document of recheck
is poor and not so useful.
We need to provide the following contents for users in the document:
recheck
eslint
pluginrecheck
algorithm explanation
'automaton'
algorithm'fuzz'
algorithm'hybrid'
algorithmThere is an error with this repository's Renovate configuration that needs to be fixed. As a precaution, Renovate will stop PRs until it is resolved.
Location: renovate.json
Error type: The renovate configuration file contains some invalid settings
Message: Invalid configuration option: regexManagers[0].depName, Regex Manager contains disallowed fields: depName, depType, Regex Manager contains disallowed fields: depType, Regex Manager contains disallowed fields: depType
native-build
job is flaky. Sometimes, builds are failed:
I'm not sure why it is caused, however many builds are succeeded, so it is needed to retry native-build
job.
We can use nick-invision/retry
action for retrying a job.
The current implementation has the "recall" problem.
In other words, because the real matching implementation does some optimization, the generated attack string may not work.
To prevent such a case, we consider adding a recall validation phase to the implementation, which runs the real program and checks whether or not the attack string works.
Still got false positive of fuzz on a project containing many regular expressions.
9:7 error Found a ReDoS vulnerable RegExp (2nd degree polynomial (fuzz)) redos/no-vulnerable
✖ 1 problem (1 error, 0 warnings)
webpack 5.73.0 compiled with 1 error in 213135 ms
That error appears in different files each time. I've set attackTimeout to null (#447) but the error doesn't disappear. Any other workarounds?
On Apple processor chips m1/m2 ARM64, it seems recheck fallsback to java implementation.
While it achieves the end goal, I was wondering if you can provide native ARM64 binaries or even use x64 emulation (unclear if that would be better than java runtime)
Hey so I'm trying to write a little CLI around this where a user can pass in a glob pattern of files to be matched, and it will find the files, loop over the lines in said files to find regexes, and finally test those against this checker.
So far so good, everything is working - however I can't get it to come up with a positive match although I've verified two results in my test file should trigger a positive (i.e. "vulnerable") match.
Here's my two test regexes and the output of running check(testRegex)
on them:
1. /^([a-zA-Z0-9-_@]+|\.\/)+\.(png|jpg|jpeg|pdf)$/m
{
source: '/^([a-zA-Z0-9-_@]+|\\.\\/)+\\.(png|jpg|jpeg|pdf)$/m',
flags: '',
status: 'safe',
checker: 'automaton',
complexity: { type: 'linear', summary: 'linear', isFuzz: false }
}
2. /^(a|a)*$/
{
source: '/^(a|a)*$/',
flags: '',
status: 'safe',
checker: 'automaton',
complexity: { type: 'linear', summary: 'linear', isFuzz: false }
}
I see on the first one in "source" it seems to have done some escaping of the backslashes itself, but I pasted both the escaped and unescaped version into your online checker, and they both came back vulnerable every single time, no matter which checker I used (fuzz or automaton).
Do I need to set any flags or anything in the second parameter of the check()
function? I didn't see any examples of flags or anything that could be set there.
Thanks for this cool checker!
When the runtine environment is busy due to another concurrent build task, the recheck sometimes reports a false positive such as the 2nd degree polynomial (fuzz)
.
Setting recallTimeout
or seedingTimeout
to null hides errors. That setting just enables unlimited checking, right?
https://github.com/falsandtru/securemark/blob/v0.274.2/.eslintrc.json
/a+$/
: Found a ReDoS vulnerable RegExp (2nd degree polynomial)
Remove those settings.
regex \bPREFIX\b(?=([ \t]*))\1[^,\s]+(?=((?:[ \t]*,[ \t]*[^,\s]+)*[\t ]*\bSUFFIX\b))\2
is reported as polynomial. I tried with the attack string, it does come linear to input length , here around 7700 steps . regex saved here with attack string input here. Please see ...
(https://regex101.com/r/kh6Nhh/1)
not sure
Config
takes a context
value, and context
is sideeffectful, so Config
is sideeffectful too.
However, we feel Config
has no sideeffect intuitively. We want to fix Config
as sideeffect-less.
Parameter
as sideeffect-less version of Config
Parameter
instead of Config
eslint-plugin-redos
is managed in another repository MakeNowJust-Labo/eslint-plugin-redos.
However this plugin implementation depends on recheck, so we want to manage this here.
Three steps.
Hi,
I wish to package recheck for debian.
Could you document how to rebuild from stratch ?
Bastien (rouca)
eslint-plugin-redos
, Dependabot opened upgrade PRs for v4.4.2 of the plugin.||=
operator on L22 of lib/main.js:for (var prop in b ||= {})
engines
field in package.json to accurately reflect the node version support.When configuring ESLint, one currently has to do this:
"plugins": ["redos"],
"rules": {
"redos/no-vulnerable": "error"
}
I t would be nice to use a very common config functionality of ESLint where both the plugin and the rule is loaded only once.
Add an ESLint config to esling-plugin-redos and let us specify it like:
"extends": [
"plugin:redos/recommended"
],
Read more at https://eslint.org/docs/latest/developer-guide/working-with-plugins#configs-in-plugins (overview at https://stackoverflow.com/a/54522973/1853417)
Platforms supported by recheck
CLI are x64 only on Windows/macOS/Linux.
To support other platforms, we can provide jar
package and run it with java
installed in a user machine.
jar
version of NPM package.jar
package.java
runner in agent
implementation.Playground report a false postive in fuzz mode.
Here is the input regex
/(?=(<table))\1(?=(\s*))\2(?<tableAttrs>(?:(?![>])[^])*)(?=(>))\4(?<tableChildren>(?=((?:(?![<])[^])*))\6)(?=(<\/table>))\7/
Log:
parse: start
parse: finish
pattern: /(?=(<table))\1(?=(\s*))\2(?<tableAttrs>(?:(?![>])[^])*)(?=(>))\4(?<tableChildren>(?=((?:(?![<])[^])*))\6)(?=(<\/table>))\7/
fuzz: start (usesAcceleration: false)
fuzz: seeding start (seeder: static)
automaton: EpsNFA construction
state size: 143
alphabet size: 10
automaton: OrderedNFA construction
state size: 39
alphabet size: 10
fuzz: seeding finish
size: 260
fuzz: iteration 1
traces: 100
max: '<table>\t<' (steps: 29, rate: 3.2222222222222223)
fuzz: attack start (status: limit)
string: '/' + '<table'.repeat(168) + '<>'.repeat(159) + '<'
fuzz: attack (exponential)
fuzz: attack (polynomial: 4)
fuzz: attack succeeded (status: timeout)
string: '/' + '<table'.repeat(269) + '<>'.repeat(260) + '<'
recall: code
const re = new RegExp('(?=(<table))\\1(?=(\\s*))\\2(?<tableAttrs>(?:(?![>])[^])*)(?=(>))\\4(?<tableChildren>(?=((?:(?![<])[^])*))\\6)(?=(<\\/table>))\\7', '');
const input = '/' + '<table'.repeat(269) + '<>'.repeat(260) + '<';
const start = Date.now();
re.exec(input);
const end = Date.now();
console.log(Number(end - start).toString());
The following script is to check a simple regexp. It prints a safe
result, but it is not terminated after the printing.
const { check } = require('recheck');
(async () => {
console.log((await check('a', '')).status);
})();
The reason of this bug is that calling subprocess.unref
is missing.
We should count running checks and it calls unref
correctly when all checks are done.
Renovate is a tool to update dependency versions automatically. It is hard to follow NPM package version update. We want to use such a tool.
Having this regex in a file takes several seconds when running ESLint using "plugin:redos/recommended"
.
const re = /cert\.pem: (-----BEGIN CERTIFICATE-----[\S\n]+-----END CERTIFICATE-----)/
I assume this is since in ESLint you have to use checkSync()
? Is there any way to speed this up?
The main problem is that e.g. in editors like VS Code where most have ESLint run on save (or even when writing code), having something take seconds is not managable as it halts DX experience completely.
Currently recheck
NPM package is written in usual JavaScript without statically type checking.
Static type checking is an important method to reduce bugs in a project.
We want to adopt this, and TypeScript is the best tool for type checking in JavaScript today.
Three steps.
esbuild
settings to transpile TypeScript.https://makenowjust-labs.github.io/recheck/docs/usage/as-javascript-library/ mentions:
There is the timeout parameter to specify timeout seconds. Please use this instead of the manual way.
There are two problems here:
AbortController
instead of the timeout
parameter? If so the text should be re-phrased. If not, it is hard to understand what the sentence is trying to say.Activating the cache in eslint-plugin-redos
like documented in the recheck docs causes an eslint validation error.
Configuration for rule "redos/no-vulnerable" is invalid:
Value {"cache":true} should NOT have additional properties.
.eslintrc
plugins: ['redos'],
rules: {
'redos/no-vulnerable': ['error', { cache: true }],
}
Example on stackblitz.com
(?)
This issue lists Renovate updates and detected dependencies. Read the Dependency Dashboard docs to learn more.
These problems occurred while renovating this repository. View logs.
Warning
Renovate failed to look up the following dependencies: Failed to look up sbt-package package org.scala-js:scalajs-java-securerandom_2.13
, Failed to look up sbt-package package io.circe:circe-scalajs_2.13
.
Files affected: build.sbt
These updates are pending. To force PRs open, click the checkbox below.
These updates have all been created already. Click a checkbox below to force a retry/rebase of any.
.github/workflows/main.yml
actions/checkout v4
coursier/setup-action v1
actions/cache v4
actions/cache v4
actions/upload-artifact v4
actions/upload-artifact v4
actions/checkout v4
coursier/setup-action v1
actions/cache v4
actions/cache v4
actions/checkout v4
actions/setup-node v4
actions/checkout v4
coursier/setup-action v1
actions/setup-node v4
actions/cache v4
codecov/codecov-action v4
actions/checkout v4
actions/setup-node v4
actions/download-artifact v4
actions/download-artifact v4
codecov/codecov-action v4
actions/checkout v4
coursier/setup-action v1
actions/cache v4
actions/cache v4
actions/upload-artifact v4
actions/checkout v4
coursier/setup-action v1
actions/cache v4
actions/cache v4
actions/checkout v4
coursier/setup-action v1
actions/setup-node v4
actions/cache v4
actions/cache v4
actions/download-artifact v4
actions/download-artifact v4
actions/download-artifact v4
actions/download-artifact v4
actions/download-artifact v4
actions/download-artifact v4
actions/checkout v4
actions/download-artifact v4
actions/download-artifact v4
actions/download-artifact v4
actions/download-artifact v4
actions/download-artifact v4
softprops/action-gh-release v2
actions/checkout v4
actions/setup-node v4
actions/download-artifact v4
actions/upload-pages-artifact v3
actions/deploy-pages v4
ubuntu 22.04
ubuntu 22.04
ubuntu 22.04
ubuntu 22.04
ubuntu 22.04
ubuntu 22.04
ubuntu 22.04
ubuntu 22.04
ubuntu 22.04
.github/workflows/scala-steward.yml
scala-steward-org/scala-steward-action v2
ubuntu 22.04
.github/workflows/update-changelog.yaml
actions/checkout v4
actions/github-script v7
ubuntu 22.04
package.json
lerna 8.1.2
packages/eslint-plugin-redos/package.json
@types/eslint 8.56.10
@types/find-cache-dir 5.0.0
@types/jest 29.5.12
@types/node 20.12.10
esbuild 0.21.1
esbuild-jest 0.5.0
esbuild-register 3.5.0
eslint 8.57.0
jest 29.7.0
prettier 3.2.5
rimraf 5.0.5
typescript 5.4.5
eslint >= 3
node >=14
packages/recheck-jar/package.json
packages/recheck-linux-x64/package.json
packages/recheck-macos-arm64/package.json
packages/recheck-macos-x64/package.json
packages/recheck-windows-x64/package.json
packages/recheck/package.json
synckit 0.9.0
@types/jest 29.5.12
@types/node 20.12.10
esbuild 0.21.1
esbuild-jest 0.5.0
esbuild-register 3.5.0
jest 29.7.0
prettier 3.2.5
rimraf 5.0.5
typescript 5.4.5
node >=18
website/package.json
@algolia/client-search ^4.17.0
@docusaurus/core 3.3.2
@docusaurus/module-type-aliases 3.3.2
@docusaurus/plugin-ideal-image 3.3.2
@docusaurus/preset-classic 3.3.2
@mdx-js/react 3.0.1
clsx 2.1.1
prism-react-renderer 2.3.1
prop-types 15.8.1
react 18.3.1
react-dom 18.3.1
react-hook-form 7.51.4
react-loadable ^5.5.0
react-loading 2.0.3
@tsconfig/docusaurus 2.0.3
typescript 5.4.5
.scalafmt.conf
org.scalameta:scalafmt-core_2.13 3.8.1
build.sbt
com.olegpy:better-monadic-for_2.13 0.3.1
com.olegpy:better-monadic-for_2.13 0.3.1
com.olegpy:better-monadic-for_2.13 0.3.1
com.olegpy:better-monadic-for_2.13 0.3.1
com.olegpy:better-monadic-for_2.13 0.3.1
com.olegpy:better-monadic-for_2.13 0.3.1
com.olegpy:better-monadic-for_2.13 0.3.1
com.olegpy:better-monadic-for_2.13 0.3.1
build.sbt
scala 2.13.13
com.olegpy:better-monadic-for 0.3.1
org.scalameta:munit 0.7.29
org.scala-js:scalajs-java-securerandom 1.0.0
com.olegpy:better-monadic-for 0.3.1
org.scalameta:munit 0.7.29
org.scala-js:scalajs-java-securerandom 1.0.0
com.olegpy:better-monadic-for 0.3.1
org.scalameta:munit 0.7.29
org.scala-js:scalajs-java-securerandom 1.0.0
com.olegpy:better-monadic-for 0.3.1
org.scalameta:munit 0.7.29
org.scala-js:scalajs-java-securerandom 1.0.0
com.lihaoyi:fastparse 3.1.0
com.olegpy:better-monadic-for 0.3.1
org.scalameta:munit 0.7.29
org.scala-js:scalajs-java-securerandom 1.0.0
io.circe:circe-core 0.14.7
com.olegpy:better-monadic-for 0.3.1
org.scalameta:munit 0.7.29
org.scala-js:scalajs-java-securerandom 1.0.0
io.circe:circe-scalajs 0.14.6
com.olegpy:better-monadic-for 0.3.1
org.scalameta:munit 0.7.29
org.scala-js:scalajs-java-securerandom 1.0.0
com.monovore:decline 2.4.1
io.circe:circe-core 0.14.7
io.circe:circe-generic 0.14.7
io.circe:circe-parser 0.14.7
com.olegpy:better-monadic-for 0.3.1
org.scalameta:munit 0.7.29
project/build.properties
sbt/sbt 1.10.0
project/build.sbt
com.ibm.icu:icu4j 75.1
project/plugin.sbt
ch.epfl.scala:sbt-scalafix 0.12.1
com.eed3si9n:sbt-assembly 2.2.0
com.github.sbt:sbt-ci-release 1.5.12
org.portable-scala:sbt-scalajs-crossproject 1.3.2
org.scala-js:sbt-scalajs 1.16.0
org.scalameta:sbt-native-image 0.3.4
org.scalameta:sbt-scalafmt 2.5.2
org.scoverage:sbt-scoverage 2.0.11
.scalafmt.conf
scalafmt 3.8.1
https://devina.io/redos-checker
Regex: \.loadUrl\(.{0,48}getExternalStorageDirectory\(
works fine - > Safe to use
Regex: \.loadUrl\(.{0,49}getExternalStorageDirectory\(
times out. - > Oh no! The checker timed out
Currently recheck
only supports JavaScript. But, there are many dialects of regular expression in the real world.
We should support other dialects in recheck
.
Hi!
This is my first time using recheck. When bundling, the output seems to turn out to be 6.8mb for just this package.
Does this package really need to bundle all what it's currently bundling? Is there something one can do reduce the bundle size?
Playground throws the next error if you change the timeout parameter to 20000 and run it.
61b0b527-2b7e-4326-827c-37089aa32669:6 Uncaught io.circe.DecodingFailure$$anon$3: Duration: DownField(timeout)
at _u.codes$quine$labs$recheck$codec$package$$$anonfun$decodeDuration$1__Lio_circe_HCursor__s_util_Either (blob:https://makenowjust-labs.github.io/61b0b527-2b7e-4326-827c-37089aa32669:6:29078)
at _u.codes$quine$labs$recheck$codec$package$$$anonfun$decodeParameters$1__Lio_circe_HCursor__Lio_circe_Decoder__s_util_Either (blob:https://makenowjust-labs.github.io/61b0b527-2b7e-4326-827c-37089aa32669:6:26837)
at Lg.check__T__T__sjs_js_$bar__sjs_js_Any (blob:https://makenowjust-labs.github.io/61b0b527-2b7e-4326-827c-37089aa32669:3:3029)
at tK (blob:https://makenowjust-labs.github.io/61b0b527-2b7e-4326-827c-37089aa32669:62:702997)
at nK (blob:https://makenowjust-labs.github.io/61b0b527-2b7e-4326-827c-37089aa32669:62:703071)
at blob:https://makenowjust-labs.github.io/61b0b527-2b7e-4326-827c-37089aa32669:62:703213
at blob:https://makenowjust-labs.github.io/61b0b527-2b7e-4326-827c-37089aa32669:1:532
_u.codes$quine$labs$recheck$codec$package$$$anonfun$decodeDuration$1__Lio_circe_HCursor__s_util_Either @ 61b0b527-2b7e-4326-827c-37089aa32669:6
_u.codes$quine$labs$recheck$codec$package$$$anonfun$decodeParameters$1__Lio_circe_HCursor__Lio_circe_Decoder__s_util_Either @ 61b0b527-2b7e-4326-827c-37089aa32669:6
Lg.check__T__T__sjs_js_$bar__sjs_js_Any @ 61b0b527-2b7e-4326-827c-37089aa32669:3
tK @ 61b0b527-2b7e-4326-827c-37089aa32669:62
nK @ 61b0b527-2b7e-4326-827c-37089aa32669:62
(anonymous) @ 61b0b527-2b7e-4326-827c-37089aa32669:62
(anonymous)
NPM package source codes are not formatted by any tools.
Prettier is an opinionated code formatter for JavaScript/TypeScript.
We can accept these styles, so we want to use prettier in our project.
prettier
to the project.Since 4.0.0, the @makenowjust-labo/recheck
package has been renamed to recheck
.
Some packages depend on the @makenowjust-labo
package.
We need to announce the new version release and please them switch to the new recheck
.
Two steps.
@makenowjust-labo/recheck
.Currently gh-pages
is not updated because
It is a bug simply. We should fix it.
Perhaps the following line is the reason.
The correct expression is github.ref_name == 'main'
...?
native-build
job is slow and flaky, so we run it only on release.
Update .github/workflows/main.yaml
.
It would be nice if https://makenowjust-labs.github.io/recheck/docs/usage/as-eslint-plugin/ mentions that the ESLint plugin uses checkSync
due to a limitation in ESLint. And possibly also link to the issue in ESLint so people are aware what the limitation is.
I am fine with this being closed directly if not wanted as it is an implementation detail, but it might be nice for users wondering. Maybe even more important if this package becomes the default in eslint-community/eslint-plugin-security#28.
At one time, we consider the small superscript representation for attack string seems good pretty printing style. However, it is hard to read and not interpretable directly. Thus, we shall propose a new pretty printing style for attack string (and witness of automaton checker).
The style uses JavaScript notation simply. For example, 'fizz'⁴ 'buzz'
is now displayed as 'fizz'.repeat(4) + 'buzz'
. It may seem lengthly and uninteresting, but it is easy readable and to use JavaScript eval
to obtain the actual attack string.
#toString
methodA declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.