Reinforcement Learning-based Hierarchical Seed Scheduling for Greybox Fuzzing
Jinghan Wang, Chengyu Song, Heng Yin · 2021
be considered as exercising an entirely different function.Our crucial observation is that when a coverage metric C j is more sensitive than C i , we can use C j to save all the intermediate waypoints without losing the ability to discover more program states; but at the same time, we can use C i to cluster seeds into a representative node and schedule at node level to achieve better exploration.More specifically, the scheduler will choose a node first, and then choose a seed in that node.Based on this observation, we propose to organize the seed pool as a multi-level tree where leaf nodes are real seeds and internal nodes are less sensitive coverage measurements.The closer a node is to the leaf, the more sensitive the corresponding coverage measurement is.Then we can utilize the existing MAB algorithms to further balance between exploitation and exploration.To validate our idea, we implemented two prototypes: one AFL-HIER based on AFL and the other AFL++-HIER based on AFL++.We performed extensive evaluation on the DARPA Cyber Grand Challenge (CGC) dataset [10] and Google FuzzBench [21] benchmarks.Compared to AFLFAST [9], AFL-HIER can find more bugs in CGC (77 vs. 61).AFL-HIER also achieved better coverage in about 83 of 180 challenges and the same coverage on 60 challenges.More importantly, AFL-HIER can find the same amount of bugs and achieve the same coverage faster than AFLFAST.On FuzzBench, AFL++-HIER achieved higher coverage on 10 out of 20 projects than AFL++ (Qemu).Contributions.This paper makes the following contributions:• We propose multi-level coverage metrics that bring a novel approach to incorporate sensitive coverage metrics in greybox fuzzing.• We design a hierarchical seed scheduling algorithm to support the multi-level coverage metric based on the multi-armed bandits model.• We implement our approach as an extension to AFL and AFL++ and release the source code at https://github.com/ bitsecurerlab/aflplusplus-hier.• We evaluate our prototypes on DARPA CGC and Google FuzzBench.The results show that our approach not only can trigger more bugs and achieve higher code coverage, but also can achieve the same coverage faster than existing approaches. II. BACKGROUND A. Greybox FuzzingAlgorithm 1 illustrates the greybox fuzzing process in more detail.Given a program to fuzz and a set of initial seeds, the fuzzing process consists of a sequence of loops named rounds.Each round starts with selecting the next seed for fuzzing from the pool according to the scheduling criteria.The scheduled seed is assigned to a certain amount of power that determines how many new test cases will be generated in this round.Next, test cases are generated through (random) mutation and crossover based on the scheduled seed.Compared to blackbox and whitebox fuzzing, the most distinctive step of greybox fuzzing is that, when executing a newly generated input, the fuzzer uses lightweight instrumentations to capture runtime features and expose them to the fitness function to measure the "quality" of a generated test case.Test cases with good quality will then be saved as a new seed into the seed pool.This step allows a greybox to gradually evolve towards a target (e.g., more coverage).The effectiveness and efficiency of greybox fuzzing depend on the following factors.