王 偉，楊 庚，張成果

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

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

王 偉，楊 庚，張成果

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

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

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

0 引 言

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

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

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

1 并行方案設(shè)計(jì)

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

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

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

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

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

1.2 并行方案模型

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

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

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

1.3 任務(wù)分配算法

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

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

輸入：節(jié)點(diǎn)個(gè)數(shù)m，SQL語(yǔ)句的條數(shù)N；

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

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

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

(3)將測(cè)試SQL語(yǔ)句通過(guò)JDBC分發(fā)到m個(gè)CryptDB節(jié)點(diǎn)上進(jìn)行加密存儲(chǔ)，得到時(shí)間開銷tm。

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

說(shuō)明：

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

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

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

1.4 文件分割算法

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

算法2：文件分割算法。

輸入：大的SQL文件；

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

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

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

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

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

1.5 Map函數(shù)

算法3：Map。

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

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

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

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

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

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

說(shuō)明：

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

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

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

2 并行方案性能分析

2.1 串行性能分析

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

Ts=Tmeta+Tenc+Tinsert

(1)

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

對(duì)于數(shù)值型的數(shù)據(jù)，RND采用的是添加初始化向量IV的Blowfish算法，DET采用的是Blowfish加密算法，DETJOIN采用的是基于ECC(橢圓加密)的ECJoin算法。對(duì)于字符型數(shù)據(jù)，RND采用的是帶初始化向量IV(即salt值)的CBC模式的AES加密算法，它能保證密文加密的隨機(jī)性，即相同的明文加密后密文可能不相同；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)的代碼中沒有實(shí)現(xiàn)OPEJOIN算法和SEARCH洋蔥，所以不進(jìn)行討論。并且由于CryptDB使用的加密算法明文在加密前都會(huì)進(jìn)行填充操作，所以輸入和輸出的規(guī)模都是定長(zhǎng)。對(duì)于數(shù)值型的數(shù)據(jù)，“等值洋蔥”的復(fù)雜度為：

UoEq_int=Recjoin+2·Rblowfish

(2)

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

UoOrder_int=Rmope+Rblowfish

(3)

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

UoAdd=ReAdd

(4)

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

UoEq_str=Recjoin+2·Raes

(5)

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

UoOrder_str=Rmope+Raes

(6)

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

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

(7)

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

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

(8)

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

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

(9)

由文獻(xiàn)[14]可知，ECJoin的橢圓計(jì)算和mOPE編碼的復(fù)雜度都為O(logn)。由文獻(xiàn)[15-16]可知，AES、Blowfish、Paillier的復(fù)雜度為O(n)。ECJoin中除了橢圓計(jì)算外還會(huì)使用AES對(duì)明文進(jìn)行編碼，因此ECJoin的復(fù)雜度為O(n+logn)。mOPE編碼后還會(huì)使用DET對(duì)B樹的葉子進(jìn)行加密，所以mOPE的復(fù)雜度也為O(n+logn)。由于當(dāng)n>0時(shí),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è)查詢?cè)獢?shù)據(jù)表的時(shí)間和插入MySQL數(shù)據(jù)庫(kù)的復(fù)雜度分別為δ次和ε次浮點(diǎn)計(jì)算，設(shè)浮點(diǎn)計(jì)算的時(shí)間為Tfc,則:

(11)

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

Ts=(Uenc+δ+ε)·Tfc

(12)

2.2 并行性能分析

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

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

M=(Uenc+ε)/p+δ

(13)

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

Ttr=ζ·p·Tfc

(14)

則并行時(shí)間為：

Tp=M·Tfc+Ttr

(15)

則加速比可表示為：

(16)

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

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)的硬件平臺(tái)包括1個(gè)Master節(jié)點(diǎn)和3個(gè)CryptDB節(jié)點(diǎn)及3個(gè)MySQL服務(wù)器。Master節(jié)點(diǎn)負(fù)責(zé)工作的監(jiān)控和調(diào)度，CryptDB節(jié)點(diǎn)負(fù)責(zé)密文計(jì)算，MySQL服務(wù)器負(fù)責(zé)執(zhí)行密文SQL并存儲(chǔ)的任務(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。

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

3.2 CryptDB并行方案INSERT性能

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

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

表1 部分實(shí)驗(yàn)結(jié)果

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

圖2 INSERT操作時(shí)間

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

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

3.3 CryptDB并行方案空間性能

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

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

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

4 結(jié)束語(yǔ)

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

未來(lái)的工作重點(diǎn)是：將任務(wù)調(diào)度方案調(diào)整為任務(wù)執(zhí)行過(guò)程中動(dòng)態(tài)實(shí)時(shí)分配；設(shè)計(jì)并實(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

時(shí)間：2017-01-10

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272084，61572263)

王 偉(1992-)，男，碩士研究生，研究方向?yàn)榧用軘?shù)據(jù)庫(kù)、并行計(jì)算；楊 庚，博士，教授，博士生導(dǎo)師，CCF高級(jí)會(huì)員，研究方向?yàn)榫W(wǎng)絡(luò)與信息安全、分布與并行計(jì)算、大數(shù)據(jù)隱私保護(hù)。

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