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 lacking 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 high-performance detection tool for ReDoS-vulnerability.
Their study was issued on 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 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 entitled "FlashRegex: deducing anti-ReDoS regexes from examples" was issued on ASE 2020.
