Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- research-articleJune 2024
Understanding Regular Expression Denial of Service (ReDoS): Insights from LLM-Generated Regexes and Developer Forums
ICPC '24: Proceedings of the 32nd IEEE/ACM International Conference on Program ComprehensionApril 2024, Pages 190–201https://doi.org/10.1145/3643916.3644424Regular expression Denial of Service (ReDoS) represents an algorithmic complexity attack that exploits the processing of regular expressions (regexes) to produce a denial-of-service attack. This attack occurs when a regex's evaluation time scales ...
Re(gEx|DoS)Eval: Evaluating Generated Regular Expressions and their Proneness to DoS Attacks
ICSE-NIER'24: Proceedings of the 2024 ACM/IEEE 44th International Conference on Software Engineering: New Ideas and Emerging ResultsApril 2024, Pages 52–56https://doi.org/10.1145/3639476.3639757With the recent advances of code generation techniques based on Large Language Models (LLMs), developers are using them for a vast range of tasks, including regex generation. Despite the efforts to generate regexes from natural language, there is no ...
- ArticleApril 2024
Efficient Matching with Memoization for Regexes with Look-around and Atomic Grouping
AbstractRegular expression (regex) matching is fundamental in many applications, especially in web services. However, matching by backtracking—preferred by most real-world implementations for its practical performance and backward compatibility—can suffer ...
- ArticleJune 2022
How to Settle the ReDoS Problem: Back to the Classical Automata Theory
Implementation and Application of AutomataJun 2022, Pages 34–49https://doi.org/10.1007/978-3-031-07469-1_3AbstractMost regular-expression matching engines in practice are based on the Thompson construction and the Spencer matching algorithm. While these engines work fast and efficiently, a serious problem, the regular expression denial-of-service (ReDoS), has ...
Exploiting input sanitization for regex denial of service
ICSE '22: Proceedings of the 44th International Conference on Software EngineeringMay 2022, Pages 883–895https://doi.org/10.1145/3510003.3510047Web services use server-side input sanitization to guard against harmful input. Some web services publish their sanitization logic to make their client interface more usable, e.g., allowing clients to debug invalid requests locally. However, this ...
Why aren’t regular expressions a lingua franca? an empirical study on the re-use and portability of regular expressions
ESEC/FSE 2019: Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software EngineeringAugust 2019, Pages 443–454https://doi.org/10.1145/3338906.3338909This paper explores the extent to which regular expressions (regexes) are portable across programming languages. Many languages offer similar regex syntaxes, and it would be natural to assume that regexes can be ported across language boundaries. But ...
- research-articleOctober 2018
The impact of regular expression denial of service (ReDoS) in practice: an empirical study at the ecosystem scale
ESEC/FSE 2018: Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software EngineeringOctober 2018, Pages 246–256https://doi.org/10.1145/3236024.3236027Regular expressions (regexes) are a popular and powerful means of automatically manipulating text. Regexes are also an understudied denial of service vector (ReDoS). If a regex has super-linear worst-case complexity, an attacker may be able to trigger ...
- research-articleSeptember 2018Distinguished Paper
ReScue: crafting regular expression DoS attacks
ASE '18: Proceedings of the 33rd ACM/IEEE International Conference on Automated Software EngineeringSeptember 2018, Pages 225–235https://doi.org/10.1145/3238147.3238159Regular expression (regex) with modern extensions is one of the most popular string processing tools. However, poorly-designed regexes can yield exponentially many matching steps, and lead to regex Denial-of-Service (ReDoS) attacks under well-conceived ...
- research-articleSeptember 2017
Turning evil regexes harmless
SAICSIT '17: Proceedings of the South African Institute of Computer Scientists and Information TechnologistsSeptember 2017, Article No.: 38, Pages 1–10https://doi.org/10.1145/3129416.3129440We explore the relationship between ambiguity in automata and regular expressions on the one hand, and the matching time of backtracking regular expression matchers on the other. We focus in particular on the extreme cases where we have either an ...
- research-articleApril 2017
The Case of the Poisoned Event Handler: Weaknesses in the Node.js Event-Driven Architecture
EuroSec'17: Proceedings of the 10th European Workshop on Systems SecurityApril 2017, Article No.: 8, Pages 1–6https://doi.org/10.1145/3065913.3065916Node.js has seen rapid adoption in industry and the open-source community. Unfortunately, its event-driven architecture exposes Node.js applications to Event Handler-Poisoning denial of service attacks. Our evaluation of the state of practice in Node.js-...