Disabling PCGUARD edge pruning for AFL++ for evaluation

[nbars]

Hey, I have another question regarding your paper's evaluation. You seem to have disabled edge pruning for AFL++, and I wonder why you did this. I reckon that this may impact the evaluation outcome since this adds overhead to AFL++ (more edges -> more guards -> more runtime overhead) and may also negatively impact AFL++ ways of scheduling test cases since the scheduling is heavenly-based on edges.

[addisoncrump]

Are there any updates on this issue?

[Dongdongshe]

Hi,

We disable edge prune for a fair apple-to-apple comparison because our technique requires edge prune feature to generate connected CFG such that we can detect frontier nodes. I am afraid your negative impact hypothesis on AFL++ performance is wrong. Critical thinking is important for scientific research but adversarial assumptions without a careful and rigorous investigation would lead you nowhere. An example is your prior issue, you simply confused the output of objdump.

Please let me know if you need further clarification. I am happy to help.

Best,
Dongdong

[nbars]

Hey, right now I am just asking questions :)

I am afraid your negative impact hypothesis on AFL++ performance is wrong.

Since you offered to provide further clarification, I would be pleased if you could give me some insight why this is no issue at all?
Do you have some data or explanation on that matter?

[nbars]

Hello @Dongdongshe, per your recommendation, I carefully investigated whether the change you applied to the competitor AFL++ harms its performance. Hence, I compiled AFL++ v4.09c without applying your patch shown below (in other words, I used AFL++ v4.09c without any changes):

diff --git a/instrumentation/SanitizerCoveragePCGUARD.so.cc b/instrumentation/SanitizerCoveragePCGUARD.so.cc
index 588eb950..e54b1372 100644
--- a/instrumentation/SanitizerCoveragePCGUARD.so.cc
+++ b/instrumentation/SanitizerCoveragePCGUARD.so.cc
@@ -113,7 +113,7 @@ namespace {
 SanitizerCoverageOptions OverrideFromCL(SanitizerCoverageOptions Options) {
 
   Options.CoverageType = SanitizerCoverageOptions::SCK_Edge;
-  // Options.NoPrune = true;
+  Options.NoPrune = true;
   Options.TracePCGuard = true;  // TracePCGuard is default.
   return Options;

To evaluate the impact, I used your evaluation tooling within the provided Docker environment. I then compared the modified AFL++ (your version) against AFL++ vanilla (without modifications) by running both on ffmpeg — the best-performing target according to your paper. The data below show the fuzzer_stats of two runs of the fuzzer, notably, the only difference is that pruning is disabled for your version of AFL++.

# The AFL++ version you have used during evaluation to compare against.
run_time          : 86399
execs_done        : 4891776
execs_per_sec     : 56.62
execs_ps_last_min : 63.43
corpus_count      : 12971
bitmap_cvg        : 4.80%
edges_found       : 35622
total_edges       : 741651
afl_banner        : /workspace/fuzzopt-eval/fuzzdeployment/targets/ffmpeg/binaries/aflpp_build/ffmpeg
afl_version       : ++4.09c

# The same AFL++ version, but with edge pruning enabled (vanilla AFL++)
run_time          : 86398
execs_done        : 10336294
execs_per_sec     : 119.64
execs_ps_last_min : 127.09
corpus_count      : 16048
bitmap_cvg        : 4.91%
edges_found       : 22452
total_edges       : 456895
afl_banner        : /workspace/fuzzopt-eval/fuzzdeployment/targets/ffmpeg/binaries/aflpp_vanilla_build/ffmpeg
afl_version       : ++4.09c

Due to the disabled pruning, the edge count is inflated from 456.895 to 741.651 (+62%). This likely impacts the flavoring schema employed by AFL++ since it heavily relies on edges. This needs to be validated by additional experiments.
Directly evident from the data is the performance impact caused by the edges that have not been pruned: The vanilla AFL++ version has been able to perform more than 100% additional executions (4.891.776 vs. 10.336.294) than the version you have been using during your paper's evaluation. The ramifications for the results presented in the paper would require additional experiments, but I think we can agree that doubling the performance will have a significant effect, especially on a target such as ffmpeg that is not instantly saturated.

Since you stated that my negative impact hypothesis is wrong, I would be grateful for any insight on why you think this is the case. I am happy to share the build config I used for the experiment, however, I suspect that you would like to do the experiments on your own for validation.

[Dongdongshe]

Hi Nils,

I think you misunderstood my point. Your original issue indicated that we disabled the edge pruning feature because we intended to apply a dirty trick that can negatively impact other baselines like AFL++ while benefiting FOX. I was saying that hypothesis is wrong. First of all, all baseline fuzzers are given the same binary compiled with the edge-pruning feature disabled. It is a fair comparison because all fuzzers would have the same runtime overhead in terms of execution and search the same code coverage space of a binary. If some baseline fuzzer performs badly on a benchmark program with a larger number of edges, I think it could be the baseline fuzzer's algorithm limitation rather than the unfair experimental design with a dirty trick.

Then, let's get to the point of why we disabled the edge pruning feature. FOX was inspired by the K-Scheduler and exploited the graph information, i.e., the frontier node. In order for the fuzzer to identify the frontier node on the CFG, every node of CFG should have a node id, that's why FOX requires the edge pruning feature disabled as K-Scheduler. It simply cannot work on edge-prune binary where many nodes are not assigned with an edge id due to the edge pruning. As your experiment pointed out, a binary instrument with an edge-prune feature would have quite a different runtime overhead than a binary instrument without an edge-prune feature. AFL++ is compatible with and without the edge-prune feature, while FOX is only compatible with the edge-prune feature. So, we designed the experiment with the edge-prune feature disabled for all baseline fuzzers to try our best to design a fair and scientific experiment.

I hope this could address your questions. Let me know if you still need further help. We can have a quick Zoom meeting if you want. Btw, I am not the owner of this Github repo and somehow missed your initial post last year. If you haven't heard back from me for more than a week, please send me an email.

Best,
Dongdong

[nbars]

Hi Dongdong,

I appreciate the explanation regarding why FOX requires the edge pruning feature to be disabled, even though I am not sure why you require the normally pruned edges to have IDs. Since they are pruned, they should not provide you with any meaningful signal since they are implicitly represented by their dominating edge (which gets an ID).

Also, thanks for your invitation to a Zoom call. However, since several others are interested in this discussion, I believe it would be best to continue it in a public forum.

I think you misunderstood my point. Your original issue indicated that we disabled the edge pruning feature because we intended to apply a dirty trick that can negatively impact other baselines like AFL++ while benefiting FOX. I was saying that hypothesis is wrong. First of all, all baseline fuzzers are given the same binary compiled with the edge-pruning feature disabled. It is a fair comparison because all fuzzers would have the same runtime overhead in terms of execution and search the same code coverage space of a binary. If some baseline fuzzer performs badly on a benchmark program with a larger number of edges, I think it could be the baseline fuzzer's algorithm limitation rather than the unfair experimental design with a dirty trick.

While I understand your intent, this evaluation approach has significant issues.

• Disabling edge pruning forces AFL++ into an unnatural state, artificially increasing its execution cost while providing no actual benefit and only degrading its efficiency. In contrast, FOX requires edge pruning to be disabled, meaning this setup causes a not uniform advantage in favor of FOX, which clearly contradicts the goal of a fair comparison.

• Your argument that all fuzzers experience the same runtime overhead is misleading. FOX benefits from additional CFG information, while AFL++ is slowed down due to inflated edge counts. My experiment shows that disabling pruning causes AFL++ to execute half as many test cases per second, meaning it explores significantly fewer paths over time.

• Your argument that "If some baseline fuzzer performs badly on a benchmark program with a larger number of edges, I think it could be the baseline fuzzer's algorithm limitation." does not hold. This assumption is incorrect in the case of AFL++. The extra edges do not represent additional useful information; instead, they inflate the number of decisions AFL++ must make, slowing it down without any benefit. This evaluation does not measure FOX’s ability to improve fuzzing in a realistic setting—it only shows that FOX can outperform an artificially hindered AFL++.

A scientifically valid evaluation should test each fuzzer under the conditions it is designed for. A fairer approach would be:

• Running FOX on a binary without edge pruning (since it requires it).
• Running AFL++ on a binary with edge pruning enabled (since the non-pruned edges only harm its performance).
• Comparing their respective performance under these conditions based on coverage computed on a neutral binary instrumented with, e.g., LLVM sanitizer coverage.

Actually, I am quite certain that these steps align perfectly with the approach to fuzzer evaluation that you advocated for not long ago on Twitter.

To be clear, I do not assume this setup was intended to get an unfair advantage—this may very well be an honest mistake. Also, I want to highlight that this case again shows that publications should always come with an artifact and that I am glad you have provided one. Which again implied that this is no "dirty trick" you applied deliberately.

Best,
Nils

[Dongdongshe]

Hi Nils，

I am afraid your argument about our evaluation having significant issues is, again, incorrect as your prior issue. It's just caused by your personal bias that AFL++ must run with edge pruning; otherwise, it's not AFL++. I don't understand why you have such constant hate and bias on FOX. If it's personal, we are really sorry that FOX fails to earn your trust. But if you are interested in fuzzing research, I hope we can have a formal academic conversation to address your questions. It's not a street fight or someone has to prove other guys wrong. But I would suggest again, PLEASE take enough investigation before you make such a strong and certain claim. Reckless critics would lead you nowhere in academic research. Let me first explain why we think AFL++ can run on a binary without the edge prune feature.

AFL++ is a community fuzzer that is built upon several key features, including AFL havoc mode, aflfast, Mopt, Laf-intel, Redqueen and other academic designs. The initial version of AFL++ built upon c2.52 does not come up with an edge prune feature. If you check AFL++ WOOT2020 paper, it never mentioned the edge prune feature as a core component. The edge prune feature is just one of the optimizations introduced later among many fixes in AFL++, not a core or indispensable part. And AFL++ is compatible with that feature (AFLFast scheduling and havoc mode are all initially built on AFL where there is no edge prune feature. Hence, I claim all major components of the AFL++ evaluated in our paper are compatible with disabling the edge prune feature ). Therefore, I think your claim that "AFL++ without edge prune feature is unnatural" is wrong. The term "unnatural" is not accurate because it's based on personal bias rather than rigorous investigation. Meanwhile, AFL++ provides various instrumentation pass in the instrumentation directory for researchers to hack. We chose this feature because our tool is only compatible with that feature.

In my mind, the fundamental issue of your argument is that you mix the instrumentation and algorithm design of fuzzer. AFL havoc mode mutation, affect scheduling, Mopt mutation, Laf-intel, and requeen, are all fuzzing algorithmic components, and they all are initially built on hash-based coverage instrumentation and are compatible with disabling the edge prune feature. If a researcher would like to investigate the performance of any algorithmic changes, the evaluation should minimize or ensure no variance or noise from the instrumentation side, i.e., ensure the instrumentation of binary across all fuzzers is the same. That's what we do in our paper evaluation: ensure all instrumentation is the same and report throughput and code coverage together.

Your proposed suggestion of so-called scientific evaluation is, therefore, incorrect. It's a typical apple-to-banana comparison unless your evaluation goal is "We just want to show the technique/algorithm of FOX is useless and bad, or maybe a scam. Hence, we compare FOX with throughput 50 (without edge prune feature) and AFL++ with throughput 100 (with edge prune feature). But we will never acknowledge that the result could be highly influenced by different throughput. We don't care. We just hate FOX." Only if that's your goal, I think you get the correct evaluation setup.

Next, let me explain in detail why the disabling feature is needed for the frontier node. Our implementation leverages the parent and child node relationship to track the frontier node. However, the edge prune feature would delete many nodes on the CFG (by not assigning an edge ID to a basic block) and change the graph structure and corresponding parent-child node relationship. In this case, it's very hard to track the frontier node based on the control flow information of the source code because the edge-pruned CFG has an inconsistent graph topology with the source code. I would suggest you read our K-Scheduler paper for more details.

In the end, I would truly thank you for your valuable feedback on the necessity of disabling the edge prune feature. After careful thinking, my hunch is that maybe it's possible to track the frontier node on the pruned CFG, but it would require some graph-level analysis. We are actually working on the integration of FOX into AFL++ official code base. The feedback and suggestions from pro users like you and your friends are really helpful to us. We really want you guys to try our technique and algorithm in the AFL++ official codebase in the way you like (i.e., with the edge prune feature). That's also the motivation why I would like to spend a lot of time writing long letters with you on this thread. I plan to investigate the feasibility of implementing a frontier node on the pruned CFG. But we are busy with several deadlines this month, so It would be slow. But I will keep you guys posted on this thread. If you guys are willing to help on this, that would be awesome.

Since they are pruned, they should not provide you with any meaningful signal since they are implicitly represented by their dominating edge (which gets an ID).

[nbars]

Your proposed suggestion of so-called scientific evaluation is, therefore, incorrect. It's a typical apple-to-banana comparison <...>

To clarify, my "so-called scientific evaluation" follows the same methodology used by FuzzBench and many fuzzing research papers. The standard practice is to give each fuzzer a binary compiled with its tooling and then use a separate, clean binary to replay the found inputs for coverage measurement. This ensures consistency and eliminates unintended biases.

Failing to do so can lead to inaccurate results. A relevant example is FishFuzz-eval, which illustrates why you should never use the same binary for both fuzzing and coverage computation, as you are suggesting. While this specific case does not directly apply to your case, it highlights the fundamental issue with your method.

---

A Thought Experiment: Imagine I publish a paper based on AFL++, rename it to AFL+++, and make zero code changes. Can I reproduce the reported improvements when compared to your fuzzer? No, I wouldn't. I would have crafted a fuzzer based on AFL++ that, with no changes, improved considerably.

That means the "improvement over state-of-the-art" in your paper isn't the actual improvement—it's just an improvement over your custom-defined baseline, which isn't reproducible by others. The same would be true if your fuzzer were integrated into FuzzBench or if it were compared to some AFL++ derivatives.

I'm not dismissing the fact that your approach provides some real improvement. However, the coverage results in your paper are misleading. FOX is not some special case that all other fuzzers must adapt to for fair comparisons. If you believe your fuzzer's performance is being unfairly impacted by non-pruned edges, the solution is not to impose artificial constraints on competing fuzzers. Whatever you were trying to measure is not a general improvement over the state-of-the-art. Instead, it is an improvement over your chosen version of the state-of-the-art. Before answering, please think about the thought experiment above and chat with your colleagues.
From my evaluation, the actual coverage increase is roughly halved compared to what your paper claims—though I make no guarantees on the exact reduction. Still, you have a solid coverage improvement that many papers would be proud of.

Best,
Nils

[vanhauser-thc]

@Dongdongshe it does not help if you try to make this a personal issue. The criticism of Nils is shared by me and several other people.-

Disable pruning for AFL++ only provides a benefit for Fox and is just disadvantage for AFL++ and hence this is neither scientific nor fair.

If Fox would outperform AFL++ with pruning enabled - that would show that Fox is superior (and that would be fine with me).

On the other hand I think it is beneficial if new techniques for coverage, path constraint solving etc. are evaluated. Even if they do not outperform existing ones, they can help fuzzing campaigns in corner cases or help further advances in research. Something new does not need to outperform existing techniques to be beneficial.