Elamur Research⌕
☰
home / papers / 2026 / Repairing Regex Vulnerabilities via Localization-Guided Instructions

Repairing Regex Vulnerabilities via Localization-Guided Instructions

Paper · 2026 · Sicheol Sung, Joonghyuk Hahn and Yo-Sub Han

Summary

Regexes underpin input validation and parsing, but some of them backtrack catastrophically and can be exploited for regular expression denial of service (ReDoS). Existing automatic fixes have opposite weaknesses. Rule-based tools are precise but brittle on unfamiliar or complex patterns. Synthesis-based tools need many examples. LLMs generalize well but often break regex syntax or meaning. The authors propose localized regex repair (LRR), a hybrid pipeline that separates finding the problem from fixing it:

  1. A deterministic symbolic analyzer, built on heuristics from existing rule-based repair tools, marks the exact vulnerable sub-pattern.
  2. An LLM receives this location together with few-shot chain-of-thought demonstrations. Each demonstration explains why the marked segment is dangerous and how a rule-based tool would fix it.
  3. The LLM then produces a safe, semantically equivalent replacement.

Across several open and proprietary LLMs, LRR raises the repair rate by 15.4 percentage points over the state of the art while keeping high semantic similarity to the original regexes. This shows that symbolic localization makes LLM-based repair markedly more dependable.

Key points

  • The localizer detects four kinds of vulnerability: quantifiers placed inside other quantifiers (NQ), disjunctions with overlapping branches under a quantifier (QOD), overlapping adjacent sub-patterns under a quantifier (QOA), and patterns that begin with a large quantifier (SLQ).
  • Tested LLMs include Qwen3 (e.g., Qwen3-8B), Llama3.1, Gemma3-12B, Phi4-14B, GPT-oss-20B and GPT5. The baselines are RegexScalpel and Remedy.
  • Semantic similarity is measured with Jaccard. Safety is checked dynamically with ReDoSHunter, so there is no formal invulnerability guarantee.
  • RegexScalpel reaches about 99.91% precision because it never widens the matched language. LRR trades a small loss of precision for removing more vulnerabilities.
  • In case studies, LLMs use contextual cues (for example, recognizing git diff headers) to bound quantifiers sensibly. Failure analysis of Phi4 shows two main error types:
    • incomplete fixes, where only part of the vulnerability is removed;
    • semantic errors, caused by format hallucinations such as double escaping or by mistaking negative look-aheads for positive ones.
  • Code: github.com/cdltlehf/LRR

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksInformation Systems · 1,437 worksSoftware · 92 works

Cite

Cite as Sicheol Sung, Joonghyuk Hahn and Yo-Sub Han. 2026. Repairing Regex Vulnerabilities via Localization-Guided Instructions. Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.eacl-long.379

@inproceedings{sung2026repairing,
  title = {{Repairing Regex Vulnerabilities via Localization-Guided Instructions}},
  author = {Sicheol Sung, Joonghyuk Hahn and Yo-Sub Han},
  booktitle = {Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.eacl-long.379},
  url = {https://doi.org/10.18653/v1/2026.eacl-long.379}
}

References

50 references, 12 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Marah Abdin, Jyoti Aneja, Harkirat Behl, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, Michael Harrison, Russell J Hewett, Mojan Javaheripi, Piero Kauffmann, and 1 others. 2024. Phi-4 technical report. arXiv preprint arXiv:2412.08905.
  2. Sandhini Agarwal, Lama Ahmad, Jason Ai, Sam Altman, Andy Applebaum, Edwin Arbus, Rahul K. Arora, Yu Bai, Bowen Baker, Haiming Bao, Boaz Barak, Ally Bennett, Tyler Bertao, Nivedita Brett, Eugene Brevdo, Greg Brockman, Sébastien Bubeck, Che Chang, Kai Chen, and 105 others. 2025. gpt-oss-120b & gpt-oss…
  3. Masudul Hasan Masud Bhuiyan, Berk Çakar, Ethan H Burmane, James C Davis, and Cristian-Alexandru Staicu. 2024. SoK: A literature and engineering review of regular expression denial of service. arXiv preprint arXiv:2406.11618. — [arXiv:2406.11618](https://arxiv.org/abs/2406.11618) find
  4. Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter,… — Language Models are Few-Shot Learners
  5. Carl Chapman and Kathryn T. Stolee. 2016. Exploring regular expression usage and context in Python. In Proceedings of the 25th International Symposium on Software Testing and Analysis, pages 282–293. find
  6. Nariyoshi Chida and Tachio Terauchi. 2022. Repairing DoS vulnerability of real-world regexes. In 2022 IEEE Symposium on Security and Privacy (SP), pages 2060–2077. find
  7. Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, and… — PaLM: Scaling Language Modeling with Pathways
  8. Corinna Cortes and Mehryar Mohri. 2008. Learning with weighted transducers. In Proceedings of the 7th International Workshop on Finite State Methods and Natural Language Processing, pages 14–22. find
  9. James C. Davis, Louis G. Michael IV, Christy A. Coghlan, Francisco Servant, and Dongyoon Lee. 2019. Why aren’t regular expressions a lingua franca? An empirical study on the re-use and portability of regular expressions. In Proceedings of the ACM Joint Meeting on European Software Engineering Confer… find
  10. DeepSeek-AI, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z. F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, and 81 others. 2025. DeepSeek-R1: Incentivizing reasoning capability in llm…
  11. Dominik D Freydenberger. 2013. Extended regular expressions: Succinctness and decidability. Theory of Computing Systems, 53(2):159–193. find
  12. Saibo Geng, Berkay Döner, Chris Wendler, Martin Josifoski, and Robert West. 2024. Sketch-guided constrained decoding for boosting blackbox large language models without logit access. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics, ACL, pages 234–245. find
  13. Sk Adnan Hassan, Zainab Aamir, Dongyoon Lee, James C. Davis, and Francisco Servant. 2023. Improving developers’ understanding of regex denial of service tools through anti-patterns and fix strategies. In 2023 IEEE Symposium on Security and Privacy (SP), pages 1238–1255. find
  14. Eran Hirsch, Aviv Slobodkin, David Wan, Elias Stengel-Eskin, Mohit Bansal, and Ido Dagan. 2025. LAQuer: Localized attribution queries in content-grounded generation. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2025, Vienna,…
  15. Xijie Huang, Li Lyna Zhang, Kwang-Ting Cheng, Fan Yang, and Mao Yang. 2024. Fewer is more: Boosting math reasoning with reinforced context pruning. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, EMNLP, pages 13674–13695. find
  16. Sewon Min, Mike Lewis, Luke Zettlemoyer, and Hannaneh Hajishirzi. 2022a. MetaICL: Learning to learn in context. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL, pages 2791–2809. find
  17. Louis G. Michael IV, James Donohue, James C. Davis, Dongyoon Lee, and Francisco Servant. 2019. Regexes are hard: Decision-making, difficulties, and risks in programming regular expressions. In 34th IEEE/ACM International Conference on Automated Software Engineering, ASE 2019, San Diego, CA, USA, Nov… find
  18. Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2022b. Rethinking the role of demonstrations: What makes in-context learning work? In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP, pages 11048–…
  19. Aishwarya Kamath, Johan Ferret, Shreya Pathak, Nino Vieillard, Ramona Merhej, Sarah Perrin, Tatiana Matejovicova, Alexandre Ramé, Morgane Rivière, Louis Rouillard, Thomas Mesnard, Geoffrey Cideron, Jean-Bastien Grill, Sabela Ramos, Edouard Yvinec, Michelle Casbon, Etienne Pot, Ivo Penchev, Gaël Liu,… find
  20. OpenAI. 2025. GPT-5 System Card. find
  21. Yeting Li, Zixuan Chen, Jialun Cao, Zhiwu Xu, Qiancheng Peng, Haiming Chen, Liyuan Chen, and Shing-Chi Cheung. 2021. ReDoSHunter: A combined static and dynamic approach for regular expression DoS detection. In 30th USENIX Security Symposium (USENIX Security 21), pages 3847–3864. find
  22. Yeting Li, Yecheng Sun, Zhiwu Xu, Jialun Cao, Yuekang Li, Rongchen Li, Haiming Chen, Shing-Chi Cheung, Yang Liu, and Yang Xiao. 2022. RegexScalpel: Regular expression denial of service (ReDoS) defense by Localize-and-Fix. In 31st USENIX Security Symposium (USENIX Security 22), pages 4183– 4200, Bost… find
  23. Yeting Li, Zhiwu Xu, Jialun Cao, Haiming Chen, Tingjian Ge, Shing-Chi Cheung, and Haoren Zhao. 2020. Flashregex: Deducing anti-ReDoS regexes from examples. In Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering, pages 659–671. find
  24. Yucheng Li, Bo Dong, Frank Guerin, and Chenghua Lin. 2023. Compressing context to enhance inference efficiency of large language models. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, EMNLP, pages 6342– 6353.
  25. Tingwen Liu, Yong Sun, Alex X. Liu, Li Guo, and Binxing Fang. 2012. A prefiltering approach to regular expression matching for network security systems. In Proceedings of the 10th International Conference on Applied Cryptography and Network Security, pages 363–380. find
  26. Robert McLaughlin, Fabio Pagani, Noah Spahn, Christopher Kruegel, and Giovanni Vigna. 2022. Regulator: Dynamic analysis to detect ReDoS. In 31st USENIX Security Symposium (USENIX Security 22), pages 4219–4235. find
  27. Pedro Orvalho, Mikolás Janota, and Vasco M. Man-quinho. 2025. Counterexample guided program repair using zero-shot learning and MaxSAT-based fault localization. In AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, pages 649–657. find
  28. Lluis Pamies-Juarez, Henk D. L. Hollmann, and Frédérique E. Oggier. 2013. Locally repairable codes with multiple repair alternatives. In Proceedings of the 2013 IEEE International Symposium on Information Theory, pages 892–896. find
  29. Julian Aron Prenner and Romain Robbes. 2024. Out of context: How important is local context in neural program repair? In Proceedings of the 46th IEEE/ACM International Conference on Software Engineering, ICSE, pages 83:1–83:13. find
  30. Leonardo Ranaldi, Giulia Pucci, Federico Ranaldi, Elena Sofia Ruzzetti, and Fabio Massimo Zanzotto. 2024. A tree-of-thoughts to broaden multi-step reasoning across languages. In Findings of the Association for Computational Linguistics: NAACL, pages 1229–1241. find
  31. Asiri Rathnayake and Hayo Thielecke. 2014. Static analysis for regular expression exponential runtime via substructural logics. arXiv preprint CoRR, 1405.7058. find
  32. Namrata Shivagunde, Vladislav Lialin, Sherin Muckatira, and Anna Rumshisky. 2024. Deconstructing in-context learning: Understanding prompts via corruption. In Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation, LREC/COLING, pages 45… find
  33. Mohammed Latif Siddiq, Jiahao Zhang, Lindsay Roney, and Joanna C. S. Santos. 2024a. Re(gEx\|DoS)Eval: Evaluating generated regular expressions and their proneness to dos attacks. In Proceedings of the 2024 ACM/IEEE 44th International Conference on Software Engineering: New Ideas and Emerging Results,… find
  34. Mohammed Latif Siddiq, Jiahao Zhang, and Joanna Cecilia Da Silva Santos. 2024b. Understanding regular expression denial of service (ReDoS): Insights from llm-generated regexes and developer forums. In Proceedings of the 32nd IEEE/ACM International Conference on Program Comprehension, ICPC ’24, page… find
  35. L. J. Stockmeyer and A. R. Meyer. 1973. Word problems requiring exponential time(preliminary report). In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC ’73, page 1–9. Association for Computing Machinery. find
  36. Weihao Su, Hong Huang, Rongchen Li, Haiming Chen, and Tingjian Ge. 2024. Towards an effective method of ReDoS detection for non-backtracking engines. In 33rd USENIX Security Symposium (USENIX Security 24), pages 271–288. find
  37. Jiashuo Sun, Yi Luo, Yeyun Gong, Chen Lin, Yelong Shen, Jian Guo, and Nan Duan. 2024. Enhancing chain-of-thoughts prompting with iterative bootstrapping in large language models. In Findings of the Association for Computational Linguistics: NAACL, pages 4074–4101. find
  38. Sicheol Sung, Hyunjoon Cheon, and Yo-Sub Han. 2022. How to settle the ReDoS problem: Back to the classical automata theory. In Implementation and Application of Automata - 26th International Conference, CIAA, Proceedings, volume 13266, pages 34–49. find
  39. Xunzhu Tang, Jiechao Gao, Jin Xu, Tiezhu Sun, Yewei Song, Saad Ezzini, Wendkûuni C. Ouédraogo, Jacques Klein, and Tegawendé F. Bissyandé. 2025. SynFix: Dependency-aware program repair via rela-tiongraph analysis. In Findings of the Association for Computational Linguistics, ACL, pages 4878–4894. pro… find
  40. Sajana Weerawardhena, Paul Kassianik, Blaine Nelson, Baturay Saglam, Anu Vellore, Aman Priyanshu, Supriti Vijay, Massimo Aufiero, Arthur Goldblatt, Fraser Burch, Ed Li, Jianliang He, Dhruv Kedia, Kojin Oshiba, Zhouran Yang, Yaron Singer, and Amin Karbasi. 2025. Llama-3.1-FoundationAI-SecurityLLM-8B-… — [arXiv:2508.01059](https://arxiv.org/abs/2508.01059) find
  41. Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. 2022a. Emergent abilities of large language models. Transactions on M…
  42. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. 2022b. Chain-of-Thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Process…
  43. An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, and 40 others. 2025. Qwen3 technical report.
  44. Yao Yao, Zuchao Li, and Hai Zhao. 2024. GoT: Effective graph-of-thought reasoning in language models. In Findings of the Association for Computational Linguistics: NAACL, pages 2901–2921. find
  45. Lenka Turonová, Lukás Holík, Ivan Homoliak, Ondrej Lengál, Margus Veanes, and Tomás Vojnar. 2022. Counting in regexes considered harmful: Exposing ReDoS vulnerability of nonbacktracking matchers. In 31st USENIX Security Symposium, USENIX Security 2022, Boston, MA, USA, August 10-12, 2022, pages 4165… find
  46. Daoguang Zan, Bei Chen, Fengji Zhang, Dianjie Lu, Bingchao Wu, Bei Guan, Yongji Wang, and Jian-Guang Lou. 2023. Large language models meet nl2code: A survey. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL, pages 7443–7464. find
  47. Brink van der Merwe, Nicolaas Weideman, and Martin Berglund. 2017. Turning evil regexes harmless. In Proceedings of the South African Institute of Computer Scientists and Information Technologists, SAICSIT ’17, New York, NY, USA. Association for Computing Machinery. find
  48. Zhaowei Zhang, Hongyu Zhang, Beijun Shen, and Xiaodong Gu. 2022. Diet code is healthy: simplifying programs for pre-trained models of of code. In Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE, pages 1073–… find
  49. Xinyi Wang, Cen Zhang, Yeting Li, Zhiwu Xu, Shuailin Huang, Yi Liu, Yican Yao, Yang Xiao, Yanyan Zou, Yang Liu, and 1 others. 2023a. Effective ReDoS detection by principled vulnerability modeling and exploit generation. In 2023 IEEE Symposium on Security and Privacy (SP), pages 2427–2443. IEEE. find
  50. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023b. Self-consistency im-Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V. Le, and Ed H. Chi. 2023.…

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sung-2026-repairing-regex-vulnerabilities-localization-guided/