[發明專利]一種應用改進遺傳算法的智能合約測試用例生成方法

有效

• 申請號: 202010579513.8
• 申請日: 2020-06-23
• 公開（公告）號: CN111797010B
• 公開（公告）日: 2022-09-23
• 發明（設計）人: 張鵬程;于佳男
• 申請（專利權）人: 河海大學
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06N3/00;G06N3/12;G06Q40/04
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 孟紅梅

1.一種應用改進遺傳算法的智能合約測試用例生成方法，其特征在于，包括如下步驟：

(1)根據以太坊智能合約程序的源代碼生成對應的控制流圖；

(2)遍歷控制流圖中節點，提取出合約程序中包含的全部整型變量的信息，同時定位合約中各個require語句所在的節點位置；

(3)根據步驟(2)獲得的整型變量信息遍歷控制流圖，統計合約中的變量的定義-使用對dup，記為N_dup；在統計得到的N_dup集合中，根據步驟(2)中的require語句定位結果進一步劃分出與require語句執行相關的dup，記為R_dup；

(4)根據統計出的R_dup和N_dup對程序進行代碼插樁，得到插樁后的智能合約程序；具體包括兩部分：在代碼最初位置插入語句聲明dup覆蓋狀態標識變量，初始化為false，并在對應dup執行后插入語句將變量賦值為true；在代碼最初位置插入語句聲明被覆蓋dup數量的統計變量并在代碼最末位置插入統計變量的輸出函數，在dup覆蓋狀態標識變量賦值true的語句后插入語句統計變量的自增；經過上述插樁后，輸出對應的智能合約代碼；

(5)根據預定義的種群規模以及步驟(2)獲取的智能合約程序中的整型變量信息初始化生成第一代種群，默認第一代種群為初始的個體最佳I_O，其中，取得最大適應度值的個體為初始全局最佳G_O；

(6)根據步驟(5)中的初始信息，采用遺傳算法的選擇、交叉、變異操作逐代生成新的種群，并將生成的每代新種群帶入步驟(4)得到的插樁后的合約程序中執行，根據預定義的適應度函數計算適應度值更新G_O、I_O并形成新的父代種群重復遺傳算法執行；

(7)當滿足預先設置的終止條件時，遺傳算法停止，輸出G_O和I_O作為算法最終的輸出結果。

2.根據權利要求1所述的應用改進遺傳算法的智能合約測試用例生成方法，其特征在于，所述步驟(1)包括如下步驟：

(11)構建智能合約中每個函數對應的子控制流圖，針對與控制結構相關的關鍵字去識別智能合約程序中的各個控制結構，包括順序結構、條件結構、循環結構；在子控制流圖構建過程中將由require所標識的控制結構處理為條件結構；

(12)構建整體控制流圖，逐個處理合約中的函數調用，對于存在調用的地方，用一對調用-返回邊來表示智能合約中的函數調用和返回關系，從而構建完整的控制流圖。

3.根據權利要求1所述的應用改進遺傳算法的智能合約測試用例生成方法，其特征在于，所述步驟(2)中包括如下步驟：

(21)遍歷控制流圖節點，基于智能合約中用于聲明整型變量信息的關鍵字，匹配字符串，獲取智能合約中的整型變量信息存儲在列表L_v中，包括變量名、變量長度和變量類型；并對L_v中每個變量分別初始化兩個列表L_{v_u}、L_{v_d}用來存儲變量的定義節點和使用節點；

(22)遍歷控制流圖節點，識別智能合約中require語句并定位其所在的節點。

4.根據權利要求3所述的應用改進遺傳算法的智能合約測試用例生成方法，其特征在于，所述步驟(3)中包括如下步驟：

(31)根據控制流圖，從初始節點開始執行前序遍歷，若遍歷節點存在對L_v中某一變量的定義，則將節點加入到對應變量的L_{v_u}中，若遍歷節點存在對L_v中某一變量的使用，則將節點加入到對應變量的L_{v_d}中，并在該變量的L_{v_u}中找到距離當前使用節點最近的前置定義節點，組成一個N_dup；遍歷控制流圖的所有路徑，統計N_dup的數量；

(32)根據智能合約中的require語句所在節點信息，在步驟(31)統計的N_dup集合的基礎上，標記出與require語句執行相關的dup，記為R_dup，統計R_dup的數量。