[發明專利]一種基于聚類不變式分析的錯誤定位方法

無效

• 申請號: 201110413498.0
• 申請日: 2011-12-13
• 公開（公告）號: CN102521130A
• 公開（公告）日: 2012-06-27
• 發明（設計）人: 陳林;吳迪;許蕾;徐寶文
• 申請（專利權）人: 南京大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 南京天翼專利代理有限責任公司 32112
• 代理人: 黃明哲

1.一種基于聚類不變式分析的錯誤定位方法，其特征是收集程序執行過程中的語句頻譜信息，計算各執行語句之間的距離，對程序執行的語句頻譜信息進行聚類分析，將程序執行空間劃分為多個類簇，對各個類簇分別計算與程序變量相關的不變式，執行新的測試用例，根據新的執行所對應的程序語句頻譜將其劃分至對應的類簇中，比較該測試用例執行結果與類簇中已有的不變式，如果新的執行違反了已有的不變式，則認為該次執行為一次錯誤執行，根據類簇信息完成錯誤定位。

2.根據權利要求1所述的一種基于聚類不變式分析的錯誤定位方法，其具體步驟如下：

1)按照程序執行的語句頻譜信息對所有執行進行聚類劃分，每個語句塊的頻譜作為聚類的數據對象，設共有n個數據對象，聚為k類：

11)計算任意兩個測試用例的歐拉距離d(x，y)，并由所有計算得到的距離構造集合U，由集合U中距離最近的兩個數據對象形成集合A_m，并從集合U中刪除這兩個對象，A_m即為將要形成的聚類，其中m為集合下標，用于標識不同的聚類，初始為1；

12)在集合U中找到距離集合A_m最近的數據對象，將其加入集合A_m，并從集合U中刪除該對象；

13)重復步驟12)直到集合中的數據對象個數大于等于n/k；

14)如果m＜k，則m←m+1，再從集合U中找到距離最近的兩個數據對象，構成集合A_m，并從集合U中刪除這兩個數據對象，返回步驟12)執行；

15)將最終形成的k個集合中的數據對象分別進行算術平均，形成k個聚類中心；

2)根據聚類結果劃分程序執行空間為多個類簇，對劃分得到的各個類簇分別計算與程序變量相關的不變式，所述不變式包括：

21)這個變量第一次執行通過一條賦值表達式后的值；

22)為這個變量維護的一個不變式向量V，V中包含三個分量：第一個分量表示每次執行時這個變量的值與第一次被賦的值是否相同，相同取1，不同取0；第二個分量表示每次執行時這個變量的值是否與第一次被賦的值有相同的正負性，相同取1，不同取0；第三個分量表示每次執行時這個變量是否與第一次執行有相同的奇偶性，相同取1，不同取0；

23)這個變量最小上限值，若某次執行時該變量被賦的值大于這個最小上限，則將最小上限記為這個值；

24)這個變量的最大下限值，若某次執行時該變量被賦的值小于這個最大下限，則將最大下限記為這個值；

25)這個變量被賦值的次數；

26)這個變量的名字、其所在函數的名字及所在基本塊的名字；

3)運行新的測試用例，收集新的執行所對應的語句頻譜，根據聚類分析判斷其所在的聚類類簇，對比該執行與其所在類簇的不變式，若產生錯誤，則判定此次執行出錯，然后根據類簇的位置實現錯誤定位。