基于分支相关性分析的不可达路径检测方法  

Detecting Infeasible Paths Based on Branch Correlations Analysis

作　　者：姜淑娟[1,2] 韩寒[1] 史娇娇[1] 张艳梅[1,3] 鞠小林[1,4] 钱俊彦[2] 

机构地区：[1]中国矿业大学计算机科学与技术学院,江苏徐州221116 [2]广西可信软件重点实验室(桂林电子科技大学),广西桂林541004 [3]计算机软件新技术国家重点实验室(南京大学),南京210023 [4]南通大学计算机科学与技术学院,江苏南通226019

出　　处：《计算机研究与发展》2016年第5期1072-1085,共14页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61502497,61562015);计算机软件新技术国家重点实验室(南京大学)基金项目(KFKT2014B19);广西可信软件重点实验室(桂林电子科技大学)研究课题(kx201530);南通市应用研究计划基金项目(BK2014055)

摘　　要：软件测试中,不可达路径的存在会导致测试资源浪费,有效地检测程序中的不可达路径有助于节约测试资源、提高测试效率.分支相关性的存在是不可达路径产生的主要起因.因此,确定分支的相关性在不可达路径的检测中占据十分重要的地位.提出了一种利用关联分析和数据流分析确定分支相关性的方法,进而实现不可达路径的自动检测.首先,结合静态分析和动态分析,构建反映程序中各分支判断语句静态依赖关系和动态执行信息的数据集;然后,利用关联分析和数据流分析技术确定分支的相关性;最后,根据分支相关性信息检测不可达路径.基于一组基准程序和开源程序,开展不可达路径检测实验.实验结果表明,该方法能够准确地检测出程序中的不可达路径,可以有效地提高软件测试的效率.The existence of infeasible paths causes a waste of test resources in software testing. Detecting these infeasible paths effectively can save test resources and improve test efficiency. Since the correlation of different conditional statements is the main reason of causing infeasible paths of a program and it costs effort for attempting to cover these paths which are never executed during software testing, the determination of branch correlations plays an important role in detecting infeasible paths. The paper proposes a new approach for detecting the infeasible paths based on association analysis and data flow analysis. Firstly, it builds the data-sets that reflect the static dependencies and the dynamic execution information of conditional statements by combining static analysis with dynamic analysis; then, with two types of branch correlations （called A-B correlation and B-B correlation） defined, it determines the branch correlations respectively with two introduced algorithms which are based on association anatysis and data flow analysis; finally, it detects the infeasible paths in accordance with the obtained and refined branch correlations. The paper applies the proposed approach to some benchmarks programs and industry programs to validate its efficiency and effectiveness. The experimental results indicate that our approach can detect infeasible paths accurately and improve the efficiency of software testing.

关 键 词：软件测试 不可达路径 分支相关性 关联分析 数据流分析 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]