趙 飛 蘇 忠 丁 小

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

0 引言

數(shù)據(jù)庫安全一直以來都是信息安全領(lǐng)域的熱點(diǎn)問題。隨著云計(jì)算、物聯(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ù)庫安全機(jī)制側(cè)重于保護(hù)數(shù)據(jù)的保密性、完整性和可用性，但無法滿足數(shù)據(jù)庫可生存性要求，即數(shù)據(jù)庫在遭受到非人為系統(tǒng)故障、內(nèi)部或外部攻擊時(shí)持續(xù)提供關(guān)鍵服務(wù)的能力。要實(shí)現(xiàn)數(shù)據(jù)庫可生存性，很關(guān)鍵的一點(diǎn)是必須能夠快速發(fā)現(xiàn)并隔離惡意事務(wù)和受污染數(shù)據(jù)，并且及時(shí)恢復(fù)相關(guān)事務(wù)和數(shù)據(jù)。隨著數(shù)據(jù)庫數(shù)據(jù)規(guī)模的急劇增大，事務(wù)提交異常頻繁，如何能夠在惡意事務(wù)檢測以后，在確保隔離精度的前提下，最大限度的減少隔離和恢復(fù)的時(shí)間就成為一個(gè)重要的研究方向，因?yàn)樗苯雨P(guān)系著數(shù)據(jù)庫持續(xù)提供服務(wù)的能力。

1 相關(guān)研究

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

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

2 基本概念介紹

2.1 單列哈希算法

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

2.2 Merkle哈希樹

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

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

圖1 Merkle哈希樹

2.3 B+-tree

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

樹中每個(gè)非葉節(jié)點(diǎn)最多有m棵子樹；

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

若根節(jié)點(diǎn)同時(shí)又是葉節(jié)點(diǎn)，則節(jié)點(diǎn)格式同葉節(jié)點(diǎn)。

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

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

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

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

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

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

圖3 Merkle哈希B+樹

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

3.1 假設(shè)條件

模型自身并不檢測惡意事務(wù)。本文設(shè)計(jì)模型本身并不檢測一個(gè)事務(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í)行的完整性要求每一個(gè)事務(wù)在提交時(shí)數(shù)據(jù)庫必須處于一致的狀態(tài)，即之前所有的合法的提交事務(wù)都已全部有序的提交并修改完相應(yīng)的數(shù)據(jù)元組，從而確保數(shù)據(jù)庫狀態(tài)變化的與事務(wù)提交之間的強(qiáng)相關(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)模型

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

圖4 系統(tǒng)模型

3.3 模型描述

在以上假設(shè)條件基礎(chǔ)上，就可以設(shè)計(jì)模型使用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é)果后計(jì)算而來的，這樣就能夠通過MHBT建立數(shù)據(jù)庫狀態(tài)和事務(wù)提交之間的一一對應(yīng)關(guān)系。

3.3.1 初始化

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

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

07 張七 男 19 計(jì)算機(jī)…… …… …… …… ……18 張18 男 19 計(jì)算機(jī)…… …… …… …… ……26 張26 男 19 計(jì)算機(jī)27 張27 男 19 計(jì)算機(jī)

圖5 模型初始化MHBT0示例

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

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

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

（1）比較根節(jié)點(diǎn)的值。在證據(jù)結(jié)構(gòu)歷史表中存儲(chǔ)有數(shù)據(jù)庫歷次更新后，各節(jié)點(diǎn)的變更信息，依據(jù)事務(wù)號(hào)及節(jié)點(diǎn)層級號(hào)能夠快速實(shí)施對根節(jié)點(diǎn)的比對：如果根節(jié)點(diǎn)值一樣，則根據(jù)MHBT樹結(jié)構(gòu)的特點(diǎn)，可以判定該事務(wù)沒有修改任何數(shù)據(jù)元組，為只讀事務(wù)，不記錄到寫事務(wù)表中；如果根節(jié)點(diǎn)值不一樣，則能確定該事務(wù)對數(shù)據(jù)元組執(zhí)行了修改操作，為寫事務(wù)，記錄到寫事務(wù)列表中，同時(shí)，依據(jù)證據(jù)結(jié)構(gòu)歷史表中存儲(chǔ)的信息，比對出所有變化的葉結(jié)點(diǎn)信息，以此來鎖定所有被修改的數(shù)據(jù)元組。如圖7中所示，T(1)，T(2)，T(3)，T(11)都執(zhí)行了寫操作，在首次判定時(shí)都會(huì)被記錄到寫事務(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ù)為強(qiáng)相關(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，因?yàn)槭聞?wù)T(1) ，T(2)對X執(zhí)行了寫操作，會(huì)被判定為強(qiáng)相關(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存儲(chǔ)端會(huì)通過其事務(wù)標(biāo)識(shí)號(hà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存儲(chǔ)端將事務(wù)隔離確定的受損數(shù)據(jù)和污染數(shù)據(jù)以事務(wù)請求方式在數(shù)據(jù)庫服務(wù)端加鎖（利用數(shù)據(jù)庫中的排他鎖，對相關(guān)數(shù)據(jù)實(shí)施加鎖操作），新事務(wù)請求中如果有訪問到這兩種數(shù)據(jù)則推遲執(zhí)行，等待訪問數(shù)據(jù)的恢復(fù)操作；如果沒有則正常提交事務(wù)，按要求生成新的數(shù)據(jù)庫證據(jù)結(jié)構(gòu)記錄到MHBT存儲(chǔ)端相關(guān)的數(shù)據(jù)表中。這樣就將正確數(shù)據(jù)與錯(cuò)誤數(shù)據(jù)合理分割，區(qū)別對待，在確保數(shù)據(jù)庫持續(xù)提供服務(wù)的同時(shí)執(zhí)行受損數(shù)據(jù)的逐個(gè)恢復(fù)，最大限度的保證用戶的服務(wù)請求，如圖9所示。

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

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

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

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

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

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

（3）依據(jù)事務(wù)操作信息，讀取MHBT存儲(chǔ)端證據(jù)結(jié)構(gòu)MHBT中存儲(chǔ)的相關(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)建時(shí)間

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

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

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

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

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

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

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

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

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

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

4.4 模型運(yùn)行效率分析

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

5 結(jié)束語

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