Maverick Woo
ABSTRACT
Black-box mutational fuzzing is a simple yet effective technique to find bugs in software. Given a set of program-seed pairs, we ask how to schedule the fuzzings of these pairs in order to maximize the number of unique bugs found at any point in time. We develop an analytic framework using a mathematical model of black-box mutational fuzzing and use it to evaluate 26 existing and new randomized online scheduling algorithms. Our experiments show that one of our new scheduling algorithms outperforms the multi-armed bandit algorithm in the current version of the CERT Basic Fuzzing Framework (BFF) by finding 1.5x more unique bugs in the same amount of time.
- A. Arcuri, M. Z. Iqbal, and L. Briand. Formal Analysis of the Effectiveness and Predictability of Random Testing. In International Symposium on Software Testing and Analysis, pages 219--229, 2010. Google Scholar
Digital Library
- P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The Nonstochastic Multiarmed Bandit Problem. Journal on Computing, 32(1):48--77, 2002. Google ScholarDigital Library
- P. Auer, N. Cesa-Bianchi, and F. Paul. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47(2--3):235--256, 2002. Google ScholarDigital Library
- T. Avgerinos, S. K. Cha, B. T. H. Lim, and D. Brumley. AEG: Automatic Exploit Generation. In Proceedings of the Network and Distributed Systems Security Symposium, 2011.Google Scholar
- D. A. Berry and B. Fristedt. Bandit Problems: Sequential Allocation of Experiments. Chapman and Hall, 1985.Google Scholar
- A. Bertolino. Software testing research: Achievements, challenges, dreams. In Future of Software Engineering, pages 85--103, 2007. Google ScholarDigital Library
- E. Bounimova, P. Godefroid, and D. Molnar. Billions and Billions of Constraints: Whitebox Fuzz Testing in Production. In Proceedings of the International Conference on Software Engineering, pages 122--131, 2013. Google ScholarDigital Library
- C. Cadar, D. Dunbar, and D. Engler. KLEE: Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs. In Proceedings of the USENIX Symposium on Operating System Design and Implementation, pages 209--224, 2008. Google ScholarDigital Library
- S. K. Cha, T. Avgerinos, A. Rebert, and D. Brumley. Unleashing Mayhem on Binary Code. In Proceedings of the IEEE Symposium on Security and Privacy, pages 380--394, 2012. Google ScholarDigital Library
- D. Engler, D. Chen, S. Hallem, A. Chou, and B. Chelf. Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code. In Proceedings of the ACM Symposium on Operating System Principles, pages 57--72, 2001. Google ScholarDigital Library
- P. Godefroid, M. Y. Levin, and D. Molnar. SAGE: Whitebox Fuzzing for Security. Communications of the ACM, 55(3):40--44, 2012. Google ScholarDigital Library
- A. L. Goel. Software Reliability Models: Assumptions, Limitations, and Applicability. IEEE Transactions on Software Engineering, 11(12):1411--1423, 1985. Google ScholarDigital Library
- N. Gupta, A. P. Mathur, and M. L. Soffa. Automated Test Data Generation Using An Iterative Relaxation Method. In Proceedings of the ACM SIGSOFT International Symposium on Foundations of Software Engineering, pages 231--244, 1998. Google ScholarDigital Library
- A. D. Householder and J. M. Foote. Probability-Based Parameter Selection for Black-Box Fuzz Testing. Technical Report August, CERT, 2012.Google ScholarCross Ref
- B. D. Jovanovic and P. S. Levy. A Look at the Rule of Three. The American Statistician, 51(2):137--139, 1997.Google Scholar
- C. Labs. zzuf: multi-purpose fuzzer. http://caca.zoy.org/wiki/zzuf.Google Scholar
- R. McNally, K. Yiu, D. Grove, and D. Gerhardy. Fuzzing: The State of the Art. Technical Report DSTO--TN--1043, Defence Science and Technology Organisation, 2012.Google Scholar
- B. P. Miller, L. Fredriksen, and B. So. An Empirical Study of the Reliability of UNIX Utilities. Communications of the ACM, 33(12):32--44, 1990. Google ScholarDigital Library
- D. Molnar, X. Li, and D. Wagner. Dynamic Test Generation To Find Integer Bugs in x86 Binary Linux Programs. In Proceedings of the USENIX Security Symposium, pages 67--82, 2009. Google ScholarDigital Library
- C. Pacheco, S. K. Lahiri, M. D. Ernst, and T. Ball. Feedback-Directed Random Test Generation. In Proceedings of the International Conference on Software Engineering, pages 75--84, 2007. Google ScholarDigital Library
- D. Wagner, J. S. Foster, E. A. Brewer, and A. Aiken. A First Step towards Automated Detection of Buffer Overrun Vulnerabilities. In Proceedings of the Network and Distributed Systems Security Symposium, pages 3--17, 2000.Google Scholar
- D. Wolpert and W. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67--82, 1997. Google ScholarDigital Library
Index Terms
- Scheduling black-box mutational fuzzing
Recommendations
Introducing elitist black-box models: When does elitist behavior weaken the performance of evolutionary algorithms?
Black-box complexity theory provides lower bounds for the runtime of black-box optimizers like evolutionary algorithms and other search heuristics and serves as an inspiration for the design of new genetic algorithms. Several black-box models covering ...
Program-Adaptive Mutational Fuzzing
SP '15: Proceedings of the 2015 IEEE Symposium on Security and PrivacyWe present the design of an algorithm to maximize the number of bugs found for black-box mutational fuzzing given a program and a seed input. The major intuition is to leverage white-box symbolic analysis on an execution trace for a given program-seed ...
OneMax in Black-Box Models with Several Restrictions
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary ComputationAs in classical runtime analysis the OneMax problem is the most prominent test problem also in black-box complexity theory. It is known that the unrestricted, the memory-restricted, and the ranking-based black-box complexities of this problem are all of ...
Comments