文/劉帥

最近幾年隨著開源軟件項(xiàng)目的數(shù)量與質(zhì)量的不斷提升，越來越多的企業(yè)也開始傾向于采取開源方案構(gòu)建自己的軟件系統(tǒng)。但在使用開源軟件項(xiàng)目的源代碼過程中，企業(yè)也隱性地承擔(dān)了因?yàn)檐浖?xiàng)目管理不善、程序員使用不當(dāng)?shù)纫蛩厮氲挠砷_源軟件許可證所帶來的法律風(fēng)險(xiǎn)。因此，對(duì)源代碼進(jìn)行同源性檢測，讓軟件企業(yè)了解其軟件代碼中包含的開源代碼成分，并分析這些開源代碼可能帶來的問題（知識(shí)產(chǎn)權(quán)風(fēng)險(xiǎn)、安全漏洞風(fēng)險(xiǎn)等）是目前規(guī)避上述風(fēng)險(xiǎn)的主要手段。然而，對(duì)于完成上述目標(biāo)的代碼同源性檢測將面臨著巨大的技術(shù)挑戰(zhàn)——不僅需要解決如何在海量的開源項(xiàng)目中提取并存儲(chǔ)用于比對(duì)的源代碼樣本數(shù)據(jù)信息，而且還需要達(dá)到快速、準(zhǔn)確地完成針對(duì)被比對(duì)軟件源代碼組成成分的檢測任務(wù)。為解決以上問題，本文將介紹一種面向海量目標(biāo)源代碼數(shù)據(jù)比對(duì)樣本的源代碼特征值提取算法，能夠基本滿足在存儲(chǔ)容量與檢測準(zhǔn)確度、效率上的對(duì)于源代碼同源性檢測的要求。本文中采用了Java語言的開源項(xiàng)目及其源代碼作為主要研究對(duì)象，既具有代表性，同時(shí)也兼顧了實(shí)際應(yīng)用價(jià)值。

1 已有源代碼同源性檢測技術(shù)

1.1 基于文本的方法

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

1.2 基于詞法的方法

對(duì)源代碼進(jìn)行詞法分析，將源代碼按照某種粒度轉(zhuǎn)化成Token序列，通過檢測Token序列中的重復(fù)序列來判定代碼克隆。這類方法的關(guān)鍵在于Token的提取和比較算法的設(shè)計(jì), 篩選的Token特征應(yīng)當(dāng)能夠應(yīng)對(duì)代碼混淆，不能被簡單混淆破壞掉。

1.3 基于語法的方法

分為基于樹的方法和基于度量的方法?；跇涞姆椒▽⒋a變換為AST，并利用樹匹配算法對(duì)子樹進(jìn)行檢測，但是樹的創(chuàng)建和比較具有較高的時(shí)空復(fù)雜度，因此代碼搜索效率較低，這種子樹搜索或節(jié)點(diǎn)間匹配的方法難以應(yīng)對(duì)代碼重排及控制流混淆。因此，后續(xù)很多研究是將AST轉(zhuǎn)換成Token序列或字符串來處理。

1.4 基于代碼特征值方法

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

2 核心算法設(shè)計(jì)

從上一章節(jié)可以看出當(dāng)前沒有完全傾向于面向海量目標(biāo)源代碼比對(duì)樣本的同源性檢測技術(shù)，因此，本文提出了一種源代碼特征值提取算法，通過該算法能夠?qū)颖敬a進(jìn)行切片后的特征值計(jì)算，提取后的特征值能夠基本滿足在存儲(chǔ)容量與檢測準(zhǔn)確度、效率上的要求。算法基于AST，其核心思路是將AST轉(zhuǎn)換為純文本內(nèi)容，再將特征值的提取問題簡化為處理海量文本去重的問題上來。下面將對(duì)每個(gè)算法步驟的具體實(shí)現(xiàn)進(jìn)行詳細(xì)說明：

2.1 消除代碼噪音步驟

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

2.2 代碼切片步驟

圖1：Token替代效果示意圖

圖2：結(jié)構(gòu)屬性多級(jí)聚類排序處理效果示意圖

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

2.3 Token替代步驟

借鑒成熟的Token替代方案，將通過對(duì)AST進(jìn)行分級(jí)處理后的各節(jié)點(diǎn)結(jié)構(gòu)體相關(guān)內(nèi)容進(jìn)行結(jié)構(gòu)信息Token符號(hào)替代，將參數(shù)、變量等名稱按結(jié)構(gòu)信息相關(guān)規(guī)則使用Token符號(hào)進(jìn)行代替，以實(shí)現(xiàn)Token化，從而消除“人為修改類、變量、方法等名稱但保持代碼邏輯”的干擾情況。Token替代算法的主要思想是利用AST對(duì)每個(gè)參數(shù)、變量在操作符兩端出現(xiàn)的次數(shù)以及在關(guān)鍵Block節(jié)點(diǎn)出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)，并根據(jù)統(tǒng)計(jì)信息合成其Token化后的名稱，處理后的效果如圖1所示。

2.4 結(jié)構(gòu)屬性多級(jí)聚類排序處理步驟

每一個(gè)AST方法節(jié)點(diǎn)都是一棵子語法樹，篩選其AST各節(jié)點(diǎn)單元結(jié)構(gòu)屬性，根據(jù)排序策略，完成多級(jí)聚類排序處理，從而在打亂代碼部分行順序但實(shí)現(xiàn)相同邏輯的情況下，可以盡量得到一個(gè)相同的結(jié)果，整個(gè)算法過程可以簡單地視為一個(gè)對(duì)所有Method子語法樹下Block節(jié)點(diǎn)語法樹內(nèi)各個(gè)節(jié)點(diǎn)結(jié)構(gòu)屬性的聚類后排序處理，并存儲(chǔ)為對(duì)應(yīng)的Struct結(jié)構(gòu)體對(duì)象的過程。處理后的效果如圖2所示。

2.5 特征值計(jì)算步驟

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

表1：相似度查詢表

3 檢測系統(tǒng)設(shè)計(jì)

如圖3所示，開源項(xiàng)目元數(shù)據(jù)采集系統(tǒng)完成從開源社區(qū)采集源代碼、元數(shù)據(jù)及許可證等數(shù)據(jù)信息，實(shí)時(shí)對(duì)所獲取數(shù)據(jù)進(jìn)行處理分類，進(jìn)行代碼特征值的分析與提取，并進(jìn)行持久化存儲(chǔ)，為同源性檢測提供必要的檢索素材與條件。代碼同源性檢測系統(tǒng)完成對(duì)待檢測源代碼的代碼組成成分與許可證風(fēng)險(xiǎn)進(jìn)行檢查。通過對(duì)目標(biāo)源代碼的特征值和分組信息的提取完成對(duì)海量代碼特征值庫的檢索。

4 測試結(jié)果與分析

本次測試中使用從Github開源社區(qū)上下載的開源代碼進(jìn)行算法的測試，測試內(nèi)容主要分為兩部分，以驗(yàn)證算法可以基本滿足面向海量目標(biāo)源代碼數(shù)據(jù)比對(duì)樣本場景下的代碼同源性檢測需求。

4.1 準(zhǔn)確性驗(yàn)證測試

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

表2：相似度檢測結(jié)果比對(duì)表

4.2 存儲(chǔ)容量驗(yàn)證測試

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

圖3：檢測系統(tǒng)設(shè)計(jì)圖

圖4：存儲(chǔ)容量對(duì)比圖

5 結(jié)束語

本文提出了一種源代碼特征值提取算法來滿足面向海量目標(biāo)源代碼數(shù)據(jù)比對(duì)樣本場景下的同源性檢測需求，在此基礎(chǔ)上對(duì)檢測系統(tǒng)進(jìn)行了設(shè)計(jì)，并使用該算法對(duì)構(gòu)造的各種抄襲類型進(jìn)行檢測并同工具檢測與其他算法結(jié)果進(jìn)行比較，證明本算法可以應(yīng)用到真實(shí)環(huán)境中并具有一定的使用價(jià)值。