Regular expressions (regexes) are widely used in different fields of computer science. However, the Regular expression Denial of Service (ReDoS) vulnerability forms a class of common and serious algorithmic complexity attacks.
The existing ReDoS-vulnerability detection tools have defects of low precision or low recall rate due to the lack of formal and comprehensive detection conditions of ReDoS-vulnerabilities.
A research team led by Prof. Chen Haiming from the Institute of Software of the Chinese Academy of Sciences developed a high-performance detection tool for ReDoS-vulnerability. Their study was issued at USENIX Security Symposium 2021. Through examining 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 developed 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.
In detecting the publicly-confirmed practical vulnerabilities in Common Vulnerabilities and Exposure (CVE), ReDoSHunter can detect 100% ReDoS-related CVEs.
In their previous study, Chen’s team proposed a programming-by-example framework, FlashRegex, for generating anti-ReDoS regexes by either synthesizing or repairing them from given examples. It is the first framework that integrates regex synthesis and repair with the awareness of ReDoS-vulnerabilities.
FlashRegex can efficiently generate or repair regexes without ReDoS-vulnerabilities, and there’re 0 ReDoS-vulnerabilities in repaired regexes. The study, titled “FlashRegex: deducing anti-ReDoS regexes from examples,” was issued at ASE 2020.