Trustworthy Systems


Shane Magrath, Defence Science and Technology Group

Industrial Fuzzing - Near Optimal Seed Selection Policy for Improved Crash Yields


Network defenders have an enduring need to find and mitigate security exploitable bugs in software that they care about. Given the high demand and low supply of highly skilled Program Security Analysts automating the security evaluation of software targets remains an important research problem. Fuzzing is one technique for searching for exploitable bugs in software and sadly remains a very effective technique. Simple fuzzing consists of "mutating" a valid input file (say) to a program in a random way and testing if the target program crashes in a security interesting state. Industrial fuzzing is fuzzing that operates at industrial scales - a large virtualisation cluster of many cores with a high performance storage system simultaneously campaigning on software targets. Typical fuzzing campaigns run against a target typically for many months.

Clearly fuzzing is an inefficient and very expensive proposition. Therefore there is considerable interest in techniques that improve operational fuzzing performance. Viewing industrial fuzzing as a stochastic control problem for optimising crash yield provides a rich theoretical framework that can be used to improve various aspects of fuzzing control. In this talk I will show on that "Follow The Leader" (FTL) policy for "seed" selection in the fuzzer significantly improves the yield when benchmarked against the current state of the art "Thompson Sampling" policy. I make an "engineering argument" that the  FTL policy should be considered (in expectation and with some limits) to be a near-optimal seed selection policy given the stochastics of fuzzing crash behaviour.

My claim is testable by experiment. Consequently , we describe ten A/B experimental fuzzing campaigns which confirms my hypothesis against five open source file type targets: XPDF, FreeType, ImageMagick (libTIFF), libPNG and FFMPEG. The experimental data is consistent with both theory and simulation and confirms the yield superiority of the FTL policy in practice.


Shane Magrath received a B.E degree from the University of New South in 1990 and a Ph.D degree from the University of Technology, Sydney in 2006. He is currently a researcher in the Australian Defence Science and Technology Group, in Canberra ACT. His interests are in software vulnerability discovery in general and more specifically, the methods by which we can automate at industrial scale software vulnerability assessments. He previously worked in DSTG as a military communications research with the goal of making network management as autonomous as possible. Prior to completing the Ph.D, Dr Magrath had fifteen years experience in the ICT industry. He variously worked in network planning, design and construction of telecommunications networks and various ICT outsourcing roles.