The trustworthy ReDoS checker
Home Page: https://makenowjust-labs.github.io/recheck/
License: MIT License
![renovate[bot] avatar](https://avatars.githubusercontent.com/in/2740?v=4 "renovate[bot]")
Currently recheck only supports JavaScript. But, there are many dialects of regular expression in the real world.
We should support other dialects in recheck.
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.
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
(?)
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
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?
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.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.1It is like this in 4.4.2 and 4.4.3 but in 4.4.1 it works.
No idea.
None.
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.
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.
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.
react, react-dom).github/workflows/main.yml
actions/checkout v4coursier/setup-action v1actions/cache v4actions/cache v4actions/upload-artifact v4actions/upload-artifact v4actions/checkout v4coursier/setup-action v1actions/cache v4actions/cache v4actions/checkout v4actions/setup-node v4actions/checkout v4coursier/setup-action v1actions/setup-node v4actions/cache v4codecov/codecov-action v4actions/checkout v4actions/setup-node v4actions/download-artifact v4actions/download-artifact v4codecov/codecov-action v4actions/checkout v4coursier/setup-action v1actions/cache v4actions/cache v4actions/upload-artifact v4actions/checkout v4coursier/setup-action v1actions/cache v4actions/cache v4actions/checkout v4coursier/setup-action v1actions/setup-node v4actions/cache v4actions/cache v4actions/download-artifact v4actions/download-artifact v4actions/download-artifact v4actions/download-artifact v4actions/download-artifact v4actions/download-artifact v4actions/checkout v4actions/download-artifact v4actions/download-artifact v4actions/download-artifact v4actions/download-artifact v4actions/download-artifact v4softprops/action-gh-release v2actions/checkout v4actions/setup-node v4actions/download-artifact v4actions/upload-pages-artifact v3actions/deploy-pages v4ubuntu 22.04ubuntu 22.04ubuntu 22.04ubuntu 22.04ubuntu 22.04ubuntu 22.04ubuntu 22.04ubuntu 22.04ubuntu 22.04.github/workflows/scala-steward.yml
scala-steward-org/scala-steward-action v2ubuntu 22.04.github/workflows/update-changelog.yaml
actions/checkout v4actions/github-script v7ubuntu 22.04
package.json
lerna 8.1.2packages/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.7esbuild 0.20.2esbuild-jest 0.5.0esbuild-register 3.5.0eslint 8.57.0jest 29.7.0prettier 3.2.5rimraf 5.0.5typescript 5.4.5eslint >= 3node >=14packages/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.7esbuild 0.20.2esbuild-jest 0.5.0esbuild-register 3.5.0jest 29.7.0prettier 3.2.5rimraf 5.0.5typescript 5.4.5node >=18website/package.json
@algolia/client-search ^4.17.0@docusaurus/core 3.2.1@docusaurus/module-type-aliases 3.2.1@docusaurus/plugin-ideal-image 3.2.1@docusaurus/preset-classic 3.2.1@mdx-js/react 3.0.1clsx 2.1.1prism-react-renderer 2.3.1prop-types 15.8.1react 18.2.0react-dom 18.2.0react-hook-form 7.51.3react-loadable ^5.5.0react-loading 2.0.3@tsconfig/docusaurus 2.0.3typescript 5.4.5
.scalafmt.conf
org.scalameta:scalafmt-core_2.13 3.8.1build.sbt
com.olegpy:better-monadic-for_2.13 0.3.1com.olegpy:better-monadic-for_2.13 0.3.1com.olegpy:better-monadic-for_2.13 0.3.1com.olegpy:better-monadic-for_2.13 0.3.1com.olegpy:better-monadic-for_2.13 0.3.1com.olegpy:better-monadic-for_2.13 0.3.1com.olegpy:better-monadic-for_2.13 0.3.1com.olegpy:better-monadic-for_2.13 0.3.1
build.sbt
scala 2.13.13com.olegpy:better-monadic-for 0.3.1org.scalameta:munit 0.7.29org.scala-js:scalajs-java-securerandom 1.0.0com.olegpy:better-monadic-for 0.3.1org.scalameta:munit 0.7.29org.scala-js:scalajs-java-securerandom 1.0.0com.olegpy:better-monadic-for 0.3.1org.scalameta:munit 0.7.29org.scala-js:scalajs-java-securerandom 1.0.0com.olegpy:better-monadic-for 0.3.1org.scalameta:munit 0.7.29org.scala-js:scalajs-java-securerandom 1.0.0com.lihaoyi:fastparse 3.1.0com.olegpy:better-monadic-for 0.3.1org.scalameta:munit 0.7.29org.scala-js:scalajs-java-securerandom 1.0.0io.circe:circe-core 0.14.6com.olegpy:better-monadic-for 0.3.1org.scalameta:munit 0.7.29org.scala-js:scalajs-java-securerandom 1.0.0io.circe:circe-scalajs 0.14.6com.olegpy:better-monadic-for 0.3.1org.scalameta:munit 0.7.29org.scala-js:scalajs-java-securerandom 1.0.0com.monovore:decline 2.4.1io.circe:circe-core 0.14.6io.circe:circe-generic 0.14.6io.circe:circe-parser 0.14.6com.olegpy:better-monadic-for 0.3.1org.scalameta:munit 0.7.29project/build.properties
sbt/sbt 1.9.9project/build.sbt
com.ibm.icu:icu4j 75.1project/plugin.sbt
ch.epfl.scala:sbt-scalafix 0.12.0com.eed3si9n:sbt-assembly 2.2.0com.github.sbt:sbt-ci-release 1.5.12org.portable-scala:sbt-scalajs-crossproject 1.3.2org.scala-js:sbt-scalajs 1.16.0org.scalameta:sbt-native-image 0.3.4org.scalameta:sbt-scalafmt 2.5.2org.scoverage:sbt-scoverage 2.0.11
.scalafmt.conf
scalafmt 3.8.1
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.Hi,
I wish to package recheck for debian.
Could you document how to rebuild from stratch ?
Bastien (rouca)
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.
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 ConfigParameter instead of ConfigHey 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!
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)
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)
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.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'...?
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)
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.
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 methodWhen 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).
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.
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.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());
Run recall code:
It seems cost 2ms to run instead of 2s
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.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.
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' algorithmhttps://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
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.
There 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 slow and flaky, so we run it only on release.
Update .github/workflows/main.yaml.
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.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.
React
A 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
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
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.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.