1 Introduction↩︎

Software performance—typically characterized by time efficiency and execution predictability—is a fundamental pillar of software quality. While performance degradation is generally viewed as a routine engineering concern, it escalates into a critical security threat when adversaries can intentionally exploit structural bottlenecks to mount Denial-of-Service (DoS) attacks. The primary vector for these attacks is Algorithmic Complexity Vulnerabilities (ACVs) [1]–[6], classified by MITRE as CWE-407 [7]. ACVs stem from inefficient algorithms that remain latent during normal operation but exhibit catastrophic runtime slowdowns when triggered by specific, worst-case inputs. Real-world incidents, such as the quadratic-time behavior in Python’s integer conversion (CVE-2020-10735) [8] and Perl’s email parsing (CVE-2014-1474) [9], demonstrate how a single ACV can paralyze critical services across massive software ecosystems.

Detecting ACVs is inherently challenging because their activation often depends on intricate program logic, such as nested loops, recursion, and specific data dependencies. Prior research has explored ACV detection using static and dynamic techniques, including fuzzing (e.g., SlowFuzz [3], HotFuzz [6], Singularity [10]), symbolic execution (e.g., WISE [11], SPF-WCA [12]), and hybrid approaches (e.g., Badger [13], Acquirer [4]). While effective on specific programs, these methods often rely on extensive dynamic exploration or significant manual driver development. This reliance limits their scalability to massive software ecosystems or language runtimes that comprise thousands of diverse library APIs.

Shadow Complexity.

The fundamental barrier to scaling these analyses is what we term shadow complexity: hidden computational costs induced by library APIs(or language built-ins) that appear computationally trivial at the call sites (e.g., string concatenation via s+=x) but exhibit non-trivial internal complexity. ACVs are particularly insidious when they arise from such hidden costs. Because these abstractions are widely distributed and implicitly trusted, a single API with an unmodeled shadow runtime bottleneck can quickly become an ecosystem-wide risk. This opacity creates a significant blind spot in traditional security audits: while reviewers typically track explicit control flow, they often miss the amplified execution cost of seemingly harmless calls. Addressing this gap requires scalable, automated detection methods capable of exposing these hidden bottlenecks. However, building such a system surfaces two fundamental practical challenges:

Challenge : Scalable & Context-Aware Screening.

As exhaustive dynamic validation of every function across a massive codebase is computationally infeasible, the first challenge is identifying a high-coverage candidate set while preserving a strict validation budget. This screening cannot rely solely on identifying explicit syntactic loops; it must account for shadow complexity whose behavior depends on the underlying implementation. For instance, a seemingly benign pattern like repeated string concatenation (s += x) in Python has implementation-dependent complexity. While CPython often optimizes this to near-linear behavior by reusing the left-hand string object, other Python implementations such as PyPy may not apply the same optimization, causing the identical source code to exhibit quadratic copying behavior. Consequently, initial screening signals must be computationally cheap yet sensitive to these hidden, implementation-dependent bottlenecks, without relying on language-specific instrumentation or manual driver development.

Challenge : Automated & Robust Validation.

The second challenge is confirming the worst-case behavior of these candidates while minimizing false positives. The system must automatically reconstruct compact executable contexts to synthesize worst-case inputs and faithfully exercise the target. Furthermore, as illustrated by runtime-specific behavior in Python implementations, ACV detection cannot rely on isolated wall-clock measurements. The analysis must robustly distinguish true algorithmic scaling issues from wall-clock noise introduced by runtime effects, such as Garbage Collection (GC) cycles and Just-In-Time (JIT) fluctuations.

.

To address these challenges, we introduce , a scalable, language-extensible ACV detection system that combines lightweight static screening, execution context recovery, LLM-assisted worst-case input construction, and measurement-based validation. Unlike prior tools that are tied to specific languages or require heavy manual effort to scale, leverages a staged architecture to efficiently identify and automatically confirm ACVs across diverse library runtimes. Specifically, has the following advantages.

Shadow Complexity Guided Screening.

To address Challenge , performs lightweight screening guided by shadow complexity, focusing on functions whose call chains may hide non-trivial costs behind library APIs. This stage combines lightweight syntactic and contextual checks to identify functions whose behavior depends on input and may amplify hidden computational costs. This allows to maintain a high-coverage candidate set while preserving a strict validation budget by filtering out functions with trivial or constant-time behavior.

Language-Extensible Execution Context Reconstruction.

To address the manual overhead of Challenge , reconstructs compact executable contexts using project level symbol information. This language-extensible approach eliminates the need for manual driver or harness development, allowing the system to transition from source code to executable tests without language-specific instrumentation.

Robust Validation & Growth Inference.

Once an executable execution context is established, uses LLM to synthesize test inputs across varying sizes to trigger worst-case execution and monitors wall-clock time. To ensure the validity of our findings, we apply a robust statistical inference module that filters out runtime jitter from GC and JIT fluctuations. An ACV is confirmed only when empirical execution time exhibits non-linear growth, providing language-independent evidence.

We evaluated on WISE, a benchmark suite for worst-case complexity analysis, and on five real-world projects: CPython, JDK, Zig, Rustc, and vLLM [14]. Across these projects, uncovered +28+3+11+8 previously unknown ACVs, of which +5+3+11+4 have been confirmed by maintainers to date. Among the confirmed cases, +2+1+1+1 are under active maintainer processing and +0+1+2+0 have already been fixed. These findings include cases in mature language runtimes and infrastructure software, and have informed security discussions and planned refactoring of the CPythonemail module.

Contributions.

We make the following contributions.

• We identify and define shadow complexity as a critical blind spot in current ACV detection—specifically, hidden computational costs within library APIs that elude manual auditing. We characterize the recurring code patterns that expose systems to this phenomenon.

• We design and implement , a staged, language-extensible, automated, and scalable detection system that reduces manual effort in ACV discovery by combining shadow complexity guided candidate screening, language-extensible execution context reconstruction, LLM-assisted worst-case input construction, and measurement-based growth validation.

• We demonstrate ’s efficacy by uncovering previously unknown ACVs in widely deployed systems (CPython, JDK, Zig, Rustc, and vLLM). These findings have yielded confirmed fixes and assigned CVEs, highlighting the tool’s practical utility across diverse software ecosystems.

2 Background & Motivation↩︎

2.1 Problem Definition↩︎

Algorithmic complexity vulnerabilities (ACVs) [1], [3], [7] refer to program behaviors whose execution time grows superlinearly with input size (e.g., \(\Omega(n^2)\) or worse) for some input family parameterized by \(n\), potentially leading to performance degradation.

ACVs often arise from interactions between control flow and data structures, or from library and API calls whose internal implementations exhibit non-trivial computational cost. Such behaviors may remain invisible at the call site but can be amplified when exercised on large or adversarial inputs.

This work focuses on identifying ACVs using syntactic signals and execution-time evidence, where scalability issues are validated through observed runtime growth trends under increasing input sizes.

2.2 Large Language Models↩︎

LLMs trained on large-scale code corpora learn rich syntactic and semantic patterns of source code [15]. Unlike traditional program analysis methods that rely on manually designed, language-specific rules, LLMs enable data-driven and unified analysis across programming languages. LLMs are also promising for detecting algorithmic complexity vulnerabilities, as they can reason about loops and recursion to identify potential performance risks. In addition, LLM-generated function summaries can assist static analysis and reduce false positives [16]. Beyond vulnerability detection, LLMs support cross-language code understanding and have demonstrated strong potential in automated unit test generation, achieving higher coverage than traditional methods [17]. Overall, LLMs introduce data-driven intelligence into program analysis and software testing.

Building on these capabilities, this work leverages LLMs to analyze program semantics related to ACVs. LLMs are used to synthesize executable, size-controlled input generators. then classifies complexity from measured execution-time trends.

2.3 Motivating Example: Shadow Complexity↩︎

Figure 1 shows a representative example from CPython. The function expandvars repeatedly searches a string for variable references and reconstructs the string after each replacement. Although the loop body appears to invoke only simple library operations, each iteration may scan or copy a string whose length is proportional to the input size. For an input containing many variable references, the hidden costs in each iteration accumulate across the loop, causing the total running time of expandvars to grow quadratically.

This example illustrates what we call shadow complexity: computational costs hidden inside API calls or operations provided by the language that are not visible at the call site. Such costs often reside in library or API implementations that appear to be constant time from the caller’s perspective, but may perform linear or superlinear work over input data. They are difficult to recognize when the implementation is hidden behind library abstractions or native interfaces such as a C ABI, where the callee’s performance behavior is not explicit and may differ across runtimes. When such operations are invoked repeatedly under control flow that depends on input, these hidden costs can be amplified into superlinear runtime behavior.

This motivates to consider not only explicit loops and recursion, but also API calls whose hidden costs can be amplified when repeatedly executed under control flow that depends on input.

3 Approach↩︎

Figure 2 illustrates the workflow of . When analyzing large-scale projects, follows a four-stage pipeline that addresses the two challenges outlined in the introduction: the first stage performs high-density selection of target functions, while the latter three stages jointly recover missing context, construct verifiable worst-case inputs, and robustly infer complexity.

Given the project, performs lightweight static analysis to quickly identify functions that may exhibit ACVs.

To construct execution context for a target function, extracts a whole-program symbol index that records definitions, source ranges, and reference links. Given a target function, resolves its dependencies via the index and expands a dependency closure over project-defined symbols. The resulting context is rendered into a compilable artifact, which is used by later stages to synthesize and validate a runnable Candidate.

Given the recovered context, constructs an executable Candidate consisting of a size-parameterized input generator and an execution harness. The harness initializes required state, invokes the target function once, and records execution time. When multiple valid generators are produced, keeps the one whose probe executions exhibit the strongest empirical growth.

validates each Candidate by executing it under increasing input sizes. Execution times are measured for each input size, and the resulting growth trend is used to infer the empirical complexity of the target function.

3.1 Static Analysis↩︎

This stage addresses Challenge  by extracting a focused set of target functions from a given project through a lightweight, language-extensible static scan. For example, CPython contains more than 15  functions, while the JDK contains more than 178  functions. ¹ However, only a small fraction of these functions can actually trigger an ACV, making exhaustive complexity analysis both inefficient and unnecessary. To narrow down the search space, we apply this scan using code patterns that are known to be prone to superlinear time complexity. Among such patterns, a natural starting point is explicit loop and recursion structures, as they are common syntactic indicators of potentially superlinear behavior. However, relying solely on these structures remains too coarse at large-project scale. We therefore incorporate shadow complexity sinks to refine the static patterns and improve the density of selected target functions.

Specifically, we define two categories of code patterns that are prone to triggering ACVs.

Nested Loops and Recursion.

Nested loops and recursion are common structural features of ACVs: when iteration bounds or recursion depth depend on external inputs, runtime costs can be multiplicatively amplified. Prior work (e.g., DISCOVER [5] and Acquirer [4]) likewise often takes loops as an entry point, first locating input-sensitive loop structures and then applying manual inspection or dynamic validation to confirm risk. Motivated by this, we leverage loop/recursion structure to identify and prioritize candidate ACVs.

Shadow Complexity Sinks.

Shadow complexity sinks are library APIs whose cost is implicit at the call site but depends on the size of an input-derived operand. When invoked inside input-dependent loops or recursion, such hidden costs can be repeatedly amplified and may trigger ACVs. Table 1 lists representative sink families across common language runtimes. uses these families to refine screening based on loops and recursion.

Figure 3 shows a representative Python example where \(N=|\texttt{methodname}|\) and the worst-case input is \((\texttt{<})^N\). The guard slice methodname[:1] copies at most one character. By contrast, because CPython strings are immutable, methodname[1:] creates a new string by copying the remaining suffix. When the current length is \(k\), this slice costs \(\Theta(k)\), so the total work is \(\sum_{k=1}^{N}\Theta(k)=\Theta(N^2)\). This copying cost is hidden in slicing and grows with string length. uses such hidden costs together with loops controlled by input to select target functions.

3pt

3.2 Context Recovery↩︎

As a prerequisite for addressing Challenge , recovers the context needed to construct worst-case inputs. For a target function, the function body alone is often insufficient: worst-case behavior may depend on surrounding project context. Without this context, input construction may fail to produce executable tests or may exercise only partial paths. We therefore recover a compact context before constructing worst-case inputs.

performs context recovery by first building a symbol index for the project. The index records program symbols, their source ranges, and reference information extracted from the project source code. Starting from the target function, expands a bounded dependency closure: when a recovered symbol references another symbol defined in the project, the corresponding definition is retrieved from the index and added to the context. The closure also preserves enclosing declarations when they are required to make the recovered fragment meaningful. This process produces a compact context containing the target and the dependencies needed by later stages, while avoiding the cost of including the entire project.

The recovered context is emitted as a context artifact and rendered into a compilable code fragment, which serves as the foundation for subsequent worst-case input construction. The context artifact records recovered symbols and unresolved references, and the rendered fragment provides the source-level definitions used by the input construction stage.

Figure 4 illustrates the context recovery process for a representative target function, treeSearch. The process begins from an unresolved context in which the target function references symbols whose definitions are not yet available. The recovery procedure resolves these references through the symbol index and incorporates the corresponding definitions into the context. The process continues until the dependency closure reaches a fixed point or a predefined recovery budget is exhausted. This recovery procedure enables subsequent analysis of the target function under an execution context with resolved dependencies, without requiring the full project source code.

3.3 Worst-Case Input Construction↩︎

Given the recovered context, this stage constructs an executable Candidate that can be used for subsequent dynamic validation. A Candidate consists of a size-parameterized input generator and an execution harness. Given an input size \(n\), the generator produces concrete arguments and optional state-building inputs intended to exercise high-cost execution paths of the target function.

Formally, the generator is a size-parameterized mapping \[G: \mathbb{N} \rightarrow A_1 \times \cdots \times A_k,\] where \(G(n) = (arg_1, \ldots, arg_k)\) denotes the inputs consumed by the execution harness. For simple targets, these arguments are passed directly to the target function. For targets whose behavior depends on receiver objects or internal state, they may instead include constructor arguments or state-building parameters. The parameter \(n\) controls the dominant size measure of the generated inputs, which is required to grow as \(\Theta(n)\).

The generator is synthesized by an LLM rather than manually designed. The prompt provides the target signature, recovered context, harness contract, and input-size parameter \(n\). Figure 5 summarizes this prompt structure. The LLM is asked to return executable generator code that maps \(n\) to inputs for the harness. Compilation errors, execution failures, and size-check violations are used as repair feedback.

Before accepting a generator, performs a lightweight size check over a small range of input sizes. Generators whose produced inputs do not preserve the intended size relation are rejected and repaired. Since a single generator may miss the intended worst-case path, asks the LLM to propose multiple input-generation strategies under the same harness. Each strategy describes a different way to construct inputs whose size is controlled by \(n\) and whose structure is intended to exercise a high-cost execution path. The strategies are instantiated as candidate generators, and keeps the valid generator with the strongest measured growth on probe executions.

Formally, given a set of candidate generators \(\mathcal{G}={G_1,\ldots,G_m}\), selects \[G^* = \arg\max_{G_i \in \mathcal{G}} \mathrm{score}(G_i),\] where \(\mathrm{score}(G_i)\) is computed from the measured growth of the target execution time on probe input sizes. The selected generator \(G^*\) is embedded with the harness to form the final Candidate. Figure 6 illustrates a synthesized Candidate for _parseparam in CPython.

3.4 Dynamic Validation↩︎

To make worst-case claims verifiable and to robustly determine complexity (Challenge ), grounds its judgment in measured scaling behavior rather than direct LLM inference. Given an accepted Candidate, executes it with increasing input sizes, collects runtime measurements \((n,t)\), and performs curve-fitting-based growth inference over the measured trace. This measurement-based validation reduces the risk that inaccurate LLM reasoning is directly reported as an ACV. As a design principle, avoids instrumentation of the program under test to preserve generality. Instead, it measures the execution time of the target function in real execution scenarios, making validation applicable across diverse runtimes.

adopts adaptive sampling to characterize execution-time growth under noisy wall-clock measurements. Because wall-clock measurements may be affected by runtime effects such as GC and JIT, timings on very small inputs can be less reliable, whereas overly large inputs are more likely to time out. therefore first performs boundary probing to identify a feasible input-size range. The lower bound avoids trivial executions with less reliable timings, while the upper bound limits excessive timeouts. Algorithm 7 illustrates the sampling procedure.

Within the identified range, prioritizes logarithmically uniform input sizes. This choice follows the common model \(T(n)=Cn^k\), where the complexity order is reflected by the slope in log–log space. Linear spacing would allocate many samples to the low-\(n\) region, where execution times are often less informative for fitting growth trends. When the interval becomes too narrow for logarithmic subdivision, falls back to the arithmetic mean to ensure progressive sampling.

For each sampled input size, executes the Candidate three times and aggregates the resulting measurements into a representative runtime for that size. This repeated measurement also reduces the influence of transient runtime noise. Executions that fail or exceed the per-run timeout are discarded. After collecting sampled data points, classifies the measured growth into four categories: Low-order (at most \(O(n \log n)\)), Polynomial (e.g., \(O(n^2)\), \(O(n^3)\)), Exponential (e.g., \(O(2^n)\), \(O(n!)\)), and Unknown. Unknown is assigned when valid data are unavailable or insufficient for reliable classification. This coarse-grained taxonomy suffices to separate low-order behavior from ACV-relevant polynomial or exponential growth.

5pt

Legend: = ; = ; = ; NA = not applicable.

4 Evaluation↩︎

is implemented in Rust and follows a language-extensible design. It leverages LLMs to reason about program semantics and execution behavior, without relying on language-specific analyses. In our evaluation, we instantiate for four widely used programming languages, Java, Python, Zig, and Rust, to demonstrate its effectiveness in practical settings. We evaluate our approach by answering the following research questions:

4.1 Experimental Setup↩︎

To address RQ1, we compare with two representative and publicly available ACV analysis tools, namely SPF-WCA [12] and Badger [13]. SPF-WCA infers algorithmic complexity by symbolic execution over worst-case paths, which is conceptually closest to our approach, while Badger combines fuzzing and concolic execution to search for worst-case inputs under fixed input sizes. Other ACV detectors, such as HotFuzz [6] and Acquirer [4], are not publicly available and are thus excluded from comparison. Since both SPF-WCA and Badger target Java programs, we use the Java-based WISE [11] benchmark provided in the SPF-WCA repository. can analyze the entire WISE benchmark automatically, whereas Badger requires significant manual effort.

To address RQ2, we use the benchmark, derived from the email module of CPython, a widely used module from the Python standard library, to evaluate the contributions of ’s major components as well as the sensitivity of its performance to the choice of underlying LLM. Static analysis yields 281 target functions. Based on the constructed ground truth, 69 of them exhibit ACV behavior. We treat analysis results classified as Polynomial or Exponential as indicating the presence of an ACV. Ground truth is constructed by systematically inspecting all target functions in the email module, followed by independent manual review by graduate student security researchers with more than three years of security experience. Any disagreements are resolved through discussion to reach a final consensus. We release this set as the benchmark for evaluating complexity-analysis techniques.

All experiments were conducted on an AMD machine with 32 threads and 96 GB of memory. DeepSeek-V4-Flash was used as the underlying LLM in all experiments, except for those in Section 4.3. We additionally evaluate GPT-4.1 [19] and DeepSeek-V3.2 [20] to compare the impact of different LLMs. This comparison examines whether remains effective across different LLM backends under the same analysis pipeline.

4.2 Benchmark Analysis↩︎

Functions from the WISE benchmark are analyzed, and the results are evaluated from two complementary perspectives: (1) the agreement between the time complexity reported by each tool and the ground-truth complexity, and (2) the average analysis time of the different tools (Table 2).

Table 2 summarizes the analysis results for the WISE benchmark across different tools. The column Real reports the ground-truth worst-case time complexity for each benchmark. For and SPF-WCA, the table reports the inferred complexity class together with the number of executions performed and the corresponding input size ranges. Badger does not infer time complexity and is therefore reported as NA in the complexity column, while its execution counts and input size ranges are still shown for comparison.

With dynamic validation, correctly identifies the ground-truth worst-case complexity class for all benchmarks in the WISE dataset. This result shows that can expose worst-case time-complexity behavior across both graph algorithms and data-structure operations. In contrast, SPF-WCA underestimates TSP, reporting Polynomial rather than the ground-truth Exponential class, which is consistent with the results reported in its original paper. For the remaining benchmarks, SPF-WCA agrees with the ground-truth complexity class reported in the WISE benchmark.

Table 2 also reports the average analysis time of , SPF-WCA, and Badger on the WISE dataset, where Avg. Time denotes the average time required to analyze a single benchmark (i.e., one target function). Since a single execution of Badger targets only a fixed input size, we run Badger with input sizes \(N\) ranging from 2 to 6 for each benchmark; at least five data points are required to reliably distinguish among Low-order, Polynomial, and Exponential time complexity classes. In contrast, SPF-WCA is executed using its default configuration, except for the TSP benchmark, where the maximum input size is set to \(N=7\), as \(N=8\) cannot be completed within the 72-hour time limit. As shown in the table, achieves a substantially shorter average per-benchmark analysis time, completing the analysis 4.7\(\times\) faster than SPF-WCA and 8.1\(\times\) faster than Badger.

4.3 Sensitivity Analysis↩︎

In this section, we present a sensitivity analysis of , focusing on four factors: (a) Context Recovery, (b) Multiple input-generation strategies, (c) Dynamic Validation, and (d) LLM model selection. Since Stage 1 Static Analysis only performs high-density candidate selection without classification, we evaluate it separately from downstream accuracy. For all other configurations, a function is considered an ACV if it is classified as Polynomial or Exponential. We evaluate each setting against the ground truth defined in Section 4.1, and report FPR, FNR, precision, recall, and F1 score. Table ¿tbl:tab:sensitivity-summary? summarizes configurations that disable key components or replace the underlying LLM backend.

Static Analysis.

Static Analysis performs lightweight static analysis for high-density candidate selection, quickly identifying target functions that may exhibit ACVs. In the email module (529 functions), Stage 1 selects 281 targets and prunes the remaining 248. Among the pruned functions, only two contain previously unseen dominant ACV sinks. Thus, Stage 1 misses only two previously unseen dominant sinks while removing 46.9% of functions from consideration.

Effectiveness of Context Recovery.

The contribution of Context Recovery is evaluated using a variant w/o Context. In this setting, generates Candidates using only the target function and omits recovered context. This substantially increases the FNR, because unresolved symbols can determine the conditions and state needed to trigger high-cost paths. With Context Recovery enabled, reconstructs these dependencies and detects additional ACVs that cannot be exposed from incomplete contexts.

Effectiveness of Multiple Input-Generation Strategies.

Compared with the default setting, w/o Strat. reduces recall from 71.0% to 53.6% and F1 from 67.6% to 56.5%, while increasing FNR from 29.0% to 46.4%. Its FPR remains nearly unchanged (12.7% versus 11.8%). This indicates that using only a single generator mainly causes to miss more true ACVs, rather than substantially reducing false positives. These results show that multiple strategies expose worst-case behavior more effectively than a single generator.

Impact of Dynamic Validation.

The contribution of dynamic validation is evaluated using a variant w/o dynamic validation. In the w/o Dyn.setting, classifies complexity from the recovered context and generated Candidate without runtime measurements. This conservative setting lowers the FPR from 12.7% to 3.3%, but sharply increases the FNR from 29.0% to 92.8%, causing most true ACVs to be missed. With dynamic validation enabled, grounds complexity inference in execution-time measurements across input sizes, substantially improving recall and F1.

Sensitivity to LLM Choice.

The robustness of to different LLM backends is evaluated by running with DeepSeek-V4-Flash [21], GPT-4.1 [19], and DeepSeek-V3.2 [20] under identical experimental settings. Across these LLMs, achieves broadly comparable performance, with only moderate variations in FPR, FNR, precision, recall, and F1. This suggests that does not rely on a single proprietary model and that its measurement-based validation provides stable performance across different LLM backends.

Comparison with Cost-Guided Fuzzing.

HypoFuzz [22], a feedback-directed Python fuzzer, is evaluated on using runtime as the feedback objective. We use runtime as the feedback objective and classify a target as an ACV when replay validation over the best discovered input family shows Polynomial or Exponential growth. Making this baseline work required non-trivial adaptation: we had to construct specific generation strategies, connect them to recovered executable harnesses, and replay the best input families for complexity classification. Even after this manual adaptation, HypoFuzz produces no false positives but finds only 5 of 69 ACV-positive targets in the full benchmark, yielding a high FNR. This result indicates that cost-guided fuzzing can discover some worst-case inputs, but its coverage on parsing-heavy API surfaces depends heavily on time-consuming domain-specific strategy engineering.

Cost and Scalability.

LLM usage in is localized to worst-case input construction. Static Analysis, Context Recovery, and Dynamic Validation do not require LLM calls. On , using DeepSeek-V4-Flash, each target function consumes 32K tokens on average, including 23K input tokens and 9K output tokens. This corresponds to an average monetary cost of approximately $0.006 per target.

2pt

4.4 RQ3: Real-World Detection↩︎

1.5pt

To answer RQ3, we apply to the five real-world projects listed in Table [tbl:tab:bug-count]: CPython, JDK, Zig, Rustc, and vLLM. These projects cover language runtimes and infrastructure software written in Python, Java, Zig, and Rust. For each language, we implemented only the language-specific parts of the pipeline: parsing and symbol extraction. This required 1,735 LOC for Python, 1,218 LOC for Java, 391 LOC for Zig, and 596 LOC for Rust; the Python implementation was reused unchanged for both CPython and vLLM.

Table [tbl:tab:bug-count] reports the ACV cases found by and the subsequent developer response. In the table, Found denotes cases reported by after manual triage. Confirmed denotes cases acknowledged by maintainers as valid issues. In Progress and Fixed summarize subsequent developer responses. Unconfirmed cases are not treated as false positives. They remain pending maintainer confirmation or disclosure discussion.

Across these projects, finds +28+3+11+8 real-world ACV cases, of which +5+3+11+4 have been confirmed by maintainers. Among the confirmed cases, +0+1+2+0 have been fixed and +2+1+1+1 are in progress. The largest numbers of findings come from CPython and JDK, where analyzes thousands of functions in mature language runtimes. The findings in Zig, Rustc, and vLLM further demonstrate the applicability of the pipeline across different language implementations and infrastructure systems.

5 Real-World Findings and Case Studies↩︎

Building on the real-world detection results, we further analyze where the findings occur and what implementation patterns they reveal. This section first examines their module-level distribution, then summarizes common root causes and representative case studies.

5.1 Distribution and Root Causes↩︎

We further examine where the real-world ACV findings occur within CPython and JDK. These two projects contain enough findings to reveal module- and package-level patterns.

Figure 8 reports the largest ACV-containing modules and packages in CPython and JDK. For CPython, the dominant email module is analyzed separately in Section [par:email]; the figure shows the largest remaining modules. Overall, the findings are concentrated in parsing- and text-processing modules. argparse, idlelib, and xml account for the largest shares, followed by _pyrepl and inspect. These modules frequently parse structured text, manipulate strings, or incrementally build outputs, which can amplify copying and scanning costs. In the JDK, findings are less concentrated and mainly appear in security, utility, and networking packages. Overall, the findings concentrate in modules that process structured or text-heavy inputs.

To understand this concentration, we manually inspect the confirmed polynomial-time findings and identify several recurring implementation patterns. The dominant pattern is copy amplification from immutability. This pattern appears when parsers repeatedly slice input buffers (e.g., s = s[i:]) or when builders repeatedly append to a growing output (e.g., out += chunk). Although each operation is locally linear, placing it inside an input-dependent loop yields quadratic behavior.

A second pattern is linear-cost list operations inside loops. Examples include queue-like use of pop(0) and repeated scans over growing lists. We also observe ordering costs and multi-parameter scaling, where both the number of items and the size of each item grow with the input. These patterns explain why parsing-heavy and text-processing modules appear prominently in the distribution.

5.2 Case Study: CPython↩︎

Long-lived singledispatch case.

detects a long-lived exponential case in Python’s singledispatch implementation in functools. Its internal _c3_mro routine was introduced in 2013 (commit 3720c77e) as part of PEP 443 [23]. The routine implements C3 superclass linearization [24], [25] in pure Python. However, it recursively recomputes sub-results for each base class without memoization.

Figure 9 shows the adversarial inheritance pattern used to trigger this behavior. Each class inherits from the previous two classes, causing repeated recursive computation of overlapping superclass linearizations. As shown in Figure 10, the vulnerable implementation grows exponentially with inheritance depth, while a memoized implementation removes the blowup. This case shows that ACVs can remain latent for years in mature standard-library code, even when the underlying fix is local.

Shared email parser.

The message.py module in CPython’s email package implements core MIME-message logic, including the public Message and EmailMessage abstractions. It is used by mail-related software and application frameworks that process MIME-formatted data, such as Django’s email subsystem, Flask-Mail, and GNU Mailman [26]–[28]. These APIs often operate on partially user-controlled inputs, including message headers and multipart parameters.

Figure 11 shows how several public APIs share the same underlying complexity bottleneck. Parameter-related methods eventually call _get_params_preserve. This helper reparses the header value and invokes the quadratic-time parser _parseparam. Thus, even simple parameter queries can trigger the same worst-case parser. Mutating APIs further reconstruct the header, and higher-level routines may repeat these operations in loops. As a result, multiple findings in email/message.py are different entry points to a shared quadratic parser rather than independent bugs.

5.3 Case Study: Zig↩︎

Zig compiler frontend case.

also detects a compile-time ACV in Zig’s compiler frontend. The trigger is a valid integer switch statement with many prong items. During semantic analysis, Zig records previously seen integer ranges in a RangeSet; the original implementation linearly scans existing ranges on each insertion to detect overlaps. This makes switch validation quadratic in the number of prongs. When the number of switch branches becomes large, compilation time increases significantly and can become prohibitively slow. The issue applies to all optimization levels and targets because semantic analysis runs before backend code generation. The merged fix keeps the range set sorted and uses binary search to check overlaps, reducing the comparison cost to \(O(n\log n)\). This case illustrates a compiler front end ACV: an adversarial source program can cause large compile-time slowdowns.

6 Discussion↩︎

6.1 Implications for Library Maintenance↩︎

Our real-world findings suggest two implications for maintaining mature libraries and language runtimes. First, long-lived parsing and text-processing code should be revisited even when its functional behavior remains stable. In CPython’s email module, some vulnerable code dates back to 2007, and incremental maintenance allowed inefficient helper patterns to persist across many public entry points. This suggests that complexity-oriented testing can complement functional regression testing for mature library code. Second, implementation-specific optimizations should not be treated as a substitute for robust algorithmic design. For example, CPython can optimize some repeated string concatenation patterns in loops [29], [30], but the optimization applies only under specific conditions and may not hold across runtimes. Using index-based parsing, explicit buffers, or builder-style accumulation provides more portable performance behavior.

6.2 Limitations↩︎

is an empirical detection system rather than a complete oracle for all possible ACVs. Although our evaluation covers multiple ecosystems and languages, extending to additional languages or domains may require engineering effort for integration and adaptation to new environments. validates findings through executable Candidates and measured runtime growth, providing evidence for developer triage but not replacing maintainer assessment. In particular, whether a detected complexity issue should be treated as a security vulnerability or a performance bug can depend on the specific usage context and deployment conditions.

7 Related Work↩︎

Crosby and Wallach [1] introduced algorithmic complexity attacks, showing that adversarial inputs can induce worst-case execution and denial of service. Subsequent work explored automated detection using fuzzing and symbolic execution. Resource-guided fuzzers such as SlowFuzz [3] and HotFuzz [6] employ evolutionary search to maximize resource usage, while Singularity [10] frames complexity testing as synthesis over input generators. Symbolic approaches, including WISE [11] and SPF-WCA [12], provide precise path-level reasoning but suffer from path explosion, with extensions such as XSTRESSOR [31] mitigating this limitation. Hybrid systems such as Badger [13], ACQUIRER [4], and DISCOVER [5] combine static analysis with guided dynamic exploration, sometimes incorporating human guidance. However, these approaches often have difficulty automatically constructing calling contexts in complex programs. In contrast, combines context recovery with LLM-assisted worst-case input construction and measurement-based validation to generate executable evidence at scale.

With the advent of LLMs, several efforts have examined their use for vulnerability detection and repair [32]–[35]. These studies further evaluate LLMs across diverse vulnerability classes and datasets, and explore their effectiveness in related management tasks such as triaging, severity assessment, and patch validation. Our work differs in that we focus on algorithmic complexity vulnerabilities rather than general vulnerability detection or management tasks. We study how LLMs can be used as a supporting component in a language-extensible analysis pipeline to reason about program behavior related to time complexity.

Prior work has studied algorithmic complexity vulnerabilities at the network, protocol, and application layers [36]–[38], focusing on attacks such as request flooding and resource exhaustion. Related efforts on regular-expression DoS [5], [39] address pathological patterns that cause excessive matching overhead. In contrast, targets algorithmic inefficiencies in software components, exposing complexity vulnerabilities that can trigger DoS even without high network traffic.

8 Conclusion↩︎

Algorithmic complexity vulnerabilities remain difficult to detect because their triggering conditions often depend on subtle interactions between program structure, input dependencies, and opaque callee behavior. In this work, we identify shadow complexity as a critical blind spot in ACV detection, where hidden computational costs behind API calls can silently amplify worst-case execution behavior.

We present , an LLM-assisted framework for discovering algorithmic complexity vulnerabilities through lightweight screening, context recovery, and measurement-driven validation. Applying to CPython, JDK, Zig, Rustc, and vLLM uncovered +28+3+11+8 previously unknown ACVs, of which +5+3+11+4 have been confirmed.

References↩︎

---

1. These numbers are obtained by counting function and method definitions using tree-sitter [18].↩︎