# Cheap to Hypothesize, Costly to Verify: The Defense Surface of Agentic Vulnerability Discovery

arXiv: https://arxiv.org/abs/2609.35909 · HTML: https://mlsanity.com/paper/2609.35909/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Agent threats, guardrails and governance, one of 16 directions in LLM agents and tool use.
- Builds on 22 of its 62 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Placed in

- LLM agents and tool use / [Agent threats, guardrails and governance](https://mlsanity.com/agents/agent-threats-guardrails-and-governance/)

## Builds on (most cited first, 22 of 22)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering](https://mlsanity.com/paper/2405.15793/) (2024)
- [DeepSeek-V4: Towards Highly Efficient Million-Token Context Intelligence](https://mlsanity.com/paper/2606.19348/) (2026)
- [GLM-5: from Vibe Coding to Agentic Engineering](https://mlsanity.com/paper/2602.15763/) (2026)
- [Cybench: A Framework for Evaluating Cybersecurity Capabilities and Risks of Language Models](https://mlsanity.com/paper/2408.08926/) (2024)
- [Kimi K3: Open Frontier Intelligence](https://mlsanity.com/paper/2607.24653/) (2026)
- [CVE-Bench: A Benchmark for AI Agents' Ability to Exploit Real-World Web Application Vulnerabilities](https://mlsanity.com/paper/2503.17332/) (2025)
- [CyberGym: Evaluating AI Agents' Real-World Cybersecurity Capabilities at Scale](https://mlsanity.com/paper/2506.02548/) (2025)
- [The Art, Science, and Engineering of Fuzzing: A Survey](https://mlsanity.com/paper/1812.00140/) (2018)
- [EnIGMA: Interactive Tools Substantially Assist LM Agents in Finding Security Vulnerabilities](https://mlsanity.com/paper/2409.16165/) (2024)
- [Hacking Back the AI-Hacker: Prompt Injection as a Defense Against LLM-driven Cyberattacks](https://mlsanity.com/paper/2410.20911/) (2024)
- [Clawdrain: Exploiting Tool-Calling Chains for Stealthy Token Exhaustion in OpenClaw Agents](https://mlsanity.com/paper/2603.00902/) (2026)
- [Indistinguishability Obfuscation from Well-Founded Assumptions](https://mlsanity.com/paper/2008.09317/) (2020)
- [LLM Agent Honeypot: Monitoring AI Hacking Agents in the Wild](https://mlsanity.com/paper/2410.13919/) (2024)
- [A Systematic Study of Code Obfuscation Against LLM-based Vulnerability Detection](https://mlsanity.com/paper/2512.16538/) (2025)
- [Trust Me, I Know This Function: Hijacking LLM Static Analysis using Bias](https://mlsanity.com/paper/2508.17361/) (2025)
- [CoTDeceptor:Adversarial Code Obfuscation Against CoT-Enhanced LLM Code Agents](https://mlsanity.com/paper/2512.21250/) (2025)
- [OTora: A Unified Red Teaming Framework for Reasoning-Level Denial-of-Service in LLM Agents](https://mlsanity.com/paper/2605.08876/) (2026)
- [On Secure and Usable Program Obfuscation: A Survey](https://mlsanity.com/paper/1710.01139/) (2017)
- [Chaff Bugs: Deterring Attackers by Making Software Buggier](https://mlsanity.com/paper/1808.00659/) (2018)
- [Honeyquest: Rapidly Measuring the Enticingness of Cyber Deception Techniques with Code-based Questionnaires](https://mlsanity.com/paper/2408.10796/) (2024)

## Abstract (arXiv)

Autonomous LLM agents turn vulnerability discovery into a repository-scale search: they generate many vulnerability hypotheses but can verify only a subset under a finite budget. We show that autonomous vulnerability discovery exhibits a hypothesis-verification asymmetry, where verifying a candidate hypothesis through reachability analysis, execution, and proof-of-concept construction is substantially more expensive than forming it. Under a finite resource budget, this makes autonomous discovery a resource-bounded selective-verification process, further exposing verification effort as a unique defense surface. We present RedHerring, which inserts certifiably safe decoys that divert verification effort from real vulnerabilities. Each decoy combines a CVE-derived vulnerability chain that attracts verification with a false bridge that keeps its dangerous sink unreachable. A private certificate lets the defender verify this property efficiently, while establishing the same fact from the released repository requires solving a computationally hard problem. RedHerring further adapts each decoy to the target repository so that it reads as ordinary program logic. Across 33 OSS-Fuzz projects, 70 evaluation instances, and five models under matched budgets, RedHerring reduces real vulnerabilities discovered by 38.7-60.4%. Trajectory analysis shows that agents spend 30.6-51.5% of completion tokens and an estimated 32.5-49.9% of runtime verifying decoys, showing that RedHerring redirects a substantial fraction of the fixed search budget toward decoys. When explicitly informed that decoys may be present, the agent adapts its search strategy, yet RedHerring still reduces vulnerabilities discovered by 37.2% relative to an informed Baseline, showing that its effectiveness does not depend on decoy secrecy.