分簇竞争PSO测试用例自动生成算法
2016-01-05黄剑
摘 要：测试用例自动生成是软件测试过程中的一个关键环节。为解决因集簇特性而导致PSO测试用例生成算法计算资源浪费的问题，提出了分簇竞争PSO测试用例生成算法（CTCC-PSO），采用“集簇度”指标对算法进行量化和分析，并通过实验证明新算法的有效性。CTCC-PSO算法包括“集簇度量化”与“簇中用例竞争约简”两个重要过程，根据“集簇度”动态地驱动簇内测试用例进行竞争，从而有效地提升测试用例生成效率。实验结果表明，CTCC-PSO算法在不失鲁棒性的前提下，与基本PSO测试用例生成算法相比，能够有效减少测试迭代规模，同时显著减少参与计算的测试用例总量。
关键词：粒子群优化；测试用例；分簇竞争
DOIDOI：10.11907/rjdk.151963
中图分类号：TP312
文献标识码：A 文章编号文章编号：1672-7800（2015）012-0063-04
基金项目基金项目：
作者简介作者简介：黄剑（1979-），男，江西南昌人，硕士，江西财经大学网络信息管理中心工程师，研究方向为计算机应用。
0 引言
软件测试是确保软件安全的重要环节，目的在于尽可能地发现并改正被测试软件中的错误，提高软件的正确性和可靠性。
传统的软件测试技术[1-4]比较复杂，表现为使用成本高、实际应用难，对具体而多样化的测试目标缺乏较好的鲁棒性。近十几年来，启发性算法被广泛应用于测试用例生成研究，主要研究工作集中在遗传算法（Genetic Algorithms，简称GA）[5-8]、神经网络（Neural Network，简称NN）[9]、蚁群算法（Ant Colony Algorithm，简称ACA）[10]等方法上，并已经取得较为成熟的成果。这些成果标志着具有启发性、学习性和演进性的智能测试用例算法成为测试用例生成算法的重要组成部分。
粒子群优化（Particle Swarm Optimization，简称PSO）[11]测试用例生成算法是一种启发性的自动化测试技术，该算法将测试用例（Test Case，简称TC）的生成过程转化为通过对种群中TC的评估和更新得到最优解的过程。PSO测试用例生成算法具备算法简单、鲁棒性好的特点，同时具有很好的导向性和收敛性[12]。
本文针对目前PSO测试用例生成算法[13-15]由于集簇特性而导致计算资源浪费的问题，提出分簇竞争PSO测试用例自动生成算法（PSO Competitive Test Case generation algorithm with Clustering，简称CTCC-PSO），并对CTCC-PSO算法的“集簇度”（Cluster Indicator，简称CI）进行了定义和分析，提出一种CI驱动的TC竞争策略，用于实现对测试用例种群规模的动态控制，从而达到节约计算资源的目的。通过对比实验与分析，CTCC-PSO与基本PSO测试用例生成算法（Basic PSO test case generation algorithm， 简称B-PSO）相比，在测试用例生成效率和计算成本上均有显著改进。
1 基本PSO测试用例生成算法
1.1 基本思想
图2 TriTyp基准实验CI量化曲线
实验显示CI具有两个基本特性：①CI随迭代进行而递增；②随着迭代的进行，CI波动性逐渐变小并趋于稳定。这两个特性表明，TC在簇内具有相互吸引的能力，并趋向于保持更紧密的邻近关系，即TC在簇内表现出位置趋同性，簇内TC间相互潜在竞争性增强。
2.2 CTCC-PSO
2.2.1 CTCC-PSO算法描述
输入：D-dimensionalSpaceTC空间特征swarmSize：TC种群规模iteratorMax：算法最大迭代次数CImax 簇c竞争驱动门限输出： 最终TC种群//根据测试目标入口参数特征初始化TCswarm = initSwarm（D-dimensionalSpace，swarmSize）； //迭代次数（iterator）达到最大值（iteratorMax）或算法已达到最优解（|fitness|=0）时，算法结束。iterator=0；while （iterator
2.2.2 TC竞争策略
输入： c CTCC-PSO中的轨迹簇CI：簇c的当前CI量化值CImax：簇c策略执行门限输出： 约简后的簇c// 计算簇c的竞争系数σ，CImax为激活簇约简策略的边界σ=CI-CImaxCImax； //c.count为簇c中TC的数量，c.minCount为簇c中最少需要保留的TC数量if（c.count-σ×c.count>c.minCount）{//对簇c内粒子按适应度由低到高排序orderTC（c）；//对簇c内粒子进行竞争和淘汰 for each TC in c { if （TC.orderID<σ×c.count）c.kill（TC）； }}//返回调用者CTCC-PSO；return to CTCC-PSO
3 B-PSO与CTCC-PSO实验对比分析
为进一步测试和分析CTCC-PSO算法的有效性，本节用面向分支插桩对TriTyp和BinarySearch程序进行测试。实验按不同参数和测试对象进行分组，验证新算法的有效性。
3.1 实验安排
CTCC-PSO算法测试实验根据测试对象分为两类：①三角分类（TriTyp）分支覆盖测试；②二分查找算法（BinarySearch）测试。每类实验分为4组，每组进行100次测试。为加强实验的可比性，每组测试中B-PSO算法和CTCC-PSO采用同一组参数，且该组参数均可使B-PSO或CCTC-PSO覆盖测试路径。具体实验编号与参数配置详见表2、表3。
3.2 实验结果与分析
图3为分组实验数据对比图，B-PSO与CTCC-PSO性能分析包括3个方面：①平均迭代次数分析；②测试用例数量分析；③整体效率分析。
平均迭代次数（Average Iterations，简称AI）指某组实验使用相同参数进行n次实验，平均每次实验需要的迭代次数，即AI=∑ni=1iterationsi/n，iterationsi为第i次实验需要的迭代数。对TriTyp进行的4组分支覆盖测试中，CTCC-PSO较B-PSO算法AI最小减少9.02%，最大减少22.80%，平均减少14.25%；对BinarySearch进行的4组分支覆盖测试中，CTCC-PSO较B-PSO算法AI最小减少25.40%，最大减少32.69%，平均减少27.67%。
参与计算的测试用例总数（Test Cases Used in Total，简称TCUT）指某组实验使用相同参数进行n次实验，平均每次实验实际参与计算的测试用例总数，即TCUT=∑ni=1NTCi/n，NTCi为第i次实验实际参与计算的测试用例总数。对TriTyp进行的4组分支覆盖测试中，CTCC-PSO较B-PSO算法TCUT最小减少9.42%，最大减少24.48%，平均减少15.05%；对BinarySearch进行的4组分支覆盖测试中，CTCC-PSO较B-PSO算法TCUT最小减少62.18%，最大减少66.71%，平均减少64.73%。
通过上述分析，CTCC-PSO较B-PSO算法可有效减少平均迭代次数和测试用例总数。分析表明，CTCC-PSO是比B-PSO更具性能优势的测试用例生成算法。
图3 B-PSO/CTCC-PSO分组实验数据对比
4 结语
本文针对PSO测试用例生成算法中TC在搜索空间运动轨迹的集簇特性，提出分簇竞争PSO测试用例生成算法（CTCC-PSO）。CTCC-PSO包含两个新的重要阶段：①CI量化阶段；②簇内竞争约简阶段。实验分析表明：CTCC-PSO算法可以有效节省测试用例的计算成本，同时减少算法迭代次数，是现有测试用例生成算法的有效补充。
本文提出的CTCC-PSO算法具有以下特点：①对测试用例群演进过程中产生的集簇性具有量化能力（Clustering Indicator Quantization，简称CIQ），该能力为基于集簇特性的测试用例竞争提供了决策基础；②CTCC-PSO算法包含了簇内TC竞争约简策略，淘汰本簇中的劣质TC。该策略构建于CIQ，是CTCC-PSO算法优于B-PSO算法的关键。
CTCC-PSO与基本的B-PSO算法相比，迭代次数更少，测试用例更精简，有效地节约了系统计算资源。
参考文献参考文献：
[1] LEE D， YANNAKAKIS M. Principles and methods of testing finite state machines-a survey[J].Proceedings of the IEEE，1996， 84（8）：1090-1123.
[2] JARD C， JERRON T. TGV： theory， principles and algorithms[J]. International Journal on Software Tools for Technology Transfer，2005， 7（4）： 297-315.
[3] AMMANN P E， BLACK P E. A specification-based coverage metric to evaluate test sets[C]. Washington， D.C.， USA： IEEE Computer Society Press， 1999：239-248.
[4] 陈继锋， 朱利， 沈钧毅. 一种基于路径的测试数据自动生成算法[J]. 控制与决策，2005，20（9）：1065-1068.
[5] JONES B， STHAMER H， EYRES D. Automatic structural testing using genetic algorithms[J].Software Engineering Journal， 1996， 11（5）： 299-306.
[6] PARGAS R P， HARROLD M J， PECK R R. Test-data generation using genetic algorithms[J].Software Testing，Verification and Reliability，1999（9）： 263.
[7] GIRGIS M R. Automatic test data generation for data flow testing using a genetic algorithm[J].Journal of Universal Computer Science，2005.
[8] GHIDUK A S， HARROLD M J，GIRGIS M R.Using genetic algorithms to aid test-data generation for data-flow coverage[C].Nagoya， Japan： IEEE Computer Society Press， 2007：41-48.
[9] ZHAO R L， LV S S.Neural-network based test cases generation using genetic algorithm[C].Melbourne， Victoria， Australia： IEEE Press， 2007：97-100.
[10] 陈明师， 刘晓洁， 李涛. 基于多态蚁群算法的测试用例自动生成[J]. 计算机应用研究，2009， 26（6）： 1347-1348.
[11] KENNEDY J， EBERHART R. Particle swarm optimization[C]. Perth， Australia： IEEE Press， 1995：1942-1948.
[12] 周龙甫， 师奕兵. PSO算法粒子运动轨迹稳定收敛条件分析[J]. 控制与决策，2009， 24（10）： 1499-1503.
[13] LI A G， ZHANG Y L. Automatic generation method of test data for software structure based on PSO[J]. Computer Engineering， 2008， 34（6）： 189-193.
[14] CUI H， CHEN L， ZHU B， et al.An efficient automated test data generation method[C].Changsha， China： IEEE Computer Society， 2010：453-456.
[15] BUENO P M S， WONG W E， JINO M. Automatic test data generation using particle systems[C]. Fortaleza， Ceara， Brazil ： ACM Press， 2008：809-814.
[16] HLA K H S， CHOI Y， PARK J S. Applying particle swarm optimization to prioritizing test cases for embedded real time software retesting[C].Sydney， Australia： Institute of Electrical and Electronics Engineers， 2008：527-532.
[17] THORNDIKE E L. Animal intelligence： experimental studies[M]. New Jersey， USA： Transaction Publishers， 2000： 297.
[18] BANDURA A. Social foundations of thought and action：a social cognitive theory[M].New Jersey， USA： Prentice Hall， 1986： 544.
（责任编辑：黄 健）