基于散列值的文件碎片與原始文件一致性檢驗方法研究

趙廣曄

摘 要：在侵犯知識產(chǎn)權(quán)、網(wǎng)絡(luò)入侵等案件的計算機司法檢驗過程中，經(jīng)常需要檢驗存儲介質(zhì)中是否存在被泄露文檔、植入的木馬等。而在實際鑒定過程中，往往只能找到一些文件碎片，那么如何檢驗原始文件與文件碎片之間的一致性關(guān)系就成了一個值得深入探討的問題。文章提出了一種基于散列值的文件碎片與原始文件一致性檢驗的方法。

關(guān)鍵詞：電子文件；文件碎片；同一性檢驗；散列值

引言

在進行計算機司法鑒定的過程中，經(jīng)常需要進行文件的一致性檢驗。根據(jù)GA/T 827-2009《電子物證文件一致性檢驗技術(shù)規(guī)范》，比較兩個文件的散列值，若兩個散列值相同，則可以判斷兩個文件的數(shù)據(jù)相同；若兩個散列值不同，則可以判斷兩個文件的數(shù)據(jù)不同[1]。但在實際檢驗的過程中，嫌疑人往往會對證據(jù)文件及其存儲介質(zhì)進行刪除或格式化等操作，通常只能夠找到一些文件碎片。因此，如何對文件碎片與原始文件的一致性關(guān)系進行鑒定就成為了相關(guān)案件鑒定過程中的一個難點。

1 文件碎片的產(chǎn)生原因及其與原始文件的關(guān)系

圖1 產(chǎn)生文件碎片的幾種情況

文件碎片是指由于文件在磁盤中不連續(xù)存儲而產(chǎn)生的文件分塊。圖1為產(chǎn)生文件碎片的幾種情況：（1）原始文件大小為4個簇，磁盤中的0、3、4三個簇已經(jīng)被其他文件占用，因此文件被分別存儲在1-2和3-4兩部分簇中，形成了兩塊文件碎片；（2）文件的原始原本存放在磁盤的0-3簇，另一個文件存儲在簇4中，現(xiàn)在對文件進行編輯使其長度增加到5個簇，在保存時新增加的內(nèi)容將保存在簇5中，產(chǎn)生了新的文件碎片；（3）文件原來存放在磁盤的0-3簇，被刪除后，簇0位置又存儲了另一個文件，這樣1-3三個簇就形成了文件碎片。由此可見，文件碎片實際上就是原始文件中的一部分。但是實際辦案中，由于蓄意破壞往往無法找到原始文件的全部碎片。鑒定檢材中是否曾經(jīng)存在原始文件就成了一個難題。

2 檢驗方法設(shè)計

由上述內(nèi)容可知，只需要驗證檢材中的文件碎片與原始文件中的部分內(nèi)容完全一致，即可認定該碎片屬于原始文件。為此，文章提出了一種基于散列值的文件碎片與原始文件一致性檢驗的方法。該方法的具體操作步驟如下：（1）將原始文件等分為大小為N字節(jié)的塊，分別計算散列值并生成散列表。該散列表結(jié)構(gòu)包含兩部分：塊索引樹，以分塊起始字節(jié)為結(jié)點關(guān)鍵字的二叉樹，見圖2左側(cè)部分；散列值索引表，記錄原始文件中以指定字節(jié)為起始的塊的散列值及其在原始文件內(nèi)的偏移地址，見圖2右側(cè)部分，該列表存放在對應(yīng)的結(jié)點中。（2）對目標文件碎片進行遍歷，如果字節(jié)值與塊搜索樹節(jié)點匹配，則計算N個字節(jié)的散列值，并在散列索引表中搜索，記錄匹配項。（3）按原始文件內(nèi)偏移地址整理遍歷結(jié)果，生成一致性檢驗報告。

3 檢驗方法的實現(xiàn)及驗證

（1）原始文件散列表的數(shù)據(jù)結(jié)構(gòu)。設(shè)原始文件的大小為T字節(jié)，拆分塊大小為N字節(jié)，拆分塊的總數(shù)量為S。若文件分塊的起始字節(jié)共有X種值，也就是在構(gòu)建塊索引樹時需要進行X次結(jié)點的插入操作，那么需要進行查找操作的次數(shù)Y=S-X。塊索引樹的結(jié)構(gòu)定義如下：

typedef struct BlockIndexTreeNode

{

byte startByte；

HashTable hashTable；

struct BlockIndexTreeNode *leftChild， *rightChild；

}BlockIndexTreeNode， *BlockIndexTree；

在構(gòu)建各個結(jié)點的散列值索引表時共需要進行S次插入操作，而且為了便于比對需要將索引表項按照散列值進行排序。散列值索引表結(jié)構(gòu)定義如下：

typedef struct HashListNode

{

byte[] hashValue；

long inFileOffset；

struct HashListNode *next；

}HashListNode；

（2）構(gòu)建散列表的文件分塊大小的界定。通過前面的分析可知，拆分塊總數(shù)量S=T/N或[T/N]+1，構(gòu)建塊索引樹時需要進行Y=S-X次查詢。即Y=T/N-X或T/N-X+1。由于X值很小。T為固定值，因此由N決定索引表構(gòu)建速度，N值越大，散列表的構(gòu)建和搜索比對速度就越快。但是，如果N值過大，就會導(dǎo)致比對結(jié)果不準確。文件系統(tǒng)對磁盤的管理單位為簇，因此N的值不應(yīng)該大于簇的大小。同時，為更精確的檢驗碎片文件與原始文件一致性，碎片文件應(yīng)該可以劃分成多個大小為N字節(jié)的塊。另外，因為常用的散列值大于等于16字節(jié)，若N值小于16字節(jié)則會降低檢驗效率。綜上所述，文件分塊大小N的計算方法如下：

N=MIN（簇大小，T/原始文件拆分度，MAX（16，碎片大小/碎片分析粒度））。

其中原始文件拆分度可以調(diào)節(jié)檢驗結(jié)果中的量化值精度，值越大精度越高；碎片分析粒度可以調(diào)節(jié)文件碎片被損壞對檢驗的影響，值越大影響越小。

（3）文件碎片的搜索比對方法。在比對的過程中對要檢驗的文件碎片進行按字節(jié)遍歷，如果當前字節(jié)存在于塊索引樹中，則從計算N個連續(xù)字節(jié)的散列值，并在散列值索引表中查找，并記錄匹配項。最后用匯總記錄的結(jié)果生成一致性檢驗報告。

（4）檢驗方法的驗證。首先，準備一些原始文件并制作文件碎片存放在測試檢材中。其次，模擬文件碎片被破壞的情況。之后，從檢材中提取可能的文件碎片。最后，使用文章提出的檢驗方法來檢驗提取出的文件碎片與原始文件的一致性。通過測試發(fā)現(xiàn)：以扇區(qū)為單位的方式進行遍歷可以大幅提高效率，但是部分情況無法匹配命中；逐字節(jié)進行遍歷執(zhí)行速度很慢，但是得到的檢驗結(jié)果精度很高。因此，提取出的文件碎片比較大的情況下，應(yīng)當優(yōu)先考慮以扇區(qū)為單位構(gòu)建散列表和遍歷文件碎片，否則應(yīng)當考慮縮小N值并進行逐字節(jié)進行遍歷。

4 結(jié)束語

文章基于散列值的文件碎片與原始文件一致性檢驗方法可以檢驗出文件碎片是否與原始文件部分匹配，并可以量化的給出一致性檢驗結(jié)果。由此可見，該方法解決了在檢驗過程中遇到檢材被破壞的情況下檢驗檢材中的文件碎片與原始文件一致性的問題。