13. Godefroid, P., Klarlund, N., and Sen, K. DART: Directed automated random testing. In Proceedings of ACM SIGPLAN 2005 Conf. Programming Language Design and Implementation (Chicago, IL, June 2005). 213–223.

14. Godefroid, P., Levin, M. Y., and Molnar, D. Automated whitebox fuzz testing. In Proceedings of Network and Distributed Systems Security (San Diego, Feb. 2008),

151–166.

15. Godefroid, P., Levin, M. Y., and Molnar, D. SAGE: Whitebox fuzzing for security testing. Commun. ACM

55, 3 (Mar. 2012), 40–44.

16. Godefroid, P., Peleg, H., and Singh, R. Learn&Fuzz: Machine Learning for Input Fuzzing. In Proceedings of the 32nd IEEE/ACM Intern. Conf. Automated Software Engineering, Nov. 2017.

17. Hanford, K.V. Automatic generation of test cases. IBM Systems J. 9, 4 (1970).

18. Hoare, C.A.R. An axiomatic approach to computer programming. Commun. ACM 12, 10 (1969), 576–580.

19. Holler, C., Herzig, K., and Zeller, A. Fuzzing with code fragments. In Proceedings of the 21st USENIX Security Symp., 2012.

20. Höschele, M. and Zeller, A. Mining input grammars with AUTOGRAM. In Proceedings of ICSE-C’2017, 31–34.

21. Howard, M. and Lipner, S. The Security Development Lifecycle. Microsoft Press, 2006.

22. King, J.C. Symbolic execution and program Ttesting.

J. ACM 19, 7 (1976), 385–394.

23. Klees, G. T., Ruef, A., Cooper, B., Wei, S., and Hicks, M.

Evaluating fuzz testing. In Proceedings of the ACM Conf. Computer and Communications Security, 2018.

24. Lämmel, R. and Schulte, W. Controllable combinatorial coverage in grammar-based testing. In Proceedings of TestCom, 2006.

25. Majumdar, R. and Xu, R. Directed test generation using symbolic grammars. In Proceedings of ASE, 2007.

26. Maurer, P.M. Generating test data with enhanced context-free grammars. IEEE Software 7, 4 (1990).

27. McMinn, P. Search-based software test data generation: A survey. Software Testing, Verification and Reliability 14, 2 (2004).

28. Pasareanu, C. S., Visser, W., Bushnell, D., Geldenhuys, J., Mehlitz, P., and Rungta, N. Symbolic pathFinder: Integrating symbolic execution with model checking for Java bytecode analysis. Automated Software Engineering, 2013, 20:391–425.

29. Peach Fuzzer; http://www.peachfuzzer.com/.

30. Project Springfield; https://www.microsoft.com/ springfield/, 2015.

31. Protos; http://www.ee.oulu.fi/research/ouspg/protos/.

32. SPIKE Fuzzer; http://resources.infosecinstitute.com/ fuzzer-automation-with-spike/.

33. Stephens, N. et al. Driller: Augmenting fuzzing through selective symbolic execution. In Proceedings of Network and Distributed Systems Security, 2016.

34. Sulley; https://github.com/OpenRCE/sulley.

35. Sutton, M., Greene, A., and Amini, P. Fuzzing: Brute Force Vulnerability Discovery. Addison-Wesley, 2007.

36. Utting, M., Pretschner, A., and Legeard, B. A Taxonomy of model-based testing approaches. Intl. J. Software Testing, Verification and Reliability 22, 5 (2012).

37. Walker, M. et al. DARPA Cyber Grand Challenge, 2016;

http://archive.darpa.mil/cybergrandchallenge/.

38. Yang, X., Chen, Y., Eide, E., and Regehr, J. Finding and understanding bugs in C compilers. In Proceedings of PLDI’2011.

39. Yun, I., Lee, S., Xu, M., Jang, Y., and Kim, T. Qsym: A practical concolic execution engine tailored for hybrid fuzzing. In Proceedings of the 27th USENIX Security Symp., 2018.

40. Zalewski, M. AFL (American Fuzzy Lop), 2015; http:// lcamtuf.coredump.cx/afl/

 

Patrice Godefroid ( [e-mail]) is a partner researcher at Microsoft Research, Redmond, WA, USA.

Copyright held by author/owner.

Publication rights licensed to ACM.

Watch the author discuss this work in the exclusive

Communications video. https://cacm.acm.org/videos/ fuzzing

creating many virtual machines in the cloud and by running different fuzzing tools and configurations on each of these machines. Fuzzing results (bugs) are continually collected by the service and post-processed for analysis, triage and prioritization, with final results available directly to customers on a secured website.

Conclusion

Is fuzzing a hack, an art, or a science? It is a bit of all three. Blackbox fuzzing is a simple hack but can be remarkably effective in finding bugs in applications that have never been fuzzed. Grammar-based fuzzing extends it to an arta form by allowing the user’s creativity and expertise to guide fuzzing. Whitebox fuzzing leverages advances in computer science research on program verification, and explores how and when fuzzing can be mathematically “sound and complete” in a proof-theoretic sense.

The effectiveness of these three main fuzzing techniques depends on the type of application being fuzzed. For binary input formats (like JPEG or PNG), fully-automatic blackbox and whitebox fuzzing techniques work well, provided a diverse set of seed inputs is available. For complex structured non-binary formats (like JavaScript or C), the effectiveness of blackbox and whitebox fuzzing is unfortunately limited, and grammar-based fuzzing with manually-written grammars are usually the most effective approach. For specific classes of structured input formats like XML or JSON dialects, domain-specific fuzzers for XML or JSON can also be used: these fuzzers parse the high-level tree structure of an input and include custom fuzzing rules (like reordering child nodes, increasing their number, inversing parent-child relationships, and so on) that will challenge the application logic while still generating syntactically correct XML or JSON data. Of course, it is worth emphasizing that no fuzzing technique is guaranteed to find all bugs in practice.

What applications should be fuzzed also depends on a number of parameters. In principle, any application that

a Art is “the expression or application of human
creative skill and imagination.”
Despite significant progress in the
art and science of fuzzing over the last
two decades, important challenges re-
main open. How to engineer exhaus-
tive symbolic testing (that is, a form of
verification) in a cost-effective manner
is still an open problem for large ap-
plications. How to automate the gen-
eration of input grammars for com-
plex formats, perhaps using machine
learning, is another challenge. Finally,
how to effectively fuzz large distrib-
uted applications like entire cloud ser-
vices is yet another open challenge.

References

1. Bastani, O., Sharma, R., Aiken, A. and Liang, P. Synthesizing program input grammars. In Proceedings of the 38th ACM SIGPLAN Conf. Programming Language Design and Implementation, 2017, 95–110.

2. Bounimova, E., Godefroid, P., and Molnar, D. Billions and billions of constraints: Whitebox fuzz testing in production. In Proceedings of 35th Intern. Conf. Software Engineering, (San Francisco, May 2013), 122–131.

3. Cadar, C., Dunbar, D., and Engler, D. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proceedings of OSDI’08 (Dec 2008).

4. Cadar, C. and Engler, D. Execution generated test cases: How to make systems code crash itself. In Proceedings of 12th Intern. SPIN Workshop on Model Checking of Soft ware 3639 (San Francisco, CA, Aug. 2005) Lecture Notes in Computer Science, Springer-Verlag.

5. Chipounov, V., Kuznetsov, V. and Candea, G. S2E: A platform for in-vivo multi-path analysis of software systems. In Proceedings of ASPLOS’2011.

6. Claessen, K. and Hughes, J. QuickCheck: A lightweight tool for random testing of Haskell programs. In Proceedings of ICFP’2000.

7. de Moura, L. and Bjorner, N. Z3: An Efficient SMT Solver. In Proceedings of 14th Intern. Conf. Tools and Algorithms for the Construction and Analysis of Systems 4963 (Budapest, April 2008), 337–340. Lecture Notes in Computer Science, Springer-Verlag.

8. Forrester, J.E. and Miller, B.P. An empirical study of the robustness of Windows NT applications using random testing. In Proceedings of the 4th USENIX Windows System Symp., Seattle, (Aug. 2000).

9. Gallagher, T., Jeffries, B., and Landauer, L. Hunting Security Bugs. Microsoft Press, 2006.

10. Ganesh, V., Leek, T., and Rinard. M. Taint-based directed whitebox fuzzing. In Proceedings of ICSE ’2009.

11. Godefroid, P. Higher-order test generation.

In Proceedings of ACM SIGPLAN 2011 Conf. Programming Language, Design and Implementation (San Jose, June 2011). 258–269.

12. Godefroid, P., Kiezun, A., and Levin, M. Y. Grammar-based whitebox fuzzing. In Proceedings of ACM SIGPLAN 2008 Conf. Programming Language Design and Implementation, (Tucson, AZ, USA, June 2008), 206–215.