Journal article

Coverage-Based Greybox Fuzzing as Markov Chain

Marcel Bohme, Pham Van-Thuan, Abhik Roychoudhury

IEEE Transactions on Software Engineering | Institute of Electrical and Electronics Engineers | Published : 2019

Abstract

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 generates an input that exercises path j. Each state (i.e., seed) has ..

View full abstract

Grants

Awarded by National Research Foundation, Prime Minister's Office, Singapore under its National Cybersecurity R&D Program (TSUNAMi project)


Funding Acknowledgements

We thank Micha Zalewski, all members of the AFL community, and the members of Team Codejitsu for the interesting discussions about our research and the independent evaluation of AFLFAST. This research was partially supported by a grant from the National Research Foundation, Prime Minister's Office, Singapore under its National Cybersecurity R&D Program (TSUNAMi project, No. NRF2014NCRNCR-001-21) and administered by the National Cybersecurity R&D Directorate. An earlier version appeared at the 23rd ACM Conference on Computer and Communications Security (ACM CCS'16) [1].