FANDANGO: Evolving Language-Based Testing

Summary

Language-based fuzzers leverage formal input specifications (languages) to generate arbitrarily large and diverse sets of valid inputs for a program under test. Modern language-based test generators combine grammars and constraints to satisfy syntactic and semantic input constraints. ISLa, the leading input generator in that space, uses symbolic constraint solving to solve input constraints. Using solvers places ISLa among the most precise fuzzers but also makes it slow. In this paper, we explore search-based testing as an alternative to symbolic constraint solving. We employ a genetic algorithm that iteratively generates candidate inputs from an input specification, evaluates them against defined constraints, evolving a population of inputs through syntactically valid mutations and retaining those with superior fitness until the semantic input constraints are met. This evolutionary procedure, analogous to natural genetic evolution, leads to progressively improved inputs that cover both semantics and syntax. This change boosts the efficiency of language-based testing: In our experiments, compared to ISLa, our search-based FANDANGO prototype is faster by one to three orders of magnitude without sacrificing precision. The search-based approach no longer restricts constraints to constraint solvers' (miniature) languages. In FANDANGO, constraints can use the whole Python language and library. This expressiveness gives testers unprecedented flexibility in shaping test inputs. It allows them to state arbitrary goals for test generation: "Please produce 1,000 valid test inputs where the voltage field follows a Gaussian distribution but never exceeds 20 mV."