Source-linked AI summary
Ensemble Fuzzing with Dynamic Resource Scheduling and Multidimensional Seed Evaluation
Yukai Zhao, Shaohua Wang, Jue Wang, Xing Hu, Xin Xia
TL;DR
Ensemble fuzzing combines multiple fuzzers, but existing approaches have limitations in resource scheduling and performance evaluation. Legion dynamically allocates resources using a UCB-based algorithm and evaluates seeds across multiple dimensions. It outperforms prior ensemble techniques and reports 20 bugs in nine real-world projects.
Problem
Existing ensemble-fuzzing approaches face limitations in resource scheduling and coarse performance evaluation, while fuzzer performance can vary during a campaign.
Source: §1 · p. 1Method
Legion dynamically schedules resources using a UCB-based approach and evaluates seed benefits with multiple metrics.
Source: §1 · p. 2Results
Legionβ reported 20 bugs in nine real-world projects, including five previously unknown bugs and three CVEs, while Legion outperformed EnFuzz and Autofz with the same base fuzzers.
Source: §1 · p. 3, §7 · p. 23Takeaways & Limitations
Legion combines adaptive resource allocation with multidimensional seed evaluation to address resource waste in ensemble fuzzing.
Source: §1 · p. 2The evaluation did not use FuzzBench because EnFuzz, the primary baseline, is deeply coupled with QSYM.
Source: §5 · p. 21
Abstract
from arXiv · showhide
Fuzzing is widely used for detecting bugs and vulnerabilities, with various techniques proposed to enhance its effectiveness. To combine the advantages of multiple technologies, researchers proposed ensemble fuzzing, which integrates multiple base fuzzers. Despite promising results, state-of-the-art ensemble fuzzing techniques face limitations in resource scheduling and performance evaluation, leading to unnecessary resource waste. In this paper, we propose Legion, a novel ensemble fuzzing framework that dynamically schedules resources during the ensemble fuzzing campaign. We designed a novel resource scheduling algorithm based on the upper confidence bound algorithm to reduce the resource consumption of ineffective base fuzzers. Additionally, we introduce a multidimensional seed evaluation strategy, which considers multiple metrics to achieve more comprehensive fine-grained performance evaluation. We implemented Legion as a prototype tool and evaluated its effectiveness on Google's fuzzer-test-suite as well as real-world open-source projects. Results show that Legion outperforms existing state-of-the-art base fuzzers and ensemble fuzzing techniques, detecting 20 bugs in real-world open-source projects-five previously unknown and three classified as CVEs.
1 Introduction
Legion addresses resource waste and coarse evaluation in ensemble fuzzing with dynamic scheduling and multidimensional seed evaluation. Its evaluation reports better benchmark performance than prior approaches and 20 bugs found in real-world projects.
1 Introduction
- Fixed resource allocations can be inefficient because fuzzer performance changes during a campaign, while Autofz profiles every fuzzer in a preparation phase and uses coarse path counts.Autofz’s preparation-phase scheduling also ignores historical performance, making decisions susceptible to fuzzing randomness.Source: §1 · pp. 1–2
- Legion schedules resources dynamically with a UCB-based algorithm using historical rewards and current performance, and evaluates seeds across multiple metrics.Seed metrics include coverage gains, crashes, deep edges, and infrequently covered paths; seeds are also synchronized across fuzzers.Source: §1 · p. 2
- 20 bugs were reported across nine real-world projects, including five previously unknown bugs and three CVEs.Legionβ used six modern base fuzzers for this evaluation.Source: §1 · p. 3
2 Background and Motivation Example
The section situates Legion among ensemble fuzzers, introduces its bandit-based scheduling rationale, and uses a synthetic program to motivate adaptive resource allocation and multidimensional seed evaluation.
2.1 Ensemble Fuzzing
- Ensemble fuzzing runs multiple base fuzzers on a program and schedules resources among them; prior systems include EnFuzz, Cupid, CollabFuzz, and Autofz.Autofz schedules dynamically using results from a preparation phase in each round.Source: §2.1 · p. 3
2.2 Multi-Armed Bandit
- Legion frames resource scheduling as a special multi-armed bandit problem, where each base fuzzer is an arm and resource allocation is a pull.Its UCB approach combines performance and exploration, with exploration favoring under-utilized fuzzers for periodic reevaluation.Source: §2.2 · pp. 3–4
2.3 Motivation Example
- A single fuzzing technique may struggle with varied challenges such as structured inputs, long-running loops, and complex constraints, motivating complementary fuzzers.Generation-based fuzzers may produce valid code snippets, while hybrid fuzzers can solve complex constraints; exchanging seeds can combine these strengths.Source: §2.3 · p. 5
- Autofz’s preparation phase runs every fuzzer, including ones no longer useful after their specialty has helped pass an earlier program check.Legion instead schedules from existing execution results and can shift resources as the program’s constraints are satisfied.Source: §2.3 · p. 5
- Path-only seed evaluation may overlook progress toward hidden states, so Legion assesses coverage gains, crashes, deep edges, and infrequently covered paths.The synthetic example illustrates a seed passing a string check that may help reach a later bug-triggering condition, even without a new path.Source: §2.3 · pp. 5–6
3 Our Approach: Legion
Legion coordinates multiple base fuzzers by dynamically assigning test resources and evaluating their seeds using multiple performance signals. Its scheduler updates fuzzer evaluations across rounds, reallocates resources during runs, and synchronizes beneficial seeds.
3.1 Overview
- Legion takes a target program, resource units, optional initial seeds, and selected base fuzzers, then coordinates fuzzing through a resource scheduler and global seed pool.Each fuzzer maintains a local seed pool that periodically synchronizes with the global pool.Source: §3.1 · p. 6
- Each round, Legion schedules resource units from prior performance evaluations, fuzzes for a set time, updates evaluations from local seed pools, and uploads profitable seeds.The schedule can also be fine-tuned during a round; post-fuzzing analysis of the global pool produces a report.Source: §3.1 · p. 7
3.2 Dynamic Resource Scheduling
- Legion models each base fuzzer as an arm in a multi-armed bandit problem, using accumulated reward and prior resource allocation to guide assignments.A resource unit assigned for one round counts as one arm pull.Source: §3.2 · pp. 7–8
- Legion combines bounded exploitation and upper-confidence exploration scores with Softmax selection, giving lower-scoring fuzzers a non-zero chance of receiving resources.The initial priming round deploys all base fuzzers, and accumulated rewards reduce the influence of noisy single-round results.Source: §3.2 · pp. 8–9
- After at least half a round, Legion reclaims a resource unit when its fuzzer produces no beneficial seeds during a monitoring interval and reallocates it to the current highest-reward fuzzer.This monitors only selected fuzzers, unlike Autofz’s per-round preparation phase that profiles all base fuzzers.Source: §3.2 · p. 10
3.3 Multidimensional Seed Evaluation
- Seed evaluation tracks new edges, paths, crashes, deep edges, and infrequently covered edges, spanning breadth, vulnerability goals, and exploration depth.Deep edges are identified using call-graph depth, while infrequently covered edges fall below half the average edge coverage count.Source: §3.3 · p. 10
- Legion weights each metric by its standard deviation across selected fuzzers and aggregates unnormalized incremental values to emphasize discriminative signals.The metrics also support qualitative seed evaluation for synchronization into the global pool.Source: §3.3 · p. 11
4 Evaluation
The evaluation compares Legion with ensemble and base fuzzers on the fuzzer-test-suite, tests it on newer real-world projects, and ablates its main components. Across these settings, Legion improves fuzzing metrics and detects more bugs than the evaluated alternatives.
4.1 Subjects and Metrics
- The evaluation used 33 subjects: 24 fuzzer-test-suite projects and nine newer real-world projects; metrics included branches, paths, crashes, bugs, and coverage.The benchmark was selected because EnFuzz depends on QSYM, which FuzzBench does not support due to modern kernel compatibility issues.Source: §4.1 · pp. 11–12
4.2 Settings and Analysis Procedures
- For ensemble comparisons, Legionα, EnFuzz, and Autofzα ran independently for 12 hours with six cores, and all experiments were repeated ten times.RQ1 used the same six base fuzzers for all three tools; RQ3 compared Legion variants, baselines, and base fuzzers on real-world projects.Source: §4.2 · pp. 12–13
4.3 RQ1-Compared with Baselines
- Legionα covered 39,364 (10.63%) and 21,772 (5.62%) more branches, executed 16,706 (6.44%) and 9,959 (3.74%) more paths, and triggered 6 (11.54%) and 3 (5.45%) more unique crashes than EnFuzz and Autofzα, respectively.Legionα triggered 58 unique crashes in 20 of 24 projects, including all crashes triggered by Autofzα and EnFuzz.Source: §4.3 · p. 13, Table 1 · p. 14
4.4 RQ2-Compared with Base Fuzzers
- Legionα averaged 18.72%–25.72% more branches and 37.73%–57.55% more paths than each base fuzzer, with 87.10% more unique crashes than the best-performing base fuzzer.Base-fuzzer performance varied by project, while Legionα outperformed all base fuzzers on almost all projects.Source: Table 2 · p. 15, Table 3 · p. 16, §4.4 · pp. 16–17
4.5 RQ3-Bug Detection in Real-world Projects
- 20 unique bugs were detected by Legionβ in nine real-world projects, including 3 known CVEs and 5 previously unknown vulnerabilities, outperforming all evaluated baselines and base fuzzers.It detected 17.65% more bugs than Autofzβ using the same base fuzzers.Source: Table 4 · p. 17, §4.5 · pp. 17, 19
4.6 RQ4-Ablation Study
- Ablating resource scheduling, multidimensional evaluation, or seed synchronization reduced branch coverage, path execution, and unique crashes.Without synchronization, unique crashes fell from 58 to 21; without multidimensional evaluation, Cov covered 5.92% fewer branches and detected 11.54% fewer crashes.Source: Table 5 · p. 18, Table 6 · p. 19, §4.6 · pp. 19–20
5 Discussions
The discussion contrasts Legion’s backward-looking, adaptive scheduling with profiling-based and statically allocated alternatives. It also reports robustness checks and identifies limits tied to benchmark selection and fuzzing randomness.
Legion vs. Existing Ensemble Frameworks
- Unlike Autofz’s repeated preparation profiling or EnFuzz’s static allocation, Legion uses prior-round evaluations to shift resources toward better-performing fuzzers.The authors report that Autofz spent more than 15% of overall resources on poorly performing fuzzers in cited evaluations.Source: §5 · p. 20
Seed Evaluation of Legion vs. Power Schedules
- Legion’s seed evaluation serves ensemble-level fuzzer scheduling, unlike within-fuzzer power schedules that allocate mutation energy to individual seeds.Its metric weights are adjusted using standard deviations across base fuzzers, and seeds contributing to the metrics enter the global pool.Source: §5 · p. 21
Robust Evaluation of Legion
- Across ten runs, Legion’s branch- and path-coverage relative error margins remained around 1% to 1.5%, which the authors report as evidence of low variance.The analysis used 80% confidence intervals over the 12-hour campaign.Source: §5 · p. 21
Analysis of Metric Normalization
- Min-Max normalization did not significantly improve boringssl fuzzing performance for branch or path coverage, with both Mann-Whitney U test p-values above 0.57.The normalized variant retained the dynamic standard-deviation-based weights.Source: §5 · p. 21
Threats to Validity
- The benchmark set is older than FuzzBench because EnFuzz depends on QSYM, which FuzzBench does not support; the authors added nine newer projects to broaden evaluation.Their selected subjects still include widely used real-world projects, and the authors repeated experiments ten times to address fuzzing and execution nondeterminism.Source: §5 · pp. 21–22
6 Related Work
The related-work discussion situates Legion among fuzzing approaches, parallel fuzzing frameworks, and vulnerability-detection methods. It distinguishes Legion by its comparative evaluation of fuzzers and dynamic resource allocation.
Fuzzing Techniques
- Generation-based, mutation-based, and hybrid fuzzers use different input-generation or analysis strategies, and Legion can combine them as base fuzzers.The paper also notes machine-learning approaches for learning input formats, improving seed generation or mutation, and predicting seed effects.Source: §6 · p. 22
Parallel Fuzzing
- Prior parallel-fuzzing work focuses on task allocation and synchronization, while Legion allocates test resources dynamically according to comparative fuzzer performance.Unlike Kraken’s optimization of the number of running instances, Legion estimates each base fuzzer’s share of resources.Source: §6 · p. 22
- Legion evaluates fuzzers globally using multidimensional metrics, whereas parallel frameworks commonly evaluate seeds with a single metric for synchronization or modification decisions.The related work also identifies fuzzing as a mainstream vulnerability-detection method and says Legion combines multiple base fuzzers to improve fuzzing efficiency.Source: §6 · p. 23
7 Conclusion
Legion dynamically schedules resources by learning base-fuzzer performance and evaluating seed benefits across multiple dimensions. It outperforms EnFuzz and Autofz with the same base fuzzers and detected 20 bugs across nine real-world projects.
7 Conclusion
- Legion outperforms EnFuzz and Autofz [23] with the same set of base fuzzers.The evaluation also reports 20 bugs detected across nine real-world projects, including three CVEs and five previously unknown bugs.Source: §7 · p. 23
- Legion dynamically schedules ensemble resources by adaptively learning base-fuzzer performance and evaluates seed benefits across multiple dimensions.Source: §7 · p. 23
- Fuzzing randomness means performance-based scheduling cannot guarantee complete accuracy; future work proposes code-based performance predictions.Source: §7 · p. 23
- Legion's end-of-round evaluation stops all base fuzzers and costs extra execution resources; proposed work would evaluate performance on-the-fly.The authors also propose time-decaying historical rewards to better handle fuzzing's non-stationarity and performance shifts.Source: §7 · p. 23