针对PathORAM的叉型访问方法
【技术领域】
[0001]本发明属于信息安全领域，涉及一种隐藏访存模式的硬件结构优化方法，具体涉及一种针对Path ORAM的叉型访问方法。
【背景技术】
[0002]基于路径的模式不可见存储器(Path Obliv1us RAM,Path ORAM)是一种可以隐藏访存模式的硬件结构。Path ORAM拥有高访存效率，算法简单等优点。由于其可行性，PathORAM被认为是最有可能用于安全处理器(Secure Processor)上的ORAM结构之一，其原型被实现在了FPGA以及ASIC代码上。但是Path ORAM还是存在一些问题，最大的问题就是访存代价过高。
[0003]在文献“MaasM, Love E, Stefanov E, et a 1.Phantom: Practical obliv1uscomputat1n in a secure processor.Acm Ccs,2013:311-324” 中，美国Martin Maas等人用FPGA实现了第一个基于Path ORAM的安全处理器Phantom，通过使用顶部缓存法(treetopcaching)以及一种树状结构来组织stash，从而降低了访存代价;但是，Phantom的每个数据块大小为4KB，和通常基于64B的块大小的ORAM设计相比，大大增加了其访存方面的代价。在文献“Fletcher C ff ,Ren L,Kwon A,et al.Freecursive oram: [nearly]free recurs1nand integrity verificat1n for posit1n-based obliv1us ram.2015.，，中，美国的Christopher W.Fletcher等人提出一种优化Hierarchical Path ORAM中对Posit1n Map访问的方法，该方法引入了PosMap Lookaside Buff er的结构来缓存PosMap的信息，同时，PosMap压缩技术也有效降低了访存代价;但是，该方法针对Path ORAM的访存代价还是很尚O
【发明内容】
[0004]为了克服上述现有技术的不足，本发明提供一种针对PathORAM的叉型访问方法，该方法是一种隐藏访存模式的硬件结构优化方法，能够达到在很小的硬件代价下降低PathORAM的访存代价，从而大大提尚系统整体性能。
[0005]为了行文方便，本文所有术语定义如下:
[0006]ORAM Tree(树状结构的模式不可见存储器):指外部存储memory的一种树形组织形式。外部memory被逻辑上组织成一个二叉树结构。每个节点叫做一个bucket (篮子)，其中包含Z个加密后的memory块(Z为一个大于3的整数)。每个叶节点都有一个标号，叫做label。每次memory访问都是对ORAM tree的一条从某个叶子节点(label-k)到根节点的路径进行访问(简称为path-k)，会将这条path上的所有memory块取入到处理器中(读阶段)，处理器读取出相应块后，会把数据写回到这条path(写阶段)。
[0007]ORAM Controller(模式不可见存储器的控制器):指processor(处理器)内部的控制ORAM工作的相关电路;包含三个部分:地址表(Posit1n Map)，隐蔽缓存(Stash)以及地址转换逻辑(Address Logic)。地址表是一个包含每个program地址的对应IabeI的查询表，隐蔽缓存是一个缓存结构，用来存放每次访存上来path中的数据块。地址转换逻辑用来计算每个program地址转换后对应path上每个块的地址。
[0008]Label Request Queue(LRQ，标签请求队列):表示在处理器中，大量program地址经过地址表转换为大量的label后，存放label的一个队列结构。Label Request Queue里的每个label请求都有一个counter，用来记录label进入queue的时间。
[0009]Address Request Queue(ARQ，地址请求队列):表示在处理器中，大量的program地址访存请求存放的一个队列结构。每个访存请求都有一个Ready标志位，用来解决数据冒险问题。
[0010]Merging Aware Cache(MAC，考虑路径合并策略的高速缓存):表示一个在地址转换逻辑之后的缓存结构，只用来缓存ORAM tree中特定层的数据。实现时，可以用传统cache结构，每个Oram tree中的memory块都可以根据块地址转换为特定的组数(set number)，每个set内部采用LRU替换策略。
[0011]本发明的原理是，首先对于任意一个末级缓存(LLC)发来的访存请求，将其插入到ARQ中，通过dependency(数据依赖性)判断以及在地址表的辅助下，将其转化为label值并插入到LRQ中，然后进行调度(scheduling)算法，将与前一个访存path重叠度最高的label提到queue的最前等待执行。每次LRQ最前的一个label会被传递给地址转换逻辑，转换为一系列逻辑地址(即在ORAM tree中与IabeI对应的path上所有块地址)后，首先判断每个地址是否在MAC中，如果在，将其对应数据从MAC中读取到隐蔽缓存中，如果不在就访问memory的相应位置。在隐蔽缓存处理完数据、末级缓存的请求被完成后，隐蔽缓存会重新写回数据到label对应的path，特定层的数据会被写回到MAC中，其余层的数据会被写回到memory中。由此实现在很小的硬件代价下降低Path ORAM的访存代价，能够大大提高系统整体性能。
[0012]本发明提供的技术方案是:
[0013]一种针对Path ORAM的叉型访问方法，包括:地址请求队列ARQ处理末级缓存请求LLC阶段、标签请求队列LRQ处理地址请求队列ARQ请求的阶段、地址转换逻辑处理标签请求队列LRQ请求的阶段，MAC处理地址转换逻辑请求阶段和内存处理MAC请求阶段，所述叉型访问方法通过隐藏访存模式的硬件结构优化，达到在很小的硬件代价下降低Path ORAM的访存代价，从而大大提尚系统整体性能;具体包括如下步骤:
[0014]A.在地址请求队列ARQ处理末级缓存LLC请求阶段，执行如下操作:
[0015]Al.末级缓存(LLC)请求设为{op,addr}，op表示读操作请求或写操作请求，addr表示末级缓存希望访问的逻辑地址；当末级缓存(LLC)发生一次miss(未命中)时，需要对内存进行访问；
[0016]A2.来自末级缓存LLC的请求需要对内存进行访问时，对于每个末级缓存LLC请求{op,addr}，根据地址请求队列ARQ中是否有和addr相同的请求{op’，addr}分别进行处理，当地址请求队列ARQ中没有和addr相同的请求时(addr不冲突)，直接将末级缓存LLC请求插入到地址请求队列ARQ;
[00?7] 当地址请求队列ARQ中有和addr相同的请求{op ’，addr}时，分为下列四种情况:
[0018]A21)当(op’，op) = (read,read)时，将{op,addr}当做普通请求处理即可；
[0019]A22)当(op，，op) = (read,write)时，{op,addr}被挂起等待{op，，addr}被处理完才能发射；[OO2O]A23)当(op’，op) = (write,read)时，直接返回数据给末级缓存；
[0021 ] A24)当(op，，op) = (write ,write)时，{op，,addr}会被取消；
[0022]A3.对于ARQ中的所有请求，通过查询地址表转换为对应的label，如果地址表中没有对应的label，通过层次化模式不可见存储器(hierarchy ORAM)中的相应机制转化为一个新的label ；
[0023]A4.将已被转换为label请求的ARQ请求传输至标签请求队列LRQ，直到标签请求队列LRQ已经充满数据请求，这时ARQ会等待LRQ有空位再传输，直到LRQ中没有无意义请求时停止传输；
[0024]B.在标签请求队列LRQ处理地址请求队列ARQ
文档序号 :
【 9826212 】
技术研发人员：孙广宇,张宪,张超,张玮其
技术所有人：北京大学
备 注：该技术已申请专利，仅供学习研究，如用于商业用途，请联系技术所有人。
声 明 ：此信息收集于网络，如果你是此专利的发明人不想本网站收录此信息请联系我们，我们会在第一时间删除
技术研发人员：孙广宇,张宪,张超,张玮其
技术所有人：北京大学
备 注：该技术已申请专利，仅供学习研究，如用于商业用途，请联系技术所有人。
声 明 ：此信息收集于网络，如果你是此专利的发明人不想本网站收录此信息请联系我们，我们会在第一时间删除