2020 · 109 citations · 27 references
ComputingComputer ScienceComputer SystemsInformation TheoryMachine LearningProbability TheoryEntropyInformation MeasuresInformation ProcessingInput Fuzzing
In this paper, we take the fundamental perspective of fuzzing as a learning process. Suppose before fuzzing, we know nothing about the behaviors of a program P: What does it do? Executing the first test input, we learn how P behaves for this input. Executing the next input, we either observe the same or discover a new behavior. As such, each execution reveals ”some amount” of information about P’s behaviors. A classic measure of information is Shannon’s entropy. Measuring entropy allows us to quantify how much is learned from each generated test input about the behaviors of the program. Within a probabilistic model of fuzzing, we show how entropy also measures fuzzer efficiency. Specifically, it measures the general rate at which the fuzzer discovers new behaviors. Intuitively, efficient fuzzers maximize information.
27
A Mathematical Theory of Communication
Claude E. Shannon · Bell System Technical Journal · 1948 · 80.7K citations
Coverage-based Greybox Fuzzing as Markov Chain
Marcel Böhme, Van-Thuan Pham, Abhik Roychoudhury · 2016 · 619 citations
George Klees, Andrew Ruef, Benji Cooper et al. · 2018 · 597 citations · Full text