[發明專利]基于代碼指紋的代碼同源性檢測方法及其裝置

有效

• 申請號: 201710375425.4
• 申請日: 2017-05-24
• 公開（公告）號: CN107169358B
• 公開（公告）日: 2019-10-08
• 發明（設計）人: 魏強;劉臻;曹琰;尹中旭;彭建山
• 申請（專利權）人: 中國人民解放軍信息工程大學;上海紅神信息技術有限公司
• 主分類號: G06F21/56
• 分類號: G06F21/56;G06F8/41
• 代理公司: 鄭州大通專利商標代理有限公司 41111
• 代理人: 周艷巧

1.一種基于代碼指紋的代碼同源性檢測方法，其特征在于，包含如下步驟：

步驟1、對兩份輸入代碼S和T進行依賴關系分析，獲取原始程序依賴圖PDG；并對原始程序依賴圖PDG進行結構簡化、嵌套移除和著色處理，獲取簡化程序依賴圖sPDG；

步驟2、基于抽象語法樹解析代碼關鍵語法信息；

步驟3、抽取代碼執行路徑的系統調用序列，獲取目標代碼的全路徑參數向量集合，構建代碼指紋；

步驟4、計算代碼指紋間的同源性系數，該同源性系數包含簡化程序依賴圖sPDG同構系數P_S,T、語法信息重合系數C_S,T以及系統調用序列相似系數A_S,T；

步驟5、根據同源性系數計算兩份代碼S和T的同源性指數，通過該同源性指數判定代碼雙方存在的同源關系。

2.根據權利要求1所述的基于代碼指紋的代碼同源性檢測方法，其特征在于，步驟1中的對原始程序依賴圖PDG進行結構簡化、嵌套移除和著色處理，獲取簡化程序依賴圖sPDG，包含如下內容：

步驟11、依據簡化原則對原始程序依賴圖PDG進行結構簡化；

步驟12、對于包含嵌套關系的節點，移除其內部所嵌套的輸入節點與輸出節點，并將其對應依賴關系的邊移除到外層函數調用節點上；

步驟13、按照語句類型對節點進行分類并著色，獲取簡化程序依賴圖sPDG。

3.根據權利要求2所述的基于代碼指紋的代碼同源性檢測方法，其特征在于，步驟11中的簡化原則，包含：去除只有一個傳出邊而沒有任何傳入邊的頂點，去除只有一個傳入邊而沒有任何外向邊的頂點；去除只有一個輸入和一個輸出邊的頂點，并引入從其輸入頂點指向輸出頂點；去除沒有任何傳入或傳出邊緣頂點。

4.根據權利要求1所述的基于代碼指紋的代碼同源性檢測方法，其特征在于，步驟2中基于抽象語法樹解析代碼關鍵語法信息，包含如下內容：

步驟21、記錄指定代碼域中的全局變量、局部變量及其屬性，組成四元組，該四元組包含變量的作用域、鏈接屬性、存儲類型及名稱；

步驟22、解析并記錄宏定義及其對應內容，組成三元組，該三元組包含宏定義標識、內容類型及名稱；

步驟23、基于抽象語法樹AST解析代碼中的關鍵數據結構，以序列形式記錄代碼中自定義結構體。

5.根據權利要求1所述的基于代碼指紋的代碼同源性檢測方法，其特征在于，步驟3包含如下內容：

步驟31、從入口函數開始，生成函數f的調用圖和后序支配樹，提取出單條執行路徑中的系統調用序列k，記錄所有可能的執行路徑中系統調用序列集合K；

步驟32、對于每條系統調用序列k中的函數f，定位其所在函數域d，解析抽象語法樹中函數f的所有參數，通過靜態污點分析確定f中各個參數的數據來源s，判定參數值的來源，并結合參數的數據類型t構成函數f的參數向量e_f＝(d,f,t,s)；得到系統調用序列k的參數向量集E_k；

步驟33、對系統調用序列集合K中每條序列k執行步驟32，獲取目標代碼的全路徑參數向量集合E_K；

步驟34、根據目標代碼的全路徑參數向量集合E_K，構建代碼指紋。

6.根據權利要求1所述的基于代碼指紋的代碼同源性檢測方法，其特征在于，步驟4包含如下內容：

步驟41、對于目標代碼的簡化程序依賴圖sPDG，通過漸進式圖同構求解算法尋求簡化程序依賴圖sPDG之間的最大同構子圖，并計算簡化程序依賴圖sPDG之間的同構系數P_S,T；

步驟42、根據步驟2獲取的關鍵語法信息，通過Jaccard算法計算重合系數C_S,T；

步驟43、根據步驟3中的目標代碼的全路徑參數向量集合E_K，通過Jaccard求解E_K子集合的相似性系數，取最高值作為系統調用序列相似系數A_S,T。