基于散列值的文件碎片与原始文件一致性检验方法研究

赵广晔

摘 要：在侵犯知识产权、网络入侵等案件的计算机司法检验过程中，经常需要检验存储介质中是否存在被泄露文档、植入的木马等。而在实际鉴定过程中，往往只能找到一些文件碎片，那么如何检验原始文件与文件碎片之间的一致性关系就成了一个值得深入探讨的问题。文章提出了一种基于散列值的文件碎片与原始文件一致性检验的方法。

关键词：电子文件；文件碎片；同一性检验；散列值

引言

在进行计算机司法鉴定的过程中，经常需要进行文件的一致性检验。根据GA/T 827-2009《电子物证文件一致性检验技术规范》，比较两个文件的散列值，若两个散列值相同，则可以判断两个文件的数据相同；若两个散列值不同，则可以判断两个文件的数据不同[1]。但在实际检验的过程中，嫌疑人往往会对证据文件及其存储介质进行删除或格式化等操作，通常只能够找到一些文件碎片。因此，如何对文件碎片与原始文件的一致性关系进行鉴定就成为了相关案件鉴定过程中的一个难点。

1 文件碎片的产生原因及其与原始文件的关系

图1 产生文件碎片的几种情况

文件碎片是指由于文件在磁盘中不连续存储而产生的文件分块。图1为产生文件碎片的几种情况：（1）原始文件大小为4个簇，磁盘中的0、3、4三个簇已经被其他文件占用，因此文件被分别存储在1-2和3-4两部分簇中，形成了两块文件碎片；（2）文件的原始原本存放在磁盘的0-3簇，另一个文件存储在簇4中，现在对文件进行编辑使其长度增加到5个簇，在保存时新增加的内容将保存在簇5中，产生了新的文件碎片；（3）文件原来存放在磁盘的0-3簇，被删除后，簇0位置又存储了另一个文件，这样1-3三个簇就形成了文件碎片。由此可见，文件碎片实际上就是原始文件中的一部分。但是实际办案中，由于蓄意破坏往往无法找到原始文件的全部碎片。鉴定检材中是否曾经存在原始文件就成了一个难题。

2 检验方法设计

由上述内容可知，只需要验证检材中的文件碎片与原始文件中的部分内容完全一致，即可认定该碎片属于原始文件。为此，文章提出了一种基于散列值的文件碎片与原始文件一致性检验的方法。该方法的具体操作步骤如下：（1）将原始文件等分为大小为N字节的块，分别计算散列值并生成散列表。该散列表结构包含两部分：块索引树，以分块起始字节为结点关键字的二叉树，见图2左侧部分；散列值索引表，记录原始文件中以指定字节为起始的块的散列值及其在原始文件内的偏移地址，见图2右侧部分，该列表存放在对应的结点中。（2）对目标文件碎片进行遍历，如果字节值与块搜索树节点匹配，则计算N个字节的散列值，并在散列索引表中搜索，记录匹配项。（3）按原始文件内偏移地址整理遍历结果，生成一致性检验报告。

3 检验方法的实现及验证

（1）原始文件散列表的数据结构。设原始文件的大小为T字节，拆分块大小为N字节，拆分块的总数量为S。若文件分块的起始字节共有X种值，也就是在构建块索引树时需要进行X次结点的插入操作，那么需要进行查找操作的次数Y=S-X。块索引树的结构定义如下：

typedef struct BlockIndexTreeNode

{

byte startByte；

HashTable hashTable；

struct BlockIndexTreeNode *leftChild， *rightChild；

}BlockIndexTreeNode， *BlockIndexTree；

在构建各个结点的散列值索引表时共需要进行S次插入操作，而且为了便于比对需要将索引表项按照散列值进行排序。散列值索引表结构定义如下：

typedef struct HashListNode

{

byte[] hashValue；

long inFileOffset；

struct HashListNode *next；

}HashListNode；

（2）构建散列表的文件分块大小的界定。通过前面的分析可知，拆分块总数量S=T/N或[T/N]+1，构建块索引树时需要进行Y=S-X次查询。即Y=T/N-X或T/N-X+1。由于X值很小。T为固定值，因此由N决定索引表构建速度，N值越大，散列表的构建和搜索比对速度就越快。但是，如果N值过大，就会导致比对结果不准确。文件系统对磁盘的管理单位为簇，因此N的值不应该大于簇的大小。同时，为更精确的检验碎片文件与原始文件一致性，碎片文件应该可以划分成多个大小为N字节的块。另外，因为常用的散列值大于等于16字节，若N值小于16字节则会降低检验效率。综上所述，文件分块大小N的计算方法如下：

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

其中原始文件拆分度可以调节检验结果中的量化值精度，值越大精度越高；碎片分析粒度可以调节文件碎片被损坏对检验的影响，值越大影响越小。

（3）文件碎片的搜索比对方法。在比对的过程中对要检验的文件碎片进行按字节遍历，如果当前字节存在于块索引树中，则从计算N个连续字节的散列值，并在散列值索引表中查找，并记录匹配项。最后用汇总记录的结果生成一致性检验报告。

（4）檢验方法的验证。首先，准备一些原始文件并制作文件碎片存放在测试检材中。其次，模拟文件碎片被破坏的情况。之后，从检材中提取可能的文件碎片。最后，使用文章提出的检验方法来检验提取出的文件碎片与原始文件的一致性。通过测试发现：以扇区为单位的方式进行遍历可以大幅提高效率，但是部分情况无法匹配命中；逐字节进行遍历执行速度很慢，但是得到的检验结果精度很高。因此，提取出的文件碎片比较大的情况下，应当优先考虑以扇区为单位构建散列表和遍历文件碎片，否则应当考虑缩小N值并进行逐字节进行遍历。

4 结束语

文章基于散列值的文件碎片与原始文件一致性检验方法可以检验出文件碎片是否与原始文件部分匹配，并可以量化的给出一致性检验结果。由此可见，该方法解决了在检验过程中遇到检材被破坏的情况下检验检材中的文件碎片与原始文件一致性的问题。