面向海量目標源代碼數據比對樣本的源代碼特征值提取算法

文/劉帥

最近幾年隨著開源軟件項目的數量與質量的不斷提升，越來越多的企業也開始傾向于采取開源方案構建自己的軟件系統。但在使用開源軟件項目的源代碼過程中，企業也隱性地承擔了因為軟件項目管理不善、程序員使用不當等因素所引入的由開源軟件許可證所帶來的法律風險。因此，對源代碼進行同源性檢測，讓軟件企業了解其軟件代碼中包含的開源代碼成分，并分析這些開源代碼可能帶來的問題（知識產權風險、安全漏洞風險等）是目前規避上述風險的主要手段。然而，對于完成上述目標的代碼同源性檢測將面臨著巨大的技術挑戰——不僅需要解決如何在海量的開源項目中提取并存儲用于比對的源代碼樣本數據信息，而且還需要達到快速、準確地完成針對被比對軟件源代碼組成成分的檢測任務。為解決以上問題，本文將介紹一種面向海量目標源代碼數據比對樣本的源代碼特征值提取算法，能夠基本滿足在存儲容量與檢測準確度、效率上的對于源代碼同源性檢測的要求。本文中采用了Java語言的開源項目及其源代碼作為主要研究對象，既具有代表性，同時也兼顧了實際應用價值。

1 已有源代碼同源性檢測技術

1.1 基于文本的方法

將代碼直接進行文本或字符串比較。將程序代碼當做文本進行分析，利用字符串匹配算法將代碼劃分為一系列子串，然后對每個子串進行哈希運算,并篩選出部分哈希值作為程序指紋。

1.2 基于詞法的方法

對源代碼進行詞法分析，將源代碼按照某種粒度轉化成Token序列，通過檢測Token序列中的重復序列來判定代碼克隆。這類方法的關鍵在于Token的提取和比較算法的設計, 篩選的Token特征應當能夠應對代碼混淆，不能被簡單混淆破壞掉。

1.3 基于語法的方法

分為基于樹的方法和基于度量的方法。基于樹的方法將代碼變換為AST，并利用樹匹配算法對子樹進行檢測，但是樹的創建和比較具有較高的時空復雜度，因此代碼搜索效率較低，這種子樹搜索或節點間匹配的方法難以應對代碼重排及控制流混淆。因此，后續很多研究是將AST轉換成Token序列或字符串來處理。

1.4 基于代碼特征值方法

在面向海量目標源代碼數據比對樣本的問題下，由BlackDuck提出了codeprint的概念，其采用純文本方案計算代碼特征值，不僅實現了快速檢索，而且在一定程度上解決了對代碼進行修改導致精度失效的問題，但純文本提取方案在故意修改源代碼的情況下會導致相似度分析準確性不足，而且如果采用較細粒度來提取特征值將耗費比較大的存儲空間。另外，有一種將AST后綴樹各子節點作為特征值提取依據的算法，大幅度提升了對于故意修改源代碼進行相似度分析的準確性，但很難將一顆完整AST后綴樹的所有子節點的結構進行哈希計算后進行存儲。

2 核心算法設計

從上一章節可以看出當前沒有完全傾向于面向海量目標源代碼比對樣本的同源性檢測技術，因此，本文提出了一種源代碼特征值提取算法，通過該算法能夠對樣本代碼進行切片后的特征值計算，提取后的特征值能夠基本滿足在存儲容量與檢測準確度、效率上的要求。算法基于AST，其核心思路是將AST轉換為純文本內容，再將特征值的提取問題簡化為處理海量文本去重的問題上來。下面將對每個算法步驟的具體實現進行詳細說明：

2.1 消除代碼噪音步驟

該步驟實現識別并剔除代碼中的噪聲內容。有一些代碼噪聲很容易被有意的添加在代碼片段中用于干擾檢查結果，造成基于文本或Token方法的源代碼同源性檢測結果精度降低，如對目標源碼中夾雜一些無用的聲明。通過該過程將一些人為混入源代碼中的無用代碼片段過濾掉，從而達到消除噪音的目的。

2.2 代碼切片步驟

圖1：Token替代效果示意圖

圖2：結構屬性多級聚類排序處理效果示意圖

代碼切片的目的是為了對源代碼選取一個合適的切分粒度，得到一系列的切片，最終為每個切片計算特征值，以細化比較的粒度，從而更加有效的進行檢索和分析。本算法采用以方法為粒度進行源代碼的切片處理。

2.3 Token替代步驟

借鑒成熟的Token替代方案，將通過對AST進行分級處理后的各節點結構體相關內容進行結構信息Token符號替代，將參數、變量等名稱按結構信息相關規則使用Token符號進行代替，以實現Token化，從而消除“人為修改類、變量、方法等名稱但保持代碼邏輯”的干擾情況。Token替代算法的主要思想是利用AST對每個參數、變量在操作符兩端出現的次數以及在關鍵Block節點出現的次數進行統計，并根據統計信息合成其Token化后的名稱，處理后的效果如圖1所示。

2.4 結構屬性多級聚類排序處理步驟

每一個AST方法節點都是一棵子語法樹，篩選其AST各節點單元結構屬性，根據排序策略，完成多級聚類排序處理，從而在打亂代碼部分行順序但實現相同邏輯的情況下，可以盡量得到一個相同的結果，整個算法過程可以簡單地視為一個對所有Method子語法樹下Block節點語法樹內各個節點結構屬性的聚類后排序處理，并存儲為對應的Struct結構體對象的過程。處理后的效果如圖2所示。

2.5 特征值計算步驟

特征值計算將主要采用Simhash算法，并在加權計算方面加以改造。Simhash是Google用來處理海量文本去重的算法，可以得到局部敏感的代碼特征值。根據對普遍的Method節點層數及計算后準確性的驗證，哈希值長度選取128位，權重一般可考慮取Method節點的基數權重為10，子節點為父節點的70%，依次計算。經過大量實驗，當海明距離小于20時，代碼相似度較高，可參考以下相似度查詢表（如表1所示）。

表1：相似度查詢表

3 檢測系統設計

如圖3所示，開源項目元數據采集系統完成從開源社區采集源代碼、元數據及許可證等數據信息，實時對所獲取數據進行處理分類，進行代碼特征值的分析與提取，并進行持久化存儲，為同源性檢測提供必要的檢索素材與條件。代碼同源性檢測系統完成對待檢測源代碼的代碼組成成分與許可證風險進行檢查。通過對目標源代碼的特征值和分組信息的提取完成對海量代碼特征值庫的檢索。

4 測試結果與分析

本次測試中使用從Github開源社區上下載的開源代碼進行算法的測試，測試內容主要分為兩部分，以驗證算法可以基本滿足面向海量目標源代碼數據比對樣本場景下的代碼同源性檢測需求。

4.1 準確性驗證測試

隨機選擇一個Github開源項目Tron(https://github.com/tronprotocol/javatron)，將其包org.tron.common.storage中的DepositImpl.java源代碼文件中的getStorage方法作為本次準確性驗證的基準源代碼樣本。與基于文本的三種比對工具Beyond Compare、WinMerge和TextDiff進行比對，可以看到本算法的準確性較高，結果如表2所示。

表2：相似度檢測結果比對表

4.2 存儲容量驗證測試

同樣使用Tron項目，將本算法在提取特征值以及檢索必要信息后的存儲容量同源文件與文本特征值提取算法進行比較，可以看到本算法所占的存儲容量相對較小，如圖4所示。

圖3：檢測系統設計圖

圖4：存儲容量對比圖

5 結束語

本文提出了一種源代碼特征值提取算法來滿足面向海量目標源代碼數據比對樣本場景下的同源性檢測需求，在此基礎上對檢測系統進行了設計，并使用該算法對構造的各種抄襲類型進行檢測并同工具檢測與其他算法結果進行比較，證明本算法可以應用到真實環境中并具有一定的使用價值。