云計算加密數據關鍵詞代數簽名索引匹配搜索

蒲 在 毅

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

0 引 言

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

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

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

1 問題描述

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

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

(1)

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

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

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

定義3對于l≥n-1，令l上R的n-gram代數簽名是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代數簽名、P代數簽名和N代數簽名記錄的各個部分。以下代數簽名的簡單性質，表示為坐標i,1≤i≤m。注意到在l的C代數簽名的第i個符號作為CASm(l)i，且類似地進行N代數簽名和P代數簽名。

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

(3)

(4)

(5)

(6)

圖1 代數簽名記錄示意

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

表1 符號定義

2 加密數據關鍵詞代數簽名索引

2.1 代數簽名索引

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

圖2 基于代數簽名的匹配嘗試

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

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

通過利用第一個和最后一個n-grams可對磁盤進行限制訪問，此時代數簽名索引搜索過程獨立于P的大小。上面概述的搜索過程的成本可降低到讀取兩個緩存的成本。哈希目錄本身通常可以緩存在RAM中，或者最多需要兩個額外的磁盤訪問。通過適當的動態哈希機制，可以均勻地分布結構中的條目并優雅地進行縮放，緩存的大小可以保持足夠均勻，以使代數簽名索引獨立于數據庫大小在恒定時間內運行。

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

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

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

圖3 代數簽名索引指標結構

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

2.2 代數簽名索引搜索過程

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

預處理階段根據模式P計算三個簽名：1)P中的第一個n-gram的m符號代數簽名，稱為S1；2) 計算在第一個n-gram之后P的后綴1-符號P代數簽名，Sp=PAS1(P,n,K-1)；3)P中的最后一個n-gram的m符號代數簽名，稱為S2。對n-gram使用m符號代數簽名來獲得適合目錄長度的大范圍散列值，同時計算1-符號P代數簽名，為降低存儲成本，在條目中僅存儲1-符號C代數簽名值。圖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)。

這些信息可用于查找數據庫中出現的模式。

圖4 搜索算法

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

圖5 搜索過程的代數簽名索引

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

c2=c1+αl1+1×Sp

(7)

算法1基于代數簽名索引搜索過程

輸入：模式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。因此，云計算加密數據模式的長度必須至少為n+1。作為一般散列，所提方法存在沖突傳遞的假陽性。為消除任何沖突，有必要對代數簽名搜索過程進行后處理，試圖在識別為匹配的每個R中實際找到P。這需要在P和它假定匹配位置之間進行符號與符號的比較。

3 實驗分析

3.1 實驗設置

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

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

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

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

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

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

3.2 簽名長度參數影響實驗

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

圖6 影響實驗

根據圖6所示實驗曲線，對于具有較小尺寸的數據傳輸文件，例如10 GB以內的數據文件，因為計算硬件具有相對較高的配置，且帶寬傳輸容量尚未達到，此時代數簽名長度變化不會對數據傳輸成本產生明顯的影響，但是當數據文件增加到10 GB以上時，數據文件大小的變化會對數據傳輸成本產生相對明顯的影響，會導致數據傳輸成本大幅度的上升。

3.3 計算時間對比實驗

對于搜索實驗，從文件中提取模式，以確保找到至少一個結果。模式尺寸范圍從25個符號到200個符號。為避免初始化成本和來自其他OS進程的諸如CPU或內存爭用之類的副作用，重復執行每次搜索直到搜索時間穩定為止。報告運行500個搜索操作的平均搜索時間。對比算法選取關鍵詞B-Tree算法(BT)和標準代數簽名索引算法(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個用于加載葉節點的磁盤訪問。此外，節點中的每個查找都需要對數據庫進行附加的隨機磁盤訪問，以便獲取完整的關鍵詞。表2-表5中給出的搜索時間比，分別給出本文算法相對于代數簽名索引算法和關鍵詞B-Tree算法的加速比，可見本文算法可在相對恒定的時間內實現對數據庫中任意長度模式關鍵詞的查找，驗證了所提算法在計算效率上的優勢。

3.4 數據完整性對比實驗

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

表6 數據完整性對比數據

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

4 結 語

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