淺析函數依賴關系在數據庫推理攻擊中的作用

1數據庫推理控制數據庫中存儲的數據通常具有很高的相關性，這些相關性可以表現為數據之間的依賴關系（例如函數依賴）和完整性限制。在多級安全數據庫中,若低安全級別的用戶利用其已知的數據關聯性,及其有權直接讀取的低安全級別數據,推理出更高安全級別的數據信息,就構成對數據庫的推理攻擊,造成高安全級別數據的泄漏。與其它攻擊方式不同的是,推理攻擊所用數據均由用戶對數據庫進行合法訪問獲得,因此它是一種較為隱蔽的攻擊方式。例如,數據庫將“貨船是否裝載了武器”作為敏感信息,但低安全級別用戶可以查詢“貨船所停靠的碼頭”以及“指定碼頭是否用于裝卸武器”這樣的非敏感信息,進而間接推理出指定貨船是否裝載了武器。數據庫推理控制的研究始于20世紀70年代末,其工作主要集中在問題的定義及框架的建立上。Jajodia證實了數據庫自身約束是造成多級關系數據庫中大多數推理問題的原因。由于問題本身的多樣性與不確定性,尚未有一個通用的能夠解決所有推理問題的方案。目前相對成熟的研究成果主要用于解決一些特定類型的推理問題。Su和嚴和平分別提出了基于數據依賴關系的推理控制方法,通過在設計階段檢測并提高某些敏感數據的安全級別來消除推理泄漏的可能,但無法避免數據可用性被降低的問題。Donald、Raymond和Brodsky分別提出了不同的推理控制方法,在查詢期間檢測并拒絕可能導致推理泄漏的查詢請求,兼顧數據可用性與安全性,但都沒有解決冗長的查詢歷史對性能的影響問題。2003年,Staddon首次明確提出了推理通道的概念,通過在查詢期間對推理通道的對象進行控制,達到防止推理泄漏的目的。該方法在處理用戶查詢時,只需對通道對象進行遍歷,不對查詢歷史進行遍歷,因此在理論上能夠保證較高的查詢效率。但該方法處理有重復對象推理通道的算法過于復雜。同時在大數據情況下,可能會存在大量推理通道,造成較大的時空消耗。本文基于推理通道的思想,通過對通道對象的動態組合,提出了一種新的針對函數依賴的動態推理控制方法。本文第2節對所用術語進行了定義。第3節研究了基于函數依賴關系的推理通道的構造算法,以及相應的動態推理控制方法。第4節是本文工作的總結與展望。2理想國里的函數依賴關系現有針對函數依賴的推理控制主要使用元數據之間的依賴關系,并不關心實際數據之間的依賴關系,即基于這樣一個假設:攻擊者事先已知函數依賴關系FD:X→Y,且已知實際數據之間的依賴關系:X=x1→Y=y1,X=x2→Y=y2,…,X=xn→Y=yn。因此,若要消除該函數依賴關系內部存在的推理危害,必須使X的安全級別不小于Y的安全級別,或者拒絕安全級別小于Y的用戶訪問X。實際上,上述假設過于嚴格,在某些情況下,攻擊者事先只能分析得到數據庫中的函數依賴關系,而無法獲得其實例,若以上述方式消除推理泄漏,則會對數據可用性造成不必要的影響。在考慮推理控制問題時,應根據函數依賴關系的實際情況確定適用的假設。定義函數依賴實例:一個函數依賴關系的實際數據之間的依賴關系,稱為函數依賴實例。定義完全函數依賴推理關系:攻擊者已知函數依賴關系,且已知該函數依賴關系的實例。定義部分函數依賴推理關系:攻擊者已知函數依賴關系,但未知該函數依賴關系的實例。例1.表1中存在完全函數依賴推理關系:(PMath,PChn,PEng)→PAvg,部分函數依賴推理關系:SNo→PMath,SNo→PChn,SNo→PEng等等。注意,在一些特殊情況下,部分函數依賴推理關系應被作為完全函數依賴推理關系,這取決于針對具體問題所做的安全假設。傳統的列級強制訪問控制只以單屬性列的粒度授予安全級別,在很多情況下并不能滿足實際要求。本文將列級強制訪問控制的安全級別粒度擴展為屬性列集合,對于前面提到的“貨船-碼頭-武器”的例子,可將{貨船,武器}設定為敏感屬性,允許低安全等級用戶單獨查詢貨船信息或武器信息,但不允許其獲得貨船與武器之間的關聯關系。在訪問強制控制粒度為單屬性列的情況下,上述安全需求只能通過將兩屬性之一設定為敏感屬性實現。因此屬性列集合的粒度更有利于保證數據可用性。3所需的部分函數依賴推理關系實際的推理攻擊不能僅通過函數依賴關系完成,攻擊者必須得到相應的函數依賴實例。除完全函數依賴推理關系的實例外,攻擊者所需的部分函數依賴推理關系的實例以及其它對象都只能通過對數據庫的查詢來獲得。要防止推理泄漏,就要對這些對象進行控制。3.1可生成性攻擊推理通道是在查詢期間對用戶查詢結果進行分析、對查詢歷史進行過濾的基礎。推理通道的構造必須具有完備性,所有可能導致推理泄漏的通道都必須被構造,否則攻擊者就有可能利用未被構造的推理通道完成推理攻擊。構造基于函數依賴關系的推理通道時,只需考慮函數依賴關系,無須考慮其實例。定義前趨屬性集合:若存在函數依賴關系FD:X→Y,則稱X為Y的前趨屬性集合,記為P(Y)=X。敏感屬性X與其前趨屬性集合P(X)通過函數依賴關系關聯,當攻擊者已知P(X)的值及相應的函數依賴實例時,就能夠推理出X的值,這樣就構成了一條推理通道。一個屬性集合可以對應多個前趨屬性集合,這些集合之間也可能存在前趨關系,這些前趨關系可以用圖來表示。例2.表(A,B,C,D)中,存在函數依賴關系A→B,C→D。定義{B,D}為敏感信息,其前趨屬性集合包括{A,C}、{B,C}、{A,D},它們之間的前趨關系如圖1所示。對上圖進行分析可以得到4條推理通道:IC0={BD},IC1={AD,A-→B},IC2={BC,C→D},IC3={AC,A→B,C→D},其中IC0可以直接通過強制訪問控制機制阻止。上述通道并不是相互獨立的,IC0可以由IC1或IC2轉化得到,IC1和IC2可以由IC3轉化得到。這個轉化過程正是攻擊者進行推理的過程,即從敏感屬性集合的一個前趨屬性集合出發,不斷使用相應的函數依賴關系轉化該集合,最終將其轉化為敏感屬性集合。因此,可以使用自動機描述推理過程并構造推理通道,其狀態包括敏感屬性集合及其前趨屬性集合,輸入字符為函數依賴關系,自動機中任何一個狀態到敏感屬性集合的路徑都可以作為一條推理通道。本文假設在構造推理自動機前,已經分析得到最小函數依賴集,并作為構造算法的輸入之一。推理自動機的構造主要分兩步:首先需要對最小函數依賴集進行擴展,目的是獲得所需的隱含的傳遞依賴關系,然后根據擴展好的函數依賴集構造推理自動機。定義函數依賴關系函數L、R:若存在函數依賴關系F:X→Y,則L(F)=X,R(F)=Y。定理函數依賴的偽傳遞規則:若存在函數依賴關系F1、F2,滿足條件R(F1)L(F2),則存在函數依賴關系F3=F1+F2,其中L(F3)=L(F1)+L(F2)-R(F1),R(F3)=R(F2)。本定理根據Armstrong公理的增廣律和傳遞律即可證得,此處從略。算法1擴展函數依賴集目的:根據偽傳遞規則對最小函數依賴進行擴展。輸入:最小函數依賴集FD＿MIN＿SET。輸出:擴展函數依賴集FD＿SET。步驟:算法分析:條件判斷3)保證R(fk)僅包含一個屬性;步驟7)到13)對fk進行化簡,保證L(fk)中不包含冗余屬性;步驟14)不僅將fk加入FD＿SET中,也將生成fk的過程加入,以便于進行動態推理控制。注意,當一個函數依賴關系存在多種不同的生成過程時,所有過程都被加入到FD＿SET中;步驟16)保證FD＿SET的完備性,即所有能夠通過偽傳遞規則生成的函數依賴關系及相應的生成過程都包含在FD＿SET中。例3.表(A,B,C,D,E,F)中,其最小函數依賴集為{A→B,B→C,D→E,CE→F}。進行擴展后FD＿SET為如下集合:{A→B,B→C,D→E,CE→F,A→C=(A→B)+(B→C),BE→F=(B→C)+(CE→F),CD→F=(D→E)+(CE→F),AE→F=(A→B)+(BE→F)=(A→C)+(CE→F),BD→F=(B→C)+(CD→F)=(D→E)+(BE→F),AD→F=(A→B)+(BD→F)=(A→C)+(CD→F)=(D→E)+(AE→F)}。算法2構造推理自動機目的:根據擴展后的函數依賴集構造推理自動機輸入:敏感屬性集合,擴展函數依賴集FD＿SET輸出:推理自動機MIC=<Q,δ,q0>,其中:Q為狀態集合,其元素為屬性集合;δ為狀態轉移函數;q0為初始狀態,為敏感屬性集合。步驟:算法分析:步驟6)得到qi的一個前趨屬性集合qk;步驟8)到14)對qk進行化簡;步驟15)對21)qi與qk之間的關聯關系fSet進行化簡;步驟25)保證qi的全部直接前趨屬性集合都被生成;步驟26)保證Q中的所有屬性集合都經過了上述處理。因此步驟25)、26)共同保證了所構造自動機的完備性。上述完備性是指所有包含前趨屬性集合的推理通道都能夠由本算法構造得到,所有僅包含函數依賴關系的推理通道已在算法1中構造得到。3.2生成通道實例傳統的設計期推理控制通過事先調整對象的安全等級來防止推理泄漏,調整只能提升對象的安全等級,這將使部分用戶無法再訪問這些對象,造成數據可用性的降低。為保證數據可用性,應在數據庫運行階段對敏感屬性進行動態推理控制。推理通道是基于元數據構造的,造成實際泄漏的是推理通道實例,其概念與函數依賴實例類似,此處從略。推理通道實例與實際數據有關,在數據庫中有大量數據的情況下,推理通道實例的數量也將是很大的。若生成并動態維護全部實例,將會占用大量,甚至數倍于原始數據的空間,這也將導致通道檢索或遍歷操作效率低下。當同一推理問題中的不同通道之間存在重復對象時,上述問題將更加明顯。如例2中,對象A→B同時包含在通道IC1、IC3中,對象C→D同時包含在通道IC2、IC3中。推理通道的基本組成元素是對象,對象通過一定的規則構成推理通道。因此可不生成全部通道實例,只生成通道的構造規則,在需要時將規則應用于對象動態構造通道實例。這樣只需生成全部對象以及相應的構造規則即可表示全部通道實例,能夠有效的降低空間消耗。通道實例的動態構造是該方法的核心步驟,影響構造效率的因素主要有二:一是構造算法的復雜程度,二是對象實例的檢索效率。由前一節的分析可知,在基于函數依賴關系的推理問題中,以自動機形式描述的推理通道形式簡單,易于實現簡單的構造算法;同時,對象可根據不同的函數依賴關系或前趨屬性集合分類存儲,檢索效率較高。因此,該方法適用于基于函數依賴關系的動態推理控制。可在數據庫運行階段記錄用戶已知的歷史對象,并在用戶發出查詢請求時根據結果集所包含的對象和歷史對象動態構造通道實例。若所有對象都無法組合成一條完整的推理通道實例,則允許本次查詢;否則,拒絕本次查詢或將結果集修改后再返回給用戶。在使用該方法進行推理控制前,需要確定所有函數依賴關系的類型。這取決于函數依賴關系本身的性質,以及針對具體問題所做的安全假設。對于完全函數依賴推理關系,應將其所有實例作為已知對象添加到歷史對象集中,并在數據庫運行階段根據數據的變化進行更新。算法3輸入:擴展函數依賴集FD-SET,推理自動機MIC,查詢結果集RES＿SET,歷史對象集HIS＿OBJ＿SET。輸出:修改后的查詢結果集RES＿SET。步驟:1)取RES＿SET中一條元組Ti;2)取Ti包含的所有函數依賴實例的集合fdSet;3)根據FD＿SET、HIS＿OBJ＿SET生成可由fdSet間接獲得的函數依賴實例并添加至fdSet;4)if(fdSet中包含敏感信息)5)從RES＿SET中刪除Ti并轉到11);6)取Ti包含的所有敏感信息的前趨屬性集合pSet;7)根據fdSet、pSet、HIS＿OBJ＿SET、MIC構造通道實例;8)if(構造成功)9)從RES＿SET中刪除Ti并轉到11);10)將fdSet、pSet中的所有對象實例添加到HIS＿OBJ＿SET中;11)返回1)重復上述過程,直至處理完RES-SET中的所有元組。4使用新的數據庫設計方法特點對比數據庫推理控制是對強制訪問控制機制的重要補充。本文基于推理通道的思想,提出了一種動態組合通道實例的方法,實現了針對函數依賴的動態推理控制。與傳統的針對函數依賴的推理控制相比,本文的