Test creat hello 0 hello 0 hello 0world ! Test creat Test delete:hello 0world ! 567 Test creat Test creat Test delete:JQK 789 Test delete:789 Test delete:567
var events = require("events"); var emitter=events.EventEmitter(); emitter.emit(eventName,data); .addListener(eventName,callback(data)) .on(eventName,callback(data)) .once(eventName,callback(data))
作者的成就:分布式,处理billion even trillion triples ,不用 relational tables and bitmap matrices,build on top of a memory cloud,首先说 随机访问的情况下 用硬盘储存三元组不够优良 ,就算有好的索引也会因为额外的join操作,作为主要的查询中 耗时,in-memory graph exploration instead of join operations for SPARQL processing ,作为对比 之前的系统 孤立使用自己划分的三元组 没有用已有的 造成了很大的中间额外开销,介绍如何降低join 数量 如何降低中间过程的大小,并且就算没有足够好的划分 也有优秀的性能,我们允许大范围的图分析
讲图分割问题 对于自然图 用大度的点 连接点来决定放置未知 以及使用 in out间接id 可以有效减少发送数据交流量
但是对于邻点少的来说用另一种方法更好 同一个点的in和out放在同一个机器上的方法
还用了
本地 谓词索引 sort all (predicate, node-id )
全局的 谓词索引 (predicate, hsubject-list i , object-list i i)
提供基本图操作
LoadNodes(predicate, direction): Return nodes that have an incoming or outgoing edge labeled as predicate. 使用全局谓词索引
LoadNeighborsOnMachine(node, direction, machine i): For a given node, return its incoming or outgoing neighbors that reside on machine i. 返回的是上面的间接id
SelectByPredicate(nid, predicate): From a given partial adjacency list specified by nid, return nodes that are labeled with the given predicate. Figure 4. LoadNodes(l2 , out) finds n2 on machine 1, and n3 on machine 2. LoadNeighborsOnMachine(n0 , in, 1) returns the partial adjacency list’s id in1 , and SelectByP redicate(in1 , l2 ) returns n2 .
Query Processing
先把 查询Q拆分为 q1 q2 q3…qn，然后让它们并行寻找 再最后再和并
单个q的匹配方式
For a triple pattern q, our goal is to find all its matches R(q). Let P de[notes] the predicate in q, V denote the variables in q, and B(V ) denote the binding of V . If V is a free variable (not bound), we also use B(V ) to denote all possible values V can take.
Heuristic 1. We expand a subgraph from its exploration point. We combine two subgraphs by connecting their exploration points.
Property 1. We expand a subgraph or combine two subgraphs through an edge. The two nodes on both ends of the edge are valid exploration points in the new graph.
Theorem 1. For a query graph G(V, E), the DP has time complexity O(n·|V |·|E|) where n is the number of connected subgraphs in G.
Theorem 2. Any acyclic query Q with query graph G is guaranteed to have an exploration plan.
Discussion. There are two cases we have not considered formally: i) G is cyclic, and ii) G contains a join on predicates.
RDF驱动用于储存索引和查询已经有一些年了,尤其是the Jena frame-work by HP Labs 显著收到欢迎,and Oracle also provides RDF support for semantic data integration in life sciences and enterprises [11, 29]. However, with the exception of the VLDB 2007 paper by Abadi et al. [1], none of the prior implementations could demonstrate convincing efficiency, failing to scale up towards large datasets and high load. [1] achieves good performance by grouping triples with the same property name into property tables, mapping these onto a column store, and creating materialized views for frequent joins
大多数可公开访问的RDF系统将RDF三元组映射到关系表（例如，RDFSuite [2, 32], Sesame [8, 28], Jena [23, 46], the C-Store-based RDF engine of [1], and also Oracle’s RDF MATCH implementation [11]）。有两种极端的方式做到这一点：
修剪主要基于估计的执行成本。也就是说，优化器为每个生成的计划调用成本模型，并修剪由廉价替代品支配的等价计划。这种修剪机制依赖于订单优化[35]来决定计划是否可以被另一个计划支配。由于优化器可以对所有三重排列使用索引，它可以按任意顺序生成元组，这使得合并连接非常有吸引力。因此，如果计划更昂贵，但产生可以在以后使用的有趣的顺序，则保留计划。注意，排序不仅通过索引扫描创建，而且还通过选择引起的功能依赖性创建，因此顺序优化组件是不重要的[35]。从种子开始，通过连接较小问题的最佳解决方案创建更大的计划。在此过程中，所有属性处理逻辑实现为对可用等价类的推理，而不是单个变量绑定。每个计划将为每个等价类产生至多一个绑定。这既简化了流水线断路器前面的隐式投影，并允许自适应传递连接条件的检测（即a = b ^ b = c⇒a = c）。
为此，我们预先计算数据图中的频繁路径，并为它们保留精确的连接统计信息。这里的频率指的是具有相同标签序列的路径。注意，我们对于链和星使用术语路径，在两种情况下结构是相似的。我们通过谓词p 1，…，p的序列来表征路径P. 。 。 ，在其遍历中看到。使用SPARQL语法，我们定义一个（链）路径P p 1 ,…,p n as P p 1 ,…,p n := select r 1 r n+1 where { (r 1 p 1 r 2 ).(r 2 p 2 r 3 ). . . . (r n p n r n+1 )}
FrequentPath(k) // Computes the k most frequent paths C 1 = {P p |p is a predicate in the database} sort C 1 , keep the k most frequent C = C 1 , i = 1 do C i+1 = ∅ for each p 0 ∈ C i , p predicate in the database if top k of C ∪ C i+1 ∪ {P p 0 p } includes all subpaths of p 0 p C i+1 = C i+1 ∪ {P p 0 p } if top k of C ∪ C i+1 ∪ {P pp 0 } includes all subpaths of pp 0 C i+1 = C i+1 ∪ {P pp 0 } C = C ∪ C i+1 , sort C, keep the k most frequent C i+1 = C i+1 ∩ C, i = i + 1 while C i 6 = ∅ return C
与Apriori设置不同，我们的RDFpath意义上的常见路径不一定包含频繁的子路径。考虑具有两个星形链路群集的图，其中所有端节点分别通过谓词（边缘标记）p 1和p 2连接到它们各自的星形中心。现在考虑在两个星形中心之间具有谓词p 3的单个边。在这种情况下，路径P p 3将不频繁，而路径P p 1，p 3，p 2将是频繁的。因此，我们不能简单地使用Apriori算法。
我们用只访问内存的本地代码实现Rowhammer攻击。攻击在 Sandy Bridge, Ivy Bridge,Haswell and Skylake, 不同的 DDR3 and DDR4 都成功
我们用纯js实现了rowhammer
背景知识
DRAM 介绍
rowhammer 介绍
CPU cache 介绍 以及别人没文档的也被反向工程了,o1表示双核cpu哪个cache来存 [o1,o2]表示4核CPU哪个cache来存,有几款CPU能自适应替换规则orz
Cache Attacks and Cache Eviction Practical attacks on cryptographic algorithms have been explored thoroughly [8,31]. There are two main types of cache attacks called Prime+Probe and Flush+Reload 小总结: 他们的不同缺点:慢,兼容性差,手工循环列,用了反向工程,用了刷cache的指令,低剔除率
27: Oren, Y., Kemerlis, V.P., Sethumadhavan, S., Keromytis, A.D.: The Spy in the Sandbox: Practical Cache Attacks in JavaScript and their Implications. In: CCS’15 (2015)
降低刷新率并对于真实攻击并不现实,已有的工作已经研究了Rowhammer的可攻击流行度, 发现85%DDR3被测试是易受到rowhammer 位翻转进攻的.只有Haswell test system and the G.Skill DIMMs in the Skylake test system在默认设置下是不易收到进攻的。因此我们的结论并不否定之前的预测,并且我们必须假设还有百万数量级的系统依旧脆弱.
第一步 4.2说了利用的可利用位翻转,在页表里有1/3的bit用于物理地址。在临近的2MB的范围里的一个页表中一个可以利用的bit翻转改变了一个物理地址。在我们的测试机器上我们已经发现了这样的位翻转。 第二步 利用脚本释放除了两个被先hammer了的以外的其它页,因此包含位翻转的页也被释放了,申请数组要求浏览器储存虚拟地址空间区域，并按照第一次访问的映射到物理地址上，攻击者决定的最大数组大小也会触发页表分配在时间攻击,在我们所有测试系统中数组大小为1MB，我们只是访问，因此为每个1MB数组申请了4K页，因此每个页表有两个用户页面，The probability to place a group of page tables in the targeted 2MB region is ≈ 1/3
第三步 再次利用脚本触发翻转，有可能发现它的内存映射改变, 有1/3的可能性地址映射到攻击者的页表中，如果成功，攻击者现在改变那个页表就会有完全的访问系统的物理地址。我们的想法在最新版linux系统和最新版ff被证实， It does not work in Google Chrome due to the immediate allocation of all physical memory for an allocated 1MB array after a single access.
The operating system allocates memory in large physical memory frames (often 2MB) for reasons of optimization. Page tables, kernel pages and user pages are not allocated in the same memory frame, unless the system is close to out-ofmemory (i.e., allocating the last few kilobytes of physical memory). Thus, the most efficient Rowhammer attack (double-sided hammering) would not possible if the operating system memory allocator was less aggressive in near-outof-memory situations. Preventing (amplified) single-sided hammering is more difficult, as hammering across the boundaries of a 2MB region is possible.
read-only shared code and data, shared libraries should not be shared over processes that run at different privilege levels or under different users.
refresh rate.
TRR
ECC
相关工作
The initial work by Kim et al. [20] and Seaborn’s [36] root exploit made the scientific community aware of the security implications of a Rowhammer attack. However, to date, there have been very few other publications, focusing on different aspects than our work. Barbara Aichinger [1] analyzed Rowhammer faults in server systems where the problem exists in spite of ECC memory. She remarks that it will be difficult to fix the problem in the millions or even billions of DDR3 DRAMs in server systems. Rahmati et al. [34] have shown that bit flips can be used to identify a system based on the unique and repeatable error pattern that occurs at a significantly increased refresh interval. Our paper is the first to examine how to perform Rowhammer attacks based on cache eviction.1 Our cache eviction techniques facilitated cache side-channel attacks on ARM CPUs [22]. Concurrent and independent work by Aweke et al. [4] has also demonstrated bit flips without clflush on a Sandy Bridge laptop. They focus on countermeasures, whereas we focus on attacking a wider range of architectures and environments.
In this paper, we presented Rowhammer.js, an implementation of the Rowhammer attack using fast cache eviction to trigger the Rowhammer bug with only regular memory accesses. It is the first work to investigate eviction strategies to defeat complex cache replacement policies. This does not only enable to trigger Rowhammer in JavaScript, it also benefits research on cache attacks as it allows to perform attacks on recent and unknown CPUs fast and reliably. Our fully automated attack runs in JavaScript through a remote website and can gain unrestricted access to systems. The attack technique is independent of CPU microarchitecture, programming language and execution environment. The majority of DDR3 modules are vulnerable and DDR4 modules can be vulnerable too. Thus, it is important to discover all Rowhammer attack vectors. Automated attacks through websites pose an enormous threat as they can be performed on millions of victim machines simultaneously.
code1a: mov (X), %eax // Read from address X mov (Y), %ebx // Read from address Y clflush (X) // Flush cache for address X clflush (Y) // Flush cache for address Y // mfence // In CMU paper, but not actually needed jmp code1a
两个变体: PNaCl(on open web. Runs pexe (LLVM bitcode): compiled to nexe by in-browser translator. No CLFLUSH?),NNaCl(in Chrome Web Store. Could use CLFLUSH.)
作者用的是NaCl :-)
利用 NaCl
安全命令序列:
1 2 3 4
andl $~31, %eax // Truncate address to 32 bits // and mask to be 32-byte-aligned. addq %r15, %rax // Add %r15, the sandbox base address. jmp *%rax // Indirect jump.
NaCl 沙箱模型:
防止跳到x86指令中间(意思是比如一条指令是 01 02 03 那么禁止跳到 02 开始的位置)
直接跳转目标只能用32位 对齐地址
位翻转导致部安全的方式
可能导致允许跳转到非32位对齐的地址
制作很多这个序列的备份 – 动态创代码(找寻位翻转 – 代码可读性)
利用改变寄存器号(13%的位翻转可利用,测试驱动开发)
NaCl 沙箱地址空间(1GB~4GB)
名
读写执性
大小
stack (initial thread)
read+write
available for mmap()
anything but exec
nexe rwdata segment
read+write
variable size
nexe rodata segment
read
variable size
dynamic code area
read+exec
~256MB
nexe code segment
read+exec
variable size
NaCl syscall trampolines
read+exec
64k
zero page
no access
64k
隐藏不安全代码的方法 in NaCl
已存在利用”跳到代码中间”的技术Existing technique for exploiting non-bundle-aligned jump:
20ea0: 48 b8 0f 05 eb 0c f4 f4 f4 f4
movabs $0xf4f4f4f40ceb050f, %rax
隐藏以后: 20ea2: 0f 05 syscall
20ea4: eb 0c jmp … // Jump to next hidden instr
20ea6: f4 hlt // Padding
NaCl 减轻rowhammer的方法
不允许 CLFLUSH
也许对Hide code并没办法
利用 Kernel
x86页表条目(PTE)是密集的可信的
他们控制物理内存访问权限，位翻转可以导致一个进程有权限访问另一个物理地址
利用的目标: 得到页表访问权->得到所有物理地址的访问权
尽量增大位翻转的有用性(用页表spray物理地址,先检测有用和可重复的位)
x86-64 Page Table Entries (PTEs)
Page table is a 4k page containing array of 512 PTEs