马竹根,舒少华
(1. 怀化学院计算机科学与工程学院,湖南 怀化 418008;2. 怀化市铁路第一小学,湖南 怀化 418000)
智能水滴算法在代码覆盖测试中的应用
马竹根1,舒少华2
(1. 怀化学院计算机科学与工程学院,湖南 怀化 418008;2. 怀化市铁路第一小学,湖南 怀化 418000)
代码覆盖在软件测试中得到了广泛应用,表示了代码被测试的程度。论文提出了一种利用智能水滴算法优化代码覆盖的算法,描述了如何把独立路径生成问题转换成智能水滴在控制依赖图的各边之间寻找最优路径的问题,通过生成带有权值的独立路径来自动生成测试序列,使得测试人员可以最优地安排测试顺序,保证充分的代码覆盖。
软件测试;控制依赖图;代码覆盖;独立路径;智能水滴算法
软件测试分为黑盒测试和白盒测试。白盒测试的充分性准则中,覆盖测试[1]可以针对不同的覆盖测试标准,以覆盖元素是否己经达到覆盖要求判断测试的充分性,其中,路径覆盖是最重要的一种覆盖测试[2]。生成测试用例[3]往往需要耗费大量的时间,软件自动化测试[4-5]将有效地减轻测试人员的负担,提高软件测试的效率和软件质量。近年来,研究人员开始使用粒子群优化算法[6]、蜂群算法[7]、神经网络[8]、蚁群算法[9]、模拟退火算法[10]等智能优化算法来解决软件测试中的测试用例的生成问题。
智能水滴算法[11](Intelligent Water Drops algorithms,IWD)是在2007年提出的一种群智能算法,模拟了天然水滴在河流系统中流动的过程,使用一种构造性的方法来构建给定问题的最优解,每个水滴通过遍历给定问题的搜索空间找到最佳路径,然后修改其流动的环境。智能水滴算法已经应用于许多自然科学与工程领域,显示出算法的强大的优势和潜力。
控制流程图(control flow graph,CFG)是程序的图形表示,控制流图可转换为控制依赖图(control dependency graph,CDG)。路径覆盖测试数据生成问题可描述为:给定程序的一条目标路径,在程序的输入空间寻找测试数据,使得以该测试数据为输入所穿越的路径为目标路径[12]。路径选择是覆盖测试中的十分重要的步骤,目标覆盖元素的选取以及初始路径的选择都依赖于控制流图上的依赖关系[13]。智能水滴算法是一种基于图的算法,因此智能水滴算法可以用于测试路径选择,使用智能水滴算法生成所有可能的测试序列用于计算代码覆盖率,使用所提出的算法计算测试用例能够遍历的所有可能路径及其相应的权值。本文提出了一种使用智能水滴算法优化技术生成自动测试序列的算法,为代码覆盖测试问题提供了一种新的解决方案。算法中应用控制依赖图(control dependency graph,CDG)作为算法的输入。
定义1 令S是一个源程序,s1和s2是S中的语句。s2是控制依赖于s1,当且仅当满足下列条件[14]:
(1)s1和s2之间存在一条路径;
(2)存在一条执行路径从s1到程序结束但不经过s2。
定义2 控制依赖图CDG(control dependency graph)是一个有向图G=(V, E),其中结点V表示程序中的语句,E表示边。边s1→s2表示从结点s1到s2的控制依赖。G中有一个特殊的源结点,表示程序的开始,它可以到达图中的每个结点。
从上面的定义可以看出,控制依赖在程序中主要由条件语句和循环语句构成。条件语句中的条件判断与对应的语句体之间存在控制依赖关系,循环条件判断和循环体之间存在控制依赖。控制依赖图中的节点表示语句,边表示它们之间的控制依赖关系。
智能水滴[11](Intelligent Water Drop,IWD),它具有以下两个重要的属性:水滴携带的泥土量soil(IWD)和水滴的速度velocity(IWD),当水滴从一个位置移动到下一个位置时,这两个属性会随着水滴流动而发生改变。水滴的速度非线性反比于路径上的泥土量。通过从路径中移除一些泥土来增加IWD的泥土,并且增加的泥土量是非线性反比于在不同位置之间移动所花费的时间。智能水滴移动的时间正比于不同位置之间的距离,反比于水滴的移动速度。智能水滴在遇到多条路径可选时,会更倾向于选择泥土量较少的路径。对于智能水滴可能选择的下一个位置,通过计算随机分布函数来实现,使得选择路径的概率与可用路径的土壤成反比。
3.1 适应度函数
要使用智能水滴算法解决路径覆盖问题,需要把该问题建模为一个函数优化问题,适应度函数的建立是关键,常用的适应度函数通常包括层接近度和分支距离[15]。设计适应度函数用来计算控制依赖图中的泥土量,基本思想是让更深更复杂的路径权值更大。构造良好的适应度函数可以增加找到求解方案和达到更高覆盖的机会,算法中使用的适应度函数如下:
soil (i, j) =a *subgraph (j) +b*condition (j), {if j是判断语句condition (j)=1,else condition (j)=0}
soil (i, j) =1 {if subgraph(j) && condition(j) = =0}
其中,soil(i,j)表示从结点i到结点j的边上的泥土量,Subgraph (j)是给定图中结点j的下层结点数。智能水滴从图的源结点出发,使用适应度函数计算每一条路径的选择概率,概率大的路径认为是水滴选择的路径。参数a和b分别赋值为常量2和1,这样赋值的原因是给那些子结点多的结点分配更高的权值。
如果subgraph(j)和condition(j)等于0,那么soil (i, j) =1。这是因为soil(I, j)将会用来计算对应节点的概率,并且要求概率不能为零。这样选择适应度函数是因为在任一判断节点或更复杂的路径中都可能产生错误。
3.2 算法步骤
步骤1:初始化参数
P(i,j) //选择从结点i到结点j的路径的概率
Time (i, j) // 从结点i到结点j的时间
ΔSoil (i, j, iwd) //从结点i到结点j泥土的增量
Vel (i, j, iwd) //从结点i到结点j的速度
av=1, bv= 1, cv=1 //速度更新参数。
as=1, bs= 1, cs=1 //泥土更新参数。
ρ=0.1 // 局部更新参数,0≤ρ≤1,依赖于结点上泥土量的多少
Init_Vel =200 //初始化IWD的速度为200
Vc (IWD) = {} // IWD遍历路径Vc (IWD),/初始值为空。
步骤2:更新参数的值
(1)while(CDG不为空)
(2)计算概率
按以下公式计算出从当前结点i出发选择结点j的概率。
P(i,j)=soil(i,j)/Σk ≠vcSoil(i,k)
soil(i,j)表示结点之间的泥土量,Σk ≠vcSoil(i,k)表示能从当前结点i遍历的路径上的泥土的总和。在原算法中,IWD朝泥土量少的路径移动,因为我们要测试更复杂的程序来发现错误,因此在算法中IWD朝泥土量多的路径移动。
(3)计算移动的时间
time (i.j) = (subgraph (i)-subgraph (j))/vel (iwd)
subgraph (i)-subgraph (j)对应结点之间的距离,vel(iwd)表示IWD的速度。
(4)计算IWD的泥土
ΔSoil (i, j, iwd) = as/ (bs+ cs*time (i, j))
as,bs,cs是由用户选定的正数。
(5)计算IWD的速度
vel(i, j, iwd) = vel(iwd) + (av/ (bv+ cvsoil(i, j)))
av,bv,cv是由用户选定的正数,soil(i, j)是结点i到结点j的路径上的泥土量。
(6)计算路径上的泥土量
Soil (i, j) = (1 - ρ) soil (i, j) - ρ * Δsoil (i, j, iwd)
ρ=0.1,是一个正的参数,Δsoil (i, j, iwd)是IWD从结点i到结点j带走的泥土量。
(7)重复步骤(2)-(6)直到遇到终端结点(叶子结点)或者是已遍历结点。到达终端结点后,删除该结点,同时检查该节点的父节点,如果所有的叶子结点被删除了,则将该结点删除。
(8)完成一条可能路径后更新遍历路径列表,重复执行步骤2,开始新一轮的迭代。如果CDG为空了,就意味着所有的路径已经遍历完成,结束循环。
通过这种方式可以找出所有可能的路径,而且每条路径带有相应的权值,路径测试顺序的优先级可直接对应路径的权值,权值高的路径优先测试。
以数据结构中熟知的二分查找算法为例说明IWD的执行过程。二分查找算法C++源程序如图1所示,其对应的控制依赖图如图2所示。
算法步骤:
首先计算每个结点的子节点的个数,通过深度优先遍历可得到每个结点的子节点数。结点的子节点数如下:
A=8,C=6,D=3,E,I,F,G,H的子节点数为0。
检查结点的判断条件值,A、C、D结点是判定节点,condition =1,其余结点condition=0。
IWD的迭代过程如下:
第1次迭代:
IWD从结点A开始,有两条可选路径J和C,为了确定下一个遍历结点,计算两个节点的选择概率。根据3.1节适应度函数公式soil(i, j) =a *subgraph (j) +b*condition (j), soil (i, j) =1 {if subgraph(j) && condition(j) = =0 }计算如下:
Soil(A,C)=2*6+1*1=13,Soil(A,J)=2*0+1*0=1(su bgraph(j)和condition(j)都为0,根据3.1节适应度计算公式Soil(A,J)=1)
P(A,J)= Soil(A,J)/(Soil(A,J)+ Soil(A,C))=1/14,
P(A,C)= Soil(A,C)/(Soil(A,J)+ Soil(A,C))=13/14,结点C的概率大于结点J的概率,因此选择结点C作为一下遍历结点。从结点A到结点C的时间计算如下:
Time(A,C)=(subgraph (A)-subgraph (C))/vel (iwd)=(8-6)/200=2/200=0.01
按照算法步骤2中的步骤(4)-(6)计算如下:
Δ Soil(A,C) = as/(bs+cs*time (A, C))=1/1+ 1*0.01)=0.99
Δvel(A,C) = vel(iwd) + (av/(bv+ cvsoil(i, j)))=100+1/(1+13))=200.07
图1 二分查找算法C++源程序Fig.1 Source code of Binary-Search
图2 二分查找算法CDG(控制依赖图)Fig.2 CDG of Binary-Search
Soil (A, C) = (1-ρ) soil (A, C)-ρ * Δsoil (A,C)= 0.9*13-0.1*0.98=11.6
Soil(iwd)=0.99
到达结点C后,水滴有3个可能的结点D、E、I可选。计算所有可能结点的选择概率:Soil(C,D)=2*3+1*1=7,Soil(C,E)=1,Soil(C,F)=1 P(C,D)=Soil(C,D)/(Soil(C,D)+Soil(C,E)+Soil(C, F))=7/9=0.77
P(C,E)=Soil(C,E)/(Soil(C,D)+Soil(C,E)+Soil(C,F))= 1/9=0.11
P(C,I)=Soil(C,I)/(Soil(C,D)+Soil(C,E)+Soil(C, F))=1/9=0.11
结点D的概率大于其他结点,因此水滴流向结点D。
Time(C,D)=(6-3)/200.07=0.015
ΔSoil (C,D) = 1/(1+1*0.015)=0.985
Δvel(C,D) =200.07+1/(1+1*7))=200.196
Soil(C,D)=(1-ρ)soil (C,D)-ρ *Δsoil (C,D)= 0.9*7-0.1*0.985=6.2
Soil(iwd)=0.99+0.985=1.984
得到路径:A-C-D。到达结点D后,水滴要决定下一个遍历结点,计算如下:
Soil(D,F)=1,Soil(D,G)=1,Soil(D,H)=1,
P(D,F)=Soil(D,F)/(Soil(D,F)+Soil(D,G)+Soil(D, FH))=1/3=0.33
P(D,G)=Soil(D,G)/(Soil(D,F)+Soil(D,G)+Soil(D, FH))=1/3=0.33
P(D,H)=Soil(D,H)/(Soil(D,F)+Soil(D,G)+Soil(D, FH))=1/3=0.33
三个结点的选择概率相同,从中随机选择一个,比如选择结点F,
Time(D,F)= (3-0)/200.196=0.015
ΔSoil (D,F) = 1/(1+1*0.015)=0.985
Δvel(D,F) =200.196+1/(1+1*1))=200.696
Soil (D,F) =(1-ρ) soil(D, F)-ρ * Δsoil (D,F)= 0.9*1-0.1*0.985=0.801
Soil(iwd)=1.984+0.985=2.961
F是叶子结点,第一次迭代结束,得到遍历路径Path1:A-C-D-F,路径的权重=Soil(A,C)+Soil (C,D)+ Soil(D,F)=13+7+1=21。IWD又从根结点A开始进行第2次迭代,通过同样的计算可得到其他可能的遍历路径和权值。实验结果如表1所示。
通过智能水滴算法得到了所有可能的带有优先级的独立路径,每一条路径的权值是路径上的泥土量的总和,权值越高的路径优先级越高,优先级可以帮助测试者决定路径的测试顺序,对于测试人员来说是很有用处的。
表1 路径及权值表Table 1 Path and weight
测试用例的生成是软件测试的重要内容,高效的软件测试用例自动生成方法可以简化软件测试过程,减少软件测试成本,提高软件测试效率和测试质量,软件测试面对的一个主要问题就是要自动生成测试数据实现充分的测试覆盖。本文提出了一种使用智能水滴算法自动生成软件测试顺序的策略,算法的输出结果包括所有可能的独立路径和路径的权值,可用来分析代码覆盖率,帮助软件测试人员确定软件测试顺序。下一步的工作中可将算法中的随机选择改用其他启发式算法代替来提高算法的效率。
[1] 俞濛, 黄俊飞. 覆盖测试中基于回溯法的路径选择[J]. 软件, 2014, 35(11): 9-13. Yu Meng, Huang Junfei. Path selection in coverage test based on backtracking[J]. Software, 2014, 35(11): 9-13.
[2] 姚香娟, 巩敦卫, 李彬. 融入神经网络的路径覆盖测试数据进化生成[J]. 软件学报, 2016, 27(4): 828-838. Yao XiangJuan, Gong DunWei, Li Bin. Evolutional test data generation for path coverage by integrating neural network[J]. Journal of Software, 2016, 27(4): 828-838.
[3] 许媛媛. 基于CBR的测试用例复用方法研究[J]. 软件, 2015, 36(9): 117-120. Xu Yuanyuan. A study of test case reuse based on CBR[J]. Software, 2015, 36(9): 117-120.
[4] 王如迅. 基于SWTBot技术的软件自动化测试的研究与实现[J]. 软件, 2016, 37(02): 121-128. Wang Ruxun. Research and iImplementation of software test automation technology based SWTBot[J]. Software, 2016, 37(02): 121-128.
[5] 高楊, 袁玉宇. 基于软件自动化测试效率的研究[J]. 软件, 2012, 33(11): 77-80. Gao Yang, Yuan Yuyu. The software automation test efficiency research[J]. Software, 2012, 33(11): 77-80.
[6] 姜淑娟, 王令赛, 薛猛, 等. 基于模式组合的粒子群优化测试用例生成方法[J]. 软件学报, 2016, 27(4): 785-801. Jiang Shujuan, Wang Lingsai, Xue Meng, et al. Test case generation based on combination of schema using particle swarm optimization[J]. Journal of Software, 2016, 27(4): 785-801.
[7] 李云玮, 孙忱, 范玉顺. 基于智能非信息素蜂群优化的软件测试研究[J]. 计算机应用研究, 2014, 31(8): 2399-2403. Li Yunwei, Sun Chen, Fan Yushun. Intelligent non- pheromone swarm optimization based software test suite[J]. Application Research of Computers, 2014, 31(8): 2399-2403.
[8] 李鑫. 基于神经网络的路径覆盖测试数据生成[D]. 北京:中国矿业大学, 2014. Li Xin. Test data generation for path coverage based on neural network[D]. Beijing: China University of Mining and Technology, 2014.
[9] 傅博. 基于蚁群算法的软件测试数据自动生成. 计算机工程与应用[J]. 2007, 43(12): 97-99. Fu Bo. Automated software test data generation based on ant colony algorithm[J]. Computer Engineering and Applications, 2007, 43(12): 97-99.
[10] 王博, 王曙燕. 一种新的基于模拟退火的测试用例生成与约简算法[J]. 计算机应用与软件, 2013, 30(2): 78-81. Wang Bo, Wang Shuyan. A novel method of test case generation and reduction algorithm based on simulated annealing[J]. Computer Applications and Software, 2013, 30(2): 78-81.
[11] Shah-Hosseini H. Problem solving by intelligent water drops[C]// Evolutionary Computation, 2007. IEEE Congress on Evolutionary Computation, 2007: 3226-3231.
[12] 单锦辉, 姜瑛, 孙萍. 软件测试研究进展[J]. 北京大学学报(自然科学版), 2005, 41(1): 134-145. Shan Jinhui, Jiang Ying, Sun Ping. Research Progress in Software Testing[J]. Acta Scicentiarum Naturalum Universitis Pekinesis, 2005, 41(1): 134-145.
[13] 王思岚. 单元测试中代码覆盖分析及路径选择技术的研究与应用[D]. 北京: 北京邮电大学, 2012. Wang Silan. Code coverage analysis and path selection technology research and application[D]. Beijing: Beijing University of Posts and Telecommunications, 2012.
[14] 姚辉萍, 赵雷, 李蓥, 等. 一种改进的计算控制依赖的算法[J]. 计算机应用与软件, 2010, 27(11): 13-15. Yao Huiping, Zhao Lei, Li Ying, et al. An improved algorithm for control dependency[J]. Computer Applications and Software, 2010, 27(11): 13-15.
[15] 巩敦卫, 张岩. 一种新的多路径覆盖测试数据进化生成方法[J]. 电子学报, 2010, 38(6): 1299-1304. Gong Dunwei, Zhang Yan. Novel evolutionary generation approach to test data for multiple paths coverage[J]. Acta Electronica Sinica, 2010, 38(6): 1299-1304.
阿里巴巴股价涨逾13%创新高 市值超3600亿美元
6月9日,阿里巴巴周五股价大涨13%,创下其上市以来的股价新高,市值达到3600亿美元。
昨日,阿里巴巴集团CEO在投资者大会上表示,2020年阿里GMV(交易总额)将达到一万亿美元。
阿里巴巴集团CFO武卫表示,预计该集团2018财年的营收将可同比增长45%到49%,这种乐观的展望在参加该集团杭州投资者日大会的人群中引起了一阵欢呼。据财经信息供应商FactSet的调查显示,截至5月31日为止华尔街分析师的平均预期是阿里巴巴集团2018财年的营收将同比增长36%,相比之下2017财年的营收增幅为47%。
截至周四收盘,阿里股价上涨16.7美元,报收于142.34美元,涨幅达13.29%,当日股价最高达143.7美元,创下上市以来新高。过去52周,其最低股价为73.3美元。
阿里巴巴股价的亮眼表现,还刺激其股东之一的雅虎公司股价创下17年来的新高。雅虎周四股价大涨10.2%,报收于55.71美元。
据雅虎最近提交的监管文件显示,截至今年3月31日为止,雅虎仍旧持有3.84亿股的阿里巴巴集团普通股;按阿里巴巴集团美国存托凭证当时的价格计算,这意味着雅虎所持该集团股份的价值高达414.1亿美元。
阿里巴巴集团在2014年9月19日IPO上市,目前其股价与当时每股68美元的发行价相比已经上涨了一倍以上。
自阿里巴巴集团IPO以来,雅虎股价与阿里巴巴集团美国存托凭证价格之间的相关系数高达0.896;如果这个系数达到1.000,则意味着两者之间的相关性达到完美匹配的水平。
据雅虎股东大会的初步结果显示,该公司股东已在周四批准了将核心互联网业务以44.8亿美元的价格出售给Verizon通信公司的交易。雅虎预计,这项交易将在2017年6月13日完成。
在过去的2017财年,阿里巴巴拿出了出色的成绩单,全年收入同比增长56%至1582.73亿元人民币。2017财年第四财季财报显示,当季度电商核心业务收入315.70亿元人民币,同比增长47%,移动电商平台贡献了中国零售平台季度收入的85%,中国零售平台年度活跃买家增至4.54亿,移动端月度活跃用户高达5.07亿。阿里巴巴平台的交易总额占中国零售总额的11%。
——转自互联网
Code coverage Testing Using Intelligent Water Drop Algorithms
MA Zhu-gen1, SHU Shao-hua2
(1. College of Computer Science and Technology, Huaihua University, Huaihua, 418008, China; 2. Huaihua Railway Primary School, Huaihua, 418000, China)
Code coverage is widely used in software testing, which describes the degree to which the code has been tested. This paper proposes a technique using Intelligent Water Drop (IWD) for automatic generation of test sequences, discusses algorithms based on IWD to generate independent path with weight over control dependency graph. It proposes how test cases can be considered as an IWD moving on the edges of the control dependency graph for finding the optimal paths. The independent path with weight and test sequence has been automatically generated so that testers can optimally arrange the test sequence to ensure complete code coverage.
Software testing; Control dependency graph; Code coverage; Independent path; Intelligent water drops algorithm
TP301.6
A
10.3969/j.issn.1003-6970.2017.05.005
湖南省教育厅项目(16C1276),武陵山片区生态农业智能控制湖南省重点实验室项目(ZNKZ2016-08)资助
马竹根(1971-),硕士,讲师。研究方向:人工智能、软件工程。
本文著录格式:马竹根,舒少华. 智能水滴算法在代码覆盖测试中的应用[J]. 软件,2017,38(5):22-26