FANDANGO: Evolving Language-Based Testing

Over the past decade, the automated generation of test inputs has made significant advances. Modern fuzzers and test generators easily produce complex input formats that do systematically cover the input and execution space. Testing protocols, though, has remained a frontier for automated testing, as a test generator has to interact with the program under test, producing messages that conform to the current state of the system. Common test generators that mutate recorded interactions often fail at this point, as messages to be generated syntactically and semantically depend on messages received earlier. Alternatively, one could model the protocol interactions. However, existing state models typically abstract away concrete protocol details to facilitate symbolic reasoning-details yet needed for testing concrete implementations. In this paper, we introduce language-based protocol testing, the first approach to specify, automatically test, and systematically cover the full state and input space of protocol implementations. We specify protocols as interaction grammars-an extension of context-free grammars that tag each message element with the communication party that is in charge of producing it. Interaction grammars embed classical state models by unifying states, messages, and transitions all into nonterminals, and can be used for producing interactions as well as parsing them, making them ideally suited for testing protocols. Additional constraints over grammar elements allow us to specify and test semantic features such as binary message formats, checksums, encodings, and the many ways that message features induce states and vice versa. To evaluate the effectiveness of language-based protocol testing, we have implemented it as part of the FANDANGO test generator. We specify several protocols as interaction grammars, including features such as human-readable interactions (SMTP), bit-level encodings (DNS), and dynamic port assignments (FTP), and use them to test the corresponding protocol implementations. By systematically covering the interaction grammar and solving the associated constraints, FANDANGO achieves comprehensive coverage of the protocol interactions, resulting in high code coverage and a thorough assessment of the program under test.