Towards the Systematic Testing of Regular Expression Engines
New testing method analyzes 1,007 bugs and 156 CVEs to find memory safety defects in engines like PCRE.
A team of researchers from academia has introduced a new framework called ReTest, designed to systematically uncover bugs and vulnerabilities in the regular expression (regex) engines that power software across countless domains. Current testing methods like differential testing are problematic due to significant variations in regex syntax between dialects (e.g., POSIX vs. PCRE), while naive fuzzing often generates invalid inputs. ReTest addresses this by combining grammar-aware fuzzing to ensure high code coverage with metamorphic testing to create dialect-independent test oracles, moving beyond simple parser testing to probe deeper matching internals.
The researchers' work is grounded in extensive analysis, having surveyed 22 regex engines and studied 1,007 documented bugs and 156 Common Vulnerabilities and Exposures (CVEs) to understand common failure modes. They curated 16 metamorphic relations for regexes based on Kleene algebra principles to guide their testing. In preliminary evaluations on the widely-used PCRE engine, ReTest demonstrated a substantial improvement, achieving 3x higher edge coverage than existing fuzzing approaches and successfully identifying three previously unknown memory safety defects. The next steps involve refining the framework to help engine developers proactively identify critical bugs without being hampered by the lack of a consistent, cross-implementation standard for regex behavior.
- ReTest combines grammar-aware fuzzing and metamorphic testing, achieving 3x higher edge coverage on PCRE than prior methods.
- The research is based on an analysis of 1,007 regex engine bugs and 156 CVEs to characterize failure modes.
- The framework has already identified three new memory safety defects in its preliminary evaluation.
Why It Matters
Vulnerabilities in foundational components like regex engines can lead to widespread security flaws in software that depends on them.