# Static Analysis for Regular Expression Exponential Runtime via Substructural Logics (Extended)

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2014.

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

- [Repairing Regex Vulnerabilities via Localization-Guided Instructions](https://mlsanity.com/paper/2510.09037/) (2025)

## Abstract (arXiv)

Regular expression matching using backtracking can have exponential runtime, leading to an algorithmic complexity attack known as REDoS in the systems security literature. In this paper, we build on a recently published static analysis that detects whether a given regular expression can have exponential runtime for some inputs. We systematically construct a more accurate analysis by forming powers and products of transition relations and thereby reducing the REDoS problem to reachability. The correctness of the analysis is proved using a substructural calculus of search trees, where the branching of the tree causing exponential blowup is characterized as a form of non-linearity.