Directed fuzzing sounds like an obviously good idea. If we already know the code location we want to reach, why waste time exploring the rest of the program? We should point the fuzzer toward the target and get there faster.

Yet modern directed fuzzers often fail to deliver on this intuition. Recent evaluations have repeatedly found that a strong coverage-guided fuzzer such as AFL++ can match or outperform directed fuzzers. This is surprising: how can a fuzzer with no destination beat one that knows exactly where to go?

The short answer is that most directed greybox fuzzers guide effort, not execution. They can choose which saved input to mutate next, but they cannot control where the mutation will go.

I believe the answer becomes much clearer if we view directed fuzzing as path finding in a latent space. This view also explains why our recent system, PBFuzz, works so much better on difficult vulnerability targets.

Planning and Decoding

A program’s concrete state is enormous. It includes its memory, registers, files, input history, and everything else that can affect execution. A fuzzer cannot efficiently search this space directly. Instead, it works with a smaller representation of the program.

I use latent space broadly here to mean this smaller, abstract search space. It need not be a learned vector representation. A control-flow graph (CFG) is a latent space too: it keeps basic blocks and control transfers while hiding most concrete program state.

Once we adopt this view, a directed input generator has four parts:

  1. Encoding: map a concrete execution into an abstract program state.
  2. Planning: choose an abstract action that appears to lead toward the goal.
  3. Decoding: turn that abstract action into a concrete test input.
  4. Feedback: execute the input and update the plan based on what actually happened.

Directed fuzzing as planning and decoding

This separation is important. Knowing where to go is not the same as knowing how to get there. A perfect plan is useless if the input generator cannot carry it out.

We can summarize the idea with a simple score for an abstract action \(a\) and decoder \(D\):

\[\mathrm{score}(a,D) \approx \frac{ P(a\ \mathrm{is\ feasible\ and\ useful}) \times P(D\ \mathrm{realizes}\ a) }{ \mathrm{cost}(a,D) }.\]

Traditional directed fuzzers mostly focus on the first probability, approximate it using graph distance, and implicitly assume that the second probability is similar for all actions. That assumption is often wrong.

What Traditional Directed Fuzzers Actually Do

Consider a typical directed greybox fuzzer such as AFLGo. It first builds a static CFG and computes distances from basic blocks to the target. During fuzzing, it gives more energy to inputs whose executions appear closer to the target.

Under our model:

Component Traditional directed fuzzer
Latent state basic blocks or coverage
Plan prefer shorter CFG distance
Latent action explore a nearby branch or path
Decoder mutate a scheduled input
Feedback coverage and distance

The control problem is easiest to see in a maze. The pictures below show four searches on the same Fuzzle challenge. The entry is at the top left and the target is at the bottom right.

AFLGo, directed, after 5 hours AFL++, coverage-guided, after 5 hours
AFLGo exploration of the Fuzzle maze AFL++ exploration of the Fuzzle maze
Beacon, directed, after 5 hours MazeRunner
Beacon exploration of the Fuzzle maze MazeRunner exploration of the Fuzzle maze

Each cell represents a function. Red cells were not visited; darker green means more revisits. The striking result is that AFLGo’s search looks much like AFL++, despite knowing the target. Beacon goes further: it stops an execution early once it can no longer reach the target. But Beacon still relies on random mutation. It can reject a wrong turn, but it cannot choose the next good one, so it also fails to solve the maze within five hours.

Since we had already built a fast concolic execution engine called SymSan, a natural idea was to replace random mutation with path constraint solving, enabling more precise control of the action-decoding stage. In this controlled maze, where most branches can be directly controlled by input bytes (i.e., are symbolic), our prototype, MazeRunner, reaches the target in 0.04 minutes on average—about 2.4 seconds.

This small experiment is a clean demonstration of why directed greybox fuzzing often fails: direction without control is not enough. In real-world code, two larger problems that Fuzzle does not model also limit MazeRunner’s effectiveness.

Problem 1: Reachability Is Not a Good Ranking

On Fuzzle-generated mazes, there is only a single path to the exit. While this makes brute-force searching hard, once static analysis finds it, the problem is reduced to following the plan. In real-world code, the picture is very different: there can be many routes to a target in the static CFG. More importantly, the graph has little information for deciding which route is likely to work.

Two paths with similar graph distance can be completely different in practice:

  • one may contain an infeasible branch;
  • one may require a checksum or a valid nested file structure;
  • one may depend on an indirect call or a long sequence of program states;
  • one may reach the target but never satisfy the bug-triggering condition;
  • one may be easy to control through the input while another is nearly impossible.

Static distance measures structural closeness, not semantic feasibility or success probability. It is therefore a weak path-finding heuristic. Worse, incorrect guidance can repeatedly send the fuzzer back to an attractive-looking but unproductive region.

This helps explain why coverage-guided fuzzing can win. Coverage is a natural runtime signal (for pruning unreachable paths). When an explored execution does not reach the target, a coverage-guided fuzzer naturally shifts effort elsewhere. It has no static target knowledge, but it continuously prunes paths using real executions. A bad prior can be worse than no prior at all.

Problem 2: A Branch Is Hard to Control

Even if we have a perfect oracle that can output the right path, it is still difficult to generate an input that follows it. Traditional fuzzers decode their plan through random mutations. Scheduling the best seed only decides where to spend mutations; it does not control what those mutations will do.

Concolic execution improves this situation. Given a symbolic branch condition, it can solve the corresponding constraints and generate an input that flips the branch. This is much more precise than random mutation.

But concolic execution does not make every branch controllable in real-world programs. They use table lookups, indirect calls, parsed objects, checksums, library code, persistent state, and other operations that may not be captured by the execution engine. For formatted inputs, there are also indirect control dependencies.

Moreover, mutational fuzzers and concolic execution can only visit nearby execution paths. This means that if the initial seeds’ execution paths are far from the target path, many low-level mutations will be needed to reach it.

This was the bitter lesson from our MazeRunner prototype. Combining runtime learning with concolic decoding works extremely well on synthetic mazes where branch conditions are directly controlled by input bytes. On real programs, the low-level action—”flip this branch”—is often itself the wrong interface.

PBFuzz Changes the Search Space

Still, the model led us to a breakthrough: our agentic “fuzzer,” PBFuzz (code). PBFuzz takes a different approach. Instead of planning mainly over basic blocks, an LLM agent reasons over a semantic representation of the code in its own embedding space: file formats, data dependencies, parser states, object relationships, and vulnerability conditions.

We cannot directly inspect the LLM’s internal representation. What we can observe is its projection into explicit hypotheses and plans. Rather than producing a sequence such as “take the true edge at branch 1, then the false edge at branch 2,” it proposes actions such as:

Construct a deeply nested XML DTD whose elements use long namespace prefixes, so recursive string construction exhausts the destination buffer.

This one semantic action may represent a long sequence of low-level branches. It also carries information that a CFG distance does not contain: which input structure is needed, why the route is plausible, and which values are likely to trigger the bug.

LLMs therefore help in two ways:

  1. They compress many low-level path combinations into a small number of semantic route hypotheses.
  2. Their learned knowledge of code and data formats provides a prior for ranking which hypotheses are likely to succeed.

This is still imperfect reasoning, not an oracle. But it is a much stronger path-finding heuristic than counting CFG edges.

Semantic Actions Need a Semantic Decoder

An LLM can describe a promising strategy, but asking it to emit test inputs one at a time is slow and unreliable. This is where property-based testing (PBT) enters the picture.

Strictly speaking, PBT alone is not the decoder. The decoder consists of:

  1. an LLM-generated, parameterized input builder that preserves the required format and semantics; and
  2. PBT, which searches the resulting parameter space efficiently.

For the XML example, the decoder may expose parameters such as nesting depth, prefix length, element-name length, and content-model type. It then generates many valid XML files while varying those properties.

This is fundamentally different from trying to flip one branch at a time. The semantic action “construct a deeply nested prefixed DTD” is directly expressible in the input generator. The generator can preserve all the structural conditions required to reach the vulnerable code while PBT searches for values that trigger the overflow.

Under our model, PBFuzz improves every important layer:

Component PBFuzz
Latent state semantic constraints and hypotheses
Plan rank plausible semantic routes using code understanding
Latent action satisfy a property or drive a program state transition
Decoder parameterized input builder plus PBT
Feedback reach/trigger signals and runtime inspection

This explains why PBFuzz works. It is not simply “an LLM attached to a fuzzer,” nor is its success explained by PBT alone. It improves the path representation, the path-ranking heuristic, the action vocabulary, and the decoder at the same time.

What This Model Predicts Next

A useful model should do more than explain past results. It should predict how to build a better system.

The immediate prediction is that future directed input generators should choose the plan and decoder jointly. A semantically attractive plan may still be a poor choice if no available decoder can realize it reliably.

There are several concrete ways to do this:

Rank Plans by Controllability

Generate several semantic plans, build a tentative decoder for each, and run a small number of probes. Then rank plans using both semantic plausibility and observed decoding success, rather than plausibility alone.

Check the Plan-to-Input Translation

Every semantic condition should map to a generator parameter, a fixed generator invariant, or a runtime check. If the LLM understands a necessary condition but forgets to encode it, the system should reject the generator before spending time fuzzing.

Adjust the Action Level

If a branch action is difficult to control, lift it into a higher-level property. If a semantic action is too broad, break it into smaller properties. The right action space should be chosen dynamically, not fixed in advance.

Use Multiple Decoders

No decoder is best for everything:

  • PBT is well suited to structured formats and program state machines;
  • concolic execution is effective for local byte and arithmetic constraints;
  • mutation remains valuable for opaque operations and deliberately malformed inputs.

The best system should select among them based on the current action and learn from previous decoding attempts.

Final Thoughts

Directed fuzzing does not fail because guidance is useless. It fails because traditional systems often confuse graph proximity with success probability, and intention with control.

Thinking of directed fuzzing as path finding in latent space separates two questions that were previously mixed together:

  1. Did we choose a path that is likely to succeed?
  2. Can we turn that choice into an input that follows the path?

Traditional directed fuzzers struggle with both. MazeRunner showed the benefit—and limits—of improving low-level decoding. PBFuzz goes further by moving planning and actions into a semantic space where both path selection and input generation become more manageable.

That, I believe, explains both why PBFuzz works and where future research should focus.