Mimic: Computing Models for Opaque Code
by Stefan Heule, Manu Sridharan and Satish Chandra
10th ACM SIGSOFT International Symposium on the Foundations of Software Engineering
September 2-4, 2015, Bergamo, Italy
Materials
- Paper (.pdf, 565.82 KiB)
- BibTeX (.bib, 382 Bytes)
- GitHub repository
- FSE'15 Replication Package (accepted by FSE)
- Slides (.pptx, 607.25 KiB)
- Slides (.pdf, 1.07 MiB)
Abstract
Opaque code, which is executable but whose source is unavailable or hard to process, can be problematic in a number of scenarios, such as program analysis. Manual construction of models is often used to handle opaque code, but this process is tedious and error-prone. (In this paper, we use model to mean a representation of a piece of code suitable for program analysis.) We present a novel technique for automatic generation of models for opaque code, based on program synthesis. The technique intercepts memory accesses from the opaque code to client objects, and uses this information to construct partial execution traces. Then, it performs a heuristic search inspired by Markov Chain Monte Carlo techniques to discover an executable code model whose behavior matches the opaque code. Native execution, parallelization, and a carefully-designed fitness function are leveraged to increase the effectiveness of the search. We have implemented our technique in a tool Mimic for discovering models of opaque JavaScript functions, and used Mimic to synthesize correct models for a variety of array-manipulating routines.