基于子路径扩展的不可达路径检测方法

doi:10.3969/j.issn.0372-2112.2015.08.013

电子学报 ›› 2015, Vol. 43 ›› Issue (8): 1555-1560.DOI: 10.3969/j.issn.0372-2112.2015.08.013

基于子路径扩展的不可达路径检测方法

王红阳¹, 姜淑娟¹, 王兴亚¹, 鞠小林^1,2, 张艳梅¹

1. 中国矿业大学计算机科学与技术学院, 江苏徐州 221116;
2. 南通大学计算机科学与技术学院, 江苏南通 226019

收稿日期:2014-09-23 修回日期:2014-12-15 出版日期:2015-08-25
- 通讯作者:
- 姜淑娟
- 作者简介:
- 王红阳 男,1990年出生,黑龙江伊春人.中国矿业大学研究生.研究方向为软件测试、不可达路径检测. E-mail:wanghongyang@cumt.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61340037,No.61202006); 中央高校基本科研业务费专项资金 (No.2013NB17); 江苏省青蓝工程; 江苏省333高层次人才培养工程项目; 江苏省研究生培养创新工程 (No.CXZZ12_0935); 南通市应用研究计划 (No.BK2014055)

An Approach for Detecting Infeasible Paths Based on Sub-Path Expansion

WANG Hong-yang¹, JIANG Shu-juan¹, WANG Xing-ya¹, JU Xiao-lin^1,2, ZHANG Yan-mei¹

1. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou, Jiangsu 221116, China;
2. School of Computer Science and Technology, Nantong University, Nantong, Jiangsu 226019, China

Received:2014-09-23 Revised:2014-12-15 Online:2015-08-25 Published:2015-08-25

摘要/Abstract

摘要：

不可达路径是造成软件测试资源消耗的一个重要方面.在路径测试之前,检测程序中的不可达路径可以有效节约软件测试资源.提出了一种基于子路径扩展的不可达路径静态检测方法.该方法首先生成程序的子路径集,将路径的可达性问题转换为不等式组的求解问题.使用约束求解器判断子路径的可达性,可以分为:可达子路径,不可达子路径和无法判定三个部分,并对后面两部分的子路径扩展出的路径做二次可达性检测,最终获得程序中所有路径的可达性信息.可达性检测工作主要在子路径集上进行,因此有效地解决了路径爆炸问题.实验结果表明本文方法可以准确有效地检测出程序中的不可达路径.

关键词: 软件测试, 子路径扩展, 不可达路径检测, 约束求解

Abstract:

Infeasible paths are one of the most important parts to cost the test resources.Before path testing, infeasible paths detecting in a program can save test resources efficiently.This paper presents a static method to detect infeasible paths which is based on sub-path expansion.First, the proposed method generates sub-path set, and the feasibility issues will be converted into inequalities.Second, the constraint solver is used to solve the inequalities, and then we can distinguish the sub-paths into three parts:one part is infeasible sub-paths, the second part is feasible sub-paths, and the third part is undetermined.The paths that are expanded from the latter two parts will be tested again to determine their feasibility.Eventually, the feasibility of all the paths is detected.Most of the detecting work is on sub-path set, so our method makes an effective solution to the path-explosion problem.Experimental results show that the proposed method can detect infeasible paths more accurately and effectively.

Key words: software testing, sub-path expansion, infeasible path detection, constraint solving

中图分类号:

TP311

王红阳, 姜淑娟, 王兴亚, 鞠小林, 张艳梅. 基于子路径扩展的不可达路径检测方法[J]. 电子学报, 2015, 43(8): 1555-1560.

WANG Hong-yang, JIANG Shu-juan, WANG Xing-ya, JU Xiao-lin, ZHANG Yan-mei. An Approach for Detecting Infeasible Paths Based on Sub-Path Expansion[J]. Acta Electronica Sinica, 2015, 43(8): 1555-1560.

参考文献

[1] Arlt S,Sch F M.Joogie:Infeasible code detection for Java[A].Proceedings of CAV'12[C].Berlin:Springer,2012.767-773.
[2] Ding Sun,Zhang Hongyu,Tan H B K.Detection of infeasible paths:Approaches and challenges[A].Proceedings of the 7th International Conference on Evaluation of Novel Approaches to Software Engineering[C].Berlin:Springer,2013.64-78.
[3] Gong Dun Wei,Yao Xiang Juan.Automatic detection of infeasible paths in software testing[J].IET Software,2010,4(5):361-370.
[4] Zhuang Xiao Tong,Zhang Tao,Pande S.Using branch correlation to identify infeasible paths for anomaly detection[A].Pro- ceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture[C].Washington,DC:IEEE Computer Society,2006.113-122.
[5] Suhendra V,Mitra T,Roychoudhury A,et al.Efficient detection and exploitation of infeasible paths for software timing analysis[A].Proceedings of the 43rd Annual Design Automation Conference[C].New York:ACM,2006.358-363.
[6] Delahaye M,Botella B,Gotlieb A.Explanation-based generalization of infeasible path[A].Proceedings of the 3th International Conference on Software Testing,Verification and Validation[C].Los Alamitos:IEEE,2010.215-224.
[7] Jaffar J,Murali V,Navas J,et al.TRACER:A symbolic execution tool for verification[A].Proceedings of CAV'12[C].Berlin:Springer,2012.758-766.
[8] Tomb A,Flanagan C.Detecting inconsistencies via universal reachability Analysis[A].Proceedings of ISSTA'12[C].New York:ACM,2012.287-297.
[9] Hermadi I,Lokan C,Sarker R.Dynamic stopping criteria for search-based test data generation for path testing[J].Information and Software Technology,2014,56(4):395-407.
[10] Ghiduk A S.Automatic generation of basis test paths using variable length genetic algorithm[J].Information Processing Letters,2014,114(6):304-316.
[11] Tonella P,Tiella R,Nguyen C D.Interpolated N-grams for model based testing[A].Proceedings of ICSE'14[C].New York:ACM,2014.10-21.
[12] Ngo M N,Tan H B K.Heuristics-based infeasible path detection for dynamic test data generation[J].Information and Software Technology,2008,50(7):641-655.

[1]	李志博, 李清宝, 兰明敬, 孙剑帆. 基于镜像选择序优化的MART算法[J]. 电子学报, 2022, 50(2): 314-325.
[2]	范书平, 张岩, 马宝英, 万里, 姚念民, 宋妍. 基于均衡优化理论的路径覆盖测试数据进化生成[J]. 电子学报, 2020, 48(7): 1303-1310.
[3]	郭曦, 王盼. 基于依赖条件重构的程序符号值分析方法[J]. 电子学报, 2019, 47(3): 630-635.
[4]	夏春艳, 张岩, 万里, 宋妍, 肖楠, 郭冰. 基于否定选择遗传算法的路径覆盖测试数据生成[J]. 电子学报, 2019, 47(12): 2630-2638.
[5]	巩敦卫, 秦备, 田甜. 基于语句重要度的变异测试对象选择方法[J]. 电子学报, 2017, 45(6): 1518-1522.
[6]	赵祖威, 冯世宁, 汤恩义, 陈鑫, 李宣东, 潘敏学, 赵晨. 一种符号执行制导的循环内界分析方法[J]. 电子学报, 2017, 45(11): 2582-2592.
[7]	廖伟志. 基于路径自动分割的测试数据生成方法[J]. 电子学报, 2016, 44(9): 2254-2261.
[8]	聂楚江, 刘海峰, 苏璞睿, 冯登国. 一种面向程序动态分析的循环摘要生成方法[J]. 电子学报, 2014, 42(6): 1110-1117.
[9]	张岩;巩敦卫. 基于搜索空间自动缩减的路径覆盖测试数据进化生成[J]. 电子学报, 2012, 40(5): 1011-1016.
[10]	曹春红;王利民;赵大哲. 基于离散元胞蚂蚁算法的几何约束求解技术研究[J]. 电子学报, 2011, 39(5): 1127-1130.
[11]	王雅文;宫云战;肖庆;杨朝红. 基于抽象解释的变量值范围分析及应用[J]. 电子学报, 2011, 39(2): 296-303.
[12]	巩敦卫;张岩. 一种新的多路径覆盖测试数据进化生成方法[J]. 电子学报, 2010, 38(6): 1299-1304.
[13]	李书浩, 王戟, 齐治昌, 董威, . 一种面向性质的实时系统测试方法[J]. 电子学报, 2005, 33(5): 827-834.
[14]	缪力, 张大方, 季洁, 宣恒农. 非定态路径测试问题的分析与一种转换算法[J]. 电子学报, 2005, 33(2): 258-261.
[15]	李书浩, 王戟, 董威, 齐治昌. 反应式系统面向性质测试的方法框架[J]. 电子学报, 2004, 32(S1): 226-230.

基于子路径扩展的不可达路径检测方法

An Approach for Detecting Infeasible Paths Based on Sub-Path Expansion

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics