ShadowProbe: Language-Extensible Detection of Hidden Algorithmic Complexity Vulnerabilities

2026-01-25 · Source: cs.SE updates on arXiv.org · Field: Technology & Digital — Software Development & Engineering, Artificial Intelligence & Machine Learning, Cybersecurity & Data Privacy · Depth: Expert, extended

Summary

ShadowProbe is a scalable, language-extensible framework designed to detect Algorithmic Complexity Vulnerabilities (ACVs), particularly those arising from "shadow complexity" – hidden computational costs within standard library APIs. It addresses limitations of traditional fuzzing and symbolic execution by combining lightweight static analysis, automated execution context reconstruction, and Large Language Model (LLM)-assisted test generation. The system screens for candidate functions, reconstructs minimal executable contexts, synthesizes size-controlled inputs, and uses statistical growth inference to validate worst-case execution behavior. Evaluated on the WISE benchmark, ShadowProbe consistently outperformed existing tools in analysis efficiency, being 4.7x faster than SPF-WCA and 8.1x faster than Badger. It also uncovered 162 previously unknown ACVs across CPython, JDK, Zig, Rustc, and vLLM, with 84 confirmed and 41 already fixed by maintainers.

Key takeaway

For software engineers and library maintainers developing or maintaining critical infrastructure, you should prioritize integrating complexity-oriented testing into your security and performance audits. This is crucial for identifying "shadow complexity" in seemingly benign library API calls, which can lead to severe algorithmic complexity vulnerabilities and Denial-of-Service conditions. Proactively revisit long-lived parsing and text-processing code, and consider adopting automated frameworks like ShadowProbe to scalably uncover these hidden risks through empirical measurement.

Key insights

ShadowProbe uses LLMs and empirical measurement to scalably detect hidden algorithmic complexity vulnerabilities across diverse languages.

Principles

• Shadow complexity in library APIs is a critical, often overlooked, source of ACVs.
• Scalable ACV detection requires lightweight static screening and automated context reconstruction.
• Robust validation distinguishes true algorithmic growth from runtime noise like GC/JIT.

Method

ShadowProbe performs static screening, reconstructs executable contexts, uses LLMs to synthesize size-controlled worst-case inputs, and validates ACVs via statistical growth inference from execution time measurements.

In practice

• Apply to language runtimes (CPython, JDK) and infrastructure (vLLM, Rustc).
• Focus audits on parsing/text-processing modules for hidden costs.
• Prioritize explicit buffers or builder-style accumulation over repeated string concatenation.

Topics

• Algorithmic Complexity Vulnerabilities
• Shadow Complexity
• LLM-Assisted Program Analysis
• Static Code Analysis
• Software Performance
• Denial-of-Service Attacks

Code references

• django/django
• Zac-HD/hypofuzz
• pallets-eco/flask-mail
• vllm-project/vllm

Best for: CTO, VP of Engineering/Data, Director of AI/ML, AI Scientist, AI Security Engineer, Software Engineer

Related on AIssential

• Code-Augur: Agentic Vulnerability Detection via Specification Inference — Agentic vulnerability detection improves by making LLM assumptions explicit and continuously validating them with fuzzing.
• Beyond Indistinguishability: Measuring Extraction Risk in LLM APIs — Indistinguishability metrics are insufficient for measuring data extraction risk in LLM APIs.
• [R] shadow APIs breaking research reproducibility (arxiv 2603.01919) — Shadow APIs providing access to large language models introduce significant reproducibility and reliability risks.
• Empirical Software Engineering TerraProbe: A Layered-Oracle Framework for Detecting Deceptive Fixes in LLM-Assisted Terraform — LLM-assisted Terraform security repairs frequently produce deceptive fixes that bypass automated checks, leaving vulnerabilities active.
• WildCode Revisited: A Comprehensive Empirical Study on the Security of LLM-Generated Code — LLM-generated code, particularly from ChatGPT, consistently contains significant security vulnerabilities, largely unaddressed by users.
• You Patched LiteLLM, But Do You Know Your AI Blast Radius? — The LiteLLM compromise reveals AI system risk extends beyond dependencies to runtime access and hidden connections.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.SE updates on arXiv.org.