韓立毛， 趙躍華， 朱偉玲

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

0 引言

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

1 安全后端模塊的框架設(shè)計(jì)

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

1.1 安全后端模塊的框架結(jié)構(gòu)

安全后端模塊處理的主要是存儲(chǔ)管理及其安全性的問題，它的框架結(jié)構(gòu)設(shè)計(jì)如下頁(yè)圖1所示。

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

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

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

加密子模塊。通過(guò)加密，當(dāng)非法用戶通過(guò)用戶認(rèn)證進(jìn)入系統(tǒng)獲得存儲(chǔ)在數(shù)據(jù)庫(kù)中的數(shù)據(jù)時(shí)，得到的只是密文，依然無(wú)法理解其含義。

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

圖1 安全后端模塊框架結(jié)構(gòu)

2 安全后端模塊的子模塊設(shè)計(jì)

2.1 Cache管理子模塊

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

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

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

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

Cache管理子模塊的功能就是將用戶所需要的數(shù)據(jù)項(xiàng)從數(shù)據(jù)庫(kù)文件中讀入內(nèi)存，并在內(nèi)存中操作，如果有需要，再把它寫回?cái)?shù)據(jù)庫(kù)文件。這種功能可以歸結(jié)為Cache讀操作、Cache寫操作和Cache替換操作。

2.1.2 Cache管理子模塊中客體重用的實(shí)現(xiàn)

客體重用安全機(jī)制對(duì)廢棄的客體進(jìn)行“漂白”操作，實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單。設(shè)計(jì)客體重用安全機(jī)制最關(guān)鍵的是執(zhí)行時(shí)機(jī)的選擇，對(duì)于一般安全嵌入式數(shù)據(jù)庫(kù)管理系統(tǒng)而言，可以在客體釋放、存儲(chǔ)空間回收、存儲(chǔ)空間分配等時(shí)刻執(zhí)行該安全機(jī)制。

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

2.2 表和索引管理子模塊

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

2.2.1 元組組織方式的選取

一個(gè)表格或者索引的元組可以以多種方式組織，如線性表、B樹等。對(duì)于順序結(jié)構(gòu)而言，若元素已按關(guān)鍵字排序，則可采用更高效的檢索法，如折半檢索。但是若元素沒有按關(guān)鍵字排序，在作插入和刪除時(shí)，需移動(dòng)大量元素，付出很高的時(shí)間代價(jià)。對(duì)于鏈?zhǔn)酱鎯?chǔ)來(lái)說(shuō)，它雖然沒有順序存儲(chǔ)的缺點(diǎn)，但隨機(jī)存儲(chǔ)性差。

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

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

2.2.2 元組組織方式設(shè)計(jì)

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

2.2.3 元組的分配和回收

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

元組分配：空間分配運(yùn)算不分配小于4個(gè)字節(jié)的空間，請(qǐng)求分配的的空間都應(yīng)大于或等于4。假設(shè)請(qǐng)求分配nRequired個(gè)字節(jié)，這nRequired個(gè)字節(jié)來(lái)自一個(gè)Page，當(dāng)這個(gè)Page總共有nFree個(gè)字節(jié)。如果nRequired〉nFree，則請(qǐng)求失敗。如果nRequired≤nFree，則進(jìn)行分配；如果在本頁(yè)中無(wú)法存儲(chǔ)，那就對(duì)此樹擴(kuò)充，從Freelist上取下一個(gè)Page，添加到樹上。

元組回收：假設(shè)一個(gè)請(qǐng)求來(lái)了，要求釋放由先前分配的nFree個(gè)字節(jié)。分配算符創(chuàng)建一個(gè)nFree個(gè)字節(jié)的空閑塊，在適當(dāng)?shù)奈恢冒阉迦氲娇臻e塊列表中。此時(shí)，它開始在附近合并釋放空閑塊。如果在鄰近的空閑塊中有一個(gè)碎片，它就把塊和碎片合并。如果空間塊在指針隊(duì)列和元組內(nèi)容之間的未分配區(qū)域就將其回收至此。

2.2.4 表和索引管理子模塊中客體重用安全機(jī)制的實(shí)現(xiàn)

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

對(duì)于文件系統(tǒng)，在當(dāng)一個(gè)Page從樹上移走，并將這個(gè)Page增加到Freepage鏈接表的時(shí)刻執(zhí)行該策略。此時(shí)調(diào)用函數(shù)ESDBMSPcmerase0實(shí)現(xiàn)客體重用安全機(jī)制。

2.3 加密子模塊

2.3.1 加密分析與方案選擇

此加密模塊除具備基本的加密功能之外，還需要盡量減少時(shí)間和空間的開銷?？紤]到這些因素，設(shè)計(jì)此模塊需要解決如下兩個(gè)問題：

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

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

2.3.2 密鑰的管理

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

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

2.3.3 加密子模塊設(shè)計(jì)

具體過(guò)程。首先將整個(gè)數(shù)據(jù)庫(kù)劃分成塊，每個(gè)塊都可以作為一個(gè)單獨(dú)的AES加密塊，在計(jì)數(shù)器和由口令和鹽產(chǎn)生的密鑰作用下加密。加密和解密用的是相同的算法Rijndael算法。首先初始化一個(gè)進(jìn)程的計(jì)數(shù)器。把數(shù)據(jù)庫(kù)分成一個(gè)一個(gè)的塊，每個(gè)都作為一個(gè)單獨(dú)的AES加密塊，每個(gè)塊都從0開始編號(hào)，依據(jù)傳入編碼函數(shù)的Page Size和Page Number參數(shù)，算出計(jì)數(shù)塊內(nèi)的計(jì)數(shù)值和偏移量，然后用它來(lái)初始化加密流。

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

2.4 OS接口子模塊

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

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

3 結(jié)語(yǔ)

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

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

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

[3] 武森,高學(xué)東,[德]M．巴斯蒂安.數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘[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] 趙躍化,蔡貴賢，蔣軍.面向電力應(yīng)用的嵌入式安全文件系統(tǒng)實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2006,57(30):193-196.

[6] 劉啟軍,程明. 嵌入式 linux中以太網(wǎng)設(shè)備驅(qū)動(dòng)的設(shè)計(jì)與實(shí)現(xiàn)[J].通信技術(shù),2009,42(09):145-147.