VULCANBOOST: Boosting ReDoS Fixes through Symbolic Representation and Feature Normalization

Regular expressions (regexes) are widely used in modern programming languages but are susceptible to ReDoS attacks due to the inefficiencies introduced by backtracking algorithms. Existing approaches for repairing ReDoS-vulnerable regexes struggle with supporting diverse character classes and extended features, often relying on test cases for repair guidance. In this paper, we introduce VULCANBOOST, a novel framework for repairing ReDoS-vulnerable regexes that addresses these challenges. VULCANBOOST leverages symbolic representation and feature normalization to simplify regex structures and repair them through DFA (Deterministic Finite Automaton) transformations, eliminating the need for test case-based repair. Our evaluation, conducted on a large dataset of 6,360 ReDoS-vulnerable regexes from real-world NPM projects, demonstrates that VULCANBOOST achieves a Test Coverage Repair Success Rate (TCRSR) of 93.95% and an Equivalence Repair Success Rate (ERSR) of 93.05%, outperforming existing methods. Moreover, we identify common vulnerability patterns from over 5,000 repaired regexes and summarize the top 100 repair patterns as open-source resources, offering valuable guidance to developers in enhancing the security and correctness of their regexes.