Combining Input Constraints with Execution Goals

Zusammenfassung

Recent advances in blackbox test generation (fuzzing) allow combining syntax specifications (grammars) with semantic constraints over grammar elements. These constraints not only help in producing valid inputs (“ $\langle$ checksum $\rangle$ should be a Luhn checksum over $\langle$ number $\rangle$ ”) but also allow specifying testing goals (“ payload should be as short as possible”). Such constraints give testers unprecedented control over the generated inputs. However, constraint-based fuzzers like ISLa or Fandango have only been limited to input features and blackbox fuzzing. This paper shows how to extend this concept with execution constraints relating to the program under test. We introduce a set of primitives that check for specific execution features such as coverage of specific locations, memory usage, execution time, and more. Testers can then use these to specify additional testing goals: “I want an input that is (1) valid, (2) as short as possible, and (3) results in a maximum of code coverage.” We implement our approach on top of the Fandango fuzzer and find that its evolutionary algorithm efficiently finds solutions that satisfy input and execution constraints. We demonstrate that combining input and execution constraints enables us to specify and implement approaches such as directed, performance, and coverage-guided fuzzing, effectively covering the entire range of testing goals from whitebox to blackbox fuzzing in a unified framework.