Perracotta: Mining Temporal API Rules from Imperfect Traces

Jinlin Yang, David Evans
Department of Computer Science
University of Virginia
         Deepali Bhardwaj, Thirumalesh Bhat, Manuvir Das
Center for Software Excellence
Microsoft Corporation
28th International Conference on Software Engineering
Shanghai, China
20-28 May 2006

Dynamic inference techniques have been demonstrated to provide useful support for various software engineering tasks including bug finding, test suite evaluation and improvement, and specification generation. To date, however, dynamic inference has only been used effectively on small programs under controlled conditions. In this paper, we identify reasons why scaling dynamic inference techniques has proven difficult, and introduce solutions that enable a dynamic inference technique to scale to large programs and work effectively with the imperfect traces typically available in industrial scenarios. We describe our approximate inference algorithm, present and evaluate heuristics for winnowing the large number of inferred properties to a manageable set of interesting properties, and report on experiments using inferred properties. We evaluate our techniques on JBoss and the Windows kernel. Our tool is able to infer many of the properties checked by the Static Driver Verifier and leads us to discover a previously unknown bug in Windows.
Note: An earlier version of this paper used "Terracotta" in the title. The name was changed to "Perracotta" due to a trademark issue.

Keywords: Dynamic analysis, temporal properties, specification inference.

Complete Paper (10 pages) [PDF]

Inexpensive Program Analysis Group Page