肖錦琦

（四川大學(xué)計算機學(xué)院，成都 610065）

0　引言

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

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

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

1.1　NILSIMSA

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

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

1.2　TLSH

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

（1）用大小為5個字節(jié)的滑動窗口處理目標(biāo)數(shù)據(jù)，一次向前滑動一個字節(jié)，設(shè)一個滑動窗口的內(nèi)容為：ABCDE；則采用 Pearson Hash[]映射得到 ABC、ABD、ABE、ACD、ACE、ADE這6個trigram的索引，進而統(tǒng)計每個trigram出現(xiàn)的次數(shù)；

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

（3）構(gòu)造TLSH哈希的頭部，共三個字節(jié)：第一個字節(jié)是數(shù)據(jù)的校驗和；第二個字節(jié)為目標(biāo)文件長度大?。坏谌齻€字節(jié)由步驟（2）計算出的四分位點構(gòu)成；

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

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

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

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

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

2　基于內(nèi)容分割的分片哈希的SSDEEP算法

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

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

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

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

3　基于特征提取的SDHASH算法

SDHASH由Roussev在2010年提出，采用了類似于機器學(xué)習(xí)的方法去提取數(shù)據(jù)特征，具體方法如下：

（1）令熵值為Hnorm、優(yōu)先級Rprec以及權(quán)重Rpop的初值為0。將數(shù)據(jù)劃分為64字節(jié)大小的塊，計算每個塊的信息熵H。

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

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

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

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

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

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

4　算法對比及應(yīng)用

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

表1　相似性摘要算法對比

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

5　結(jié)語

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

參考文獻：

[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.