FlagThis

Abstract

Algorithmic Complexity Vulnerabilities (ACVs) are a class of software flaws in which adversarial or carefully crafted inputs trigger worst case execution behavior, leading to severe performance degradation and Denial-of-Service (DoS) conditions. A key but underexplored source of such vulnerabilities is shadow complexity, where non-trivial computational costs are hidden inside seemingly benign standard library APIs. These costs are not visible at the call site and can be systematically exploited to induce unexpected superlinear runtime behavior. Existing ACV detection techniques primarily rely on fuzzing, symbolic execution, or hybrid analysis. However, they are often specific to individual programming languages, require substantial manual effort to construct execution harnesses, and depend on heavy runtime instrumentation. This limits their scalability across large and diverse codebases. In this work, 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. Rather than relying on zero shot LLM inference, ShadowProbe uses a structured multi stage pipeline. It first performs static screening guided by signals from shadow complexity to identify candidate functions. It then reconstructs minimal executable contexts from project level symbols, and finally synthesizes inputs with controlled size to probe worst case execution behavior. Execution time measurements are used for validation, and robust statistical growth inference is applied to separate true algorithmic blowups from runtime noise, including garbage collection and JIT compilation effects. We evaluate ShadowProbe on the WISE benchmark and show that it consistently outperforms existing approaches in analysis efficiency. We further apply ShadowProbe to large scale software systems, including CPython, the JDK, Zig, Rustc, and vLLM, where it uncovers many previously unknown ACVs, a large portion of which have been confirmed and partially remediated by maintainers. These results demonstrate the effectiveness of ShadowProbe in identifying hidden algorithmic risks across diverse real world codebases.