蒲 在 毅

(西華師范大學網(wǎng)絡與信息化管理中心 四川 南充 637009)

0 引 言

隨著現(xiàn)代信息技術的發(fā)展，云端存儲呈現(xiàn)出數(shù)據(jù)量的爆炸式增長，特別是電子郵件數(shù)據(jù)量、隱私視頻數(shù)據(jù)量等。如果采取云存儲方式進行數(shù)據(jù)存儲，則可大幅度降低數(shù)據(jù)處理開銷，實現(xiàn)處理效率提升。但由于云服務商和用戶之間存在信息的不對稱，導致其處于不同可信域內(nèi)，對于數(shù)據(jù)進行外包處理存在較大安全性問題，因此云服務過程中的可信度是人們比較關心的重點。應該嚴格避免信息意外泄漏給未授權客戶。但是在云計算過程中，存在短時間內(nèi)大量用戶數(shù)據(jù)檢索和數(shù)據(jù)外包可能性。明文環(huán)境下常用的搜索策略是利用關鍵詞檢索方式進行加密文件的檢索和提取，但是在加密環(huán)境下對關鍵詞進行直接搜索不現(xiàn)實，因為加密過程限制這種搜索行為。

為實現(xiàn)對云計算過程中加密數(shù)據(jù)有效檢索，學者們提出采用關鍵詞索引的方式對文件檢索。創(chuàng)建磁盤工作版本是近年來研究的熱點，但由于參考位置的不良性、尋呼方案的復雜性以及插入結構導致的結構劣化，導致技術實現(xiàn)上存在較大的困難。后綴數(shù)組將指針存儲在按字典順序排序的后綴列表中，并使用二進制搜索進行模式匹配。然而，標準數(shù)據(jù)庫體系結構以塊形式存儲記錄，且支持動態(tài)插入和刪除，這使得順序存儲維護變得困難。目前解決完全模式匹配搜索的磁盤索引方法主要有兩種：關鍵詞B-Tree算法和n-gram反向索引算法。前者的全局結構是B+樹的結構，其中鍵是指向數(shù)據(jù)庫中后綴的指針。每個節(jié)點被組織成一個Patricia單詞查找樹，這有助于指導搜索和插入操作。文本搜索需求的另一個方向是索引n-gram(n個連續(xù)符號)而不是整個單詞的索引。它們是“磁盤友好”的，因為其依賴于快速的順序掃描，提供良好的引用位置，且易于適應分頁和分區(qū)。然而，在數(shù)據(jù)庫的大小和模式大小上，搜索成本都是線性的。本文提出一種新的基于索引的全文檢索數(shù)據(jù)結構，稱為代數(shù)簽名索引。它遵循基于n-gram的倒排文件路徑，將標準數(shù)據(jù)庫大規(guī)模索引(即散列)與基于代數(shù)簽名的新散列演算相結合。

本文方法創(chuàng)新點是利用在數(shù)學結構中的字符作為符號的解釋。這種結構(Galois字段)中的操作有助于開發(fā)新的計算技術，用于在恒定時間內(nèi)識別搜索的結果項。因此，所提云計算加密數(shù)據(jù)索引結構具有吸引人的特性，目前就我們所知，這種特性是獨特的，即獨立于數(shù)據(jù)庫的大小和模式的長度，使用恒定數(shù)量的磁盤訪問來執(zhí)行記錄查找。

1 問題描述

使用大小為2f的伽羅瓦域(GF)GF(2f)，伽羅瓦域的元素是長度為f的位串。選擇利用代數(shù)簽名CII碼對云計算加密數(shù)據(jù)8位串處理，并使用Unicode碼對16位串處理，該運算相互結合，具有中性元素0和1，且存在加性和乘性逆。在伽羅瓦域GF(2f)中，加法和減法被實現(xiàn)為按位異或。云計算加密數(shù)據(jù)日志/反日志表通常提供最實用乘法方法。采用通常的數(shù)學符號來表示以下操作。使用GF(2f)的基礎元素α，意味著α的冪枚舉伽羅瓦域的所有非零元素。令R=r0,r1,…,rM-1是具有M個符號的記錄，可將R解釋為GF元素的序列。

定義1記錄R的m符號代數(shù)簽名(代數(shù)簽名)是具有m坐標(s1,s2,…,sm)向量ASm(R)，可定義為：

(1)

將R的m符號代數(shù)簽名表示為十六進制符號中sm,…,s1的級聯(lián)。例如，如果s1=#34和s2=#12，則可將2符號代數(shù)簽名表示為s2s1=#1234。

定義2令l∈[0,M-1]為R中任意偏移位置。在CASm(R,l)上的累積代數(shù)簽名(C代數(shù)簽名)是rl結尾的前綴代數(shù)簽名，即CASm(R,l)=ASm(r0,r1,…,rl)。

從l′到l的部分代數(shù)簽名(P代數(shù)簽名)的值PASm(R,l′,l)=ASm(rl′,rl′+1,…,rl)，具有0≤l′≤1。最后，使用長度為n的子串P代數(shù)簽名，即，n-gram。

定義3對于l≥n-1，令l上R的n-gram代數(shù)簽名是NASm(R,l)=PASm(R,l-n+1,l)，進而可得：

NASm(R,l)=(rl-n+1+…+rl×αn-1,

rl-n+1+…+rl×α2(n-1),

?

rl-n+1+…+rl×αm(n-1))

(2)

圖1給出在偏移l上定義的C代數(shù)簽名、P代數(shù)簽名和N代數(shù)簽名記錄的各個部分。以下代數(shù)簽名的簡單性質(zhì)，表示為坐標i,1≤i≤m。注意到在l的C代數(shù)簽名的第i個符號作為CASm(l)i，且類似地進行N代數(shù)簽名和P代數(shù)簽名。

CASm(l)i=CASm(l-1)i+rl×αil

(3)

(4)

(5)

(6)

圖1 代數(shù)簽名記錄示意

式(3)-式(5)可在掃描云計算加密數(shù)據(jù)輸入記錄或模式時增量地計算下一個C代數(shù)簽名和N代數(shù)簽名，而不是完全重新計算簽名，這大大提升了計算速度。表1總結了本文中使用的符號及其定義。

表1 符號定義

2 加密數(shù)據(jù)關鍵詞代數(shù)簽名索引

2.1 代數(shù)簽名索引

代數(shù)簽名是加密數(shù)據(jù)處理過程中具有代數(shù)性質(zhì)的數(shù)字簽名，它主要應用在大規(guī)模存儲系統(tǒng)中的數(shù)據(jù)審計、奇偶校驗和計算委托等任務中，具有可變長度磁盤駐留緩存的經(jīng)典哈希文件(見圖2)，系統(tǒng)散列目錄指向該緩存。這樣的文件具有簡單性和優(yōu)異性，得到廣泛關注，主要優(yōu)點是磁盤訪問次數(shù)不變，與文件和模式大小無關，對于降低數(shù)據(jù)訪問復雜度具有顯著作用。對于tree/trie訪問方法，不可能有一定數(shù)量磁盤訪問。每個緩存存儲條目列表，每個條目在數(shù)據(jù)庫中索引一些n-gram。代數(shù)簽名索引基本變體是密集的，索引為每個n-gram。為條目提供緩存的哈希函數(shù)使用n-gram值作為哈希鍵值。哈希函數(shù)是特殊的：它依賴于n-gram的代數(shù)簽名。在下文中，只處理靜態(tài)代數(shù)簽名索引，但是哈希結構可使用標準機制來實現(xiàn)動態(tài)性、可伸縮性和分布。

圖2 基于代數(shù)簽名的匹配嘗試

根據(jù)圖2所示，對云計算加密數(shù)據(jù)模式P的搜索過程如下：首先，針對三個簽名對P進行預處理：1) 初始n-gramS1；2) 最終n-gramS2；3) 在S1(包括S2)之后的P后綴Sp。在與S1簽名相同的數(shù)據(jù)庫中，定位緩存上S1的散列的每個條目e1可對n-gram進行索引。同樣地，在S2上散列定位緩存，每個條目e2用S2簽名索引n-gram。只考慮對在同一記錄和正確距離之間的條目。因此，至少在簽名的初始和終端n-gram上找到任何關鍵詞S的匹配模式P。

最后，進行AS(e1,e2,Sp)代數(shù)計算，決定Sp是否匹配S的后綴。這種計算是通過簽名的特定屬性實現(xiàn)的，這些屬性允許檢查一些語義屬性(例如，關鍵詞匹配)，盡管它們的表示非常緊湊，但是標準散列函數(shù)無法實現(xiàn)這一點。該方法本質(zhì)上是概率性的，假陽性的可能性很低?？梢酝ㄟ^模式與記錄的相關部分之間的符號比較來避免甚至極小的錯誤匹配的可能性。

通過利用第一個和最后一個n-grams可對磁盤進行限制訪問，此時代數(shù)簽名索引搜索過程獨立于P的大小。上面概述的搜索過程的成本可降低到讀取兩個緩存的成本。哈希目錄本身通?？梢跃彺嬖赗AM中，或者最多需要兩個額外的磁盤訪問。通過適當?shù)膭討B(tài)哈希機制，可以均勻地分布結構中的條目并優(yōu)雅地進行縮放，緩存的大小可以保持足夠均勻，以使代數(shù)簽名索引獨立于數(shù)據(jù)庫大小在恒定時間內(nèi)運行。

云計算加密數(shù)據(jù)庫由記錄標識符(RID)和一些非關鍵字段記錄組成。假設非關鍵字段可由從伽羅瓦域解釋為符號的關鍵詞組成。當討論偏移和代數(shù)簽名時，僅指非鍵字段。對于字段R中的字符ri，其偏移可表示為i。n-gram序列G=rl-n+1,…,rl是R中n個連續(xù)符號的任意序列。通過擴展，將l稱為n-gram序列的偏移量。

定義4令G是在R中偏移o的n-gram，條目索引G，表示為E(G)，是一個三元組(rid,o′,c)，其中rid是R的記錄標識符(RID)，c是累積代數(shù)簽名CAS1(R,o)，o′是偏移o的模2f-1。

通過取余數(shù)來保證條目具有恒定大小。對于所有伽羅瓦場元素χ，利用同一性度量χ2f-1=χ，可證明模的選擇。假設索引是“密集”的，即數(shù)據(jù)庫中的每一個n-gram都由一個不同的條目索引。為了構造索引，在數(shù)據(jù)庫中處理所有的n-gram。索引是一個哈希文件，表示為D[0,1,…,L-1]，目錄長度L=2v為2的冪(見圖3)。

圖3 代數(shù)簽名索引指標結構

總之，代數(shù)簽名索引行結構類似于反轉(zhuǎn)文件中的發(fā)布列表，除在每個條目中存在代數(shù)簽名c和偏移量l的特定表示之外。由于使用散列文件，所以行應該具有沖突解決方法，例如使用指向溢出空間的指針的經(jīng)典單獨鏈接。這種技術適應適度增長，但如果需要適應大的增長，那么需要動態(tài)散列方法，比如線性散列。

2.2 代數(shù)簽名索引搜索過程

本節(jié)設計了基于代數(shù)簽名索引的云計算加密數(shù)據(jù)模式搜索，利用三個簽名對模式進行預處理，并檢索(可能)匹配的代數(shù)簽名索引，有利于提高算法的執(zhí)行效率。首先，令P=p0,p1,…,pK-1是匹配模式。代數(shù)簽名索引搜索提供了包含P的數(shù)據(jù)庫中的每個記錄的RID。搜索算法先預處理P，然后檢索(可能)匹配的代數(shù)簽名索引。

預處理階段根據(jù)模式P計算三個簽名：1)P中的第一個n-gram的m符號代數(shù)簽名，稱為S1；2) 計算在第一個n-gram之后P的后綴1-符號P代數(shù)簽名，Sp=PAS1(P,n,K-1)；3)P中的最后一個n-gram的m符號代數(shù)簽名，稱為S2。對n-gram使用m符號代數(shù)簽名來獲得適合目錄長度的大范圍散列值，同時計算1-符號P代數(shù)簽名，為降低存儲成本，在條目中僅存儲1-符號C代數(shù)簽名值。圖4給出在運行示例中確定簽名S1、S2和Sp的部分模式。設置n=5和m=4。預處理模式P=“University Paris Dauphine”，并得到：

1)S1=NAS4(P,4)(for 5-gram "Unive")；

2)S2=NAS4(P,24)(for 5-gram "phine")；

3)Sp=PAS1(P,5,24)。

這些信息可用于查找數(shù)據(jù)庫中出現(xiàn)的模式。

圖4 搜索算法

該代數(shù)簽名搜索過程見圖5所示。令i=hL(S1)，i′=hL(S2)。緩存D[i]中的每個條目(R,l1,c1)在記錄R中的n-gram索引G，其N代數(shù)簽名SG是hL(SG)=hL(S1)。同樣地，緩存D[i]中的每個條目(R,l2,c2)的n-gram索引G′，使得hL(G′)=hL(S2)。在可能的碰撞中，G和G′分別對應于P中的第一個和最后一個n-gram。

圖5 搜索過程的代數(shù)簽名索引

只考慮配對(G,G′)可能的特征匹配關鍵詞S=P。這涉及到附加約束R′=R和l2=(l1+K-n)。G′中的最后分量c2必須與c1和Sp計算值相匹配：

c2=c1+αl1+1×Sp

(7)

算法1基于代數(shù)簽名索引搜索過程

輸入：模式P=p0,p1,…,pK-1，n-gram大小n

輸出：包含P的記錄列表

Begin

//預處理階段

//i是第一行索引

//i′是第二行索引

//搜索過程

For eachE(R,l1,c1)∈D[i] do

c2=c1+αl1+1×Sp;

l2=(l1+K-n) mod (2f-1);

If ?E′(R,l2,c2)∈D[i′] then

報告R搜索成功；

Endif

Endfor

End

該過程選擇性依賴于其操縱三個不同簽名的能力，S1、S2和Sp。因此，云計算加密數(shù)據(jù)模式的長度必須至少為n+1。作為一般散列，所提方法存在沖突傳遞的假陽性。為消除任何沖突，有必要對代數(shù)簽名搜索過程進行后處理，試圖在識別為匹配的每個R中實際找到P。這需要在P和它假定匹配位置之間進行符號與符號的比較。

3 實驗分析

3.1 實驗設置

使用四種類型具有非常明顯特征的數(shù)據(jù)集來模擬云計算加密數(shù)據(jù)集關鍵詞的檢索過程，分別是：alpha，DNA，text和wikipedia。具體情況描述如下：

(1) alpha(Σ)類型數(shù)據(jù)集由合成代數(shù)簽名CII記錄組成，具有均勻的分布，遍歷字母表Σ作為擴展代數(shù)簽名CII字符的子集。對于這些類型，組成的數(shù)據(jù)集范圍從20 MB到20 GB，每個復合了20個文件。

(2) dna包括從UCSC數(shù)據(jù)庫中提取的真實DNA記錄。這個數(shù)據(jù)集由97個文件組成，這些文件的大小范圍很大，從幾十KB到數(shù)百MB，甚至幾個GB(對于兩個文件)，其總尺寸為9.9 GB。

(3) text類型文本由從加密數(shù)據(jù)庫中提取的大型英文圖書的代數(shù)簽名CII文件創(chuàng)建的真實文本記錄組成。文本記錄典型大小為0.5×2 MB，大小分布幾乎一致且在該范圍內(nèi)。創(chuàng)建大小為16.6 GB包含29個文件539文本的數(shù)據(jù)庫。

(4) wikipedia將免費的維基百科百科全書進行加密，并轉(zhuǎn)儲將維基百科的所有XML記錄附加到一個大小為24 GB的單個XML記錄中。

為限制由于字母表大小導致的n-gram格簽名的沖突，將DNA文件的n-gram格大小設置為8，維基百科為6，其他數(shù)據(jù)集為4。

3.2 簽名長度參數(shù)影響實驗

在該實驗中，對代數(shù)簽名的概率因子的影響問題進行實驗驗證，假定實驗過程中所要驗證對象的大小所屬區(qū)間是1～1 000 GB，簽名長度參數(shù)設定的變化區(qū)間16 b～256 b。則隨著驗證文件對象的大小變化，對數(shù)據(jù)驗證過程中的計算成本進行實驗對比，結果見圖6。

圖6 影響實驗

根據(jù)圖6所示實驗曲線，對于具有較小尺寸的數(shù)據(jù)傳輸文件，例如10 GB以內(nèi)的數(shù)據(jù)文件，因為計算硬件具有相對較高的配置，且?guī)拏鬏斎萘可形催_到，此時代數(shù)簽名長度變化不會對數(shù)據(jù)傳輸成本產(chǎn)生明顯的影響，但是當數(shù)據(jù)文件增加到10 GB以上時，數(shù)據(jù)文件大小的變化會對數(shù)據(jù)傳輸成本產(chǎn)生相對明顯的影響，會導致數(shù)據(jù)傳輸成本大幅度的上升。

3.3 計算時間對比實驗

對于搜索實驗，從文件中提取模式，以確保找到至少一個結果。模式尺寸范圍從25個符號到200個符號。為避免初始化成本和來自其他OS進程的諸如CPU或內(nèi)存爭用之類的副作用，重復執(zhí)行每次搜索直到搜索時間穩(wěn)定為止。報告運行500個搜索操作的平均搜索時間。對比算法選取關鍵詞B-Tree算法(BT)和標準代數(shù)簽名索引算法(ASI)，其中選取ASI算法實驗結果作為標準結果。實驗結果如表2-表5所示。

表2 文件dna搜索時間 ms

表3 文件text搜索時間 ms

表4 文件wikipedia搜索時間 ms

表5 文件alpha(26)搜索時間 ms

對于選取的20 GB文件，關鍵詞B-Tree算法的高度是5，與字母表大小無關。根始終在緩存中，根以下級別的重要部分，取決于索引文件大小。關鍵詞B樹遍歷一般被減少到(5-2)=3個用于加載葉節(jié)點的磁盤訪問。此外，節(jié)點中的每個查找都需要對數(shù)據(jù)庫進行附加的隨機磁盤訪問，以便獲取完整的關鍵詞。表2-表5中給出的搜索時間比，分別給出本文算法相對于代數(shù)簽名索引算法和關鍵詞B-Tree算法的加速比，可見本文算法可在相對恒定的時間內(nèi)實現(xiàn)對數(shù)據(jù)庫中任意長度模式關鍵詞的查找，驗證了所提算法在計算效率上的優(yōu)勢。

3.4 數(shù)據(jù)完整性對比實驗

為驗證所提算法對于數(shù)據(jù)搜索過程完整性的影響，選取數(shù)據(jù)完整性驗證指標作為實驗指標，對比算法仍然選取ASI(加速比)和BT(加速比)兩種算法作為對比，實驗文件的大小設定區(qū)間是2～10 GB，結果如表6所示。

表6 數(shù)據(jù)完整性對比數(shù)據(jù)

根據(jù)表6數(shù)據(jù)，本文算法在數(shù)據(jù)搜索完整性上相對于選取的兩種算法具有更好的性能表現(xiàn)。隨著實驗數(shù)據(jù)文件變化，數(shù)據(jù)搜索的完整性出現(xiàn)下降，但是相對而言，變化的幅度并不大，這說明算法具有相對較好的魯棒性，而對比算法ASI(加速比)和BT(加速比)，本文算法具有相對較低的數(shù)據(jù)搜索完整性，算法的穩(wěn)定性能不佳。

4 結 語

本文提出一種基于代數(shù)簽名和代數(shù)計算的云計算加密數(shù)據(jù)庫中關鍵詞搜索的新方法。本文的貢獻在于提出了一種簡單、快速的搜索算法，該算法可以在任意大小的數(shù)據(jù)庫中，在相對恒定的時間內(nèi)找到任意長度的模式。這項工作從基礎理論角度，利用數(shù)學結構中字符作為符號解釋來開發(fā)新的計算技術。索引的可擴展和分布式是今后的一個有前途的研究方向。