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

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