Coverage-Based Greybox Fuzzing as Markov Chain

By Marcel Böhme, Van-Thuan Pham, Abhik Roychoudhury. IEEE Transactions on Software Engineering, 2016

1,055 citations recorded by the source corpus.

Coverage-based Greybox Fuzzing (CGF) is a random testing approach that requires no program analysis. A new test is generated by slightly mutating a seed input. If the test exercises a new and interesting path, it is added to the set of seeds; otherwise, it is discarded. We observe that most tests exercise the same few “high-frequency” paths and develop strategies to explore significantly more paths with the same number of tests by gravitating towards low-frequency paths. We explain the challenges and opportunities of CGF using a Markov chain model which specifies the probability that fuzzing the seed that exercises path $i$ i generates an input that exercises path $j$ j . Each state (i.e., seed) has an energy that specifies the number of inputs to be generated from that seed. We show that CGF is considerably more efficient if energy is inversely proportional to the density of the stationary distribution and increases monotonically every time that seed is chosen. Energy is controlled with a power schedule. We implemented several schedules by extending AFL. In 24 hours, AFLFast exposes 3 previously unreported CVEs that are not exposed by AFL and exposes 6 previously unreported CVEs 7x faster than AFL. AFLFast produces at least an order of magnitude more unique crashes than AFL. We compared AFLFast to the symbolic executor Klee. In terms of vulnerability detection, AFLFast is significantly more effective than Klee on the same subject programs that were discussed in the original Klee paper. In terms of code coverage, AFLFast only slightly outperforms Klee while a combination of both tools achieves best results by mitigating the individual weaknesses.

Subfields: Computer Science Applications, Software

View Paper: https://www.semanticscholar.org/paper/99f88a55e46c3228a7d624ea9a959b9216a032ba

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Science Applications

In Software

Citations in the corpus

NAUTILUS: Fishing for Deep Bugs with Grammars (2019, result): “This allows us to achieve an effect similar to AFLFast [25].”
The Art, Science, and Engineering of Fuzzing: A Survey (2018, background): “But for more advanced fuzzers such as BFF [49] and AFLFast [37], a major factor to their success lies in their innovative scheduling algorithms.”
Learning to Fuzz from Symbolic Execution with Application to Smart Contracts (2019, methodology): “AFLFast [12] and NEUZZ [53] model program branching behavior using Markov Chains and NNs, respectively, learned from inputs generated during fuzzing.”
VUzzer: Application-aware Evolutionary Fuzzing (2017, background): “In a very recent work [8] (concurrent to our work), the authors of AFLFAST proposed a markovmodel based technique to identify low-frequency paths to focus fuzzing efforts in that direction.”
Hawkeye: Towards a Desired Directed Grey-box Fuzzer (2018, methodology): “AFL determines how many new inputs should be generated (i.e., “energy”) from a test seed to improve the fuzzing effectiveness (i.e., increase the coverage); this is termed “power scheduling” in [6, 7].”
CollAFL: Path Sensitive Fuzzing (2018, methodology): “For example, AFLfast [11] prioritizes seeds that exercise lessfrequent paths, which may be inaccurate given the coverage is captured by an approximate bitmap.”
Fuzzing: A Survey for Roadmap (2022, methodology): “, they intend to discover more code coverage [21, 23, 62, 88, 157, 203].”
kAFL: Hardware-Assisted Feedback Fuzzing for OS Kernels (2017, methodology): “However, with the development of American Fuzzy Lop (AFL), smarter fuzzers have gained significant traction in the industry [1] as well as in research [8, 14, 35, 37].”
AFL++ : Combining Incremental Steps of Fuzzing Research (2020, background): “AFLF AST [11] by Böhme et al. shows the need to stress low-frequency paths to explore more branches and ﬁnd more bugs.”
Skyfire: Data-Driven Seed Generation for Fuzzing (2017, background): “AFLFast [45] boosts the AFL by several strategies to focus most of the fuzzing effort on low-frequency paths so as to explore more paths with the same amount of fuzzing time.”
Angora: Efficient Fuzzing by Principled Search (2018, background): “AFLFast [4] observed that most fuzzing tests exercised the same few “high frequency” paths.”
NEZHA: Efficient Domain-Independent Differential Testing (2017, methodology): “33b, AFL implements the explore schedule as presented in AFLFast [23], thus we omit comparison with the latter.”
Superion: Grammar-Aware Greybox Fuzzing (2018, positive): “A fuzzer can be classiﬁed as generation-based (e.g., [32, 62, 64, 69]) or mutation-based (e.g., [9, 43, 55, 59]), depending on whether test inputs are generated by the knowledge of the input format or grammar or by modifying well-formed test inputs.”
AFLNET: A Greybox Fuzzer for Network Protocols (2020, background): “Meanwhile, vanilla CGF fuzzers like AFL and its extensions [5]–[7] neither know the server state information nor the required structure or order of the messages to be sent.”
Steelix: program-state based binary fuzzing (2017, background): “Grey-box fuzzers (e.g., [8, 24]) are in between.”
REDQUEEN: Fuzzing with Input-to-State Correspondence (2019, methodology): “We, therefore, choose VUZZER as one of the few available academic state-of-the-art fuzzers, as well as AFL with the LAF-INTEL and AFLFAST extensions.”