ShadowProbe: Language-Extensible Detection of Hidden Algorithmic Complexity Vulnerabilities

• URL: http://arxiv.org/abs/2607.05474v1
• Date: Mon, 06 Jul 2026 09:15:25 GMT
• Title: ShadowProbe: Language-Extensible Detection of Hidden Algorithmic Complexity Vulnerabilities
• Abstract summary: Algorithmic Complexity Vulnerabilities (ACVs) arise when adversarial inputs trigger worst-case execution behavior.<n>We present ShadowProbe, a framework for discovering ACVs through lightweight static analysis.<n>We apply it to large-scale systems including CPython, Zig Rustc, and vLLM.
• Score: 28.083603872030892
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• FeedbackLLM: Metadata driven Multi-Agentic Language Agnostic Test Case Generator with Evolving prompt and Coverage Feedback [0.0]
  Traditional approaches to test case generation often involve manual effort and incur significant computational overhead.<n>We propose FeedbackLLM, a novel automated language-agnostic test case generation framework based on tightly coupled two-stage approach.<n>The performance of the proposed architecture is evaluated on the standard benchmark programs related to C and Python programs.
  arXiv  Detail & Related papers  (2026-05-02T05:43:29Z)
• DALC-CT: Dynamic Analysis of Low-Level Code Traces for Constant-Time Verification [0.08749675983608168]
  We propose a novel approach for verifying constant-time programs based on dynamic analysis of low-level execution traces.<n>We developed an open-source tool called DALC-CT, for the constant-time verification of programs using this approach.
  arXiv  Detail & Related papers  (2026-04-18T04:47:54Z)
• Dynamic analysis enhances issue resolution [53.50448142467294]
  DAIRA (Dynamic Analysis-enhanced Issue Resolution Agent) is an automated repair framework that embeds dynamic analysis into the agent's reasoning cycle.<n> Driven by a Test Tracing-Driven methodology, DAIRA utilizes lightweight monitors to extract critical runtime data.<n>When powered by Gemini 3 Flash Preview, DAIRA establishes a new state-of-the-art (SOTA) performance, achieving a 79.4% resolution rate on the SWE-bench Verified dataset.
  arXiv  Detail & Related papers  (2026-03-23T14:48:54Z)
• ForgeryVCR: Visual-Centric Reasoning via Efficient Forensic Tools in MLLMs for Image Forgery Detection and Localization [62.03035862528452]
  ForgeryVCR is a framework that materializes imperceptible traces into explicit visual intermediates via Visual-Centric Reasoning.<n>ForgeryVCR achieves state-of-the-art (SOTA) performance in both detection and localization tasks.
  arXiv  Detail & Related papers  (2026-02-15T11:14:47Z)
• Prism: Efficient Test-Time Scaling via Hierarchical Search and Self-Verification for Discrete Diffusion Language Models [96.0074341403456]
  Inference-time compute has re-emerged as a practical way to improve LLM reasoning.<n>Most test-time scaling (TTS) algorithms rely on autoregressive decoding.<n>We propose Prism, an efficient TTS framework for dLLMs.
  arXiv  Detail & Related papers  (2026-02-02T09:14:51Z)
• Multi-Agent Taint Specification Extraction for Vulnerability Detection [49.27772068704498]
  Static Application Security Testing (SAST) tools using taint analysis are widely viewed as providing higher-quality vulnerability detection results.<n>We present SemTaint, a multi-agent system that strategically combines the semantic understanding of Large Language Models (LLMs) with traditional static program analysis.<n>We integrate SemTaint with CodeQL, a state-of-the-art SAST tool, and demonstrate its effectiveness by detecting 106 of 162 vulnerabilities previously undetectable by CodeQL.
  arXiv  Detail & Related papers  (2026-01-15T21:31:51Z)
• Can LLMs Recover Program Semantics? A Systematic Evaluation with Symbolic Execution [1.5377279217726239]
  Obfuscation poses a persistent challenge for software engineering tasks such as program comprehension, maintenance, testing, and vulnerability detection.<n>We investigate whether fine-tuned language models can effectively deobfuscate programs and restore analyzability.
  arXiv  Detail & Related papers  (2025-11-24T13:55:20Z)
• Hybrid Fuzzing with LLM-Guided Input Mutation and Semantic Feedback [0.0]
  I present a hybrid fuzzing framework that integrates static and dynamic analysis with Large Language Model (LLM)-guided input mutation and semantic feedback.<n>Our method achieves faster time-to-first-bug, higher semantic diversity, and a competitive number of unique bugs compared to state-of-the-art fuzzers.
  arXiv  Detail & Related papers  (2025-11-06T02:38:24Z)
• Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking [54.43083499412643]
  Test-time algorithms that combine the generative power of language models with process verifiers offer a promising lever for eliciting new reasoning capabilities.<n>We introduce a new process-guided test-time sampling algorithm, VGB, which uses theoretically grounded backtracking to achieve provably better robustness to verifier errors.
  arXiv  Detail & Related papers  (2025-10-03T16:21:14Z)
• FoC: Figure out the Cryptographic Functions in Stripped Binaries with LLMs [51.898805184427545]
  We propose a novel framework called FoC to Figure out the Cryptographic functions in stripped binaries.<n>We first build a binary large language model (FoC-BinLLM) to summarize the semantics of cryptographic functions in natural language.<n>We then build a binary code similarity model (FoC-Sim) upon the FoC-BinLLM to create change-sensitive representations and use it to retrieve similar implementations of unknown cryptographic functions in a database.
  arXiv  Detail & Related papers  (2024-03-27T09:45:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.