基于關鍵頁覆寫的數據清除技術

郭松輝，王玉龍，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.