[科普中國]-特征碼

特征碼（attribute code）用來判斷某段數(shù)據(jù)屬于哪個計算機字段。共計40個字符。

概念特征碼的獲取不可能再是簡單的取出一段代碼來，而是分段的，中間可以包含任意的內(nèi)容（也就是增加了一些不參加比較的“掩碼字節(jié)”，在出現(xiàn)“掩碼字節(jié)”的地方，出現(xiàn)什么內(nèi)容都不參加比較）。這就是曾經(jīng)提出的廣譜特征碼的概念。

基于特征碼的網(wǎng)頁去重隨著網(wǎng)絡(luò)技術(shù)和信息技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)已經(jīng)成為人們獲取信息的一個重要途徑?，F(xiàn)有的搜索引擎面臨的最大一個問題就是返回的結(jié)果集中包含大量重復(fù)的信息。如何更有效地幫助用戶獲取所需要的信息，能夠快速、準(zhǔn)確地為用戶提供信息，是網(wǎng)絡(luò)信息服務(wù)面臨的新課題。優(yōu)化搜索結(jié)果可以采用多種手段，如通過提取網(wǎng)頁的特征進行基于內(nèi)容的信息檢索，利用用戶反饋的信息進一步精確檢索結(jié)果，將結(jié)果集中的重復(fù)信息盡可能地消除等。

由于網(wǎng)絡(luò)信息分布的特點，網(wǎng)站上的信息存在相互轉(zhuǎn)載及鏡像站點等情況。出現(xiàn)相同網(wǎng)頁主要有以下幾種情形：網(wǎng)頁的URL完全相同；網(wǎng)頁的URL形式不同，但網(wǎng)站域名所對應(yīng)的IP是相同的；URL雖然不同，但網(wǎng)頁內(nèi)容完全相同；URL不同，為不同的網(wǎng)頁形式，但網(wǎng)頁上主要內(nèi)容是相同的。本文主要討論對于網(wǎng)頁內(nèi)容重復(fù)性的消除。

網(wǎng)頁去重系統(tǒng)結(jié)構(gòu)網(wǎng)頁為半結(jié)構(gòu)化的信息形式，它與單純的文本文檔并不完全相同。網(wǎng)頁中的有效信息主要包括以下幾方面的內(nèi)容：網(wǎng)頁標(biāo)題、網(wǎng)頁正文、導(dǎo)航信息、超鏈接信息、圖片聲音等多媒體信息等。從以上信息中可以提取出有關(guān)網(wǎng)頁內(nèi)容的一些特征。首先對檢索結(jié)果集中的網(wǎng)頁進行預(yù)處理，將其余信息屏蔽，獲得網(wǎng)頁的正文信息，然后用后面介紹的算法對網(wǎng)頁正文進行去重處理。即判斷是否已經(jīng)有相同內(nèi)容的網(wǎng)頁在結(jié)果集中，若有，則進行刪除或合并處理，若沒有，則將該網(wǎng)頁保留在檢索結(jié)果集中。網(wǎng)頁去重系統(tǒng)主要結(jié)構(gòu)如圖1所示。

基于特征碼的網(wǎng)頁去重算法對網(wǎng)頁進行去重處理，實質(zhì)上是從一批網(wǎng)頁中將內(nèi)容相同或相近的網(wǎng)頁分為一類，進行聚類處理。用傳統(tǒng)算法進行聚類處理，只能將同一大類的網(wǎng)頁聚合為一類，與傳統(tǒng)意義上的聚類處理不同，網(wǎng)頁去重需要對網(wǎng)頁進行較為精確的歸類。如果嚴(yán)格按照網(wǎng)頁內(nèi)容進行分類，則分類結(jié)果中類別會很大，導(dǎo)致在確定一個網(wǎng)頁屬于哪一類時計算所花費的時間過大。如果直接將網(wǎng)頁正文逐字進行匹配處理來實現(xiàn)歸類，也同樣會出現(xiàn)計算量過大，而在響應(yīng)時間上無法承受的問題。較好的方法是從網(wǎng)頁正文中抽取出少量信息構(gòu)成特征碼，在歸類時，以特征碼取代網(wǎng)頁，通過判斷特征碼是否相同或相近來判斷相應(yīng)的網(wǎng)頁內(nèi)容是否是重復(fù)的。

（1）網(wǎng)頁特征碼

網(wǎng)頁特征碼首先必須能夠較為全面地反映網(wǎng)頁的內(nèi)容，其次為了計算上的方便，特征碼在長度上有一定的限制，不能太長。采用以下方法構(gòu)造網(wǎng)頁特征碼:特征碼由主碼和輔碼兩部分構(gòu)成。依次提取網(wǎng)頁正文中每段段首的第一個字，組成主碼。再從各段中將每一個標(biāo)點符號前面的一個字提取出來，依次構(gòu)成輔碼，考慮特征碼長度方面的限制，輔碼提取中只對每段的前n個標(biāo)點符號進行提取。若某一網(wǎng)頁正文共有5段，取n值為3，則提取出來的網(wǎng)頁特征碼結(jié)構(gòu)如圖2所示。

（2）網(wǎng)頁重復(fù)性判斷算法

提取出網(wǎng)頁的特征碼之后，下一步工作是依據(jù)特征碼判斷網(wǎng)頁正文是否重復(fù)。假設(shè)網(wǎng)頁a對應(yīng)的特征碼為Ta，網(wǎng)頁b所對應(yīng)的特征碼為Tb，判斷a與b是否為重復(fù)網(wǎng)頁的主要步驟為：

1)比較Ta與Tb的主碼部分，若兩者主碼完全相同，則認(rèn)為網(wǎng)頁a與網(wǎng)頁b是內(nèi)容相同的網(wǎng)頁，轉(zhuǎn)4)，否則轉(zhuǎn)2)；

2)若Ta與Tb的主碼比較結(jié)果為以下情形之一：①其中一個的主碼為另一個主碼的真子集；②兩者不互為真子集，但兩者主碼取交集的結(jié)果較大，則轉(zhuǎn)3)作進一步判斷；若兩者主碼取交集為空或交集結(jié)果較小，則認(rèn)為網(wǎng)頁a與網(wǎng)頁b是內(nèi)容不同的網(wǎng)頁，轉(zhuǎn)4)；

3)對Ta、Tb主碼的交集，即兩者相同的主碼部分進行處理，判斷對應(yīng)的輔碼是否相同，若完全相同或大部分相同，則認(rèn)為網(wǎng)頁a與網(wǎng)頁b是內(nèi)容相同的網(wǎng)頁，若相同的輔碼很少，則認(rèn)為網(wǎng)頁a與網(wǎng)頁b是不同的網(wǎng)頁，轉(zhuǎn)4)；

4)算法結(jié)束。

在判斷算法中，對于以下情況認(rèn)為兩個網(wǎng)頁是相同的：一個網(wǎng)頁內(nèi)容是另一個網(wǎng)頁的部分內(nèi)容，或兩個網(wǎng)頁雖然不完全相同，但其中大部分內(nèi)容是相同的?？梢酝ㄟ^設(shè)定一定的閾值對算法中的不確定因素進行判定。如兩者交集結(jié)果超過其中任何一個的80%，則表示兩者交集結(jié)果較大，反之當(dāng)小于20%時，認(rèn)為兩者交集結(jié)果較小;在對輔碼進行比較時，當(dāng)相同的輔碼占80%以上時，認(rèn)為輔碼大部分相同?？梢愿鶕?jù)實際檢索的結(jié)果，將閾值調(diào)整至一個比較合適的取值范圍，獲取較為滿意的檢索結(jié)果。

（3）算法有效性分析

網(wǎng)頁重復(fù)性判斷算法是否有效，關(guān)鍵是特征碼與網(wǎng)頁正文內(nèi)容之間的對應(yīng)關(guān)系，若不同內(nèi)容的網(wǎng)頁對應(yīng)的特征碼是不同的，則保證了算法的有效性。若出現(xiàn)多個不同內(nèi)容的網(wǎng)頁有相同的特征碼，則會將不同內(nèi)容的網(wǎng)頁歸并到一類進行處理。若單純從文字上看，以中文網(wǎng)頁為例，常用的漢字大約為6700個，特征碼主碼的長度為n，則對于不同網(wǎng)頁出現(xiàn)相同特征碼主碼的概率為1/(6700)n。雖然對于一些熱門新聞，段首文字多以“據(jù)報道”、“新華社”等文字開頭，若有m段文字以這樣的固定詞開頭，(m小于n)，出現(xiàn)重復(fù)特征碼的概率為1/(6700)n-m，當(dāng)n-m或n的取值稍大，如大于5時，這樣的概率值是很小的。同時在算法中，還考慮了輔碼的作用，當(dāng)出現(xiàn)主碼部分相同時，進一步判斷輔碼的分布以確定特征碼是否相同。

算法實現(xiàn)（1）數(shù)據(jù)結(jié)構(gòu)的選擇

檢索結(jié)果集中的網(wǎng)頁具有動態(tài)變化和數(shù)量巨大兩個特征，必須選擇一種合適的數(shù)據(jù)結(jié)構(gòu)，減少去重過程(相同網(wǎng)頁合并過程)的比較次數(shù)，同時又能較好地表示動態(tài)變化的特征碼集合。二叉排序樹能較好地滿足上述要求，選擇二叉排序樹作為算法實現(xiàn)的主要數(shù)據(jù)結(jié)構(gòu)。二叉排序樹或為一空樹；或是具有下列特征的二叉樹：1)若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；2)若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；3)它的左、右子樹也分別為二叉排序樹。

為描述方便，以下所說相等是指兩個特征碼對應(yīng)的網(wǎng)頁內(nèi)容相同或相近，不等是指兩個特征碼對應(yīng)的網(wǎng)頁內(nèi)容不同。當(dāng)出現(xiàn)特征碼相等的情況時，需要進行合并處理。算法采用擴展二叉排序樹為主要的數(shù)據(jù)結(jié)構(gòu)，在傳統(tǒng)的二叉排序樹的每個結(jié)點中增加一個指針，該指針指向由特征碼構(gòu)成的鏈表，稱為“輔指針”。輔指針指向與該結(jié)點對應(yīng)網(wǎng)頁內(nèi)容相近的網(wǎng)頁特征碼，這樣就可以較方便地處理網(wǎng)頁合并的情形。最終保留在檢索結(jié)果集中的是擴展二叉排序樹中各結(jié)點表示的特征碼對應(yīng)的網(wǎng)頁。擴展二叉排序樹結(jié)構(gòu)如圖3所示。

（2）特征碼歸類過程

二叉排序樹的構(gòu)建過程也就是對特征碼進行歸類處理的過程。對于一個新處理的特征碼，在二叉排序樹中沒有找到可以合并的結(jié)點時，直接對該特征碼進行插入操作即可。在二叉排序樹中找到相等的特征碼時，該特征碼要進行合并操作，而不同于普通意義上二叉排序樹的查找操作。當(dāng)二叉排序樹為空時，將新處理的特征碼作為新結(jié)點插入樹中，插入新結(jié)點時，該結(jié)點的輔指針為空。當(dāng)二叉排序樹非空時，首先將新處理的特征碼與根結(jié)點表示的特征碼比較，若相等，則進行合并處理，若不等，則根據(jù)新處理的特征碼與根結(jié)點表示的特征碼之間的大小關(guān)系，分別在左子樹或右子樹上繼續(xù)進行比較，在比較過程中，若出現(xiàn)相等的情形，則將新處理的特征碼與相應(yīng)的結(jié)點進行合并，若在整個比較過程中，始終出現(xiàn)的是不等的情況，則說明新處理的特征碼所對應(yīng)的網(wǎng)頁內(nèi)容還沒有在二叉排序樹中，將其作為一個新接點插入。

假設(shè)網(wǎng)頁x對應(yīng)的特征碼為Tx，網(wǎng)頁y所對應(yīng)的特征碼為Ty，Tx為新處理的特征碼，Ty為二叉排序樹中出現(xiàn)的與Tx相等的特征碼，采取以下策略進行合并：1)若Tx與Ty的主碼完全相同，則二叉排序樹不需要做任何改動，直接將檢索結(jié)果集中網(wǎng)頁x刪除；2)若Tx主碼為Ty主碼的真子集，則將Tx與Ty輔指針?biāo)赶蜴湵碇懈鹘Y(jié)點的特征碼進行比較，若無相等的特征碼，則將Tx作為一個新結(jié)點插入Ty輔指針?biāo)赶蜴湵碇校?)若Ty主碼為Tx主碼的真子集，將Tx取代二叉排序樹中結(jié)點Ty，同時將Ty依據(jù)2)中的原則插入Tx輔指針?biāo)赶蜴湵碇校?)Tx與Ty不互為真子集，但兩者主碼取交集的結(jié)果較大，處理方法同2)。

（3）算法效率分析

不管新處理特征碼是進行合并或插入，均要先進行查找比較，已確定插入的位置或合并的結(jié)點。對二叉排序樹進行比較，在結(jié)點出現(xiàn)概率為隨機概率分布的情況下，平均查找長度小于等于2(1+1/m)lnm，m為二叉排序樹中結(jié)點的個數(shù)，平均查找長度與logm成數(shù)量級，即比較過程的時間復(fù)雜度為O(logm)。插入結(jié)點過程只是一些指針的移動，時間可以忽略不計。由于特征碼主要由各段段首字及每段中前n個標(biāo)點符號前的文字構(gòu)成，因此對特征碼的提取不需要對整個網(wǎng)頁正文都掃描一次，特征碼的提取時間與處理的網(wǎng)頁正文長度有關(guān)，可以看成是一線性關(guān)系，特征碼提取的時間復(fù)雜度為O(n)。1

基于特征碼技術(shù)的攻防策略當(dāng)前單純意義上的病毒已逐步被木馬、蠕蟲所代替。操作系統(tǒng)的升級為后門病毒大規(guī)模的破壞提供了便利，并且從自啟動發(fā)展為注冊系統(tǒng)服務(wù)，從單進程發(fā)展為守護進程和遠程線程注入，甚至采用驅(qū)動技術(shù)來隱藏后門程序，讓用戶手動查找愈加困難。在這種局勢下，各種新技術(shù)和殺軟被不斷開發(fā)出來，和病毒進行著沒有硝煙的較量。2

引言所謂特征碼，就是防毒軟件從病毒樣本中提取的不超過64字節(jié)且能代表病毒特征的十六進制代碼。主要有單一特征碼、多重特征碼和復(fù)合特征碼這三種類型。特征碼提取的思路是：首先獲取一個病毒程序的長度，根據(jù)樣本長度可將文件分為若干份(分段的方法在很大程度上避免了采用單一特征碼誤報病毒現(xiàn)象的發(fā)生，也可以避免特征碼過于集中造成的誤報)，每份選取16B或32B的特征串，若該信息是通用信息或者全零字節(jié)則舍棄，認(rèn)為或隨機調(diào)整偏移最后重新選取。最后，將選取出來的幾段特征碼及它們的偏移量存入病毒庫，標(biāo)示出病毒的名稱即可。根據(jù)這個思路可編寫出特征碼提取程序?qū)崿F(xiàn)自動提取，并保存病毒記錄。在掃描病毒時，防毒軟件將目標(biāo)文件通過模式匹配算法與病毒庫中的特征碼進行比對，以確定是否染毒。

特征碼的檢測與處理（1）特征碼的定位

單一特征碼掃描，就是從病毒樣本中提取連續(xù)的能標(biāo)示此病毒的若干個字節(jié)。其好處在于開銷小，便于升級和維護病毒庫。但這種技術(shù)容易導(dǎo)致誤查誤殺，已較少使用。對于多重特征碼，可在單一特征碼掃描的基礎(chǔ)上進一步提取不連續(xù)的若干段特征碼，僅當(dāng)待檢測文件完全符合這多段特征碼時才報苦。這樣可以減少誤殺率，提高查殺的準(zhǔn)確度，因此成為多數(shù)防毒軟件的首選技術(shù)。用“逐字節(jié)替換法”可手動定位多重特征碼。把目標(biāo)木馬服務(wù)端或病毒逐字節(jié)地替換為OOh或fh(其他亦可)，每替換一次存為一個文件，然后對生成的幾份文件殺毒，未被刪除的就是被修改了特征碼的文件。匯總被修改的字節(jié)就得到了殺軟對該木馬或病毒所定義的“特征碼”。然而，手工操作和占用空間都過于龐大，可用分段法加以改進，即逐步縮小特征碼所在范圍。實驗中選取某防毒軟件對黑客工具進行特征碼定位。首先以128 B為替換單位，從查殺后的文件可知特征碼的偏移和范圍，之后還原代碼，再以32 B為單位對該范圍進行替換并查殺，最后使用逐字節(jié)替換定位出連續(xù)的特征碼字節(jié)。這樣每次僅需幾兆的空間，且速度很快。整個由粗略到精細(xì)的定位。至此，多重特征碼定位成功，只需任選一段特征碼來定位，修改后就可以逃過查殺。

（2）特征碼的修改

對定位后的特征碼進行修改便能逃過查殺。對可執(zhí)行文件，要根據(jù)匯編代碼來修改特征碼，首先進行反匯編，使用調(diào)試器(如ollydbg)調(diào)試程序，并根據(jù)特征碼的文件偏移地址轉(zhuǎn)換成的虛擬地址找到匯編指令。修改方法主要有：修改字符串大小寫法、等價替換法、指令順序調(diào)換法、通用跳轉(zhuǎn)法。許多病毒采用自動變形技術(shù)來逃避特征碼檢測，即所謂的多動態(tài)病毒，它在外觀形態(tài)上沒有固定的特征碼川。病毒的多態(tài)致使對其代碼段的加密能完全改變原有特征碼，因此搖在零區(qū)域加入解密代碼來解密，然后使用JMP指令跳回原指令代碼執(zhí)行，由于對某一字節(jié)執(zhí)行XOR兩次后可還原代碼，因此可以手動加密代碼，下次病毒執(zhí)行時，可以解密代碼并執(zhí)行。致使特征碼完全變樣，達到免殺。

策略改進與技術(shù)展望特征碼技術(shù)具有低誤報率、高準(zhǔn)確性、高可靠等不可比擬的優(yōu)勢，其技術(shù)機理和執(zhí)行流程也非常成熟。為了彌補特征碼技術(shù)的被動性，建議輔以如下幾種防病毒新技術(shù)：

（1）輸入表關(guān)聯(lián)特征碼

病毒運行時需要調(diào)用存在于輸入表中的API函數(shù)，如果將特征碼鎖定在可執(zhí)行文件的“敏感”區(qū)域—輸入表中，由于輸入表位置固定，因此不能用通用跳轉(zhuǎn)法來修改特征碼，這樣能有效地保護特征碼。

（2）偽特征碼

防病毒軟件可以檢測某一段自己的特征碼，如果發(fā)現(xiàn)它被填充為O，那么就激活原先設(shè)置的隨機效用的偽特征碼并報替，就算能找到這些特征碼，對于查殺沒有影響。

（3）廣譜特征串過濾技術(shù)

為應(yīng)對不斷變化和未知的病毒，啟發(fā)式掃描方式出現(xiàn)了。啟發(fā)式掃描是通過分析指令出現(xiàn)的順序，或特定組合情況等常見病毒的標(biāo)準(zhǔn)特征來決定文件是否感染未知病毒。因為病毒要達到感染和破壞的目的，通常的行為都會有一定的特征，例如非常規(guī)讀寫文件，終結(jié)自身，復(fù)制自身到系統(tǒng)目錄，修改注冊表某一鍵值，調(diào)用特定的AIP函數(shù)等等。所以可以根據(jù)掃描特定的行為或多種行為的組合來判斷一個程序是否為病毒。這種啟發(fā)式掃描比起靜態(tài)的特征碼掃描要先進的多，可以達到一定的未知病毒處理能力，但仍會有不準(zhǔn)確的時候。特別是因為無法確定一定是病毒，而不可能做未知病毒殺毒。3

本詞條內(nèi)容貢獻者為:

陳紅 - 副教授 - 西南大學(xué)