贡献

  • 提供了系统分类的RDF存储管理器实现
  • 容易检测到特定RDF存储管理器实现之间的差异
  • 通过多进程环境获取有关有效进程的属性。

Single(T,I,Q,S,J,C,D,F)

Table

  • vertical
  • property
  • horizontal

Indexx structure

  • 6-independent
  • GSPO-PGPS
  • matrix

Query type

  • SPARQL
  • original

String translation method

  • URI
  • literal
  • long
  • none

Join optimization method

  • RDBMS-based
  • column-strore-based
  • conventional ordering
  • pruning
  • none

Cache type

  • materialized-path-index
  • reified-statement
  • none

Dabase engine type

  • RDB
  • custom

inference Feature type

  • TBox 本体推断
  • ABox 断言推断
  • no

Multiple(D,Q,S,A)

Data distribution method

  • hash
  • data-source
  • none

Query process distribution method type

  • data-parallel
  • data-replication
  • none

Stream process

  • pipeline
  • none

sharing Architecture

  • memory
  • disk
  • nothing
name T I Q S J C D F D Q S A
3store v S U R R T n n n
4store v S U o R h p n
Virtuoso v G S Ulo R R TA n n n
RDF-3X v 6 S Ul o R n n n
Hexastore v 6 o Ul n n n n
Apache Jena p S Ulo R r R n n n
SW-store h Uo c m c n n n
BitMat v m S Ul p c p
AllegroGraph S c h p m
Haddop/HBase h c p m
wukong v ??? S Ul c+? ? R? ? dh? p p m

dgraph engine for web scale rdf data

ABSTRACT

现有的对于网络范围的RDF数据现有依然不是高效的,内部存储不用bitmap,other operations,

INTRODUCTION

挑战:可扩展性(急切)和普遍性,需要分布式,现有依然三元组,join巨大中间结果,过大的开销 通常指数级 ,现有不支持更有意义的查询 仅仅对SPARQL优化

作者的成就:分布式,处理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 数量 如何降低中间过程的大小,并且就算没有足够好的划分 也有优秀的性能,我们允许大范围的图分析

  1. 新的基于图表的管理RDF数据 ,有对于RDf 高效基于图查询 和 图分析 的可能性
  2. 新的查询规范(相对于SPARQL)有效的提高性能 减少总监结果 和提高系统可扩展性
  3. 新的价值模型 新的基数估计基数 分布式查询生成的优化算法 ,这些成果提供 在web 范围 RDF数据上 出色的性能

Section 2 join操作 和 图探索 的区别. Section 3 Trinity.RDF 系统的架构. Section 4 how we model RDF data as native graphs. Section 5 describes SPARQL query processing techniques. Section 6 shows experimental results. We conclude in Section 8.

Join vs. Graph Exploration

RDF and SPARQL 的介绍 和 缺点(join 耗费高 中间无用结果大)

图探索 介绍方法 并说需要更高效的储存方式来适应这种方法 用native graph 会把原来的每次 读入O(log N)的时间复杂度降低为O(1) 需要搜索的顺序优化来

System Architecture

就是图储存,并且完全存在内存里 (因为是分布式的所以才可以储存这么多)

架构client,proxy,string server,trinity machine [看来陈榕老师就是按照这样的思路改的代码

Data Modeling

(node-id, in-adjacency-list, out-adjacency-listi)

讲图分割问题 对于自然图 用大度的点 连接点来决定放置未知 以及使用 in out间接id 可以有效减少发送数据交流量

但是对于邻点少的来说用另一种方法更好 同一个点的in和out放在同一个机器上的方法

还用了

  • 本地 谓词索引 sort all (predicate, node-id )
  • 全局的 谓词索引 (predicate, hsubject-list i , object-list i i)

提供基本图操作

  1. LoadNodes(predicate, direction): Return nodes that have an incoming or outgoing edge labeled as predicate. 使用全局谓词索引
  2. LoadNeighborsOnMachine(node, direction, machine i): For a given node, return its incoming or outgoing neighbors that reside on machine i. 返回的是上面的间接id
  3. 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.

从 S 去找 O ,写作q→

从 O 去找 S ,写作q←

分为两个阶段

src

用LoadNodes(本机)找到基于 所有可能predicate 的所有可能的src

对于所有可能src 在所有机器LoadNeighborsOnMachine(有远端操作)找nid_i 把结果M再发给所有机器

tgt

对于收到的结果M 的每一个(src,nid)

找所有的可能的predicate

用 SelectByPredicate(本机) 交 所有可能的tgt 得到R

方案是 合并相邻 的操作来减少中间过程的损耗

然后讲优化 也就是顺序优化

注意到用了合并以后 前面j个操作 只要集合相同 那么结果与前面j个的内部顺序无关

我们使用 启发式算法

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.

Exploiting-The-DRAM-Rowhammer-Bug-To-Gain-Kernel-Privileges.pdf阅读整理

它是什么

重复行激活可导致相邻的行位翻转

翻转导致可能的权限位变化

2003 paper: “Using Memory Errors to Attack a Virtual Machine”

  • by Sudhakar Govindavajhala, Andrew Appel
  • Escape from Java VM

完全随机的 vs 可控和可重复的

  • 触发方式相近
  • 但可重复的能提供更多控制力

2014 paper: “Flipping Bits in Memory Without Accessing Them: An Experimental Study of DRAM Disturbance Errors”

  • 在一些桌面电脑测试,但它们有ECC – 能强力减轻这种bug

DRAM badness by year graph

如何触发/触发方法

1
2
3
4
5
6
7
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

必要条件1: 绕过cache 直接访问 → x86 CLFLUSH 指令

  • 它是非特权指令
  • 无法禁用它(不像RDTSC)

必要条件2: 找到坏行

  • 有一些的DRAM的坏行比其它的DRAM多
  • 申请大块内存,尝试很多地址

    DRAM 被分成了 banks → 每一个有它当前的行
    必要条件3: 选中>=2个地址

  • 映射同一个bank的不同行
  • 行的地址冲突对(CMU 论文用的: Y = X + 8MB)
  • 需要能用物理地址
  • Memtest: 在管理权限下运行 完全在硬件上的
  • On Linux: 可以使用 /proc/$PID/pagemap
Row # Bank 0 Bank 1 Bank 2 Bank 7
0 0 0x2000 0x4000 0xe000
1 0x10000 0x12000 0x14000 0x1e000
128… 0x800000 0x802000 0x804000 0x80e000

如果是随机地址

  • 那么有8 banks → 1/8 机会导致行冲突

根据上面得出的精炼结论是: 尝试的地址数量 >2 addresses, 比如 4 或 8 个

  • 一次测试更多的行
  • 增加行冲突的机会
  • 硬件通常有多个访问队列

Double-sided row hammering

  • 激活这两个邻国的一行,不仅仅是少了一个数据
  • 现有的论文还没探索

探索出DRAM 地址的映射机制

  • 通过位翻转观察
  • 通过时间
    选择地址
  • 使用物理地址 – 禁用 /proc/PID/pagemap
  • 大页(2MB) – 不被禁用
  • 其它连续的物理块

查询DRAM 的SPD 数据 sudo decode-dimms

以上理论的结果: rowhammer-test

  • 在用户态运行 申请1GB 等待位翻转
  • 风险:可能破坏其它进程或者内核 在试验中 它也的确发生了

它在2014年还测了更多的机器

根据以上得出的精炼结论是:

  • 难度:易 找到冲突地址对 ( 通过运行一定时间 , 找到坏行更快) 也就是知道映射关系
  • 难度:易 在128ms(2倍行刷新时间)内 真实的产生这个bug ( 通过最大化行刷新时间间隔中的行激活 通过最大化造成坏行的机会(比如上面的一次多行))
  • 难度:较难 能利用(2-sided) ( 需要更多的物理地址知识)

如何利用/可利用性

系统一直依赖内存

两个利用的地方

本地(NaCl)的Chrome 沙箱

  • 位翻转会被判为安全代码
  • 可以让chrome读代码来发现位翻转

    Linux 内核权限提升

  • 在页表入口(PTE)翻转
  • 获得页表读写权

    密集的数据结构

    -

    本地客户端介绍(NaCl)

  • 运行C/C++源码的沙箱
  • Chrome 的一部分
  • 类似Asm.js, 但是代码生成器是不可信的
  • 安全子集的x86——软件故障隔离(x86安全检测,但它允许CLFLUSH指令)
  • 两个变体: 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

  • Each PTE is 64 bits, containing: graph

可以翻转 :

  • 2% 的机会 可写位1bit
  • 31% 的机会 物理地址号: 20位/4GB 系统

What happens when we repeatedly map a file with read-write permissions?

  1. PTEs in physical memory help resolve virtual addresses to physical pages.
  2. We can fill physical memory with PTEs. graphs
  3. Each of them points to pages in the same physical file mapping.
  4. If a bit in the right place in the PTE flips
  5. the corresponding virtual address now points to a wrong physical page - with RW access.
  6. Chances are this wrong page contains a page table itself.
  7. An attacker that can read / write page tables can use that to map any memory read-write.

利用策略 (特权提升 7 个简单的步骤)

  1. Allocate a large chunk of memory
  2. Search for locations prone to flipping
  3. Check if they fall into the “right spot” in a PTE for allowing the exploit
  4. Return that particular area of memory to the operating system
  5. 通过申请大量的地址空间 强迫系统为PTEs重用内存
  6. 引起位翻转 即改变PTE的指向
  7. Abuse R/W access to all of physical memory In practice, there are many complications.

可能出现的问题

  1. 第6步 如果文件在内存中是连续的一块,有可能我们改变了PTE的指向 但是它任然指向的是文件内部 而非页表的部分 (解决方案:尽力分化文件在内存中所占的位置为分散的)
  2. 第5步 很难让系统有规律的为PTE重用内存(作者说:我花了几个下午以某种方式探索Linux物理页分配器。不是很有趣的代码,结论Mark很聪明 他把系统内存压力逼到某个角落 系统表现得很好)

减轻rowhammer

  • CMU paper: “The industry has been aware of this problem since at least 2012”
  • 行业打算去减轻,但没有安全通告
  • ECC(错误纠正机制 一位错纠正 两位错检测 3位以上没有但可能性很小) 但前提是运行的机器使用了ECC 评价:该减轻方案不理想 昂贵 不能保证工作
  • TRR(目标行刷新) “理想”的方案 统计被激活行的次数 当达到阈值时刷新邻行(LPDDR4在使用,内存控制器pTRR,Intel也说Ivy桥用pTRR 虽然并没找到证据?)
  • 更高的DRAM刷新率,2x刷新率 当前CPU支持 很多厂商BIOS里可以设置这个参数tREFI(怎么验证刷新率?2x就够了么?)

我们能利用javascript 搞事情吗(产生rowhammer)

通过正常缓存地址的访问在不适用CLFLUSH的情况下

通过生成大量的cache misses

JS的引擎速度不是问题 接近原生的访问数组 比如Asm.js

cache missed 是缓慢的

lavados正在搞这个

引发cache misses

需要在所有cache层 都miss (L1, L2, L3)

Row hammering by accident in benchmarks (see paper)

Not with an inclusive cache

  • 被驱逐的cache line 从 L1 L2 L3 都被驱逐
  • 用的是Intel 的CPUs

获取cache配置算法/找到L3 cache相同的映射关系

比如 12路的 L3 cache 找13个地址 依次访问一定会造成一次miss 见paper: The Spy in the Sandbox – Practical Cache Attacks in Javascript

  • 通过一定时间的内存访问
  • 原始动机:L3 cache side channel 攻击

Cache 剔除方案

  • LRU 对于 12路cache 每次循环会发生13次misses
  • 减少6.5倍行激活。不理想
  • 理想的是每个迭代2个cache misses

真实CPU

  • Sandy Bridge: bit 伪 LRU 1bit/1cache line
  • Ivy Bridge : Quad Age LRU 2bit/cache line
  • 增加适应性: “设置决斗(set duelling)”

通过 Cache side channel 减弱rowhammer

  • 减少时间精度(performance.now()) Changes in Firefox, Chrome, Safari/WebKit

也许没用

  • 用更长的时间还是可以获知cache配置算法
  • 多线程: 建立自己的时钟 ( PNaCl, SharedArrayBuffers in Javascript WebAssembly )
  • CPU 性能计数器

未知:

  • ARM 和 移动设备 (cache 组织? CPU性能 和 内存控制器)
  • 损坏 Anecdotal observations

总结

作为软件层面沙箱越来越吊,攻击者将去玩更深奥的缺陷,如硬件错误

Rowhammer: 不只是可靠性的问题

难判定硬件达到了标准

Mailing list

总结

利用clflUSH可以触发rowhammer,并找出提高触发率的一些访问方式(一轮多组 找冲突对)

通过作者提供的方案步骤可以利用rowhammer

有ECC TRR 提高刷新频率等应对/解决/减弱的方案