npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

scslre

v0.3.0

Published

A library to find JS RegExp with super-linear worst-case time complexity for attack strings that repeat a single character.

Downloads

2,701,136

Readme

Single-character super-linear RegExps

what a name...

Actions Status npm

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.

Usage

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.

Documentation

For more information on the exact inputs and outputs of each function, see the full API documentation.

Limitations

Analysis

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

False negatives

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.

False positives

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.

Reports

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.

Exponential backtracking

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.