基于人工免疫算法的软件输出域覆盖测试

南京大学学报(自然科学版) ›› 2018, Vol. 54 ›› Issue (4): 742–.

基于人工免疫算法的软件输出域覆盖测试

张卫祥*，齐玉华

出版日期:2018-04-30
作者简介:北京跟踪与通信技术研究所，北京，100094
基金资助:
基金项目：国家自然科学基金(61502015) 收稿日期：2018－05－17 *通讯联系人，E－mail：vxiang@126.com

Software testing for output domain coverage based on artificial immune algorithm

Zhang Weixiang*，Qi Yuhua

Online:2018-04-30
About author:Beijing Institute of Tracking and Telecommunications Technology，Beijing，100094，China

摘要/Abstract

摘要： 如何实现软件输出域覆盖，是对安全攸关软件开展功能测试时面临的一个难题. 采用智能化软件测试思路，提出了基于人工免疫算法的软件测试数据自动生成方法. 首先分析了软件输出域覆盖问题的由来和面临的困难，说明了利用灰盒测试技术将输出域覆盖转化为软件伪路径覆盖的技术途径，并给出了软件测试数据质量评价的度量指标. 其次，给出了人工免疫算法应用于软件测试数据生成的基本思路，介绍了人工免疫算法的一般步骤及其与遗传算法的异同分析. 然后，分别设计了抗体亲和度评价算子、抗体浓度评价算子、免疫选择算子、克隆算子、变异算子、抑制算子、刷新算子等人工免疫算法的主要算子，实现了基于人工免疫算法的测试数据自动化生成方法. 最后，采用三种不同类型软件对方法有效性进行了验证，并对数据命中率、平均迭代轮次以及测试用例总个数等指标进行了分析. 结果表明，该方法满足软件输出域覆盖要求，总体效果优于遗传算法和随机测试．

Abstract: The purpose of this work is to generate software testing data automatically by using artificial immune algorithm. As known，for software testing of safety－critical software，software output domain coverage is a necessary and important task，and it is also a difficult problem in engineering practice. Using intelligence testing approach，this paper proposes a solution based on artificial immune algorithm. Firstly，the origin and difficulty of the software output domain coverage problem are analyzed. The technical approach to convert the output domain coverage into software pseudo－path coverage using the gray box test technology is illustrated. The metrics of software test data quality evaluation are given. Secondly，the basic idea of applying artificial immune algorithm to software test data generation is given. The general steps of artificial immune algorithm and its similarities and differences with genetic algorithms are introduced. Then，the main operators of the artificial immune algorithm such as antibody affinity evaluation operator，antibody concentration evaluation operator，immune selection operator，clone operator，mutation operator，suppression operator，and refresh operator are designed. Thus，the paper realizes an automatic generation method of test data based on artificial immune algorithm，which is named AIAOT(Artificial Immune Algorithm for Output－oriented Test data generation). Finally，three different types of software are used to verify the validity of the method，and the indexes such as the data hit rate，the average iteration round，and the total number of test cases are analyzed. The results show that this method implements the software output domains coverage and its overall effect is better than the genetic algorithm and random testing.

张卫祥*，齐玉华. 基于人工免疫算法的软件输出域覆盖测试[J]. 南京大学学报(自然科学版), 2018, 54(4): 742–.

Zhang Weixiang*，Qi Yuhua. Software testing for output domain coverage based on artificial immune algorithm[J]. Journal of Nanjing University(Natural Sciences), 2018, 54(4): 742–.

参考文献

[1]　Alessandro O，Gregg R. Software testing：A research travelogue(2000－2014) ∥ Proceedings of the on Future of Software Engineering. Hyderabad，India：ACM，2014：117－132. [2] 黄席樾. 现代智能算法理论及应用. 北京：科学出版社，2005，134. [3] Endoh S，Toma N，Yamada K. Immune algorithm for n－TSP ∥ IEEE International Conference on Systems，Man，and Cybernetics. San Diego，CA，USA：IEEE，1998，3844－3849. [4] 蒋加伏，陈荣元，唐贤瑛等. 基于免疫——蚂蚁算法的多约束QoS路由选择. 通信学报，2004，25(8)：89－95.(Jiang J F，Chen R Y，Tang X Y，et al. A multiple constrained QoS routing based on immune － ant algorithm. Journal of Communications，2004，25(8)：89－95.) [5] 梁勤欧，祝国瑞. 基于克隆选择算法的布局分配问题研究. 测绘通报，2004(11)：17－19.(Liang Q O，Zhu G R. Research on location－allocation problem based on clonal selection principle. Bulletin of Surveying and Mapping，2004(11)：17－19.) [6] Li M J，Tang Z. An artificial immune algorithm based on bidding of power market ∥ Proceedings of International Conference on Power System Technology. Kunming，China：IEEE，2002，2405－2408. [7] 刘　英，戚玉涛，公茂果. 免疫克隆分类算法. 电子学报，2005，33(12A)：2301－2307.(Liu Y，Qi Y T，Gong M G. Immune clonal algorithm for classification. Acta Electronica Sinica，2005，33(12A)：2301－2307.) [8] 左万利，韩佳育，刘　露等. 基于人工免疫算法的增量式用户兴趣挖掘. 计算机科学，2015，42(5)：34－41.(Zuo W L，Han J Y，Liu L，et al. Incremental user interest mining based on artificial immune algorithm. Computer Science，2015，42(5)：34－41.) [9] 莫宏伟，左兴权. 人工免疫系统. 北京：科学出版社，2009，68－172.(Mo H W，Zuo X Q. Artificial immune system. Beijing：Science Press，2009，68－172.) [10] 张卫祥，魏　波，杜会森. 一种基于遗传算法的测试用例优先排序方法. 小型微型计算机系统，2015，36(9)：1998－2002.(Zhang W X，Wei B，Du H S. Test case prioritization method based on genetic algorithm. Journal of Chinese Computer Systems，2015，36(9)：1998－2002.) [11] Zhang W X，Wei B，Du H S. An output－oriented approach of test data generation based on genetic algorithm ∥ Wang G J，Zomaya A，Martinez，et al. Algorithms and Architectures for Parallel Processing. Zhangjiajie，China：Springer，2015：100－108. [12] 张卫祥，齐玉华，李德治. 基于离散粒子群算法的测试用例优先排序. 计算机应用，2017，37(1)：108－113.(Zhang W X，Qi Y H，Li D Z. Test case prioritization based on discrete particle swarm optimization algorithm. Journal of Computer Applications，2017，37(1)：108－113.) [13] 严　俊，张　健. 组合测试：原理与方法. 软件学报，2009，20(6)：1393－1405.(Yan J，Zhang J. Combinatorial testing：Principles and methods. Journal of Software，2009，20(6)：1393－1405.) [14] 段海滨，张祥银，徐春芳. 仿生智能计算. 北京：科学出版社，2011，175－179.(Duan H B，Zhang X Y，Xu C F. Bio－inspired computing. Beijing：Science Press，2011，175－179.) [15] 孙　宁. 人工免疫优化算法及其应用研究. 博士学位论文. 哈尔滨：哈尔滨工业大学，2006.(Sun N. Artificial immune optimization algorithm and applications. Ph. D. dissertation. Harbin：Harbin Institute of Technology，2006.) [16] 李茂军，舒　宜，童调生. 旅行商问题的人工免疫算法. 计算机科学，2003，30(3)：80－82，89.(Li M J，Shu Y，Tong T S. An artificial immune algorithm for travelling salesman problem. Computer Science，2003，30(3)：80－82，89.) [17] 焦李成，杜海峰. 人工免疫系统进展与展望. 电子学报，2003，91(10)：1540－1548.(Jiao L C，Du H F. Development and prospect of the artificial immune system. Acta Electronica Sinica，2003，91(10)：1540－1548.)

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed