韓立毛， 趙躍華， 朱偉玲

(①鹽城工學院 信息工程學院，江蘇 鹽城 224051；②江蘇大學 計算機科學與通信學院，江蘇 鎮(zhèn)江 212013)

0 引言

在嵌入式系統(tǒng)中，物理存儲空間是除了CPU之外最基本、最重要的資源，在系統(tǒng)中的管理效率對于整個系統(tǒng)的效率起著決定性的作用，內存和外存中存放的數據是安全嵌入式數據庫管理系統(tǒng) (ESDBMS，Secure and Embedded Database Management System)的重要保護對象。所以，如何高效地管理內存和外存空間，如何盡快的查找到數據庫文件中的有用信息，如何實現存儲管理的安全性等[1]，這些都是設計和實現ESDBMS安全后端模塊需要解決的問題。安全后端模塊作為與嵌入式操作系統(tǒng)聯系緊密的模塊，如何使其不受平臺影響，也是需要解決的問題。

1 安全后端模塊的框架設計

安全后端模塊的設計采用分層設計的思想，屏蔽掉各層之間的差異性，實現高層向低層的透明調用，這樣有利于降低層次之間的耦合度。對于ESDBMS的其它功能模塊，它們可以透明地調用安全后端模塊最高層提供的標準接口，而不需要了解安全后端模塊的底層實現機制，這樣有利于安全后端模塊的拆卸和擴充[2]，有利于實現ESDBMS整體的模塊化。

1.1 安全后端模塊的框架結構

安全后端模塊處理的主要是存儲管理及其安全性的問題，它的框架結構設計如下頁圖1所示。

1.2 安全后端模塊的子模塊劃分

表和索引管理子模塊。通過使用B+樹對頁面組織管理，對頁面空間進行分配和回收，以利于高效存儲、查找與組織元組。對執(zhí)行回收操作頁面內容的清除也是本模塊的任務[3]。

Cache管理子模塊。主要是在內存和外存之間移動頁面并對頁面進行管理。如何組織Cache中的頁面，如何對Cache中的頁面進行讀、寫、替換操作，這些是此模塊所要解決的重點。在將Cache中的內容提交給文件系統(tǒng)后，需要及時清除Cache中所包含的內容，這就是客體重用的任務。Cache管理子模塊實現如何把以字節(jié)為存取單位的文件提取為以頁為單位存取的文件。B+樹將目標元組所在頁碼傳送給Cache管理子模塊，Cache管理子模塊返回一個指向該元組所在頁的指針。

加密子模塊。通過加密，當非法用戶通過用戶認證進入系統(tǒng)獲得存儲在數據庫中的數據時，得到的只是密文，依然無法理解其含義。

0S接口。則用來屏蔽不同操作系統(tǒng)間的差異，從而為上層提供一種抽象層，以方便將來能運行于其它的操作系統(tǒng)上。

圖1 安全后端模塊框架結構

2 安全后端模塊的子模塊設計

2.1 Cache管理子模塊

2.1.1 Cache管理方案的選取與Cache的組織

Cache管理方案的選取[4]。Cache管理子模塊是本地文件系統(tǒng)和其它上層模塊之間的中間模塊，它是通過本地操作系統(tǒng)IO API訪問本地數據庫和日志文件的模塊，即定義一個易于使用、獨立于文件系統(tǒng)的接口，用來從數據庫文件中訪問頁面。表和索引管理子模塊總是通過Cache管理子模塊來訪問數據庫，并且從來不直接訪問數據庫或者日志文件，它將數據庫文件視為頁面的邏輯結構。

對每個數據庫文件來說，在文件和Cache之間移動頁面是頁面緩沖管理作為Cache管理器的基本功能。頁面的移動對表和索引管理子模塊和更高層次的模塊來說是透明的。為了提高數據庫的運行速度，本系統(tǒng)利用哈希表來組織內存中的頁。

Cache的組織。利用哈希表來組織Cache頁，為了區(qū)分內存和外存中的頁，在外存中的頁為Page，在內存中的頁為Slot，即任何的Slot可以存儲任何的Page。哈希表最初是空的，隨著頁面要求的不斷增加，Cache管理子模塊建立新的Slot并且把Slot插入到哈希表中。

Cache管理子模塊的功能就是將用戶所需要的數據項從數據庫文件中讀入內存，并在內存中操作，如果有需要，再把它寫回數據庫文件。這種功能可以歸結為Cache讀操作、Cache寫操作和Cache替換操作。

2.1.2 Cache管理子模塊中客體重用的實現

客體重用安全機制對廢棄的客體進行“漂白”操作，實現起來比較簡單。設計客體重用安全機制最關鍵的是執(zhí)行時機的選擇，對于一般安全嵌入式數據庫管理系統(tǒng)而言，可以在客體釋放、存儲空間回收、存儲空間分配等時刻執(zhí)行該安全機制。

由于內存管理和文件系統(tǒng)的存儲介質的物理特性存在很大的區(qū)別，所以內存管理和文件系統(tǒng)中執(zhí)行該安全機制的時機是不同的。對于內存管理，根據其具體設計，在Cache回收時執(zhí)行“垃圾”內存塊的擦除操作。即在Cache讀、寫和替換函數中插入Cache擦除操作函數來實現該安全機制。

2.2 表和索引管理子模塊

Cache管理子模塊實現把以字節(jié)為存取單位的文件提取為以頁為存取單位的文件，在這里主要實現把以頁為單位存取的文件提取為以元組為單位存取的文件。

2.2.1 元組組織方式的選取

一個表格或者索引的元組可以以多種方式組織，如線性表、B樹等。對于順序結構而言，若元素已按關鍵字排序，則可采用更高效的檢索法，如折半檢索。但是若元素沒有按關鍵字排序，在作插入和刪除時，需移動大量元素，付出很高的時間代價。對于鏈式存儲來說，它雖然沒有順序存儲的缺點，但隨機存儲性差。

B-樹是目前為止基于DBMS的外部存儲的最重要的索引結構。B-樹是存儲搜集類似數據記錄，并通過它們的鍵排序次序的一種組織方法。B-樹是一種深度平衡的樹，所有的Leaf節(jié)點在同一個水平。搜索信息存儲在Internal節(jié)點和Leaf節(jié)點。B-樹提供所有樹操作中最適宜的性能，比如插入、刪除、搜索和搜索下一個。B+樹具備B-樹所有的優(yōu)點，只將所有的元組存儲于Leaf節(jié)點，而不是像B-樹那樣將元組存于Leaf和Internal節(jié)點。B+樹中，元組是成對的，包括鍵值和數據值，它們按健值排序。Internal節(jié)點只包含搜索信息和孩子指針，鍵是按排序存儲的，它們用來直接搜索孩子節(jié)點。

安全后端模塊元組的組織方式選擇B+樹結構。B樹結構顯然比線性表結構查詢快捷，而實時性是嵌入式系統(tǒng)在對其他方面沒有大影響的前提下，首要考慮的因素，故選擇B樹結構。由于B+樹所有的元組都存放在Leaf頁中，Internal頁只存儲搜索信息和孩子指針。這樣就將Leaf頁和Internal頁的管理簡單化，降低設計難度。B-樹的查詢效率與鍵在樹中的位置有關，最大時間復雜度與B+樹相同，最小時間復雜度為1，而B+樹的時候復雜度對某建成的樹是固定的。

2.2.2 元組組織方式設計

ESDBMS通過分配根頁來創(chuàng)建一棵樹。每一棵樹通過它的根頁號碼來區(qū)分，號碼存儲在主目錄表中，主目錄表的根始終在Page 1。ESDBMS的tree節(jié)點包括Internal節(jié)點和Leaf節(jié)點，如下頁圖2所示。元組內容是Leaf頁的一部份，每個元組的鍵和數據組成Payload，如果Payload超過了此頁的大小，那么就將其溢出至Overflow Page。

2.2.3 元組的分配和回收

表和索引管理子模塊幫助安全數據庫引擎模塊把所有的表和索引組織成B+樹。每棵樹由一個或多個數據庫Page組成。數據庫引擎能存儲和搜索任何樹中可變長度的元組，在任何時候刪除樹中的元組。表和索引管理子模塊可在任意時候從數據庫引擎收到插入和刪除記錄的要求。一個插入操作需要在Tree Page和Overflow Page中分配空間。一個刪除操作清空Tree Page和Overflow Page中占據的空間。管理空閑空間對于有效分配和回收空間是至關重要的?？臻e空間主要包括Free Page的空閑空間和Tree Page的空閑空間。

元組分配：空間分配運算不分配小于4個字節(jié)的空間，請求分配的的空間都應大于或等于4。假設請求分配nRequired個字節(jié)，這nRequired個字節(jié)來自一個Page，當這個Page總共有nFree個字節(jié)。如果nRequired〉nFree，則請求失敗。如果nRequired≤nFree，則進行分配；如果在本頁中無法存儲，那就對此樹擴充，從Freelist上取下一個Page，添加到樹上。

元組回收：假設一個請求來了，要求釋放由先前分配的nFree個字節(jié)。分配算符創(chuàng)建一個nFree個字節(jié)的空閑塊，在適當的位置把它插入到空閑塊列表中。此時，它開始在附近合并釋放空閑塊。如果在鄰近的空閑塊中有一個碎片，它就把塊和碎片合并。如果空間塊在指針隊列和元組內容之間的未分配區(qū)域就將其回收至此。

2.2.4 表和索引管理子模塊中客體重用安全機制的實現

由于內存管理和文件系統(tǒng)中執(zhí)行客體重用安全機制只是時機的不同，故內存中客體重用機制的實現方法與文件系統(tǒng)中這種安全機制的實現方法類同。

對于文件系統(tǒng)，在當一個Page從樹上移走，并將這個Page增加到Freepage鏈接表的時刻執(zhí)行該策略。此時調用函數ESDBMSPcmerase0實現客體重用安全機制。

2.3 加密子模塊

2.3.1 加密分析與方案選擇

此加密模塊除具備基本的加密功能之外，還需要盡量減少時間和空間的開銷。考慮到這些因素，設計此模塊需要解決如下兩個問題：

① 加密粒度。在數據庫加密系統(tǒng)中，數據庫具有的文件、記錄、字段多層次的概念，故必須綜合考慮選擇合適的加密粒度。對記錄或者字段進行加密存儲在嵌入式系統(tǒng)中是不現實的，對記錄或者字段進行加密，其密鑰的管理會成為一個特別棘手的問題，這對有快速，精簡要求的嵌入式而言不適合。而選擇對文件進行加密雖然粒度較粗，容易造成對不必要信息進行加密，但在電力系統(tǒng)從站中，數據量不大且數據類型很少，若采用計數器模式加密方法則不會增加任何的空間開銷，與明文大小等同[5]。其密鑰的管理也相當簡單；

② 加密算法。加密算法是數據加密的核心，從加解密的密鑰是否相同可以分為對稱加密算法和非對稱加密算法。對稱加密算法由于其加解密的快速性在嵌入式系統(tǒng)中應用比較廣泛，AES就是一種很成熟的對稱加密算法。

2.3.2 密鑰的管理

基于口令的加密。在密鑰學的許多應用中，用戶安全性最終取決于一個或多個秘密文本值或口令?？诹畈皇侵苯涌捎米髅艽a系統(tǒng)的密鑰，相反，需要對口令進行一些處理才能用它進行密碼操作。

密鑰的產生。采用基于口令的加密方案，其密鑰產生的過程：首先選擇一個S和一個迭代次數C；其次選擇導出密鑰的字節(jié)長度dkLen；再其次將密鑰導出函數應用于口令P、S、迭代次數和密鑰長度以生成一個導出密鑰DK(P，S，C，dkLen)；最后輸出導出的密鑰。其中S用于產生對應于給定口令的一個大集合的密鑰，依據該S從中隨機選取一個密鑰。迭代計數C傳統(tǒng)上用于增加從口令生成密鑰的代價，從而增加攻擊的難度。密鑰導出函數是一個散列函數，包括MD2、MD5、SHA-1或SHA256等。導出密鑰的字節(jié)長度dkLen與密鑰導出函數有關，MD2和MD5是16字節(jié)，SHA-1是20字節(jié)。本加密模塊采用的是SHA256，密鑰長度是32字節(jié)。

2.3.3 加密子模塊設計

具體過程。首先將整個數據庫劃分成塊，每個塊都可以作為一個單獨的AES加密塊，在計數器和由口令和鹽產生的密鑰作用下加密。加密和解密用的是相同的算法Rijndael算法。首先初始化一個進程的計數器。把數據庫分成一個一個的塊，每個都作為一個單獨的AES加密塊，每個塊都從0開始編號，依據傳入編碼函數的Page Size和Page Number參數，算出計數塊內的計數值和偏移量，然后用它來初始化加密流。

加密模塊提供的接口。加密模塊完成之后，給用戶提供了用于加密的API接口EDBMS_keyO，EDBMS-rekeyO。此加密模塊為可剪裁的模塊，用戶可以根據自己的需要對其進行增刪。

2.4 OS接口子模塊

OS接口的作用是為上層模塊提供了一種抽象層，用來屏蔽不同操作系統(tǒng)的差別，為將來能移植到其它操作系統(tǒng)作鋪墊。它的最終結果就是：不管是在哪種操作系統(tǒng)上，上層模塊只看到一種單一的接口[6]。這樣設計，不僅使其它模塊不用考慮操作系統(tǒng)，從而編寫的代碼更簡單，而且使模塊問的關系整潔有序。

在OS接口模塊中，主要是完成文件的一系列操作以及對文件鎖的處理，包括文件的打開、關閉、刪除和讀鎖、寫鎖信息的取得。由于不同的操作系統(tǒng)有自己獨特的機制，這里只是說明了適用于Linux的的接口函數，如果以后擴展，可以對函數進行修改。

3 結語

本文采用分層設計的思想，設計和實現了ESDBMS的安全后端模塊，屏蔽掉了各層之間的差異性，實現了高層向低層的透明調用，有利于降低層次之間的耦合度。對于ESDBMS的其它功能模塊，它們可以透明地調用安全后端模塊最高層提供的標準接口，而不需要了解安全后端模塊的底層實現機制，這樣有利于安全后端模塊的拆卸和擴充，有利于實現ESDBMS的整體模塊化。設計的ESDBMS安全后端模塊能有效的管理存儲空間、快速檢索數據庫文件中的信息、提高了存儲管理的安全性，具有良好的實用性和創(chuàng)新性。

[1] 崔文靜.實時數據庫系統(tǒng)中并發(fā)控制的研究[D].濟南:山東大學,2004.

[2] 王利青,武仁杰,蘭安怡.Web安全測試及對策研究[J].通信技術，2008,41(06):29-32.

[3] 武森,高學東,[德]M．巴斯蒂安.數據倉庫與數據挖掘[M].北京:冶金工業(yè)山版社,2003.

[4] WolfSon O,Huang Y X.Competive Analysis of Cashing in Distributed Database[J].IEEE Trans on Parallel and Distributed Systems,1998,l9(04):391-409.

[5] 趙躍化,蔡貴賢，蔣軍.面向電力應用的嵌入式安全文件系統(tǒng)實現[J].計算機工程與應用,2006,57(30):193-196.

[6] 劉啟軍,程明. 嵌入式 linux中以太網設備驅動的設計與實現[J].通信技術,2009,42(09):145-147.