Regular 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 ...

With 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 ...

Regular 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 ...

Most 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 ...

Web 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 ...

This 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 ...

Regular 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 ...

Regular 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 ...

We 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 ...

Node.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-...