基于包结构的数据恢复技术

摘要

数据恢复是尚未克服的难题，由于众多文件系统对基本存储单元的集中管理，使得磁盘灾难带来的损失不可挽回。常见的文件系统FAT、NTFS、LINUX、NETWARE的存储都是原始数据方式(RAW)方式，没有特别的标记和序号，文件碎片(fragment)造成文件的存储单元分布是杂乱无序的。一旦文件分配表遗失，即使磁盘数据可以访问，数据也无法有效恢复。本发明借鉴IP包处理分段的概念，提出了一个切实可行的应用方案：统一数据存储协议(General Data Storage Protocol)，在磁盘的每一个基本存储单元内封装一个文件包头，将文件碎片有效地组织起来，不再仅仅依靠文件分配表，以方便完成逻辑故障引起的数据恢复。对于各操作系统的目录，GDSP目前用文件的方式来对待。

说明书

技术领域

本发明涉及计算机数据安全领域，是一个应用包结构的数据恢复技术。

背景技术

由于计算机数据的重要性，目前已经有不少数据备份和数据恢复技术。前者通过在正常时存储一个以上的拷贝，在故障发生后能够还原到备份时的状态，优点是能够记录数据的阶段性变化，缺点是成本大，备份时间长，备份与还原有时间差。例如隐藏分区备份、镜像文件备份、多种媒体备份等。后者是针对只有一份数据的情况，在故障发生后进行“事后补救”，综合运用硬件技术和软件技术将异常数据调整为有效数据。优点是无备份成本，无备份时间消耗，缺点是只能恢复数据到一个状态，对于用户数据的阶段性变化无能为力。例如电路板更换、无尘环境开盘检修、反删除、反格式化、分区修复、文件修复等。另外有一种镜像技术，介于备份和恢复之间，如磁盘镜像、双机热备份等，能够以多份冗余数据预防硬件故障，其特点是备份与正常操作同时进行，一份数据发生硬件故障不影响其他的数据，不需要恢复和还原，但是成本最高，不能应付逻辑故障。

对于逻辑故障的恢复的主要原理是，首先尽量搜寻磁盘上的分区和卷的信息，按照原来文件系统进行“分区恢复”、“丢失文件恢复”、“格式化还原”等等；其次，如果系统还原都不能进行，就在没有分区的情况下，对整个磁盘的原始数据(RAW)进行分析，假设所有文件都是顺序排列，按照其所掌握的文件类型和结构来找寻特征字符，获得文件的假设起止位置，分别将其中数据保存为单个的文件。但是由于文件碎片(fragment)的存在，成功率较低。除非从来不进行删除文件的操作，较优秀的软件可以完成大部分的恢复工作，否则，完全恢复文件碎片是不可能的。    

本发明是针对两种情况的数据恢复技术，一是在磁盘物理性能正常的情况下，逻辑故障导致的数据失效，如格式化、文件系统崩溃、分区表被篡改等；一是在文件系统关键部位的磁盘介质小范围物理损坏而导致的文件系统崩溃。

发明内容

放眼望去，一个失去文件分配表(FAT或者BITMAP)的卷包含着许多大小等于基本存储单元的文件碎片，就如同Internet中传送的纷杂的IP包。不同之处在于IP包有明确的识别号和分段号，而文件碎片全都是RAW数据。结果碎而多的IP包能够被正确地解包、重组，大而少的文件碎片却难于恢复。

鉴于IP包结构在Internet上的成功，结合到文件碎片的无序排列，本发明针对磁盘数据恢复，提出一种新的协议：统一数据存储协议(General Data Storage Protocol)，简称GDSP。该协议将上层应用程序的写盘数据打包封装，存入磁盘；也可以将磁盘上封装的数据解包，并还原后的资料将交付上层应用程序。

GDSP采取了积极主动的方式对磁盘数据进行有序处理，防止出现在面对有用的数据却一筹莫展。类似于Linux的VFS，在每个操作系统中加入一个过滤驱动程序(GDSP层)，这使得文件的存储不再完全依靠操作系统的集中管理，增强了冗余和容错性。

以下是GDSP协议的格式定义，参见说明书附图。

Version：4bits

版本，占用4个位，允许有16个不同的定义，分别说明该条目在长度(Length)内的选项，加上NextOPT所调用的附加空间，足够表示更复杂的应用。

Length：4bits

长度，表示该包头占用多少16-octet(即128位)。在使用GDSP时，不建议使用太小或太大的单位，在目前文件大小一般不超过232字节的情况下，128位是一个合适的选择，128位占用16octets。

Block：4bits

卷基本存储单元的大小，可以表示16个值。该值加上9后作为2的幂即为单元大小的字节数。如果单元为32K，即2¹⁵字节，该值为6。磁盘最小的单元是512字节，即2⁹字节，该值为0。NTFS、FAT32和FAT16的最大单元是64K，NetWare也是如此，LINUX的单元固定为1K。

NextOPT：4bits

附加的包头，表示在本包头后面还有扩展包头。允许有15个不同的定义，“0x1”表示附加的内容是扩展64位的文件系统，“0xF”表示没有附加的内容。结合Length可以得到附加包的长度。

注意每个附加的包头都有NextOPT项，类似于数据结构中的指针，可以连接到下一个包头。例如：如果图4中的NextOPT为“0x2”是，表示后续的是一个文件名包头，如图3所示，该包头可以容纳15.5个字符的文件名，结合Length：4bits，连续使用扩展文件包头的话，一共能够存储232个字符的文件名。对于某些情况，文件名可能包含了十分有用的信息，这些信息在文件内部不一定能找到，如果文件数量巨大的话，保存足够长的文件名是有意义的。考虑到对于所有的文件碎片来说，文件名是唯一的，所以该扩展包头只出现在第一个文件碎片。

Extension：16bits

扩展名，由大写英文字母表示，保存该文件的特性。这是GDSP核心项，Volume、Identification、Extension、Fragment四项可以唯一地确定一个磁盘上的任意一个文件。如，大写英文字母“A”的ASCII码为0x41，“Z”为0x5A，变化范围是26，数目不超过2⁵，所以将每个字母的ASCII码与“0x1F”做逻辑与运算后，三个字母只需要15位空间。恢复时，加上“0x40”，即可得到原来的ASCII码。例如，图4中“.EXE”。

由于文件类型识别效率不高，而且繁琐，明确地将原来的文件类型表示出来十分有必要。文件识别牵涉到许多技术和非技术的问题。首先，必须解析文件的结构，确定文件的起止标志，作为数据恢复的依据。但是这涉及到每个公司的私有版权，多数文件格式受到版权保护，无论是解析还是获取授权，单价不菲。其次，多数文件的前后顺序有相关性，中间如果有空缺的话，会造成整个文件无法使用，如：WORD文档、ZIP文件、JPG图片等，这与普通的文本文件大不一样。

目前各种操作系统常用的文件类型不下1000种，如果要把全部标志都纳入恢复工作，计算则太大。其次不是每种文件都有标志可以判定。再次，在文件碎片存在的情况下，即使采用上述头尾标志并不能完整地获得完整的文件。因此，在GDSP之间以尽量少的代价保存文件类型的信息可以大大减少恢复工作的困难。

该项之所以要在每个文件碎片标志出来，是因为扩展名非常重要，文件名可有可无，但是没有扩展名，数据恢复是不成功的。在文件碎片不能被完全找回的情况，某些文件(象文本发明件、DBF等)仍然可以正常使用。

Age：16bits

寿命，表示该单元的使用次数，范围从1到65535，反映了MTBF数据。如果使用次数超过了一定的阀值，应该考虑将该单元的数据转移到一个值少的单元，如果该值达到了2¹⁶-1，应该被视为坏扇区而尽量避免使用。

由操作系统的磁盘操作模式以及实践经验，磁盘上的扇区使用频率是非常不均匀的。例如，Windows98以前的写操作由于默认使用卷空间内的第一个有效单元，造成了卷的尾部几乎没有机会进行操作，而磁盘的某些部位频繁地被读写，硬件故障的发生率比较高。而同时，操作系统又顽固地在固定的位置寻找MBR、PBR、FAT等信息，一旦这些地方因为使用率高而产生坏扇区的话，整个卷的信息都将崩溃，无法使用。

Volume：8bits

卷编号，从1到254，能够允许在一个磁盘上有254个卷。这是GDSP核心项，Volume、Identification、Extension、Fragment四项可以唯一地确定一个磁盘上的任意一个文件。在一个海量磁盘中，也许存在32个以上的卷，每个卷上都应该有满足操作系统要求的文件标志Identification，卷与卷之间可能存在相同的Identification，所以Volume非常有必要参与识别文件碎片。当然，如果统一用磁盘的绝对扇区编号来做Identification，Volume可以省略。

Security：8bits

安全项，这部分可以考虑用来做安全保密的设置，如MD5，或者其他有有助于保密的信息。说到保密，一般人只注重于系统的口令和网络上的访问权限，很少有人考虑本地数据资料的保密。本发明证明，目前的文件系统都是用RAW方式存放文件，任何直接对磁盘的访问都可以造成泄密。为了在GDSP中实现本地数据的保密性，可以考虑用该项将GDSP包中的数据全部由明文转换为密文，或者整个卷使用统一的密码来读取文件，或者每个文件都可以使用自己的加密方式。

Identification：32bits

文件标志符，可以标志2³²-1个文件。这是GDSP核心项，Volume、Identification、Extension、Fragment四项可以唯一地确定一个磁盘上的任意一个文件碎片。实际上，目前的操作系统多是32位的操作系统，只允许2³²的文件数目。

该项值可以随机地由哈希函数产生，也可以由GDSP顺序产生。尽管可能性很小，当有必要用到64位的时候，可以利用NextOPT项获得额外的空间来保存大文件的Identification。当然也可以考虑用磁盘的绝对扇区号来完成，但这会造成大量编号的浪费。

Fragment：24bits

分段，表示该存储单元在文件中的位置，从1到2²⁴，以Block为单位。这是GDSP核心项，Volume、Identification、Extension、Fragment四项可以唯一地确定一个磁盘上的任意一个文件。文件最大可到2²⁴*2¹⁶字节，能够满足32位的文件系统和一般的多媒体文件。不过NTFS号称支持2⁶⁴-1字节大小的文件，为了满足这一点的话，指针NextOPT需要设置为指向如附图2所示的结构。

Checksum：8bits

校验和，把整个GDSP包头的值以octet为单位校验一次，也可作为数据恢复时的比对工具。校验很重要，由于GDSP各项之间并没有重复的定义，无法互相检查冗余，有必要对整个GDSP包头采用一定的检验措施，以保证数据恢复的正确性。考虑到算法和实用性，可以只对四个核心项Volume、Identification、Extension、Fragment校验。其次，该项在恢复数据时，对搜寻磁盘上的GDSP包头起到定位作用。

具体实施方式

本发明类似于IP在协议簇中的作用。本发明在操作系统中插入一个过滤层，接管上层API对的磁盘操作的请求，并以GDSP打包后，再把读写任务交给底层的硬件驱动。对于上层API来说，GDSP是透明的，这一点可以方便地应用到Linux的VFS、Windows 95的VXD以及Windows 2000的WDM。

在Linux中，承上：VFS接管所有磁盘读写任务，是其他子系统与EXT2、MINIX、MSDOS等逻辑文件系统的接口；启下：对逻辑文件系统来说，VFS是一个管理者。所以，上层子系统并不关心硬件层的操作，只要对VFS做适当的修改，就可以在其中实现本发明。而同时，Linux是一个源代码开放的操作系统，本发明完全可以在改写VFS时得到实现。

在Windows系列中，Microsoft公司也提供了诸多软件开发工具(SDK)让用户自己来扩展系统工具和底层驱动。

Windows 9x是通过虚拟机VM(Virtual Machine)环境来确保其兼容和多任务特性，VxD(Virtual Device Driver)在虚拟机管理器VMM(Virtual Machine Manager)的监控下运行的虚拟设备驱动程序，而VMM实际上是一个特殊的VxD。VMM执行与系统资源有关的工作，提供虚拟机环境(能产生、调度、卸载VM)、负责调度多线程占先时间片及管理虚拟内存等工作。VMM和VxDs构成了Win95的ring0级的系统核心(应用程序运行在ring3级，ring1、ring2级未被使用)，具有系统的最高优先权。

在Windows2000及以后的版本中，VXD已经被淘汰，取而代之的是层次关系更加清晰明了的WDM(Windows Driver Mode)。WDM作为编写驱动程序的规格，WDM负责将I/O请求传送至系统，由驱动程序进行相应的处理，WDM在很大程度上和Windows NT相同，基本的IRP指令基本相同。但也存在一些不同，首先，WDM驱动程序必须有一些动态的请求如即插即用，第二，Windows NT依靠HAL同硬件交互信息，而WDM则由系统总线驱动程序作大量的工作。

一个驱动程序必须和其他驱动程序交互信息，接收其他驱动程序的IRP指令，或向其他驱动程序发送IRP指令。这种结构最基本的类型是驱动程序类和最小驱动程序。WDM环境下的驱动程序是负责系统底层的处理和在硬件总线上配置设备，驱动程序通过发送IRP和总线驱动程序交互信息，这样，驱动程序不直接交互信息，而是通过总线驱动程序进行。

按照这种模式，本发明更加容易在其硬件抽象层和WIN32子系统之间加入自己的驱动程序。如何在Windows体系中加入用户自己的驱动程序，这已经是本领域的基本技能，这里不再多言。因此本发明完全可以在操作系统的上层应用和下层驱动之间，改写默认的驱动程序或者加入自己开发的过滤驱动程序。

对于NetWare和其他以原始数据格式存储资料的操作系统，本发明均能够利用其开发工具编写相应的过滤驱动程序，以达到透明地嵌入GDSP层。

本发明侧重于文件的数据恢复，但目录在文件系统中的地位无可替代。许多同名的文件因为目录而可以放在同一个卷里面，同时，许多应用程序完全依赖于目录的结构才得以运行。但由于目录在各个操作系统的表现形式不一致，并不象文件那样是原始数据(RAW)方式，那么在目录区实现GDSP会破坏操作系统的体系结构，即使是象NTFS或者NETWARE这样把目录也当作文件来处理的。比如，在NTFS中，目录是主文件MFT的一个分支，固定在某个扇区的位置读取关键信息，要在每个Cluster的头部实现GDSP就会改变MFT的树结构，但是要让本发明透明地嵌入MFT，不容易做到。Netware和Linux也是同样的行为。如果本发明要封装目录，就要改写每个操作系统的目录API，这可能是比较大的工作量。

考虑到多数操作系统对文件的存储是是原始数据格式(RAW)，借鉴Windows的「虚拟内存交换文件」，可以自然地采用文件的形式，取一块连续的存储空间来保存文件系统的目录。例如，分配相当数量的连续磁盘空间给一个文件GDSPFOLD.SYS，其GDSP文件包头有明显的扩展GDSP包头，表明该文件存储的是目录。

由于目录在操作系统中的增减变化很大，B⁺树是比较合适的选择。将目录集成到一个文件中，等价于一个数据结构的存储问题。这个文件仅仅用于数据恢复，只要保存尽可能少的的信息，因此有文件的分配单元或者GDSP包头的Identification信息就可以了。

在磁盘的数据都被本发明整理过，那么在能够读取物理扇区的情况下，所有文件都能够被完整地恢复到新磁盘。通过查找GDSP的包头关键信息，如Version，NextOPT等，再检验Checksum，GDSP包头可以被准确的定位。由于有GDSP提供信息，即Volume，Identification，fragment，Block，以及该GDSP所在的物理扇区位置，可以建立一个对应的数据表。对于一个40GB的磁盘，约有78125000个扇区，假设卷基本单元的大小是8个扇区的话，最多需要9765625条记录用来保存表中的信息，大小约146MB，可以单独建立一个文件来协助处理。

然后，通过类似于数据库的排序就可以找出所有文件的碎片所在扇区，进而提取到新磁盘上。对于NTFS嵌入在MFT中的小文件，也可以通过额外的算法，找到位置不在扇区头部的GDSP包头，提出这种小于728字节的文件。

附图说明

图1 GDSP包头结构

图2附加16-octet GDSP的64位包头

图3附加16-octet GDSP的文件名包头

图4文件扩展名EXE的示例。