SUMMARY#R##N##R##N#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.
['Ray‐yaung Chang', 'Andy Podgurski']
Discovering programming rules and violations by mining interprocedural dependences