移動(dòng)自組網(wǎng)中多級(jí)安全事務(wù)的并發(fā)控制

雷向東，陳莉莉

(中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙 410083)

移動(dòng)自組網(wǎng) MANETS（Mobile Ad Hoc Networks）是由多個(gè)移動(dòng)節(jié)點(diǎn)通過無線鏈路相連接，具有時(shí)變拓?fù)浣Y(jié)構(gòu)的一個(gè)多跳、臨時(shí)性自治系統(tǒng)。MANETS中的數(shù)據(jù)庫系統(tǒng)是由許多移動(dòng)主機(jī)組成的動(dòng)態(tài)分布式數(shù)據(jù)庫系統(tǒng)。通常分布式數(shù)據(jù)庫中總是有若干個(gè)事務(wù)在運(yùn)行，這些事務(wù)可能并發(fā)地存取相同的數(shù)據(jù)。當(dāng)數(shù)據(jù)庫中有多個(gè)事務(wù)并發(fā)運(yùn)行時(shí)，系統(tǒng)必須對(duì)并發(fā)事務(wù)之間的相互作用加以控制，即通過并發(fā)控制機(jī)制來實(shí)現(xiàn)。然而，由于在MANET網(wǎng)絡(luò)中節(jié)點(diǎn)到處移動(dòng)導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁變化，使得很多有線網(wǎng)絡(luò)中的并發(fā)技術(shù)在MANET網(wǎng)絡(luò)中行不通。例如鎖機(jī)制或時(shí)間戳機(jī)制，這些并發(fā)控制機(jī)制被應(yīng)用到MANET的多級(jí)事務(wù)時(shí),將會(huì)產(chǎn)生很多問題，如隱通道、高級(jí)事務(wù)被餓死和檢索異常等[1]。因此解決MANETS中多級(jí)事務(wù)的并發(fā)控制具有重要的意義。

MANETS中的數(shù)據(jù)庫管理系統(tǒng)（DBMS）是一個(gè)由不同訪問權(quán)限的用戶共享的、包含多安全等級(jí)數(shù)據(jù)的安全系統(tǒng)。系統(tǒng)中的每一個(gè)數(shù)據(jù)項(xiàng)具有其安全等級(jí)，并且每一個(gè)用戶被賦予不同的訪問權(quán)限。由于這些特點(diǎn)，并發(fā)執(zhí)行的事務(wù)可能導(dǎo)致不同的主體為了獲取數(shù)據(jù)而產(chǎn)生競爭，進(jìn)而競爭會(huì)導(dǎo)致安全問題，于是就要求DBMS對(duì)并發(fā)操作進(jìn)行正確調(diào)度[2]，即允許非沖突的事務(wù)并行執(zhí)行，而沖突的事務(wù)必須被串行化，即實(shí)現(xiàn)可串行化調(diào)度。

為保證MANETS中多級(jí)安全數(shù)據(jù)庫的完整性和一致性，本文提出一種運(yùn)用在MANET中的多版本兩段鎖并發(fā)控制協(xié)議。

1 多級(jí)事務(wù)

首先，看一個(gè)多級(jí)事務(wù)的例子：

這里R（x,U,S）表示具有秘密密級(jí)的主體在具有公開安全級(jí)的對(duì)象x上的一個(gè)讀操作；同樣，W（y,S,S）表示具有秘密密級(jí)的主體在具有秘密安全級(jí)的對(duì)象y上的一個(gè)寫操作。對(duì)于這類多級(jí)事務(wù)，定義被簡化為如下形示：

這個(gè)主體的分類級(jí)別與事務(wù)名有關(guān)聯(lián)。

1.1 多級(jí)事務(wù)處理系統(tǒng)

目前多級(jí)安全事務(wù)處理系統(tǒng)有4種主要的體系結(jié)構(gòu)：基于完整性鎖的體系結(jié)構(gòu)、基于內(nèi)核化的體系結(jié)構(gòu)、基于數(shù)據(jù)復(fù)制的體系結(jié)構(gòu)和基于可信主體的體系結(jié)構(gòu)。這里以基于可信主體的體系結(jié)構(gòu)為例，由DBMS自身實(shí)現(xiàn)強(qiáng)制訪問控制。要求運(yùn)行在多級(jí)安全局域網(wǎng)上，通過安全網(wǎng)絡(luò)進(jìn)行通信，所有對(duì)數(shù)據(jù)庫的訪問必須通過可信DBMS，DBMS在多個(gè)文件中存儲(chǔ)多級(jí)數(shù)據(jù)庫。在可信主體體系結(jié)構(gòu)中實(shí)現(xiàn)多級(jí)安全的事務(wù)處理所遵循的機(jī)制如圖1所示。

圖中事務(wù)管理器TM(Transaction Manager)由可信事務(wù)管理器和各安全級(jí)上的不可信事務(wù)管理器組成。事務(wù)管理器負(fù)責(zé)管理所有事務(wù)的執(zhí)行，事務(wù)的每一個(gè)操作都需要事務(wù)管理器的調(diào)解。對(duì)于單級(jí)事務(wù)，系統(tǒng)將它發(fā)送給該安全級(jí)上的不可信事務(wù)管理器進(jìn)行處理。對(duì)于多級(jí)事務(wù)，事務(wù)管理器用單級(jí)事務(wù)的處理機(jī)制來實(shí)現(xiàn)多級(jí)事務(wù)的處理。系統(tǒng)首先將多級(jí)事務(wù)發(fā)送給可信事務(wù)管理器，然后可信事務(wù)管理器將多級(jí)事務(wù)劃分為單安全級(jí)的子事務(wù)，將這些子事務(wù)分別發(fā)送給相應(yīng)安全級(jí)的不可信事務(wù)管理器。可信鎖管理器負(fù)責(zé)安全鎖協(xié)議的實(shí)現(xiàn)，它的主要功能是提供對(duì)數(shù)據(jù)項(xiàng)的加鎖和解鎖操作。可信文件管理器管理對(duì)數(shù)據(jù)項(xiàng)的物理訪問。

1.2 一種安全調(diào)度框架

要實(shí)現(xiàn)一個(gè)多級(jí)事務(wù)調(diào)度的安全性能需實(shí)現(xiàn)以下兩方面安全性：

（1）調(diào)度協(xié)議的安全性；

（2）執(zhí)行的安全性。

本文只關(guān)注第一部分,通過分析協(xié)議，可以估計(jì)一個(gè)調(diào)度的內(nèi)在的安全性。無需考慮調(diào)度的執(zhí)行就可以評(píng)估調(diào)度。不安全的調(diào)度協(xié)議能夠在執(zhí)行之前被發(fā)現(xiàn)。如果調(diào)度協(xié)議是安全的，則可以考慮對(duì)執(zhí)行問題做分析；否則，很可能將對(duì)協(xié)議的分析簡化為對(duì)執(zhí)行情況的分析。

1.3 多版本調(diào)度

在數(shù)據(jù)庫中，多版本調(diào)度允許一個(gè)元素有多個(gè)版本。這種特征降低了對(duì)一個(gè)元素的爭奪。一個(gè)多版本調(diào)度產(chǎn)生的調(diào)度表稱為一個(gè)完整的調(diào)度時(shí)間表，表示為（s，V）。其中s代表輸出操作，V代表版本類型。它映射了輸出操作s與被訪問元素版本V之間的關(guān)系。其中版本V有3種類型：(1)到寫版本的先前操作的參考；(2)到新版本的參考，即寫操作創(chuàng)建一個(gè)新版本；(3)到空版本的參考，即一個(gè)元素的寫操作會(huì)被丟棄。當(dāng)操作到達(dá)時(shí)，調(diào)度程序會(huì)做出3個(gè)基本決定：(1)操作是否可以立即執(zhí)行；(2)讀操作或?qū)懖僮鞯膶?shí)體是什么版本；(3)調(diào)度是否可以繼續(xù)。而調(diào)度程序會(huì)根據(jù)本身的間隔狀態(tài)做出決定。

現(xiàn)在，定義一種調(diào)度程序，把這個(gè)程序之前的輸出操作定義為調(diào)度狀態(tài)，這里只討論調(diào)度程序的輸出操作，不考慮為讀或?qū)懖僮鞣峙浒姹尽?/p>

定義1一個(gè)調(diào)度程序是輸出狀態(tài)等價(jià),當(dāng)且僅當(dāng)任意兩個(gè)狀態(tài) st1、st2有各自的輸出（s1，V1）、（s2，V2），如果s1等于s2，則s1對(duì)一個(gè)即將被調(diào)度的程序的操作決策與s2對(duì)該程序做出的操作決策是相同的。換言之，一個(gè)輸出狀態(tài)等價(jià)調(diào)度，如果兩個(gè)不同狀態(tài)調(diào)度的輸出操作是相同的，則這兩個(gè)狀態(tài)是等價(jià)的。這意味著到達(dá)的操作即將被調(diào)度，但發(fā)生了延遲，不過不影響調(diào)度程序所做的決定。

現(xiàn)在定義一個(gè)輸出狀態(tài)等價(jià)的弱版本。在這種情況下，輸出操作僅決定帶有決策的調(diào)度行為。

定義2 一個(gè)調(diào)度程序是輸出調(diào)度沖突,當(dāng)且僅當(dāng)任意兩個(gè)狀態(tài) st1、st2有各自的輸出（s1，V1）、（s2，V2）。 如果s1等于s2，則 s1對(duì)一個(gè)即將被調(diào)度的程序的操作決策與s2對(duì)該程序做出的操作決策是相同的。

如圖2所示的簡單調(diào)度模型中，操作從左邊輸入，右邊輸出。如果一個(gè)操作不能被立即調(diào)度，它將被排在隊(duì)列中。調(diào)度問題主要關(guān)注事務(wù)操作的順序，以便保持正確性，并允許同一時(shí)間的并發(fā)性。如果兩個(gè)事務(wù)之間出現(xiàn)沖突，就將事務(wù)串行化。

2 多版本兩段鎖協(xié)議

[3]提出了一種使用多版本數(shù)據(jù)的安全的并發(fā)控制機(jī)制。當(dāng) Ti試圖寫一個(gè)數(shù)據(jù)對(duì)象x時(shí)發(fā)現(xiàn)Ts已經(jīng)在x上請(qǐng)求了一個(gè)讀鎖，Ti就創(chuàng)建了x的一個(gè)新的版本。因?yàn)橥ㄟ^給每一個(gè)多級(jí)事務(wù)一個(gè)不同的版本已經(jīng)解決了沖突，所以就避免了隱通道的創(chuàng)建。然而，這樣做帶來了新的問題，即高級(jí)事務(wù)的讀操作讀到的可能是不一致的版本，即所謂的檢索異常。但是在兩段鎖協(xié)議中，一個(gè)事務(wù)應(yīng)當(dāng)在確定其不再需要其他加鎖的情況后才釋放所持有的鎖。于是下面提到的多版本兩階段封鎖協(xié)議可以解決檢索異常問題。

2.1 多版本兩段鎖協(xié)議概述

每一個(gè)只讀事務(wù)Ti發(fā)出讀數(shù)據(jù)項(xiàng)Q時(shí)，返回值是小于Ts(Ti)時(shí)間戳的最大版本Qk的內(nèi)容。這是因?yàn)橐粋€(gè)事務(wù)應(yīng)讀取在它之前的最近版本。更新事務(wù)執(zhí)行兩段鎖協(xié)議，在提交之前不釋放任何鎖，事務(wù)可以按其提交的順序串行化，更新事務(wù)Ti。讀取數(shù)據(jù)項(xiàng)Q時(shí)，Ti在獲得數(shù)據(jù)項(xiàng)Q上的共享鎖后讀取Q最新版本的值。更新事務(wù)Ti。想寫數(shù)據(jù)項(xiàng)Q時(shí)，Ti首先要獲得數(shù)據(jù)項(xiàng)Q上的排它鎖，然后為Q創(chuàng)建一個(gè)新版本，寫操作在新版本上進(jìn)行。新版本的時(shí)間戳初值為∞，它大于任何可能的時(shí)間戳值。在創(chuàng)建此版本的事務(wù)Ti完成之前，阻止其他只讀事務(wù)對(duì)此版本進(jìn)行讀操作。當(dāng)更新事務(wù)Ti完成后，Ti將它創(chuàng)建的每一個(gè)版本的時(shí)間戳設(shè)為Counter+1。然后Ti將Counter增加1。在Counter增加之前啟動(dòng)的只讀事務(wù)將看到被Ti更新之前的值。無論是哪種情況，只讀事務(wù)均不必等待加鎖[4]。

2.2 多版本兩段鎖調(diào)度算法

多版本調(diào)度允許同一實(shí)體有多個(gè)版本，通過限制訪問一個(gè)實(shí)體的競爭加強(qiáng)并發(fā)性。這種競爭會(huì)引起不安全調(diào)度或者不安全恢復(fù)。這里考慮到的調(diào)度之一是沖突集調(diào)度。這個(gè)調(diào)度的輸出是有序沖突調(diào)度的集合。有序沖突的定義如下：

定義3一個(gè)調(diào)度是有序沖突的，當(dāng)且僅當(dāng)它能通過一系列0次或者多次轉(zhuǎn)換變成一個(gè)有序調(diào)度。在這些轉(zhuǎn)換中，任何一對(duì)來自不同事務(wù)的相鄰步驟可以互換,除非它們相沖突。即兩個(gè)事務(wù)沖突，如果它們訪問相同實(shí)體并且這兩個(gè)實(shí)體中至少有一個(gè)正在執(zhí)行寫操作。接下來定義一種調(diào)度屬性——安全級(jí)別有序。

定義4 一個(gè)調(diào)度是安全級(jí)別有序的,當(dāng)且僅當(dāng)調(diào)度中所有的事務(wù)對(duì)p和q共享一個(gè)單一主題的分類等級(jí)，且在一個(gè)序列順序中p緊跟q或q緊跟p。

根據(jù)上述描述，設(shè)計(jì)多版本兩段鎖并發(fā)控制調(diào)度算法,其算法描述如下：

(1)在沖突集 Ci（Q）上搜索在數(shù)據(jù)項(xiàng) Q的持鎖事務(wù)Ti和優(yōu)先級(jí)最高事務(wù) Tj；

(2)如果Tj估計(jì)運(yùn)行時(shí)間+系統(tǒng)時(shí)間≤Tj截止時(shí)間并且Ti截止時(shí)間

(3)判斷 Tj在數(shù)據(jù)項(xiàng) Q上是否持有排他鎖，若沒有則轉(zhuǎn)到步驟（7）；(4)判斷Ti是否申請(qǐng)共享鎖，若沒有，則轉(zhuǎn)到步驟(6)；(5)在沖突集Ci（Q）上，每個(gè)申請(qǐng)共享鎖的事務(wù)獲準(zhǔn)共享鎖，執(zhí)行步驟（9）；

(6)獲準(zhǔn) Ti排它鎖，執(zhí)行步驟（9）；

(7)判斷Tj在數(shù)據(jù)項(xiàng)Q上是否持共享鎖，若沒有，則轉(zhuǎn)到步驟（9）；

(8)Ti獲得排他鎖，Tj重啟動(dòng)；

(9)算法結(jié)束。

本算法中只讀事務(wù)不必等待任何鎖。更新事務(wù)在對(duì)數(shù)據(jù)項(xiàng)加鎖發(fā)生沖突時(shí)，若持鎖的事務(wù)優(yōu)先級(jí)低，而重啟動(dòng)不會(huì)延誤截止時(shí)間，則持鎖的事務(wù)重啟動(dòng)。在該協(xié)議中，一次只允許一個(gè)更新事務(wù)提交。

3 模擬仿真和性能分析

仿真的目的是研究新提出的并發(fā)控制協(xié)議在MANETS中的性能。為了對(duì)比，選用多版本協(xié)議和兩段鎖協(xié)議作為基準(zhǔn)協(xié)議。主要的性能指標(biāo)為延誤截止時(shí)間率和重啟動(dòng)率。仿真模型由移動(dòng)主機(jī)和廣播磁盤組成。廣播磁盤傳輸數(shù)據(jù)項(xiàng)和控制信息，數(shù)據(jù)項(xiàng)所有版本放在同一個(gè)磁盤上，每個(gè)數(shù)據(jù)項(xiàng)所有版本將相繼廣播，熱數(shù)據(jù)的老版本位于最新版本之后，都放在快速磁盤上。冷數(shù)據(jù)所有版本則位于慢速磁盤上。一個(gè)數(shù)據(jù)項(xiàng)所有版本以相同的頻率廣播[5-6]。仿真參數(shù)如表1所示，一旦事務(wù)截止時(shí)間到，事務(wù)立即結(jié)束。

表1 仿真測試參數(shù)

從圖3、圖4可以看出，在MANETS網(wǎng)絡(luò)中多版本兩階段封鎖協(xié)議的性能優(yōu)于多版本協(xié)議和兩段鎖協(xié)議,且事務(wù)到達(dá)率越高效果就越明顯。前者的延誤截止時(shí)間率、重啟動(dòng)率都比較低。這是由于多版本機(jī)制消除了只讀事務(wù)和更新事務(wù)的沖突，降低了只讀事務(wù)的響應(yīng)時(shí)間，又通過多版本動(dòng)態(tài)調(diào)整串行次序，而兩階段鎖協(xié)議保證了并發(fā)操作調(diào)度的正確性，避免了一切不必要的事務(wù)重啟動(dòng)。又因?yàn)橐苿?dòng)事務(wù)在移動(dòng)主機(jī)上進(jìn)行了部分有效性確認(rèn)，從而及早地檢測了數(shù)據(jù)沖突，進(jìn)而減少了移動(dòng)事務(wù)延誤截止時(shí)間率。此外，多版本機(jī)制消除了移動(dòng)只讀事務(wù)和移動(dòng)更新事務(wù)之間沖突，讀請(qǐng)求從不失敗且不必等待。

該文提出了在MANETS中處理多級(jí)安全事務(wù)要采用的多版本兩段鎖并發(fā)控制協(xié)議。該協(xié)議結(jié)合了多版本和兩段鎖協(xié)議的優(yōu)點(diǎn)，在MANETS中提高了事務(wù)的并發(fā)度，讀請(qǐng)求從不失敗且不必等待，事務(wù)間沖突通過等待解決而不是通過回滾解決。

該協(xié)議與兩段鎖協(xié)議、多版本協(xié)議相比，在多級(jí)事務(wù)的處理上能更好地保證數(shù)據(jù)的完整性和一致性。仿真結(jié)果表明,在正常負(fù)載下其延誤截止時(shí)間率和重啟動(dòng)率都要低得多，性能較好。

參考文獻(xiàn)

[1]KIM H W，PARK D S.Advanced transaction scheduling protocol for multilevel secure database in wireless mobile network environment[C].Joint 4th IEEE International Conference on ATM(ICATM 2001)and High Speed Intelligent Internet Symposium,2001.

[2]曲立平.基于多版本的多級(jí)安全并發(fā)控制機(jī)制的研究[J].信息技術(shù),2005,52（6）：14-16.

[3]李麗萍，何守才.數(shù)據(jù)庫多級(jí)安全模型的研究[J].上海第二工業(yè)大學(xué)學(xué)報(bào)，2006，23（3）：218-222.

[4]雷向東，袁曉莉.并行實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)多版本兩階段封鎖并發(fā)控制協(xié)議[J].中南工業(yè)大學(xué)學(xué)報(bào)，2003,34（3）：298-301.

[5]雷向東，袁曉莉.多版本兩階段封鎖并發(fā)控制協(xié)議性能研究[J].計(jì)算機(jī)工程與科學(xué)，2003,25(04):46-49.

[6]RAHBAR A.A new data communication protocol for distributed mobile datbases in mobile Ad Hoc networks[C].Sixth International Conference on Information Technology,2009.