红米3打开usb调试模式:NTFS文件系统的数据恢复程序设计

来源:百度文库 编辑:偶看新闻 时间:2024/03/29 18:39:47
   本页导读:系统与数据恢复技术已经开始在一些高校的信息安全专业中开设,相信这将使得更多的学生不再畏惧数据恢复

系统与数据恢复技术已经开始在一些高校的信息安全专业中开设,相信这将使得更多的学生不再畏惧数据恢复,因为笔者每次和同学谈论数据恢复技术程序设计与实现,大多数人都觉得很高深,其实这主要是因为没有真正的理解文件系统的内部结构原理,而只是在上操作系统课程时,略微学习了一些文件系统的组织结构、功能等,因而,就无从谈起数据恢复程序设计了。
其实笔者在2009年第1期上深入地分析过基于NTFS的数据恢复技术,但当初笔者是第一次在黑防上发表文章,认为读者们应该都具备一定的数据恢复技术,所以没有从文件系统内部结构开始分析,而是直接与读者们交流了笔者实现数据恢复程序设计时采用的关键技术,可能很多读者都没有理解清楚。下面笔者从NTFS的内部结构原理开始分析,然后逐步过渡到数据恢复程序设计的实现,希望本文的介绍再加上2009年第1期的《自主开发专业数据恢复软件》,能使读者真正地理解NTFS下的数据恢复技术,并开发出自己的专业恢复软件。
本文将分三个小节进行阐述,其一,深入分析NTFS文件系统的内部结构原理,包括主控文件表MFT、NTFS下的各重要属性及其索引记录与目录结构等;其二,阐述文件删除后可恢复性原理,通过实例对比分析文件删除前后MFT各重要属性的变化;最后重点分析NTFS下已删除文件的数据恢复程序设计,提出一种已删除文件目录树重构的算法,及其已删除文件的数据恢复算法,并澄清了主控文件表(MFT)80属性中数据运行的存储原理。(注:数据恢复关键代码已在2009年第1期给出,本文的意义主要是深入阐述恢复技术核心原理,这是必须的,否则初学者无法看懂01期的代码,希望想深入了解恢复核心技术的读者认真阅读)。

NTFS文件系统内部结构原理
NTFS文件系统的一大特点是所有的数据,包括系统信息,如引导程序、记录整个卷的分配状态位图等都以文件的形式存在。MFT是NTFS卷结构的核心,系统通过MFT来确定文件在磁盘上的位置以及文件的所有属性,MFT是一个与文件相对应的文件属性数据库,它记录了除文件数据信息外的所有属性(包括文件的MAC时间、文件名、文件的父目录MFT参考号等),甚至当文件内容很短时,其内容直接在MFT的数据属性中存放,不再额外占用簇空间。这一点就有别于FAT系统了,在FAT结构中,即使文件很小,也必须占用1个簇的空间,这其实是很浪费磁盘空间的。读者可以自行使用WinHex软件测试(WinHex软件是数据恢复程序设计开发的必备工具)。
1.MFT结构分析
每个文件都与MFT表一一对应,而文件删除、修改等操作都在MFT表中得到了体现,故我们首先必须分析出MFT结构。同样还是采用WinHex软件进行分析。MFT由两个部分组成,即MFT头(也称文件记录头)和属性列表。MFT头的长度和偏移的数据含义是固定不变的,而属性列表则是可变的,其不同的属性数据有着不同的含义,后面将对其进行具体的分析。下面先分析MFT头结构中主要的偏移位置,即笔者认为在数据恢复程序设计中必须考虑的偏移位置。
(1)文件记录头前四个字节的值总为0x454C4946H,标识其为MFT记录表项。
(2)偏移14H处,记录了MFT头的总长度,即MFT中第一个属性流的开始。故在程序设计中,即可采用条件语句IF(strcmp(MFTFlag,"FILE") != 0 || *(LPWORD)(lpBuffer + 0x14) ==0)来判断当前读取的文件是否为MFT记录表项,若非,则直接忽略此文件(其中,MFTFlag表示MFT头最前面四字节值;lpBuffer表示MFT的起始偏移)。
(3)偏移16H处的值为标记字节,具体含义为:00H表示已删除的文件,01H表示正常的文件,02H表示已删除的目录,03H则表示正常的目录,故偏移16H处的值可用于判断此MFT表项是否为非目录文件且是否已删除。
(4)偏移18H处四字节,记录了MFT表项(即记录头和属性)的总长度,通过获取此值就可判断MFT表项的结束偏移位置,其中MFT的结束偏移处的标记为FFFFFFFFH,但在NTFS卷的一些MFT中有时会出现不止一个FFFFFFFFH的情况。
属性列表也被细分成了两个逻辑组成部分,即属性头部和属性数据,其中属性头部标识了属性的类型、属性数据的相对偏移及其长度。因MFT大小只有1KB,故可能导致有些属性并不能完全存放在单个的MFT表项中,NTFS采用了簇运行列表结构(runslist),将不能完全存放下来的属性值采用了多个簇分开存放,这些簇在物理上可以不连续,故NTFS引入了LCN、VCN来定位簇号,此类型的属性在NTFS卷中称为非常驻属性,反之则为常驻属性,其中10属性、30属性、90属性总为常驻属性,而用于反映数据存储位置的80属性则常为非常驻属性。下面深入地分析与数据恢复相关的属性结构。
2.NTFS下重要的属性结构
1)10属性分析
10类型属性即$STANDARD_INFORMATION属性,为文件的标准信息。包括一些基本的文件属性,如只读、系统、存档、隐藏及MAC属性。其中,相对属性头的偏移14H~15H两字节值为10属性值的开始偏移,偏移04H~08H四字节值为10属性的总长度。
获取与文件相关的MAC时间。MAC日期与时间相对属性值的偏移分别为00H、08H、18H处,且均占8个字节。MFT表项中的MAC采用64位即8个字节来表现,存储格式为Coordinated UniversalTime(UTC),其精确度为100ns,且是从1601年1月1日00:00:00开始为起点。程序设计中,采用结构体FILETIME即可存放64bit的MAC时间,然后再调用Microsoft提供的上层API函数FileTimeToSystemTime,将UTC时间转换为本地时间即可重现文件的MAC日期及时间。
2)30属性分析
30类型属性即$FILE_NAME属性,用于存储文件名,总为常驻属性,其相对属性头的偏移代表的含义和10属性一样,不再赘述。属性值中包括父目录的MFT参考号、文件名,获取父目录的MFT参考号。MFT参考号即MFT的相对$MFT表的序号,即给定一个MFT参考号N,即可求出此文件MFT表项在MFT区域的物理位置,N对应的MFT表项的物理扇区数=N*2+BPB_MFTStartClus*8。其中,BPB_MFTStartClus值表示NTFS指定分区的MFT起始簇,可以从BPB结构体中获得。上式表明,已知父目录的MFT参考号即可映射到其父目录的MFT表项位置,从而可以获取父目录MFT表项的相关属性信息,故在程序设计中可以依次的向上搜索出整个目录树。
30属性值偏移00H处开始,共8个字节,即为父目录的MFT参考号。在程序设计中,其实只需要读取前4个字节内容,因为4个字节最大值即为FFFF FFFFH,折算后该逻辑分区大概为4TB大小,这在目前是不可能存在的,所以不需要考虑后四个字节。
获取文件或目录名。NTFS卷中文件名采用Unicode编码,每个字符占两个字节。在30属性中,文件名的首个字符从属性值偏移42H开始,字符总数记录在偏移40H处,故借助这两处的偏移值,即可准确的读取文件或目录名。但有些MFT表项中会出现两个30属性,前者用于兼容8.3格式文件,假设文件名为recovery.txt的文件,在首个30属性中,其文件名则为RECOVE~1.txt,共12字节;后者用于记录文件或目录的长文件名,如图1所示。
 
图1 Encase6_en.ppt文件的MFT表项30属性结构
由图可知,在实现数据程序设计编码时,需要判断MFT表项是否存在两个30属性,若存在,则直接跳过首个30属性,分析后面的30属性,这样才可完整地获取文件或目录的文件名。
3)80属性分析
80属性即$DATA属性,用于存放文件真实数据或文件数据存放的物理偏移位置。80属性可为常驻属性也可以是非常驻属性,取决于文件数据大小。当文件数据很小,能直接在MFT中存放时,则为常驻属性;反之,则为非常驻属性。常驻80属性,属性头偏移10H~13H处的值为文件数据所占字节数,偏移14H~17H处的值为文件数据存储的起始位置,故读取这两个偏移处的值即可以直接获取文件的真实内容。需要特别注意的是,笔者将自己研发的数据恢复软件进行过大量测试,发现编码设计时需要考虑一种特殊情况,当文件数据某一位置x处对应的值为0x00H时,则需要将MFT头部偏移32H、33H这两个字节的值来分别填充x-1与x位置的值。
非常驻80属性。当文件很大时,则会在属性值位置记录文件数据的簇运行列表(Data Runslist),这个列表直接反映了文件数据是否离散存储、占用的簇数及其簇的物理偏移位置。非常驻属性头偏移20H处的值记录了数据运行(DataRuns)的偏移地址;偏移04H处则记录了属性的总长度。故将偏移04H处的值减去偏移20H处的值即可得到数据运行列表所占字节数。下面给出数据运行列表的一般结构图,如图2所示。
 
图2 数据运行列表的基本结构
数据运行列表中第一个字节如31,其低4位为表示运行所占用的簇数在此运行中占用的字节数,高4位表示运行的起始簇号在此运行中所占字节数,若存在多个数据运行,则下一个运行的起始簇号是相对上一个运行的首簇号来计算的。但需要澄清的是,每个簇运行中的运行起始簇是如何相对上一个簇运行的起始簇号,这里并不是一种简单的相对偏移关系。 实际上,数据运行核心存储原理需要分为多种情况考虑。
Normal, Fragmented(正常的碎片文件)
Normal, Scrambled(正常的零乱文件)
Sparse, Unfragmented(稀疏的正常文件)
Compressed, Unfragmented(压缩的正常文件)
笔者这里只举一个特例进行分析,下面的数据运行为正常的碎片文件,数据运行列表中各运行的分析结果如表1所示。
Data runs: 11 30 60 21 10 00 01 11 20 E0 00
Regrouped: 11 30 60 - 21 10 00 01 - 11 20 E0 – 00
Num Group Header Data
  Length size Offset size Length Offset
1 11 30 60 1 byte 1 byte 0x30(1byte) 0x60(1 byte)
2 21 10 00 01 1 byte 2 bytes 0x10 0x160(0x100相对0x60)
3 11 20 E0 1 byte 1 byte 0x20 0x140(-0x20相对0x160)
4 00 End
表1 上例的数据运行列表解析
在第3行中,数据的起始簇偏移其结果为何会是0x140。如果直接是相对上一个簇运行的偏移,则其值应该为0x100+0xE0=0x1E0。实际上,相对偏移是建立在一个取模运算之后,具体解析为:设数据运行中文件的起始簇号为N,则若N占1个字节时且N>0x80H,则取负值,N=(N mod0x80)–0x80;若N占2个字节且N>0x8000,则N=(N mod 0x8000)–0x8000;若N占3个字节且N>0x800000,则N =(N mod 0x800000)–0x800000;依次类推,则可以准确的解析出每个簇运行的起始簇偏移。
4)90属性分析
90类型属性,即$INDEX_ROOT,为索引根属性,该属性是实现NTFS的B+树索引的根节点,包括标准属性头、索引根和多个索引项,显然,只有目录文件才拥有90属性。紧跟索引根的是索引头信息,偏移00H处为第1个索引项的偏移(注:此偏移相对此位置开始)。程序设计中,获取第一索引项的偏移值后,可直接转向索引项。在每个索引项中,偏移00H、10H处分别记录了此文件的MFT参考号及其父目录的MFT参考号;偏移08H处则记录了每个索引项的大小,故可通过索引项大小转向到下一个索引项,再结合属性头偏移04H处描述的90属性总长度,即可获取该目录下的所有文件及子目录的MFT参考号。
但当目录下包含大量的文件及子目录导致MFT表项中不能够全部存放时,就会有两个附加的属性出现,即索引分配属性和索引位图属性。索引分配属性是用来描述B+树目录的子节点的;索引位图属性描述的是索引块的索引分配属性使用的虚拟簇号,则会引入索引分配属性,即$INDEX_ALLOCATION属性,也称为A0属性,该属性的结构与80属性的非常驻属性结构完全相同。下面给出一个基本的根目录MFT表的结构,如图3所示。
 
图3 NTFS分区下根目录MFT表项的结构
3.树形目录结构
当创建一个目录文件时,NTFS必须对目录中的文件名进行索引。目录的MFT表项会将其目录下的文件名和子目录名进行排序,并保存到90属性中,但对大目录而言,则会引入A0属性,A0属性实际上存储了簇运行列表(Runslist),其结构与80属性中的数据运行结构完全一样,描述了运行簇的起始偏移及簇数。通过这两处的值即可定位到存储在大目录下的文件及目录的物理位置,即索引缓冲区(INDX结构)。
索引缓冲区大小固定为4KB,采用B+树结构实现,极大地提高了查找文件或目录项时所需要的磁盘访问次数。B+树索引由两部分组成,上部分为索引,下部分为顺序集,数据内容记录均在叶子节点,索引仅起路标作用。下面对INDX结构中主要的偏移进行分析。
索引结构中每个索引记录由一个标准的索引头和一组包含索引关键词与索引数据的块组成,索引记录的大小一般为4KB,其大小在BPB结构体成员BPB_ClusPerIndexBloc中定义。标准索引头结构前四个字节总为“INDX”,偏移18H~1BH记录了第一个索引项在INDX结构中的偏移,偏移1CH~1FH则记录了此索引结构的总大小。故程序设计中可直接转移到索引项中获取INDX结构中的所有索引子项。
每个索引子项中,记录了文件及其父母的MFT参考号、文件的MAC日期与时间、文件名等相关信息,前三项在索引项中的具体偏移位置分别为00H~07H、10H~17H、18H~30H。通过文件的MFT参考号可找到自己在MFT区域中的MFT表项,根据10属性、30属性、80属性读取文件的重要信息,若为目录文件则需要读取90属性甚至A0属性,从而定位文件的数据信息存储在分区中的物理位置或目录下文件及其子目录在分区中的物理存储位置。
实际上,NTFS的目录树结构也是倒型目录树结构,依旧是通过BPB结构体来得到目录区的存放位置,从而读取目录中的文件及其子目录,再借助各自的MFT参考号转向MFT表项来获取文件数据或者目录下文件及子目录的物理存储位置。与FAT文件系统对比分析发现,FAT文件系统是通过目录中的首簇号映射到FAT表,通过FAT表得到文件数据的各簇号或者目录下文件及子目录的簇号;而NTFS系统则是借助MFT表来定位文件或目录的物理存放位置。只不过FAT表项需要多次的映射,而MFT表一次即可完成全部映射,它们的目录树构建对比分析图如图4和图5所示。
 
图4 FAT结构中构建目录树基本算法       图5 NTFS卷中构建目录树基本算法

NTFS下文件删除前后MFT表对比分析
在NTFS卷中删除一个文件时,系统至少在三个地方做了改变。其一,文件的MFT头偏移16H处的字节值;其二,父目录MFT表项中的90属性或者A0属性值;其三,位图元数据文件$Bitmap中把已删除文件所占簇数对应的位置清零,以便在新文件没有足够的新空间时可直接覆盖已删除文件所占的磁盘空间。
笔者下面将在一个新的NTFS分区中做实验,将文件删除前后,其对应的MFT表项各属性值及父目录MFT表项相关属性值的变化进行对比分析,为数据恢复程序设计实现小节做铺垫。为了更清楚的理解文件删除后的MFT变化,下面分两种情况考虑,一是将目录及目录下的文件及子目录一并删除;二是只删除目录下的文件。
目录和目录下的文件及子目录一并删除。在NTFS卷分区中存放了一个名为Experiment的目录,Experiment目录下存放了5个文件,并分别命名为abc.txt、bde.pdf、fgh.doc、klm.ppt及pku.jpg。Experiment目录删除前后,其相应的MFT表项前后变化如图6和图7所示。
 
图6 Experiment目录删除前其相应的MFT90属性信息
因为图片大小的原因,这里给出了90属性全部内容,需要了解整个MFT表项的变化,可以借助Winhex软件自己做实验,比对删除前后的整个MFT。从上图中可以看出,Experiment目录中所有的子文件的索引项都在90属性中存储着,那么正常的目录树构建就可直接从根目录区开始不断的深层次去寻找子目录下的所有文件,最后构建成一颗倒型的目录树,具体操作流程见图5。
 
图7 Experiment目录删除后其相应的MFT90属性信息
观察图7中的90属性,物理位置0x0C00079C0处的值为第一个索引子项的偏移,其值为0x30,而0x0C00079C0+0x30=0x0C00079F0,查看0x0C00079F0处的值,发现其值为0xFFFFFFFFH,表明90属性已经结束,故90属性下的所有索引子项均已删除。因为Experiment目录下只有5个文件,故其MFT表项中没有涉及到索引分配属性,即A0属性。那么当Experiment目录下存有大量文件及子目录时,A0属性的簇运行是否会随着目录的删除而被清空呢?笔者通过大量实验发现,在一般情况下是不会清空的,除非此MFT表项已经被清空。
针对只删除目录下文件的情况,同样其90属性下描述此文件的索引子项内容也会被清空,这里就不再举例说明。
总之,在NTFS卷中,虽然文件被删除了,但其MFT表项并没有清空。不过删除文件的同时,MFT被清空的可能性也存在,在极端情况下,如系统分配给MFT的空间已经接近用完时,系统在删除文件的同时也会将MFT清空,并直接用其他文件的MFT覆盖该文件的MFT。一般情况下,只要MFT表项没有清空,则文件MFT表项中80属性值就不会清空,也就是说文件数据还存在磁盘上,故文件数据就存在恢复的可能。

数据恢复程序设计关键技术分析
每个目录及文件都存在至少一个MFT表项,那么只要遍历所有的MFT表项,读取它们所包含的重要属性,即可判断文件是否删除并获取文件名、文件的数据簇运行等等。那么如何遍历MFT表项呢?是不是从第一个非元文件开始依次遍历MFT表项,直到读取的起始位置不再表示FILE0为止呢?实际上,笔者通过实验发现,NTFS卷在很久没有进行磁盘整理的情况下,经常会出现MFT碎片,即存在物理上不连续的多个MFT子区域,因而连续的遍历MFT表项是不可行的。有人提出了一种通过遍历整个分区,来查找不连续的多个MFT区域,但此方法需要耗费大量的扫描时间,当分区很大时,其扫描时间之长几乎是用户不可接受的。
深入分析MFT区域中的头几个元文件不难发现,$MFT表项中其实已经存放了所有文件的MFT表项的起始扇区号及其簇号,采用的存储方式为80属性中数据运行的结构,通过数据运行结构列表即可判断MFT是否存在碎片,如图8所示。
 
图8 NTFS卷某分区$MFT表项的30属性及80属性信息
从图8可知,上图的分区存在MFT碎片,因为80属性下有两个数据运行结构,分别为32 DC 07 00 00 0C和32 30 01 AE 5B0E。由前一个运行结构可知,第一个MFT区域的起始簇号为0C0000H=786432,正好就是图8最左边的首个簇号,故只需读取元文件$MFT表项中的80属性,解析出数据运行列表中每个结构的起始簇号及簇数,就可快速遍历完NTFS卷下所有的MFT表项。
构建已删除文件的目录树。通过遍历NTFS卷下所有的MFT表项,就可很清楚地判断文件是否删除及文件名、文件数据起始簇号、簇数等等。那么如何将已删除文件及目录组合起来呢?笔者采用的是从目录树的底部开始逐渐往上构建整个目录树。算法基本流程如下:
(1)读取$MFT表项中80属性下的簇运行列表,获取每个簇运行结构的起始簇号与簇数,再根据首簇号和簇数,循环遍历NTFS卷下每个簇运行结构中所有的MFT表项。
(2)读取MFT表头,判断文件及目录是否删除,若目录及文件未删除,则直接忽略此MFT表项,转下一个表项;不然,则new一个新节点结构,获取表项中30属性下的文件名或目录名及父目录的MFT参考号。
(3)若父目录的MFT参考号不是0x05(即根目录下的文件或子目录),则转步骤(4);然后再判断此MFT对应的是文件还是目录,若为非目录文件,则读取80属性值,获取文件数据或文件数据的首簇号及簇数,存储到新节点结构体中,然后将此节点插入到目录树中;若为目录文件,则直接将此节点插入到目录树中。
(4)根据父目录的MFT参考号,读取每个父目录的MFT参考号,获取目录的文件名,然后再调用搜索函数,在已部分构建的目录树中寻找此文件是否在目录树中,若没有搜索到,则new一个新节点,并将文件的文件名、文件及父目录的MFT参考号分别保存在该节点中,再判断此目录是否为根目录,若非,则保存此节点到目录树结构体的Vector数组中,然后递归调用,转步骤(4)继续读取其父目录的MFT号,若为根目录,则将此节点插入到目录树合适节点下;若搜索到了,则直接返回。
这样,就可以全部获取到NTFS卷分区中所有的已删除文件及目录,并构建好整个目录树结构。下面用图的方式来表示目录树的构建算法,如图9所示。
 
图9 NTFS下已删除文件目录树重构算法
写着写着就这么多了,笔者也很想简单描述,但数据恢复技术难点就在于理解这些核心技术原理,不能再简略了。阅读到这里,读者可能在想,扫描出来的文件如何插入?采用什么树形结构来实现?这些在第1期上已经给出了解析。OK,核心技术就这么多了。读者有什么新的想法,欢迎与我交流。

小结
数据恢复技术实现是一个难点,但只要深入了解其内部结构原理,再加上一定的C++编程经验,相信都能编写出自己的数据恢复软件。