ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (5): 1072-1085.doi: 10.7544/issn1000-1239.2016.20148031

• 软件技术 • 上一篇    下一篇

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

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

  1. 1(中国矿业大学计算机科学与技术学院 江苏徐州 221116); 2(计算机软件新技术国家重点实验室(南京大学) 南京 210023); 3(南通大学计算机科学与技术学院 江苏南通 226019); 4(广西可信软件重点实验室(桂林电子科技大学) 广西桂林 541004) (shjjiang@cumt.edu.cn)
  • 出版日期: 2016-05-01
  • 基金资助: 
    国家自然科学基金项目(61502497,61562015);计算机软件新技术国家重点实验室(南京大学)基金项目(KFKT2014B19);广西可信软件重点实验室(桂林电子科技大学)研究课题(kx201530);南通市应用研究计划基金项目(BK2014055)

Detecting Infeasible Paths Based on Branch Correlations Analysis

Jiang Shujuan1,4, Han Han1, Shi Jiaojiao1, Zhang Yanmei1,2, Ju Xiaolin1,3, Qian Junyan4   

  1. 1(School of Computer Science and Technology, China University of Mining and Technology, Xuzhou, Jiangsu 221116); 2(State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 210023); 3(School of Computer Science and Technology, Nantong University, Nantong, Jiangsu 226019); 4(Guangxi Key Laboratory of Trusted Software (Guilin University of Electronic Technology), Guilin, Guangxi 541004)
  • Online: 2016-05-01

摘要: 软件测试中,不可达路径的存在会导致测试资源浪费,有效地检测程序中的不可达路径有助于节约测试资源、提高测试效率.分支相关性的存在是不可达路径产生的主要起因.因此,确定分支的相关性在不可达路径的检测中占据十分重要的地位.提出了一种利用关联分析和数据流分析确定分支相关性的方法,进而实现不可达路径的自动检测.首先,结合静态分析和动态分析,构建反映程序中各分支判断语句静态依赖关系和动态执行信息的数据集;然后,利用关联分析和数据流分析技术确定分支的相关性;最后,根据分支相关性信息检测不可达路径.基于一组基准程序和开源程序,开展不可达路径检测实验.实验结果表明,该方法能够准确地检测出程序中的不可达路径,可以有效地提高软件测试的效率.

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

Abstract: 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 analysis 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.

Key words: software testing, infeasible paths, branch correlations, association analysis, data flow analysis

中图分类号: