馬竹根，舒少華

(1. 懷化學院計算機科學與工程學院，湖南 懷化 418008；2. 懷化市鐵路第一小學，湖南 懷化 418000)

智能水滴算法在代碼覆蓋測試中的應用

馬竹根1，舒少華2

(1. 懷化學院計算機科學與工程學院，湖南 懷化 418008；2. 懷化市鐵路第一小學，湖南 懷化 418000)

代碼覆蓋在軟件測試中得到了廣泛應用，表示了代碼被測試的程度。論文提出了一種利用智能水滴算法優(yōu)化代碼覆蓋的算法，描述了如何把獨立路徑生成問題轉換成智能水滴在控制依賴圖的各邊之間尋找最優(yōu)路徑的問題，通過生成帶有權值的獨立路徑來自動生成測試序列，使得測試人員可以最優(yōu)地安排測試順序，保證充分的代碼覆蓋。

軟件測試；控制依賴圖；代碼覆蓋；獨立路徑；智能水滴算法

0 引言

軟件測試分為黑盒測試和白盒測試。白盒測試的充分性準則中，覆蓋測試[1]可以針對不同的覆蓋測試標準，以覆蓋元素是否己經(jīng)達到覆蓋要求判斷測試的充分性，其中，路徑覆蓋是最重要的一種覆蓋測試[2]。生成測試用例[3]往往需要耗費大量的時間，軟件自動化測試[4-5]將有效地減輕測試人員的負擔，提高軟件測試的效率和軟件質(zhì)量。近年來，研究人員開始使用粒子群優(yōu)化算法[6]、蜂群算法[7]、神經(jīng)網(wǎng)絡[8]、蟻群算法[9]、模擬退火算法[10]等智能優(yōu)化算法來解決軟件測試中的測試用例的生成問題。

智能水滴算法[11]（Intelligent Water Drops algorithms，IWD）是在2007年提出的一種群智能算法，模擬了天然水滴在河流系統(tǒng)中流動的過程，使用一種構造性的方法來構建給定問題的最優(yōu)解，每個水滴通過遍歷給定問題的搜索空間找到最佳路徑，然后修改其流動的環(huán)境。智能水滴算法已經(jīng)應用于許多自然科學與工程領域，顯示出算法的強大的優(yōu)勢和潛力。

控制流程圖（control flow graph，CFG）是程序的圖形表示，控制流圖可轉換為控制依賴圖（control dependency graph，CDG）。路徑覆蓋測試數(shù)據(jù)生成問題可描述為：給定程序的一條目標路徑，在程序的輸入空間尋找測試數(shù)據(jù)，使得以該測試數(shù)據(jù)為輸入所穿越的路徑為目標路徑[12]。路徑選擇是覆蓋測試中的十分重要的步驟，目標覆蓋元素的選取以及初始路徑的選擇都依賴于控制流圖上的依賴關系[13]。智能水滴算法是一種基于圖的算法，因此智能水滴算法可以用于測試路徑選擇，使用智能水滴算法生成所有可能的測試序列用于計算代碼覆蓋率，使用所提出的算法計算測試用例能夠遍歷的所有可能路徑及其相應的權值。本文提出了一種使用智能水滴算法優(yōu)化技術生成自動測試序列的算法，為代碼覆蓋測試問題提供了一種新的解決方案。算法中應用控制依賴圖（control dependency graph，CDG）作為算法的輸入。

1 控制依賴圖

定義1 令S是一個源程序，s1和s2是S中的語句。s2是控制依賴于s1，當且僅當滿足下列條件[14]：

（1）s1和s2之間存在一條路徑；

（2）存在一條執(zhí)行路徑從s1到程序結束但不經(jīng)過s2。

定義2 控制依賴圖CDG（control dependency graph）是一個有向圖G=(V, E)，其中結點V表示程序中的語句，E表示邊。邊s1→s2表示從結點s1到s2的控制依賴。G中有一個特殊的源結點，表示程序的開始，它可以到達圖中的每個結點。

從上面的定義可以看出，控制依賴在程序中主要由條件語句和循環(huán)語句構成。條件語句中的條件判斷與對應的語句體之間存在控制依賴關系，循環(huán)條件判斷和循環(huán)體之間存在控制依賴?？刂埔蕾噲D中的節(jié)點表示語句，邊表示它們之間的控制依賴關系。

2 智能水滴算法介紹

智能水滴[11]（Intelligent Water Drop，IWD），它具有以下兩個重要的屬性：水滴攜帶的泥土量soil（IWD）和水滴的速度velocity（IWD），當水滴從一個位置移動到下一個位置時，這兩個屬性會隨著水滴流動而發(fā)生改變。水滴的速度非線性反比于路徑上的泥土量。通過從路徑中移除一些泥土來增加IWD的泥土，并且增加的泥土量是非線性反比于在不同位置之間移動所花費的時間。智能水滴移動的時間正比于不同位置之間的距離，反比于水滴的移動速度。智能水滴在遇到多條路徑可選時，會更傾向于選擇泥土量較少的路徑。對于智能水滴可能選擇的下一個位置，通過計算隨機分布函數(shù)來實現(xiàn)，使得選擇路徑的概率與可用路徑的土壤成反比。

3 算法設計

3.1 適應度函數(shù)

要使用智能水滴算法解決路徑覆蓋問題，需要把該問題建模為一個函數(shù)優(yōu)化問題，適應度函數(shù)的建立是關鍵，常用的適應度函數(shù)通常包括層接近度和分支距離[15]。設計適應度函數(shù)用來計算控制依賴圖中的泥土量，基本思想是讓更深更復雜的路徑權值更大。構造良好的適應度函數(shù)可以增加找到求解方案和達到更高覆蓋的機會，算法中使用的適應度函數(shù)如下：

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的下層結點數(shù)。智能水滴從圖的源結點出發(fā)，使用適應度函數(shù)計算每一條路徑的選擇概率，概率大的路徑認為是水滴選擇的路徑。參數(shù)a和b分別賦值為常量2和1，這樣賦值的原因是給那些子結點多的結點分配更高的權值。

如果subgraph(j)和condition(j)等于0，那么soil (i, j) =1。這是因為soil(I, j)將會用來計算對應節(jié)點的概率，并且要求概率不能為零。這樣選擇適應度函數(shù)是因為在任一判斷節(jié)點或更復雜的路徑中都可能產(chǎn)生錯誤。

3.2 算法步驟

步驟1：初始化參數(shù)

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 //速度更新參數(shù)。

as=1， bs= 1， cs=1 //泥土更新參數(shù)。

ρ=0.1 // 局部更新參數(shù)，0≤ρ≤1，依賴于結點上泥土量的多少

Init_Vel =200 //初始化IWD的速度為200

Vc (IWD) = {} // IWD遍歷路徑Vc (IWD)，/初始值為空。

步驟2：更新參數(shù)的值

（1）while（CDG不為空）

（2）計算概率

按以下公式計算出從當前結點i出發(fā)選擇結點j的概率。

P(i,j)=soil(i,j)/Σk ≠vcSoil(i,k)

soil(i,j)表示結點之間的泥土量，Σk ≠vcSoil(i,k)表示能從當前結點i遍歷的路徑上的泥土的總和。在原算法中，IWD朝泥土量少的路徑移動，因為我們要測試更復雜的程序來發(fā)現(xiàn)錯誤，因此在算法中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是由用戶選定的正數(shù)。

（5）計算IWD的速度

vel(i, j, iwd) = vel(iwd) + (av/ (bv+ cvsoil(i, j)))

av，bv，cv是由用戶選定的正數(shù)，soil(i, j)是結點i到結點j的路徑上的泥土量。

（6）計算路徑上的泥土量

Soil (i, j) = (1 - ρ) soil (i, j) - ρ * Δsoil (i, j, iwd)

ρ=0.1,是一個正的參數(shù)，Δsoil (i, j, iwd)是IWD從結點i到結點j帶走的泥土量。

（7）重復步驟（2）-（6）直到遇到終端結點（葉子結點）或者是已遍歷結點。到達終端結點后，刪除該結點，同時檢查該節(jié)點的父節(jié)點，如果所有的葉子結點被刪除了，則將該結點刪除。

（8）完成一條可能路徑后更新遍歷路徑列表，重復執(zhí)行步驟2，開始新一輪的迭代。如果CDG為空了，就意味著所有的路徑已經(jīng)遍歷完成，結束循環(huán)。

通過這種方式可以找出所有可能的路徑，而且每條路徑帶有相應的權值，路徑測試順序的優(yōu)先級可直接對應路徑的權值，權值高的路徑優(yōu)先測試。

4 實例驗證

以數(shù)據(jù)結構中熟知的二分查找算法為例說明IWD的執(zhí)行過程。二分查找算法C++源程序如圖1所示，其對應的控制依賴圖如圖2所示。

算法步驟：

首先計算每個結點的子節(jié)點的個數(shù)，通過深度優(yōu)先遍歷可得到每個結點的子節(jié)點數(shù)。結點的子節(jié)點數(shù)如下：

A=8，C=6，D=3，E，I，F(xiàn)，G，H的子節(jié)點數(shù)為0。

檢查結點的判斷條件值，A、C、D結點是判定節(jié)點，condition =1，其余結點condition=0。

IWD的迭代過程如下：

第1次迭代：

IWD從結點A開始，有兩條可選路徑J和C，為了確定下一個遍歷結點，計算兩個節(jié)點的選擇概率。根據(jù)3.1節(jié)適應度函數(shù)公式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，根據(jù)3.1節(jié)適應度計算公式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所示。

通過智能水滴算法得到了所有可能的帶有優(yōu)先級的獨立路徑，每一條路徑的權值是路徑上的泥土量的總和，權值越高的路徑優(yōu)先級越高，優(yōu)先級可以幫助測試者決定路徑的測試順序，對于測試人員來說是很有用處的。

表1 路徑及權值表Table 1 Path and weight

5 結論

測試用例的生成是軟件測試的重要內(nèi)容，高效的軟件測試用例自動生成方法可以簡化軟件測試過程，減少軟件測試成本，提高軟件測試效率和測試質(zhì)量，軟件測試面對的一個主要問題就是要自動生成測試數(shù)據(jù)實現(xiàn)充分的測試覆蓋。本文提出了一種使用智能水滴算法自動生成軟件測試順序的策略，算法的輸出結果包括所有可能的獨立路徑和路徑的權值，可用來分析代碼覆蓋率，幫助軟件測試人員確定軟件測試順序。下一步的工作中可將算法中的隨機選擇改用其他啟發(fā)式算法代替來提高算法的效率。

[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] 姚香娟, 鞏敦衛(wèi), 李彬. 融入神經(jīng)網(wǎng)絡的路徑覆蓋測試數(shù)據(jù)進化生成[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技術的軟件自動化測試的研究與實現(xiàn)[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] 姜淑娟, 王令賽, 薛猛, 等. 基于模式組合的粒子群優(yōu)化測試用例生成方法[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] 李云瑋, 孫忱, 范玉順. 基于智能非信息素蜂群優(yōu)化的軟件測試研究[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] 李鑫. 基于神經(jīng)網(wǎng)絡的路徑覆蓋測試數(shù)據(jù)生成[D]. 北京:中國礦業(yè)大學, 2014. Li Xin. Test data generation for path coverage based on neural network[D]. Beijing: China University of Mining and Technology, 2014.

[9] 傅博. 基于蟻群算法的軟件測試數(shù)據(jù)自動生成. 計算機工程與應用[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] 鞏敦衛(wèi), 張巖. 一種新的多路徑覆蓋測試數(shù)據(jù)進化生成方法[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%創(chuàng)新高 市值超3600億美元

6月9日，阿里巴巴周五股價大漲13%，創(chuàng)下其上市以來的股價新高，市值達到3600億美元。

昨日，阿里巴巴集團CEO在投資者大會上表示，2020年阿里GMV(交易總額)將達到一萬億美元。

阿里巴巴集團CFO武衛(wèi)表示，預計該集團2018財年的營收將可同比增長45%到49%，這種樂觀的展望在參加該集團杭州投資者日大會的人群中引起了一陣歡呼。據(jù)財經(jīng)信息供應商FactSet的調(diào)查顯示，截至5月31日為止華爾街分析師的平均預期是阿里巴巴集團2018財年的營收將同比增長36%，相比之下2017財年的營收增幅為47%。

截至周四收盤，阿里股價上漲16.7美元，報收于142.34美元，漲幅達13.29%，當日股價最高達143.7美元，創(chuàng)下上市以來新高。過去52周，其最低股價為73.3美元。

阿里巴巴股價的亮眼表現(xiàn)，還刺激其股東之一的雅虎公司股價創(chuàng)下17年來的新高。雅虎周四股價大漲10.2%，報收于55.71美元。

據(jù)雅虎最近提交的監(jiān)管文件顯示，截至今年3月31日為止，雅虎仍舊持有3.84億股的阿里巴巴集團普通股；按阿里巴巴集團美國存托憑證當時的價格計算，這意味著雅虎所持該集團股份的價值高達414.1億美元。

阿里巴巴集團在2014年9月19日IPO上市，目前其股價與當時每股68美元的發(fā)行價相比已經(jīng)上漲了一倍以上。

自阿里巴巴集團IPO以來，雅虎股價與阿里巴巴集團美國存托憑證價格之間的相關系數(shù)高達0.896;如果這個系數(shù)達到1.000，則意味著兩者之間的相關性達到完美匹配的水平。

據(jù)雅虎股東大會的初步結果顯示，該公司股東已在周四批準了將核心互聯(lián)網(wǎng)業(yè)務以44.8億美元的價格出售給Verizon通信公司的交易。雅虎預計，這項交易將在2017年6月13日完成。

在過去的2017財年，阿里巴巴拿出了出色的成績單，全年收入同比增長56%至1582.73億元人民幣。2017財年第四財季財報顯示，當季度電商核心業(yè)務收入315.70億元人民幣，同比增長47%，移動電商平臺貢獻了中國零售平臺季度收入的85%，中國零售平臺年度活躍買家增至4.54億，移動端月度活躍用戶高達5.07億。阿里巴巴平臺的交易總額占中國零售總額的11%。

——轉自互聯(lián)網(wǎng)

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)，武陵山片區(qū)生態(tài)農(nóng)業(yè)智能控制湖南省重點實驗室項目(ZNKZ2016-08)資助

馬竹根(1971-)，碩士，講師。研究方向：人工智能、軟件工程。

本文著錄格式：馬竹根，舒少華. 智能水滴算法在代碼覆蓋測試中的應用[J]. 軟件，2017，38（5）：22-26