Search papers, labs, and topics across Lattice.
This paper introduces ShadowProbe, a novel framework designed to detect Algorithmic Complexity Vulnerabilities (ACVs) that arise from hidden computational costs in standard library APIs. By employing lightweight static analysis and leveraging Large Language Models for test generation, ShadowProbe automates the identification of these vulnerabilities without the extensive manual effort typical of existing methods. The framework's evaluation on the WISE benchmark demonstrates significant improvements in analysis efficiency, revealing previously unknown ACVs in large-scale systems like CPython and the JDK, many of which have been confirmed by maintainers.
ShadowProbe uncovers hidden algorithmic risks in codebases, revealing vulnerabilities that traditional methods miss, with significant implications for software reliability.
Algorithmic Complexity Vulnerabilities (ACVs) arise when adversarial inputs trigger worst-case execution behavior, causing severe performance degradation or Denial-of-Service conditions. A key but underexplored source is shadow complexity: non-trivial computational costs hidden inside seemingly benign standard library APIs. Because these costs are invisible at call sites, attackers can exploit them to induce unexpected superlinear runtime behavior. Existing ACV detectors often rely on fuzzing, symbolic execution, or hybrid analysis, but they are usually language-specific, require substantial manual effort to construct harnesses, and depend on heavy runtime instrumentation. We present ShadowProbe, a scalable and language-extensible framework for discovering ACVs through lightweight static analysis, automated reconstruction of execution contexts, and Large Language Model (LLM) assisted test generation. ShadowProbe uses a structured multi-stage pipeline: it statically screens for candidate functions guided by shadow-complexity signals, reconstructs minimal executable contexts from project-level symbols, and synthesizes size-controlled inputs to probe worst-case behavior. It then validates candidates using execution-time measurements and robust statistical growth inference, separating true algorithmic blowups from runtime noise such as garbage collection and JIT compilation effects. We evaluate ShadowProbe on the WISE benchmark, where it consistently improves analysis efficiency over existing approaches. We further apply it to large-scale systems including CPython, the JDK, Zig, Rustc, and vLLM, uncovering many previously unknown ACVs, many of which have been confirmed and partially remediated by maintainers. These results show that ShadowProbe can identify hidden algorithmic risks across diverse real-world codebases.
Tsinghua AI