Algorithmic Complexity Safeguards (Pattern/Regex Execution Limits)
Description
Enforces computational budgets on pattern matching, regular expression evaluation, and recursive parsing operations to prevent algorithmic complexity denial-of-service attacks. Encompasses three complementary techniques: (1) execution limits — regex step counts, match timeouts, and recursion depth caps that terminate runaway computations before they exhaust CPU or block event loops; (2) safe engine selection — mandating linear-time regex engines (RE2, Rust regex crate, .NET NonBacktracking mode) or equivalent guaranteed-polynomial parsers instead of backtracking NFA engines susceptible to catastrophic backtracking; (3) pattern compilation guards — never compiling user-controlled input directly into regex or pattern language without escaping metacharacters or using literal-match APIs, and pre-screening pattern structure for known dangerous constructs (nested quantifiers, overlapping alternations, unbounded repetition groups). Complements CME-114 (OS-level process resource limits) by providing application-level, per-operation granularity — a regex timeout kills the match attempt while keeping the service alive, whereas ulimit kills the entire process.
CVSS Vector Impacts
| Metric | Transition | Rationale |
|---|---|---|
| Availability (A) | H → L | Computational budgets (step limits, timeouts) and safe engine guarantees cap the worst-case execution time of any single pattern operation. The attacker can still trigger the vulnerable code path, but the operation is terminated or completes in bounded time, preventing sustained resource exhaustion and event-loop blocking |
CWE Relationships
Verification
Verify that the application uses linear-time regex engines or enforces execution budgets on pattern operations. Check for RE2 bindings, regex timeout configuration, recursion depth limits, and that user-controlled input is never compiled directly into regex patterns without escaping.
# Expected: RE2 available
# Expected: google-re2 available
# Expected: NonBacktracking mode available (.NET 7+)
# Expected: Regex operations use NonBacktracking mode (.NET 7+) or explicit MatchTimeout
# Expected: No instances of user-controlled input compiled into RegExp without escaping