All posts
Concept ~3 min read

DoS is more than DDoS: algorithmic-complexity attacks

Most people hear ‘DoS’ and picture a flood of traffic. A cheaper denial of service is a single small request that hits super-linear code.

“DoS” covers more than floods

Ask most developers what a denial-of-service attack is and you’ll hear some version of: a botnet floods the server with traffic until it falls over. That’s DDoS: distributed and volumetric, a question of bandwidth and packets. It’s real, but you mostly handle it with infrastructure: a CDN, rate limits, autoscaling, a scrubbing provider.

The denial of service an application developer should worry about has a different shape. It is not a flood. It is one small, well-formed request (sometimes a few hundred kilobytes, sometimes a few hundred bytes) that makes the server do a disproportionate amount of work. There is no botnet and no bandwidth requirement, and often no authentication. One request pins a worker at 100% CPU (or runs it out of memory) for seconds or minutes. Send a handful in parallel and the service is down.

This family is called algorithmic-complexity DoS, and it lives in your code, not your network.

The variants worth knowing

  • ReDoS (regular-expression denial of service). A regex with “catastrophic backtracking” (typically nested or ambiguous quantifiers like (a+)+, or a lazy [\s\S]*? scanning for a terminator that never comes) can degrade from linear to quadratic or exponential time on a crafted input. A pattern that validates an email in microseconds can take seconds on a 1 KB string built to maximise backtracking.
  • Accidentally quadratic parsers. No regex needed: an O(n²) loop over untrusted input (re-scanning, repeated string concatenation, nested membership tests) is an availability bug once the input size is attacker-controlled.
  • Decompression or “zip” bombs. A few KB that expand to gigabytes. Any code that gzip/zlib/zip-inflates untrusted data without a size cap is a target.
  • Entity expansion (“billion laughs”). XML (and some YAML) with recursively nested entities expands to gigabytes of memory from a tiny document. It is the XXE-adjacent DoS.
  • Hash-flooding. Worst-case O(n²) hash-table behaviour when an attacker can supply colliding keys (historically a wave of web-framework CVEs).
  • Unbounded recursion or allocation. Deeply nested JSON/markdown/HTML that blows the stack or allocates without limit.

What these share: somewhere, untrusted input chooses the size of the problem, and the algorithm scales worse than linearly in that size. Volumetric defenses (rate limits, CDNs) barely help, because the attacker isn’t sending much. They send the worst possible small input.

A concrete one: the regex that took down a global network

A widely cited production ReDoS is public and well documented. On 2 July 2019 Cloudflare deployed a new WAF rule whose regular expression contained the fragment .*(?:.*=.*). Two greedy .* compete for the same characters around an =, so when a match fails the backtracking engine tries every way of splitting the input between them, and that work grows super-linearly with input length. Deployed to every edge server at once, the rule pinned the CPUs that handled HTTP traffic worldwide, and Cloudflare’s network largely stopped serving for about half an hour. No attacker was involved: ordinary request traffic was enough.

Cloudflare’s postmortem (“Details of the Cloudflare outage on July 2, 2019”) is worth reading in full. Two of its lessons generalise:

  • The pattern looks harmless. Nothing about .*(?:.*=.*) signals danger to a reviewer. You find these by measuring, not by reading.
  • The structural fix is a linear-time engine. Cloudflare’s follow-up was to move toward regex engines that guarantee linear run time (RE2- or Rust-style, no backtracking). For code you own, the equivalent is a non-backtracking engine, or replacing the regex with a hand-written linear parser.

The same sub-family shows up in parsers. A lazy [\s\S]*? scanning for a terminator that never arrives re-scans the rest of the input once per opener, which is O(n²). For a real library bug of exactly that shape, see the PEM ReDoS in @peculiar/utils.

Where to look

When you threat-model availability, don’t stop at “can someone flood us?” The usual suspects are regexes over untrusted strings, decompression, XML/YAML/JSON/Markdown parsers, and anything that sorts or de-duplicates attacker data. Then measure the scaling: double the input and time it. If the time more than doubles, you have a lead.

Takeaway

Find where small input sets the workload.

Ask where an untrusted input decides how much work you do, whether that work grows faster than the input, and measure it by doubling the input size.