基于文化粒子群算法的軟件缺陷定位方法

王憲勇 石建樹(shù)

摘要：自動(dòng)化軟件缺陷定位方法能夠在無(wú)人工干預(yù)下快速定位軟件中缺陷位置，但是不少缺陷定位方法存在定位準(zhǔn)確性低的問(wèn)題。為了提升軟件缺陷定位的準(zhǔn)確性，提出一種基于文化粒子群算法的軟件缺陷定位方法CAPSOFaL，該方法使用缺陷程序?qū)嶓w構(gòu)建算法種群，通過(guò)兩個(gè)進(jìn)化空間的協(xié)作得到最優(yōu)解，并通過(guò)分析最優(yōu)解得到測(cè)試程序內(nèi)的真實(shí)缺陷位置。該方法能夠減少冗余信息對(duì)實(shí)體懷疑值計(jì)算的干擾，并顯著提升真實(shí)缺陷位置在缺陷報(bào)告中的排名，進(jìn)而提升缺陷定位的準(zhǔn)確性。

關(guān)鍵詞：軟件測(cè)試;缺陷定位;文化算法;粒子群算法

中圖分類(lèi)號(hào)：TP311.5 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）31-0271-02

1概述

隨著軟件規(guī)模的不斷擴(kuò)大，軟件中包含的缺陷也越來(lái)越多，這些缺陷影響軟件的可靠性，甚至阻礙軟件的正常運(yùn)行，如何快速準(zhǔn)確地找到軟件中的缺陷位置，成為開(kāi)發(fā)維護(hù)人員關(guān)注的重點(diǎn)。傳統(tǒng)的人工調(diào)試消耗大量的時(shí)間和人力資源，而且隨著軟件規(guī)模的擴(kuò)大已經(jīng)力不從心。自動(dòng)化軟件缺陷定位方法的出現(xiàn)就是為了將開(kāi)發(fā)人員從繁重的調(diào)試中解放出來(lái)。在已有的自動(dòng)化軟件缺陷定位方法中，基于頻譜的缺陷定位方法（program Spectrum based Fault Localization，簡(jiǎn)稱(chēng)sFL）定位效果表現(xiàn)優(yōu)秀。該方法收集程序中每個(gè)實(shí)體的測(cè)試用例的執(zhí)行覆蓋情況，并與執(zhí)行結(jié)果一起構(gòu)成該程序的頻譜信息，通過(guò)統(tǒng)計(jì)計(jì)算頻譜信息得出實(shí)體的懷疑值，最后生成缺陷分析報(bào)告從而輔助開(kāi)發(fā)人員進(jìn)行缺陷定位和修復(fù)。圖1給出了SFL方法缺陷定位的流程。

在SFL方法中，Tarantula、Ochiai、Jaccard等方法因?yàn)閷?shí)現(xiàn)簡(jiǎn)單，定位效果較好而受到廣泛關(guān)注。這些方法可以計(jì)算并生成一個(gè)實(shí)體懷疑值的降序序列，該序列中位置越靠前的實(shí)體，越有可能是程序中的真實(shí)缺陷位置。但是在生成的序列中，排在序列前端的具有較高懷疑值的實(shí)體，往往是缺陷程序中被失敗測(cè)試用例和成功測(cè)試用例同時(shí)較多覆蓋的非缺陷實(shí)體。因此，提出一種基于文化粒子群算法的缺陷定位方法CAPSOFaL，該方法將缺陷程序中的每個(gè)實(shí)體作為一個(gè)懷疑元素，通過(guò)懷疑元素的不同組合來(lái)構(gòu)建個(gè)體，并在粒子群算法的基礎(chǔ)上增加信度空間，采用大小種群差速進(jìn)化、互相影響的方式，進(jìn)一步強(qiáng)化最優(yōu)個(gè)體對(duì)種群進(jìn)化的引導(dǎo)，從而減少冗余信息對(duì)實(shí)體懷疑序列構(gòu)建的干擾，提升真實(shí)缺陷位置在實(shí)體懷疑序列中的排名，并最終提升缺陷定位效果。

2文化粒子群算法

文化粒子群算法由兩部分構(gòu)成，一部分是粒子群算法，另一部分是根據(jù)文化算法的思想構(gòu)建的信度空間，下面將給出這兩種算法以及文化粒子群算法的具體描述。

2.1文化算法

文化算法（Cultural Algorithm，簡(jiǎn)稱(chēng)CA）是1994年Reynolds受到文化的進(jìn)化對(duì)人類(lèi)文明進(jìn)化的影響而提出的一種雙層進(jìn)化機(jī)制。該機(jī)制的創(chuàng)新之處在于，除了傳統(tǒng)的種群進(jìn)化空間之外，新添加了信度空間，將知識(shí)的概念融人種群的進(jìn)化中，從而加快了整個(gè)種群的進(jìn)化速度。文化算法的基本結(jié)構(gòu)將在圖2中給出。

信度空間由種群知識(shí)構(gòu)成，是文化算法的核心。種群知識(shí)是指種群中個(gè)體的進(jìn)化經(jīng)驗(yàn)與信息，這些知識(shí)可以分為五大類(lèi)：狀態(tài)知識(shí)、規(guī)范知識(shí)、地勢(shì)知識(shí)、領(lǐng)域知識(shí)和歷史知識(shí)。其中，狀態(tài)知識(shí)和規(guī)范知識(shí)較為重要，狀態(tài)知識(shí)反映了種群進(jìn)化的線性過(guò)程，規(guī)范知識(shí)反映了種群隨著進(jìn)化的加深其搜索空間的不斷變化。信度空間的構(gòu)建主要通過(guò)接受函數(shù)從原始種群進(jìn)行選拔，滿足條件的個(gè)體才會(huì)被允許進(jìn)入信度空間。而信度空間產(chǎn)生的知識(shí)將通過(guò)影響函數(shù)對(duì)原始種群的進(jìn)化進(jìn)行引導(dǎo)。接受函數(shù)和影響函數(shù)的形式將在下面給出。

2.2粒子群算法

粒子群算法（Particle Swarm Optimization，簡(jiǎn)稱(chēng)PSO），也稱(chēng)為粒子群優(yōu)化算法，是一種模擬鳥(niǎo)群覓食行為的群體智能優(yōu)化算法。該方法通過(guò)模擬龐大的鳥(niǎo)群在一定范圍內(nèi)搜索未知位置的食物的行為，來(lái)得到待解決問(wèn)題的最優(yōu)解。在粒子群算法中，鳥(niǎo)群對(duì)應(yīng)算法的種群，鳥(niǎo)群的搜索范圍對(duì)應(yīng)問(wèn)題的解空間，也就是算法的搜索空間，鳥(niǎo)群的搜索行為對(duì)應(yīng)種群的進(jìn)化，未知食物位置搜索對(duì)應(yīng)搜索問(wèn)題的最優(yōu)解。算法的搜索過(guò)程可以描述為：將問(wèn)題的解空間作為算法的搜索空間，將問(wèn)題的每個(gè)可能解映射為一個(gè)粒子位置，通過(guò)適應(yīng)度函數(shù)的控制，使得種群中的個(gè)體向最優(yōu)個(gè)體的位置靠近，算法進(jìn)化終止后種群內(nèi)適應(yīng)度函數(shù)值最高的粒子位置，即為當(dāng)前問(wèn)題的最優(yōu)解。粒子群算法中最重要的步驟就是個(gè)體的速度及位置更新，下面將在公式（3）（4）（5）中給出具體形態(tài)。

2.3文化粒子群算法

文化粒子群算法結(jié)合粒子群算法和文化算法的優(yōu)勢(shì)，在原始種群進(jìn)化空間的基礎(chǔ)上，增加信度空間，在接受函數(shù)的控制下形成小規(guī)模的最優(yōu)種群，通過(guò)加速進(jìn)化的方式，獲得原始種群下一步的進(jìn)化方向，并通過(guò)影響函數(shù)引導(dǎo)原始種群的進(jìn)化，并最終提升整體進(jìn)化速度。在種群的構(gòu)建上，給缺陷程序中的每個(gè)實(shí)體賦上唯一的編號(hào)并作為一個(gè)懷疑元素，將固定長(zhǎng)度的隨機(jī)懷疑元素的組合作為粒子，算法結(jié)束時(shí)產(chǎn)生的最優(yōu)粒子位置即為缺陷程序的實(shí)體懷疑序列。粒子的形態(tài)為：

{9，5，6，8，7，4，1，3，2}

示例中假設(shè)缺陷程序內(nèi)包含9個(gè)實(shí)體，每一個(gè)數(shù)字唯一標(biāo)識(shí)一個(gè)實(shí)體，紅色標(biāo)識(shí)的數(shù)字表示假設(shè)的缺陷位置。為了正確評(píng)價(jià)這種特殊形態(tài)的粒子，適應(yīng)度函數(shù)設(shè)計(jì)為兩種相似性的比值，其中一種相似性為失敗相似性，它表示一個(gè)粒子中包含失敗執(zhí)行軌跡中元素的數(shù)量，同理，成功相似性為粒子中包含成功軌跡中元素的數(shù)量。適應(yīng)度函數(shù)的形態(tài)將在公式4中給出。

通過(guò)新生成的粒子位置{9，5，6，8，6，7，3，4，}可以看到，假設(shè)的缺陷位置已經(jīng)挪動(dòng)到了序列的前端。在序列中元素6出現(xiàn)了兩次，原因是示例中粒子位置的移動(dòng)只受到gtest的影響而缺少pbest的影響，在實(shí)際的進(jìn)化情況，粒子位置的移動(dòng)不會(huì)只受一種最優(yōu)位置的影響，所以懷疑元素重復(fù)出現(xiàn)的情況不會(huì)發(fā)生。最終，進(jìn)化完成的算法將產(chǎn)生一個(gè)最優(yōu)粒子位置，假設(shè)最優(yōu)粒子位置為：{5，8，9，6，7，3，4，1，2}，則生成的缺陷位置報(bào)告為：

3結(jié)論

本文提出的基于文化粒子群算法的軟件缺陷定位方法CAPSOFaL，能夠提升真實(shí)缺陷位置在缺陷報(bào)告中的排名，提高了缺陷定位的準(zhǔn)確性，減少了開(kāi)發(fā)人員搜尋缺陷位置的工作量。下一步將在縮減方法時(shí)間復(fù)雜度的情況下進(jìn)一步提升缺陷定位的精確度。