基于密文策略屬性基加密系統訪問機制的緩存替換策略

陳 建,沈瀟軍,姚一楊,邢雅菲,琚小明

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

基于密文策略屬性基加密系統訪問機制的緩存替換策略

陳 建1,沈瀟軍1,姚一楊1,邢雅菲2,琚小明2*

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

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

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

0 引言

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

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

1 基于CP-ABE訪問機制的緩存問題

1.1 CP-ABE屬性策略的研究基礎

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

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

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

定義3 訪問結構樹。用于描述加密文件的訪問結構,結構樹每個葉節點表示一個屬性項,每一個非葉子節點表示某個門關系,例如AND、OR等門限關系。

1.2 基于CP-ABE訪問機制的緩存問題

給定有限的加密文件集F,每個加密文件f∈F。假設緩存的加密文件的請求序列為Q=f1f2…fm,緩存的總容量為C,其狀態表示為S,假定對于任一個加密文件fi小于緩存容量。

max {fi}≤C

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

(1)

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

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

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

2.1 加密文件訪問策略中的屬性值統計

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

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

表1 屬性值統計

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

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

表2 變化后的屬性值統計

2.2 文件屬性值價值計算

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

(2)

(3)

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

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

(4)

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

3 仿真實驗與分析

本章給出MAV算法與傳統經典的LRU算法、Size算法、LFU算法在不同條件下的比較結果。

3.1 實驗環境

本次實驗硬件使用的是Dell臺式機,具體配置為:CPU Intel Core Duo i5主頻3.1 GHz;內存4 GB;硬盤1 TB。

軟件環境采用的是:Windows 8操作系統;網絡仿真軟件OPNET Modeler10。

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

3.2 實驗結果

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

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

圖1 緩存大小對字節命中率的影響

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

圖3 文件大小對字節命中率的影響

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

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

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

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

4 結語

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

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

References)

[1] 劉磊, 熊小鵬. 最小駐留價值緩存替換算法[J]. 計算機應用, 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] 秦秀磊, 張文博, 魏峻, 等.云計算環境下分布式緩存技術的現狀與挑戰[J]. 軟件學報, 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] 盧秉亮, 梅義博, 劉娜. 位置相關查詢中基于最小訪問代價的緩存替換方法[J]. 計算機應用, 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]. 信息技術, 2016(6): 107-110. (XIAO J W, ZHAO Y X. Cache replacement strategy based on PageRank[J]. Information Technology, 2016(6): 107-110.)

[5] 石磊, 孟彩霞, 韓英杰. 基于預測的Web緩存替換策略[J]. 計算機應用, 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算法的云存儲數據訪問控制方案設計[J]. 信息網絡安全, 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] 彭敏, 黃佳佳, 朱佳暉, 等. 基于頻繁項集的海量短文本聚類與主題抽取[J]. 計算機研究與發展, 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] 肖敬偉.基于數據挖掘的緩存替換算法研究[D]. 北京: 北京交通大學, 2015: 1-66. (XIAO J W. Cache replacement algorithms based on data mining[D]. Beijing: Beijing Jiaotong University, 2015: 1-66.)

[9] 陳勇. 基于P2P的內容分發網絡及緩存替換算法研究[D]. 成都: 電子科技大學, 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。

國家電網科技項目(5211XT160008)。

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

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.