[發明專利]一種基于概率對齊的代碼錯誤定位方法

有效

• 申請號: 202010576945.3
• 申請日: 2020-06-23
• 公開（公告）號: CN111737131B
• 公開（公告）日: 2023-08-08
• 發明（設計）人: 許蕾;王智楷;劉翔宇;田曉濱;王瀚霖;顏同路
• 申請（專利權）人: 南京大學
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06F16/35
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于概率對齊的代碼錯誤定位方法，其特征是通過LLVM(LoW?Level?VirtualMachine)工具對源代碼進行優化，提取出程序的符號信息并跟蹤執行流程，再根據提取的信息，對程序實例進行分類存儲，構建代碼結構和符號執行流，之后對代碼實例進行序列對齊，并在此基礎上進行概率對齊，最后根據兩個程序的關鍵實例和對齊結果切片，進行二次對齊，關注應該匹配但沒有匹配的實例，從而定位錯誤；其包括以下幾個步驟：

1)使用LLVM工具將測試代碼轉化為語言無關的中間代碼，并使用Pass對中間代碼進行處理，得到源程序的符號信息和執行信息；

2)分析得到的源程序信息，對指令類型進行分類存儲，構建程序結構；

3)對傳入實例進行序列對齊，加載符號執行信息文件中的內容，將正確版本與錯誤版本的切片兩兩匹配，每次匹配會根據當前兩項迭代次數與執行次序進行一次描述匹配概率的評分，具體評分規則為迭代次數與執行次數的差越小，分數就越高，在初始賦值結束后，依照匹配規則整合匹配情況，將記錄為“匹配”的對應項記錄到序列對齊中，得到最初的序列對齊；再進行概率對齊，將初始對齊中由于缺少依賴信息而發生的對齊項刪去，得到更準確的對齊結果，即再次遍歷初始序列對齊中的所有匹配項并賦概率初值，判斷對齊兩項的距離與閾值的關系，擴展對齊序列；最后根據概率規則，計算每組對齊序列的匹配可能性，將結果分別加上一定的權值，作為匹配準確性的結果，比較結果與設置的閾值，如果超過閾值則記入新的對齊序列中，多次執行后得到基于概率的匹配序列；

4)在概率對齊后的兩個程序的實例序列中查找兩程序不同的PRINT實例并進行分析，得到兩個程序的關鍵實例；通過對齊中得到的各自的關鍵實例分別制作切片，得到程序中與關鍵實例相關的實例；最后對切片進行第二次對齊，可得到兩個程序的新切片，即應匹配但未匹配的實例序列，同時得到新的對齊結果，將錯誤程序的代碼進行每行打印，并將包含切片實例的代碼標注錯誤信息，同時打印符號表達式的值。

2.根據權利要求1所述的一種基于概率對齊的代碼錯誤定位方法，其特征是步驟2)中，還原并存儲源程序的結構及執行信息，讀入LLVM的Pass處理后得到的輸出文件；首先根據代碼實例的類型進行分類存儲，構建代碼結構，每一個實例都有唯一的id標識；然后讀入程序的執行信息，根據id對應的相應代碼進行處理，記錄執行順序，記錄到符號執行信息文件中。