CryptDB密文數據庫系統并行方案研究

王 偉，楊 庚，張成果

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

CryptDB密文數據庫系統并行方案研究

王 偉，楊 庚，張成果

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

加密數據庫對隱私數據的加密存儲保護是解決當前互聯網中用戶隱私數據泄露的一種可行方案。鑒于互聯網中每日產生的用戶隱私數據規模巨大，傳統的串行計算會導致隱私數據的加密存儲時間消耗較長。為提高加密存儲等數據處理的速度，將MapReduce并行框架與CryptDB密文數據庫系統進行有機結合，設計并實現了CryptDB密文數據庫系統并行加密和分布式存儲的方案。并行方案采用任務調度算法、文件分割算法來提高其并行性和可控性，通過重寫MapReduce框架中的Map方法來實現CryptDB密文數據庫系統的并行加密和分布式存儲。基于由1個Master節點、3個CryptDB節點和3個MySQL服務器構成的實驗平臺，進行了并行方案的實驗驗證及其性能分析。實驗結果表明，所構建的并行方案在3個CryptDB節點集群中的加速比可達到2.51，加密和存儲時間節省了60.2%，可用于大規模關系數據的加密存儲。

加密數據庫；MapReduce；CryptDB系統；并行加密；分布式存儲

0 引 言

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

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

文中以CryptDB系統的加密存儲過程為出發點，利用云計算MapReduce框架對海量數據運算高效的特點，設計并實現了基于任務并行的CryptDB系統優化方案，實現了對大規模隱私數據進行高效加密及存儲的處理。該方案對DML/DDL語句進行分組，然后把每組操作分發到部署有CryptDB系統的節點上，并對其進行加密計算并存儲，以達到縮短加密及存儲時間的目的。

1 并行方案設計

1.1 CryptDB密文數據庫系統

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

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

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

(3)洋蔥加密方案可以高效地調整數據的加密等級。

1.2 并行方案模型

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

圖1 任務并行方案

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

1.3 任務分配算法

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

算法1：任務分配算法。

輸入：節點個數m，SQL語句的條數N；

輸出：每個節點的任務規模Xm。

(1)輸入參數為集群中CryptDB節點的個數m，以及待加密的任務規模即SQL語句的條數N。

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

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

(6)分別用最優的map時間乘以各節點計算能力，得到每個節點應分配到的任務規模Xm=tava·xm。

說明：

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

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

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

1.4 文件分割算法

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

算法2：文件分割算法。

輸入：大的SQL文件；

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

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

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

(3)當累加器的SQL語句達到當前節點所需規模時，將temp中的內容保存到HDFS文件系統中，并以節點編號命名。

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

1.5 Map函數

算法3：Map。

輸入：文件路徑、容器大小、節點個數。

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

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

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

(4)將提取出的屬性值根據預先設定的容器大小進行拼接，構建成新的標準SQL語句。

(5)通過JDBC調用CryptDB密文數據庫系統，執行SQL語句，加密并存儲數據。

說明：

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

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

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

2 并行方案性能分析

2.1 串行性能分析

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

Ts=Tmeta+Tenc+Tinsert

(1)

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

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

UoEq_int=Recjoin+2·Rblowfish

(2)

“保序洋蔥”的復雜度為：

UoOrder_int=Rmope+Rblowfish

(3)

“HOM洋蔥”的復雜度為：

UoAdd=ReAdd

(4)

對于字符型數據，“等值洋蔥”的復雜度為：

UoEq_str=Recjoin+2·Raes

(5)

保序洋蔥的復雜度為：

UoOrder_str=Rmope+Raes

(6)

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

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

(7)

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

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

(8)

設待加密字段有a個數值型數據和b個字符型數據，則:

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

(9)

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

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

(10)

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

(11)

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

Ts=(Uenc+δ+ε)·Tfc

(12)

2.2 并行性能分析

設共有p個CryptDB節點處理包含a個數值型數據和b個字符型數據的SQL文件。該SQL文件被分割成了p個數據塊，對應p個mapper。則每個分塊中包含a/p個數值型數據和b/p個字符型數據。

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

M=(Uenc+ε)/p+δ

(13)

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

Ttr=ζ·p·Tfc

(14)

則并行時間為：

Tp=M·Tfc+Ttr

(15)

則加速比可表示為：

(16)

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

3 實 驗

3.1 實驗環境

實驗的硬件平臺包括1個Master節點和3個CryptDB節點及3個MySQL服務器。Master節點負責工作的監控和調度，CryptDB節點負責密文計算，MySQL服務器負責執行密文SQL并存儲的任務,其配置均為：

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性能

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

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

表1 部分實驗結果

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

圖2 INSERT操作時間

(1)對于相同規模的SQL語句，CryptDB系統的執行時間比CryptDB并行方案單節點執行時間短。這是由于Hadoop并行框架中有任務調度和通信時間開銷。

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

3.3 CryptDB并行方案空間性能

表2 數據庫大小

圖3 數據庫文件平均大小

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

4 結束語

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

未來的工作重點是：將任務調度方案調整為任務執行過程中動態實時分配；設計并實現其他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

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

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

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