ReDoS Vulnerability in tiny-regex-c Library: Analysis and PoC

Vulnerability Overview Vulnerability Name: ReDoS CPU Denial of Service Vulnerability in Vulnerability ID: #100 Vulnerability Description: The and functions in the library are vulnerable when handling greedy quantifiers (such as and ). These functions first consume as much input as possible, then backtrack from right to left, calling for each candidate split point. When multiple greedy quantifiers are chained and the overall match fails at the end, the engine repeatedly re-evaluates the same input, leading to an exponentially growing number of failed paths. An attacker can exploit this vulnerability by crafting specific inputs or by triggering vulnerable patterns already present in the host application. Affected Matching Logic: Stable Reproducer: Important Constraint: is set to 30. The reproducer intentionally keeps the number of repeated tokens low to ensure the trailing is compiled. If too many tokens are added, the pattern tail will be truncated, potentially turning a failing match into a successful one and hiding the ReDoS behavior. Impact Scope Environment: - Compiler: GCC 11.2.0 - Build Command: Steps: 1. Build the verifier: 2. Run the matcher with incrementally increasing input lengths for failing matches: 3. Observe that all inputs fail to match, but CPU time increases rapidly: Screenshots: Impact: - Crafted patterns and failing match inputs can lead to excessive CPU consumption. - In network services, exposing regex matching directly or indirectly allows unauthenticated remote attackers to spawn worker threads or event loops, causing a denial of service. - In CLI, embedded, or local usage, exploitability depends on whether untrusted users can provide regex patterns or trigger worst-case path inputs. - The closest CWE is CWE-1333: Low Complexity Regular Expression. CWE-400: Uncontrolled Resource Consumption also applies. Remediation Replace the current backtracking quantifier implementation with a linear-time matching strategy, such as Thompson NFA or Pike VM-style execution, or any other design that does not re-evaluate identical states. Add matching step budgets, timeouts, or recursion/backtracking limits, and fail safely when the budget is exceeded. Reject or warn about ambiguous chains of repeating quantifiers, especially repeated greedy quantifiers on the same atom, which could lead to catastrophic backtracking. Return a compilation-time error when would truncate the pattern, rather than silently compiling a prefix that might alter the matching result. In host applications, when accepting untrusted regex patterns, capture pattern length if user-controlled, limit input length, isolate matching, enforce timeouts, and consider using a regex engine with guaranteed linear-time behavior. Additional Files contains all files required to reproduce the issue, including , , , and .

Goal Reached Thanks to every supporter — we hit 100%!

ReDoS Vulnerability in tiny-regex-c Library: Analysis and PoC

More from this source