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={p₁, p₂, …, p_n}为所有属性的集合, 则每个用户的属性Ati是P的一个非空子集, Ati⊆{p₁, p₂, …, p_n}, 那么N个属性可用于鉴别2N个用户。

定义2  访问结构。访问结构Tr是全集{p₁, p₂, …, p_n}的一个非空子集, Tr⊆2^{{p₁, p₂, …, pn}}\{∅}。Tr表示一个属性判断条件, 在Tr中属性集合称作授权集, 不在T中属性集合称作非授权集。

定义3  访问结构树。用于描述加密文件的访问结构, 结构树每个叶节点表示一个属性项, 每一个非叶子节点表示某个门关系, 例如AND、OR等门限关系。

1.2 基于CP-ABE访问机制的缓存问题

给定有限的加密文件集F, 每个加密文件f∈F。假设缓存的加密文件的请求序列为Q= f₁f₂…f_m, 缓存的总容量为C, 其状态表示为S, 假定对于任一个加密文件f_i小于缓存容量。

max {f_i}≤C

当请求序列为Q= f₁ f₂…f_m时, S₀表示为缓存的初始状态, S_k表示为K时刻缓存的状态, f_k表示k时刻被访问的文件,

$Sk=\left\{ \begin{align} & Sk-1,\quad \quad \quad \quad \quad \quad \quad fk\in Sk-1 \\ & Sk-1\cup \{fk\},\quad \quad \quad \quad fk\notin Sk-1,Cf\ge fk \\ & \{Sk-1-Dk\}\cup \{fk\},fk\notin Sk-1,Cf<fk \\ \end{align} \right.$

(1)

其中:D_k表示的是被替换出的数据对象;C_f表示的是剩余的缓存内的空间大小。当出现式(1) 中的第三种情况时, 表示缓存空间已满, 这时就需要利用本文所提出的基于CP-ABE访问策略的缓存替换算法进行替换。以下是对本文算法的具体描述。

2 基于CP-ABE访问机制的缓存替换策略

本文所提出的基于CP-ABE访问机制的缓存替换算法——最小属性价值算法(MAV), 要对加密文件访问策略中的属性值进行统计, 进而对文件属性值价值进行计算, 在缓存替换中, 替换文件属性值价值最小的文件。

2.1 加密文件访问策略中的属性值统计

MAV算法要对缓存文件的访问策略中的属性值进行统计。建立一张属性表T, 容量为C, Ate={a₁, a₂, …, a_q}是表T中的属性集合, 属性统计表T分为三列, 分别记载:序号、属性值、属性值个数。表T中的属性值的排列顺序根据包含有该属性值的文件的被访问时间, 按照最近使用的属性值排在最前面的原则进行排列。

假设现在缓存中存在A、B、C、D、E共5个文件, 其访问顺序为B、D、A、C、E, 这5个文件的访问策略中的属性值分别为, A: 华师大、软件学院、嵌入式、学生;B: 华师大、软件学院、嵌入式、老师;C: 华师大、软件学院、密码学、学生;D: 华师大、教育学院、学前教育、学生;E:华师大、体育学院、健美操、学生。根据属性值的访问次数和属性值的访问频率, 以上五个文件的属性值统计如表 1所示。

当缓存中有文件被替换出去时, 被替换出去的文件的属性值在表T中相应的个数要减少, 并且当存在某个属性的个数被减少为0时, 将该属性值从表T中删除;当缓存中有新的文件被替换进来时, 新文件的属性值的个数在表T中要相应增加, 并且表T中属性的排列顺序要根据新的访问时间进行相应的位置的变动。

在上面的例子中, 若最后通过MAV算法将D文件替换出去, F文件被替换进来, 其中D文件的属性值为:华师大、教育学院、学前教育、学生, F文件的属性值为:华师大、软件学院、海量所、老师根据上面的原则, 此时属性值统计表T发生相应的变化, 新的属性值统计如表 2所示。

2.2 文件属性值价值计算

借鉴数据挖掘中常用的“文本相似度”的概念, 计算加密文件的“属性相似度”, 同时考虑缓存文件的大小因素, 计算文件属性值价值(File Attribute Value, FAV), 将属性值价值作为缓存中文件替换的标准。本文采用余弦相似度的方法计算加密文件的属性相似度, 余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小, 余弦值越接近1, 就表明夹角越接近0°, 也就是两个向量越相似^[7]。

在属性表T中, 将表T看为一种文本, 表T中的属性值看为关键词, 将属性值的个数作为属性的权重, 从而得出属性频向量$\overrightarrow{X}$=(x₁, x₂, …, x_n), 其中, 每一个分量都对应属性表T中的一个属性a_i, 分量值x_i为属性a_i的个数;同理, 将单个加密文件看为一种文本, 加密文件访问策略中的属性值看为关键词, 计算属性值的个数作为属性的权重, 得出另一个属性频向量$\overrightarrow{Y}$=(y₁, y₂, …, y_m), 其中, 每个分量对应该文件访问策略中的一个属性值p_i, 分量值y_i同样为属性p_i的个数。这里要求向量$\overrightarrow{X}$和向量$\overrightarrow{Y}$中n=m, 但是在表T的属性集合Ate={a₁, a₂, …, a_q}和单个文件的属性集合P={p₁, p₂, …, p_k}中, q≠k且q≫k。为了进行相似度计算, 令n根据m的大小, 在表T中从序号1到q依次对应, 从而使得n=m。根据余弦相似度计算公式, 得出属性相似度计算公式为:

$\begin{matrix} Sim(X,Y)=\frac{\sum\limits_{i=1}^{n}{(xi\times yi)}}{\sqrt{\sum\limits_{i=1}^{n}{{{(xi)}^{2}}}}\times \sqrt{\sum\limits_{i=1}^{\text{m}}{{{(yi)}^{2}}}}}= \\ \frac{a· b}{\left\| a \right\|\times \left\| b \right\|} \\ \end{matrix}$

(2)

根据余弦相似度的性质, 计算出的属性相似度越接近1, 就表明夹角越接近0°, 也就是两个文本越相似。以2.1节例子中的文件A为例, 由表T得出向量$\overrightarrow{T}$=(5, 1, 1, 4), 由文件A得出向量$\overrightarrow{A}$=(5, 3, 2, 4), 计算$\overrightarrow{A}$=(5, 3, 2, 4) 与$\overrightarrow{T}$=(5, 1, 1, 4) 的属性相似度为:

$\begin{matrix} \cos (A)=\frac{5\times 5+3\times 1+2\times 1+4\times 4}{\sqrt{{{5}^{2}}+{{3}^{2}}+{{2}^{2}}+{{4}^{2}}}\times \sqrt{{{5}^{2}}+{{1}^{2}}+{{1}^{2}}+{{4}^{2}}}}= \\ \frac{46}{\sqrt{43}\times \sqrt{54}}\approx 0.955 \\ \end{matrix}$

(3)

得出的相似度接近1, 表明文件A与表T具有较高的相似度。下面结合缓存文件的大小因素, 描述计算文件属性值价值的具体过程。

设FAV_i为文件的属性值价值, 初始值设为0, P_i={p₁, p₂, …, p_k}为缓存文件F_i的属性值集合, Size_i表示文件F_i的大小, 根据式(2), 结合传统的Size算法的策略, 得到FAV_i的计算公式如下:

$FAVi=\frac{\sum\limits_{i=1}^{k}{(xi\times yi)}}{\sqrt{\sum\limits_{i=1}^{k}{{{(xi)}^{2}}}}\times \sqrt{\sum\limits_{i=1}^{k}{{{(yi)}^{2}}}}\times Sizei}=\frac{Sim(X,Y)}{Sizei}$

(4)

缓存替换过程中, 分别计算缓存中文件和即将被替换进来的新文件的属性值价值, 替换FAV_i值最小的文件。

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算法进行编写。实验的数据来源于浙江电力局提供的相关数据集。在实验中, 设置总共可以访问的文件数目为1000个, 文件大小在1 MB~1024 MB内随机选取, 在测试中保证每种算法的总访问文件的次数为345686。

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算法的字节命中率和加密文件命中率都高于其他三种算法。

从图 2所示的各种算法在不同缓存大小下的加密文件命中率可看出：当缓存大小小于16%时, MAV算法的加密文件命中率高于LRU算法和Size算法, 略低于LFU算法;当缓存大小大于16%以后, MAV算法的加密文件命中率都高于其他三种算法。

从图 3所示的各种算法在不同缓存文件大小下的字节命中率可看出：对于不同大小的加密文件, 在字节命中率方面, MAV算法明显高于LRU算法和LFU算法, 对于小文件MAV算法的命中率略低于Size算法, 但对于大文件MAV算法具有明显的优势。

从图 4所示的各种算法在不同缓存文件大小下的加密文件命中率可看出：对于不同大小的加密文件, 在加密文件命中率方面, MAV算法同样明显高于LRU和LFU算法, 也同样高于Size算法, 这样的优势对于大文件更加明显。

4 结语

本文提出的缓存替换算法, 分析了基于CP-ABE加密的文件的特点, 结合其访问策略中的属性值, 充分考虑了文件的访问频率、访问时间问题, 建立了属性值统计表, 根据余弦相似度的计算方法计算文件属性相似度, 并且综合Size算法中文件的大小因素, 计算出文件的属性值价值。在实验部分, 分别考虑了在不同缓存大小下的加密文件命中率和字节命中率, 以及在不同文件大小下的加密文件命中率和字节命中率。实验数据表明, 针对基于CP-ABE加密的数据, 本文提出的MAV算法可以有效地提高缓存文件命中率和字节命中率。

本文所设计的缓存替换策略仅考虑了单个缓存的环境, 今后的工作将集中在分布式缓存下加密数据的缓存策略的研究。