An Empirical Analysis of ReDoS Vulnerabilities and ReDoS Detection Tools

1 Introduction

• ReDoS occurs when a backtracking regex engine handles an evil pattern, allowing a maliciously crafted input to require exponential or large-polynomial validation time.The attack requires both a backtracking engine and a regex exhibiting an evil pattern.Source: §1 · p. 1
• The literature does not agree on the exact definition of evil patterns, and some detection tools consequently recognize only a subset of vulnerable patterns.The paper identifies Li et al.’s five-pattern classification as the most thorough proposal, while noting it is not universally accepted.Source: §1 · pp. 1–2
• Uncertainty about problematic patterns accompanies growing ReDoS prevalence and disagreement among tools assessing whether regexes exhibit an evil pattern.The authors present two experiments intended to provide actionable information for developers and security professionals.Source: §1 · p. 2
• The study analyzes over 400 ReDoS CVEs, evaluates five detection tools and one correction tool across three datasets, and releases two labeled datasets.It also proposes a multi-factor metric for assessing regex vulnerability.Source: §1 · p. 2

2 Related Works

• Two large-scale studies found ReDoS in 1% of over 400,000 regexes and in 339 of 2,846 popular websites, though their definitions may overlook patterns defined by Li et al..Davis et al. reported the regex finding, while Staicu et al. reported the website finding.Source: §2 · p. 2
• Prior studies develop tools to detect whether a regex is vulnerable; these methods span static, dynamic, and hybrid approaches, which the paper reviews and evaluates in Section 5.Source: §2 · p. 2
• The study focuses on RegexScalpel, whose sequence of regex modifications may change the original regex’s semantics.Source: §2 · p. 3

3.1 Datasets

• The ReDoS CVE dataset combines NVD entries identified by CWE-1333 with CVEs whose descriptions contain ReDoS-related search terms.As of September 2025, 341 NVD entries carried CWE-1333, but manual inspection found relevant CVEs under other or no CWE labels.Source: ReDoS CVE Dataset · p. 3
• From 3,514 RegexLib regexes obtained through RXXR2, the study retained 2,853 after excluding malformed, ambiguous, or trivially simple entries.RegexLib supplies regexes for commonplace tasks that developers may borrow rather than write themselves.Source: RegexLib · p. 3
• Regex_before and Regex_after contain regexes extracted from vulnerable and patched CVEFixes code, but their entries are not necessarily vulnerable regexes and corresponding patches.After malformed regexes were excluded, the datasets contained 379 and 391 entries, respectively; they also include duplicates.Source: CVEFixes · pp. 3–4

3.2 Analysis tools

• The study applies five tools to each regex: Saferegex, Rescue, ReDoSHunter, Revealer, and RAT.The suite includes static, dynamic, and hybrid analyzers; static tools may produce false positives, while dynamic tools may miss vulnerable regexes.Source: §3.2 · p. 4
• The researchers excluded another freely available tool because it cannot handle regexes containing features such as backreferences.Source: §3.2 · p. 5
• RegexScalpel suggests corrections, but may impose hard-coded quantifier limits that change regex semantics; corrected regexes are retested and may receive a second correction.The evaluation applies the same detection suite to corrected regexes and repeats correction when a regex remains vulnerable.Source: §3.2 · pp. 4–5

4 Empirical Analysis

• The study compares 490 ReDoS CVEs with 215,085 non-ReDoS CVEs to characterize how ReDoS vulnerabilities differ.Source: §4 · p. 5

4.1 Prevalence

• ReDoS CVEs were reported fewer than 20 times annually until 2020, when reports spiked to 103; subsequent years saw approximately 60 reports per year.The earliest reported ReDoS vulnerability dates to 2010.Source: §4.1 · p. 5, Figure 1 · p. 6

4.2 CVSS scores

• ReDoS CVEs were mostly network attacks (97.64%), required no privileges (84.48%) or user interaction (96.12%), and had low attack complexity (96.77%), but lower average base scores.Average base scores were 6.88 for ReDoS and 7.11 for non-ReDoS CVEs; only 0.43% of ReDoS CVEs were HiLac, versus 42.33% of non-ReDoS CVEs.Source: §4.2 · p. 6, Table 1 · p. 7

4.3 Exploitation and Exploitability

• 277 of 286 ReDoS CVEs published from 2019–2023 (97%) appeared in sources documenting exploitation, suggesting ReDoS may be among the most exploited attack categories.The evidence combined the KEV catalog with data from three industrial partners.Source: §4.3 · p. 7
• Exploitability signals were mixed: exploit-tag references were more common for ReDoS, while peak EPSS scores did not significantly distinguish the groups.Exploit-tag references occurred for 47.4% of ReDoS versus 26.2% of non-ReDoS CVEs. Peak EPSS occurred after 498.40 versus 698.30 days, respectively; ReDoS CVEs also had no .gov references, and EPSS averages did not differ significantly.Source: §4.3 · pp. 7–8

4.4 CPE

• Ruby programs were prevalent among ReDoS CVEs, Python was most overrepresented against non-ReDoS CVEs, and four top-ten vendors also appeared on a list of commonly exploited vendors.Since March 2023, Ruby v. 3.2 has incorporated an improved regex matching algorithm that makes ReDoS attacks impossible.Source: §4.4 · p. 8, Figure 2 · p. 9

4.5 CWE

• CWE-1333 was the most common label (330 CVEs), followed by CWE-400 (142), while other labels and unassigned categories reflect ambiguity in CWE assignment.The analysis also reports 18 CVEs labeled NVD-CWE-noinfo and 16 labeled NVD-CWE-Other.Source: §4.5 · p. 9, Figure 3 · p. 10

5.1 Methodology

• The pipeline sanitizes RegexLib and CVEfixes regexes, runs five detection tools, then re-tests corrected regexes using one randomly selected correction when several are available.The study evaluates the results in Table 2.Source: §5.1 · p. 10, Figure 4 · p. 11

5.2 Results and Analysis

• 74% of vulnerable regexes were flagged by a single tool (1051/1411), while only 5 cases were flagged by all five tools.The tools exhibited greater disagreement than agreement.Source: Figure 5 · p. 11, §5.2 · p. 11
• Rescue reports more timeouts than definitive vulnerable verdicts across all three datasets, while RAT flags few regexes yet catches some no other tool marks vulnerable.ReDoSHunter commonly identifies juxtaposed quantifiers with shared valid sequences; Rescue timeouts may be false positives, and Rescue and Revealer often reach similar verdicts.Source: §5.2 · pp. 11–13
• The upset plot shows that SafeRegex and ReDoSHunter flag most regexes deemed vulnerable, but agree little with each other or the other tools.At least one tool marks 15% of RegexLib regexes vulnerable; the authors caution against borrowing public-library regexes uncritically.Source: Figure 6 · p. 12, §5.2 · pp. 12–13

5.3 Case studies

• Case studies expose inconsistent verdicts: tools split on backreferences and user-supplied headers, and some miss regexes the authors describe as obviously vulnerable.Capturing-group regexes were sometimes missed by static tools but flagged by dynamic ones; the five cases all tools agreed on were simple and contained overlapping quantifiers.Source: §5.3 · pp. 13–14

5.4 Multi-Factor Metric and Correction Phase

• The proposed metric deems a regex vulnerable when any of three combinations of ReDoSHunter, Revealer, static or grey-box tools, and dynamic tools flags it.The criteria were selected experimentally after comparing variants and manually inspecting samples; the metric flagged 25.51% of regexes across the three datasets.Source: §5.4 · p. 14
• RegexScalpel suggested corrections for 339 of 440 vulnerable RegexLib regexes, with 332 adequate (75.45%); 17 of 36 Regex_After cases remained vulnerable (52.77%).For Regex_Before, it suggested corrections for 26 of 61 vulnerable regexes, and only 13 corrected regexes were deemed benign.Source: §5.4 · p. 14
• RegexScalpel corrections are not always semantically equivalent to the originals, so the authors advise against relying on correction tools alone to protect applications.Common changes include limiting quantifiers to 500 iterations and adding anchors.Source: §5.4 · p. 15

• ReDoS vulnerabilities are both easy to exploit and likely to be exploited.Source: §6 · p. 15
• The study evaluates five ReDoS detection tools and one correction tool using over 3000 real-life regexes.Source: §6 · p. 15
• The analysis distinguishes ReDoS vulnerabilities from other types of vulnerabilities and finds most detection and correction tools have significant lacunae.Source: §6 · p. 15