publication . Conference object . Preprint . 2018

Deep Reinforcement Fuzzing

Böttinger, Konstantin; Godefroid, Patrice; Singh, Rishabh;
Open Access English
  • Published: 14 Jan 2018
Abstract
Fuzzing is the process of finding security vulnerabilities in input-processing code by repeatedly testing the code with modified inputs. In this paper, we formalize fuzzing as a reinforcement learning problem using the concept of Markov decision processes. This in turn allows us to apply state-of-the-art deep Q -learning algorithms that optimize rewards, which we define from runtime properties of the program under test. By observing the rewards caused by mutating with a specific set of actions performed on an initial program input, the fuzzing agent learns a policy that can next generate new higher-reward inputs. We have implemented this new approach, and prelim...
Subjects
acm: TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS
free text keywords: Computer Science - Artificial Intelligence, Computer Science - Cryptography and Security
23 references, page 1 of 2

[1] M. Sutton, A. Greene, and P. Amini, Fuzzing: Brute Force Vulnerability Discovery, 1st ed. Boston, MA, USA: Addison-Wesley Professional, 2007.

[2] M. Howard and S. Lipner, The Security Development Lifecycle. Microsoft Press, 2006.

[3] G. Tesauro, “Practical issues in temporal difference learning,” in Advances in neural information processing systems, 1992, pp. 259-266.

[4] --, “Td-gammon: A self-teaching backgammon program,” in Applications of Neural Networks. Springer, 1995, pp. 267-285.

[5] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski et al., “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, pp. 529-533, 2015.

[6] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot et al., “Mastering the game of go with deep neural networks and tree search,” Nature, vol. 529, no. 7587, pp. 484-489, 2016.

[7] R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction. MIT press Cambridge, 1998.

[8] A. Takanen, J. DeMott, and C. Miller, Fuzzing for Software Security Testing and Quality Assurance, 1st ed. Norwood, MA, USA: Artech House, Inc., 2008.

[9] P. Godefroid, M. Y. Levin, and D. A. Molnar, “Automated whitebox fuzz testing.” in NDSS, vol. 8, 2008, pp. 151-166. [Online]. Available: http://46.43.36.213/sites/default/files/Automated%20Whitebox% 20Fuzz%20Testing%20(paper)%20(Patrice%20Godefroid).pdf

[10] P. Purdom, “A sentence generator for testing parsers,” BIT Numerical Mathematics, vol. 12, no. 3, pp. 366-375, 1972.

[11] M. Utting, A. Pretschner, and B. Legeard, “A Taxonomy of Model-Based Testing,” Department of Computer Science, The University of Waikato, New Zealand, Tech. Rep, vol. 4, 2006.

[12] M. Zalewski, “American fuzzy lop,” http://lcamtuf.coredump.cx/afl/.

[13] P. Godefroid, H. Peleg, and R. Singh, “Learn&fuzz: Machine learning for input fuzzing,” in 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE 2017), January 2017. [Online]. Available: https://www.microsoft.com/en-us/research/ publication/learnfuzz-machine-learning-input-fuzzing/ [OpenAIRE]

[14] K. V. Hanford, “Automatic generation of test cases,” IBM Systems Journal, vol. 9, no. 4, pp. 242-257, 1970.

[15] O. Bastani, R. Sharma, A. Aiken, and P. Liang, “Synthesizing program input grammars,” in Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, ser. PLDI 2017. New York, NY, USA: ACM, 2017, pp. 95-110. [Online]. Available: http://doi.acm.org/10.1145/3062341.3062349

23 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Conference object . Preprint . 2018

Deep Reinforcement Fuzzing

Böttinger, Konstantin; Godefroid, Patrice; Singh, Rishabh;