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

王憲勇 石建樹

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

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

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

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

1概述

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

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

2文化粒子群算法

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

2.1文化算法

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

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

2.2粒子群算法

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

2.3文化粒子群算法

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

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

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

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

3結論

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