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 preliminary empirical evidence shows that reinforcement fuzzing can outperform baseline random fuzzing.
Most existing automated debugging techniques focus on reducing the amount of code to be inspected and tend to ignore an important component of software failures: the inputs that cause the failure to manifest. In this paper, we present a new technique based on dynamic tainting for automatically identifying subsets of a program's inputs that are relevant to a failure. The technique (1) marks program inputs when they enter the application, (2) tracks them as they propagate during execution, and (3) identifies, for an observed failure, the subset of inputs that are potentially relevant for debugging that failure. To investigate feasibility and usefulness of our technique, we created a prototype tool, PENUMBRA, and used it to evaluate our technique on several failures in real programs. Our results are promising, as they show that PENUMBRA can point developers to inputs that are actually relevant for investigating a failure and can be more practical than existing alternative approaches. We present an algorithm for synthesizing a context-free grammar encoding the language of valid program inputs from a set of input examples and blackbox access to the program. Our algorithm addresses shortcomings of existing grammar inference algorithms, which both severely overgeneralize and are prohibitively slow. Our implementation, GLADE, leverages the grammar synthesized by our algorithm to fuzz test programs with structured inputs. We show that GLADE substantially increases the incremental coverage on valid inputs compared to two baseline fuzzers. Recent work has established the importance of automatic reverse engineering of protocol or file format specifications. However, the formats reverse engineered by previous tools have missed important information that is critical for security applications. In this paper, we present Tupni, a tool that can reverse engineer an input format with a rich set of information, including record sequences, record types, and input constraints. Tupni can generalize the format specification over multiple inputs. We have implemented a prototype of Tupni and evaluated it on ten different formats: five file formats (WMF, BMP, JPG, PNG and TIF) and five network protocols (DNS, RPC, TFTP, HTTP and FTP). Tupni identified all record sequences in the test inputs. We also show that, by aggregating over multiple WMF files, Tupni can derive a more complete format specification for WMF. Furthermore, we demonstrate the utility of Tupni by using the rich information it provides for zero-day vulnerability signature generation, which was not possible with previous reverse engineering tools. A fast algorithm is given to produce a small set of short sentences from a context free grammar such that each production of the grammar is used at least once. The sentences are useful for testing parsing programs and for debugging grammars (finding errors in a grammar which causes it to specify some language other than the one intended). Some experimental results from using the sentences to test some automatically generated simpleLR(1) parsers are also given. Knowledge about how a program processes its inputs can help to understand the structure of the input as well as the structure of the program. In a JSON value like [1, true, "Alice"], for instance the integer value 1, the boolean value true and the string value "Alice" would be handled by different functions or stored in different variables. Our AUTOGRAM tool uses dynamic tainting to trace the data flow of each input character for a set of sample inputs and identifies syntactical entities by grouping input fragments that are handled by the same functions. The resulting context-free grammar reflects the structure of valid inputs and can be used for reverse engineering of formats and can serve as direct input for test generators. A video demonstrating AUTOGRAM is available at https: youtu.be Iqym60iWBBk. The machine production of programs for testing certain aspects of programming products has been achieved. The system has been successfully used on a number of products to establish their reliability in accepting new test cases without error. The input to the system is a syntax definition in a formal notation. The construction of such a definition for a high-level language is an exacting task. It yields important bonuses by deepening knowledge of the structure of the language and showing up obscurities or ambiguities in the existing documentation, Definitions exist for ECMA Algol, FORTRAN IV, and a major subset of PL I. The future effort required to adapt the definitions to particular versions of these languages should be small.