# Algorithmic complexity testing Algorithmic complexity is a performance property: how an operation's cost grows with the size of its input. A routine that is accidentally $O(n^2)$ where $O(n \log n)$ was intended is invisible at test sizes ($n = 10$) and dominates at production scale ($n = 10^6$). The measuring methods answer the *average* case: [load and stress testing](https://quality.stereobooster.com/load-and-stress-testing.md) under a representative profile, [microbenchmarking](https://quality.stereobooster.com/microbenchmarking.md) of a function, [profiling](https://quality.stereobooster.com/profiling.md) of a realistic dataset. The methods here target the *growth curve* and the *worst case*, which an average-case benchmark never provokes. When an attacker can *choose* the input that forces the worst case, the same cost becomes a denial of service, a [security](https://quality.stereobooster.com/security.md) concern rather than a performance one. ## What it catches Cost that grows faster than its input: - **Accidentally-quadratic hot paths.** A parser, serializer, or membership loop that degrades to $O(n^2)$. The same accidental growth can hide in a resource count rather than CPU time, as in the database N+1 query. - **Worst-case denial of service.** An attacker-chosen input that forces the pathological path. Its regex form (ReDoS) is caught before it runs by a static [linter](https://quality.stereobooster.com/deep-static-analysis.md#redos); the general case needs complexity fuzzing. ## Approaches and tools ### Empirical big-O regression Run the operation across a sweep of input sizes and fail the build when the growth curve bends superlinear: roughly, when $t(2n)/t(n)$ trends toward 4× rather than ~2×. That is an ordinary [microbenchmarking](https://quality.stereobooster.com/microbenchmarking.md) or [load and stress testing](https://quality.stereobooster.com/load-and-stress-testing.md) gate applied across sizes, not a separate tool. No reliable *static* detector for the "accidentally quadratic" case exists. A common special case needs no size sweep at all: the database **N+1 query**. One query is issued per row instead of one for the whole set, so the query count grows with the row count where it should stay constant. Query count is a cleaner signal than wall-clock time here, and dedicated tools assert on it directly: [Bullet](https://github.com/flyerhzm/bullet) flags N+1 queries and unused eager loading in a Rails app during development and test runs; in Java, [QuickPerf](https://github.com/quick-perf/quickperf)'s `@ExpectSelect(n)` annotation fails a JPA/Hibernate test when the query count exceeds a bound; Django ships `assertNumQueries(n)` as a built-in, and the `nplusone` package surfaces the lazy loads at runtime. ### Complexity fuzzing Where the growth-curve gate requires the sizes to be named in advance, complexity fuzzing searches for the pathological input a reviewer will not imagine. It evolves inputs to maximize execution cost: [SlowFuzz](https://github.com/nettrino/slowfuzz) (Petsios et al. 2017)[^petsios2017] and the later, AFL-based [PerfFuzz](https://github.com/carolemieux/perffuzz) (Lemieux et al. 2018)[^lemieux2018] are the two research tools. It is a specialization of [fuzzing](https://quality.stereobooster.com/fuzzing.md): where an ordinary fuzzer searches for an input that *crashes*, a complexity fuzzer searches for one that is *slow*. Aimed at parsers, serializers, and hash-table code on a security boundary, it is also the most direct answer to the worst-case denial-of-service question. ## When to use, when not **Use:** - To catch an N+1 query on any request that loops over a collection and touches the database or an external service. A query-count assertion is cheap and pins the regression precisely. - To harden code that parses, deserializes, or hashes attacker-controlled input, where the worst case sits on a security boundary. Complexity fuzzing searches for the pathological input directly. - To gate a hot library function with an empirical big-O sweep when its inputs grow unboundedly in production. **Don't:** - For code whose input is bounded and small. The growth curve is irrelevant and a big-O sweep is noise. - As a proof of safety. A clean complexity fuzz run found no blow-up in the budget it ran, nothing more. ## Evidence - **Search finds pathological inputs automatically.** SlowFuzz drove algorithmic-complexity blow-ups in real-world libraries by evolutionary search over the input (Petsios et al. 2017)[^petsios2017]; PerfFuzz, maximizing each program location's execution count, exercised the most-frequently executed branch 5–69× more often than SlowFuzz on four C libraries (Lemieux et al. 2018)[^lemieux2018]. ## Related **Performance** These aren't competing choices — they answer different performance questions, at different scopes. [Microbenchmarking](https://quality.stereobooster.com/microbenchmarking.md) measures the cost of one small unit in isolation. [Profiling](https://quality.stereobooster.com/profiling.md) explains *where* time or memory goes in a real workload. [Load and stress testing](https://quality.stereobooster.com/load-and-stress-testing.md) drives the whole system under traffic to find where it degrades. You reach for whichever fits the question. **Bounding a program's cost** All three ask how much a computation costs, and meet the same undecidable core (the halting problem) at different guarantee levels. [Termination analysis](https://quality.stereobooster.com/termination-analysis.md) proves the qualitative floor: does the program halt at all, over every input. [Worst-case execution-time analysis](https://quality.stereobooster.com/wcet-analysis.md) assumes it halts and proves a sound *upper* bound on running time for the modeled hardware. Algorithmic complexity testing trades proof for search: it hunts an input that drives cost past its expected growth, witnessing a *lower* bound on how bad the worst case gets. Termination is the precondition, since a runtime that might be infinite has no bound to compute. WCET and complexity testing then bracket the same worst case from opposite sides: WCET over-approximates (sound, never optimistic, sometimes pessimistic), while complexity testing under-approximates (a blow-up it finds is real, but finding none proves nothing). The two sound static methods and the one empirical search are the formal and the testing answers to a single question about resource use. ## Classification - **Quality dimensions:** Performance, Security. - **Area:** Code whose cost grows with input size: parsers, serializers, hash tables, database access, hot loops; scalability review and worst-case (denial-of-service) hardening. - **Guarantee:** Empirical: a found input proves a blow-up exists; not finding one proves nothing about the worst case. ## Referenced by - [Performance](https://quality.stereobooster.com/performance.md) · Quality dimensions - [Security](https://quality.stereobooster.com/security.md) · Quality dimensions - [Deep static analysis](https://quality.stereobooster.com/deep-static-analysis.md) · Methods - [Fuzzing](https://quality.stereobooster.com/fuzzing.md) · Methods - [Search-based software testing (SBST)](https://quality.stereobooster.com/search-based-software-testing.md) · Methods ## References [^petsios2017]: Petsios, Theofilos, Jason Zhao, Angelos D. Keromytis, and Suman Jana. 2017. "[SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities](https://arxiv.org/pdf/1708.08437)." *Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS '17)*, 2155–68. . [^lemieux2018]: Lemieux, Caroline, Rohan Padhye, Koushik Sen, and Dawn Song. 2018. "[PerfFuzz: Automatically Generating Pathological Inputs](https://www.carolemieux.com/perffuzz-issta2018.pdf)." *Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2018)*, 254–65. . ## Acronyms - CCS — Calculus of Communicating Systems - JPA — Java Persistence API - SBST — search-based software testing - WCET — worst-case execution time