[發明專利]基于啟發式規則的并發式自適應隨機測試方法

有效

• 申請號: 202110674680.5
• 申請日: 2021-06-17
• 公開（公告）號: CN113468047B
• 公開（公告）日: 2022-05-17
• 發明（設計）人: 沐燕舟;王贊;劉爽
• 申請（專利權）人: 天津大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 李素蘭

1.一種基于啟發式規則的自適應隨機并發測試方法，其特征在于，該方法包括以下步驟：

步驟1、隨機執行待測試并發程序，作為本流程的輸入：首先隨機執行一次待測程序，得到結果；如果本次執行已經觸發了程序中包含的錯誤，則直接將檢測到的錯誤信息輸出，退出運行；否則，將本次隨機運行成功的程序調度路徑的信息且包含的內存訪問模式記錄下來存儲在集合T中，作為積累信息，為之后的搜索檢測提供指導來矯正之后的檢測方向；

步驟2、從初始狀態開始探索程序狀態空間，具體處理包括：隨機執行完待測程序沒有遇到錯誤后，重新回到程序狀態空間的最初始狀態，從上往下重新探索程序的狀態空間；每次探索首先獲取到待測試并發程序當前狀態下所有可行的直接子狀態，將其全部存入隊列Q中，然后計算隊列Q中所有子狀態和目前探索過的并行程序狀態組成的調度路徑與隊列T中已經探索過的程序調度路徑的距離度量；接下來，將隊列Q按降序排序，選出隊首元素即與集合T相比距離最大的子狀態出隊列，然后繼續執行；如果排序之后的隊列Q中的隊首元素的距離度量和第二個元素取值一樣，則認為此次排序無效，進入啟發式規則排序階段；

計算基于內存訪問模式的距離度量，表達式如下：

其中，dtst(trace_a，trace_b)表示它們對應的內存訪問模式集合之間包含的內存訪問模式個數，trace_a，trace_b分別表示兩條不同的程序調度路徑，分別表示兩條程序調度路徑包含的內存訪問模式集合，兩條程序調度路徑之間的距離；

步驟3、進行啟發式規則排序選擇，具體包括：計算隊列Q中距離度量最大的子狀態和目前探索過的程序狀態組成的調度路徑對應的三種啟發式規則的取值，如果根據三種啟發式規則中有任意一種規則能夠從隊列Q中區分出一個取值最大的子狀態，則排序結束，將該子狀態出隊列；否則，從所有距離最大的子狀態中隨機選擇出隊列；

三種啟發規則分別為線程切換頻率、寫操作占比和共享變量個數；

步驟4、繼續再執行，具體包括：在基于距離度量以及啟發式規則排序之后，控制存儲所有可行子狀態的隊列Q的長度，在選擇完子狀態繼續執行后，如果隊列Q的長度超過超參數N，則將隊尾多余的元素刪去，然后執行新的子狀態，重復探索程序狀態空間的過程直至到達程序的終止狀態；

步驟5、進行錯誤報告，具體包括：如果此時程序正常執行完畢沒有報告錯誤，則將本次從初始狀態探索直到當前終止狀態的探索過的程序調度路徑的信息記錄到集合T中，然后回到程序初始狀態，重新開始探索；否則，表明檢測到了程序的錯誤，直接退出運行，并且報告錯誤信息。