# Static Detection of DoS Vulnerabilities in Programs that use Regular Expressions (Extended Version)

arXiv: https://arxiv.org/abs/1701.04045 · HTML: https://mlsanity.com/paper/1701.04045/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2017.

## Built on by (most cited first, 1 of 1)

- [Lost in Translation? Converting RegExes for Log Parsing into Dynatrace Pattern Language](https://mlsanity.com/paper/2506.19539/) (2025)

## Abstract (arXiv)

In an algorithmic complexity attack, a malicious party takes advantage of the worst-case behavior of an algorithm to cause denial-of-service. A prominent algorithmic complexity attack is regular expression denial-of-service (ReDoS), in which the attacker exploits a vulnerable regular expression by providing a carefully-crafted input string that triggers worst-case behavior of the matching algorithm. This paper proposes a technique for automatically finding ReDoS vulnerabilities in programs. Specifically, our approach automatically identifies vulnerable regular expressions in the program and determines whether an "evil" input string can be matched against a vulnerable regular expression. We have implemented our proposed approach in a tool called REXPLOITER and found 41 exploitable security vulnerabilities in Java web applications.