[發明專利]一種基于蟻群算法的軟件缺陷定位方法及裝置

有效

• 申請號: 201910041810.4
• 申請日: 2019-01-16
• 公開（公告）號: CN111444078B
• 公開（公告）日: 2023-02-07
• 發明（設計）人: 曹鶴玲;鄧淼磊;王憲勇;苗建雨;費選;靳小波;宋炯炯;薛正元;許德剛;趙玉娟;楊靜;徐振強
• 申請（專利權）人: 河南工業大學
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06N3/006
• 代理公司: 鄭州睿信知識產權代理有限公司 41119
• 代理人: 吳敏

1.一種基于蟻群算法的軟件缺陷定位方法，其特征在于，包括以下步驟：

構建蟻群搜索圖，該蟻群搜索圖包括N層，N等于缺陷程序的可執行語句數，每層設置有兩個節點，一個節點表示執行對應的可執行語句，另一個節點表示不執行對應的可執行語句，且每一層中的每個節點與該層下一層中的每個節點均連通；

初始化蟻群搜索圖中所有路徑的信息素濃度；

構造用于揭示缺陷分布能力的適應度函數，所述適應度函數FitOchiai(C)為：FitOchiai(C)＝σ(C)×(T_f×(σ(C)+ψ(C)))^-1/2，其中，C代表路徑，T_f代表失敗測試數據的數量，σ(C)代表路徑C與失敗測試數據執行軌跡的重合度，ψ(C)代表路徑C與成功測試數據執行軌跡的重合度；

將M只螞蟻置于所述蟻群搜索圖的第一層的其中一個節點位置處，進行搜索，根據當前節點與下一層兩個節點之間的信息素濃度，選擇信息素濃度較高的路徑對應的節點，在移動之后通過調整局部信息素揮發系數來更新該路徑上的信息素濃度，在M只螞蟻完成對所有層的搜索之后，形成M條長度為N的路徑，利用所述適應度函數分別計算這M條路徑的適應度值，并根據M條路徑的適應度值選取當前最優路徑集；判斷是否滿足迭代終止條件，若不滿足迭代終止條件，則通過調整全局信息素揮發系數來更新當前最優路徑集中各最優路徑上的信息素濃度，并進行下一輪的搜索，直至滿足迭代終止條件，得到最終最優路徑集；其中，所述滿足迭代終止條件為達到設定的迭代次數；

統計最終最優路徑集中各最優路徑中的可執行語句出現的次數，選取次數大于設定次數的可執行語句作為缺陷語句。

2.根據權利要求1所述的基于蟻群算法的軟件缺陷定位方法，其特征在于，所述在移動之后通過調整局部信息素揮發系數來更新該路徑上的信息素濃度，對應的信息素濃度更新公式為：τ(V_k,V_k+1)＝ατ(V_k,V_k+1)+(1-α)τ₀，其中，τ(V_k,V_k+1)為路徑(k,k+1)上的信息素濃度，α為局部信息素揮發系數，τ₀為路徑初始信息素濃度。

3.根據權利要求1所述的基于蟻群算法的軟件缺陷定位方法，其特征在于，所述通過調整全局信息素揮發系數來更新當前最優路徑集中各最優路徑上的信息素濃度，對應的信息素濃度更新公式為：τ(V_k,V_k+1)＝ρτ(V_k,V_k+1)+(1-ρ)Δτ(V_k,V_k+1)，其中，τ(V_k,V_k+1)為路徑(k,k+1)上的信息素濃度，ρ為全局信息素揮發系數，Δτ(V_k,V_k+1)為路徑(k,k+1)上信息素濃度的增量，Δτ(V_k,V_k+1)＝1/H_opt，H_opt為當前最優路徑的適應度值。

4.根據權利要求1所述的基于蟻群算法的軟件缺陷定位方法，其特征在于，在不滿足迭代終止條件時，若連續設定輪次得到的最優路徑集中各最優路徑的適應度值均沒有增大，則降低局部信息素揮發系數和全局信息素揮發系數，并重新進行下一輪搜索。