Collected research

Counting in Regexes Considered Harmful: Exposing ReDoS Vulnerability of Nonbacktracking Matchers

Lenka Turoňová, Lukáš Holík, Ivan Homoliak, Ondřej Lengál, Margus Veanes and Tomáš Vojnar · usenix.org

Nonbacktracking regex engines are assumed immune to ReDoS, but bounded repetition such as (ab){100} forces them into costly simulation of a counting automaton. The authors generate inputs that maximise that cost, slowing real matchers including Hyperscan, .NET and a hardware engine enough to deny service in applications such as SNORT.

Record

Researcher

Lenka Turoňová, Lukáš Holík, Ivan Homoliak, Ondřej Lengál, Margus Veanes and Tomáš Vojnar

Published by

usenix.org

Topic

Other

In the archive

• Collected in the 2022 research round

Related sources

• USENIX Security '22 - Counting in Regexes Considered Harmful: Exposing ReDoS Vulnerability of

Tags

• algorithmic-complexity
• dos
• formal-analysis
• measurement-study
• dotnet
• tooling
• owasp-a04-2021

This page is the archive's own catalogue record. The research is the work of Lenka Turoňová, Lukáš Holík, Ivan Homoliak, Ondřej Lengál, Margus Veanes and Tomáš Vojnar, first published at the original source. Preserved copies are kept so the citation survives its host; this one was last captured on 19 August 2026.