多級(jí)安全數(shù)據(jù)庫(kù)中的推理問(wèn)題一直是數(shù)據(jù)庫(kù)安全領(lǐng)域的重要研究?jī)?nèi)容。推理問(wèn)題描述的是低安全級(jí)別的用戶可以通過(guò)推理的方法從低安全級(jí)別的信息中得到高安全級(jí)別的信息。通常，低級(jí)用戶都是通過(guò)一系列的查詢來(lái)完成推理的。例如，假設(shè)支持某個(gè)項(xiàng)目的公司信息是高安全等級(jí)的，但用戶可以訪問(wèn)諸如項(xiàng)目、參加會(huì)議的人員以及人員所屬的公司等信息，這樣用戶就可以推斷出每個(gè)公司具體支持哪個(gè)項(xiàng)目。
　　在處理推理問(wèn)題時(shí)存在著柔性訪問(wèn)和響應(yīng)時(shí)間" title="響應(yīng)時(shí)間">響應(yīng)時(shí)間的內(nèi)在平衡。在決定是否授予一個(gè)用戶查詢權(quán)限時(shí)，為了阻止多個(gè)用戶合作進(jìn)行推理，不僅需要考慮該用戶，而且需要考慮具有相同安全等級(jí)的所有用戶以及他們的所有查詢，這個(gè)特性稱為防共謀。這個(gè)特性強(qiáng)化了推理問(wèn)題的復(fù)雜性，因?yàn)檫@個(gè)特性需要一個(gè)新的推理控制方法。該推理方法能夠區(qū)別在一個(gè)推理通道中的n個(gè)用戶、每個(gè)用戶訪問(wèn)" title="用戶訪問(wèn)">用戶訪問(wèn)m－1個(gè)對(duì)象的情況和n(m－1)個(gè)用戶、每個(gè)用戶訪問(wèn)1個(gè)對(duì)象的情況。
　　國(guó)內(nèi)外有許多學(xué)者進(jìn)行推理控制方面的研究，并取得了豐富的成果。在參考文獻(xiàn)^[1]中，F(xiàn)RANCIS CHIN提出了關(guān)于統(tǒng)計(jì)數(shù)據(jù)庫(kù)的推理控制方法。在參考文獻(xiàn)^[2]和^[7]中Su和Ozsoyolu以及吳恒山等提出了關(guān)于函數(shù)依賴和多值依賴的推理控制方法。在參考文獻(xiàn)^[3]中Xiaolei Qian等提出了基于語(yǔ)義網(wǎng)絡(luò)的推理通道的檢測(cè)方法。在參考文獻(xiàn)^[4]中R.Yip和K.Levitt提出了基于推理規(guī)則的推理控制方法。在參考文獻(xiàn)^[5]中M.Stickel提出了基于最大" title="最大">最大信息共享的推理控制方法。以上這些都是設(shè)計(jì)期推理控制方法和推理通道檢測(cè)方面的研究。在查詢期的推理控制方面，一直以來(lái)都是集中在研究基于用戶的查詢歷史的控制方法。2003年Staddon提出了動(dòng)態(tài)推理控制的方法^[6]。本文提出一種基于標(biāo)記的動(dòng)態(tài)推理控制方法。該方法使用訪問(wèn)標(biāo)記來(lái)控制查詢過(guò)程，因此又稱為標(biāo)記方法。該方法能夠有效預(yù)防共謀而且易于實(shí)現(xiàn)。與參考文獻(xiàn)^[6]的方法不同，這種方法在解決推理問(wèn)題并保持快速查詢處理的同時(shí)，還能夠保證用戶的最大訪問(wèn)能力。
1 相關(guān)定義和定理
　　定義1 對(duì)象：數(shù)據(jù)庫(kù)中存儲(chǔ)的信息單元，例如事實(shí)、屬性或者關(guān)系等。本文中以O(shè)表示對(duì)象。
　　定義2 推理通道：由完成一次推理所必需的對(duì)象組成，由n個(gè)對(duì)象組成的推理通道稱為n－通道。
　　定義3 防共謀策略：設(shè)c為一個(gè)整數(shù)，0〈c≤n。對(duì)于一個(gè)推理控制策略，如果c個(gè)用戶共謀也無(wú)法查詢到任一推理通道上的所有對(duì)象，則稱此策略為c防共謀策略。
　　定義4 擁擠控制：如果存在用戶訪問(wèn)一個(gè)推理通道中的對(duì)象數(shù)量達(dá)到最大對(duì)象數(shù)量(m個(gè)對(duì)象中的m－1個(gè))，則沒(méi)有用戶可以通過(guò)查詢完成這個(gè)推理通道。
　　定義5 擁擠控制：設(shè)0〈ε〈1，U表示任意一個(gè)用戶。對(duì)于一個(gè)c防共謀策略，如果c個(gè)用戶中的多于x組的用戶共同訪問(wèn)了m－通道{O₁，……O_m}中的m－1個(gè)對(duì)象：，用戶U能訪問(wèn)剩余對(duì)象{O₁，……O_m}-{}的概率小于ε，則稱該策略具有(x，c，ε)擁擠控制。
　　定理1 設(shè)0〈ε〈1，采取c防共謀策略，q為標(biāo)記數(shù)量。如果這個(gè)策略具有(x，c，ε)擁擠控制，則：
　　

　　引理1 設(shè)0〈ε〈1，如果個(gè)用戶，每個(gè)用戶的訪問(wèn)對(duì)象數(shù)量都已經(jīng)達(dá)到了m－通道的最大對(duì)象數(shù)量，則不屬于x個(gè)用戶中的用戶U能夠同樣訪問(wèn)m－通道中對(duì)象的數(shù)量可以達(dá)到最大對(duì)象數(shù)量的概率大于1-ε。
　　定理2 設(shè)0〈a〈1，如果可以達(dá)到最大對(duì)象數(shù)量的用戶的數(shù)量為，則其他用戶可以訪問(wèn)任何個(gè)對(duì)象的概率大于1-ε。
　　引理2 如果個(gè)用戶最多可以訪問(wèn)m－通道，則其他用戶可以訪問(wèn)m－通道中個(gè)對(duì)象的概率為1。
2 基于標(biāo)記的動(dòng)態(tài)推理控制方法
　　在這個(gè)方法中，首先需要產(chǎn)生訪問(wèn)標(biāo)記的集合，這個(gè)集合由系統(tǒng)的標(biāo)記生成算法自動(dòng)產(chǎn)生。每個(gè)標(biāo)記擁有對(duì)象關(guān)聯(lián)的信息。標(biāo)記集合中標(biāo)記的數(shù)量由推理通道的長(zhǎng)度決定。用K來(lái)表示標(biāo)記集合。本文提供了兩種標(biāo)記方法：(1)標(biāo)記集合僅由數(shù)據(jù)庫(kù)系統(tǒng)使用，因此用戶不必保留任何標(biāo)記；(2)每個(gè)用戶都有一個(gè)秘密標(biāo)記。在初始階段，推理通道中的所有對(duì)象都與標(biāo)記集合中的全部或者部分標(biāo)記相關(guān)聯(lián)。當(dāng)一個(gè)查詢處理算法使用一個(gè)標(biāo)記訪問(wèn)一個(gè)對(duì)象時(shí)，其他訪問(wèn)也使用相同的標(biāo)記訪問(wèn)這個(gè)對(duì)象，這要通過(guò)刪除該對(duì)象與其他標(biāo)記之間的關(guān)聯(lián)來(lái)實(shí)現(xiàn)。通過(guò)這樣的方法，可以確保最大限度的柔性訪問(wèn)控制(用戶可以自主決定訪問(wèn)的對(duì)象并且可以訪問(wèn)推理通道中的任何對(duì)象，只有其中的一個(gè)不能訪問(wèn))。在這個(gè)方法中，響應(yīng)時(shí)間由推理通道的長(zhǎng)度而不是用戶的查詢歷史決定，從而實(shí)現(xiàn)了快速查詢處理。此外，所有的標(biāo)記都是不同的，不同的標(biāo)記不能用來(lái)訪問(wèn)相同的對(duì)象。在后面的討論中將介紹如何通過(guò)該特征防共謀。
　　這種方法分為兩部分：第一部分是標(biāo)記的初始化；第二部分是查詢處理，詳細(xì)說(shuō)明查詢的算法。初始算法只需要運(yùn)行一次(除非整個(gè)系統(tǒng)需要更新)，而查詢處理算法只需要在用戶訪問(wèn)對(duì)象的時(shí)候運(yùn)行。
2.1 單一推理通道的簡(jiǎn)單情況
　　首先考慮數(shù)據(jù)庫(kù)中只有一個(gè)推理通道的情況。m表示推理通道的長(zhǎng)度。推理通道中的對(duì)象由O₁，……，O_m表示。U表示數(shù)據(jù)庫(kù)中的一個(gè)用戶。
　　對(duì)象O與由K(O)表示的標(biāo)記集合相關(guān)聯(lián)。在簡(jiǎn)單的方案中，全部標(biāo)記的數(shù)量為m－1，標(biāo)記的集合K={k₁，……，k_m-1}，推理通道中的每一個(gè)對(duì)象都與全部m－1個(gè)初始標(biāo)記相關(guān)聯(lián)，K(O_i)=K，i=1，2，……，m。
　　查詢處理如下：當(dāng)一個(gè)用戶試圖訪問(wèn)一個(gè)對(duì)象時(shí)，算法將任意選擇一個(gè)標(biāo)記，同時(shí)刪除這個(gè)標(biāo)記與推理通道中其他對(duì)象的關(guān)聯(lián)。當(dāng)所有m－1個(gè)標(biāo)記都被使用時(shí)，推理通道中的m個(gè)對(duì)象中的m－1個(gè)對(duì)象已經(jīng)與標(biāo)記關(guān)聯(lián)。但是，推理通道中還有一個(gè)對(duì)象沒(méi)有與任何一個(gè)對(duì)象所關(guān)聯(lián)。這個(gè)對(duì)象稱為“保留對(duì)象”，這意味著沒(méi)有用戶可以訪問(wèn)這個(gè)對(duì)象。一旦“保留對(duì)象”被認(rèn)定，系統(tǒng)將為其指定一個(gè)指示器。在這種情況下，沒(méi)有用戶可以訪問(wèn)保留對(duì)象。換句話說(shuō)，用戶可以訪問(wèn)推理通道中除了保留對(duì)象之外的全部對(duì)象。因此，一組用戶試圖進(jìn)行共謀推理是沒(méi)有意義的?，F(xiàn)在通過(guò)下面的算法給出該方法的形式化描述。這個(gè)算法由標(biāo)記初始化算法和查詢處理算法組成。K表示由m－1個(gè)標(biāo)記組成的標(biāo)記集合。
　　算法1 單用戶訪問(wèn)對(duì)象O_i的單個(gè)通道方法
　　初始標(biāo)記
　　K(O_i)=K，i=1，……m；
　　查詢處理
　　輸入：I；輸出：是否允許進(jìn)行查詢。
　　步驟：(1)如果標(biāo)記集合為空，則禁止訪問(wèn)；(2)在標(biāo)記集合中任選一個(gè)標(biāo)記；(3)將這個(gè)標(biāo)記賦予查詢對(duì)象；(4)將這個(gè)標(biāo)記從標(biāo)記集合中刪除；(5)將這個(gè)對(duì)象指派給這個(gè)用戶；(6)返回允許查詢。
2.2 無(wú)重復(fù)對(duì)象的多推理通道情況
　　對(duì)于數(shù)據(jù)庫(kù)中有多于一個(gè)推理通道的情況，解決方法是為每個(gè)推理通道制定一個(gè)標(biāo)記集合。C表示一個(gè)推理通道，l表示數(shù)據(jù)庫(kù)中推理通道的數(shù)量，推理通道為C1，……，CI，C_j的長(zhǎng)度由m_j(j=1，……，l)表示，mmax表示所有推理通道中的最大長(zhǎng)度。在這部分中，僅考慮所有推理通道彼此區(qū)分開(kāi)的情況。在這種情況下，標(biāo)記集合K中有mmax－1個(gè)標(biāo)記。
　　查詢處理算法與單個(gè)推理通道中的相應(yīng)算法相似。主要區(qū)別是標(biāo)記集合的初始算法。
　　初始狀態(tài)下，對(duì)通道C_j，k_j由K中任意選擇的m_j-1個(gè)標(biāo)記組成，j=1，2，……，l。如果O_i∈C_j，則K(O_i)=k_j。
　　算法 2 用戶訪問(wèn)O_i的可區(qū)分多通道方法
　　初始標(biāo)記
　　(1)k_j={K中任意選擇m_j-1個(gè)標(biāo)記}，j=1，2，……，l。
　　(2)如果(O_s∈C_j)，則對(duì)所有可能的s，{K(O_s)=k_j；}
　　查詢處理
　　輸入：I；輸出：是否允許進(jìn)行查詢。
　　步驟：(1)如果找不到j(luò)滿足對(duì)象O_i∈C_j，則轉(zhuǎn)(8)步驟；(2)如果標(biāo)記集合為空，禁止訪問(wèn)；(3)在標(biāo)記集合中任選一個(gè)標(biāo)記；(4)將這個(gè)標(biāo)記賦予查詢對(duì)象；(5)將這個(gè)標(biāo)記從標(biāo)記集合中刪除；(6)將這個(gè)對(duì)象指派給這個(gè)用戶；(7)返回允許查詢；(8)返回信息未找到。
2.3 有重復(fù)對(duì)象的多推理通道情況
　　最后，考慮一些對(duì)象在多個(gè)推理通道中重復(fù)出現(xiàn)的情況。查詢處理分為兩種不同的情況：一種情況是重復(fù)的對(duì)象在任何通道中都不是“保留對(duì)象”。在這種情況下，對(duì)重復(fù)對(duì)象的訪問(wèn)與其他對(duì)象相同。另一種情況是用戶試圖訪問(wèn)的重復(fù)對(duì)象是“保留對(duì)象”，這種情況下的訪問(wèn)請(qǐng)求將被系統(tǒng)拒絕。
　　解決這類問(wèn)題應(yīng)使用如下算法。標(biāo)記集合的初始算法與2.2小節(jié)中介紹的相同。所使用的標(biāo)記的數(shù)量是mmax－1。對(duì)于重復(fù)對(duì)象，其標(biāo)記的數(shù)量等于它在所有推理通道中出現(xiàn)的頻率。這里使用k_j(O_i)表示通道C_j中對(duì)象O_i的標(biāo)記集合。
　　算法3 用戶訪問(wèn)O_i的多通道方法
　　初始標(biāo)記
　　(1)k_j={K中任意選擇m_j－1個(gè)標(biāo)記}，j=1，2，……，l；
　　(2)對(duì)所有可能的s，如果(O_s∈C_j)，則k_j(O_s)=k_j，j=1，2，……，l。
　　查詢處理
　　輸入：I；輸出：是否允許進(jìn)行查詢。
　　步驟：(1)如果對(duì)象不屬于推理通道，則轉(zhuǎn)(8)步驟；(2)如果標(biāo)記集合為空，則禁止訪問(wèn)；(3)對(duì)每一個(gè)擁有該對(duì)象的推理通道，任意選擇一個(gè)標(biāo)記集合中的標(biāo)記,依次執(zhí)行(4)～(7)步驟；(4)將這個(gè)標(biāo)記賦予查詢對(duì)象；(5)將這個(gè)標(biāo)記從標(biāo)記集合中刪除；(6)將這個(gè)對(duì)象指派給這個(gè)用戶；(7)返回允許查詢；(8)返回信息未找到。
　　假設(shè)一個(gè)推理通道中存在一個(gè)重復(fù)對(duì)象并存在一個(gè)保留對(duì)象。為了阻止用戶在其余推理通道中得到這個(gè)保留對(duì)象的信息，需要同步考慮這個(gè)對(duì)象在所有包括這個(gè)對(duì)象的推理通道的情況。具體方法是：在重復(fù)對(duì)象被用戶訪問(wèn)之后，在所有包含這個(gè)對(duì)象的推理通道中都將給這個(gè)對(duì)象分配一個(gè)訪問(wèn)標(biāo)記。如果在一個(gè)推理通道中一個(gè)重復(fù)對(duì)象被確認(rèn)為保留對(duì)象，則在所有包含這個(gè)重復(fù)對(duì)象的推理通道中這個(gè)對(duì)象都被確認(rèn)為保留對(duì)象。
3 性能分析
　　為了解決推理問(wèn)題，必須考慮三個(gè)因素：(1)安全性：無(wú)論單個(gè)用戶還是多個(gè)用戶聯(lián)合，通過(guò)推理都不能得到其不能訪問(wèn)的信息。(2)柔性訪問(wèn)：在對(duì)推理進(jìn)行嚴(yán)格控制的基礎(chǔ)上保證最大的信息共享。(3)響應(yīng)時(shí)間：查詢處理時(shí)間需要滿足應(yīng)用的要求。
　　在本方法中，同一安全等級(jí)下的所有用戶都可以訪問(wèn)推理通道中的m－1個(gè)對(duì)象。因此對(duì)于用戶來(lái)說(shuō)，無(wú)論單獨(dú)或者聯(lián)合進(jìn)行推理都不能獲得足夠的推理信息。同時(shí)由于用戶最多可以訪問(wèn)m個(gè)對(duì)象中的m－1個(gè)對(duì)象，從而實(shí)現(xiàn)了柔性控制。標(biāo)記的數(shù)量由通道的最大長(zhǎng)度決定，而且所占存儲(chǔ)空間很小。響應(yīng)時(shí)間與不考慮推理問(wèn)題的情況基本相同。
　　表1給出了Staddon的動(dòng)態(tài)推理方法^[6]和本文方法的比較。