VCAO: Verifier-Centered Agentic Orchestration for Strategic OS Vulnerability Discovery

The paper introduces VCAO, a verifier-centered agentic orchestration framework that models OS vulnerability discovery as a repeated Bayesian Stackelberg search game to dynamically allocate analysis budgets across heterogeneous tools, achieving significantly higher vulnerability discovery rates and lower false positives than existing baselines.

The Gist

Imagine you are the head of security for a massive, ancient castle (the Operating System). This castle has thousands of rooms, secret passages, and hidden traps. You know there are thieves (hackers) trying to break in, but you don't know exactly where they are or which door they will try first.

You have a limited amount of money and time (Budget) to hire security guards, install cameras, and run tests. The problem is: you can't check every single room every day. If you check the wrong room, you waste money. If you miss the right room, the castle gets robbed.

This paper introduces a new system called VCAO (Verifier-Centered Agentic Orchestration) to solve this problem. Here is how it works, explained simply:

1. The Old Way: Guessing and Checking

Previously, security teams used two main strategies:

• The "Fuzzing" Team: They threw random rocks at every wall to see if one broke. (This is like a Fuzzer). It's good at finding weak spots, but it wastes a lot of time on strong walls.
• The "Static Analysis" Team: They read the blueprints of the castle to find logical errors. (This is like CodeQL). It's smart, but it often raises false alarms about things that aren't actually broken.

Both teams worked separately, or they just split the budget evenly. This was inefficient.

2. The New Way: The "Master Strategist" (VCAO)

VCAO introduces a Master Strategist (an advanced AI) who acts like a grand chess player. Instead of just checking things, this AI plays a game against a "virtual thief."

Here is the 6-step process VCAO uses:

Step 1: Drawing the Map (Surface Mapper)

The AI first creates a detailed map of the castle. It identifies every door, window, and secret tunnel (syscalls, parsers, etc.). It knows exactly where a thief could enter.

Step 2: Building the "Thief's Path" (Attack Graph)

The AI builds a "Thief's Map." It doesn't just look at one room; it connects the dots.

• Analogy: If a thief picks the lock on the front door, can they then climb the stairs to the master bedroom? The AI draws lines connecting these steps to see the full path a thief would take to steal the crown jewels.

Step 3: The Great Game (The Brain)

This is the magic part. The AI plays a game called a Stackelberg Game.

• The Setup: The AI (the Defender) says, "I will spend my money checking these specific rooms."
• The Reaction: The AI then simulates a "Smart Thief" who sees where the AI is looking and tries to sneak in through the unwatched door.
• The Strategy: The AI realizes, "If I check the front door, the thief will go to the back window. If I check the back window, they'll go to the chimney."
• The Solution: The AI calculates the perfect mix of checks to minimize the thief's chance of success, even if the thief is smart. It uses math to decide: "Spend 10 minutes on the kitchen, 20 minutes on the library, and 5 minutes on the attic."

Step 4: The Specialized Teams (Parallel Executors)

Once the AI decides where to look, it sends out different teams of specialized agents to do the work simultaneously:

• The "Diff Miner": Looks at old repair logs to see if a fix was done halfway.
• The "Code Reader": Reads the blueprints for logic errors.
• The "Rock Thrower": Tries to crash the system with random inputs.
• The "Memory Watcher": Checks for leaks in the walls.
• The "Race Detector": Checks if two workers are trying to use the same tool at the same time.

Step 5: The "Double-Check" (Cascaded Verifier)

When a team finds something suspicious, it doesn't immediately scream "INTRUDER!"
Instead, the finding goes through a Three-Layer Filter:

1. Can we make it happen again? (Reproducibility)
2. How bad would it be? (Severity)
3. Have we seen this before? (Deduplication)
   This stops the security team from panicking over false alarms.

Step 6: The Safety Guard (Safety Governor)

Because this AI is powerful enough to find real vulnerabilities, it has a strict "Safety Guard" built-in. It runs in a locked sandbox (a digital prison) so it can't accidentally break the real castle. It also requires a human to sign off before any secrets are revealed to the public.

Why is this better?

The paper tested VCAO on real Linux computer systems (the "castle").

• Result: It found 2.7 times more real vulnerabilities than just throwing rocks at walls (fuzzing).
• Result: It found 1.9 times more than just reading blueprints (static analysis).
• Result: It reduced false alarms by 68%. This means human security guards spend less time chasing ghosts and more time catching real thieves.

The Big Picture

Think of VCAO not as a tool that just "looks for bugs," but as a smart resource manager. It understands that security is a game of strategy. By predicting how a smart attacker would move, it allocates its limited time and money to the exact spots where they will do the most good, leaving the attacker with nowhere to hide.

Technical Summary

1. Problem Statement

The discovery of operating system (OS) vulnerabilities, particularly in the Linux kernel, faces a critical bottleneck. While powerful individual tools exist (e.g., CodeQL for static analysis, Syzkaller for fuzzing, KASAN for memory safety), current workflows rely on ad-hoc heuristics to coordinate them. This leads to inefficient resource allocation, high false-positive rates, and missed vulnerabilities.

The authors argue that the primary challenge is no longer tool capability but decision-theoretic coordination: determining where to look, how to look, and when to verify to minimize a strategic attacker's advantage. Existing systems fail to answer the question: "Which analysis action most reduces the strategic attacker's expected payoff?"

2. Methodology: The VCAO Framework

The paper proposes VCAO (Verifier-Centered Agentic Orchestration), a system that formulates vulnerability discovery as a repeated Bayesian Stackelberg search game.

A. Game-Theoretic Formulation

• The Game: A Bayesian Stackelberg Vulnerability Discovery (BSVD) game where the Defender (an LLM Orchestrator) commits to a mixed strategy of allocating analysis budget across kernel components, and a Strategic Attacker (modeled by type) best-responds by choosing exploit paths to maximize damage.
• Intra-Kernel Attack Graph (L2): The system constructs a directed acyclic graph $G=(V, E, C, \phi, \psi)$ representing the kernel.
  • Nodes ($V$): Entry points (syscalls, ioctls), internal functions, privilege boundaries, and attacker goals (e.g., root access).
  • Edges ($E$): Control-flow, data-flow, and privilege transitions.
  • Probabilities: Vertices have prior vulnerability probabilities ($\phi$) derived from CVSS scores and defect density; edges have exploitability probabilities ($\psi$).
• Objective: The defender aims to find an optimal coverage vector $c^*$ that maximizes expected utility against the attacker's best response, minimizing the probability of a successful exploit path.

B. The Six-Layer Architecture

VCAO operationalizes this theory through a six-layer agentic system:

1. Surface Mapper (L1): An LLM agent extracts security-relevant entry points (syscalls, parsers) and maps reachable internal functions.
2. Attack Graph Builder (L2): Constructs the intra-kernel attack graph, defining privilege boundaries and attacker goals.
3. Game-Theoretic Ranker (L3): The core solver. It uses a DOBSS-derived Mixed-Integer Linear Programming (MILP) formulation to compute the optimal budget allocation ($c^*$) across files, functions, and analysis methods (CodeQL, Fuzzing, KASAN, etc.) under resource constraints.
4. Parallel Executor Agents (L4): Specialized agents execute the allocated tasks in parallel:
   • Patch-Diff Miner: Finds incomplete fix propagation.
   • CodeQL Agent: Runs data-flow queries.
   • Fuzzing Agent: Directs Syzkaller with custom descriptions.
   • KASAN/KCSAN Agents: Run memory and concurrency sanitizers.
5. Cascaded Verifier (L5): A three-stage verification pipeline (Reproducibility $\to$ Severity Assessment $\to$ Deduplication) to drastically reduce false positives before human review.
6. Safety Governor (L6): Enforces isolation, logging, and mandatory human review to prevent misuse and ensure responsible disclosure.

C. Learning and Adaptation

• Bayesian Belief Update: After each round of analysis, the orchestrator updates its beliefs about the latent vulnerability state of specific code regions based on tool outputs (alerts, crashes, clean results) using Bayesian inference.
• Online Regret: The system employs online learning extensions (inspired by EXP3 and Thompson sampling) to adapt to unknown attacker behaviors, guaranteeing a sublinear regret bound of $\tilde{O}(\sqrt{T})$.

3. Key Contributions

1. Formal Game-Theoretic Model: First formulation of OS vulnerability discovery as a repeated Bayesian Stackelberg game with intra-kernel attack graphs.
2. VCAO Architecture: A novel six-layer agentic system integrating Large Reasoning Models (LRMs) with heterogeneous security tools and game-theoretic optimization.
3. Optimization Algorithm: A DOBSS-adapted MILP for optimal budget allocation under uncertainty, coupled with a formal regret bound proof.
4. Comprehensive Evaluation: Rigorous testing on five Linux kernel subsystems, demonstrating significant improvements over state-of-the-art baselines.

4. Experimental Results

The system was evaluated on five Linux kernel subsystems (Filesystem, Networking, Namespaces/Capabilities, Drivers, io_uring/BPF) using two modes:

• Replay Mode: Replaying 847 historical CVEs (2019–2025) on past kernel snapshots.
• Live Mode: Discovery on upstream snapshots (6.12–6.14).

Key Performance Metrics:

• Vulnerability Yield: VCAO discovered 2.7× more validated vulnerabilities per unit budget than coverage-only fuzzing and 1.9× more than static-analysis-only baselines.
• Efficiency: It outperformed non-game-theoretic multi-agent pipelines by 1.4×.
• False Positives: The cascaded verification reduced the false-positive rate reaching human reviewers by 68% (dropping from ~31–47% in baselines to 15.1%).
• Time to Discovery: VCAO reduced the time to first validated vulnerability significantly (3.2 hours vs. 14.2 hours for uniform allocation).
• Ablation Study: Confirmed that the Bayesian belief update (-31% impact if removed), Stackelberg optimization (-21.2%), and attack graph structure (-24.8%) are the most critical components.

5. Significance and Impact

• Paradigm Shift: Moves vulnerability discovery from "tool-centric" (running tools until they finish) to "strategy-centric" (optimizing tool usage based on game theory and probabilistic reasoning).
• Resource Efficiency: Demonstrates that strategic allocation of limited compute budgets yields significantly higher returns than brute-force or heuristic approaches.
• Safety and Ethics: The framework is explicitly designed with a "Safety Governor" and follows dual-use research protocols (offline execution, human review, coordinated disclosure), addressing the risks associated with AI-driven vulnerability discovery.
• Open Science: The authors are releasing the simulation framework, synthetic attack-graph generator, and evaluation harness to foster reproducible research in this domain.

In conclusion, VCAO represents a major advancement in automated security, proving that combining Large Reasoning Models, Game Theory, and Formal Verification can systematically outperform existing manual and automated workflows in finding critical OS vulnerabilities.