[發明專利]一種基于條件概率的程序錯誤定位方法

在審

• 申請號: 201611052266.6
• 申請日: 2016-11-24
• 公開（公告）號: CN106776283A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 舒挺;黃明獻;王磊
• 申請（專利權）人: 浙江理工大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 杭州天勤知識產權代理有限公司33224
• 代理人: 胡紅娟

技術領域

本發明屬于軟件程序錯誤定位檢測技術領域，具體涉及一種基于條件概率的程序錯誤定位方法。

背景技術

軟件規模和復雜程度的與日俱增給軟件開發和調試技術帶來了極大的挑戰，面對軟件開發過程中如影相隨的軟件缺陷問題，軟件測試是提升其質量和可靠性的重要技術手段。因此，人們在軟件測試方面的投入逐年不斷增加，軟件測試過程中，當發生被測軟件的行為與預期不一致(即失效)時，開發人員就需要隨即開展軟件調試.軟件調試的首要任務是缺陷定位，它為后續錯誤代碼修復工作提供了基礎。

缺陷定位旨在探測和查找引起軟件失效的錯誤代碼，是一項非常枯燥和耗時的活動。傳統的手工設置斷點的調試方法，不僅斷點位置選擇困難，且時間開銷巨大；因此，實現缺陷定位的自動化成為了軟件學術界和工業界共同追求的目標。目前自動化的缺陷定位方法尚未成熟，仍是軟件工程領域的研究熱點，近些年來，研究人員從不同的角度嘗試提出了一系列缺陷定位方法，包括基于切片的錯誤定位方法、基于不變量的錯誤定位方法、模型檢驗方法和基于程序頻譜的錯誤定位方法等。基于切片的錯誤定位方法主要通過對程序的靜態或動態分析，找出與給定變量相關聯的語句，從而縮小錯誤查找范圍。基于不變量的錯誤定位，則通過利用成功和失效測試例不變量之間的差異信息，從而輔助定位錯誤語句。模型檢驗方法則利用失效程序行為與期望模型行為的沖突來推導程序錯誤。相比而言，基于頻譜的缺陷定位方法(Spectrum-based Fault Localization，SFL)由于不需要考慮程序本身結構，執行開銷小，成為了一種當前比較行之有效的重要方法。

程序頻譜通常指程序運行時代碼覆蓋信息的集合，是程序動態行為特征的一種描述形式。由于程序運行失效時，必定至少執行到了某條錯誤語句，據此，可以得出經驗性的推斷：當某條語句被更多的失效執行所覆蓋，那么它為錯誤語句的可能性就越高。因此，通過收集程序的頻譜和執行結果兩方面的信息來推導出程序缺陷位置成為了可能。具體的，SFL方法主要通過對比分析被測程序在成功執行和失效執行的程序頻譜信息，構造相應的可疑度計算公式來估測程序元素(如語句，謂詞等)出錯的可能性，最終調試人員將程序元素按照可疑度大小降序逐一排查錯誤。因此，可疑度值輔助缺陷定位的精確程度成為了衡量SFL方法優劣的主要性能指標。

程序頻譜和執行結果之間存在的潛在關聯是可疑度計算公式構造的基礎，顯然，充分地挖掘和利用這種潛在關聯蘊含的缺陷揭示信息，有助于提升可疑度計算公式缺陷定位的效用。

發明內容

鑒于上述，本發明提供了一種基于條件概率的程序錯誤定位方法，通過經驗性研究程序頻譜和執行結果兩者之間的內在關聯，引入統計學的條件概率思想，構建了用以量化分析兩者關系強弱評估的P模型，從而提出相應的可疑度計算公式，具有更好的缺陷定位效果。

一種基于條件概率的程序錯誤定位方法，包括如下步驟：

(1)統計軟件程序中各條語句在每組測試用例下的語句覆蓋情況，得到對應的語句覆蓋矩陣；

(2)統計每組測試用例在軟件程序運行下的執行結果：正確或錯誤；

(3)對于軟件程序中的任一條語句s，構建由概率P_fe、P_ef、P_te、P_et和P_tn所組成的條件概率模型；其中，P_fe表示在執行語句s的情況下軟件程序運行結果為失敗的概率，P_ef表示在軟件程序運行結果為失敗的情況下執行語句s的概率，P_te表示在執行語句s的情況下軟件程序運行結果為成功的概率，P_et表示在軟件程序運行結果為成功的情況下執行語句s的概率，P_tn表示在不執行語句s的情況下軟件程序運行結果為成功的概率；

(4)根據所述的條件概率模型計算語句s的錯誤可疑度并依此遍歷軟件程序中的所有語句；進而根據所述的錯誤可疑度從高到低對軟件程序中的語句進行排序并逐條進行錯誤排查。

所述語句覆蓋情況的定義為：以某一測試用例作為軟件程序的輸入，若軟件程序對于該測試用例的整個運行過程中執行了某一條語句，則該語句在該測試用例下的語句覆蓋情況表示為1，否則表示為0。

所述語句覆蓋矩陣的維度為m×n，m為軟件程序中的語句總數，n為測試用例總數；該矩陣中第i行第j列的元素值為第i條語句在第j組測試用例下的語句覆蓋情況，i和j均為自然數且1≤i≤m，1≤j≤n。