黎 明

(廣東理工學(xué)院 信息技術(shù)學(xué)院,廣東 肇慶 526100)

隨著計算機(jī)應(yīng)用的普及和信息技術(shù)的不斷發(fā)展,與之息息相關(guān)的數(shù)據(jù)庫技術(shù)的發(fā)展也日趨成熟與完善,應(yīng)用范圍越來越廣泛。數(shù)據(jù)庫技術(shù)是計算機(jī)信息技術(shù)的重要組成部分,數(shù)據(jù)庫中包含了用戶隱私、商業(yè)機(jī)密等各種重要信息,因此容易成為受到攻擊并進(jìn)行數(shù)據(jù)竊取的目標(biāo)[1]。目前常規(guī)的訪問控制手段,對于重要數(shù)據(jù)以及敏感數(shù)據(jù)來說,難以起到完備的保護(hù)作用。因此,借助加密算法加密數(shù)據(jù)庫中的數(shù)據(jù),已成為一種常見的數(shù)據(jù)庫數(shù)據(jù)保護(hù)手段[2]。此類方法能夠較好地提升數(shù)據(jù)庫的安全性,但是數(shù)據(jù)在被加密之后,往往容易失去數(shù)據(jù)本身具有的相似性、有序性以及可比性,這對加密數(shù)據(jù)來說,顯然會影響查詢效率[3-4]。如何保證密文數(shù)據(jù)庫在起到加密保護(hù)作用的同時,也能夠?qū)崿F(xiàn)快速查詢,成為業(yè)界研究的重難點。目前已有的針對嵌入式加密數(shù)據(jù)庫的快速查詢方案,在針對劃分值的提取上仍然存在有待改進(jìn)之處。本研究針對常見的缺陷,提出以最佳桶劃分為基礎(chǔ)依據(jù)的嵌入式加密數(shù)據(jù)庫快速查詢與儲存的方案。

1 以最佳桶劃分為依據(jù)的數(shù)據(jù)庫加密方案

1.1 快速查詢的嵌入式數(shù)據(jù)庫加密

數(shù)據(jù)庫加密的具體流程可以簡述如下:

設(shè)原始數(shù)據(jù)表為ω(k,j),那么針對該數(shù)據(jù)表分類的公式為

(1)

式(1)中:加密數(shù)據(jù)的屬性通過Kjk表示,標(biāo)類號通過li表示,數(shù)據(jù)中待分類的部分通過λi表示,數(shù)據(jù)屬性對應(yīng)獨立條件通過δ表示。加密過程為

(2)

式(2)中:H_exch為數(shù)據(jù)加密后的密文,隨機(jī)數(shù)的生成通過Q(I)完成,以實現(xiàn)密鑰的初始化功能,響應(yīng)系統(tǒng)中初始的參數(shù)值用μ表示,由加密屬性推得關(guān)鍵數(shù)的索引用m(k,v)表示,相鄰的加密數(shù)據(jù)中二次迭代的對應(yīng)通過AS(i,θ)表示,加密屬性提取后對應(yīng)的劃分值通過ξ(i,k)表示,ψ為不用加密數(shù)據(jù)類對應(yīng)的權(quán)重參數(shù)。

分類隱私加密方式為

(3)

1.1.1 字符型數(shù)據(jù)加密的存儲

圖1 存儲字符型數(shù)據(jù)加密流程

1.1.2 字符型數(shù)據(jù)加密的查詢

針對字符串加密進(jìn)行SQL(Structured Query Language)查詢,可以通過兩階段查詢方式來實現(xiàn)[6]。初次查詢是粗糙查詢,主要的方式是過濾待查詢字符串當(dāng)中的索引字段。但在過濾的過程中,可能會錯漏掉部分字段,產(chǎn)生一定的“偽記錄”,因此需進(jìn)行第二次查詢(精確查詢),對模糊查詢得到的結(jié)果,再次進(jìn)行SQL語句查詢。在實際實施過程中,通過隨機(jī)映射函數(shù)的方式進(jìn)行查詢,如對Ai=b進(jìn)行查詢時,得到的映射函數(shù)可表示為

MapQAi(b)=IdentQAi(lj)

(4)

式(4)中,包含b對應(yīng)的劃分用lj表示。當(dāng)Ai>b時進(jìn)行查詢,此時的映射函數(shù)應(yīng)當(dāng)滿足條件MapQAi>b,且映射值包含的劃分{li,li+1,…,lj}應(yīng)當(dāng)全部大于b對應(yīng)的值;同樣當(dāng)Ai

圖2 字符型數(shù)據(jù)加密查詢流程

1.2 分析改進(jìn)算法

1.2.1 分析正確性

改進(jìn)算法進(jìn)行的兩個階段的查詢,在模糊查詢也即第一次查詢時,選定的記錄中必然包含所有符合條件的記錄;在精確查詢也即第二次查詢的過程中,首次查詢漏掉的不符合條件的查詢記錄一定會被過濾掉。因此通過兩階段查詢,能夠獲得目標(biāo)需求的所有準(zhǔn)確集合。

1.2.2 分析查詢效率

與等深或等寬劃分相比,以最佳桶劃分為基礎(chǔ)的查詢方式具有最低的查詢成本以及更高的查詢效率[7]。理論上,對桶劃分策略衡量的參數(shù)依據(jù),應(yīng)當(dāng)是錯檢元組的總數(shù)。當(dāng)劃分桶區(qū)間當(dāng)中包含的屬性值為X時,錯檢元組的總數(shù)為

(5)

也就是說,當(dāng)限定了桶劃分的區(qū)間數(shù)目時,要保證查詢獲得最高的命中率,就要使用最小的錯檢元組的總數(shù)XF。

以等深劃分或最佳桶劃分為依據(jù)的過濾效率的對比,可以通過對各劃分當(dāng)中錯檢元組的總數(shù)進(jìn)行計算來實現(xiàn)。如

(6)

其中:(a,4)表示在輸入當(dāng)中,共有4個字符串是以a開頭的,其他組同理。如果設(shè)在劃分子區(qū)當(dāng)中,上限數(shù)目X=4,那么劃分方式為等深劃分時,劃分區(qū)間的分布為{a,b,c},syggg00,{e,f},{g,h,i,j},錯檢元組的總數(shù)求得為130;當(dāng)劃分方式采用最佳桶劃分時,劃分所得的劃分區(qū)間的分布為{a,b,c},{d,e},{f,g},{h,i,j},錯檢元組的總數(shù)求得為120。其錯檢元組分組示意圖如圖3所示。

圖3 錯檢元組分組示意

也就是說,通過最佳桶劃分的方式,能夠保證在加密數(shù)據(jù)庫當(dāng)中得到的錯誤元更少,查詢效率更高。等深劃分和最佳桶劃分通過在500條的隨機(jī)字符串當(dāng)中的查詢代價的對比如圖4所示。

圖4 等深劃分與最佳桶劃分的查詢代價對比

1.2.3 選取劃分桶的數(shù)量

選取劃分桶的數(shù)量,首先應(yīng)當(dāng)設(shè)定相應(yīng)待加密字段的閾值。提高劃分桶的數(shù)量在一定程度上來說是為了能夠得到更好的查詢效率,但是并不是越高的劃分桶數(shù)量就能獲得越高的查詢效率。一是因為劃分桶數(shù)量的刻意提高容易降低對應(yīng)的索引字段的安全性,當(dāng)過濾效率不是100%時,設(shè)置劃分值不僅是無意義的,而且會對原方案的安全性造成破壞;二是因為劃分桶的數(shù)量提升到一定的閾值時,過濾效率將不再提升,只停留在當(dāng)前階段,這就使得攻擊者能夠通過劃分值對原字符串進(jìn)行推測。在改進(jìn)算法當(dāng)中,主要考慮兩個因素對劃分桶數(shù)量的選定的影響:一是設(shè)定相應(yīng)的加密字段的閾值;二是在設(shè)定閾值條件下,選擇劃分桶的最大可行數(shù)量[8]。

2 實驗設(shè)計與結(jié)果分析

仿真實驗采用的操作系統(tǒng)為Windows 7,服務(wù)器數(shù)據(jù)庫為SQL Server 2008,數(shù)據(jù)表選用AdventrueWorks中的Person.asses。實驗的數(shù)據(jù)源選擇數(shù)據(jù)表記錄中的前1 000條,加密處理的敏感字段為AddressLine1字段。采用高級加密標(biāo)準(zhǔn)(Advanced Encryption Standard, AES)加密算法進(jìn)行敏感字段的加密,密鑰長度選取128 bit。

2.1 測試查詢時間效率

對以最佳桶劃分為依據(jù)的方式以及解密之后再進(jìn)行查詢的方式進(jìn)行對比試驗時,需將對應(yīng)的查詢條件設(shè)定為Ai=b,試驗結(jié)果如圖5所示。

圖5 不同劃分方法查詢時間比較

從圖5可以看出,在劃分桶數(shù)量不斷增加的過程當(dāng)中,最佳桶劃分以及等深劃分的方式查詢需要的時間不斷縮短,也就是說其查詢效率不斷提升。其中,通過最佳桶劃分方式面對不同劃分個數(shù)需要的時間均值為53.07 ms,通過等深劃分的時間均值為57.89 ms,相較而言,最佳桶劃分所需查詢時間更短。

2.2 測試過濾效率

圖6 不同劃分方法過濾效率比較

從圖6可以看出:解密后查詢的方式不涉及過濾效率,過濾效率曲線為0。最佳桶劃分以及等深劃分兩種方式對于加密數(shù)據(jù)都具有一定的過濾能力。在劃分桶不斷增加的過程中,兩種方式的過濾能力也不斷提高。相比之下,最佳桶劃分的過濾效率更高,消耗資源更少,任務(wù)執(zhí)行更加穩(wěn)定。

2.3 隱私數(shù)據(jù)分類誤差對比

SQL Server 2008數(shù)據(jù)庫中,在選定的數(shù)據(jù)表Person.asses中隨機(jī)選取1 000條數(shù)據(jù),對選取的數(shù)據(jù)進(jìn)行加密并進(jìn)行隱私數(shù)據(jù)分類,并計算其誤差概率,實驗結(jié)果如圖7所示。

圖7 不同劃分方法誤差概率比較

從圖7可以看出,通過解密后查詢的方式對隱私數(shù)據(jù)的劃分誤差約為0.8%,等深劃分對隱私數(shù)據(jù)的劃分誤差約為0.4%,基于最佳桶劃分的方式在0.2%之內(nèi)。在對隱私數(shù)據(jù)的劃分誤差上,最佳桶劃分相比其他方式更為精確。

2.4 測試可靠性

在數(shù)據(jù)庫中隨機(jī)選取不同數(shù)量數(shù)據(jù)進(jìn)行數(shù)據(jù)加密,選取的數(shù)據(jù)數(shù)量分別為500,1 000,1 500,2 000,2 500,3 000條,通過虛擬非授權(quán)用戶對加密數(shù)據(jù)進(jìn)行非法解密,依靠解密率比較數(shù)據(jù)加密技術(shù)的可靠性,實驗結(jié)果如圖8所示。

圖8 不同劃分方式可靠性比較

從圖8可以看出,解密后查詢以及等深劃分的方式數(shù)據(jù)加密技術(shù)的可靠性均超過0.7%,基于最佳桶劃分的方式數(shù)據(jù)庫加密的可靠性約為0.5%。故最佳桶劃分的方式相比其他方式可靠性更高。

3 結(jié) 語

通過以最佳桶劃分為依據(jù)的方式對劃分值進(jìn)行提取,來實現(xiàn)嵌入式數(shù)據(jù)庫加密當(dāng)中的快速查詢。同時,通過與等深劃分以及解密之后再進(jìn)行查詢的方式進(jìn)行實驗對比,進(jìn)一步驗證了最佳桶劃分的方式具有更高的過濾效率、更短的查詢時間,證明最佳桶劃分的查詢方式針對字符段數(shù)據(jù)以及動態(tài)數(shù)據(jù)具有更好的查詢效果。