云計算環(huán)境下高效安全的冠字號碼查詢方法

侯作鑫，秦 拯，歐 露，胡玉鵬

（湖南大學信息科學與工程學院，長沙410012）

云計算環(huán)境下高效安全的冠字號碼查詢方法

侯作鑫，秦 拯，歐 露，胡玉鵬

（湖南大學信息科學與工程學院，長沙410012）

針對現(xiàn)有冠字號碼管理系統(tǒng)查詢時間長、數(shù)據(jù)存儲可擴展性差等問題，將云計算技術應用于冠字號碼的存儲和查詢中。根據(jù)銀行ATM機加鈔過程及網(wǎng)點清分過程，定義存儲冠字號碼信息的關聯(lián)形式，結(jié)合錢幣的冠字號碼，提出可交換加密的折半查找索引算法，對索引及數(shù)據(jù)進行加密，保證冠字號碼的安全性。理論分析與實驗結(jié)果表明，該方法可利用云計算平臺的虛擬存儲和虛擬計算能力，滿足銀行對冠字號碼管理系統(tǒng)的數(shù)據(jù)傳輸能力和擴展性能的要求，并且與當前主流查詢方法相比，具有較高的查詢效率及安全性。

云計算；冠字號碼；可交換加密；查詢；安全索引

1 概述

冠字號碼是一種標記鈔票唯一性的符號，由大寫英文字母和十進制數(shù)字組成，總位數(shù)為10，其中，前4位中有2位是大寫英文字母，其他2位是十進制數(shù)字；后6位是十進制數(shù)字。針對國家反洗錢、現(xiàn)鈔追蹤和數(shù)據(jù)統(tǒng)計等方面需求，中國人民銀行規(guī)定，客戶的每一筆存取款業(yè)務都要滿足冠字號碼查詢需求。中國銀行業(yè)服務改進情況報告顯示，當前銀行柜臺和自助設備現(xiàn)金交易量數(shù)目巨大，2012年僅銀行自助設備的交易情況已達321.56億筆，總交易額達923.71萬億元。自2005年以來，全國年均增長超過20%的現(xiàn)金投放總量，對傳統(tǒng)的人民幣流通管理模式形成很大壓力和挑戰(zhàn)［1］。

雖然國內(nèi)已有部分省市對冠字號碼進行了管理，比如北京、上海等，但由于冠字號碼數(shù)據(jù)量龐大，數(shù)據(jù)處理比較復雜，查詢時間較長，給用戶造成較差體驗，影響了冠字號碼管理系統(tǒng)的推廣，不利于管理機構(gòu)對錢幣的監(jiān)管統(tǒng)計。

同時，由于銀行業(yè)的特殊性，需要保證客戶信息的安全，傳統(tǒng)的數(shù)據(jù)庫索引加密是對整個數(shù)據(jù)庫索引進行加密［2］，在索引查找時，需先解密再比較，I/O次數(shù)多、效率低。目前，有關云數(shù)據(jù)庫下的密文檢索研究，一般指檢索文件［3-4］，不適合冠字號碼的密文檢索。

本文根據(jù)銀行ATM機加鈔過程及網(wǎng)點的清分過程，定義冠字號碼在存儲中的關聯(lián)形式，結(jié)合冠字號碼可轉(zhuǎn)化為二進制形式的特征，提出可交換加密的折半查找索引算法（Commutative Encryption Binary Search-Chord，CEBS-Chord），考慮到云計算在海量存儲以及高性能計算方面的優(yōu)勢［5-6］，設計基于云計算的冠字號碼高效安全查詢方法。

2 基于云計算的冠字號碼查詢框架

2.1 查詢框架

云計算是繼服務計算和網(wǎng)格計算之后的一種新的計算模式，在遠程的數(shù)據(jù)中心，成千上萬臺電腦和服務器連接成一片電腦云，用戶通過電腦、手機、其他智能終端等方式接入云計算，就可以按自己的需求進行存儲和運算。它是能夠提供動態(tài)資源池、虛擬化和高可用性的下一代計算平臺［7-8］。云計算具有高可擴展性和高可用性?？蓴U展性表達了云計算能夠無縫地擴展到大規(guī)模的集群之上，甚至包含數(shù)千個節(jié)點同時進行處理，而這正好能滿足冠字號碼不斷增加所需的擴展容量。文獻［9］介紹了銀行業(yè)與云計算應用結(jié)合的必要性。

本文方法中的冠字號碼數(shù)據(jù)不存儲在本地，而是保存在云計算提供的虛擬存儲中心，銀行的各種查詢、處理等應用程序也不運行在前置機中，而是運行在云計算的數(shù)據(jù)處理中心，即大規(guī)模的服務器集群中?；谠朴嬎愕墓谧痔柎a管理利用基于時間戳的數(shù)據(jù)庫管理系統(tǒng)來追溯每一張紙幣，特別是假幣的歷史信息，并可將此信息與用戶個人身份認證信息、流通過程的信息進行對應，為紙幣使用情況的統(tǒng)計提供數(shù)據(jù)支持。針對包含冠字號碼的海量數(shù)據(jù)挖掘，分析用戶的消費狀況、監(jiān)控可疑資金以及可疑人員的流動情況，從空間和時間2個層次上實現(xiàn)金融業(yè)的動態(tài)監(jiān)管，為相關部門制定政策以及監(jiān)管金融業(yè)運行提供強大的數(shù)據(jù)支撐服務。

圖1 基于云計算的冠字號碼存儲與查詢結(jié)構(gòu)

2.2 索引框架

云環(huán)境下的冠字號碼數(shù)據(jù)按照水平分區(qū)的形式分成若干個數(shù)據(jù)塊，這些數(shù)據(jù)塊分布式地存儲在數(shù)據(jù)中心的不同服務器上。存儲節(jié)點是云數(shù)據(jù)中心分布式存儲系統(tǒng)中的一個節(jié)點，保存著分配在此節(jié)點的原始冠字號碼數(shù)據(jù)、根據(jù)原始冠字號碼數(shù)據(jù)建立的本地索引和部分全局索引等信息。由于使用傳統(tǒng)的中心服務器形式存儲所有全局索引易形成性能瓶頸問題，因此將全局索引分布式地保存在各個存儲節(jié)點。每個存儲節(jié)點邏輯上按照Chord組織在一起，共同維護全局索引。為存儲在從節(jié)點的數(shù)據(jù)建立局部索引，而全部存儲節(jié)點按照Chord結(jié)構(gòu)共同維護全局索引。根據(jù)索引公布策略，將局部索引信息通過Chord接口公布到整個覆蓋網(wǎng)絡形成全局索引。局部索引的信息格式為（ip，Uj），其中，ip指局部索引所在節(jié)點的IP地址；Uj是局部索引對應的第j個從節(jié)點，如圖2所示。

圖2 索引結(jié)構(gòu)

數(shù)據(jù)查詢分為2個階段：（1）通過Chord覆蓋網(wǎng)絡查詢?nèi)炙饕祷貪M足條件的索引信息條目（ip，Uj）；（2）通過索引信息條目中的ip地址和Uj定位到存儲節(jié)點的CEBS索引中，并在此索引中進行數(shù)據(jù)查詢，返回最終滿足要求的結(jié)果。

3 冠字號碼數(shù)據(jù)采集

冠字號碼在云中主要存儲的數(shù)據(jù)為：冠字號碼編號，交易地點，交易時間，使用人。冠字號碼的數(shù)據(jù)存儲過程分為2種情況：ATM機上和銀行前臺的冠字號碼存儲?？紤]第1種情況，針對現(xiàn)有ATM機有抓取冠字號碼的能力才能投入使用的不足，提出一種關聯(lián)模式，并且無需對ATM機進行加裝冠字號抓取模塊的改造，節(jié)省了大量的ATM機改造費用。具體過程是：將錢幣在清分機中以捆扎為單位存儲，在ATM加鈔時，以捆扎為單位裝入ATM鈔箱，形成ATM機與所裝鈔箱對應、所裝鈔箱與捆扎對應、捆扎與冠字號碼對應，當使用者取錢時可以記錄使用者信息，這樣使用者信息、交易時間信息、交易地點信息（所屬ATM機）就被記錄下來。考慮第2種情況，前臺的冠字號碼存儲經(jīng)清分機完成，當客戶在前臺存錢或者取錢時，就記錄了使用者信息、交易時間、交易地點（所在網(wǎng)點）。具體對應關系如圖3所示。

教育技術AECT1994定義的教學技術是為了促進學習對有關的資源與過程進行設計、開發(fā)、利用、管理和評價的理論和實踐，明確了教育技術是關于理論與實踐的學科。而現(xiàn)代教育技術是在教育技術的基礎之上賦予“現(xiàn)代”二字，即把教育技術與現(xiàn)代信息技術相結(jié)合，運用新技術、新方法、新理念完成新的歷史任務。通過對比分析，可以看出“十一五”“十二五”“十三五”三個階段的現(xiàn)代教育技術教材的課程目標均是圍繞教育技術理論與實踐制定的，只是側(cè)重點有所不同。具體見表2。

圖3 冠字號碼與ATM機、銀行網(wǎng)點的對應關系

4 冠字號碼安全索引查詢

冠字號碼的查詢基于冠字號碼的存儲，根據(jù)以上存儲過程及方法，結(jié)合冠字號碼特征，提出一種快速、安全的兩層索引結(jié)構(gòu)——CEBS-Chord索引。

4.1 全局索引

Chord是一種結(jié)構(gòu)化P2P覆蓋網(wǎng)絡。Chord把節(jié)點和資源標識映射到相同空間，以保證一致性哈希，并選擇SHA-1作為哈希函數(shù)，是分布式哈希（Distributed Hash Table，DHT）的一種實現(xiàn)。Chord是一個算法，也是一個協(xié)議。作為一個算法，Chord可以從數(shù)學的角度嚴格證明其正確性和收斂性；作為一個協(xié)議，Chord詳細定義了每個環(huán)節(jié)的消息類型。Chord通過使用一致性雜湊函數(shù)，把關鍵值存儲在Chord中的相應節(jié)點上［10-11］。一致性雜湊函數(shù)通過使每個節(jié)點存儲數(shù)量大致相等的關鍵值來平衡負載，并且使得當節(jié)點加入或退出時關鍵值的相對移動比較小。Chord中的路由表是分散的，每個節(jié)點通過和其他的少數(shù)節(jié)點交流來獲取路徑信息。一個由N個節(jié)點組成的索引在穩(wěn)定狀態(tài)時，每個節(jié)點僅保存O（log N）個其他節(jié)點的信息，查詢操作也僅需要發(fā)送O（log N）條消息到其他節(jié)點。當索引更新時所產(chǎn)生的消息量在絕大多數(shù)情況下不超過O（log2N）。其中，每個節(jié)點都維護一個Finger表，該表長度為m，其第i項存放節(jié)點n的第（n+2i-1）mod 2m個successor（1≤i≤m）。每個節(jié)點都維護一個predecessor和successor列表，該列表的作用是能快速定位前繼和后繼，并能周期性地檢測前繼和后繼的健康狀態(tài)。存放的successor是按2的倍數(shù)等比遞增。資源Key存儲在下面的Node上：沿Chord環(huán)，Hash（Node）≥Hash（Key）的第1個Node為這個Key的successor。給定一個Key，查找其對應資源的節(jié)點（即查找該Key的successor）步驟如下：

（1）檢查Hash（Key）是否在節(jié)點m和m的直接successor之間。

（2）若是，則查找結(jié)束，m的直接successor即為目標。

（3）在m的Finger表中，找出與Hash（Key）距離最近且小于Hash（Key）的m的successor，然后把查找請求轉(zhuǎn)發(fā)到該節(jié)點。

（4）繼續(xù)上述過程，直至找到Key的successor節(jié)點。

4.2 CEBS索引

云計算中從節(jié)點中的索引［12］一般采用B樹［13-15］結(jié)構(gòu)，CEBS索引相對原索引算法進行以下3點改進：

（1）在結(jié)構(gòu)上根據(jù)冠字號碼特征將其存儲形式由字符串改為二進制數(shù)，既減少了存儲空間，又降低了查詢時的比對次數(shù)，提高了查詢效率。

（2）對索引結(jié)構(gòu)中的存儲信息進行交替加密，保護查詢數(shù)據(jù)。具體加密方法如下：令s=snsn-1…s1∈｛0，1｝n為一個長度為n的二進制數(shù)據(jù)流，表示需要進行比較的數(shù)據(jù)。

定義1 二進制數(shù)據(jù)流S的0編碼由如下形式表示：

定義2 二進制數(shù)據(jù)流S的1編碼由如下形式表示：

（3）在B樹節(jié)點中的查詢加密的冠字號碼時采用折半查找的查詢算法，提高了其查詢效率，具體步驟如下：

1）主節(jié)點發(fā)送查詢請求，根據(jù)存儲的全局Chord索引找出對應的本地B樹索引。

2）從屬節(jié)點將查詢請求中的冠字號碼轉(zhuǎn)換為二進制類型，每一個字符占6 bit，如0對應二進制000000，9對應二進制001001，A對應二進制001100，Z對應二進制100011，冠字號碼T2U5025132對應二進制數(shù)011101 000010 011110 000101 000000 000010 000101 000001 000011 000010。

3）對轉(zhuǎn)換后的二進制形式冠字號碼采用1編碼的形式進行交替加密，然后計算：

4）設要查詢的冠字號碼二進制0編碼后為target，加密后的冠字號碼ta=Ea（Eb（target）），B樹節(jié)點中含冠字號碼個數(shù)為n，設存儲的索引節(jié)點的二進制流的1編碼形式為A［n］，在CEBS索引中采用折半查找ta的算法具體如下：

步驟1 設置low=0，high=n-1。

步驟2 mid=（low+high）/2，如果low≥high，則進入步驟3；如果Rx≠0，則low=m id+1；如果Rx=0&&Rx+1≠0，則結(jié)束查詢，返回結(jié)果。如果Rx=0&&Rx+1=0，則high=mid-1；如果low＜high，則重復步驟2。

步驟3 如果A［mid］.next==NULL，則返回A［mid］的值；如果A［m id-1］＜ta和A［m id-1］≥ta，而且A［mid］.next！=NULL，則執(zhí)行下一層搜索，返回步驟1。

在算法執(zhí)行過程中，輸入的數(shù)據(jù)都進行了加密處理，因此，不會導致冠字號碼信息的泄漏，滿足了銀行對數(shù)據(jù)安全性的要求。查詢得到的返回值是符合查詢條件鍵值的地址塊，該地址對應相應的冠字號碼信息。將該冠字號碼信息返回給主節(jié)點，便完成了整個查詢。

5 實驗與結(jié)果分析

實驗中使用實驗室局域網(wǎng)中的3臺計算機來模擬云計算平臺，每臺機器的通信帶寬為10 M b/s，處理器為Inter（R）Core（TM）i5CPU，2.40 Hz，內(nèi)存為2 GB，硬盤為500 GB，實驗數(shù)據(jù)取自于某合作銀行的真實數(shù)據(jù)。

實驗從索引建立效率和查詢吞吐量2個方面來評估本文查詢方法的性能。其中，索引建立效率反映了索引更新和建立性能以及索引的可擴展性；查詢吞吐量用于評估查詢方法的速度。在下文實驗中，將CEBS-Chord索引算法與SNB索引算法［17］進行相關性能的對比。選擇SNB索引算法的原因是SNB索引是現(xiàn)有云環(huán)境下使用樹型結(jié)構(gòu)的典型索引。分別建立1×106條～5×106條冠字號碼數(shù)據(jù)，為了更全面準確地比較2種索引算法，考慮樹形結(jié)構(gòu)索引中唯一的參數(shù)M（M表示M叉樹）對索引性能的影響，選取M=7和M=14比較建立索引時間，分析2種查詢算法建立索引的效率，實驗結(jié)果如圖4所示。

圖4 索引建立效率對比

根據(jù)圖4可知，雖然CEBS-Chord索引算法需要對冠字號碼數(shù)據(jù)進行預處理，但其建立時間仍要優(yōu)于SNB索引算法，這是因為相對于預處理時間，其在CEBS-Chord索引中的查找比對時間遠少于原索引查找比對時間。因此，CEBS-Chord索引建立效率要優(yōu)于原索引，并且這種優(yōu)勢不以M的變化而變化，但是針對同一種索引算法，M的大小影響查詢效率［18］。

查詢吞吐量是指單位時間內(nèi)可以處理的查詢數(shù)量，反映了單位時間內(nèi)索引可以支持的查詢量，是衡量索引結(jié)構(gòu)的重要指標。該實驗比較了CEBSChord和SNB算法的查詢性能，從數(shù)據(jù)庫中隨機選擇1 000條記錄作為查詢樣本，取這1 000條記錄的查詢時間代表各自的查詢性能。在1×106條～5×106條冠字號碼數(shù)據(jù)中，對1 000條冠字號碼記錄進行查詢，記錄其查詢時間，得出M=7和M= 14下2種算法在單位時間內(nèi)的查詢條數(shù)，如圖5所示。

圖5 查詢效率對比

根據(jù)圖5可知，當冠字號碼數(shù)量增加時，2種索引算法對應的查詢吞吐量均增加。CEBS-Chord索引算法的查詢效率要優(yōu)于SNB索引算法，這是因為CEBS-Chord索引節(jié)點內(nèi)及節(jié)點間的數(shù)據(jù)比較是二進制數(shù)，相對于SNB索引算法的字符型比較，其效率要高很多。此時查詢效率的提高與M的大小無關。綜上所述，CEBS-Chord索引算法有效地提高了整體查詢性能。

6 結(jié)束語

本文利用云計算的海量虛擬存儲能力和虛擬計算能力，將云計算技術運用到冠字號碼的存儲和查詢中。采用CEBS-Chord索引查詢算法，給出針對冠字號碼特征的二進制存儲形式，將字符轉(zhuǎn)化為二進制數(shù)，既能提高查詢效率，又能減少存儲空間。通過對索引數(shù)據(jù)進行可交換加密保證了查詢時數(shù)據(jù)的安全性。采用云計算技術及可交換加密技術，在保障冠字號碼安全存儲的前提下，增強了冠字號碼存儲結(jié)構(gòu)的易擴展性，同時為云數(shù)據(jù)庫中針對冠字號碼的安全索引查詢提供了一種優(yōu)化方法。由于本文只對二級索引進行改進，查詢性能還有提升空間，下一步將根據(jù)二級索引中節(jié)點的查詢熱度，優(yōu)化二級索引在一級索引中的部署，提高整體查詢性能。

［1］ 李 文.冠字號碼技術應用有利于人民幣流通管理［J］.金融博覽，2012，（12）：53-54.

［2］ 雷春紅，余建橋.基于密文塊數(shù)組折半查找的B+樹密文數(shù)據(jù)庫索引［J］.計算機工程與設計，2010，31（4）：713-716.

［3］ 馮貴蘭，譚 良.云環(huán)境中基于多屬性排序的密文檢索方案［J］.計算機科學，2013，40（11）：131-136.

［4］ 項 菲，劉川意.云計算環(huán)境下密文搜索算法的研究［J］.通信學報，2013，34（7）：143-152.

［5］ 陳 康，鄭緯民.云計算：系統(tǒng)實例與研究現(xiàn)狀［J］.軟件學報，2009，20（5）：1337-1348.

［6］ Ding Linlin，Qiao Baiyou，Wang Guoren，et al.An Efficient Quad-tree Based Index Structure for Cloud Data Management［C］//Proceedings of the 12 th International Conference on Web-age Information M anagement. Berlin，Germany：Springer，2011：238-250.

［7］ 劉 鵬.云計算［M］.北京：電子工業(yè)出版社，2010.

［8］ 郭又銘，王 鵬，唐 華，等.基于相空間的云計算專用監(jiān)控系統(tǒng)［J］.計算機工程，2013，39（7）：40-44.

［9］ 蔚趙春，凌 鴻.我國商業(yè)銀行私有云建設研究［J］.浙江金融，2012，（5）：59-62.

［10］ Chord算法（原理）［EB/OL］.（2013-06-05）.http：//blog. sina.com.

［11］ 蔡瑞青.覆蓋網(wǎng)絡自組織結(jié)構(gòu)及其QoS路由研究［D］.杭州：浙江大學，2007.

［12］ Wu Sai，Jiang Dawei.Efficient B-tree Based Indexing for Cloud Data Processing［J］.Proceedings of the VLDB Endowment，2010，3（1）：1207-1218.

［13］ Wu Sai，W u Kun-Lung.An Indexing Framework for Efficient Retrieval on the Cloud［J］.IEEE Data Engineering Bulletin，2009，32（1）：77-84.

［14］ W ang Jinbao，W u Sai.Indexing Multi-dimensional Data in a Cloud System［C］//Proceedings of the ACM International Conference on Management of Data. New York，USA：ACM Press，2010：591-602.

［15］ 林子雨，賴永炫.云數(shù)據(jù)庫研究［J］.軟件學報，2012，23（5）：1148-1166.

［16］ 查 俊，蘇錦海.姚氏百萬富翁問題的高效解決方案［J］.計算機工程，2010，36（14）：124-126.

［17］ Zhou W ei，Lu Jin.SNB-index：A SkipNet and B+Tree Based Auxiliary Cloud Index［J］.Cluster Computing，2014，17（2）：453-462.

［18］ 余祥宣，劉 偉.數(shù)據(jù)庫的密文索引機制［J］.華中科技大學學報：自然科學版，2002，30（3）：16-18.

編輯 陸燕菲

Efficient and Safe Query Method of Crown Word Number in Cloud Computing Environment

HOU Zuoxin，QIN Zheng，OU Lu，HU Yupeng
（College of Information Science and Engineering，Hunan University，Changsha 410012，China）

For the problem s of long query time and poor data storage scalability of the existing crown word number management system，the cloud Computing is applied to the storage and query of crown word number.The association form of storing information of crown word numbers is defined according to the money-adding process of bank ATM and the counting process of bank branches.In order to ensure the safety of crown word number，a Commutative Encryption Binary Search-Chord（CEBS-Chord）is proposed in this paper to realize index and data encryption.Theoretical analysis and experimental result show that the method can make full use of the virtual storage and virtual computing power of cloud computing platform，and it can meet the data transmission capacity and extension performance requirements of an crown word number management system.Compared with the current query methods，it has efficient query efficiency and high security.

cloud computing；crown word number；commutative encryption；query；safe index

侯作鑫，秦 拯，歐 露，等.云計算環(huán)境下高效安全的冠字號碼查詢方法［J］.計算機工程，2015，41（11）：47-51.

英文引用格式：Hou Zuoxin，Qin Zheng，Ou Lu，et al.Efficient and Safe Query Method of Crown Word Number in Cloud Computing Environment［J］.Computer Engineering，2015，41（11）：47-51.

1000-3428（2015）11-0047-05

A

TP393.09

10.3969/j.issn.1000-3428.2015.11.009

國家自然科學基金資助項目（61272546）。

侯作鑫（1989-），男，碩士，主研方向：云計算，數(shù)據(jù)庫索引技術；秦 拯，教授；歐 露，博士；胡玉鵬，副教授。

2014-07-15

2014-09-15 E-m ail：houzuoxin@163.com