These tools not only solved the limitations of current ReDoS tools, but also significantly enhanced and surpassed the performance of the state-of-the-art tools, serving as vital tools of efficiency and convenience in ReDoS-vulnerability detection, exploitation, repair and defense.

Regular expressions (regexes) are widely used in different fields of computer science, however the ReDoS-vulnerability forms a class of common and serious algorithmic complexity attacks, and there’s a growing tendency of it in recent years. However, due to the unsolved challenging problem of giving formal and comprehensive detection conditions of ReDoS-vulnerabilities, the existing ReDoS-vulnerability detection tools all have defects of low precision or low recall rate.

To address the problem above, by close examination of massive ReDoS-vulnerable regexes, Chen’s team proposed the ReDoS-vulnerability detection conditions, namely the ReDoS-vulnerability patterns, and gave the necessary conditions for triggering these patterns formally. Based on this, they proposed a static and dynamic combined ReDoS-vulnerability detection algorithm, and designed ReDoSHunter, the ReDoS-vulnerability detection tool.

ReDoSHunter can pinpoint multiple root causes in a vulnerable regex, prescribe the degree of the vulnerability and generate attack-triggering strings, etc. It has achieved 100% precision and recall ratio on datasets of Corpus, RegExLib and Snort with 37,651 regexes. On detecting the publicly-confirmed practical vulnerabilities in Common Vulnerabilities and Exposure (CVE), ReDoSHunter can detect 100% ReDoS-related CVEs, comparing with 60.00%, the highest achieved by the state-of-the-art works. The excellent performance of ReDoSHunter makes Institute of Software currently the first rank internationally in the quantity of ReDoS-vulnerability disclosures of CVEs.

ReDoSHunter has also been applied in open source projects. For example, it has been used in ReDoS detection of open source projects like Python source code, CKEditor and prismjs. In the meantime they cooperate with Synk to disclose ReDoS-vulnerabilities efficiently. There has been 27 unrevealed ReDoS-vulnerabilities assigned CVEs up to now, and they have received official thanks from multiple projects.

Related research results entitled "ReDoSHunter: a combined static and dynamic approach for regular expression DoS detection" have been accepted by USENIX Security 2021.

An Instance of ReDoSHunter Detection Process

Comparison of the Overall Effectiveness over Four Popular Regex Engines on the Benchmarks with 37,651 Regexes.

The current synthesizing and repair works on regexes all neglected ReDoS-vulnerabilities, therefore their results are vulnerable towards ReDoS attacks.

To settle this issue, Chen’s team proposed a programming-by-example framework, FlashRegex, for generating anti-ReDoS regexes by either synthesizing or repairing from given examples. It is the first framework that integrates regex synthesis and repair with the awareness of ReDoS-vulnerabilities. They presented novel algorithms to deduce anti-ReDoS regexes by reducing the ambiguity of these regexes and by using Boolean Satisfiability (SAT) or Neighborhood Search (NS) techniques. To accelerate the process, the team used deterministic automata and a heuristic strategy called Local Constraints Strengthening (LCS), and implemented FlashRegex, the corresponding tool.

FlashRegex can efficiently generate or repair regexes without ReDoS-vulnerabilities, and there’re 0 ReDoS-vulnerabilities in repaired regexes, comparing to the incompleteness and low efficiency of traditional manual repair.

The Repair Procedure of FlashRegex

FlashRegex has been applied in open source projects to repair ReDoS-vulnerabilities, and was approved or acknowledged by maintainers of postccs, nltk and Python source code and a dozen of other projects along with Snyk.

The study entitled"FlashRegex: deducing anti-ReDoS regexes from examples" was accepted in ASE 2020.