基于集合论的E-mail碎片雕刻模型及算法

李炳龙，张传富，韩宗达，王清贤

(解放军信息工程大学，a. 四院；b. 数学工程与先进计算国家重点实验室；c. 三院，郑州 45 0004)

基于集合论的E-mail碎片雕刻模型及算法

李炳龙a,b，张传富c，韩宗达a,b，王清贤a,b

(解放军信息工程大学，a. 四院；b. 数学工程与先进计算国家重点实验室；c. 三院，郑州 45 0004)

为获取存储介质中的碎片E-mail证据，利用集合论原理对邮件碎片文件雕刻问题进行分析，确定基于集合论划分思想的碎片文件雕刻思路。设计包含预处理、E-mail文件碎片子集确定、E-mail碎片间的连接关系确定等过程的邮件碎片文件雕刻算法模型。利用十六进制编辑器，阐述E-mail文件的内部结构特征，结合碎片邮件头尾和内嵌的html文件特征，论述存储介质上碎片的属性，给出碎片间的集中特性、跟随特性、线性特性以及信息特性的连接规则。实验结果表明，碎片邮件文件雕刻算法能更有效地获取邮件证据。

E-mail文件雕刻；数字犯罪调查；碎片子集；特征标识；复合文件类型；碎片连接规则

1 概述

E-mail(电子邮件)已经成为数字犯罪取证调查领域中的重要数字证据之一[1]，美国等大部分国家已经把E-mail作为有效的数字证据[2-3]。然而，随着反取证技术的发展，E-mail证据容易遭受损坏，造成数字案件中数字证据获取困难[4-5]。因此，研究电子邮件证据有效获取技术尤为重要。

传统的数字证据获取方法是基于文件系统元数据信息进行文件恢复，但是由于大部分现代文件系统对于已删除文件元数据进行清除，以及病毒、木马等恶意软件的破坏经常造成文件系统损坏，使得该方法正变得越来越不切实际[6-7]。文件雕刻是解决在文件系统损坏情况下进行数据恢复或数字证据还原的重要技术之一，典型的数字取证工具如EnCase中具有文件雕刻功能，能够利用文件类型本身的特征信息恢复还原文件内容，但是这些工具对于存储介质中文件构成数据块在连续存储情况下可以进行有效获取。文献[8]的DFRWS Challe nge中，利用形式化方法研究了E-mail碎片文件的雕刻算法，在存储介质中连续存放情况的雕刻算法。而当文件构成数据块具有不连续的情况下，则往往会产生错误的雕刻结果[9]。针对存储介质中文件碎片情况下的雕刻技术研究较少，而且这些碎片文件雕刻算法多是针对特定类型(如RAR类型)[10-11]，具有局限性。

为此，本文利用集合论划分的思想，研究E-mail碎片文件雕刻理论与算法。对存储介质碎片文件雕刻问题进行分析，利用集合论划分思想，确定E-mail碎片文件雕刻思路，并以此为基础，设计E-mail碎片文件雕刻模型。通过分析E-mail协议特征、文件类型特征及其内部数据结构，设计E-mail文件头尾、内嵌HTML文件特征，以及碎片连接规则相结合的碎片邮件雕刻算法，并同现有的E-mail文件雕刻算法作比较。

2 E-mail碎片文件雕刻模型

2.1 问题描述

在文件系统损坏后，可假设存储介质中数据区的簇(或者数据块)称为碎片，所以存储介质可抽象为一个碎片集合：其中，li表示存储介质上的任意一个碎片；n表示集合L的大小，并且n值取决于存储介质容量以及原始文件系统在格式化时指定的簇大小，如果存储介质容量一定的情况下，簇的大小越大，则碎片集合L中元素个数就越小[7]。集合L具有如下特性：

(1)对于1≤i, j≤n ，li, lj表示集合L中的碎片，如果i≠j，那么li∩lj=ϕ，表示碎片集合L中2个不同碎片，在存储空间上不存在交集，2个碎片上所存储的文件内容不存在交集。

(2)连接性：对于1≤i, j≤n ，li, lj从文件构成角度分析，只有2种可能的连接方式，即lilj和ljli。

根据以上假设，文件可以看作为具有特定碎片构成的碎片子集合，由于存储介质中有多个文件，因此从集合划分思想，文件碎片子集和存储介质碎片集合L之间具有如下构成关系：

其中，1≤k≤m ；fk表示文件碎片子集，其本质是具有特定文件类型(如Office文件类型、Acrobat PDF文件类型等)的一个文件。所以碎片文件雕刻问题的第1步可以建立碎片集合L到文件碎片子集fk的映射，即L→fk，从而获得文件碎片子集中的所有碎片。

第2步是根据文件碎片子集的文件类型特征、内部结构特征以及存储特征，确定碎片子集中元素之间的连接关系，恢复还原碎片文件内容。

2.2 邮件碎片雕刻模型

E-mail是一个可内嵌多种文件类型构成的复合文件类型[12-13]。根据以上对碎片文件雕刻问题的描述，E-mail碎片文件雕刻可以分为2个子问题：(1)邮件文件碎片子集确定；(2)文件碎片子集中元素之间的连接。即首先从存储介质碎片集合中识别出E-mail文件碎片子集；然后利用碎片信息、E-mail文件类型信息以及存储特性，确定碎片之间的连接关系。为此，根据E-mail文件类型特征、内部结构特征及存储介质的存储特性，设计如图1所示的碎片邮件雕刻算法模型。

图1 碎片邮件雕刻算法模型

碎片邮件雕刻过程可分为3个阶段：预处理，邮件文件碎片子集确定，碎片子集元素间的连接确定。

(1)预处理：即先对可疑存储介质映像进行扫描分析，其关键是过滤掉不含有任何数据的碎片，方法是利用0/1二进制数据统计特征[7]，最终获取文件碎片集合。该阶段主要是扫描分析、提取E-mail文件类型信息，包括邮件文件头碎片在映像中的逻辑位置以及碎片中有关邮件的元数据等信息。

(2)邮件文件碎片子集确定：即首先利用邮件文件头识别算法，确定邮件在存储介质中的逻辑起始位置；然后利用邮件碎片分类算法和内嵌文件类型识别算法，确定属于该文件的其他碎片元素；最后，利用邮件文件尾部识别算法，确定该邮件在存储介质中的逻辑结束位置，并最终获取邮件碎片子集。

(3)碎片子集中元素间的连接确定：即利用碎片信息特征、E-mail文件类型特征以及碎片存储特性等，确定碎片子集中碎片之间的连接关系，进而重构碎片邮件内容信息。

3 算法实现

3.1 邮件文件头、尾识别算法

图2 邮件文件头二进制特征

图3 邮件文件尾二进制特征

邮件在存储介质中二进制的文件头碎片特征为D0 CF 11 E0 A1 B1 1A E1；文件尾部特征为63 00 6F 00 6E 00 74 00 65 00 6E 00 74 00 2D 00 74 00 79 00 70 00 65。利用这2个二进制特征，可以设计相应的存储介质映像扫描算法，确定邮件文件头和尾碎片包含的邮件元数据信息，比如邮件文件的长度、字符集、编码方法等信息，从而为后续邮件内容重构奠定基础。

3.2 基于邮件结构特征的碎片分类算法

邮件基于RFC822和MIME协议进行构建[14]，它包括2个主要的组成部分：邮件头和邮件体，所以从数据在存储介质的存储层次分析，邮件文件具有RFC822和MIME协议的分类和雕刻特征。

3.2.1 邮件头结构分类特征

通过分析RFC822规范，每一个邮件头以“字段名：字段值”的格式出现，即每一行邮件头的内容依次由字段名、冒号、空格、字段值、回车换行符组成，所以邮件头结构分类特征如表1所示。

表1 邮件头结构特征

利用邮件头结构的单个或者组合特征，有助于识别邮件碎片，以及确定邮件的元数据信息，比如对于Subject: =? gb2312?B?TUlNRdCt0unLtcP308q8/g==?=。可以推断出：gb2312部分说明邮件主题的原始内容为gb2312编码的字符文本，B部分说明对邮件主题的原始内容按照BASE64方式进行了编码，TUlNRdCt0unLtcP308q8/g==为对邮件主题的原始内容进行了BASE64编码后的结果。

在压缩机启动的过程中，出口阀门关闭，气体在出口截断阀和入口截断阀之间循环。直至喘振控制调节阀完全关闭，压缩机达到额定转速，出口阀门开启，上游系统开始持续进气，压缩机进入正常操作状态。在压缩机启动过程中，由于整个系统处于密闭循环状态，所有功率消耗大部分用于加热系统内的气体，出口气体过热引起压缩机的喘振是在启动过程中存在的关键问题。

此外，邮件头可能还包含其他格式结构特征，但是由于是可选的，因此在邮件碎片分类中只能作为辅助。

3.2.2 邮件体结构特征

根据MIME协议规范，邮件体同样由多个属性/值构成，其结构特征如表2所示。

表2 邮件体结构特征

邮件体结构特征一方面可以帮助识别、确定邮件碎片类型，另一方面该特征也提供了确定碎片之间连接关系的方法，如Content-Type:multipart/mixed; boundary="----= _NextPart_000_0050_01C"是某一个具体的Content-Type特征，其中，multipart/mixed部分说明邮件体中包含多段数据，每段数据之间使用boundary属性中指定的字符文本作为分隔标识符，边界是一个随机字符串，该字符串用来表示该部分在消息中的开始、分割以及结束标志。所以边界有助于确定碎片之间的连接关系。

基于邮件结构特征的碎片分类算法主要利用这些结构特征的单个或者复合特征进行类型判断，用以确定邮件文件碎片子集。

3.3 HTM L雕刻算法的嵌入

3.3.1 HTML碎片特征提取

HTML文件是邮件最常见的嵌入类型之一，本文主要分析嵌入类型为HTML时的雕刻算法。通过WinHex分析，HTML文件类型的头尾碎片特征如图4和图5所示。

图4 H TML文件头部标识

图5 H TML文件尾部标识

根据图4和图5给出的HTML文件起始碎片特征，可以确定HTML文件类型的起始碎片。

3.3.2 HTML碎片雕刻算法

嵌入在邮件中的文件类型理论上可以有多种，比如Office办公文档、Acrobat PDF以及图片等类型，根据HTML语法，HTML文件构成具有如下特征：对称性，嵌入性，灵活性。

为此，设计一个基于堆栈结构的HTML文件雕刻算法，堆栈用于存储可能有语法错误的标签，算法关键思想如下：

(1)识别HTML文件头碎片结构标识后，即建立一个属于本次雕刻的堆栈数据结构。

(2)扫描HTML碎片数据并分析，如果是＜a-z＞标识，则可能是一个标签，此时将相关标签入栈。

(3)继续进行扫描分析，如果出现＜a-z＞这样的标识，表示可能是某个标签的结束，此时则弹出栈顶数据，与新出现的标签进行比较，如果2个标签相对应，则表示结构正确，返回到步骤(2)继续进行；否则，执行步骤(4)。

(4)如果期望的标签在规定最大限度内仍没有出现，则雕刻算法将放弃，并且雕刻算法增加相应的错误计数，然后释放它，比如这样的序列：＜a…b＞。

堆栈结构的目的是判断HTML扫描数据语法是否合理，假设所扫描数据语法正常，则最终堆栈结构将是空的，否则其中所包含的信息，则是错误信息。

该算法和现有的HTML解析器相比，更能够容忍解析过程中语法的错误特征，而更集中于HTML文件的有效性检测，从而能够提高HTML文件雕刻算法的精度，有助于数字取证调查获取更多有效的数字证据。

3.4 碎片连接特性规则

根据文件系统分配策略，以及邮件文件类型二进制特征，设计了如下规则，用于碎片邮件雕刻算法。

(1)集中特性：操作系统为文件分配存储空间时最佳原则是选择连续存储单元进行分配。此外，只有当对文件进行反复操作，比如修改、删除等，或者当存储空间不足时，才可能产生文件以碎片化存储。所以可以认为，文件的多数存储单元(或者文件碎片)通常存储在文件头碎片后续存储位置，把这种特性命名为集中特性。这个特性也可理解为局域特性。

(2)跟随特性：为了提高文件I/O访问速率，操作系统在分配存储空间时，尽可能让属于一个文件的存储单元(或者文件碎片)连续存放，即文件头存储单元后依次跟着下一个存储单元，把这种连续性称为文件存储单元之间的跟随性，即文件存储单元都跟随在文件头之后，并且连续存放。

(3)线性特性：根据存储空间的逻辑特性，存储单元在存储介质中的存放特点是以线性方式存放，设A和B是存储中的2个存储单元，A和B之间的位置关系仅有2种，即A在B的前面，或者A在B的后面，把这种存放关系称为线性特性。

(4)信息特性：每个存储单元都有可能存储有文件的信息，尽管这种信息是局部的、零散的。而文件一方面具有类型信息，也具有内容信息，并且一个文件从结构上具有完整性。所以把存储单元上具有特定文件信息的这种特性，称为信息特性。存储单元的信息特性度量还比较困难，但是有2个极端情况：1)存储单元中含有文件的许多信息，比如类型、结构、内容等；2)存储单元上根本没有任何信息，只有二进制的0和1。这种没有任何信息特性的存储单元在碎片文件雕刻过程中是不具任何价值的。

(5)无关特性：即2个不同文件碎片之间是无关的。

碎片邮件雕刻算法的核心思想是：利用文件头碎片特征信息，首先确定碎片邮件文件头位置，从而确定了碎片的集中特性，然后利用邮件碎片的内容信息、结构信息等信息属性，确定碎片的跟随特性。利用碎片的无关特性，删除掉不属于邮件文件类型的碎片信息。利用碎片的线性特性，遍历整个存储介质碎片空间，确定碎片邮件剩余的碎片信息。最后根据获得的碎片集合及其连接关系，恢复邮件内容。

4 实验及结果分析

碎片邮件雕刻算法评估尚未有确定的方法，根据经验[15-16]，为验证算法的有效性，利用公布的3个映像进行实验，映像的详细信息如表3所示。2010-nps-emails映像是用于测试E-mail地址的映像，利用设计的算法在该映像中能够发现30多个不同的E-mail地址及其相关内容，并且这些E-mail内容具有不同的编码方案，结果和2010年该网站公布的结果一致。

表3 存储介质映像来源及其他情况

值得注意的是算法还能够获取E-mail文件碎片数据，尽管这些数据无法以E-mail形式显示，但是可以确定的是E-mail文件类型的碎片数据，如表4所示，可以从中获取部分内容信息，比如E-mail文件的收件人、发件人等，这对于数字取证调查是有意义的。

表4 收发信息

2012-dfrws-challenge是2012年DFRWS公布的取证分析挑战，该映像是Android手机中的SD-Card内容，对该映像应用算法进行获取分析。能够获取犯罪嫌疑人在生前和多人通信的gmail等邮件34封，并全部恢复还原。利用十六进制编辑器对映像进行分析，可以发现有3个E-mail文件以碎片形式存在，在雕刻过程中，可以全部获取。

2009-nps-ntfs1是一个经常上网的计算机硬盘映像。使用2007雕刻算法[8]对该映像进行分析，能够找到4个MIME邮件文件；而设计的算法能够找到10个完整的邮件文件，另外，从映像中找到12个碎片邮件文件。图6显示了其中一个碎片邮件信息，虽然不能完整恢复邮件数据，但是从中能够提取出邮件发送时间、接收时间等信息，这些信息对数字取证调查也是关键的。

图6 邮件信息

此外，提出的邮件碎片雕刻算法模型中对碎片文件雕刻问题的描述以及转化，使得提出的邮件雕刻算法不但能够处理线性碎片化文件的雕刻，而且还能有效处理非线性碎片化文件雕刻问题。而利用WinHex中的雕刻算法则不能处理非线性方式的碎片文件雕刻。另外设计的算法也存在不能完整雕刻邮件碎片，但是能够有效提供邮件碎片的局部有用取证信息，比如本文的算法能够获取部分被覆盖的邮件文件，但是仅限于E-mail文件头尚未被损坏，否则找到的信息比较少，增加了算法的适用范围。

另外，在算法实验过程中发现，算法雕刻结果精度会出现乱码，比如图7展示了错误的雕刻结果，出现乱码的原因从理论分析可能归结于邮件文件没有明确的结束标识，使得在雕刻时不好指定文件结束的位置，只能指定文件的大小，但这样就可能导致不能把文件的数据写完，或是多写了部分数据到文件中，从而造成乱码现象。

图7 错误的雕刻结果

5 结束语

本文利用集合论划分思想对碎片文件雕刻问题进行了抽象描述，并基于集合论划分思想，提出碎片邮件文件雕刻模型，设计邮件头尾识别算法、内嵌HTML的文件雕刻算法以及基于邮件结构特征的碎片分类算法，根据RFC822 和MIME协议规范，设计邮件碎片分类的结构特征。结合存储介质数据特征、邮件结构特征等，设计邮件碎片之间的连接规则，以及碎片连接关系算法。实验结果表明，本文算法对碎片邮件雕刻具有普遍的适应性，并能够获得较好的雕刻结果，但是对于大容量存储介质来说，算法运行速率不是非常理想。后续工作将进一步优化该算法的运行速度，并增加对其他内嵌文件类型的雕刻优化。

[1] Haggerty J, Karran A, Lamb D. A Framework for the Forensic Investigation of Unstructured Email Relationship Data[J]. International Journal of Digital Crime and F orensics, 2011, 3(3): 1-18.

[2] Lin Hanhe. Predicting Sensitive R elationships from Email Corpus[C]//Proc. of the 4th In ternational Conf erence o n Genetic a nd Ev olutionary Comp uting. [S. l.]: IE EE Press, 2010: 264-267.

[3] Gupta G, Mazumdar C, Rao M S. Digital Forensic Analysis of E-mails: A Trusted E-mail Protocol[J]. International Journal of Digital Evidence, 2004, 2(4): 1-14.

[4] Iqbal F, Binsalleeh H, Fung B, et al. Mining Write Prints from Anonymous E-mails for Forensic Investigation[J]. Digital Investigation, 2010, 3(2): 1-9.

[5] Banday M T. Analysing E-mail Headers for Forensic Investigation[J]. Journal of Digital Forensics, Security and Law, 2011, 6(2): 49-64.

[6] Fellows G H. The Joys of Complexity and the Deleted File[J]. International Journal of Digital Forensics & Incident Response, 2005, 2(2): 89-93.

[7] Carrier B. File System Forensic A nalysis[M]. [S. l.]: Addison Wesley, 2005.

[8] Cohen M. Advanced Car ving Techniques[J]. International Journal of Digital Forensics & Incident Response, 2007, 4(3/4): 119-128.

[9] Garfinkel S L. Carving Contiguous and Fragmented Files with Fast O bject Validation[J]. International Journal of D igital Forensics & Incident Response, 2007, 4(9): 2-12.

[10] Wei Yingjie, Zheng Ning, Xu Ming. An Automatic Carving Method for RAR File Based on Content an d S tructure[C]// Proc. of the 2nd International Conference on I nformation Technology and Computer Science. [S. l.]: IEEE Press, 2010: 68-72.

[11] Yoo B, Par k J, Lim S, et al. A Study on Multimedia File Carving Method[J]. Multimedia Tools and Applications, 2012, 61(1): 243-261.

[12] Conti G, Bratus S, Shu bina A, et al. Automated Mapping of Large Binary O bjects U sing Primit ive Fragment Type Classification[J]. International Journal of Digital Forensics & Incident Response, 2010, 7(8): 3-12.

[13] 张 鹏, 陈 焘, 刘宏伟, 等. 基于身份密码的安全电子邮件系统[J]. 计算机工程, 2009, 35(6): 194-196.

[14] 梁 力, 严建伟, 聂 影. 基于源地址约束的垃圾邮件过滤模型[J]. 西安交通大学学报, 2005, 39(4): 376-379.

[15] Tomar D S, Malviya O, Verma R. Analysis Framework for Quality Measurement of Carving T echniques[C]//Proc. of National Conference on Emerging Trends in Computing and Communication. Hamirpur, India: [s. n.], 2008: 421-426.

[16] Garfinkel S, Paul F, Vassil R, et al. Bringing Science to Digital Forensics with Standardized Forensic Corpora[J]. International Journal of Digital Forensics & Inci dent Response, 2009, 6(9): 2-11.

编辑 顾逸斐

E-mail Fragment Carving Model and Algorithm Based on Set Theory

LI Bing-longa,b, ZHANG Chuan-fuc, HAN Zong-daa,b, WANG Qing-xiana,b

(a. Fourth Institute; b. State Key Laboratory of Mathematical Engineering and Advanced Computing; c. Third Institute, PLA Information Engineering University, Zhengzhou 450004, China)

To acquire fragment E-mail evidence from storage medium, this paper analyzes the E-mail fragment file carving problem on the base of the set partition theory, determines the fragment file carving thought. According to the model, it designs E-mail fragment file carving algorithm model including preprocessing, E-mail file fragment subset determination, conne cted relation determination be tween E-mail fragments. By using hexadecimal editor, it expounds internal structure features of E-mail file, combined with the characteristics of fragment mail head and tail and embedded html files, discusses the fragment attributes in storage medium, and gives the adjacent rules among concentration characteristics, follow characteristics, lin ear properties and information characteristics fro m the fragmen ts. Experimental results show that the algorithm can acquire E-mail evidence more effectively.

E-mail file carving; digital crime investigation; fragment subset; characteristic identifier; compound file type; fragm ent adjacent rule

10.3969/j.issn.1000-3428.2014.05.066

国家自然科学基金资助项目(60903220)；郑州市科技攻关计划基金资助项目“基于内存及存储介质的网络取证调查系统”。

李炳龙(1974－)，男，副教授、CCF会员，主研方向：数字犯罪取证调查，信息系统容灾；张传富，讲师；韩宗达，硕士研究生；王清贤，教授、博士生导师。

2013-01-22

2013-04-12E-mail：libinglong2009@163.com

1000-3428(2014)05-0317-05

A

TP301.6