Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)
计算机科学技术     
基于覆盖难度选择路径的测试数据进化生成
田甜,巩敦卫
中国矿业大学 信息与电气工程学院,江苏 徐州 221116
Evolutionary generation of test data for path coverage through selecting target paths based on coverage difficulty
TIAN Tian,GONG Dun-wei
School of Information and Electrical Engineering, China University of Mining and Technology, Xuzhou 221116, China
 全文: PDF(981 KB)  
摘要：

为了解决消息传递并行程序路径覆盖测试数据生成问题，提出一种基于覆盖难度选择目标路径的测试数据进化生成方法.通过影响路径执行的变量、路径关键条件的复杂度，以及Halstead测度等，选择最容易覆盖的路径作为目标路径，以降低目标路径覆盖的难度；基于该路径，建立测试数据生成问题的数学模型；采用遗传算法生成覆盖目标路径的测试数据.将所提方法应用于5个基准并行程序的测试数据生成, 并与已有方法比较.结果表明，所提方法能够减少测试数据生成过程中的计算量，使用较少的个体评价次数，有效生成覆盖并行程序路径的测试数据.
关键词： 软件测试;  测试数据生成;  并行程序;  路径覆盖;  遗传算法    
Abstract:

In order to tackle the problem of generating test data covering paths of a message-passing parallel program, a method of evolutionarily generating test data was presented through selecting target paths based on the coverage difficulty. In the light of variables affecting a path’s execution, complexities of a path’s crucial conditions, and Halstead’s metric, the path which is the easiest to be covered was selected as the target path to reduce the coverage difficulty. The mathematical model for generating test data was built according to the selected path. A genetic algorithm was employed to solve the above model so as to generate test data covering the target path. The proposed method was applied to generate test data for five benchmark parallel programs and compared to the existing methods. The results show that the proposed method can reduce the computation cost, and effectively generate test data for path coverage of parallel programs with the less number of evaluated individuals.
Key words:  software testing    test data generation    parallel program    path coverage    genetic algorithm
出版日期: 2014-06-12
:  TP 311  
基金资助:

国家自然科学基金资助项目(61075061, 61203304, 61375067)；高等学校博士学科点专项科研基金资助项目(20100095110006)；江苏省自然科学基金资助项目（BK2012566);江苏省普通高校研究生科研创新计划资助项目(CXZZ11_0292).
通讯作者: 巩敦卫，男，教授.     E-mail: dwgong@vip.163.com
作者简介: 田甜(1987-)，女，博士生，从事并行软件测试的科研工作．E-mail: tian_tiantian@126.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
巩敦卫
田甜

引用本文:

田甜,巩敦卫. 基于覆盖难度选择路径的测试数据进化生成[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2014.05.028.

TIAN Tian,GONG Dun-wei. Evolutionary generation of test data for path coverage through selecting target paths based on coverage difficulty. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2014.05.028.

链接本文:

http://www.zjujournals.com/xueshu/eng/CN/10.3785/j.issn.1008-973X.2014.05.028    或    http://www.zjujournals.com/xueshu/eng/CN/Y2014/V48/I5/948

［1］ 李东, 宫云战. 软件测试方法综述［J］. 装甲兵工程学院学报, 2003, 17(2): 913．
LI Dong, GONG Yun-zhan. A summary about software testing methods ［J］. Journal of Academy of Armored Force Engineering, 2003, 17(2): 913．
［2］ 单锦辉, 姜瑛, 孙萍. 软件测试研究进展［J］. 北京大学学报：自然科学版, 2005, 41(1): 134145．
SHAN Jin-hui, JIANG Ying, SUN Ping. Research progress of software testing ［J］. Acta Scientiarum Naturalium Universitatis Pekinensis, 2005, 41(1): 134145.
［3］ 田甜, 巩敦卫. 消息传递并行程序路径覆盖测试数据生成问题的模型及其进化求解方法［J］. 计算机学报,2013, 36(11): 22122223
TIAN Tian, GONG Dun-wei. Model of test data generation for path coverage of message-passing parallel programs and its Evolution-based Solution ［J］. Chinese Journal of computers, 2013, 36(11): 22122223．
［4］ 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): 641655．
［5］ CHRISTAKIS M, SAGONAS K. Detection of asynchronous message passing errors using static analysis ［C］∥Proceedings of the 13th International Symposium on Practical Aspects of Declarative Language. Berlin: Springer, 2011, 6539:518.
［6］ GODEFROID P. Model checking for programming languages using verisoft ［C］∥Proceedings of the Symposium on Principles of Programming Languages. New York: ACM, 1997: 174186．
［7］ FLANAGAN C, GODEFROID P. Dynamic partial-order reduction for model checking software ［C］∥ Proceedings of the Symposium on Principles of Programming Languages. New York: ACM, 2005: 110121．
［8］ VAKKALANKA S, DELISI M, GOPALAKRISHNAN G. Implementing efficient dynamic formal verification methods for MPI programs ［C］∥ Proceedings of the 15th European PVM/MPI Users Group Meeting. Berlin: Springer, 2008, 5205: 248256．
［9］ HRUB V, KRENA B, LETKO Z. Testing of concurrent programs using genetic algorithms ［C］∥Proceedings of the 4th International Symposium on Search Based Software Engineering. Berlin: Springer, 2012: 152167．
［10］ STEENBUCK S, FRASER G. Generating unit tests for concurrent classes ［C］∥ Proceedings of the 6th International Conference on Software Testing, Verification and Validation. New York: IEEE, 2013: 144153．
［11］ CARVER R, LEI Y. Distributed reachability testing of concurrent programs ［J］. Concurrency and Computation: Practice and Experience, 2010, 22(18): 24452466．
［12］ KRAMMER B, RESCH M. Correctness checking of MPI one-sided communication using Marmot ［C］∥Proceedings of the 13th European PVM/MPI Users Group Meeting. Berlin: Springer, 2006, 4192: 105114．
［13］ VETTER J S, SUPINSKI B R. Dynamic software testing of MPI applications with umpire ［C］∥Proceedings of the Supercomputing ACM/IEEE Conference. New York: IEEE, 2000: 7079．
［14］ SOUZA S R S, VERGILIO S R, SOUZA P S L, et al. Structural testing criteria for message-passing parallel programs ［J］. Concurrency and Computation: Practice and Experience, 2008, 20(16): 18931916．
［15］ SOUZA P S L, SOUZA S R S, ZALUSKA E. Structural testing for message-passing concurrent programs an extended test model ［J］. Concurrency and Computation: Practice and Experience, 2013, 25(18): 149158.
［16］ SOUZA S R S, SOUZA P S L, MACHADO M C C, et al. Using coverage and reachability testing to improve concurrent program testing quality ［C］∥Proceedings of the International Conference on Software Engineering and Knowledge Engineering. \[s.l\]:\[s.n.\],2011: 207212.
［17］ XANTHAKIS S, ELLIS C, SKOURLAS C. Application of genetic algorithms to software testing ［C］∥ Proceedings of the International Conference on Software Engineering and its Applications.\[s.l.\]:\[s.n.\], 1992: 625636.
［18］ VARSHNEY S, MEHROTRA M. Search based software test data generation for structural testing: a perspective ［J］. ACM SIGSOFT Software Engineering Notes, 2013, 38(4): 16．
［19］ CONTE S D, DUNSMORE H E, SHEN V Y. Software engineering metrics and models ［M］. San Francisco: Benjamin/Cummings, 1986．
［20］ NEJMEH B A. NPATH: a measure of execution path complexity and its applications ［J］. Communications of the ACM, 1988, 31(2): 188210．
［21］ MCCABE T A. A complexity measure ［J］. IEEE Transactions on Software Engineering, 1976, 2(4): 308320．
［22］ HALSTEAD M. Elements of software science ［M］. North-Holland: Elsevier Science, 1977．
［23］ KUMAR A, TIWARI S, MISHRA K K,et al. Generation of efficient test data using path selection strategy with elitist GA in regression testing ［C］∥Proceedings of the IEEE International Conference on Computer Science and Information Technology. New York: IEEE, 2010, 9: 389393．
［24］ DEBBARMA M K, KAR N, SAHA A. Static and dynamic software metrics complexity analysis in regression testing ［C］∥ Proceedings of the International Conference on Computer Communication and Informatics. New York: IEEE, 2012: 16．
［25］ JEANNE F, KARL J O, JOE D W. The program dependence graph and its use in optimization ［J］. ACM Transactions on Programming Languages and Systems, 1987, 9(3): 319349．
［26］ CLARKE L A, RICHARDSON D J. Symbolic evaluation methods: implementations and applications ［J］. Computer Program Testing, 1981, 65102．
［27］ ZHANG J, WANG X X. A constraint solver and its application to path feasibility analysis ［J］. International Journal of Software Engineering & Knowledge Engineering, 2011, 11(2): 139156.
[1] 赵斌, 张松, 李剑峰. 基于零件摩擦学性能的磨削参数优化[J]. 浙江大学学报(工学版), 2018, 52(1): 16-23.
[2] 张玄武, 郑耀, 杨波威, 张继发. 基于级联前向网络的翼型优化设计[J]. 浙江大学学报(工学版), 2017, 51(7): 1405-1411.
[3] 张丽娜, 余阳. 海量O2O服务组合的优化[J]. 浙江大学学报(工学版), 2017, 51(6): 1259-1268.
[4] 苏亮, 宋明亮, 董石麟, 罗尧治. 循环遗传聚类法稳定图自动分析[J]. 浙江大学学报(工学版), 2017, 51(3): 514-523.
[5] 张俊红,郭迁,王健,徐喆轩,陈孔武. 塑料机油冷却器盖加强筋参数的多目标优化[J]. 浙江大学学报(工学版), 2016, 50(7): 1360-1366.
[6] 司恩波, 王晶, 靳其兵, 周靖林. 工业无线网络链路选择与时隙分配的同步优化[J]. 浙江大学学报(工学版), 2016, 50(6): 1203-1213.
[7] 王树朋,黄凯,严晓浪. 基于遗传算法的覆盖率驱动测试产生器[J]. 浙江大学学报(工学版), 2016, 50(3): 580-588.
[8] 李清,胡志华. 基于多目标遗传算法的灾后可靠路径选择[J]. 浙江大学学报(工学版), 2016, 50(1): 33-40.
[9] 刘扬,鲁乃唯,蒋友宝. 结构体系可靠度分析的改进支持向量回归[J]. 浙江大学学报(工学版), 2015, 49(9): 1692-1699.
[10] 高史义, 罗小华, 卢宇峰, 刘富春, 张晨秋. 基于遗传算法的功能覆盖率收敛技术[J]. 浙江大学学报(工学版), 2015, 49(8): 1509-1515.
[11] 赵琼,童水光,钟崴,葛俊旭. 基于GA-FEA的门座起重机变幅机构优化设计[J]. 浙江大学学报(工学版), 2015, 49(5): 880-886.
[12] 苗峰,谢安桓,王富安,喻峰,周华. 多阶段可替换分组并行机调度问题的求解[J]. 浙江大学学报(工学版), 2015, 49(5): 866-872.
[13] 艾小祥,俞慈君,方强,陈磊,方伟,沈立恒. 基于遗传算法的机翼壁板扫描路径优化[J]. 浙江大学学报(工学版), 2015, 49(3): 448-456.
[14] 过海,倪益华,王进,陆国栋. 车用空调冷凝器性能多目标优化方法[J]. 浙江大学学报(工学版), 2015, 49(1): 142-159.
[15] 肖文生,崔俊国,刘健,吴晓东,黄红胜. 直驱采油用永磁同步电机削弱齿槽转矩优化[J]. 浙江大学学报(工学版), 2015, 49(1): 173-180.