Finding what's not there

Abstract

Neglected conditions are an important but difficult-to-find class of software defects. This paper presents a novel approach to revealing neglected conditions that integrates static program analysis and advanced data mining techniques to discover implicit conditional rules in a code base and to discover rule violations that indicate neglected conditions. The approach requires the user to indicate minimal constraints on the context of the rules to be sought, rather than specific rule templates. To permit this generality, rules are modeled as graph minors of program dependence graphs, and both frequent itemset mining and frequent subgraph mining algorithms are employed to identify candidate rules. We report the results of an empirical evaluation of the approach in which it was used to discover conditional rules and neglected conditions in ~25,000 lines of source code.