Discovering neglected conditions in software by mining dependence graphs
Discovering neglected conditions in software by mining dependence graphs
复制标题
DOI：
10.1109/tse.2008.24
复制
发表时间：
2008-09-01
影响因子：
7.4
通讯作者：
Yang, Jiong
中科院分区：
文献类型：
--
作者：
Chang, Ray-Yaung;Podgurski, Andy;Yang, Jiong
被忽略的情况是一类重要但很难发现的软件缺陷。本文提出了一种新的方法，揭示被忽视的条件，结合静态程序分析和先进的数据挖掘技术，发现隐含的条件规则的代码库，并发现规则违反，指示被忽视的条件。该方法要求用户指示对要查找的规则的上下文的最小约束，而不是特定的规则模板。为了允许这种普遍性，规则被建模为增强的过程依赖图（EPDG），其中控制和数据依赖边由表示共享数据依赖的边增强的图未成年人。采用启发式最大频繁子图挖掘算法从EPDG中提取候选规则，采用启发式图匹配算法识别规则违反。我们还报告了一个实证研究的结果，其中的方法被应用到四个开源项目（openssl，make，procmail，amaya）。这些结果表明，该方法是有效的，合理的效率。
Neglected conditions are an important but difficult-to-find class of software defects. This paper presents a novel approach for 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.