
Security News
Oracle Drags Its Feet in the JavaScript Trademark Dispute
Oracle seeks to dismiss fraud claims in the JavaScript trademark dispute, delaying the case and avoiding questions about its right to the name.
A library to find JS RegExp with super-linear worst-case time complexity for attack strings that repeat a single character.
what a name...
A library to find JS RegExp with super-linear worst-case time complexity for attack strings that repeat a single character.
The static analysis method implemented by this library focuses on finding attack string tuples where a single character is repeated. This major limitation allows the library to be fast while also offering decent support for backreferences and assertions.
This library is not intended as a full static analysis to guard against super-linear worst-case time complexity. It is meant to be as a supplementary analysis on top of existing general analysis methods that don't (or don't fully) support advanced regex features, or as a lightweight analysis on top of existing full (but heavyweight) analysis methods. Libraries that provide such general or near-full analysis are known as recheck and vuln-regex-detector. You may consider using these libraries as well.
This library exports only a single function, analyse
, which takes a RegExp literal and returns a list of reports that show the quantifiers causing super-linear worst-case time complexity.
For more information on the exact inputs and outputs of each function, see the full API documentation.
This library is implemented using a very limited static analysis method that can only find attack strings where a single character is repeated. Attack strings are generated from a tuple (x,y,z) such that every string s = xynz (or x + y.repeat(n) + z
for JS folks) takes O(np) or O(2n) many steps to reject, p>1. This analysis method can only find tuples where y is a single character. E.g. the polynomial backtracking in /^(ab)*(ab)*$/
for (x,y,z) = ("", "ab", "c") cannot be detected by this library because y is not a single character.
However, this limitation allows the static analysis method to be quick and to provide good (but not perfect) support for backreferences and assertions (e.g. \b
, (?<!ba+)
).
The analysis method primarily searches for polynomial backtracking. Finds of exponential backtracking are only a byproduct. Because of this, not all causes of super-linear worst-case time complexity are found.
This library doesn't actually search for the whole tuple (x,y,z); it only searches for y and assumes that adequate values for x and z can be found. A single-character approximation of the suffix z will be computed and accounted for but false positives are still possible.
There are 3 different types of reports that each indicate a different type of cause for the super-linear worst-case time complexity. All are explained in the documentation of their types.
While most reports show polynomial backtracking, some report exponential backtracking. Exponential backtracking is a lot more dangerous and can easily be exploited for ReDoS attacks.
While other reports may be dismissed, all reports of exponential backtracking must be fixed.
All reports with exponential: true
report exponential backtracking.
0.3.0 (2023-09-05)
refa
, regexp-ast-analysis
.v
flag.FAQs
A library to find JS RegExp with super-linear worst-case time complexity for attack strings that repeat a single character.
The npm package scslre receives a total of 391,198 weekly downloads. As such, scslre popularity was classified as popular.
We found that scslre demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
Oracle seeks to dismiss fraud claims in the JavaScript trademark dispute, delaying the case and avoiding questions about its right to the name.
Security News
The Linux Foundation is warning open source developers that compliance with global sanctions is mandatory, highlighting legal risks and restrictions on contributions.
Security News
Maven Central now validates Sigstore signatures, making it easier for developers to verify the provenance of Java packages.