王憲勇 石建樹

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

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

中圖分類號：TP311.5 文獻標識碼：A

文章編號：1009-3044（2019）31-0271-02

1概述

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

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

2文化粒子群算法

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

2.1文化算法

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

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

2.2粒子群算法

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

2.3文化粒子群算法

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

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

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

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

3結(jié)論

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