RL-Guided Fuzzing for Binary Vulnerability Detection — an Open Reimplementation and 13-Agent Study of VSGFuzz

Project Background

A 2025 Array paper proposes VSGFuzz: predict how vulnerable each function of a stripped binary is with a graph-embedding network, turn that prediction into a per-basic-block value, score every test case by the blocks it executes, and use that score as the reward for a reinforcement learning agent that decides which mutation operator to apply next. The paper selects DDPG, with DQN reported only as a comparison.

It is an appealing idea and it ships with a problem: no artifact. No source, no seeds, no binaries, no scoring scripts — and the pipeline it describes is built on IDA Pro, Intel Pin and VUzzer (Python 2). None of it can be re-run.

So I re-derived the whole method from the text with open tooling, and then asked the question the paper leaves open: is DDPG actually the right algorithm for scheduling fuzzer mutations? Thirteen agents — from a stateless bandit up to SAC — are compared on the same MDP, the same reward and the same seeds. The answer turned out to be an uncomfortable one, and it is the reason this project is worth reading.

Code: github.com/Emad-Mahmodi/vsgfuzz-rl

What Was Reimplemented

Every numbered equation, algorithm and table of the paper is mapped to code, and every place the paper is ambiguous is documented with the reading implemented and the flag that switches to the alternative — 13 such ambiguities, from a disagreement between Eq. (4) and Algorithm 1 to the fact that the paper never says how a continuous-control algorithm addresses fourteen discrete operators.

The pipeline runs static analysis → vulnerability prediction → block values → an MDP whose reward is the seed score, and closes the loop through a score-ranked seed pool.

Headline Result — the paper’s algorithm ranks last, and nothing beats random

Six agents, 10 seeds each, 25,000 mutations per run, identical reward and identical seed pool.

Two findings, stated at the confidence the data actually supports:

• No agent significantly beats uniform-random operator choice. After Holm correction the best result against random is p = 0.28. The baseline the paper argues against — the “equal seed mutation strategy” — is not beaten by any of the thirteen learners, while running 120× faster per step than DDPG.
• DDPG ranks last, and that part is significant. Against dueling_dqn: A₁₂ = 0.85 (large effect), p_Holm = 0.030. It is also the only agent with a reliability problem — it found no crash at all in 3 of its 10 runs, while every other agent found one in all 10.

Why DDPG Collapses — a measurable mechanism, not a guess

The failure is not bad luck; it is visible in what the policy does. Operator-distribution entropy (1 = uniform over the fourteen operators, 0 = always the same one) puts DDPG at 0.10: 96% of its steps go to two operators, and which two differs by seed.

This is exactly the failure mode you would predict from pushing a continuous-control algorithm through a non-differentiable argmax onto fourteen discrete operators — and it is precisely the gap the paper never explains. Both plausible readings are implemented (ddpg with a straight-through Gumbel-softmax relaxation, ddpg_argmax as the literal reading), and both land at the bottom of the table.

The stateless bandits (ucb1, thompson, exp3) are the most informative baseline in the set for a different reason: they see no state at all. When a bandit ties with a deep agent, the deep policy is not using the state — which suggests most of the work is being done by the seed pool’s score-ranked selection rather than by the mutation policy.

Ablation — does vulnerability guidance actually help?

This is the paper’s central claim: that scoring seeds by predicted vulnerability beats scoring them by coverage alone. It is testable, and the paper does not test it. Three settings, 3 agents × 10 seeds = 30 runs each:

• uniform — VP = 0 everywhere, which reduces Eq. (5) to BV = W(b) and turns VSGFuzz into a plain coverage-guided fuzzer;
• model — the trained graph-embedding predictor, i.e. the method as published;
• oracle — ground-truth labels, the ceiling a perfect predictor could ever reach.

No measurable benefit — and there is a structural reason to expect that. Even a perfect predictor does not separate from ignoring vulnerability entirely (A₁₂ = 0.48, p = 0.80). In Eq. (5), k·p_v is a constant added to every block of a function, so it shifts every path through that function by the same amount: it can re-rank whole functions, but says nothing about which path inside a function is worth reaching — and reaching the buggy path, not the buggy function, is the hard part.

That diagnosis points directly at the fix: a distance-to-target formulation in the style of AFLGo uses the same prediction to steer within a function. It is the first item on the future-work list.

The Vulnerability Prediction Model

structure2vec graph embeddings over ACFGs (8 attributes per basic block), trained on 150 synthetic programs / 1,800 functions for 25 epochs.

The paper reports 99.8% accuracy on Juliet. That number is reachable here too — the synthetic generator’s signal_strength knob controls how separable the two classes are, and at 1.0 the task is nearly trivial. The default was deliberately set to keep the predictor imperfect, because a perfect predictor would make the ablation above meaningless. The oracle setting then measures the ceiling separately.

Real Binaries — and an honest caveat about coverage

The executor is pluggable, and the three backends trade fidelity against throughput by three orders of magnitude:

The real-binary path works end to end: angr extracts 28 functions / 1,029 basic blocks from /usr/bin/who in 4.5 s (the paper reports ~1.8 s with IDA Pro), and afl-showmap supplies real edge coverage that finds real ASan-detected bugs in two of three bundled vulnerable targets.

A caveat worth knowing before trusting the block mapping. AFL has two edge-ID schemes. In QEMU mode the bitmap index derives from the block address, which is what lets a statically extracted CFG edge be pre-hashed to the slot it will set at runtime — the only mode in which the Eq. (5) block values apply to real coverage. Compile-time instrumentation assigns random IDs, and the mapping resolves nothing: measured overlap on one function was 81 static edges against 8 observed IDs, 0 matches. In that case the raw edge IDs are used as coverage units, scoring degrades to plain coverage guidance, and a warning says so.

Experimental Discipline

The methodology is the point of the project as much as the pipeline is.

• Two-stage design. A wide screening sweep (13 agents × 3 seeds) carries no significance testing and is used only to choose which agents to confirm; a separate confirmatory run (6 agents × 10 seeds) carries every statistical claim. Testing all thirteen at once would make the comparison family large enough that correction swallows any real effect.
• Non-parametric statistics. Vargha–Delaney A₁₂ effect sizes with Holm-corrected p-values — the standard for fuzzing evaluation, where crash counts are neither normal nor independent across seeds.
• Multiple seeds, always. The paper reports single runs with no variance; fuzzing is highly stochastic. Everything here is mean ± std, plus the number of runs that found any crash and the executions-to-first-crash.
• Committed raw results. Every run’s full JSON timeline is in the repository, so the published numbers can be checked without re-running anything.
• A preprint that cannot drift. Every number in the accompanying paper/ is generated from the run JSON by a script rather than typed in.
• 74 tests, all runnable without a GPU or any binary tooling, and a one-command make quick that reproduces a small end-to-end result in about 20 seconds.

What This Does Not Show

The default target is a synthetic program with executable ACFG semantics — every branch is a real predicate over the input bytes (magic-byte comparisons, length checks, checksums, in the style of LAVA-M bug injection), and planted vulnerable blocks crash when reached. That is a benchmark, not a claim about real software. It tells you which algorithm learns a mutation schedule better under an identical reward; it does not tell you how many CVEs you will find. For that, the AFL++ backend is the honest path. The results are a ranking on one benchmark family, and only the gap between the DQN family and DDPG is wide enough to lean on.

Nor is this a refutation of the paper’s real-world numbers, which were measured on real binaries with tooling that could not be reproduced here. It is a demonstration that the algorithmic choice at the centre of the method does not survive a controlled comparison — which is a claim about method design, and a useful one either way.

Full paper mapping, all 13 documented ambiguities, architecture notes, extensions and the real-binary guide: github.com/Emad-Mahmodi/vsgfuzz-rl

Based On

A reinforcement learning based fuzzing technique for binary programs vulnerabilities detection G. Cao, Y. Ma, M. Geng — Array, 27 (2025) 100458 doi:10.1016/j.array.2025.100458 (CC BY)

This repository is an independent reimplementation re-derived from the text and is not affiliated with the paper’s authors. Code released under MIT. Only fuzz software you own or are authorised to test.