Algorithmic Complexity Is a Security Boundary: Finding Superlinear Parsers Before Release

A parser benchmark doubles one malformed quoted literal at each step. Input size grows linearly; CPU time bends upward much faster. The request remains below the body limit and creates few final tokens, yet one worker spends most of its time revisiting the same prefixes before it can reject the input.

A recent SQL-parser advisory documented this shape in a regular-expression path for incomplete delimiters. A later token cap offered no protection because the lexer had already paid the expensive cost. The fixed release changed the behavior, but the review lesson applies to any parser, sanitizer, router, validator, or policy engine: accepted byte count and required work are separate parts of the input contract.

The useful test is a growth curve, not one dramatic timeout. Isolate the relevant phase, increase a harmless adversarial pattern in bounded steps, record CPU and allocations, verify cancellation, and compare the slope before and after remediation. That evidence distinguishes superlinear amplification from ordinary slowness and noisy infrastructure.

Key Takeaways

• Input byte limits do not bound parser work when an algorithm rescans suffixes, backtracks, retries alternatives, or repeatedly normalizes the same data.
• A post-lexing token limit cannot protect an expensive lexer path that runs before tokens exist.
• Security testing should measure a growth curve across controlled input sizes, not rely on one slow sample or an attempt to crash the service.
• Complexity budgets need absolute ceilings, scaling-ratio thresholds, isolation, cancellation checks, and stable benchmark methodology.
• Durable fixes remove repeated work, guarantee progress, pre-index delimiters, use linear-time engines, or apply an earlier semantic budget.
• Continuous validation should tie the safe reproducer to parser and dependency changes so performance regressions cannot silently reopen availability risk.

Availability Depends on Work per Byte

Perimeter controls usually measure bytes, requests, and connections. Those are useful proxies when server work scales roughly linearly. A superlinear algorithm breaks the relationship.

Let n represent attacker-controlled input size and T(n) the CPU time required to parse it:

linear:      T(n) ~= c * n
quadratic:   T(n) ~= c * n^2
cubic:       T(n) ~= c * n^3
exponential: T(n) ~= c * k^n

Real measurements include constants, startup work, allocation, caching, and noise, so we should not infer exact mathematical complexity from one ratio. Still, growth behavior matters. If doubling a controlled pattern repeatedly produces close to four times the time, the path deserves investigation. If each request ties up a scarce event-loop or worker thread, modest traffic can become an availability incident.

CPU Amplification and Memory Expansion Are Different

Both are resource-consumption risks, but they require different oracles:

A parser may have both CPU and memory problems, but calling every case "large input" obscures which stage and algorithm need correction.

Where Superlinear Parser Behavior Comes From

Repeated Suffix Scans

A lexer tries to match a construct at many positions. For each candidate opener, it searches the remaining input for a corresponding closer. When closers are absent or unique openers never match, each attempt scans a large suffix. The total work accumulates quadratically.

Catastrophic or Expensive Backtracking

Ambiguous nested quantifiers and overlapping alternatives can force a backtracking engine to explore many paths before rejecting a string. Not every regular-expression denial of service is exponential; quadratic behavior can be enough for practical impact on a request path.

Recursive Ambiguity

A parser may retry grammar alternatives over the same tokens or recurse without memoization. Malformed input can force it to explore combinations that valid input resolves quickly.

Repeated Normalization and Decoding

Canonicalization, Unicode handling, entity decoding, or path normalization may be applied inside loops. A value copied and transformed at every level creates more work than its final size suggests.

Error Recovery Without Progress

Parsers often try to recover after malformed syntax. If a recovery branch does not consume input or repeatedly restarts from an earlier point, one invalid token can trigger a large amount of repeated analysis.

User-Controlled Patterns

Some systems allow users to supply regular expressions, filters, or grammars. The risk may come from compiling the pattern, applying it to attacker-controlled text, or both. Pattern complexity and data complexity are separate inputs even when they meet in the same request.

Map the Real Parsing Pipeline

The vulnerable stage may not be where the application applies its documented limit.

network bytes
  -> decompression and character decoding
  -> coarse size check
  -> lexer or tokenizer
  -> parser and grouping
  -> semantic validation
  -> normalization
  -> application execution

A maxTokens rule in grouping cannot stop a regex that consumes CPU before tokenization completes. A request timeout at the proxy may return an error while backend CPU continues. A route-level size check cannot help if framework middleware parses the body first.

Phase Budget Matrix

Budgets should be enforced by the component that can stop the work. A gateway cannot cancel CPU it does not control unless cancellation propagates and the parser observes it.

Find Complexity Selectors in Code

Code review should look for attacker input controlling repeated work, not only dangerous functions.

Search for:

• Regex evaluation inside a loop over input positions.
• Backreferences or overlapping alternatives over unbounded input.
• Repeated find, substring, or suffix scans.
• Nested loops over tokens derived from the same request.
• Recursive descent without a depth or work counter.
• Reparse or re-tokenize operations after every modification.
• Error recovery that resets the cursor.
• String concatenation that repeatedly copies growing buffers.
• Lookups that are linear but performed for every token.
• User-controlled grammar, pattern, delimiter, or normalization mode.
• Limits enforced only after expensive object construction or tokenization.

The question is: what controls the number of times each byte or token can be visited? A linear parser should make bounded progress. If a character can trigger rescanning of the entire remainder, document why the number of such triggers is bounded.

Dependency Code Is Part of the Path

Applications frequently use parsers for SQL formatting, syntax highlighting, logs, Markdown, templates, email, archives, media metadata, configuration, and security validation. The application may never execute the parsed language. If unauthenticated or low-cost input reaches the library, parser CPU is still part of the application's attack surface.

The benchmark record should include the exact library version, invocation mode, wrapper limits, call sites, authentication state, concurrency model, and whether parsing runs on a shared event loop or worker pool.

Measure a Curve, Not a Crash

Safe complexity testing does not try to exhaust production. It uses small, increasing inputs in an isolated process and stops well before service failure.

Establish a Stable Harness

• Pin runtime, parser version, CPU allocation, and configuration.
• Disable unrelated network and storage activity.
• Warm up runtime compilation and caches consistently.
• Run each size several times.
• Record median and a high percentile, not only the fastest sample.
• Measure CPU time where possible in addition to wall time.
• Isolate one parser invocation per worker or reset state.
• Set strict per-case timeout and total test budget.

Synthetic strings that exercise one grammar property are sufficient. A weaponized endpoint recipe or production target adds risk without improving the complexity measurement.

Choose Geometric Input Sizes

Conservatively bounded sizes such as n, 2n, and 4n make the growth ratios visible:

R(n) = T(2n) / T(n)

For a sufficiently large stable region, a linear path trends toward roughly 2, quadratic toward roughly 4, and worse algorithms grow faster. Constants and noise can dominate small sizes, so examine several intervals. The goal is to detect unhealthy growth, not publish a formal complexity proof from a microbenchmark.

Define Stop Conditions Before Running

Stop when any case reaches:

• A conservative wall or CPU duration.
• A worker health threshold.
• A scaling ratio above the investigation threshold.
• An unexpected allocation or process event.
• A parser exception indicating the intended path is no longer being exercised.

The test succeeds when it gathers enough evidence to classify the growth. Crashing the worker adds little value.

Avoid Benchmark Mistakes

One Slow Input Does Not Prove Superlinearity

A fixed startup cost, garbage collection, CPU throttling, logging, or cold cache can make one case slow. Repeat runs, isolate variables, and compare growth.

Timeouts Can Hide Continuing Work

If the client times out but the parser thread continues, wall-clock measurement from the client underestimates resource occupation. Process CPU and cancellation behavior show whether the underlying operation really stopped.

Optimized Builds Matter

Debug instrumentation can distort absolute timing, while production optimization can change regex or parser behavior. Production-equivalent builds are useful for confirmation, with a separate instrumented harness retaining scan or transition counts.

Parallel Tests Distort Curves

Sequential cases on controlled CPU reduce scheduler noise unless contention is the property under test. Parallel benchmark jobs can otherwise make the harness itself exhaust the runner.

Passing a Short Ceiling Is Not Proof of Linear Growth

A vulnerable path may stay under 100 milliseconds at current test sizes yet scale dangerously at the application's maximum accepted input. An absolute budget and a growth-ratio budget capture different parts of that risk.

Fix the Algorithm, Then Add Limits

Input caps reduce maximum harm but can leave a poor algorithm within the allowed range. Correct the repeated-work cause where possible.

Guarantee Progress

Each lexer or parser iteration should consume input, advance a cursor, or spend from an explicit work budget. Error recovery must not restart indefinitely.

Replace Repeated Search

Pre-indexed delimiters, a single state-machine scan, or a stack can avoid searching the remaining suffix for every opener. The important choice is a parsing strategy with understood bounds for the supported grammar.

Use Linear-Time Pattern Engines or Safer Patterns

Where feature requirements allow, a linear-time regex engine or patterns without ambiguous backtracking and repeated suffix scans can simplify the bound. Engine changes still need semantic testing because they may alter supported syntax.

Apply Early Semantic Budgets

Decoded bytes, delimiter count, nesting, token candidates, and work units are most useful as limits before expensive phases. A delimiter budget may matter more than bytes when each delimiter starts a costly search, and unknown cost should not default to unlimited work.

Make Cancellation Cooperative

Deadlines need to reach parsing code and be checked at bounded intervals. Where unsafe work cannot be interrupted reliably, a disposable process provides a termination boundary, with temporary state and partial output kept away from promotion.

Protect the Service Around the Parser

Even a linear parser can consume resources on large input. Layer controls:

• Authenticate expensive features where product design permits.
• Use endpoint-specific body and field limits.
• Place parsing in a bounded worker pool, not the primary event loop.
• Apply per-principal and global work quotas.
• Shed load before all workers are occupied.
• Propagate cancellation.
• Limit queued work and reject when capacity is exhausted.
• Cache only safe, identity-bound results.
• Monitor CPU time per parser and input class.

Autoscaling is not a primary fix. It can multiply cost and turn CPU amplification into denial of wallet. Scale for legitimate demand after bounding per-request work.

CI Complexity Budgets

A parser regression test should be stable enough to gate changes without becoming flaky.

Use Two Thresholds

1. Absolute threshold: The largest safe test input completes within a conservative time or instruction budget.
2. Growth threshold: Ratios across geometric sizes remain below a value that signals superlinear behavior, with allowance for noise.

Instruction counts, regex-step counters, or explicit work-unit instrumentation are more stable than wall time when available. Wall time remains useful for end-to-end impact.

Compare Against a Baseline Carefully

A known-good parser version or commit gives the harness a comparison baseline. Running old and proposed versions on the same worker reduces environmental noise, while input-generator version, runtime, CPU details, measurements, and confidence bounds keep the result reproducible. Large relative regressions may deserve a gate even before absolute time becomes high.

Separate Fast PR Tests from Deeper Scheduled Tests

Pull requests can run a small deterministic growth check on changed parsers and call sites. Nightly or release tests can use larger safe ranges, more repetitions, alternate runtimes, and full service instrumentation. Neither should approach host exhaustion.

Validate Reachability and Business Impact

A vulnerable library version does not prove every application is exploitable. The application-specific case depends on:

• Can an external or low-privilege actor control the parsed text?
• What size limits and authentication apply before parsing?
• Does the affected grammar feature run for that input?
• Is parsing synchronous on a shared request thread or isolated?
• How many concurrent operations can one actor trigger?
• Does timeout actually cancel work?
• What service function becomes unavailable?
• Are there compensating queues, quotas, or process boundaries?

Those answers support severity and upgrade priority. Active exploitation still needs a reliable source, and a package's high score does not transfer unchanged to every deployment.

Tie the Growth Curve to the Code Path

Complexity testing is most useful when it connects a dependency advisory or code pattern to an actually reachable application path. Code analysis can trace untrusted text into the parser and identify which limits execute first. An isolated runtime test can then measure controlled curves and verify cancellation.

SecureHup's code-aware analysis and sandboxed validation are relevant because they can narrow testing to reachable parser paths, collect resource evidence, and replay a safe growth check when a pull request changes the parser, wrapper, or input limit. The user value is a verified performance-security boundary: not merely that a dependency version is listed, but that attacker-controlled input can or cannot create disproportionate work in the deployed path.

Connect Complexity Budgets to Service Capacity

A parser benchmark becomes operationally meaningful when its budget is tied to the service's concurrency model. Suppose one request may consume 200 milliseconds of CPU and the service has eight parser workers. An attacker does not need an individually catastrophic input to occupy the pool; enough accepted work can keep those workers busy. Per-request cost therefore belongs beside queue length, per-principal and global concurrency, and recovery headroom.

Use a simple capacity model during design review:

maximum admitted parser work
  = per-request CPU budget
  * concurrent parser slots
  * allowed queued requests

This is not a precise performance forecast, but it exposes unsafe combinations. A generous input limit, long timeout, deep queue, and broad unauthenticated reach can multiply into minutes of committed CPU. Admission control should reject or defer work before the queue consumes all capacity needed for health checks and ordinary traffic.

The distribution of parser CPU by endpoint, principal class, input size, and result type can reveal rising cost for rejected input before overall latency crosses an SLO. Bounded labels avoid recording raw untrusted content, while CPU-per-byte growth, cancellation failures, repeated budget exhaustion, and slow worker-pool recovery provide useful alert conditions.

Finally, test graceful degradation. When the parser budget is exhausted, the service should return a bounded error, release memory and worker state, avoid verbose rendering of the entire input, and continue serving valid requests. Availability security includes the failure path and recovery time, not only the duration of the pathological call.

Incident and Remediation Checklist

• Upgrade to the fixed, supported parser release.
• Inventory every service and job using the affected version.
• Identify externally controlled call sites and pre-parser limits.
• Move risky parsing off shared event loops where possible.
• Apply conservative temporary input and concurrency limits.
• Confirm timeouts cancel actual parser work.
• Review CPU spikes, queue saturation, and repeated malformed-input patterns.
• Add a safe growth-curve reproducer and valid-input controls.
• Verify the patched curve and output semantics.
• Add PR and scheduled complexity budgets.
• Reassess related regex and multiline grammar paths using the same algorithm shape.
• Document deployment-specific prerequisites before assigning impact.

FAQ

What is an algorithmic complexity denial of service?

It occurs when attacker-controlled input causes an algorithm to perform disproportionately large CPU, memory, or other work. In parsers, repeated scans, ambiguous backtracking, recursive alternatives, and non-progressing error recovery are common causes. A request can be within byte limits and still occupy a worker for an unsafe duration.

How is ReDoS different from a normal slow regular expression?

ReDoS is security-relevant when an attacker can trigger pathological matching behavior that threatens availability. The evidence should include reachable untrusted input, unhealthy growth across controlled sizes, and service impact. One slow benchmark is not enough; measure repeatable scaling and deployment concurrency.

Will a request timeout prevent parser CPU exhaustion?

Only if cancellation reaches the parser and stops its work. A proxy or client timeout may close the request while the backend thread continues consuming CPU. Process behavior after timeout reveals the difference, and a bounded disposable worker provides a fallback where the parser cannot be interrupted safely.

How can we test complexity safely in CI?

Small geometrically increasing inputs, a pinned environment, repeated measurements, strict timeouts, and a disposable worker provide a safe benchmark shape. Absolute ceilings and growth ratios answer different questions, while instruction or work counters can reduce timing noise well before resource exhaustion.

Is limiting input length enough to fix a superlinear parser?

It is useful containment but may not be a durable fix. A quadratic path can still be expensive within an allowed length, and business requirements may later raise the limit. Correct the algorithm or pattern, guarantee progress, enforce phase-specific budgets, and retain the length limit as defense in depth.

Complexity Is Part of Parser Correctness

A stable growth curve tells us more than one payload that happens to time out. By isolating the expensive phase and increasing a bounded pattern in steps, a team can see whether work remains proportionate to input or starts to accelerate. That slope can become a build criterion even when each individual case still fits beneath a generous timeout.

The eventual fix may remove repeated scans, place budgets earlier, improve cancellation, or move parsing away from scarce shared threads. Keeping the original growth fixture beside the affected dependency preserves the reason for those controls. A parser is not fully correct when it reaches the right answer only after doing an unpredictable amount of work.

#ApplicationSecurity #ReDoS #ParserSecurity #DenialOfService #SecureCoding #AutonomousPentesting