趙 飛 蘇 忠 丁 小

（1.空軍指揮學(xué)院 網(wǎng)絡(luò)中心 北京 100097 2.95865部隊 北京 100092）

0 引言

數(shù)據(jù)庫安全一直以來都是信息安全領(lǐng)域的熱點問題。隨著云計算、物聯(lián)網(wǎng)等新興技術(shù)的迅速發(fā)展，以及社交網(wǎng)絡(luò)、微博、推特等新型網(wǎng)絡(luò)應(yīng)用的快速普及，包括銀行、鐵路、水電等基礎(chǔ)設(shè)施要害領(lǐng)域的信息系統(tǒng)的安全受到更加廣泛關(guān)注，而信息系統(tǒng)是否安全在很大程度上取決于數(shù)據(jù)庫的安全。傳統(tǒng)的數(shù)據(jù)庫安全機制側(cè)重于保護(hù)數(shù)據(jù)的保密性、完整性和可用性，但無法滿足數(shù)據(jù)庫可生存性要求，即數(shù)據(jù)庫在遭受到非人為系統(tǒng)故障、內(nèi)部或外部攻擊時持續(xù)提供關(guān)鍵服務(wù)的能力。要實現(xiàn)數(shù)據(jù)庫可生存性，很關(guān)鍵的一點是必須能夠快速發(fā)現(xiàn)并隔離惡意事務(wù)和受污染數(shù)據(jù)，并且及時恢復(fù)相關(guān)事務(wù)和數(shù)據(jù)。隨著數(shù)據(jù)庫數(shù)據(jù)規(guī)模的急劇增大，事務(wù)提交異常頻繁，如何能夠在惡意事務(wù)檢測以后，在確保隔離精度的前提下，最大限度的減少隔離和恢復(fù)的時間就成為一個重要的研究方向，因為它直接關(guān)系著數(shù)據(jù)庫持續(xù)提供服務(wù)的能力。

1 相關(guān)研究

Merkle Hash Tree（MHT）最早被引入到驗證服務(wù)數(shù)據(jù)的真實性是在文獻(xiàn)[1]中，它解決了指定查詢服務(wù)結(jié)果可靠性的認(rèn)證問題。Martel 等人在解決在線數(shù)據(jù)庫查詢安全認(rèn)證問題時提出了檢索有向非循環(huán)圖(search directed acyclic graph)的驗證方法[2]，并引入了MHT結(jié)構(gòu)，提升了檢查的效率。Devanbu 等人提出一種基于MHT的驗證機制來解決第三方數(shù)據(jù)發(fā)布方的數(shù)據(jù)完整性和可靠性驗證問題[3]，在機制中要求數(shù)據(jù)庫所有者為每一個數(shù)據(jù)表建立MHT，并將MHT根處的信息摘要直接發(fā)給用戶，以此來實現(xiàn)查詢結(jié)果的驗證。Ma 等人在文獻(xiàn)[3]基礎(chǔ)上作了修改[4]，對單獨元組的屬性值建立MHT，從而在驗證時能夠精確到數(shù)據(jù)元組，提升了驗證精度和效率。Pang H 等人從查詢結(jié)果的完整性和可靠性兩個方面對文獻(xiàn)[3]中提出的方法作了實驗性驗證[5]，內(nèi)容涵蓋了查詢、查詢投影、多點查詢等數(shù)據(jù)庫常用服務(wù)功能，并從通信代價、數(shù)據(jù)庫升級代價等角度對模型進(jìn)行了量化分析，具有很強的現(xiàn)實意義。

以上基于MHT的方法都是建立在第三方（外包）數(shù)據(jù)庫服務(wù)方靜態(tài)環(huán)境條件下（許多是基于理想化模型條件），解決的問題為數(shù)據(jù)庫查詢的正確性和完整性要求。Li 等人在文獻(xiàn)[2]的基礎(chǔ)上，提出了查詢事務(wù)及時性的驗證需求[6]，并通過引入B+-tree設(shè)計驗證索引結(jié)構(gòu)Merkle B-tree，建立驗證模型，同時還將設(shè)計方法拓展到動態(tài)數(shù)據(jù)庫服務(wù)中，提出Embedded Merkle B-tree的數(shù)據(jù)結(jié)構(gòu)，合理的緩解了驗證結(jié)構(gòu)存儲空間消耗問題。Jain 等人在文獻(xiàn)[6]基礎(chǔ)上提出了事務(wù)完整性的概念[7]，設(shè)計的基于Merkle Hash B+-Tree（MHBT）模型不僅能夠?qū)崿F(xiàn)驗證數(shù)據(jù)正確性和完整性的要求，還能夠通過建立事務(wù)執(zhí)行與數(shù)據(jù)庫狀態(tài)結(jié)構(gòu)MHBT之間的對應(yīng)關(guān)系，驗證事務(wù)執(zhí)行的完整性，并實現(xiàn)攻擊數(shù)據(jù)恢復(fù)操作。

2 基本概念介紹

2.1 單列哈希算法

單向哈希函數(shù)h()可以把一個變長的輸入值x通過函數(shù)計算輸出為一個定長值y，即：y=h（x），單向哈希函數(shù)h()具有單向性、唯一性等特點。單向性是指：給定一個哈希值y和函數(shù)h()，不可能找到一個值x，使得h（x）=y；唯一性是指：不可能找到兩個不同的值x、y，使得h（x）=h（y）。目前常用的單向哈希函數(shù)是SHA-256。

2.2 Merkle哈希樹

Merkle哈希樹，又被稱為哈希樹或Merkle樹，1979年由Ralph Merkle首先提出，主要用于對特定對象的認(rèn)證。MHT是一棵完全二叉樹，在這棵樹中，葉節(jié)點為需認(rèn)證的對象的哈希值，而中間節(jié)點則是其左右孩子節(jié)點的并置哈希值。圖1所示的是一棵Merkle哈希樹示意圖。

在圖1里，Merkle哈希樹共有四個葉節(jié)點{S1,S2,S3,S4}，其值分別為需認(rèn)證的對象{O1,O2,O3,O4}的哈希值，即Si=H(Oi)(i=1,2,3,4)(H()為單向哈希函數(shù))；非葉節(jié)點S34可表示為S34=H(S3||S4)。“||”表示并置操作。

圖1 Merkle哈希樹

2.3 B+-tree

B+樹是平衡多叉樹。一棵m階B+樹的定義如下[8]：

樹中每個非葉節(jié)點最多有m棵子樹；

根節(jié)點(非葉節(jié)點) 至少有2棵子樹。除根節(jié)點外，其它的非葉節(jié)點至少有棵子樹；

若根節(jié)點同時又是葉節(jié)點，則節(jié)點格式同葉節(jié)點。

有n 棵子樹的節(jié)點有n個關(guān)鍵碼，對應(yīng)的指向?qū)ο蟮牡刂分羔樢灿衝個；

所有非葉節(jié)點中包含下列信息數(shù)據(jù)( n,K1,P1,K2,P2,… ,Kn,Pn)，其中： Ki(i=1,…,n)為關(guān)鍵碼，且Ki＜Ki+1,Pi(i=0,…,n)為指向子樹根節(jié)點的指針,n為關(guān)鍵碼的個數(shù)；

所有的非葉子節(jié)點可以看成是索引部分，節(jié)點中僅含有其子樹（根節(jié)點）中的最?。ɑ蜃畲螅╆P(guān)鍵碼；

每個葉節(jié)點中的子樹棵數(shù)可以多于m，可以少于m，視關(guān)鍵碼字節(jié)數(shù)及對象地址指針字節(jié)數(shù)而定。

所有葉節(jié)點都處于同一層次上，包含了全部關(guān)鍵碼及指向相應(yīng)數(shù)據(jù)對象存放地址的指針，且葉節(jié)點本身按關(guān)鍵碼從小到大順序鏈接；

在B+樹中有兩個頭指針：一個指向B+樹的根節(jié)點，一個指向關(guān)鍵碼最?。ɑ蜃畲螅┑娜~節(jié)點。圖2是一棵3階的B+樹示意圖[8]。

圖2 B+樹

2.4 Merkle哈希B+樹

Merkle哈希B+樹（Merkle Hash B+-Tree ,MHBT）就是將MHT中的樹結(jié)構(gòu)拓展成為B+樹，如同構(gòu)建MHT一樣，對B+樹采用分層哈希的模式。一個MHBT的數(shù)據(jù)結(jié)構(gòu)有著與常規(guī)B+樹相同的節(jié)點構(gòu)成，所不同的是在每個節(jié)點處擴充的加入了節(jié)點標(biāo)記值，每個節(jié)點的標(biāo)記值是孩子節(jié)點哈希值的并置哈希值，其計算方法如同MHT：非葉子節(jié)點的標(biāo)記值通過計算子節(jié)點標(biāo)記值的并置哈希值求得；葉子節(jié)點的標(biāo)記值通過計算該節(jié)點所包含數(shù)據(jù)元組哈希值獲得。如圖3(a)所示，數(shù)據(jù)庫初始化時，對所有的數(shù)據(jù)元組進(jìn)行哈希運算后，依據(jù)B+樹的構(gòu)建方法，逐級構(gòu)建此時的證據(jù)結(jié)構(gòu)MHBT。具體詳細(xì)的節(jié)點示意圖如圖3(b)所示，其中kj為節(jié)點的關(guān)鍵碼值，pj為指針，hj為節(jié)點的標(biāo)記值（其中hi…h(huán)k為該節(jié)點下屬孩子節(jié)點標(biāo)記值的并置哈希值），節(jié)點i為非葉子節(jié)點，hi為該節(jié)點標(biāo)記值，即節(jié)點所指向數(shù)據(jù)元組哈希值的并置哈希值。

圖3 Merkle哈希B+樹

3 基于MHBT的隔離與恢復(fù)模型

3.1 假設(shè)條件

模型自身并不檢測惡意事務(wù)。本文設(shè)計模型本身并不檢測一個事務(wù)是否為惡意，惡意事務(wù)的檢測由入侵檢測系統(tǒng)完成，模型的主要功能是在惡意事務(wù)信息的基礎(chǔ)上，快速準(zhǔn)確的隔離污染事務(wù)及相應(yīng)的受損數(shù)據(jù)。

數(shù)據(jù)庫事務(wù)的提交是嚴(yán)格串行化的。為了能夠確保數(shù)據(jù)有最嚴(yán)格意義的準(zhǔn)確性和完整性，這里我們假設(shè)數(shù)據(jù)庫事務(wù)的提交是嚴(yán)格串行化的，事務(wù)執(zhí)行的完整性要求每一個事務(wù)在提交時數(shù)據(jù)庫必須處于一致的狀態(tài)，即之前所有的合法的提交事務(wù)都已全部有序的提交并修改完相應(yīng)的數(shù)據(jù)元組，從而確保數(shù)據(jù)庫狀態(tài)變化的與事務(wù)提交之間的強相關(guān)性。

事務(wù)本身限定其具有可復(fù)制性。事務(wù)的可復(fù)制性是指事務(wù)具有確定性，即在數(shù)據(jù)庫穩(wěn)定狀態(tài)上，事務(wù)的執(zhí)行結(jié)果完全由讀取的數(shù)據(jù)庫值和外部輸入的參數(shù)值決定，撤銷重做執(zhí)行結(jié)果相同。

3.2 系統(tǒng)模型

模型中采用“三方”機制運行，分別是數(shù)據(jù)庫服務(wù)端、數(shù)據(jù)庫客戶端和MHBT存儲端。其中，數(shù)據(jù)庫服務(wù)端與客戶端采用“一對多”模式，即一個數(shù)據(jù)庫服務(wù)端對應(yīng)有多個數(shù)據(jù)庫客戶端，MHBT存儲端為一個。系統(tǒng)模型如圖4所示。

圖4 系統(tǒng)模型

3.3 模型描述

在以上假設(shè)條件基礎(chǔ)上，就可以設(shè)計模型使用MHBT來建立事務(wù)與數(shù)據(jù)庫狀態(tài)之間的關(guān)系模型：數(shù)據(jù)庫每一次狀態(tài)變化都可以通過更新MHBT的證據(jù)結(jié)構(gòu)來記錄，而MHBT的更新又是建立在事務(wù)提交的基礎(chǔ)上，新的樹形結(jié)構(gòu)是在之前樹結(jié)構(gòu)應(yīng)用事務(wù)執(zhí)行結(jié)果后計算而來的，這樣就能夠通過MHBT建立數(shù)據(jù)庫狀態(tài)和事務(wù)提交之間的一一對應(yīng)關(guān)系。

3.3.1 初始化

在數(shù)據(jù)庫開始向用戶提供服務(wù)前，首先構(gòu)造數(shù)據(jù)庫初始狀態(tài)時的MHBT0。MHBT存儲端復(fù)制初始狀態(tài)時數(shù)據(jù)庫服務(wù)端的所有數(shù)據(jù)元組，根據(jù)2.4節(jié)中MHBT構(gòu)建方法，對此時數(shù)據(jù)庫所擁有的所有數(shù)據(jù)表，建立初始狀態(tài)時各自的證據(jù)結(jié)構(gòu)MHBT0，證據(jù)結(jié)構(gòu)中所有節(jié)點的信息通過MHBT存儲端建立存儲表的形式存儲。此后數(shù)據(jù)庫服務(wù)端開始正常工作，接收用戶發(fā)來的請求事務(wù)。圖5為一個簡單的數(shù)據(jù)庫表1在初始化時的示例，為了便于演示，我們將每條數(shù)據(jù)記錄（數(shù)據(jù)元組）以t1，t2，t3…代號的形式表示，Hi為該條數(shù)據(jù)元組的哈希值。

表1 數(shù)據(jù)庫初始化時數(shù)

07 張七 男 19 計算機…… …… …… …… ……18 張18 男 19 計算機…… …… …… …… ……26 張26 男 19 計算機27 張27 男 19 計算機

圖5 模型初始化MHBT0示例

3.3.2 事務(wù)執(zhí)行

數(shù)據(jù)庫在執(zhí)行事務(wù)時先記錄被修改數(shù)據(jù)元組的信息，如果事務(wù)提交成功，數(shù)據(jù)庫就將更新的數(shù)據(jù)元組和事務(wù)標(biāo)識號（事務(wù)在數(shù)據(jù)庫服務(wù)端的標(biāo)識信息）發(fā)送到MHBT存儲端，而后再將事務(wù)執(zhí)行結(jié)果集返回給客戶端。MHBT存儲端根據(jù)事務(wù)標(biāo)識號和修改的數(shù)據(jù)元組更新證據(jù)機構(gòu)MHBT。具體如圖6所示，事務(wù)的提交是串行化的，如果i是做為本次提交事務(wù)的標(biāo)識號，數(shù)據(jù)庫就將識別其為事務(wù)Ti，即第i個提交的事務(wù)，串行化隔離級別能夠確保事務(wù)Ti的執(zhí)行是在DBi-1的狀態(tài)上（之前所有事務(wù)全部響應(yīng)后的一致狀態(tài)），事務(wù)執(zhí)行后數(shù)據(jù)庫進(jìn)入下一個一致狀態(tài)DBi，數(shù)據(jù)庫服務(wù)端將修改的數(shù)據(jù)元組與相應(yīng)的事務(wù)位置號Ti一并發(fā)送給MHBT存儲端，而后數(shù)據(jù)庫服務(wù)端向用戶發(fā)送響應(yīng)信息：事務(wù)序列號（客戶端查證事務(wù)）、事務(wù)執(zhí)行結(jié)果集。MHBT存儲端根據(jù)收到的事務(wù)標(biāo)識號和所修改的數(shù)據(jù)元組計算相應(yīng)的證據(jù)結(jié)構(gòu)MHBTi（從之前的MHBTi-1基礎(chǔ)上計算當(dāng)前的MHBTi：未修改元組直接讀取MHBTi-1中記錄的節(jié)點值，有改動數(shù)據(jù)元組計算哈希值并存入相應(yīng)節(jié)點后與未修改數(shù)據(jù)元組節(jié)點一起生成新的證據(jù)機構(gòu)MHBTi），做為當(dāng)前事務(wù)執(zhí)行后的數(shù)據(jù)庫狀態(tài)信息。

圖6 事務(wù)執(zhí)行過程

3.3.3 事務(wù)與數(shù)據(jù)隔離

當(dāng)入侵檢測系統(tǒng)檢測到惡意事務(wù)后，數(shù)據(jù)庫會根據(jù)事務(wù)標(biāo)識號i調(diào)取惡意事務(wù)的證據(jù)結(jié)構(gòu)MHBTi，因為數(shù)據(jù)庫是嚴(yán)格串行化隔離的，所以受影響的事務(wù)必定是在事務(wù)i提交之后的事務(wù)，MHBT通過比對事務(wù)i之后的所有證據(jù)結(jié)構(gòu)能夠快速的確定受影響事務(wù)。

證據(jù)結(jié)構(gòu)具體比對方法是：

（1）比較根節(jié)點的值。在證據(jù)結(jié)構(gòu)歷史表中存儲有數(shù)據(jù)庫歷次更新后，各節(jié)點的變更信息，依據(jù)事務(wù)號及節(jié)點層級號能夠快速實施對根節(jié)點的比對：如果根節(jié)點值一樣，則根據(jù)MHBT樹結(jié)構(gòu)的特點，可以判定該事務(wù)沒有修改任何數(shù)據(jù)元組，為只讀事務(wù)，不記錄到寫事務(wù)表中；如果根節(jié)點值不一樣，則能確定該事務(wù)對數(shù)據(jù)元組執(zhí)行了修改操作，為寫事務(wù)，記錄到寫事務(wù)列表中，同時，依據(jù)證據(jù)結(jié)構(gòu)歷史表中存儲的信息，比對出所有變化的葉結(jié)點信息，以此來鎖定所有被修改的數(shù)據(jù)元組。如圖7中所示，T(1)，T(2)，T(3)，T(11)都執(zhí)行了寫操作，在首次判定時都會被記錄到寫事務(wù)列表中，而T(12)僅讀取了數(shù)據(jù)，沒有修改數(shù)據(jù)，這里就不做記錄。

（2）依次比對寫事務(wù)列表。依據(jù)寫事務(wù)列表所對應(yīng)的MHBT樹結(jié)構(gòu)，比對出后一事務(wù)在之前事務(wù)基礎(chǔ)上做的數(shù)據(jù)修改，記錄相應(yīng)改變的數(shù)據(jù)元組。如果改變數(shù)據(jù)元組中包含有受損數(shù)據(jù)元組或污染數(shù)據(jù)元組，則定義該事務(wù)為強相關(guān)事務(wù)，記錄到待恢復(fù)事務(wù)列表中，所有修改元組記錄為污染數(shù)據(jù)；如果不包含受損數(shù)據(jù)元組或污染數(shù)據(jù)元組，則記錄為嫌疑事務(wù)，進(jìn)入到下層比對模型。如7圖中所示，事務(wù)T(1)，T(2)對應(yīng)的證據(jù)結(jié)構(gòu)中，比對出的修改元組包含有受損數(shù)據(jù)X，因為事務(wù)T(1) ，T(2)對X執(zhí)行了寫操作，會被判定為強相關(guān)事務(wù)，記錄到待恢復(fù)列表中，數(shù)據(jù)Y記錄為污染數(shù)據(jù)；事務(wù)T(3)，T(11)與其之前證據(jù)結(jié)構(gòu)比對出的修改數(shù)據(jù)元組不包含有受損數(shù)據(jù)X及污染數(shù)據(jù)Y，判定為嫌疑事務(wù)，進(jìn)入到下層比對模型中。

（3）嫌疑事務(wù)判定。對2記錄的嫌疑事務(wù)，MHBT存儲端會通過其事務(wù)標(biāo)識號讀取數(shù)據(jù)庫服務(wù)端事務(wù)日志記錄中的事務(wù)操作信息，如果該事務(wù)有讀取受損數(shù)據(jù)或污染數(shù)據(jù)的操作，則判定為污染事務(wù)，記錄到待恢復(fù)事務(wù)列表中；如果該事務(wù)沒有讀取受損數(shù)據(jù)的操作，則可以判定為正常事務(wù)，釋放相關(guān)的加鎖數(shù)據(jù)元組。如圖7中所示，事務(wù)T(3)有執(zhí)行讀取數(shù)據(jù)X的操作，被判定為污染事務(wù)，記錄到待恢復(fù)事務(wù)列表中；事務(wù)T(11)沒有執(zhí)行數(shù)據(jù)X的讀操作，雖然有修改數(shù)據(jù)庫中數(shù)據(jù)，但仍就判定為正常事務(wù)，釋放對數(shù)據(jù)U的鎖定操作。

圖8為具體事務(wù)的比對流程。

圖7 數(shù)據(jù)庫事務(wù)分類圖

圖8 事務(wù)比對流程

可生存性保證：MHBT存儲端將事務(wù)隔離確定的受損數(shù)據(jù)和污染數(shù)據(jù)以事務(wù)請求方式在數(shù)據(jù)庫服務(wù)端加鎖（利用數(shù)據(jù)庫中的排他鎖，對相關(guān)數(shù)據(jù)實施加鎖操作），新事務(wù)請求中如果有訪問到這兩種數(shù)據(jù)則推遲執(zhí)行，等待訪問數(shù)據(jù)的恢復(fù)操作；如果沒有則正常提交事務(wù)，按要求生成新的數(shù)據(jù)庫證據(jù)結(jié)構(gòu)記錄到MHBT存儲端相關(guān)的數(shù)據(jù)表中。這樣就將正確數(shù)據(jù)與錯誤數(shù)據(jù)合理分割，區(qū)別對待，在確保數(shù)據(jù)庫持續(xù)提供服務(wù)的同時執(zhí)行受損數(shù)據(jù)的逐個恢復(fù)，最大限度的保證用戶的服務(wù)請求，如圖9所示。

圖9 數(shù)據(jù)庫服務(wù)端事務(wù)執(zhí)行流程圖

3.3.4 數(shù)據(jù)修復(fù)

在數(shù)據(jù)庫服務(wù)端的歷次更新中，模型運行機的歷史表中記錄了所有變化的元組值，當(dāng)需要修復(fù)時，MHBT存儲端能夠通過事務(wù)號查到在執(zhí)行本次事務(wù)時，數(shù)據(jù)庫修改元組和節(jié)點值時所參照的上一數(shù)據(jù)庫服務(wù)端的狀態(tài)結(jié)構(gòu)信息（參照的相關(guān)元組值）；待修列表中事務(wù)按提交號順序排列，通過讀取事務(wù)日志信息，執(zhí)行事務(wù)的重做操作，恢復(fù)數(shù)據(jù)服務(wù)端到正確狀態(tài)。

在數(shù)據(jù)庫服務(wù)端的歷次更新中，MHBT存儲端的數(shù)據(jù)元組歷史表中記錄了歷次修改的數(shù)據(jù)元組值，當(dāng)需要修復(fù)時，MHBT存儲端能夠通過事務(wù)號查詢到在執(zhí)行本次事務(wù)時，數(shù)據(jù)庫修改數(shù)據(jù)元組和節(jié)點值時所參照的上一數(shù)據(jù)庫服務(wù)端的狀態(tài)結(jié)構(gòu)信息；待修列表中事務(wù)按標(biāo)識號順序排列，通過讀取事務(wù)日志信息，執(zhí)行事務(wù)的重做操作，恢復(fù)數(shù)據(jù)服務(wù)端到正確狀態(tài)。具體恢復(fù)恢復(fù)方法是：

（1）將隔離模型中所確定待修復(fù)事務(wù)按標(biāo)識號順序排列，標(biāo)識號在數(shù)據(jù)庫服務(wù)端是按事務(wù)提交順序依次遞增排列的，順序排列修復(fù)事務(wù)，能夠有效提高讀取數(shù)據(jù)庫服務(wù)端事務(wù)日志記錄的效率。

（2）讀取數(shù)據(jù)庫服務(wù)端事務(wù)日志，索取事務(wù)具體的操作序列。

（3）依據(jù)事務(wù)操作信息，讀取MHBT存儲端證據(jù)結(jié)構(gòu)MHBT中存儲的相關(guān)信息，執(zhí)行事務(wù)，修改相應(yīng)的記錄值，形成新的證據(jù)結(jié)構(gòu)。

（4）返回結(jié)果給數(shù)據(jù)庫服務(wù)端，修改對應(yīng)的數(shù)據(jù)元組，解除加鎖操作。

圖10為具體事務(wù)恢復(fù)流程圖。

圖10 事務(wù)修復(fù)過程

4 模型分析

4.1 狀態(tài)結(jié)構(gòu)構(gòu)建時間

構(gòu)建數(shù)據(jù)庫某個狀態(tài)時的MHBT樹結(jié)構(gòu)所耗費的時間包括計算每個數(shù)據(jù)元組的哈希值以及樹中每個節(jié)點哈希值，另外還有將這些節(jié)點信息寫入磁盤的時間。

一個數(shù)據(jù)庫擁有n個元組，扇出（fanout，非葉結(jié)點平均擁有的孩子節(jié)點數(shù)）為，如果構(gòu)建MHBT樹的高度為d，那么樹中構(gòu)建的節(jié)點為：

則構(gòu)建樹的時間為：

其中，Sn樹節(jié)點占用存儲塊大小，St數(shù)據(jù)元組占有存儲塊大小，Ch為計算一個哈希值所需要的時間，CIO為一個數(shù)據(jù)塊的IO時間消耗。構(gòu)建證據(jù)樹MHBT的時間復(fù)雜度為，正比于數(shù)據(jù)庫的存儲容量。

4.2 狀態(tài)結(jié)構(gòu)存儲空間分析

所提出的模型模型需要存儲數(shù)據(jù)更新歷史中的所有元組和節(jié)點的值及更新后的元組和節(jié)點值，所以這里所需的存儲空間相當(dāng)于MHBT樹的兩倍，所以在k次更新后，模型所需要的存儲空間為：

模型的空間復(fù)雜度為O(n+klog(n))，正比于數(shù)據(jù)庫容量和數(shù)據(jù)更新次數(shù)。

4.3 數(shù)據(jù)庫更新延遲分析

在MHBT樹中插入或刪除一個元組，相應(yīng)的從葉子節(jié)點到根節(jié)點的路徑信息都需要更新，并且更新后的結(jié)果值還要寫入到歷史記錄表中，所以更新數(shù)據(jù)所需的時間為：

其時間復(fù)雜度為O(logn)

4.4 模型運行效率分析

隔離模型的模型核心是對MHBT樹的比對，而MHBT樹又以元組的形式記錄在數(shù)據(jù)庫表中，故模型相當(dāng)于是在數(shù)據(jù)庫表中查詢和比對相應(yīng)元組值是否相等，查詢時間復(fù)雜度為：

5 結(jié)束語

傳統(tǒng)基于檢查點的數(shù)據(jù)庫恢復(fù)技術(shù)，不論是物理恢復(fù)還是邏輯恢復(fù)，都需要停止數(shù)據(jù)庫服務(wù)，而且要花費相當(dāng)長的時間（將檢查點之后的所有數(shù)據(jù)重新操作一遍）來恢復(fù)，本文提出的模型機制能夠在確定惡意事務(wù)的前提下，通過比對MHBT中數(shù)據(jù)元組值的變化情況，并結(jié)合日志記錄中事務(wù)的操作信息，實現(xiàn)對污染數(shù)據(jù)的精確隔離；同時，通過數(shù)據(jù)與事務(wù)之間的依賴關(guān)系，從日志記錄中篩選出污染事務(wù)，實施精確修復(fù)，減少了數(shù)據(jù)修復(fù)時間，提升數(shù)據(jù)庫恢復(fù)的效率，最大限度的保證了數(shù)據(jù)庫的可生存性。模型機制的優(yōu)點是與數(shù)據(jù)庫日志系統(tǒng)相結(jié)合，但又不完全依賴于日志系統(tǒng)。在不停止數(shù)據(jù)庫服務(wù)的前提下，充分發(fā)揮MHBT樹的數(shù)據(jù)結(jié)構(gòu)特點，提升數(shù)據(jù)庫隔離的精度和速度，提高數(shù)據(jù)恢復(fù)的效率。文章最后通過數(shù)學(xué)分析評估了模型的性能，在下一步的工作中，將針對論文中提出的分析評價參數(shù)，展開算法模型的設(shè)計與實驗性驗證，以在實際應(yīng)用中分析模型的可行性和高效性。

[1]Merkle R C.A certified digital signature[C]//Advances in Cryptology—CRYPTO’89 Proceedings.Springer New York,1990: 218-238.

[2]Martel C,Nuckolls G,Devanbu P,et al.A general model for authenticated data structures[J].Algorithmica,2004,39(1): 21-41.

[3]Devanbu P,Gertz M,Martel C,et al.Authentic data publication over the internet[J].Journal of Computer Security,2003,11(3):291-314.

[4]Ma D,Deng R,and Pang H.Authenticating Query Results From Untrusted Servers Over Open Networks.In Submitted for Publication,2004.

[5]Pang H H,Jain A,Ramamritham K,et al.Verifying completeness of relational query results in data publishing[C]//Proceedings of the 2005 ACM SIGMOD international conference on Management of data.ACM,2005: 407-418.

[6]Li F,Hadjieleftheriou M,Kollios G,et al.Dynamic authenticated index structures for outsourced databases[C]//Proceedings of the 2006 ACM SIGMOD international conference on Management of data.ACM,2006: 121-132.

[7]Jain R,Prabhakar S.Trustworthy Data from Untrusted Databases[C].ICDE,2013.

[8]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].清華大學(xué)出版社,2011.