Topological Differential Testing
This addresses the challenge of understanding input specifications from program behavior, particularly for file formats like PDF, but appears incremental as it builds on existing topological concepts.
The paper tackles the problem of extracting consensus behavior from multiple programs on a set of inputs, using topological differential testing to identify inputs that cause inconsistencies and reveal de facto specifications, with an application to PDF file format analysis.
We introduce topological differential testing (TDT), an approach to extracting the consensus behavior of a set of programs on a corpus of inputs. TDT uses the topological notion of a simplicial complex (and implicitly draws on richer topological notions such as sheaves and persistence) to determine inputs that cause inconsistent behavior and in turn reveal \emph{de facto} input specifications. We gently introduce TDT with a toy example before detailing its application to understanding the PDF file format from the behavior of various parsers. Finally, we discuss theoretical details and other possible applications.