Discovering neglected conditions in software by mining program dependence graphs

Neglected conditions are an important but difficult-to-find class of software defects. This thesis presents an intraprocedural approach and an interprocedural approach to revealing neglected conditions that integrate static program analysis and advanced data mining techniques to discover implicit conditional rules in a code base and rule violations that indicate neglected conditions. The approaches require the user to indicate minimal constraints on the context of the rules to be sought, rather than specific rule templates. In order 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. Greedy algorithms for mining maximal frequent subgraphs and frequent graph minors are used to extract candidate rules from EPDGs, and heuristic algorithms based on graph matching are used to identify rule violations. The evaluation of our approaches on open source projects such as the openssl, net-snmp , and Apache projects demonstrates that our approaches based on mining program dependence graphs are able to discover a significant number of neglected conditions. The experimental results show that our approaches detected 62 new bugs from the latest versions of these applications, with 35 of them confirmed and fixed by developers according to our reports. More interestingly, our empirical study indicates that our approaches are able to discover ordering rules, which involve ordering of function calls, and the corresponding rule violations also.