Abstract

Identifying a defect in a software implementation generally requires its specification. However, we can find promising “defect candidates” by statistical analysis of the implementation alone. The idea is that every large program contains redundancies which may be considered as patterns: “a function that calls lock() also calls unlock()”. Any deviation from a pattern with many instances is a potential defect. Unlike many previous methods, this does not rely on pre-defined patterns or names but works purely structural. The theory of Formal Concepts provides an elegant and practical framework to describe and compute patterns and their violations. Formal Concept Analysis is related to frequent-item mining, which was used previously but lacks the rich algebraic structure of Formal Concepts. Nonetheless, the talk is light on math and builds on intuition and real-world examples. It demonstrates how to find bugs in C programs with a simple control-flow insensitive analysis and object usage anomalies in large Java programs using a flow-sensitive analysis.

Christian Lindig is a member of the scientific staff of Schloss Dagstuhl, a leading international conference center for computer science. He received his PhD from Technical University of Braunschweig in 1999 under supervision of Gregor Snelting for his work on formal concept analysis in software engineering. In 2000 he joined Norman Ramsey’s group at Harvard, co-designed and implemented the initial version of the Quick C—compiler and worked on the definition, implementation, and test of compiler calling conventions. After returning to Germany he joined Andreas Zeller’s group in 2003 at Saarland University and worked on aspect mining, defect localization, and code theft detection. His work on code theft recently received attention by national and international mainstream media, including Deutschlandfunk and Technology Review.