面向片外不可信内存的一种实用ORAM方案

濮传威 张功萱 周俊龙 付安民

(南京理工大学计算机科学与工程学院 南京 210094)

为了防止信息通过内存总线泄露，研究者们已经提出了安全处理器模型，例如XOM[1]，AEGIS[2]，SGX[3].安全处理器模型主要依靠数据加密确保系统安全性.

然而，单独使用数据加密已经不足以保护系统的安全性，因为每次内存访问仍然需要明文内存地址.攻击者仍然可以通过总线窥探访问的内存地址从而获得隐式信息[4]，如图1所示.因此，内存地址被访问的顺序(即内存访问模式，简称访问模式)可以暴露正在运行的程序和数据的大量敏感信息.例如，观察指令的执行顺序可以揭示程序执行的转移方式、循环次数以及访问某个内存地址的频率等.

图1 窥探安全处理器的总线获得隐式信息

鉴于此，有研究者们提出了不经意随机访问机(oblivious random access machine, ORAM)[5-6].ORAM是一种加密原语，它将每次对存储器的真实访问转换为一系列随机访问，从而隐藏真实访问.ORAM最初作为一种软件算法由Goldreich[5]提出，用于隐藏客户端对远程云存储的访问模式，该算法具有非常大的性能开销.在ORAM的最初提议之后，研究者们一直在努力寻找一种在加密方面更安全、更可行的ORAM方案.

ORAM的概念也被考虑在处理器—内存级别，以隐藏处理器对片外不可信内存的访问模式[7-10].处理器对内存进行访问时，集成在片上的ORAM控制器会生成对片外内存的虚拟访问，这些虚拟访问从随机内存地址获取加密的数据块，对数据进行操作后重新加密并写回内存，使攻击者无法发现真实访问地址或访问类型.因此，ORAM在完成访问时会产生巨大的延迟，使得ORAM对于大多数应用程序都是不切实际的，尤其是在硬件级别实现到处理器中时.

针对具有片外不可信内存的处理器系统，本文提出了一种可广泛实际应用的处理器—内存级的ORAM方案——分组ORAM(group ORAM).该方案在保证安全性的同时降低性能开销.与现有技术相比，其性能开销不会随着内存容量增加而增加，并与应用程序大小无关，因此对于大型应用程序具有高度可扩展性，从而降低了成本，并使ORAM概念实用化.同时，分组ORAM引入了参数化设计，可以调整参数以满足对性能、安全性的不同需求.

ORAM的概念最初由Goldreich[5]提出，以防止在访问远程不可信云存储设备时通过访问模式泄露信息.在现阶段ORAM是隐藏用户访问模式的主要方法.当用户访问存储在服务器的数据时，他们会同时访问有效数据和虚拟数据，这将混淆用户访问的目标数据，从而隐藏用户的访问行为[11-12].然而，ORAM在提高安全性的同时，会显著增加存储空间的负担和交互数据量，例如：为了混淆目标数据块，需要添加部分虚拟数据块，并且需要对不同数据块进行多次访问.如何在保证用户访问行为安全性的前提下提高ORAM的访问效率是一个挑战性问题.

另一种减少性能开销的方案是Goldreich等人[6]提出的分层ORAM(hierarchical ORAM).该方案将数据块组织成层次结构.需要lbN层来存储N个数据块.第i层包含2i个桶，每个桶又包含lbN个数据槽用于存储数据.每个层级中的数据块使用随机选择的散列函数存储在相应的桶中.对于每次数据访问，首先扫描2个顶部的桶，在其他每个较低层级上，只扫描1个桶(若数据未找到，则扫描该层级上由散列函数指定的桶；
若数据已找到，则随机扫描该层级上的1个桶).最后将找到的数据写入第1层的桶内.该方案对于每次数据访问的平均开销为O(lb4N)，最坏情况下为O(Nlb3N).

分层ORAM方案由于客户端存储量小且层次结构中每个较高级别的数据块数量呈指数增长，因此随着层次结构中每个新层级的添加，数据打乱重组的开销会显著增加.这限制了分层ORAM的可伸缩性和性能.

实施和管理多个ORAM及其本地缓存的开销是很大的.针对这个问题，Shi等人[15]对分层ORAM进行了改进，进一步提出了Path ORAM[16]，它以二叉树的形式存储数据.每个叶子节点代表1条路径，每个数据映射到1个叶子节点即1条路径.数据可以存储在该路径上的任意节点之中.使用位置图映射数据块所在路径；
并用缓冲区暂时存放访问的数据块.对于每次数据访问，Path ORAM找到该数据块所在的路径，并读取该路径上所有数据块，然后将它们解密后缓存到缓冲区中，再将请求数据块返回给处理器以进行读取或更新.然后将请求的数据块随机映射到新的路径上.Path ORAM对于每次数据访问在最好和最坏情况下的开销是相同的，即O(lbN).

基于Path ORAM算法，研究者们提出了多种Path ORAM原型系统(PHANTOM[7],Tiny ORAM[8],Secure Dimm[9],D-ORAM[10],Freecursive[17],ASCEND[18])，旨在实际环境中评估该算法的实用性.表1给出了现有ORAM原型系统的归纳.

表1 现有ORAM原型的归纳

尽管现有设计使ORAM实现成为可能，但它们的性能开销仍然很大.在第2节将给出一种分组ORAM方案，它在最佳和最坏情况下都具有O(1)的性能开销，即性能开销与应用程序大小无关，这使得它在处理器级系统设计上具有高度可扩展性.并且针对不同平台对安全性以及性能的要求，可以进行灵活配置.

2.1 分组ORAM方案设计

图2给出了带有分组ORAM的处理器系统的抽象视图.分组ORAM与处理器位于同一芯片上并被视为可信，而内存位于片外并被视为不可信，攻击者可以观察到被访问的数据及其地址.

图2 使用分组ORAM的处理器系统的抽象视图

图3 分组ORAM体系结构

处理器在每次Cache未命中时通过分组ORAM访问片外内存.为了访问数据块，处理器指定其逻辑地址LA要执行的操作op(读/写)和要写入的数据data(如果操作是写入).分组ORAM将内存访问请求的逻辑地址转换为随机物理地址访问序列{PA1，PA2，…}.

分组ORAM所需的应用程序的逻辑存储空间由2部分组成：应用程序空间(application space)和虚拟空间(dummy space).假设应用程序大小为N个数据块,虚拟空间为D个数据块，则对于该应用程序，分组ORAM所需的总内存空间为N+D.虚拟空间仅对分组ORAM可见，而应用程序空间对处理器和分组ORAM均可见.类似地，包含应用程序数据的数据块称为真实块(true block)，包含虚拟数据的数据块称为虚拟块(dummy block).

与其他现有方案类似，分组ORAM方案将执行1组任务以隐藏访问模式：选择1组数据块，解密该组数据块(将其中真实访问的数据块返回给处理器)，将该组数据块与ORAM缓存中的块进行随机排列，再将其重新加密，并写入内存.这组基本任务统称为ORAM操作.ORAM操作将真实内存访问转换为一系列虚拟访问以覆盖真实访问从而隐藏访问模式.

2.2 分组ORAM结构

图3示出分组ORAM的体系结构.包括位置图(position map)、组管理单元(group management unit, GMU)、加密单元(Enc-pipe)、解密单元(Dec-pipe)、随机数生成器(random number generator, RNG)以及2个特殊缓冲区，数据缓存缓冲区(cache buffer, CBuffer)和组地址缓冲区(group address buffer, GAB).除了这些组件之外，还有1个读缓冲区(read buffer, RBuffer)和1个写缓冲区(write buffer, WBuffer)来保存内存读取和写入操作的数据.

位置图：提供每个逻辑数据块的当前物理地址.由于位置图的目的是映射每个数据块的当前位置，因此只要数据块的位置改变，该表就会更新.

CBuffer：暂时存放从内存读取的真实数据块，并且在对读取的数据块进行打乱重组时起关键作用.

GMU：保存每个数据块对应的组，若分组ORAM需要从片外内存访问某个数据块，则在GMU中找到该数据块对应的组，位置图将给出该组数据块物理地址，并将其发送到GAB.

GAB：保留当前操作的1组数据块的片外内存地址.因此，GAB的大小与组大小相同.

加/解密单元(encryption/decryption pipelines)：为了保护数据机密性，每个数据块在被发送到片外内存之前都进行了加密.当从片外内存获取数据块时，需要将其解密.

RNG：在ORAM操作过程中，有6种类型的随机值r1～r6需要动态生成.

r1：位数为lb(N+D)(单位为b)，用于初始化GMU，从而为每个数据块随机构建相应的组.

r2：位数为lbG(单位为b)，用于在块置换期间为将要移动到WBuffer中的块选择新位置.其中G是组大小.每个ORAM操作总共需要G个不同的r2值.

r3：位数为lbC(单位为b)，用于选择CBuffer中的位置以缓存从内存读取的真实数据块，其中C为CBuffer大小.每个ORAM操作都需要G个r3值.

r4：用于生成需要放入WBuffer的虚拟块.

r5：位数为lbG(单位为b)，用于选择GAB中的位置，以放置数据块的物理地址PA.

r6：用于在重新加密相同明文数据块.

2.3 分组ORAM算法

在分组ORAM设计中，任何时候，真实数据块都位于片上CBuffer或片外内存中的某个位置.在对数据块进行访问时，如果块位于CBuffer，则不需要进一步的ORAM操作；
否则，将执行ORAM操作从片外内存中获取请求的块.

初始化时，CBuffer滞空，位置图存储每个数据块的当前位置.GMU为每个数据块构建其对应的组.图4(a)为1个简单的GMU存储示例，每个数据块都有其对应的组(在这个示例中，组大小G=3).并且每个数据块与组内其他数据块的关系可以用有向图表示，如图4(b)所示.以数据块A为例，数据块C和D被分配在该组内，在访问数据块A时，数据块A,C,D将形成一小簇数据块一同被ORAM控制器访问.为了隐藏访问模式，在数据块A被访问后，ORAM控制器将该组数据块在WBuffer内进行随机排列并写入片外内存，同时更新位置图以及GMU内数据块之间的关系.

为了从片外内存访问数据块，处理器将请求access(A,op,D)发送到分组ORAM控制器，其中数据块的逻辑地址是LA，op是读或写操作，如果是写操作，则D是要写入的数据.分组ORAM控制器遵循算法1中定义的数据访问协议oram_access，以隐藏对片外内存的真实访问.

图4 GMU存储示例

对于处理器的1次访问请求，ORAM控制器首先查找位置图以确定数据块的位置.如果块在片上，则在CBuffer上执行访问——如果是读操作，则将请求的数据发送给处理器进行读取，否则使用新数据更新缓冲区中的块.但是，如果块位于片外内存中，则执行ORAM操作，具体操作步骤由算法1给出.

算法1.oram_access:用于数据访问的分组ORAM协议.

输入：处理器请求(A，op，D)、位置图、组管理单元GMU、组大小G；

输出：执行对所请求的数据块的操作op.

① 在位置图中查找数据块A所在位置;

② if 数据块A在片上 then

③//片上访问

④ ifop==读操作 then

⑤ 在CBuffer内查找数据块A并将其返回给处理器;

⑥ else

⑦ 在CBuffer内查找数据块A并将其更新为D;

⑧ end if

⑨ goto end

⑩ else

3.1 安全性分析

由于数据块之间形成关系图保持不变，并且每次对1组数据块访问后，都将这组数据块与ORAM缓存中的块一同随机排列，所以每个数据块可以在整个关系图中以相同的概率出现在任意位置.因此，在整个内存空间的分配中，分组ORAM均匀随机地将数据块的逻辑地址映射到物理地址.此外，每个数据块在内存中都以密文的方式存储，并且数据块在被处理器访问后都需进行重新加密.因此攻击者在数据总线上窥探时不能得到任何显示信息.

为了访问某个数据块，分组ORAM首先找到其所在的组，并将该组数据块一并进行访问.这组数据块具有以下几个性质：1)内存空间中的任意数据块都以相同的概率可能出现在该组内；
2)组内数据块之间并无关联；
3)组内数据块以随机顺序被访问.因此，攻击者在窥探地址总线时无法知道请求块的真实位置.此外，组内的真实数据块在被访问后将以随机位置保存在CBuffer中，并且这些位置原有的数据块与虚拟数据块将以随机位置写回内存.这意味着，如果处理器再次请求相同的块，它将直接从CBuffer中读取，除非在访问该数据块时，该数据块已经被其他真实数据块替换并写回内存.

给定N个数据块的应用空间和D个数据块的虚拟空间，组大小为G.假设y是处理器请求内存的访问序列，其中包含m个请求块.对于y=(a1,a2,…,am)，分组ORAM生成实际访问序列：

z=(G1,G2,…,Gm),

(1)

其中Gi表示数据块ai对应的组，每个组中包含G个需实际访问的数据块.

在数据块ai被访问后，它将暂时存放于CBuffer中，由于它在CBuffer中的位置是随机的，它被其他后续访问的数据块替换的顺序也是随机的，并且被替换后与组内其他数据块进行随机排列，形成新的组Gj，因此数据块ai下一次被访问时所在组的可能性的总数为

(2)

假设数据块ai下一次被访问时所在的组为Gj，Gj被选择的概率为

(3)

并且在组内，每个块都以概率1/G独立映射，利用贝叶斯原理，可以得到：对于访问序列y，分组ORAM根据y形成的2次实际访问序列z=z′的概率为

(4)

这个概率非常小，以至于实际访问序列z与z′在计算上无法区分，也就是说，对于某个访问序列y，攻击者几乎不可能观察到2次相同的实际访问序列.因此，攻击者无法知道真正的访问模式y.

3.2 开销分析

如前所述，现有ORAM方案面临的一个难题就是开销.在保证安全性的同时，这里对分组ORAM在内存带宽使用、访问延迟和内存空间消耗3个方面产生的开销进行分析.

内存带宽使用：从算法1可以看出，对于每次真实访问，分组ORAM从片外内存读取G个数据块，然后写入相同数量的数据块，导致每次真实访问总共使用2G块带宽.由于它是1个常数，并且作为参数可以设置，所以无论片外内存容量(或应用程序数据块总数)多大，内存带宽使用开销均为O(1).

访问延迟：对于每次真实访问，分组ORAM仅访问恒定的G个数据块，同时位置图以及GMU更新也都只针对常数量的数据块.因此，分组ORAM算法的延迟开销也为O(1).

由于内存带宽使用以及访问延迟带来的开销都为O(1)，因此，分组ORAM的性能与应用程序或片外内存的大小无关.然而，片外内存的大小影响了位置图以及GMU的大小.

内存空间消耗：像大多数现有的ORAM方案一样，分组ORAM需要消耗额外的内存空间用于虚拟数据块.理想情况下，虚拟空间越大块位置越不可预测.但是，虚拟空间太大会导致片外和片上的大量存储消耗.本文尝试减少虚拟空间，同时为每次内存访问实现尽可能高的随机性，如下所示.

由于分组ORAM中可以使用的不同组的总数为S，如式(2)所示，因此，分组ORAM具有足够大的块空间供数据块打乱重组，并提供比其他现有ORAM方案更高的随机化能力，例如数据块只能打乱重组到N条路径上的Path ORAM.

给定组大小G，1个组包含1个虚拟数据块的概率为P1=D/(N+D)，包含2个虚拟数据块的概率为P2=(D/(N+D))2，包含k个虚拟数据块的概率为Pk=(D/(N+D))k，其中k

如2.1节所述，分组ORAM使用CBuffer和WBuffer将数据块随机打乱重组写回内存，并且对于随机性，参与ORAM操作的虚拟块具有重要作用.

为了实现每个组中虚拟数据块数量的随机性，组中具有不同数量虚拟块的概率应尽可能接近.也就是说，概率比例r=Pi/Pi+1=(N+D)/D应尽可能小.该比例随着虚拟空间D的增加而减小，但存在1个肘点，如图5中的r曲线所示.肘点为最佳(最小)虚拟空间提供了良好的折中方案.

给定r曲线，要找到肘点，首先创建1条连接曲线2个端点的直线.肘点则位于从该直线到曲线形成最长直角距离的位置，如图5所示：

图5 r值与虚拟空间的关系

r曲线可以写成:

(5)

其中y1表示比例，x表示虚拟空间大小，N作为常数表示应用程序数据空间大小.

2个端点可以近似为(0,N)，(N,0)，它们之间的连线可以表示为

y2=-x+N.

(6)

由于r曲线的导数为y′=-N/x2，其中N>0，x2>0，所以y′<0.则r曲线单调递减.在r曲线上任意一点的切线，都与该点的曲率半径相垂直，而斜率相等的2条直线相互平行.因此，在r曲线y1上找一点，如果该点的切线的斜率与直线y2的斜率相等，那么该点的曲率半径垂直于直线y2，因此，该点就是所求的肘点.

(7)

将式(7)代入式(5)，得

(8)

(9)

对于给定的应用程序，使用处理器模拟工具Simplescalar[19]对其在处理器上的执行进行模拟，从中获得处理器的内存访问序列(Las)，分组ORAM使用Verilog HDL实现，并使用Xilinx vivado对Xilinx xc7vx330t FPGA平台进行仿真和综合.通过Xilinx仿真，可以得到分组ORAM输出的实际访问序列(PAs)，然后使用NIST[20]测试套件检测内存总线上地址访问的随机性.

在实验中，将内存块大小B设置为128 b，内存块地址大小设置为18 b(N+D=218).加密算法选择国密算法SM2[21]进行加密和解密，SM2是基于基本椭圆曲线(ECC)密码的公钥密码算法标准，其安全强度比RSA高，且运算速度快于RSA.同时采用与文献[8]中使用的片外内存相同的模型，并使用线性反馈移位寄存器(LFSR)进行随机数生成.

下面将首先评估分组ORAM的性能开销，然后讨论生成的访问序列的随机性.

4.1 性能评估

在实验中，研究了配置不同组大小和CBuffer大小时的性能开销.对于每种配置都执行Mibench基准测试程序组[22]的子集.对于每个基准测试，获得了没有分组ORAM的处理器系统以及集成了分组ORAM的处理器系统的执行时间.性能开销用执行速度降低μ来衡量，即使用分组ORAM时的执行时间与不使用分组ORAM时的执行时间之比，μ值越高说明执行速度的降低越明显.

如2.3节所述，如果在CBuffer中发现请求的数据块，分组ORAM不会执行片外内存访问.因此，除了数据打乱重组，CBuffer的大小C影响应用程序的总体执行时间.为了探究这种影响，测试了不同CBuffer大小的执行性能.从图6可以观察到，对于给定的组大小和CBuffer大小，执行时间之比μ都不同，具有良好局部性或较小工作数据集的基准测试程序(如CRC32)会产生较少的内存访问，因此它们的性能不会受到ORAM的太大影响.但对于一些基准测试程序，如Rijndael，执行速度会大幅降低.其次，执行各种基准测试程序时，对于不同CBuffer大小，μ值都有所变化，其中组大小G固定为16个数据块.可以观察到，每当CBuffer大小增加1倍，μ值会随之降低，当CBuffer大小较大时，μ值降低更明显.当CBuffer大小从256块增加到512块时，μ值降低了23.6%.

图6 当分组ORAM配置不同CBuffer大小时执行时间之比

决定性能开销的另一主要因素是组大小G.组大小与ORAM操作的延迟成正比.因此，在评估中纳入了分组ORAM组大小.图7示出给定CBuffer大小C=256的条件下，随着组大小的变化，执行时间之比μ的变化.从图7可以看出，当组大小增加时，μ值随之增加，即执行性能下降.这一趋势再次证实了预期的结果，即增加组大小会增加每个基准测试程序的完成时间.然而，由于处理器缓存中的高命中率，具有良好数据局部性或较小工作集的应用程序受到的影响相对较小.

图7 当分组ORAM配置不同组大小时执行时间之比

图8 当分组ORAM配置不同CBuffer大小时访问序列随机性变化

从图7还可以观察到，当组大小G从16增加到32时，执行时间之比μ会大幅增加，这意味着ORAM访问效率大幅下降，在4.3节将对最佳组大小G的选择进行分析.

4.2 安全性评估

分组ORAM生成的实际访问序列的随机性同时受组大小和CBuffer大小的影响.在执行每个基准测试程序期间，通过配置不同的组大小G和CBuffer大小C，获得了分组ORAM生成的内存访问序列.每个访问序列中的随机性都是通过NIST随机性测试套件评估的.对于每个内存访问序列，执行NIST测试套件中的所有测试，从而获得该访问序列的平均随机性通过率.更高的通过率意味着序列的随机性更高.

图8示出在给定组大小G为16个块时，CBuffer大小C如何影响生成的访问序列的随机性.同样，在给定CBuffer大小为256块时，图9显示了组大小G如何影响生成的访问序列的随机性.从图8可以看出，随机性与组大小和CBuffer大小成正比.这是因为增加组大小会在每次ORAM操作中打乱重组更多数据块，而增加CBuffer大小会提供更多的片上数据打乱重组空间.

从图9还可以发现，组大小G从16增加到32时，随机性通过率的变化并不明显.这意味着当组大小达到16时，安全性已经到达瓶颈，再增加组大小只会造成性能大幅下降，如4.1节所述.

图9 当分组ORAM配置不同组大小时访问序列随机性变化

4.3 比 较

下面，将分组ORAM与目前最先进的设计方案Tiny ORAM[8]进行比较.表2示出两者在FPGA资源消耗方面的开销——查找表(LUT)、触发器(FF)和块RAM(BRAM)数量.表3示出两者在每次内存访问时操作效率方面的比较.

表2 2种方案在FPGA资源消耗方面的比较

表3 2种方案在1次内存访问时操作效率方面的比较

从表2可以看出，分组ORAM消耗较少的为FF，LUT和BRAM相对较多.而从表3可以看出，对于每次内存访问，分组ORAM需要0.29～0.34 μs.与Tiny ORAM相比，延迟降低了75.7%～79.3%.

本文提出了一种ORAM方案——分组ORAM，它将真实内存访问隐藏在对一小簇内存地址的虚拟访问中，从而达到隐藏内存访问模式的目的.该方案使用缓冲区来解耦读取和写入之间的块，从而使每个组不相关.此外，该方案引入了参数化设计，可以调整参数以满足不同平台对性能、安全性的需求.通过执行Mibench基准测试程序来评估该方案的性能，并使用NIST测试生成的片外内存访问序列的随机性评估该方案的安全性.实验结果表明，相较之前的工作，分组ORAM方案能显著减少性能开销.同时，针对组大小为8～32个数据块和CBuffer大小为64～512个数据块的不同配置，其生成的内存访问序列随机性测试通过率达到94.6%～98.5%.与现有方案相比，分组ORAM在性能、安全性和内存消耗方面的表现都有所提升.

猜你喜欢随机性内存应用程序删除Win10中自带的应用程序电脑报(2019年12期)2019-09-10“春夏秋冬”的内存当代陕西(2019年13期)2019-08-20谷歌禁止加密货币应用程序中国计算机报(2018年30期)2018-11-12浅析电网规划中的模糊可靠性评估方法中国科技纵横(2016年20期)2016-12-28考虑负荷与分布式电源随机性的配电网无功优化电测与仪表(2016年12期)2016-04-11适用于随机性电源即插即用的模块化储能电池柜设计通信电源技术(2016年5期)2016-03-22内存搭配DDR4、DDR3L还是DDR3？电脑爱好者(2015年21期)2015-09-10基于内存的地理信息访问技术测绘科学与工程(2014年5期)2014-02-27三星电子将开设应用程序下载商店计算机世界(2009年34期)2009-11-17微软软件商店开始接受应用程序计算机世界(2009年29期)2009-08-14

相关热词搜索：不可信 面向 内存