SUMMARY This paper presents a novel approach to discovering implicit programming rules and rule violations in a code base, which integrates static interprocedural analysis and graph mining techniques to identify both function‐call ordering rules and conditional rules that check input parameters or return values of functions. The approach discovers rules even when rule instances cross function boundaries. Rules are modeled as graph minors of dependence graphs augmented with edges indicating shared data dependences. The approach employs two innovative algorithms: a greedy one for mining maximal frequent minors from a set of interprocedural dependence spheres and a heuristic minor‐matching algorithm for discovering rule violations. We evaluated our approach on the latest versions of three applications: net‐snmp, openssl, and the Apache HTTP server. It detected 62 new bugs (24 involving rules with interprocedural instances), 35 of which have been confirmed and fixed recently by developers based on our reports. Copyright © 2011 John Wiley & Sons, Ltd.

We present empirical results indicating that when programmers fix bugs, they often fail to propagate the fixes to all of the locations in a code base where they are applicable, thereby leaving instances of the bugs in the code. We propose a practical approach to help programmers to propagate many bug fixes completely. This entails first extracting a programming rule from a bug fix, in the form of a graph minor of an enhanced procedure dependence graph. Our approach assists the programmer in specifying rules by automatically matching simple rule templates; the programmer may also edit rules or compose them from scratch. A graph matching algorithm for detecting rule violations is then used to locate the places in the code base where the bug fix is applicable. Our approach does not require that rules occur repeatedly in the code base. We present empirical results indicating that the approach nevertheless exhibits good precision.

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 enhanced procedure dependence graphs (EPDGs), in which control and data dependence edges are augmented by edges representing shared data dependences. A heuristic maximal frequent subgraph mining algorithm is used to extract candidate rules from EPDGs, and a heuristic graph matching algorithm is used to identify rule violations. We also report the results of an empirical study in which the approach was applied to four open source projects (openssl, make, procmail, amaya). These results indicate that the approach is effective and reasonably efficient.

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.