基于相似性摘要算法的應用與研究

肖錦琦

（四川大學計算機學院，成都 610065）

0　引言

傳統的數據摘要算法如MD5、SHA-1等目前被廣泛應用于數據完整性校驗、數據加密等領域，其特點是摘要生成過程不可逆，且對原始數據十分敏感，一個字節的變化就會導致生成完全不同的摘要。但在電子數據取證以及惡意軟件檢測領域，存在各式各樣的具有一定相似性的數據需要被挖掘出來，例如識別惡意軟件變種、補丁升級的軟件、被修改過的文本、或者是計算內存與硬盤中數據信息的相似程度等，而這些算法難以應對這類問題。相似性摘要算法便是用來解決這些最鄰近搜索問題的一種有效手段，它將每個文件生成較短的指紋，不逐一比較文件本身，而是比較指紋。這樣來降低比較量，提高效率。目前較為常見的有SSDEEP[1]、SDHASH[2,3]、NILSIMSA[4]、TLSH[5]等算法，其共同特點就是目標信息的改變程度會反應在生成的摘要信息上。按照實現方法可以將其分為基于內容分割的分片哈希算法、特征提取算法以及局部敏感哈希算法等三個類別，本文闡述了幾種算法的核心思想，并對幾種算法進行對比，討論了其適用范圍以及發展趨勢。

1　基于局部敏感哈希的相似性摘要算法

局部敏感哈希算法的基本思想是將兩個點沖突的可能性與其距離緊密相連，即兩個點的距離越近它們沖突可能性越高，距離越遠則沖突的可能性則越低。目前基于局部敏感哈希實現的相似性摘要算法有NILSIMSA和TLSH兩種。

1.1　NILSIMSA

NILSIMSA最早被應用于垃圾郵件過濾中，通過步長為1，大小為5個字節的滑動窗口遍歷目標數據，再將每個窗口中生成的3字節組（trigram）通過哈希函數h（）進行映射，即令 i=h（trigram），其中 i的取值范圍在0～255，用來統計每個trigram出現的次數，進計算所有trigram次數的平均值，若第i個trigram的次數大于平均值則輸出1，否則輸出0。由此可產生一個大小為32字節的摘要信息。

相似度則是通過按位統計兩個摘要信息之間相同的總數減去128得出，也就是相似度的取值范圍在-128～128之間，原文作者指出在相似度超過54時，可以認為兩個文本的匹配度較高。

1.2　TLSH

TLSH算法是由趨勢科技公司提出的一種相似性摘要算法，其借鑒了NILSIMSA的一些基本思想，工作原理如下：

（1）用大小為5個字節的滑動窗口處理目標數據，一次向前滑動一個字節，設一個滑動窗口的內容為：ABCDE；則采用 Pearson Hash[]映射得到 ABC、ABD、ABE、ACD、ACE、ADE這6個trigram的索引，進而統計每個trigram出現的次數；

（2）定義 q1、q2、q3為：75%的 trigram 的個數≥q1，50%的trigram的個數≥q2，25%的trigram的個數≥q3；

（3）構造TLSH哈希的頭部，共三個字節：第一個字節是數據的校驗和；第二個字節為目標文件長度大小；第三個字節由步驟（2）計算出的四分位點構成；

（4）構造TLSH哈希的主體部分：并按如下公式生成相應的二進制位，由此得到大小為32字節的主體部分摘要信息。

（5）將步驟（3）、（4）所求得的哈希頭部與主體連接起來，得到最終的TLSH摘要信息。

TLSH通過距離值表示兩個信息之間的匹配度，首先定義mod_diff（a，b，R）為一個在大小為R的循環隊列中a到b的最小距離，即：

mod_diff（a，b，R）=Min（（a-b）modR，（b-a）modR）

通過mod_diff（）計算前三個頭字節的距離并累加起來，而主體部分的距離計算方式與漢明距離較為相似。頭部距離與主體距離之和為最終的距離值，其范圍可以達到1000以上，與NILSIMSA相比具有更好的區分度。

2　基于內容分割的分片哈希的SSDEEP算法

基于內容分割的分片哈希算法（Context Triggered Piecewise Hashing,CTPH）又被稱為模糊哈希算法（Fuzzy hash），2006年 Jesse Kornblum 提出 CTPH，并實現了一個名為spam sum的算法實例。隨后，Jason Sherman開發了SSDEEP工具以實現這一算法。該算法最初用于取證，后來被用于惡意代碼檢測，最近又有用于開源軟件漏洞挖掘等。目前SSDEEP已經成為惡意軟件分析領域的一個標準算法，被NIST以及Virus Total作為相似性摘要算法所支持，其工作原理如下：

（1）首先將數據進行分片，讀取前n個字節使用Alder-32算法作為滾動哈希算法得到哈希值h，若h除以n的余數恰好等于n-1時就在當前位置分片，否則，不分片，并向前移動一個字節，重復上述步驟。其中n的初值近似于文件的長度除以64的值，為2的整數倍，并根據分得的片數調整n的大小，如果當前片數較低，則將n減小一半，若較多則將n乘以2。最終使得分得的片數維持在32～64之間。

（2）使用Fowler-Noll-Vo hash[7]哈希算法計算每個分片的哈希值，并取哈希值的后六位以ASCII碼表示出來作為摘要信息的最終結果。

（3）采用加權編輯距離（weighted edit distance）作為評價其相似性的依據，然后將這個值除以兩個數據的長度之和，再將其映射到0～100的整數值上，100代表完全一致，0表示完全不同。

3　基于特征提取的SDHASH算法

SDHASH由Roussev在2010年提出，采用了類似于機器學習的方法去提取數據特征，具體方法如下：

（1）令熵值為Hnorm、優先級Rprec以及權重Rpop的初值為0。將數據劃分為64字節大小的塊，計算每個塊的信息熵H。

其中，P(Xi)表示字節值i在該塊中出現的概率，然后計算得到Hnorm。

Hnorm=1000×H/log2B（B=64）

其中Hnorm向下取整，而Rprec由Hnorm映射得到。（2）計算出所有塊的Rprec后，用大小為8，步長為1的滑動窗口依次遍歷所有的Rprec值，并將窗口中值最小且位于最左端的Rprec值對應的Rpop值加一，選出所有Rpop≥t的塊作為特征，這里t為4。

（3）每個被選出的特征轉換為SHA-1，并將得到的哈希值分成5份放入Bloom過濾器[7]中，當過濾器存滿時，則再創建一個新的過濾器進行填充，直到處理完所有特征。

（4）處理完所有特征后，Bloom過濾器中存儲的數據即為最終的摘要信息，其距離計算公式SD(F,G)如下：

其中，信息摘要 F=f1f2…fn，G=g1g1…gn，（f和 g代表Bloom過濾器）。

4　算法對比及應用

目前已有一些工作對幾種相似性摘要算法做了安全性的分析[8-9]，其中Breitinger對SSDEEP做了分析認為該算法并沒有使用基于密碼學的哈希函數，構成并不嚴謹，因此存在漏洞可以被利用。而文獻[10]對相似性摘要算法的健壯性以及對網頁、圖片等格式的區分度做了詳細的對比實驗，結果認為TLSH應對隨機性變化的能力要好于SDHASH與SSDEEP。其特點對比如表1：

表1　相似性摘要算法對比

除了在電子取證方面有著廣泛的應用，近年來也有人通過相似性摘要算法在安全領域進行試驗，如文獻[11,12,13]對其在惡意軟件二進制變種識別上做了研究，并取得了較好的結果。

5　結語

本文對相似性摘要算法做了全面的介紹，同時針對其在安全領域方面的應用做了分析，該算法由于極強的區分能力以及抗隨機干擾能力，在惡意軟件家族分類，軟件漏洞分析等領域也有極大的優勢，但目前相似性摘要算法只支持字面上的區分，無法做到語義上的區分，因此針對特定的領域還需進一步的提取其深層次的特征。

參考文獻：

[1]Kornblum J.Identifying Almost Identical Files Using Context Triggered Piecewise Hashing[J].Digital Investigation,2006,3（3）:91-97.

[2]Roussev,V.:An Evaluation of Forensics Similarity Hashes.In:Proceedings of the 11th Annual DFRWS,pp.S34.S41.Elsevier,（2011）

[3]Roussev V.Data Fingerprinting with Similarity Digests[C].Advances in Digital Forensics VI-Sixth IFIP WG 11.9 International Conference on Digital Forensics,Hong Kong,China,January 4-6,2010,Revised Selected Papers.DBLP,2010:207-226.

[4]Damiani E,Vimercati S D C D,Paraboschi S,et al.An Open Digest-based Technique for Spam Detection[C].ISCA,International Conference on Parallel and Distributed Computing Systems,September 15-17,2004,the Canterbury Hotel,San Francisco,California,Usa.DBLP,2004:559-564.

[5]Oliver J,Cheng C,Chen Y.TLSH--A Locality Sensitive Hash[C].Fourth Cybercrime and Trustworthy Computing Workshop.IEEE Computer Society,2013:7-13.

[6]Eastlake D,Fowler G,Vo K P,et al.The FNV Non-Cryptographic Hash Algorithm[J].2014.

[7]B.Bloom,Space/Time Trade-Offs in Hash Coding with Allowable Errors,Communications of the ACM,vol.13（7）,pp.422-426,1970.

[8]Breitinger,F.:Sicherheitsaspekte Von Fuzzy-Hashing.Master's Thesis,Hochschule Darmstadt,2011

[9]Breitinger,F.,Baier,H.,Beckingham,J.:Security and Implementation Analysis of the Similarity Digest sdhash,1st International Baltic Conference on Network Security&Forensics（NeSeFo）,Tartu（Estland）（2012）.

[10]Oliver J,Forman S,Cheng C.Using Randomization to Attack Similarity Digests[M].Applications and Techniques in Information Security.Springer Berlin Heidelberg,2014.

[11]Daniel Raygoza.Automated Malware Similarity Analysis.Black Hat 2009

[12]Madison J,Techreport I,Smith M.Identifying Malware with Byte Frequency Distribution and Context Triggered Piecewise Hashing[J].2007.

[13]Azab A,Layton R,Alazab M,et al.Mining Malware to Detect Variants[C]//Cybercrime and Trustworthy Computing Conference.IEEE,2015:44-53.