ReDoS risk in Python regexes exposes availability gaps

At a glance

What this is: This article explains how ReDoS bugs arise in Python regular expressions and why catastrophic backtracking can turn a single crafted input into an availability outage.

Why it matters: It matters to IAM and security teams because identity workflows, authentication gates, and API protection logic often rely on regexes, and a fragile pattern can become an access-path denial-of-service condition.

By the numbers:

• 90% of IT leaders say properly managing NHIs is essential for a successful zero-trust implementation.
• Only 5.7% of organisations have full visibility into their service accounts.
• 96% of organisations store secrets outside of secrets managers in vulnerable locations including code, config files, and CI/CD tools.

👉 Read Semgrep's analysis of ReDoS bugs in Python regular expressions

Context

Regular expression denial of service is a control failure, not just a code-quality bug. When a pattern creates excessive backtracking, one malformed input can monopolise CPU and stall the service that depends on it. In identity and access paths, that can affect login flows, token validation, input sanitisation, and policy evaluation, which makes regex safety part of availability governance as much as application security.

Semgrep's analysis is useful because it shows how static detection can identify risky regex forms before they become production incidents. For IAM practitioners, the larger lesson is that trust boundaries in authentication and authorisation code often depend on small parsing rules, and those rules should be reviewed with the same discipline as secrets handling and access control logic.

Key questions

Q: What breaks when a regular expression is vulnerable to catastrophic backtracking?

A: The application can stop responding because the regex engine consumes excessive CPU trying many matching paths for a single input. That risk is highest when the pattern sits on a public request path, a login flow, or an input validation step. In practice, a ReDoS bug turns one crafted string into a denial-of-service condition.

Q: Why do regex bugs matter in identity and access workflows?

A: Identity workflows often depend on parsing, validation, and policy evaluation logic that accepts user input or token contents. If those checks use inefficient regular expressions, an attacker can slow or block authentication and authorisation flows without needing to break cryptography or steal credentials.

Q: How do security teams know a regex is actually risky?

A: Look for structural warning signs such as nested repetition, overlapping alternation, or a trailing token that forces repeated backtracking. Then confirm the path is reachable from untrusted input and measure runtime under adversarial test cases. A regex that only behaves well on normal data is not safe enough.

Q: Who should own ReDoS prevention in a development programme?

A: Application security, secure engineering, and the team that owns the affected service should share ownership. The key is to treat regex review as a release gate for exposed code paths, because availability failures caused by pattern matching are a product risk, not just a developer mistake.

Technical breakdown

Why nested quantifiers trigger catastrophic backtracking

Nested quantifiers occur when a repeated expression contains another repeated expression, such as (a+)+. The engine tries many possible ways to satisfy both layers of repetition, and when the rest of the pattern cannot match, it keeps backtracking across a growing search space. That turns linear-looking input handling into exponential work. This is why a pattern that looks harmless in review can become a CPU sink under adversarial input, especially in services that process user-supplied text at scale.

Practical implication: flag nested repetition in code review and SAST before regexes reach production authentication or parsing paths.

How overlapping alternation expands the search space

Mutually inclusive alternation happens when either side of an OR clause can consume the same characters, such as ([a-z]|a)+. The engine cannot quickly decide which branch is correct, so it explores multiple interpretations of the same input. If the pattern then requires a trailing token that cannot be matched, the engine backtracks through every combination it tried. This is the same failure mode as nested quantifiers, but it often hides inside apparently simple either/or syntax.

Practical implication: replace overlapping alternation with tighter character classes or anchored patterns that remove ambiguous branch selection.

Why SAST heuristics matter for regex review

Semgrep's approach is to identify suspicious structure rather than prove a vulnerability from input alone. That is important because ReDoS risk depends on both the pattern and the context in which it is executed. Heuristics can catch dangerous constructs early, then developers can validate whether the regex is reachable from untrusted input. This is especially valuable in large codebases where manually auditing every regular expression is unrealistic.

Practical implication: add regex-specific rules to SAST and route findings into secure code review, not just generic linting.

Threat narrative

Attacker objective: The attacker aims to deny service by exhausting compute resources through a single malicious input pattern.

1. Entry occurs when an attacker submits crafted input designed to exercise a vulnerable regular expression in a public-facing parser or validation path.
2. Escalation happens when nested quantifiers or overlapping alternation force the regex engine into excessive backtracking and tie up CPU.
3. Impact is service degradation or outage because the application cannot process legitimate requests while the regex engine monopolises resources.

Breaches seen in the wild

• Salesloft OAuth token breach — hackers stole OAuth tokens to access Salesforce data via Salesloft.
• Internet Archive breach — unsecured GitLab authentication tokens exposed 31M Internet Archive accounts.

Read our 52 NHI Breaches Analysis report for a comprehensive view of breaches impacting Non-Human Identities including AI Agents.

NHI Mgmt Group analysis

ReDoS is a governance problem when regexes sit on trust boundaries. The article shows that a tiny pattern flaw can create an availability incident, which means secure development teams should treat regexes as security-relevant code. In identity-heavy systems, these patterns often sit in authentication, token parsing, and policy logic, so a failure here can block access as effectively as an outage. Practitioners should review regex risk as part of application and identity governance, not as a formatting issue.

Regex backtracking debt: the accumulated risk from ambiguous patterns that survive code review and slowly widen outage exposure. This is the kind of failure that grows when teams rely on manual inspection alone. The article's examples show that both nested quantifiers and overlapping alternation can remain invisible until a crafted input reveals the problem. Practitioners should build detection into the development pipeline before these patterns become operational dependencies.

Availability controls need to cover security logic, not just infrastructure. ReDoS can take down an application even when the network, host, and perimeter controls are functioning normally. That means resilience planning has to include code-path abuse, especially where user input reaches regex-driven validation or filtering. Security teams should align this with NIST CSF resilience thinking and with secure coding standards that treat input handling as an operational risk.

Static analysis is useful here because it finds structural risk before exploitation. The article's value is not only the detection of specific bugs but the demonstration that tooling can surface regex hazards across large codebases. That shifts the control discussion from reactive patching to preventive review. Practitioners should use this pattern to prioritise remediation work on exposed regex paths first, then use runtime monitoring to validate that fixes actually reduce CPU exposure.

From our research:

• 97% of NHIs carry excessive privileges, increasing unauthorised access and broadening the attack surface, according to Ultimate Guide to NHIs.
• 71% of NHIs are not rotated within recommended time frames, increasing the risk of compromise over time.
• For the broader governance context: review Top 10 NHI Issues to see how identity sprawl and weak lifecycle control shape control failures.

What this signals

ReDoS is a reminder that application security controls must extend into the logic that validates identity traffic. When regexes are embedded in login, token, or policy code, a small parsing flaw becomes an operational outage, so development teams need security testing that understands performance as well as correctness. The safest programmes treat these checks as part of the same governance surface covered by NIST SP 800-53 Rev 5 Security and Privacy Controls.

Regex ambiguity debt: the hidden operational cost of patterns that are syntactically valid but computationally fragile. Teams that do not catalog these expressions will struggle to distinguish ordinary code defects from exploitable backtracking conditions. For that reason, the best next step is to pair secure code review with targeted detection and remediation work in the most exposed request paths.

For practitioners

• Inventory regexes on trusted input paths Map every regular expression that touches authentication, authorisation, token parsing, or request validation and rank them by exposure to untrusted input. Focus first on user-facing code paths that can be triggered repeatedly without authentication.
• Block ambiguous regex structures in review Reject nested quantifiers and overlapping alternation unless there is a documented, tested reason they cannot be rewritten. Add code review guidance that treats patterns like (a+)+ and overlapping character branches as security findings.
• Add regex-focused SAST rules Use Semgrep or equivalent static analysis to detect structural ReDoS patterns early in the pipeline and route findings to secure engineering review. Tune the rules so they catch high-risk patterns in application code and infrastructure policy code alike.
• Test for worst-case backtracking Create unit tests that feed maliciously structured strings into exposed regexes and measure execution time under load. If a pattern degrades non-linearly, replace it with a safer design before it becomes an availability issue.

Key takeaways

• Catastrophic backtracking turns a single crafted string into an availability risk when inefficient regexes sit on exposed code paths.
• Semgrep's findings show that nested quantifiers and overlapping alternation are practical ReDoS indicators, not theoretical edge cases.
• Teams should treat regex review, SAST, and worst-case input testing as part of secure engineering for authentication and validation logic.

Key terms

• Regular Expression Denial Of Service: A ReDoS issue happens when a regular expression takes disproportionate time to evaluate against a crafted input. The root cause is usually excessive backtracking in the regex engine, which can consume CPU and stall an otherwise healthy service.
• Catastrophic Backtracking: Catastrophic backtracking is the explosive search behavior that occurs when a regex engine tries too many ways to match an ambiguous pattern. It becomes a security issue when an attacker can trigger the worst case and force resource exhaustion.
• Nested Quantifiers: Nested quantifiers are repeated patterns inside other repeated patterns, such as a group that contains another plus sign or star. They are a common source of ReDoS because they create a large number of matching paths that the engine may need to explore.
• Overlapping Alternation: Overlapping alternation is an either-or expression where multiple branches can match the same characters. That ambiguity can cause the engine to try several interpretations before failing, which increases the chance of excessive backtracking and performance collapse.

What's in the full article

Semgrep's full post covers the operational detail this post intentionally leaves for the source:

• The exact Bento check logic used to detect inefficient regular expressions in Python projects.
• Examples of the specific vulnerable patterns found in urllib, poetry, grpc, colorama, bottle, and requests-kerberos.
• The engineering workflow Semgrep used to run the check across several thousand open source Python projects.
• Background on the Python bpo-39503 and CVE-2020-8492 findings that the pattern uncovered.

👉 Semgrep's full post includes the Bento check, vulnerable regex examples, and the Python projects it flagged.

Deepen your knowledge

NHI Foundation Level course, the industry's only accredited NHI security programme, covers NHI governance, machine identity security, secrets management, and identity lifecycle control. It is designed for practitioners who need to connect identity governance with the broader security controls their programmes depend on.