陳 建,沈?yàn)t軍,姚一楊,邢雅菲,琚小明

(1.國網(wǎng)浙江省電力公司信息通信分公司, 杭州 310007; 2.華東師范大學(xué) 計算機(jī)科學(xué)與軟件工程學(xué)院,上海 200062) (*通信作者電子郵箱xmju@sei.ecnu.edu.cn)

基于密文策略屬性基加密系統(tǒng)訪問機(jī)制的緩存替換策略

陳 建1,沈?yàn)t軍1,姚一楊1,邢雅菲2,琚小明2*

(1.國網(wǎng)浙江省電力公司信息通信分公司, 杭州 310007; 2.華東師范大學(xué) 計算機(jī)科學(xué)與軟件工程學(xué)院,上海 200062) (*通信作者電子郵箱xmju@sei.ecnu.edu.cn)

為提高基于密文策略屬性基加密(CP-ABE)系統(tǒng)的數(shù)據(jù)緩存性能，針對CP-ABE加密的數(shù)據(jù)，提出一種有效的緩存替換算法——最小屬性價值(MAV)算法。該算法結(jié)合CP-ABE加密文件的訪問策略并統(tǒng)計高頻屬性值的個數(shù)，利用余弦相似度方法和高頻屬性值統(tǒng)計表來計算屬性相似度；同時結(jié)合屬性相似度和文件大小計算緩存文件的屬性值價值，并替換屬性值價值最小的文件。在與最近最少使用(LRU)、最不經(jīng)常使用(LFU)、Size緩存替換算法的對比實(shí)驗(yàn)中，針對CP-ABE加密后的數(shù)據(jù)， MAV算法在提高加密文件請求命中率和字節(jié)命中率方面具有更好的性能。

屬性策略;緩存替換策略;密文策略屬性基加密算法;加密數(shù)據(jù);余弦相似度

0 引言

緩存技術(shù)是提高云存儲數(shù)據(jù)的存取速度的一種重要方法,緩存技術(shù)的核心內(nèi)容是緩存替換策略。針對緩存問題,目前所提出的緩存替換策略主要有：1)傳統(tǒng)經(jīng)典的緩存替換算法,包括最近最少使用(Least-Recently-Used, LRU)、最不經(jīng)常使用(Least-Frequently-Used, LFU)替換算法,這些傳統(tǒng)的替換算法實(shí)現(xiàn)簡單,但未考慮時間間隔、對象大小等因素的影響;2)基于對象大小的緩存替換算法,包括Size和GD-Size(Greedy Dual-Size)算法[1],這些算法充分考慮了對象大小的影響因素,但并未考慮緩存對象的訪問頻率的影響因素[2]。針對傳統(tǒng)緩存替換算法的不足,結(jié)合不同的緩存數(shù)據(jù)的特點(diǎn),一些新的緩存替換算法被提出，主要包括:根據(jù)數(shù)據(jù)的位置相關(guān)性提出的位置相關(guān)查詢中基于最小訪問代價的緩存替換方法[3],該方法對于位置相關(guān)性好的數(shù)據(jù)有良好的效果,對于位置相關(guān)性差的數(shù)據(jù)的作用卻并不明顯;根據(jù)緩存文件的權(quán)重值提出的基于PageRank的緩存替換策略[4],該算法優(yōu)于LFU算法,但是具有單個緩存系統(tǒng)的局限性;針對Web緩存具有延遲的特點(diǎn)提出的基于預(yù)測的Web緩存替換策略[5],該策略相對于傳統(tǒng)替換算法而言提高了Web緩存的命中率和字節(jié)命中率,但是該預(yù)測代價太大,算法過于復(fù)雜。

目前提出的緩存替換算法針對的都是明文數(shù)據(jù),還沒有一種是針對加密數(shù)據(jù)進(jìn)行的緩存替換策略。本文充分考慮基于CP-ABE加密的數(shù)據(jù)的特點(diǎn),結(jié)合基于CP-ABE加密數(shù)據(jù)的特有的訪問策略,提出針對一種基于CP-ABE加密的數(shù)據(jù)的緩存替換算法——最小屬性價值(Minimum Attribute Value, MAV)算法。該算法是一種低開銷、高性能和適應(yīng)性的算法,它結(jié)合基于CP-ABE加密的文件特有的訪問策略,通過統(tǒng)計加密文件的訪問策略中的屬性值,建立屬性值統(tǒng)計表,計算屬性權(quán)重,利用計算文本相似度方法中的余弦相似度算法計算加密文件的屬性值相似度,同時考慮文件的大小因素,計算緩存中文件的屬性值價值,替換屬性值價值最小的文件。

1 基于CP-ABE訪問機(jī)制的緩存問題

1.1 CP-ABE屬性策略的研究基礎(chǔ)

基于CP-ABE加密的文件,每個文件都有一個訪問策略,文件的訪問策略與屬性值集密切相關(guān)。在上傳文件時,要先設(shè)計好相應(yīng)的訪問策略,才能進(jìn)行文件的加密[7]。訪問策略被建立成一棵訪問結(jié)構(gòu)樹,樹的葉節(jié)點(diǎn)都是相應(yīng)的屬性值。解密時,用戶首先要上傳自己的屬性,系統(tǒng)將要解密用戶的屬性值與訪問策略中的屬性值相比較,屬性值可以匹配,就可形成相應(yīng)的私鑰,從而可以解密文件[6]。有關(guān)CP-ABE屬性策略的相關(guān)定義如下:

定義1 屬性。設(shè)P={p1,p2,…,pn}為所有屬性的集合,則每個用戶的屬性Ati是P的一個非空子集,Ati?{p1,p2,…,pn},那么N個屬性可用于鑒別2N個用戶。

定義2 訪問結(jié)構(gòu)。訪問結(jié)構(gòu)Tr是全集{p1,p2,…,pn}的一個非空子集,Tr?2{p1, p2,…, pn}{?}。Tr表示一個屬性判斷條件,在Tr中屬性集合稱作授權(quán)集,不在T中屬性集合稱作非授權(quán)集。

定義3 訪問結(jié)構(gòu)樹。用于描述加密文件的訪問結(jié)構(gòu),結(jié)構(gòu)樹每個葉節(jié)點(diǎn)表示一個屬性項(xiàng),每一個非葉子節(jié)點(diǎn)表示某個門關(guān)系,例如AND、OR等門限關(guān)系。

1.2 基于CP-ABE訪問機(jī)制的緩存問題

給定有限的加密文件集F,每個加密文件f∈F。假設(shè)緩存的加密文件的請求序列為Q=f1f2…fm,緩存的總?cè)萘繛镃,其狀態(tài)表示為S,假定對于任一個加密文件fi小于緩存容量。

max {fi}≤C

當(dāng)請求序列為Q=f1f2…fm時,S0表示為緩存的初始狀態(tài),Sk表示為K時刻緩存的狀態(tài),fk表示k時刻被訪問的文件,

(1)

其中:Dk表示的是被替換出的數(shù)據(jù)對象;Cf表示的是剩余的緩存內(nèi)的空間大小。當(dāng)出現(xiàn)式(1)中的第三種情況時,表示緩存空間已滿,這時就需要利用本文所提出的基于CP-ABE訪問策略的緩存替換算法進(jìn)行替換。以下是對本文算法的具體描述。

2 基于CP-ABE訪問機(jī)制的緩存替換策略

本文所提出的基于CP-ABE訪問機(jī)制的緩存替換算法——最小屬性價值算法(MAV),要對加密文件訪問策略中的屬性值進(jìn)行統(tǒng)計,進(jìn)而對文件屬性值價值進(jìn)行計算,在緩存替換中,替換文件屬性值價值最小的文件。

2.1 加密文件訪問策略中的屬性值統(tǒng)計

MAV算法要對緩存文件的訪問策略中的屬性值進(jìn)行統(tǒng)計。建立一張屬性表T,容量為C,Ate={a1,a2,…,aq}是表T中的屬性集合,屬性統(tǒng)計表T分為三列,分別記載:序號、屬性值、屬性值個數(shù)。表T中的屬性值的排列順序根據(jù)包含有該屬性值的文件的被訪問時間,按照最近使用的屬性值排在最前面的原則進(jìn)行排列。

假設(shè)現(xiàn)在緩存中存在A、B、C、D、E共5個文件,其訪問順序?yàn)锽、D、A、C、E,這5個文件的訪問策略中的屬性值分別為,A: 華師大、軟件學(xué)院、嵌入式、學(xué)生;B: 華師大、軟件學(xué)院、嵌入式、老師;C: 華師大、軟件學(xué)院、密碼學(xué)、學(xué)生;D: 華師大、教育學(xué)院、學(xué)前教育、學(xué)生;E:華師大、體育學(xué)院、健美操、學(xué)生。根據(jù)屬性值的訪問次數(shù)和屬性值的訪問頻率,以上五個文件的屬性值統(tǒng)計如表1所示。

表1 屬性值統(tǒng)計

當(dāng)緩存中有文件被替換出去時,被替換出去的文件的屬性值在表T中相應(yīng)的個數(shù)要減少,并且當(dāng)存在某個屬性的個數(shù)被減少為0時,將該屬性值從表T中刪除;當(dāng)緩存中有新的文件被替換進(jìn)來時,新文件的屬性值的個數(shù)在表T中要相應(yīng)增加,并且表T中屬性的排列順序要根據(jù)新的訪問時間進(jìn)行相應(yīng)的位置的變動。

在上面的例子中,若最后通過MAV算法將D文件替換出去,F文件被替換進(jìn)來,其中D文件的屬性值為:華師大、教育學(xué)院、學(xué)前教育、學(xué)生,F文件的屬性值為:華師大、軟件學(xué)院、海量所、老師根據(jù)上面的原則,此時屬性值統(tǒng)計表T發(fā)生相應(yīng)的變化,新的屬性值統(tǒng)計如表2所示。

表2 變化后的屬性值統(tǒng)計

2.2 文件屬性值價值計算

借鑒數(shù)據(jù)挖掘中常用的“文本相似度”的概念,計算加密文件的“屬性相似度”,同時考慮緩存文件的大小因素,計算文件屬性值價值(File Attribute Value, FAV),將屬性值價值作為緩存中文件替換的標(biāo)準(zhǔn)。本文采用余弦相似度的方法計算加密文件的屬性相似度,余弦相似度用向量空間中兩個向量夾角的余弦值作為衡量兩個個體間差異的大小,余弦值越接近1,就表明夾角越接近0°,也就是兩個向量越相似[7]。

(2)

(3)

得出的相似度接近1,表明文件A與表T具有較高的相似度。下面結(jié)合緩存文件的大小因素,描述計算文件屬性值價值的具體過程。

設(shè)FAVi為文件的屬性值價值,初始值設(shè)為0,Pi={p1,p2,…,pk}為緩存文件Fi的屬性值集合,Sizei表示文件Fi的大小,根據(jù)式(2),結(jié)合傳統(tǒng)的Size算法的策略,得到FAVi的計算公式如下:

(4)

緩存替換過程中,分別計算緩存中文件和即將被替換進(jìn)來的新文件的屬性值價值,替換FAVi值最小的文件。

3 仿真實(shí)驗(yàn)與分析

本章給出MAV算法與傳統(tǒng)經(jīng)典的LRU算法、Size算法、LFU算法在不同條件下的比較結(jié)果。

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

本次實(shí)驗(yàn)硬件使用的是Dell臺式機(jī),具體配置為:CPU Intel Core Duo i5主頻3.1 GHz;內(nèi)存4 GB;硬盤1 TB。

軟件環(huán)境采用的是:Windows 8操作系統(tǒng);網(wǎng)絡(luò)仿真軟件OPNET Modeler10。

本次實(shí)驗(yàn)主要使用網(wǎng)絡(luò)仿真軟件OPNET Modeler10進(jìn)行仿真模擬,利用C語言對MAV算法,以及傳統(tǒng)的LRU算法、Size算法、LFU算法進(jìn)行編寫。實(shí)驗(yàn)的數(shù)據(jù)來源于浙江電力局提供的相關(guān)數(shù)據(jù)集。在實(shí)驗(yàn)中,設(shè)置總共可以訪問的文件數(shù)目為1 000個,文件大小在1 MB～1 024 MB內(nèi)隨機(jī)選取,在測試中保證每種算法的總訪問文件的次數(shù)為345 686。

3.2 實(shí)驗(yàn)結(jié)果

為了進(jìn)行對比,本實(shí)驗(yàn)在相同的實(shí)驗(yàn)環(huán)境下，與文獻(xiàn)[9]中的傳統(tǒng)經(jīng)典的緩存替換算法LRU、LFU和Size的數(shù)據(jù)進(jìn)行對比。同時，對本文所提出的MAV算法進(jìn)行實(shí)驗(yàn)，分別計算其在不同緩存大小下的加密文件請求命中率和字節(jié)命中率，以及針對不同文件大小的加密文件請求命中率和字節(jié)命中率。本文設(shè)置的緩存大小為：1%、3%、5%、10%、20%、30%、40%、50%，設(shè)置的文件大小為：32 MB、64 MB、128 MB、256 MB、512 MB、1024 MB。

圖1為各種算法在不同緩存大小下的字節(jié)命中率。從圖1可以看出,當(dāng)緩存大小小于20%時,本文提出的MAV算法的字節(jié)命中率高于LRU算法和Size算法,略低于LFU算法;當(dāng)緩存大小大于20%以后,MAV算法的字節(jié)命中率和加密文件命中率都高于其他三種算法。

圖1 緩存大小對字節(jié)命中率的影響

圖2 緩存大小對加密文件命中率的影響

圖3 文件大小對字節(jié)命中率的影響

從圖2所示的各種算法在不同緩存大小下的加密文件命中率可看出：當(dāng)緩存大小小于16%時,MAV算法的加密文件命中率高于LRU算法和Size算法,略低于LFU算法;當(dāng)緩存大小大于16%以后,MAV算法的加密文件命中率都高于其他三種算法。

從圖3所示的各種算法在不同緩存文件大小下的字節(jié)命中率可看出：對于不同大小的加密文件,在字節(jié)命中率方面,MAV算法明顯高于LRU算法和LFU算法,對于小文件MAV算法的命中率略低于Size算法,但對于大文件MAV算法具有明顯的優(yōu)勢。

從圖4所示的各種算法在不同緩存文件大小下的加密文件命中率可看出：對于不同大小的加密文件,在加密文件命中率方面,MAV算法同樣明顯高于LRU和LFU算法,也同樣高于Size算法,這樣的優(yōu)勢對于大文件更加明顯。

圖4 文件大小對加密文件命中率的影響

4 結(jié)語

本文提出的緩存替換算法,分析了基于CP-ABE加密的文件的特點(diǎn),結(jié)合其訪問策略中的屬性值,充分考慮了文件的訪問頻率、訪問時間問題,建立了屬性值統(tǒng)計表,根據(jù)余弦相似度的計算方法計算文件屬性相似度,并且綜合Size算法中文件的大小因素,計算出文件的屬性值價值。在實(shí)驗(yàn)部分,分別考慮了在不同緩存大小下的加密文件命中率和字節(jié)命中率,以及在不同文件大小下的加密文件命中率和字節(jié)命中率。實(shí)驗(yàn)數(shù)據(jù)表明,針對基于CP-ABE加密的數(shù)據(jù),本文提出的MAV算法可以有效地提高緩存文件命中率和字節(jié)命中率。

本文所設(shè)計的緩存替換策略僅考慮了單個緩存的環(huán)境,今后的工作將集中在分布式緩存下加密數(shù)據(jù)的緩存策略的研究。

References)

[1] 劉磊, 熊小鵬. 最小駐留價值緩存替換算法[J]. 計算機(jī)應(yīng)用, 2013, 33(4): 1018-1022. (LIU L, XIONG X P. Least cache value replacement algorithm [J]. Journal of Computer Applications, 2013, 33(4): 1018-1022.)

[2] 秦秀磊, 張文博, 魏峻, 等.云計算環(huán)境下分布式緩存技術(shù)的現(xiàn)狀與挑戰(zhàn)[J]. 軟件學(xué)報, 2013, 24(1): 50-66. (QIN X L, ZHANG W B, WEI J, et al. Progress and challenges of distributed caching techniques in cloud computing [J]. Journal of Software, 2013, 24(1): 50-66.)

[3] 盧秉亮, 梅義博, 劉娜. 位置相關(guān)查詢中基于最小訪問代價的緩存替換方法[J]. 計算機(jī)應(yīng)用, 2011, 31(3): 690-693. (LU B L, MEI Y B, LIU N. Cache replacement method based on lowest access cost for location dependent query[J]. Journal of Computer Applications, 2011, 31(3): 690-693.)

[4] 肖敬偉, 趙永祥. 基于PageRank的緩存替換策略[J]. 信息技術(shù), 2016(6): 107-110. (XIAO J W, ZHAO Y X. Cache replacement strategy based on PageRank[J]. Information Technology, 2016(6): 107-110.)

[5] 石磊, 孟彩霞, 韓英杰. 基于預(yù)測的Web緩存替換策略[J]. 計算機(jī)應(yīng)用, 2007, 27(8): 1842-1845. (SHI L, MENG C X, HAN Y J. Web replacement policy based on prediction[J]. Journal of Computer Applications, 2007, 27(8): 1842-1845.)

[6] 程思嘉, 張昌宏, 潘帥卿, 等. 基于CP-ABE算法的云存儲數(shù)據(jù)訪問控制方案設(shè)計[J]. 信息網(wǎng)絡(luò)安全, 2016(2): 1-6. (CHENG S J, ZHANG C H, PAN S Q, et al. Design on data access control scheme for cloud storage based on CP-ABE algorithm[J]. Netinfo Security, 2016(2): 1-6.)

[7] 彭敏, 黃佳佳, 朱佳暉, 等. 基于頻繁項(xiàng)集的海量短文本聚類與主題抽取[J]. 計算機(jī)研究與發(fā)展, 2015, 52(9): 1941-1953. (PENG M, HUANG J J, ZHU J H, et al. Mass of short texts clustering and topic extraction based on frequent itemsets[J]. Journal of Computer Research and Development, 2015, 52(9): 1941-1953.)

[8] 肖敬偉.基于數(shù)據(jù)挖掘的緩存替換算法研究[D]. 北京: 北京交通大學(xué), 2015: 1-66. (XIAO J W. Cache replacement algorithms based on data mining[D]. Beijing: Beijing Jiaotong University, 2015: 1-66.)

[9] 陳勇. 基于P2P的內(nèi)容分發(fā)網(wǎng)絡(luò)及緩存替換算法研究[D]. 成都: 電子科技大學(xué), 2008: 1-79. (CHEN Y. Research on P2P-based content distribution network and cache replacement algorithm[D]. Chengdu: University of Electronic Science and Technology of China, 2008: 1-79.)

[10] GOMAA W H, FAHMY A A. A survey of text similarity approaches[J]. International Journal of Computer Applications, 2013, 68(13): 13-18.

[11] HARATY R A, ZEITOUNY J. Rule-based data mining cache replacement strategy[J]. International Journal of Data Warehousing amp; Mining, 2015, 9(1): 56-69.

[12] DAS S, AAMODT T M, DALLY W J. Reuse distance-based probabilistic cache replacement[J]. ACM Transactions on Architecture amp; Code Optimization, 2016, 12(4): 33.

[13] GAST N, VAN HOUDT B. Transient and steady-state regime of a family of list-based cache replacement algorithms[C]// SIGMETRICS 2015: Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. New York: ACM, 2015: 123-136.

[14] LEE M K, MICHAUD P, SIM J S, et al. A simple proof of optimality for the MIN cache replacement policy[J]. Information Processing Letters, 2015, 116(2): 168-170.

[15] LI L, CHEN X, JIANG H, et al. P-CP-ABE: parallelizing ciphertext-policy attribute-based encryption for clouds[C]// Proceedings of the 2016 17th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing. Piscataway, NJ: IEEE, 2016: 575-580.

[16] ZOU J, ZHANG Y. Research of the application of CP-ABE algorithm in ABAC model under cloud environment[J]. Journal of Computational Information Systems, 2015, 11(1): 261-268.

Cachereplacementstrategybasedonaccessmechanismofciphertextpolicyattributebasedencryption

CHEN Jian1, SHEN Xiaojun1, YAO Yiyang1, XING Yafei2, JU Xiaoming2*

(1.InformationandCommunicationBranch,ZhejiangElectricPowerCompany,StateGridCorporationofChina,HangzhouZhejiang310007,China;2.SchoolComputerScienceandSoftwareEngineering,EastChinaNormalUniversity,Shanghai200062,China)

In order to improve the performance of cache for encrypted data based on Ciphertext Policy Attribute Based Encryption (CP-ABE), an effective replacement algorithm named Minimum Attribute Value (MAV) algorithm was proposed.Combining the access mechanism of ciphertext in CP-ABE and counting the number of high frequency attribute values, the attribute similarity was calculated by using cosine similarity method and the table of high frequency attribute values; meanwhile, the attribute value of each cache file was calculated according to the attribute similarity and size of the encrypted file, then the file with the minimum attribute valuve was replaced. The experimental results prove that the MAV algorithm has better performance in increasing byte hit rate and file request hit rate than the algorithms of Least-Recently-Used (LRU), Least-Frequently-Used (LFU) and Size for encrypted data based on CP-ABE.

attribute policy; cache replacement policy; Ciphertext Policy Attribute Based Encryption (CP-ABE) algorithm; encrypted data; cosine similarity

2017- 04- 20;

2017- 06- 23。

國家電網(wǎng)科技項(xiàng)目(5211XT160008)。

陳建(1965—),男,福建福州人,教授級高級工程師,主要研究方向:信息安全; 沈?yàn)t軍(1972—),男,浙江紹興人,中級工程師,主要研究方向:信息系統(tǒng)管理; 姚一楊(1984—),男,浙江杭州人,高級工程師,碩士,主要研究方向:信息安全; 邢雅菲(1993—),女,山東淄博人,碩士研究生,主要研究方向:云計算分布式緩存; 琚小明(1967—),男,浙江衢州人,副教授,博士,CCF會員,主要研究方向:嵌入式系統(tǒng)軟件、計算機(jī)軟件、互聯(lián)網(wǎng)。

1001- 9081(2017)10- 2964- 04

10.11772/j.issn.1001- 9081.2017.10.2964

TP393

A

This work is partially supported by the National Grid Technology Project (5211XT160008).

CHENJian, born in 1965, senior engineer. His research interests include information security.

SHENXiaojun, born in 1972, engineer. His research include information system management.

YAOYiyang, born in 1984, M. S., senior engineer. His research interests include information security.

XINGYafei, born in 1993, M. S. candidate. Her research interests include cloud computing distributed cache.

JUXiaoming, born in 1967, Ph. D, associate professor. His research interests include embedded system software, computer software, Internet.