Chemotactic Test Case Recombination for Large-Scale Fuzzing

Authors

  • Konstantin Böttinger Fraunhofer Institute for Applied and Integrated Security, 85748 Garching, Germany

DOI:

https://doi.org/10.13052/jcsm2245-1439.542

Keywords:

Fuzzing, Random Testing, Vulnerability Detection

Abstract

We present a bio-inspired method for large-scale fuzzing to detect vulnerabilities in binary executables. In our approach we deploy small groups of feedback-driven explorers that guide colonies of high throughput fuzzers to promising regions in input space. We achieve this by applying the biological concept of chemotaxis: The explorer fuzzers mark test case regions that drive the target binary to previously undiscovered execution paths with an attrac-tant. This allows us to construct a force of attraction that draws the trailing fuzzers to high-quality test cases. By introducing hierarchies of explorers we construct a colony of fuzzers that is divided into multiple subgroups. Each subgroup is guiding a trailing group and simultaneously drawn itself by the traces of their respective explorers. We implement a prototype and evaluate our presented algorithm to show the feasibility of our approach.

Downloads

Download data is not yet available.

Author Biography

Konstantin Böttinger, Fraunhofer Institute for Applied and Integrated Security, 85748 Garching, Germany

Konstantin Böttinger joined the Fraunhofer Institute for Applied and Integrated Security (AISEC) as research associate in 2011 and is currently working in the Department for Product Protection and Industrial Security. His research focuses on cryptographic protocols, software testing, and anomaly detection. Prior to joining the Fraunhofer AISEC, Konstantin Böttinger studied mathematics and physics at Heidelberg University, where he finished with a Diploma in mathematics.

References

Böttinger, K. (2016). Fuzzing binaries with Lévy flight swarms. EURASIP J. Inform. Sec. 2016.

Böttinger, K. (2016). “Hunting bugs with Lévy flight foraging,” in Proceedings of the IEEE Security and Privacy Workshops, San Jose, CA, 111–117.

Böttinger, K. (2017). “Guiding a colony of black-box fuzzers with chemotaxis,” in Proceeding of the IEEE Symposium on Security and Privacy Workshops, San Jose, CA.

Böttinger, K., and Eckert, C. (2016). “Deepfuzz: triggering vulnerabilities deeply hidden in binaries,” in Proceedings of the 13th International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment (DIMVA), (New York, NY: Springer), 25–34.

Cadar, C., Ganesh, V., Pawlowski, P. M., Dill, D. L., and Engler, D. R. (2008). “EXE: automatically generating inputs of death.” in Proceedings of the 13th ACM Transactions on Information and System Security (TISSEC), eds A. Juels, Wright, and S.D.C. di Vimercati (New York, NY: ACM).

Godefroid, P., Levin, M. Y., and Molnar, D. (2012). SAGE: whitebox fuzzing for security testing. Commun. ACM 55, 40.

Hillen, T., and Painter, K. J. (2009). A users guide to pde models for chemotaxis. J. Math. Biol. 58, 183–217.

Luk, C.-K., Cohn, R., Muth, R., Patil, H., Klauser, A., Lowney, G., et al. (2005). “Pin: Building customized program analysis tools with dynamic instrumentation,” in Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’05, (New York, NY: ACM), 190–200.

Miller, B. P., Fredriksen, L., and So, B. (1990). An empirical study of the reliability of unix utilities. Commun. ACM 33, 32–44.

Painter, K. J., and Hillen, T. (2002). Volume-filling and quorum-sensing in models for chemosensitive movement. Can. Appl. Math. Quart. 10, 501–543.

Rawat, S., Jain, V., Kumar, A., Cojocar, L., Giuffrida, C., and Bos, H. (2017). “Vuzzer: application-aware evolutionary fuzzing,” in Proceedings of the Network and Distributed System Security Symposium (NDSS 2017), San Diego, CA.

Rebert, A., Cha, S. K. Avgerinos, T., Foote, J., Warren, D., Grieco, G., and Brumley, D. (2014). “Optimizing seed selection for fuzzing,” in Proceedings of the USENIX Security Symposium, (Berkeley, CA: USENIX Association), 861–875.

Riley, J. R., Greggers, U., Smith, A. D., Reynolds, D. R., and Menzel, R. (2005). The flight paths of honeybees recruited by the waggle dance. Nature 435, 205–207.

Shoshitaishvili, Y., Wang, R., Salls, C., Stephens, N., Polino, M., Dutcher, A., et al. (2016). “SOK: (state of) the art of war: offensive techniques in binary analysis,” in Proceedings of the IEEE Symposium on Security and Privacy, San Jose, CA, 138–157.

Stephens, N., Grosen, J., Salls, C., Dutcher, A., Wang, R., Corbetta, J., et al., (2016). “Driller: augmenting fuzzing through selective symbolic execution,” in Proceedings of the Network and Distributed System Security Symposium (NDSS), San Diego, CA.

Sumpter, D. J. T., and Beekman, M. (2003). From nonlinearity to optimality: pheromone trail foraging by ants. Animal Behav. 66, 273–280.

Sutton, M., Greene, A., and Amini, P. (2007). Fuzzing: Brute Force Vulnerability Discovery, 1st Edn. Boston, MA: Addison-Wesley Professional.

Takanen, A., DeMott, J., and Miller, C. (2008). Fuzzing for Software Security Testing and Quality Assurance. Norwood, MA: Artech House, Inc.

Woo, M., Cha, S. K., Gottlieb, S., and Brumley, D. (2003). “Scheduling black-box mutational fuzzing,” in Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security (CCS), (New York, NY: ACM), 511–522.

Downloads

Published

2017-09-26

How to Cite

1.
Böttinger K. Chemotactic Test Case Recombination for Large-Scale Fuzzing. JCSANDM [Internet]. 2017 Sep. 26 [cited 2024 Mar. 28];5(4):269-86. Available from: https://journals.riverpublishers.com/index.php/JCSANDM/article/view/6091

Issue

Section

Articles