Yeting Li and Yecheng Sun, Institute of Information Engineering, Chinese Academy of Sciences and School of Cyber Security, University of Chinese Academy of Sciences; Zhiwu Xu, College of Computer Science and Software Engineering, Shenzhen University; Haiming Chen, Institute of Software, Chinese Academy of Sciences; Xinyi Wang, Hengyu Yang, and Huina Chao, Institute of Information Engineering, Chinese Academy of Sciences and School of Cyber Security, University of Chinese Academy of Sciences; Cen Zhang, School of Computer Science and Engineering, Nanyang Technological University; Yang Xiao, Yanyan Zou, Feng Li, and Wei Huo, Institute of Information Engineering, Chinese Academy of Sciences and School of Cyber Security, University of Chinese Academy of Sciences
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.
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
author = {Yeting Li and Yecheng Sun and Zhiwu Xu and Haiming Chen and Xinyi Wang and Hengyu Yang and Huina Chao and Cen Zhang and Yang Xiao and Yanyan Zou and Feng Li and Wei Huo},
title = {{VULCANBOOST}: Boosting {ReDoS} Fixes through Symbolic Representation and Feature Normalization},
booktitle = {34th USENIX Security Symposium (USENIX Security 25)},
year = {2025},
isbn = {978-1-939133-52-6},
address = {Seattle, WA},
pages = {4463--4479},
url = {https://www.usenix.org/conference/usenixsecurity25/presentation/li-yeting},
publisher = {USENIX Association},
month = aug
}
