王 偉，楊 庚，張成果

(南京郵電大學(xué) 計算機學(xué)院，江蘇 南京 210003)

CryptDB密文數(shù)據(jù)庫系統(tǒng)并行方案研究

王 偉，楊 庚，張成果

(南京郵電大學(xué) 計算機學(xué)院，江蘇 南京 210003)

加密數(shù)據(jù)庫對隱私數(shù)據(jù)的加密存儲保護是解決當(dāng)前互聯(lián)網(wǎng)中用戶隱私數(shù)據(jù)泄露的一種可行方案。鑒于互聯(lián)網(wǎng)中每日產(chǎn)生的用戶隱私數(shù)據(jù)規(guī)模巨大，傳統(tǒng)的串行計算會導(dǎo)致隱私數(shù)據(jù)的加密存儲時間消耗較長。為提高加密存儲等數(shù)據(jù)處理的速度，將MapReduce并行框架與CryptDB密文數(shù)據(jù)庫系統(tǒng)進行有機結(jié)合，設(shè)計并實現(xiàn)了CryptDB密文數(shù)據(jù)庫系統(tǒng)并行加密和分布式存儲的方案。并行方案采用任務(wù)調(diào)度算法、文件分割算法來提高其并行性和可控性，通過重寫MapReduce框架中的Map方法來實現(xiàn)CryptDB密文數(shù)據(jù)庫系統(tǒng)的并行加密和分布式存儲?；谟?個Master節(jié)點、3個CryptDB節(jié)點和3個MySQL服務(wù)器構(gòu)成的實驗平臺，進行了并行方案的實驗驗證及其性能分析。實驗結(jié)果表明，所構(gòu)建的并行方案在3個CryptDB節(jié)點集群中的加速比可達(dá)到2.51，加密和存儲時間節(jié)省了60.2%，可用于大規(guī)模關(guān)系數(shù)據(jù)的加密存儲。

加密數(shù)據(jù)庫；MapReduce；CryptDB系統(tǒng)；并行加密；分布式存儲

0 引 言

隨著互聯(lián)網(wǎng)的普及和互聯(lián)網(wǎng)技術(shù)的高速發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)庫安全成為了新興的研究領(lǐng)域。計算機安全研究所(CSI)和FBI統(tǒng)計發(fā)現(xiàn)，平均每年有超過70%的用戶曾遭受過網(wǎng)絡(luò)攻擊。這表明，傳統(tǒng)的防火墻技術(shù)已經(jīng)無法保證網(wǎng)絡(luò)數(shù)據(jù)庫的絕對安全。攻擊者可以利用網(wǎng)絡(luò)應(yīng)用的安全漏洞竊取用戶的隱私數(shù)據(jù)，對數(shù)據(jù)好奇的數(shù)據(jù)庫管理員也會對用戶隱私數(shù)據(jù)造成泄漏的風(fēng)險。因此，如何設(shè)計并實現(xiàn)可檢索的加密方案并運用到傳統(tǒng)的數(shù)據(jù)庫中，以加密用戶隱私數(shù)據(jù)并支持在密文上進行SQL操作，成為了目前亟需解決的問題。

1995年，Benny Chor等提出了私有信息檢索的概念,并在不泄露檢索信息的前提下,實現(xiàn)從數(shù)據(jù)庫中檢索到用戶所需的信息[1]。2000年，D.Song等提出一種可檢索的對稱加密方案(SSE)[2],開創(chuàng)了在不解密的情況下查詢密文的先例，具有很高的實用性。在此之后，可檢索加密機制進展迅速，并且支持對密文數(shù)據(jù)進行多關(guān)鍵詞和模糊關(guān)鍵詞搜索[3-6]。2004年，D.Boneh等提出了真正意義上的可搜索公鑰加密方案(PEKS),為此業(yè)界把2004年定義為可搜索公鑰加密的元年[7]。另外，可檢索加密機制不但在理論上有了多樣化的發(fā)展，許多研究者也將它們應(yīng)用到了實際的場景之中。例如，MIT計算機科學(xué)和人工智能實驗室(CSAIL)研發(fā)了一個加密數(shù)據(jù)庫系統(tǒng)CryptDB[8]。該數(shù)據(jù)庫系統(tǒng)允許用戶查詢加密的SQL數(shù)據(jù)庫，而且能在無需解密儲存信息的情況下返回結(jié)果。由于CryptDB系統(tǒng)采用了多層加密的洋蔥加密方案來加密數(shù)據(jù)，并把數(shù)據(jù)加密成多份以適用于多種檢索場景，當(dāng)數(shù)據(jù)規(guī)模巨大時，其加密存儲對服務(wù)器的運算和存儲開銷是巨大的。為了解決大規(guī)模數(shù)據(jù)加密時間開銷巨大的問題，Kamara等在2013年提出了并行同態(tài)加密方案[9]。該方案支持通過評估算法對加密數(shù)據(jù)進行并行處理；并且研究了在MapReduce并行計算模型下的各種操作,包括關(guān)鍵詞檢索。2015年，F(xiàn) Wang 等提出了使用Hadoop集群對明文數(shù)據(jù)庫中已存在的數(shù)據(jù)進行并行加密并存儲的方案，適用于企業(yè)級大型數(shù)據(jù)庫中明文數(shù)據(jù)加密成密文存儲的場景，相比于單一服務(wù)器時間開銷更小[10]。

文中以CryptDB系統(tǒng)的加密存儲過程為出發(fā)點，利用云計算MapReduce框架對海量數(shù)據(jù)運算高效的特點，設(shè)計并實現(xiàn)了基于任務(wù)并行的CryptDB系統(tǒng)優(yōu)化方案，實現(xiàn)了對大規(guī)模隱私數(shù)據(jù)進行高效加密及存儲的處理。該方案對DML/DDL語句進行分組，然后把每組操作分發(fā)到部署有CryptDB系統(tǒng)的節(jié)點上，并對其進行加密計算并存儲，以達(dá)到縮短加密及存儲時間的目的。

1 并行方案設(shè)計

1.1 CryptDB密文數(shù)據(jù)庫系統(tǒng)

CryptDB[8]是一個密文數(shù)據(jù)庫系統(tǒng)，它在可信的MySQL-Prxoy代理服務(wù)器端對明文SQL語句進行攔截，之后對隱私字段進行加密，隨后將改寫后的SQL語句提交到不可信的MySQL服務(wù)器端執(zhí)行存儲以實現(xiàn)對隱私數(shù)據(jù)的保護。CryptDB系統(tǒng)可直接對密文數(shù)據(jù)進行SQL操作。實現(xiàn)該操作的核心是三個創(chuàng)新的方案[11]：

(1)利用支持SQL的加密策略將SQL操作映射到加密框架中；

(2)可調(diào)整的加密方案使得可以根據(jù)用戶的查詢語句來調(diào)整數(shù)據(jù)的加密等級；

(3)洋蔥加密方案可以高效地調(diào)整數(shù)據(jù)的加密等級。

1.2 并行方案模型

為了保證數(shù)據(jù)的安全性及密文的可檢索，CryptDB系統(tǒng)利用多個洋蔥模型對數(shù)據(jù)進行加密。因此利用CryptDB密文數(shù)據(jù)庫系統(tǒng)對隱私數(shù)據(jù)進行加密存儲的計算開銷是巨大的。文中提出基于MapReduce計算框架的CryptDB系統(tǒng)任務(wù)并行方案，結(jié)合云計算環(huán)境的特性與CryptDB密文數(shù)據(jù)庫系統(tǒng)的特點，將巨大的計算任務(wù)分發(fā)到各個部署有CryptDB系統(tǒng)的節(jié)點上進行計算并提交到對應(yīng)的MySQL服務(wù)器上存儲，方案中負(fù)責(zé)任務(wù)調(diào)度的主節(jié)點和負(fù)責(zé)加密的CryptDB節(jié)點都是可信服務(wù)器，因此不會造成明文的泄漏。并行方案如圖1所示。

圖1 任務(wù)并行方案

MapReduce的編程模型一般包含三個重要的組成部分：分片、map階段和reduce階段。首先，該方案根據(jù)負(fù)載均衡策略將大的SQL指令分割成多個分塊；ResourceManager根據(jù)MapReduce框架的調(diào)度機制將各個分塊分發(fā)到相應(yīng)的CryptDB節(jié)點上，并啟動mapper對分塊中的明文SQL進行字段提??；最后調(diào)用CryptDB系統(tǒng)對數(shù)據(jù)進行加密。加密后的密文SQL將提交到MySQL服務(wù)器端執(zhí)行。由于方案中每個CryptDB節(jié)點都對應(yīng)一臺MySQL服務(wù)器，并且加密后的SQL仍為標(biāo)準(zhǔn)的SQL語句，可直接被MySQL解析。提交到MySQL服務(wù)器執(zhí)行后，數(shù)據(jù)將直接以密文形式存儲在MySQL數(shù)據(jù)庫中。因此方案中不需對數(shù)據(jù)進行Reduce操作。

1.3 任務(wù)分配算法

該方案中的并行策略是基于任務(wù)的分割，考慮到每個節(jié)點的計算能力不同，若將任務(wù)平均分配，計算能力較弱的節(jié)點完成任務(wù)的時間會較長，得不到最優(yōu)解。方案中提出了任務(wù)分配算法，該算法致力于在任務(wù)并行階段提高并行度，得到較優(yōu)的map時間。

算法1：任務(wù)分配算法。

輸入：節(jié)點個數(shù)m，SQL語句的條數(shù)N；

輸出：每個節(jié)點的任務(wù)規(guī)模Xm。

(1)輸入?yún)?shù)為集群中CryptDB節(jié)點的個數(shù)m，以及待加密的任務(wù)規(guī)模即SQL語句的條數(shù)N。

(2)隨機生成n條與待加密SQL語句屬性個數(shù)及類型相同的測試SQL語句。

(3)將測試SQL語句通過JDBC分發(fā)到m個CryptDB節(jié)點上進行加密存儲，得到時間開銷tm。

(6)分別用最優(yōu)的map時間乘以各節(jié)點計算能力，得到每個節(jié)點應(yīng)分配到的任務(wù)規(guī)模Xm=tava·xm。

說明：

(1)該算法不會影響整個方案的效率。第2步中的參數(shù)n為預(yù)先設(shè)定的一個常量(n?N)。因此該算法時間開銷相對于之后的加密存儲操作而言，可以忽略不計。

(2)該算法應(yīng)用于JobControl階段，產(chǎn)生任務(wù)分配的策略，以提高方案的整體性能。

(3)該算法在每次執(zhí)行任務(wù)前都會被執(zhí)行，以根據(jù)實時計算能力產(chǎn)生分配策略。

1.4 文件分割算法

由于集群中有m個節(jié)點，所以文中方案加入文件分割算法，根據(jù)每個節(jié)點的計算能力，將大的SQL文件分割成相應(yīng)大小的SQL文件，并按相應(yīng)的編號命名文件塊。map階段，每個mapper會根據(jù)文件名處理對應(yīng)的文件。

算法2：文件分割算法。

輸入：大的SQL文件；

輸出：分割后小的SQL文件。

(1)將大的SQL文件讀到內(nèi)存中。

(2)從文件的起始位置開始，按行讀取SQL語句，保存到temp變量中。

(3)當(dāng)累加器的SQL語句達(dá)到當(dāng)前節(jié)點所需規(guī)模時，將temp中的內(nèi)容保存到HDFS文件系統(tǒng)中，并以節(jié)點編號命名。

MapReduce框架中的InputFormat算法是將大的文件分割成對應(yīng)的文件塊，分配給相應(yīng)的mapper處理。文中提出的文件分割算法有別于InputFormat算法，將大的文件以小的文件格式保存在HDFS文件系統(tǒng)中。該算法使得mapper根據(jù)文件名處理相對應(yīng)規(guī)模的小任務(wù)文件，而不是MapReduce框架中的隨機分配任務(wù)。提高了并行方案的可控性，有利于提高方案的并行度。

1.5 Map函數(shù)

算法3：Map。

輸入：文件路徑、容器大小、節(jié)點個數(shù)。

(1)從HDFS中獲取待處理文件的文件名，即節(jié)點的編號，該文件的文件名由算法2給出。

(2)根據(jù)編號從properties文件中讀取節(jié)點的地址等信息，將該文件分發(fā)到對應(yīng)的CryptDB節(jié)點進行解析處理。

(3)CryptDB節(jié)點接收到待處理的SQL文件后，首先讀取文件內(nèi)容，然后對SQL語句中的關(guān)鍵詞進行處理，提取出待加密的屬性值。

(4)將提取出的屬性值根據(jù)預(yù)先設(shè)定的容器大小進行拼接，構(gòu)建成新的標(biāo)準(zhǔn)SQL語句。

(5)通過JDBC調(diào)用CryptDB密文數(shù)據(jù)庫系統(tǒng)，執(zhí)行SQL語句，加密并存儲數(shù)據(jù)。

說明：

實踐教學(xué)是學(xué)生掌握知識的重要渠道，是學(xué)生把所學(xué)的理論知識轉(zhuǎn)化為實際技能的重要途徑，也是培養(yǎng)學(xué)生創(chuàng)新能力的源泉；也是拓展學(xué)生職業(yè)能力的根本途徑，同時還是展現(xiàn)學(xué)生個性化的舞臺。

(1)該算法第2步提到的properties文件為構(gòu)建CryptDB集群時所記錄的配置信息，所包含的內(nèi)容為節(jié)點編號及IP地址。

(2)該算法第4步中提到的容器大小為新建MapReduce任務(wù)時給出的值，該值應(yīng)小于CryptDB密文數(shù)據(jù)庫系統(tǒng)單次所能處理SQL的最大屬性值個數(shù)。

2 并行方案性能分析

2.1 串行性能分析

文中首先討論CryptDB系統(tǒng)INSERT操作的串行執(zhí)行時間。CryptDB系統(tǒng)INSERT操作可以看成三個部分：第一部分是查詢元數(shù)據(jù)表，第二部分是對數(shù)據(jù)進行加密，第三部分是將加密后的數(shù)據(jù)插入到MySQL數(shù)據(jù)庫。設(shè)這三個部分的時間分別為Tmeta、Tenc、Tinsert，如式(1)所示。

Ts=Tmeta+Tenc+Tinsert

(1)

CryptDB系統(tǒng)中任何類型的數(shù)據(jù)都利用“等值洋蔥”和“保序洋蔥”進行加密[12]，數(shù)值型數(shù)據(jù)還會利用“HOM洋蔥”加密，字符型數(shù)據(jù)會利用“SEARCH洋蔥”加密。其中，等值洋蔥中分別對數(shù)據(jù)使用了DETJOIN算法、DET算法和RND算法進行加密。保序洋蔥使用了OPE算法和RND算法對數(shù)據(jù)進行加密。HOM洋蔥使用同態(tài)算法加密。SEARCH洋蔥使用了SEARCH算法進行加密[13]。

對于數(shù)值型的數(shù)據(jù)，RND采用的是添加初始化向量IV的Blowfish算法，DET采用的是Blowfish加密算法，DETJOIN采用的是基于ECC(橢圓加密)的ECJoin算法。對于字符型數(shù)據(jù)，RND采用的是帶初始化向量IV(即salt值)的CBC模式的AES加密算法，它能保證密文加密的隨機性，即相同的明文加密后密文可能不相同；DET采用的是初始向量相同的CMC模式(即初始化向量都為“0”的CBC模式)AES加密算法，所以相同的明文加密后能得到相同的密文；OPE采用的是mOPE加密算法；HOM采用的Paillier加密算法；SEARCH采用的SWPSearch加密算法。設(shè)Blowfish加密算法Blowfish、AES、ECJoin、mOPE、HOM的復(fù)雜度分別為Rblowfish、Raes、Recjoin、Rmope、Rpaillier。由于CryptDB系統(tǒng)的代碼中沒有實現(xiàn)OPEJOIN算法和SEARCH洋蔥，所以不進行討論。并且由于CryptDB使用的加密算法明文在加密前都會進行填充操作，所以輸入和輸出的規(guī)模都是定長。對于數(shù)值型的數(shù)據(jù)，“等值洋蔥”的復(fù)雜度為：

UoEq_int=Recjoin+2·Rblowfish

(2)

“保序洋蔥”的復(fù)雜度為：

UoOrder_int=Rmope+Rblowfish

(3)

“HOM洋蔥”的復(fù)雜度為：

UoAdd=ReAdd

(4)

對于字符型數(shù)據(jù)，“等值洋蔥”的復(fù)雜度為：

UoEq_str=Recjoin+2·Raes

(5)

保序洋蔥的復(fù)雜度為：

UoOrder_str=Rmope+Raes

(6)

由式(2)～(4)可知，加密一個數(shù)值型的數(shù)據(jù)的復(fù)雜度為：

Uint=UoEq_int+UoOrder_int+UoAdd= Recjoin+3·Rblowfish+Rmope+Rpaillier

(7)

由式(5)、式(6)可知，加密一個字符型數(shù)據(jù)的復(fù)雜度為：

Ustr=UoEq_str+UoOrder_str= Recjoin+3·Raes+Rmope

(8)

設(shè)待加密字段有a個數(shù)值型數(shù)據(jù)和b個字符型數(shù)據(jù)，則:

Uenc=a·Uint+b·Ustr=(a+b)· (Recjoin+Rmope)+3a·Rblowfish+(a+4b)· Raes+a·Rpaillier

(9)

由文獻(xiàn)[14]可知，ECJoin的橢圓計算和mOPE編碼的復(fù)雜度都為O(logn)。由文獻(xiàn)[15-16]可知，AES、Blowfish、Paillier的復(fù)雜度為O(n)。ECJoin中除了橢圓計算外還會使用AES對明文進行編碼，因此ECJoin的復(fù)雜度為O(n+logn)。mOPE編碼后還會使用DET對B樹的葉子進行加密，所以mOPE的復(fù)雜度也為O(n+logn)。由于當(dāng)n>0時,n>logn,因此n+logn<2n。所以ECJoin、mOPE的復(fù)雜度都可表示為O(n)。因此可設(shè)Recjoin、Rblowfish、Rmope、Rpaillier分別為Raes的α1,α2,α3,α4倍，即:

Uenc=(a+b)·(α1+3α2+2α3+α4+3)Raes

(10)

設(shè)查詢元數(shù)據(jù)表的時間和插入MySQL數(shù)據(jù)庫的復(fù)雜度分別為δ次和ε次浮點計算，設(shè)浮點計算的時間為Tfc,則:

(11)

因此，由式(1)、式(9)、式(10)得：

Ts=(Uenc+δ+ε)·Tfc

(12)

2.2 并行性能分析

設(shè)共有p個CryptDB節(jié)點處理包含a個數(shù)值型數(shù)據(jù)和b個字符型數(shù)據(jù)的SQL文件。該SQL文件被分割成了p個數(shù)據(jù)塊，對應(yīng)p個mapper。則每個分塊中包含a/p個數(shù)值型數(shù)據(jù)和b/p個字符型數(shù)據(jù)。

因為CryptDB系統(tǒng)并行化方案沒有Reduce階段，所以只討論map部分。設(shè)Map算法的復(fù)雜度為M，則得到：

M=(Uenc+ε)/p+δ

(13)

在map階段，每個mapper開始前和結(jié)束后都會和ResourceManager進行通信。又因為數(shù)據(jù)被分割成了p塊，所以至少有2p次通信。設(shè)通信耗時為：

Ttr=ζ·p·Tfc

(14)

則并行時間為：

Tp=M·Tfc+Ttr

(15)

則加速比可表示為：

(16)

實際工程應(yīng)用中，CryptDB節(jié)點數(shù)遠(yuǎn)小于待加密的數(shù)據(jù)的規(guī)模,即p?a+b，此時通信時間可以忽略不計，即ζ→0。由于加密數(shù)據(jù)規(guī)模較大時，查詢元數(shù)據(jù)表的時間相對于加密時間可忽略不計，即δ→0。由式(16)可知，加速比理想值為p。

3 實 驗

3.1 實驗環(huán)境

實驗的硬件平臺包括1個Master節(jié)點和3個CryptDB節(jié)點及3個MySQL服務(wù)器。Master節(jié)點負(fù)責(zé)工作的監(jiān)控和調(diào)度，CryptDB節(jié)點負(fù)責(zé)密文計算，MySQL服務(wù)器負(fù)責(zé)執(zhí)行密文SQL并存儲的任務(wù),其配置均為：

CPU:Intel(R) Xeon E3-1225 v3, 3.2 GHz/8 M Cache；

Memory:16 GB (2x8 GB) 1 333 MHz Dual Ranked RDIM；

Disk:1 TB 3.5-inch 7.2 K RPM SATA II Hard Drive。

軟件平臺為:Ubuntu 12.04，Java 1.7.0，Hadoop版本為Hadoop-2.5.2，CryptDB為2015年3月下載版本。

3.2 CryptDB并行方案INSERT性能

實驗的數(shù)據(jù)集為隨機生成的SQL文件。測試文件所含的SQL語句條數(shù)為1 000～10 000，間隔為1 000，共十個文件。每條數(shù)據(jù)有五個數(shù)值型字段和五個字符型字段。實驗中，當(dāng)mapper的個數(shù)為1時，為串行時間。當(dāng)mapper的個數(shù)為n時，表示SQL文件被分割成了n個數(shù)據(jù)分塊，對應(yīng)n個CryptDB節(jié)點，即n個CryptDB節(jié)點計算并行時間。

文中用相同的測試數(shù)據(jù)在原生的CryptDB系統(tǒng)中進行實驗，并記錄了不同規(guī)模的測試數(shù)據(jù)插入操作的總時間、系統(tǒng)吞吐量、方案的加速比以及方案的效率(加速比/節(jié)點個數(shù))。結(jié)果如表1和圖2所示。

表1 部分實驗結(jié)果

從表1的數(shù)據(jù)和圖2中的曲線變化趨勢可以得出：

圖2 INSERT操作時間

(1)對于相同規(guī)模的SQL語句，CryptDB系統(tǒng)的執(zhí)行時間比CryptDB并行方案單節(jié)點執(zhí)行時間短。這是由于Hadoop并行框架中有任務(wù)調(diào)度和通信時間開銷。

(2)隨著CryptDB節(jié)點個數(shù)的增加，算法的總耗時呈下降趨勢。這是由于集群的計算能力會隨著節(jié)點個數(shù)的增加而增大。加速比和效率總體呈上升趨勢，這是由于當(dāng)數(shù)據(jù)規(guī)模足夠大時，算法中對數(shù)據(jù)的加密時間占主導(dǎo)地位。通信的耗時在整體時間中可以忽略不計，所以加速比和效率都會逼近理想值。算法的加速比在最好的情況下，接近于CryptDB節(jié)點個數(shù)p，與理論分析相符。并行方案的吞吐量隨著節(jié)點個數(shù)增加接近于比例上升。這是由于在任務(wù)的分配階段，使用了任務(wù)調(diào)度算法。該算法會根據(jù)集群中計算節(jié)點的計算能力動態(tài)分配任務(wù)，使得所有參與計算的節(jié)點不會存在閑置或等待的情況，表明了該方案有較高的并行度。

3.3 CryptDB并行方案空間性能

表2 數(shù)據(jù)庫大小

圖3 數(shù)據(jù)庫文件平均大小

圖3和表2反應(yīng)的是：集群中平均每個CryptDB節(jié)點上的加密數(shù)據(jù)庫文件所占的空間隨著節(jié)點個數(shù)改變的變化趨勢。并行方案單節(jié)點數(shù)據(jù)庫文件大小接近于CryptDB的數(shù)據(jù)庫文件大小。這表明該并行方案不會造成額外的空間開銷。變化趨勢表明，每個節(jié)點上的數(shù)據(jù)庫平均大小接近于比例下降，當(dāng)插入數(shù)據(jù)規(guī)模較大時，數(shù)據(jù)庫的增長百分比接近于零。這是由于該并行方案中僅在每個數(shù)據(jù)庫節(jié)點中冗余了表信息及部分索引信息，并且隨著數(shù)據(jù)庫插入內(nèi)容規(guī)模的增大，該部分信息所占的存儲空間的比例呈下降趨勢。結(jié)論表明，該方案達(dá)到了分布存儲的目的，數(shù)據(jù)規(guī)模較大時，對減小服務(wù)器的存儲壓力具有重要意義。

4 結(jié)束語

提出并實現(xiàn)了一種基于MapReduce框架的并行CryptDB加密數(shù)據(jù)庫系統(tǒng)加密存儲的并行方案。實驗結(jié)果表明，該方案能夠提高大規(guī)模關(guān)系數(shù)據(jù)庫數(shù)據(jù)的加密和存儲速度。方案中設(shè)計并實現(xiàn)了任務(wù)調(diào)度算法以產(chǎn)生任務(wù)分配策略，并對SQL文件按照產(chǎn)生的分配策略進行分割以提高方案的并行度。在SQL語句預(yù)處理、加密并存儲的過程中，充分利用了MapReduce框架的并行性，提高了CryptDB加密數(shù)據(jù)庫系統(tǒng)對于大規(guī)模數(shù)據(jù)加密并存儲的效率。方案整體的加速比接近于CryptDB節(jié)點個數(shù)p。和傳統(tǒng)單節(jié)點加密數(shù)據(jù)庫相比，每個CryptDB節(jié)點上的數(shù)據(jù)庫大小和節(jié)點個數(shù)成反比，即在每個CryptDB計算能力相同的理想環(huán)境下，數(shù)據(jù)庫大小為單節(jié)點的1/p。當(dāng)數(shù)據(jù)規(guī)模較大時，對減小服務(wù)器存儲壓力有著重要意義。

未來的工作重點是：將任務(wù)調(diào)度方案調(diào)整為任務(wù)執(zhí)行過程中動態(tài)實時分配；設(shè)計并實現(xiàn)其他SQL操作的并行化方案。

[1]ChorB,GoldreichO,KushilevitzE,etal.Privateinformationretrieval[J].JournaloftheACM,1998,45(6):965-981.

[2]SongDX,WagnerD,PerrigA.Practicaltechniquesforsearchesonencrypteddata[C]//ProceedingoftheIEEEsymposiumonsecurityandprivacy.[s.l.]:IEEE,2000:44-55.

[3]XiaZH,WangXH,SunXM,etal.Asecureanddynamicmulti-keywordrankedsearchschemeoverencryptedclouddata[J].IEEETransactionsonParallel&DistributedSystems,2016,27(2):340-352.

[4]SunW,WangB,CaoN,etal.Verifiableprivacy-preservingmulti-keywordtextsearchinthecloudsupportingsimilarity-basedranking[J].IEEETransactionsonParallel&DistributedSystems,2014,25(11):3025-3035.

[5]LiJ,WangQ,WangC,etal.Fuzzykeywordsearchoverencrypteddataincloudcomputing[C]//Internationalconferenceoncomputercommunications.[s.l.]:[s.n.],2010:1-5.

[6]CaoN,WangC,LiM,etal.Privacy-preservingmulti-keywordrankedsearchoverencryptedclouddata[J].IEEETransactionsonParallel&DistributedSystems,2011,25(1):829-837.

[7]BonehD,CrescenzoG,OstrovskyR,etal.Publickeyencryptionwithkeywordsearch[C]//ProceedingsoftheEUROCRYPT.Berlin:Springer-Verlag,2004:506-522.

[8]RalucaA,PopaN,ZeldovichH,etal.CryptDB:apracticalencryptedrelationalDBMS[R].Cambridge,MA:ComputerScienceandArtificialIntelligenceLaboratory,2011.

[9]KamaraS,RaykoyaM.Parallelhomomorphicencryption[M].Berlin:Springer-Verlag,2013:213-225.

[10]WangF,MathiasK,AndreasS.InitialencryptionoflargesearchabledatasetsusingHadoop[C]//Proceedingsofthe20thACMsymposiumonaccesscontrolmodelsandtechnologies.[s.l.]:ACM,2015:165-168.

[11]TuS,KaashoekMF,MaddenS,etal.Processinganalyticalqueriesoverencrypteddata[J].ProceedingsoftheVLDBEndowment,2013,6(5):289-300.

[12]PopaRA,LiFH,ZeldovichN.Anideal-securityprotocolfororder-preservingencoding[C]//ProceedingoftheIEEEsymposiumonsecurityandprivacy.[s.l.]:IEEE,2013:463-477.

[13]PopaRA,RedfieldCMS,ZeldovichN,etal.CryptDB:protectingconfidentialitywithencryptedqueryprocessing[C]//ProceedingoftheSOSP.[s.l.]:[s.n.],2011:85-100.

[14]PopaRA,ZeldovichN.CryptographictreatmentofCryptDB'sadjustablejoin[R].Cambridge,MA:ComputerScienceandArtificialIntelligenceLaboratory,2012.

[15]MartinL.XTS:amodeofAESforencryptingharddisks[J].IEEESecurity&Privacy,2010,8(3):68-69.

[16]BrakerskiZ,VaikuntanathanV.Efficientfullyhomomorphicencryptionfrom(standard)LWE[J].SIAMJournalonComputing,2014,43(2):831-871.

Investigation on Parallel Scheme of CryptDB Encrypted Database System

WANG Wei,YANG Geng,ZHANG Cheng-guo

(College of Computer Science,Nanjing University of Posts and Telecommunications, Nanjing 210003,China)

Encrypting data with encrypted DBMS is a feasible way to protect privacy of customer’s sensitive data on the Internet.Due to the massive privacy data generated by Internet every day,the traditional serial calculation can lead to longer time consumption of encrypted storage of privacy data.Combined the characteristic of MapReduce and CryptDB,a parallel insert and distributed storage scheme is designed and realized to improve the accelerate the speed of encrypting.Another two algorithms named JobControl and FileSplit are also proposed to improve the parallelism and controllability of this scheme.Map method in MapReduce is rewritten to achieve the parallel encryption and distributed storage of CryptDB system.After doing the experiments and performance analysis on the platform consists of 1 Master node and 3 CryptBD nodes and 3 MySQL server nodes,the experimental results show that the speed-up radio of this proposed scheme can reach 2.51,and the total time cost of CyrptDB parallel scheme can be reduced to 39.8% on the cluster consisting of 3 CyrptDB nodes.It can be used into the encryption and storage of large-scale relational data.

encrypted DBMS;MapReduce;CryptDB system;parallel encryption;distributed storage

2016-04-11

2016-08-05

時間：2017-01-10

國家自然科學(xué)基金資助項目(61272084，61572263)

王 偉(1992-)，男，碩士研究生，研究方向為加密數(shù)據(jù)庫、并行計算；楊 庚，博士，教授，博士生導(dǎo)師，CCF高級會員，研究方向為網(wǎng)絡(luò)與信息安全、分布與并行計算、大數(shù)據(jù)隱私保護。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.1019.060.html

TP31

A

1673-629X(2017)02-0090-06

10.3969/j.issn.1673-629X.2017.02.021