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

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