基于关键页覆写的数据清除技术

郭松辉，王玉龙，2，邵奇峰，牛小鹏，2

（1.信息工程大学，河南 郑州450000；2.信息工程大学 数学工程与先进计算国家重点实验室，河南 郑州450000）

0 引 言

目前，基于Flash［1］的移动存储设备被人们广泛使用。如何保护存储器中数据安全已成为一个重要课题，安全存储器的概念应运而生。在安全存储器的使用过程中，其数据残留的彻底清除问题容易被忽视。这对于一些数据敏感领域极其重要，因为即使是加密的数据落在攻击者手中也是不被允许的。目前，关于如何进行数据销毁的研究主要关注磁盘 （或阵列）中数据销毁问题，如采用物理消磁、多次覆写等手段［2－5］，而对基于闪存芯片的移动存储设备中数据销毁问题研究较少，现有的主要手段是通过主机对设备目标数据进行数据填充的方式来实现数据的销毁或清除。这种方法对于闪存型存储器存在两方面问题：①该方法需要通过写操作来完成，而在闪存中写操作过程繁琐，耗时较长，时间开销很大［6］；②出于对闪存寿命及磨损平衡的考虑，存储器保留有用于备份的冗余块，该方法在使用过程中会导致数据残留在备份块中。

为了避免上述问题，本文提出了一种基于硬件操作的由控制器完成的数据快速删除方案。该方案通过在固件中植入数据删除模块，在特定条件下触发，可自动执行数据删除操作。实验结果表明，采用该方案，可在文件系统不被破坏的前提下，对数据进行删除操作，无论采取软件技术还是硬件技术，被删除的数据均不可恢复。

1 Flash型存储系统原理

Flash芯片无法像磁盘一样随意读写，只能按照一定大小的地址块进行操作，因此，若想与传统磁盘设备兼容，还需借助控制器来完成。有关Nand Flash特点及存储管理方案将分别在本节的1.1、1.2小节进行讨论。

1.1 Nand Flash芯片操作特征分析

Nand Flash芯片［6］的物理结构为阵列式结构，依据其陈列的行列分布特点，在使用时划分为页 （Page）、块（Block）、区 （Zone）这3级。每64个页组成一个物理块，每1024个物理块组成一个区 （Zone）。

由于制造工艺与实现原理的特殊性，使得Flash芯片具有如下几个特点：

（1）在生产和使用过程中可能会出现无法正常使用的坏块。因此，Nand Flash 在使用时，需保留部分物理块备用。

（2）只能按块进行擦除、按页进行读写，且只能对已擦除的页进行写操作。因此，若要对物理块X 的Page N 进行修改，需先将待修改的页读入缓存修改，修改后写入一个未被使用的块中，然后再将原块中未修改的页搬移到新块中，将原物理块设置为未使用。具体过程如图1所示。

图1 修改物理页操作

1.2 基于FTL的存储管理机制

为了与传统磁盘存储设备保持兼容，闪存控制器使用一些数据结构与算法建立一个 “闪存转换层 （flash translation layer，FTL）”，向上层提供块设备接口，并对下层存储器进行有效管理。

FTL层关键作用是高效可靠地实现从逻辑地址到物理地址的寻址。基于查找表 （look－up table）的地址映射方案实现FTL层是最常用的方法。下面是一个较为有效的实现方案。

固件为每个区 （zone）建立一个一表两用的查找表gLog2Phy［］，每个gLog2Phy［］为1024项，项中各位的意义见表1。当以逻辑块地址作为索引进行查找时，可通过bit0－bit9找到当前逻辑块对应的物理块地址，通过bit10查看对应物理地址的初始化情况；当以物理块地址作为索引进行查找时，可通过bit13、bit14、bit15，获取当前物理块相关标志信息。

表1 gLog2phy［］项中各位的意义

存储空间数量的关系为：物理块＝逻辑块＋备用块＋坏块。因此，在gLog2Phy ［］中，只有0－999用于逻辑块寻址，而物理块标志信息则在0－1023中都有记录。图2给出了一个gLog2phy［］的示例。

在物理块的冗余区记录着当前块对应的逻辑块地址，若物理块未映射则地址默认以 “0xFF”填充，通过查询该信息即可获知物理块对应的逻辑地址。本文采用动态磨损平衡算法，逻辑块地址与物理块地址映射关系是动态变化的。每次执行写操作，都会申请一个新物理块，将修改内容写入到新的物理块，再将原块释放为自由块，这样就保证了每个物理块的使用次数趋于一致。

图2 gLog2Phy［］示例

2 FAT32文件系统分析

FAT32文件系统［7，8］是在闪存中使用最普遍、适配性最好的文件系统。

在FAT32文件系统中，最小的数据单位为扇区 （Sector），默认大小为512 字节；若干连续扇区组成一个簇（Cluster），是数据存储的最小单位。FAT32文件系统由操作系统引导记录区DBR （dos boot record）及其保留区、FAT 表1、FAT 表2 （FAT 表1的备份）和数据区组成，如图3所示。引导记录区记录着一些文件系统的关键信息，如：根目录首簇号、每个扇区大小、每个簇包含的扇区数等。FAT 表由FAT 表项组成，每个表项对应数据区的一个簇，每个表项为8字节，且每个表项都有一个固定的编号对应数据区的一个簇，表项的值不同代表的含义不同。数据区主要存放数据信息，是文件系统的主要区域。将磁盘格式化为FAT32文件系统，其实就是在磁盘恰当的逻辑扇区写入一些数据，建立DBR 及其保留扇区、FAT 表1、FAT 表2。因此，我们称这些页为关键页，其所在位置为关键位置。

图3 FAT32文件系统结构

3 基于关键页覆写的数据删除技术

依据对Flash存储系统及FAT32文件系统原理分析可知，要确保FAT32文件系统不被破坏，关键是与文件系统相关的页要恢复到文件系统被格式化之初的状态；要保证数据被彻底清除，则需要将数据区的数据进行严格的 “0”填充或“1”填充操作。本文提出的基于关键页覆写的数据删除技术 （data deleting technology based on key－pages overwriting，KPOW 技术），能够有效的满足上述两点要求，既保证了文件系统不被破坏，又保证了数据被“0”全部覆盖。

3.1 KPOW 原理

KPOW 的基本实现思路是，对FAT32文件系统的起始扇区等关键页进行保存，在执行数据删除操作时，对Flash全部物理块进行擦除 （所有数据存储位置为1）操作，然后将关键页写回对应的逻辑块中重新建立文件系统。这样就保证了在文件系统不被破坏的情况下，数据得到彻底清除。

为完整重建FAT32文件系统，首先要对文件系统的关键页进行保存。KPOW 将这些关键页保存在一个特定的物理块中，并将该物理块置为已占用、且为配置块，这样就可保证该物理块既不被逻辑块映射，又不会被加入到备用块队列。该工作实际为KPOW 的准备工作，需要在格式化存储器之后、存储数据之前完成。

KPOW 通过对除配置块之外的物理块进行擦除操作以实现对数据的彻底清除。对全部物理块进行擦除操作可以有效的对原物理块上的信息进行掩盖，且Flash执行擦除操作的速度比对物理块执行写操作快得多。

数据被彻底删除后，文件系统也被破坏，因此，需要重建文件系统。文件系统重建主要依赖于之前保存的关键页。通过将关键页覆写回对应逻辑地址处，完成对FAT32文件系统的重建。写回原逻辑地址并不是写回原关键页所在物理地址处，在1.2节处已讨论过，出于磨损平衡考虑，关键页覆写实际是将关键页写入新申请的物理块中，再将该物理块映射到关键页对应的逻辑块中。

3.2 算法实现

在算法实现上可分为两个部分：①FAT32文件系统关键页的提取与保存；②数据无痕清除及基于关键页覆写的文件系统重建。

3.2.1 FAT32文件系统关键页的提取与保存

关键页的提取与保存由关键页提取模块来完成，提取算法如见表2。该模块在FAT32文件系统建立之初、还未被使用之前执行一次。

表2 关键页提取算法描述

由于有些关键页在同一块中，甚至在同一物理页中，故在保存这些关键页时需注意这些页的相互位置关系。由于在存储器未被使用的初始阶段，FAT 表只在第一个扇区起始处有 “F8FF FF 0FFF FF FF FF”8字节的内容，其余扇区都为 “0x00”（称之为0－扇区），同样的在保留扇区中也存在大量的0－扇区。因此，只需保留有内容的物理页及由 “0x00”填充的0－页即可。

3.2.2 数据删除与基于KPOW 的文件系统重建

通过对用于存放数据的物理块逐块擦除操作，可实现对存储器数据的清除。对于已执行了清除操作的物理块，在gLog2Phy［］中对应的标志位信息也要做同步修改，该物理块对应的逻辑地址标志信息也需修改。当所有数据物理块都被释放后，才能够重建文件系统。通过关键页覆写重建文件系统时，冗余区信息也需要随覆写进行实时修改。

当完成数据清除工作之后，才能够重建文件系统。通过关键页覆写重建文件系统时，冗余区信息也需要随覆写进行实时修改。除关键页外，根目录前的其它逻辑页也需用0－页填充，实现原理与关键页覆写过程类似，由于篇幅关系，该部分内容在下面算法中略去。表3以伪代码的形式给出文件系统算法实现。

表3 基于KPOW 的文件系统重建算法描述

4 测试与分析

本节将KPOW 与文件普通删除、文件强力删除、存储器格式化3种操作，在数据残留、执行效率两个关键指标上进行对比，对实际效果进行比较，并从实现原理上进行分析。

实验的测试环境如下：硬件平台为自制高速U 盘方案板卡，控制芯片为Cypress公司的EZ－USB FX2CY68013A通用型USB 接口控制芯片［9］，存储器为三星公司的K9F1G08Nand型Flash芯片 （可用存储空间为125 MB）。软件开发平台的开发语言为扩展51C，采用Keil uv2作为编译环境。操作系统为Window XP SP2。采用360安全卫士8.1提供的 “文件强力粉碎机”作为文件强力删除工具。

4.1 数据残余测试与分析

被执行删除操作的文件在存储器中是否有残余直接表征了删除操作效果好坏。本节采用分别测试的方法对目标磁盘 （或存储在磁盘中的全部文件）进行操作，并采用多种手段查看数据残余效果。具体实验步骤如下：①对文件普通删除、磁盘格式化、文件强力粉碎3种操作进行测试时，首先，在开发板内刷入不含KPOW 模块的原始固件（具有完整的U 盘功能）。每次操作前都利用Cypress公司提供的Flash格式化工具Nand Programmer，将开发板上的Flash刷写为格式一致的FAT32文件系统。每次在开发板中拷入相同的测试文件，分别进行5次上述操作，查看数据残留结果。②对KPOW 方法进行测试时，首先刷入原始固件；再使用Nand Programmer，将固件刷写为与对比方法一致的FAT32文件系统，然后拷入相同的测试文件，重新刷入包含KPOW 的固件，查看数据残留结果。

查看数据残留的方式包括：①采用360 安全卫士中的文件恢复工具对文件进行恢复，并查看恢复结果；②采用Winhex14.2 专业版直接查看目标存储器［10］；③利用与EZUSB FX2 68013A 配套的在线调试工具，直接读取目标存储器中物理块，查看数据残留情况。表4为执行删除操作后数据残余的可恢复性测试结果。

表4 删除操作后数据残余测试结果

普通删除操作只是将文件目录的属性设置为删除状态，数据仍然存在于数据区，因此3种数据残留测试方法都可以查看到文件内容。格式化操作只会覆盖掉原文件系统的FAT 表、根目录等关键数据，在数据区仍会有部分数据残余，一些结构紧凑的小文件仍能被恢复软件恢复，Winhex查看数据区发现有大量的残余数据存在，检查物理块数据残余的结果与Winhex一致。强力删除操作能够完美删除数据区数据，通过文件恢复工具无法恢复，Winhex也无法检查到有数据残余，但是，由于写操作通常会在新的空闲块中进行，将原物理块从逻辑地址空间移除后不会马上擦除，因此通过在线调试工具查看可以发现，会有部分数据残留在被替换块中。采用3种方法对KPOW 进行检测都未发现有残余数据存在，这是因为KPOW 会对所有数据块进行擦除操作，避免了数据清除不彻底的情形。

上述实验结果表明，KPOW 在数据残余方面有更为突出的表现。

4.2 执行效率测试与分析

执行效率的高低直接影响易用性，执行效率通过操作耗时长短体现出来。本节实验主要通过对比4种方法对存储相同文件的目标磁盘的操作时间，来比较各方法执行效率。

测试文件有两种，分别是：①由2103个小文件组成的大小为101 M 的文件组；②大小为101 M 的单个大文件。因此，测试相应分为不同两组：①多个小文件测试；②单个大文件测试。图4以柱形图的方式给出了测试结果。

图4 4种数据清除方法用时比较

从图4耗时结果分析看出：清除多个小文件数据时，格式化耗时最短；清除单个大文件时，普通删除耗时最短。无论单个大文件还是多个小文件，强力删除耗时最长。普通删除和强力删除的数据规模一致时，多个小文件耗时远比单个大文件耗时要长；而KPOW 和格式化的耗时与文件数量无关，基本是固定的。普通删除只修改文件目录属性及Fat表，因此耗时与文件数量有关；而强力删除除了要修改文件目录，还要用 “00”填充文件数据区，因此与文件数量有关。格式化和KPOW 与存储器中数据类型、大小、数量都无关，耗时相对固定。KPOW 和格式化耗时较长，主要是由于KPOW 在重建文件系统之前还需逐块执行数据清除操作。

擦除Nand Flash的一个物理块耗时不超过4ms，擦除1000个数据块用时大约在4～5s。因此，就数据清除操作而言，KPOW 的耗时较短，与其它方法相比具有一定优势。理论上，随着存储器规模增大，数据清除操作耗时也会增加。

5 结束语

本文针对安全存储存储器中敏感数据需要及时、彻底清除的问题，提出了一种先逐块清除数据，再通过关键页覆写重建文件系统的数据清除方法。本文着重介绍了该方法的原理及算法实现，并与其它方法在数据残余、执行效率两个方面进行了比较。

实验结果表明，本文提出的KPOW 数据清除方案，是一种彻底的数据清除方案，执行效率相对较高，具有一定实用性。

［1］ZHENG Wenjing，LI Mingqiang，SHU Jiwu.Flash storage technology ［J］.Journal of Computer Research and Development，2010，47 （4）：716－726 （in Chinese）.［郑文静，李明强，舒继武.Flash存储技术 ［J］.计算机研究与发展，2010，47 （4）：716－726.］

［2］YIN Yanbin，WEN Weiping.Computer data secure delete and privacy protect［J］.Netinfo Security，2009 （5）：55－58 （in Chinese）.［尹燕彬，文伟平.计算机数据安全删除和隐私保护 ［J］.信息网络安全，2009 （5）：55－58.］

［3］CHENG Yu.Study on the data destruction of magnetic storage media［D］.Chengdu：University of Electronic Science and Technology of China，2010：6－8 （in Chinese）. ［程玉.磁介质数据销毁技术的研究 ［D］.成都：电子科技大学，2010：6－8.］

［4］TANG Di，WEI Ying.Research on the technology of storage medium data destruction ［J］.Information Security and Technology，2012 （1）：9－15（in Chinese）. ［唐迪，魏英.存储介质数据销毁技术研究［J］.信息安全与技术，2012 （1）：9－15.］

［5］LI Min，ZHOU Anmin.Study and implementation of computer data secure deletion ［J］.Information Security and Communications Privacy，2010 （10）：73－77 （in Chinese）. ［李敏，周安民.计算机数据安全删除的研究与实现 ［J］.信息安全与通信保密，2010 （10）：73－77.］

［6］LU Linyan，WANG Lujing，ZHENG Zhengqi.Study and analysis on realization coding of NAND FLASH ［J］.Computer Technology and Development，2008，18 （3）：118－124 （in Chinese）. ［陆林燕，王鲁静，郑正奇.计算机技术与发展 ［J］.NAND FLASH编程实现研究分析，2008，18 （3）：118－124.］

［7］YUAN Jiandong，ZHAO Qiang，ZHENG Jianling.Obtaining and analyzing FAT32subarea information under Windows［J］.Hebei Journal of Industrial Science and Technology，2007，24（1）：11－14 （in Chinese）.［袁建东，赵强，郑见灵.Windows系统下FAT32分区信息分析与获取方法 ［J］.河北工业科技，2007，24 （1）：11－14.］

［8］LIU Wei.The deep secret on data recovery vehicle［M］.Beijing：Publishing House of Electronics Industry，2010：229－248（in Chinese）. ［刘伟.数据恢复深度揭秘 ［M］.北京：电子工业出版社，2010：229－248.］

［9］EZ－USB? FX2LPTMUSB microcontroller high－speed USB peripheral controller ［EB／OL］. ［2013－11－26］.http：／／www.cypress.com／？docID＝45142.

［10］WinHex：Computer forensics ＆data recovery software，hex editor ＆ disk editor ［EB／OL］ .［2013－12－28］.http：／／www.x－ways.net／winhex／index－m.html.