四种指针

参考文

个人整理

四个智能指针: auto_ptr, shared_ptr, weak_ptr, unique_ptr 其中后三个是c++11支持，并且第一个已经被c++11弃用。

用于测试的结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Test
{
public:
    Test(string s)
    {
        str = s;
       cout<<"Test creat\n";
    }
    ~Test()
    {
        cout<<"Test delete:"<<str<<endl;
    }
    string& getStr()
    {
        return str;
    }
    void setStr(string s)
    {
        str = s;
    }
    void print()
    {
        cout<<str<<endl;
    }
private:
    string str;
};

auto_ptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int main()
{
    auto_ptr<Test> ptest(new Test("123"));
    ptest->setStr("hello 0");
    ptest->print();
    ptest.get()->print();
    ptest->getStr() += "world !";
    (*ptest).print();
    ptest.reset(new Test("567"));
    ptest->print();

    auto_ptr<Test> ptest(new Test("789"));
    auto_ptr<Test> ptest2(new Test("JQK"));
    ptest2 = ptest;
    ptest2->print();
    if(ptest.get() == NULL)cout<<"ptest = NULL\n";
    return 0;
}

输出

1
2
3
4
5
6
7
8
9
10
11
12
13

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

unique_ptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

unique_ptr<Test> fun()
{
    return unique_ptr<Test>(new Test("789"));
}
int main()
{
    unique_ptr<Test> ptest(new Test("123"));
    unique_ptr<Test> ptest2(new Test("456"));
    ptest->print();
    ptest2 = std::move(ptest);//不能直接ptest2 = ptest
    if(ptest == NULL)cout<<"ptest = NULL\n";
    Test* p = ptest2.release();
    p->print();
    ptest.reset(p);
    ptest->print();
    ptest2 = fun(); //这里可以用=，因为使用了移动构造函数
    ptest2->print();
    return 0;
}

输出

1
2
3
4
5
6
7
8
9
10
11

Test creat
Test creat
123
Test delete:456
ptest = NULL
123
123
Test creat
789
Test delete:789
Test delete:123

share_ptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int main()
{
    shared_ptr<Test> ptest(new Test("123"));
    shared_ptr<Test> ptest2(new Test("456"));
    cout<<ptest2->getStr()<<endl;
    cout<<ptest2.use_count()<<endl;
    ptest = ptest2;//"456"引用次数加1，“123”销毁
    ptest->print();
    cout<<ptest2.use_count()<<endl;//2
    cout<<ptest.use_count()<<endl;//2
    ptest.reset();
    ptest2.reset();//此时“456”销毁
    cout<<"done !\n";
    return 0;
}

输出

1
2
3
4
5
6
7
8
9

Test creat
Test creat
456
1
Test delete:123
456
2
2
Test delete:456

总结

auto_ptr

• 手动释放资源 .reset()
• 将指针置空,返回资源控制权 .release()
• 用 .get()==NULL 判断是否为空

unique_ptr

• 和auto_ptr相似
• 不能使用两个智能指针赋值操作，应该使用std::move
• 可以直接用if(ptest == NULL)来判断是否空指针

share_ptr

• 使用计数机制来表明资源被几个指针共享,.use_count()来查看资源的所有者个数
• 没有release

weak_ptr

• weak_ptr是用来解决shared_ptr相互引用时的死锁问题,如果说两个shared_ptr相互引用,那么这两个指针的引用计数永远不可能下降为0,资源永远不会释放。它是对对象的一种弱引用，不会增加对象的引用计数，和shared_ptr之间可以相互转化，shared_ptr可以直接赋值给它，它可以通过调用lock函数来获得shared_ptr。

很久以前就有听说这个命题

但我始终也不能说出个所以然,最多的个人体验也就是root权限

知乎这种逐渐变为垃圾问答区的地方，显然是大量的0说服力的答案,慢慢变成百度知道了:-)

搜了一篇 当做英文休闲阅读了

original link

写在前面

• windows的想法是好的,闭源比开源更难攻击
• 事实上并没有得到预期的更好,由永无休止的补丁可证(?啊,Linux 没补丁的咯?)

这里的意思并没有反驳闭源的安全性比开源更好 同样的linux(闭) > linux(开) > windows(闭) > 同样的windows(开)

安全性:同样A,A(闭源) > A(开源)，但开源带来的可以让A变成A+ 那么安全性上,A+(开) 是可能 > A(闭)的

权限

windows

• 日常运行 对于文件:高权限
• 能够操作任何电脑上任何文件

Linux

• 日常运行 对于文件:低权限
• 只能操作当前用户有权限的文件

也就是说用户的文件等在Linux 还是有同样的风险?

这里原文没有说细,[对于不同用户,windows是可以操作他人的文件,而linux可一通过权限控制在一个用户内+共享?]

小总结:Linux 也不是绝对可靠

• 更难发生系统级别的破坏
• 更难发生用户层面广泛的破坏

社社社…社会工程学

好吧 说得有那么一点道理 (这里也有执行时需要权限属于上一部分的东西)

病毒呢 传播时 通常诱导用户添加/点击/安装

说是windos呢 例子:给个带exe附件的邮件并诱导你下载点击，然后 就完事了 (简言之 点3下就可以入侵)

但是linux呢 你下下来给它执行权限chmod么才行(简言之 要执行过程复杂繁琐+运行有系统级别破坏时需要系统权限)

个人看法

• 不认可
• 如果把两边用户交换一下,linux 也能提供点3下就执行程序的,并且目前的易用操作系统的流程已经很简洁了
• 感觉这一点 大自和用户习惯,使用方式,社区安全,用的人少相联系

单种效应

…….这个名词 瞎翻译的,说的是 windows就一个,但linux 有各种分支,不同的邮件客户端,不同的架构,然后病毒的兼容性很难实现…..

仔细想一想 还是有那么些道理的 但我只想到作为server端，比如架构

外网—我们的linux1—我们的linux2—我们的linux3—我们的linux4(服务)—我们的linux5(数据)

那么要从外网进攻, 至少需要4个不同兼容性 而window就just do it again....
讲道理的话....真有做这么多层这样防护的吗,目前只了解到 有 外网-server1-服务-数据这样的

以及,本身作为非系统的server的话,在不同的linux之间的移植能力，也会比 攻击程序 的移植能力强。

感觉有那么一些道理,对我还不是太有说服力，感觉比第二点说服力强很多

用户多

个人看法

• 不认可
• 这只能说可能是 当下linux比当下window安全的一个原因
• 并不想讨论当下 我更喜欢数学上的 如果有相同的用户量呢 如果linux 比windows用户更多呢,如果真的是因为用户少而更安全,那我认为是无数学上的优势的
• 其它看法linux desktop 少，但linux server多啊 虽然数据并不多到那里去数据

开源

就是上面我自己碎碎念的

大量的人能看到代码的bug,并及时去维护。

有利有弊吧

总结

啊,唯一让我满意一点的就是权限的说明了…

这篇文章也没有深入到系统里,感觉还是很表面的东西,不过windows也不开源,不知道能不能找到逆向工程出来的系统级别的,和linux的系统级别的深入比较的文章。。。恩 我不打算自己研究 还是看文章好了，期望能找到

之后在一个长篇的知乎回答上得到了一点对于权限的补充说明”其繁殖速度必须超过其死亡(被消灭)的速度”

所以,我现在能想到一个没有杀软的linux的进攻(相对于windows点3下)即是 下载并运行(社会工程学:-))->写入用户的需要管理员权限的可执行文件/脚本文件?->用户执行了它->达到和windows点3下同样能达到的效果

mongodb 学习记录

本文依赖

nodejs

mongodb

angularjs

记录

工作总图

Detail

nodejs

事件驱动可扩展性，端到端

npm install

npm search

npm install -g

npm install -g npm-check

npm-check -u -g

模块封装

事件模型 阻塞I/O

发送接受P59

1
2
3
4
5
6

var events = require("events");
var emitter=events.EventEmitter();
emitter.emit(eventName,data);
.addListener(eventName,callback(data))
.on(eventName,callback(data))
.once(eventName,callback(data))

json/buffer/stream(网页流数据/压缩解压) -P90

文件系统 -P107

require(“fs”)

HTTP:

1
2
3

require("http")
require("url")
require("querystring")

HTTPS:P127-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/*
openssl genrsa -out server.pem 2048
openssl req -new -key server.pem -out server.csr
openssl x509 -req -days 365 -in server.csr -signkey server.pem -out server.crt
*/
var https = require("https");                                                                                                                          
var fs = require("fs");
var options = {
  key: fs.readFileSync("./server.pem"),
  cert: fs.readFileSync("./server.crt")
};
https.createServer(options,function(req,res){
  res.writeHead(200);
  res.end("Hello Secure World\n");
}).listen(8128);

socket P132-

多处理器

process

child_process

cluster,worker实现多个”线程”监听一个port并可自动处理cluster_server.js /cluster_worker.js/cluster_client.js

1
2
3

process.stdin.on("data",function(data){;});
process.on("SIGINT",function(){;});
process.on("SIGBREAK",function(){;});

https://raw.githubusercontent.com/bwdbooks/nodejs-mongodb-angularjs-web-development/master/ch09/process_info.js

exec() / execFile()/spawn()

其它模块介绍,runnoob上也有https://nodejs.org/api/

os见os_info.js

util有format,log,debug,checktype,转对象为字串原型继承见util_inherit.js

dns有lookup不同level的resolve

Express(server)

npm install express

route,Error handle,易于集成,cookie,会话缓存

_http_https.js require('url')

1
2
3

app.get('/user/:userid',function(req.res){
	res.send("Get User: "+ req.param("userid"));
});

express_routes.js 路由demo/req.params/正则/Request对象/Response对象

express_json.js/express_send_file.js/res.download([path])/res.redirect()

模板引擎ejs+jade,express_templates.js and other files

中间件大法

app.use(path,bodyParser()).use(path,bodyParser()).use(path,bodyParser());

app.get(path,bodyParser(),function(req,res){});

• static 内置 流式处理静态文件访问
• express-logger
• basic-auth-connect基本身份验证
• cookie-parser读取设置cookie
• cookie-session/会话支持
• express-session,相当强大会话实现
• body-parser req正文中的JSON解析为req.body
• compression 对客户端大响应提供Gzip支持
• csurf 跨站点请求 伪造保护

res.query. 用于查询把url转化为json

静态文件服务

app.use(pathurl,express.static(path_file_or_dir_local)[,config]);//maxAge hidden redirect index

auth_session.js 会话+验证

mongodb(NoSQL)

针对文档，高性能，高可用性，高可扩展性

安装

mongodb类型

基础教程

封顶集合(capped collection) 超过大小以旧的替代新的

索引？分片？复制？

生命周期？应用程序代码控制或者TTL

1
2
3
4

help <option>
use <database>
show <option> (such as dbs,collections,profile,log)
exit

用户管理身份验证-P196

数据库管理

1
2
3
4
5
6
7
8
9

db.copyDatabase(origin,destination)
db.dropDatabase()
db.createCollection("collectionname")
coll =db.getCollection("collectionname")
coll.drop()
coll.find({'key':'value'})
coll.insert({'key':'value'})
coll.remove({'key':'value'})
coll.update(where,set,other option) //inc set push sort等update运算符

mongo+nodejs

1
2

npm install mongo
npm install mongoose

见 db_connect_object.js

demo

db,Admin,Collection,Cursor对象

atomically:findAndModify()/findAndRemove()

upsert()/save()/remove()

mongo可以直接执行js :generate_data.js

count / limit

aggregate([{$match:{tasdf:X"}},{$group:{asdf:"agqwe",sdfo:{$sum:"agqwe"}}}]) //mapreduce? 聚合

mongoose结构化模式与验证

mongoose/schema/query/Document

mongoose_find.js/_create.js/_save/_update_one

***.validate(function(value){;})

中间件

pre/post

mongoDB高级

ensureIndex /MongoClient

分片集群等等 GridFS/GridStore

修复 备份

angularjs

数据绑定，可扩展性，整洁，可重用，整洁，支持，兼容性

MVC

node_server.jssimple demo

专有对象提供器animation,controller,filter,directive

服务提供器value,constant,factory,service,provider

注入21 injector.js

作用域+广播emit/broadcast/on->event的属性targetScope/currentScope/name/stopPropagation/preventDefault/defaultPrevented

ng-model,data-ng-model,x-ng:model,ng_model 都被规范化为ngModel

内置过滤器currency,filter:exp:compare,json,limitTo:limit,lowercase,uppercase,number[:fraction],orderBy:exp:reverse,date[:format]

DIY过滤器

1
2
3
4

angular.module(***).filter('fff',function(){return function(leftinput,argument){return result;}})
controller('aController',['$scope','fffFilter',function($scope,fffFilter){
	;//直接在html上用 或者 用作函数也行
}])

支持AngularJS模板功能的指令/表单 P411-419

24directive_custom.js/html

• template允许你定义插入指令的元素的AngularJS模板
• templateUrl同上但是是url
• restrict允许你指定该指令 A属性名E元素名C类名
• replace取代元素
• transclude内部是否可以访问内部作用域以外的作用域
• scope指定内部作用域，{}隔离 @funcname/@ 绑定到DOM = 双向绑定 & 局部绑定到指定scope
• link指定 作用域 DOM元素 和其它能操作DOM属性的链接函数
• controller
• require所需要的其它指令

内置常用服务

animate(css),cacheFactory,compile,cookies,document,http,interval,locale,location,resource,rootElement,rootScope,route,sce,templateCache,timeout/interval,window.alert,

$http 请求delete/get/head/jsonp/post/put

26章完整登陆注册验证实例

社交媒体账户作为身份验证来源 npm install passport/passport-google/passport-facebook/passport-twitter 已验证后的序列化和反序列化 google_auth.js

27定义评论回复照片和页面模型 /mongoose model schema的应用 更复杂的控制实现 和 angularJS的service应用/

28购物车 mongoose model schema的应用

建议的代码文件结构方式,代码编码顺序[bg(node)/view(html[css])/fg(angularJS)]

29 选项卡 天气服务 可拖动组件 交互表格数据

贡献

• 提供了系统分类的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

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.

ABSTRACT

这个论文写的是RDF-3X的引擎,一个基于SPARQL的实现，并超级高效,小心的设计出的追求RISC格式和流线型结构和的简洁的数据结构和操作。

1. 储存和索引3元RDF的通用解决方案,且完全不用做物理设计的调整。
2. 一个强力且简单的query处理器对最大可能性范围利用快速合并。
3. 一个用基于整个连接路径的统计对照表的耗费模型来选择最优合并顺序的query优化程序

RDF-3X与先前最先进的系统相比，在几个大规模数据集上进行测量，这些数据集具有超过5000万个RDF三元组和基准查询，包括模式匹配和长连接路径 基础数据图。

INTRODUCTION

Motivation and Problem

RDF数据结构已经存在了十年,它被设计为对于语义Web的模式松弛或甚至无模式的信息的灵活表示。到商业化的今天的电子世界，RDF也没有得到太多的关注，但RDF建立了强大的动力。语义网络风格的本身和知识是基于数百万现实来自维基百科和其它在线已经创建并可获取的来源。E-science数据容器以导入/导出的格式支持RDF,并也可以筛数据选(基于query),更引人注目的,是在生命科学领域。最终,Web 2.0平台的在线社区将RDF视为非专有交换格式,并将其作为构建信息混搭的工具。

在RDF格式中，所有的数据元素都表示为(subject,predicate,object) 三元组,有的是(subject,property,value)三元组,例如

• (id1, hasT itle, ”Sweeney T odd”),
• (id1, producedInYear, ”2007”),
• (id1, directedBy, ”T im Burton”),
• (id1, hasCasting, id2),
• (id2, RoleN ame, ”Sweeney T odd”), (id2, Actor, id11),
• (id1, hasCasting, id3),
• (id3, RoleN ame, ”M rs. Lovett”), (id3, Actor, id12),
• (id11, hasN ame, ”Johnny Depp”),
• (id12, hasN ame, ”Helena Bonham Carter”)

这样,注意到predicate和属性没有两样,并且这没有数据库模式,这种三元组的概念非常适合现在的随收随付(pay as you go),和实体关系模型相比,都有实体的属性和关系/谓语,所有的三元组放在一起可以看作一个巨大的层次结构图。

SPARQL查询语言是官方标准用来搜索RDF仓库。它支持三元组的conjunctions 和 disjunctions,在关系引擎中选择项目连接查询的对应项。比如我们可以得到Johnny Depp 的电影的title用 SPARQL查询语句:

1
2
3

Select ?title Where {
?m <hasTitle> ?title. ?m <hasCasting> ?c.
?c <Actor> ?a. ?a <hasName> "Johnny Depp" }

这里每一个点代表一个conjunction(join),整个查询也可以看做在RDF数据图中做图模式匹配,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数据需要很多技术挑战，包括储存布局,索引和查询过程。

1. (没有固定结构与实际的数量大变化频繁的矛盾)缺少全局模式和谓词名称的多样性对物理数据库设计提出了主要问题。原则上，可以依靠自动调谐“向导”来实现频繁的连接路径;然而在实践中，数据的不断发展的结构和不一致动态的工作量将这个问题变成一个复杂的西斯弗斯任务。
2. (join 查询多难预测 RDF为动态应用空间 需要适合的动态优化查询算法)通过RDF数据 - 三元组而不是整个记录或实体的细粒度建模 - 具有大量连接的查询将固有地形成工作负载的大部分，但连接属性比关系设置中的可预测性要差得多。这要求查询处理算法的特定选择，以及对复杂连接查询的仔细优化;但RDF是用于在数据空间上的即时应用程序，因此优化发生在查询运行时。
3. (需要统计来 找到 优化方案 不同优化方案的适应度差别大)由于连接顺序和其他执行计划优化需要数据统计来进行选择性估计，因此RDF引擎面临的问题是，在没有模式的情况下，统计信息收集的合适粒度是显而易见的。例如，在工作负载的where子句中出现的所有属性的单维直方图 - 关系系统中的最先进的方法 - 不适用于RDF，因为它错过了长连接链或大连接星的影响多对多关系。
4. (和XML样子像但是具体差别挺大)虽然RDF使用XML语法，而SPARQL涉及类似于XML路径表达式的搜索模式，但是RDF三元组形成图形而不是树的集合的事实是对更深入研究的XML设置的主要区别。

Contribution and Outline

本文为上述问题提供了一个全面，可扩展的解决以上问题的方案。 它提供了一个完整的系统，创造的RDF-3X（RDF Triple eXpress），从头设计和实现，专门用于管理和查询RDF数据。 RDF-3X遵循[24,39]中倡导的为特定应用领域设计和定制的数据管理系统可以通过两个数量级来超越通用主流系统的原理。 在这个论点的因素包括

1. 数据结构和算法的裁剪，而不是支持更多各种各样的方法
2. 更轻的软件脚印和开销，
3. 简化的系统内部优化和更容易配置 和自适应变化的环境（例如，数据和工作量特性）。

RDF-3X遵循这种RISC风格的设计理念[10]，设计用于支持RDF的“精简指令集”.RDF-3X基于三个原则：

1. 物理设计通过在单个“巨型三元组表”上创建适当的索引来独立于工作负载.RDF-3X不依赖于自动调整向导的成功（或限制），而是有效地消除了对物理设计调整的需要。它通过在构成RDF三元组的三个维度的所有6个排列上构建索引，并且附加地对所有三维二维和所有三个一维投影的计数聚合变体进行索引。每个索引都可以很好地压缩;所有索引的总存储空间小于主数据的大小。
2. 查询处理器是RISC风格的，主要依赖于对排序后的索引列表的合并连接。这可以通过三元组表的“穷举”索引来实现。事实上，所有处理都是仅索引的，并且三元组表仅仅虚拟地存在。运算符树被构造以便在最大可能程度上保留后续连接的有趣顺序[17];只有当这不再可能时，RDF-3X才会切换到基于散列的连接处理。这种方法可以在代码级别进行高度优化，并且与传统查询处理器相比具有低得多的开销。同时，支持SPARQL的各种重复消除选项，查询中的分离模式以及SPARQL所需的所有其他功能也非常有用。
3. 查询优化器主要关注执行计划生成时的连接顺序。它采用动态规划计划枚举，成本模型基于RDF特定的统计概要。这些统计包括数据图的路径中的频繁谓词序列的计数器;这样的路径是电位连接模式。与通用数据库系统中的查询优化器相比，RDF-3X优化器更简单，但在执行计划的选择性估计和决策方面更加准确。

这项工作的科学贡献是：

1. 用于RDF索引和查询的新颖架构，消除对物理数据库设计的需要，
2. 用于大规模连接查询在无结构的RDF三元组上的优化器，由新的对于RDF路径的选择性估计驱动，
3. 基于具有三个大数据集的实际测量的综合性能评估，示出了先前最好的发动机[1]的大增益（对于一些查询，通常为5和高达20） 。 RDF-3X的源代码和实验数据可根据要求提供非商业用途。

BACKGROUND AND STATE OF THE ART

SPARQL

SPARQL查询[36]是构成RDF数据图的三元组上的模式匹配查询。 除了语法糖，一个基本的SPARQL查询具有形式

1
2

select ?variable1 ?variable2 ...
where { pattern1. pattern2. ... }

其中每个模式由subject，predicate，object组成其中的每一个都是变量或文字。 查询模型是和样例一样：查询指定已知的文字并将未知数保留为变量。 变量可以出现在多个模式中，由默认连接。 查询处理器需要查找满足给定模式的所有可能的变量绑定，并将来自projection子句的绑定返回到应用程序。 请注意，并非所有变量都必须绑定（例如，如果变量只出现在projection中，而不是在pattern中），这将返回NULL。

该模式匹配方法限制了关于可能的执行计划的查询引擎的自由度，如以下示例所示：

1
2

select ?a ?c
where { ?a label1 ?b. ?b label2 ?c }

用户对通过?b可以连接的所有?a和?c感兴趣。 ?b本身的值不是projection子句的一部分。 不幸的是，模式匹配语义要求仍然需要计算所有的?b的绑定。 可能有多种方式从?a到?c，导致输出重复。 由于这通常不是用户/应用程序的意图，SPARQL引入了两个查询修饰符：distinct关键字指定必须删除重复项，而reduced关键字指定重复项可以但不必删除。 reduced关键字的目标显然是通过允许优化来帮助RDF查询引擎，但是使用减少的选项，查询输出具有非确定性。

然而，即使是创建所有重复的默认模式允许一些优化。 查询处理器不能忽略由于它们对重复项的影响而被投影掉的变量，但是它不必创建显式绑定。 只要我们能保证产生正确数目的重复，绑定本身是不相关的。 我们稍后将通过计数重复项的数量而不是产生重复项本身来使用此观察。

Related Work

大多数可公开访问的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]）。有两种极端的方式做到这一点：

1. 所有三元组存储在一个单一的，巨大的三元组表与通用属性主题，谓词，对象。
2. 三元组按其谓词名称分组，具有相同谓词名称的所有三元组存储在同一属性表中。可以使具有用于每个谓词名称的单独表的属性表的极端形式更加灵活，从而导致混合方法：
3. 基于对于相同实体类的谓词或工作负载中的同现（co-occurrence），通过谓词名称对三元组进行聚类;

每个簇属性表包含少量相关谓词的值，并且对于具有不频繁谓词的三元组，可以另外存在“剩余”表。集群属性表具有类别特定的模式，其具有在相应的RDF谓词之后命名的属性，并且其宽度可以从单个谓词（属性）到相同实体类型的所有谓词。

早期的开源系统如Jena [23,46]和Sesame [8,28]使用集群属性表，但将物理设计留给了应用程序调优专家。这些系统都没有报告任何性能基准，大型数据在千兆字节范围内有超过1000万个三元组。 Oracle [29]在[11]中报告了非常好的性能结果，但是似乎在很大程度上依赖于良好的调整，除了基本的三元组表之外，通过正确选择物化连接视图（创建的主题 - 属性矩阵）。 [1]目前最快的RDF引擎使用最小宽度属性表（即二进制关系），但将它们映射到列存储系统。 [41]给出了不同存储布局的一个很好的分类，并提出了中型合成数据和合成工作负载的系统性能比较。与[1]针对“巨 - 三元组表”方法的论据相反，我们的RDF3X系统显示了如何成功地使用具有优异性能的三元组表。

性能最佳的系统，Oracle和C-Storebased的引擎擎，依赖于这些视图上的物化连接路径和索引。索引本身是分别由底层RDBMS和列存储支持的标准索引。本地YARS2系统[19]提出了在6个单独的B +树或散列索引中的三元组及其所有嵌入子三元组（对和单值）的详尽索引。这类似于我们的方法，但是YARS2忽略了在subject, predicate, object（作为主要，次要和第三级排序标准）的规范顺序之外的排序顺序中索引三元组。对于HPRD系统[6]提出了一个非常相似的方法，并在Sesame系统中作为选项（创造的“三重指数”）[28]。 YARS2和HPRD似乎主要适用于简单的查找操作，并且对连接的支持有限;他们缺乏DBMS风格的查询优化（例如，不考虑任何连接顺序优化，虽然[6]认识到这个问题）。 [5]提出使用后缀数组索引整个连接路径，但不讨论优化此物理设计的查询。 [42]介绍了一种基于明智选择的“中心节点”的新型路径索引;该指数，创造的GRIN，在小到中等数据和手指定的执行计划表现出良好的性能。在[12]中也讨论了模式无关的“宽和稀疏表”的物理设计，没有具体考虑RDF。所有这些用于RDF索引和物化视图的方法都会产生一些形式的物理设计问题，并且没有一个解决了这些物理设计特性所产生的查询优化问题。

对于查询优化，[11,29]和[1]利用与这些解决方案分层的SQL引擎一起提供的最先进的技术。 据我们所知，没有一个采用任何RDF本地优化。 [38]概述了代数重写的框架，但似乎性能增益的主要规则是推动选择低于连接; 没有考虑连接排序。 [20]具有类似的风格，同样忽视找到好的连接排序的关键问题。

最近，图上的SPARQL模式的选择性估计已经由[38]和[25]解决。方法[38]收集每个主题，每个谓词和每个对象（标签或值）的单独的频率统计;通过假设主语，谓词和对象分布在概率上是独立的来估计整个三元模式的频率。 [25]的方法通过在所选择的任意形状的图形模式的集合上建立统计来更加复杂。它将模式的选择转换为优化问题，并使用贪婪启发式。查询模式的基数估计识别统计存在的最大子模式，并且将它们与关于超级模式的统一性假设组合而没有统计。虽然[38]似乎太过于简单，不能产生准确的估计，方法[25]是基于一个复杂的优化问题，并依靠简单的启发式选择一组好的模式的总和结构。我们在RDF-3X中采用的方法捕获路径标签频率，从而超越[38]，但避免了计算的复杂性[25]。

STORAGE AND INDEXING

Triples Store and Dictionary

虽然大多数先前的，特别是最近的文献喜欢存储模式与属性表，我们决定采用概念上更简单的方法与单个，可能巨大的三元组表，我们自己的存储实现下面（相对于使用RDBMS ）。 这反映了我们的RISC风格和“无旋钮”设计理念。 我们克服了以前的批评，即通过创建“正确的”索引集合（见下文）和非常快速的合并连接处理（见第4节），三元组表会产生太多昂贵的自联接。

我们将所有三元组存储在（压缩的）聚类B +树中。三元组在B +树中按字典顺序排序，这允许将SPARQL模式转换为范围扫描。 在模式（literal1，literal2，?x）中，文字指定公共前缀，因此有效地进行范围扫描。 在对中等数量的叶页的单次扫描期间找到每个可能的?x的绑定。

因为三元组可以包含长字符串，所以我们采用使用字典+id映射替换所有字面量的方法（参见例如[11]）。这有两个好处：1）它压缩三元组存储，现在只包含id三元组，和2）它是查询处理器的一个伟大的简化，允许快速，简单，RISC式操作符（见第4.5节）。这些增益的小成本是两个附加的字典索引。在查询翻译期间，在查询中出现的文字被翻译成其字典id，这可以通过从字符串到id的标准B +树来完成。在处理查询之后，所得到的id必须被转换回文本作为应用/用户的输出。我们也可以在这个方向上使用B +树，但是我们实现了一个直接映射索引[14]。直接映射被调谐用于id查找并且导致更好的高速缓存命中率。请注意，这只是当查询产生很多结果时的问题。通常，先前的步骤（连接等）支配成本，但是对于具有许多结果字典查找的简单查询是不可忽略的。

id+字典的方式 提高效率

Compressed Indexes

在上面给出的索引范围扫描示例中，我们依赖于变量是后缀（即，对象或谓词和对象）的事实。 为了保证我们能够通过仅执行单个索引扫描来回答模式三元组的任何位置中的变量，我们在六个单独的维度中保持主语（S），谓词（P）和对象（O）的所有六个可能的排列 索引。 我们可以提供这种级别的冗余，因为我们压缩id三元组（下面讨论）。 在所有实验数据集上，所有索引的总大小小于原始数据。

由于六个索引中的每一个的排序规则顺序不同（SPO，SOP，OSP，OPS，PSO，POS），我们使用通用术语值1，值2，值3而不是主语，谓词， 不同列。 索引中的三元组通过（值1，值2，值3）（对于六个不同排列中的每一个）按字典顺序排序，并且直接存储在聚类B +树的叶页面中。

归类顺序使得相邻三元组非常相似：最邻近的三元组在值1和值2中具有相同的值，并且值3的增加趋向于非常小。 这个观察自然导致三元组的压缩方案。 代替存储完整的三元组，我们只存储三元组之间的变化。 这种压缩方案的灵感来自文本检索系统中的倒排列表[50]，但我们将其推广到id三元组而不是简单的id。 由于下面讨论的原因，我们只在单个叶子页面中应用压缩，而不是跨页面。

对于压缩方案本身，在压缩项目的解压缩或解释的空间节省和CPU消耗之间存在明显的权衡[45]。我们注意到，当压缩过于积极时，CPU时间开始成为一个问题，因此确定了一个字节级（而不是位级）压缩方案。我们计算每个值的增量，然后使用最小字节数来仅对增量编码。标题字节表示由以下值使用的字节数（图1）。每个值在0字节（不变）和4字节（delta需要完整的4字节）之间消耗，这意味着每个值有5个可能的大小。对于三个值，这些是5 * 5 * 5 = 125个不同大小的组合，其适合于报头字节的有效载荷。剩余间隙位用于指示小间隙：当仅值3改变，并且增量小于128时，其可以直接包括在报头字节的有效载荷中。这种小的delta是非常常见的，并且可以在我们的方案中由单个字节编码。

三元压缩伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

compress((v 1 , v 2 , v 3 ),(prev 1 , prev 2 , prev 3 ))
// writes (v 1 , v 2 , v 3 ) relative to (prev 1 , prev 2 , prev 3 )
if v 1 = prev 1 ∧ v 2 = prev 2
  if v 3 − prev 3 < 128
    write v 3 − prev 3
  else encode(0,0,v 3 − prev 3 − 128)
else if v 1 = prev 1
  encode(0,v 2 − prev 2 ,v 3 )
else
  encode(v 1 − prev 1 ,v 2 ,v 3 )
encode(δ 1 , δ 2 , δ 3 )
// writes the compressed tuple corresponding to the deltas
write 128+bytes(δ 1 )*25+bytes(δ 2 )*5+bytes(δ 3 )
write the non-zero tail bytes of δ 1
write the non-zero tail bytes of δ 2
write the non-zero tail bytes of δ 3

压缩的细节如上所示。算法计算前一个元组的增量。 如果它是小的，它被直接编码在标题字节中，否则它计算每个树值和调用编码的δi值。 编码用大小信息写头部字节，然后写入δi的非零尾部（即，它按字节写入i，但跳过前导零字节）。 这导致具有不同大小的压缩元组，但是在解压缩期间，可以容易地从报头字节重建大小。 由于所有操作都是逐字节的，解压缩仅涉及几个便宜的操作并且非常快。

我们测试了压缩率和解压时间（以秒为单位）的逐字节压缩与文献中提出的许多逐位压缩方案[33]。 Barton数据集（见第6节）的结果如图3所示。我们的逐字节方案压缩几乎与最佳逐位压缩方案一样好，同时提供更好的解压缩速度。在IR系统中倒置列表中流行的Gamma和Golomb压缩方法执行得更糟，因为在我们的设置中，每当三重前缀发生变化时，间隙就可能很大。

我们还在我们的压缩方案之上试验了更强大的LZ77压缩。有趣的是，我们的压缩方案使用LZ77比原始数据压缩更好，因为增量编码在三元组中表现出共同的模式。附加的LZ77压缩大约减少索引大小两倍，但显着增加CPU时间，这对于复杂查询将变得至关重要。因此，RDF-3X发动机不使用LZ77。

压缩索引的一个重要考虑是每个叶页是单独压缩的。压缩更大的数据块导致更好的压缩（特别是与LZ77压缩相结合），但是逐页压缩有几个优点。首先，它允许我们寻找（通过B +树遍历）任何叶子页面，并直接开始读取三元组。如果我们压缩更大的块，我们经常需要解压缩前面的页面。第二，压缩索引的行为就像一个正常的B +树（有一个特殊的叶编码）。因此，可以像标准B +树中那样容易地进行更新。这极大地简化了压缩索引与其余引擎的集成，并保持其RISC性质。特别是，我们可以采用先进的并发控制和恢复方法进行索引管理，而无需任何更改。

以上新的index 按字节压缩法索引方法 比既有所有的方案效率更优 大小更小(具体方法见上面伪代码)

Aggregated Indices

对于许多SPARQL模式，索引部分三元组而不是完全三元组就足够了，如以下SPARQL查询所示：

1
2

select ?a ?c
where { ?a ?b ?c }

它计算通过任何谓词连接的所有?a和?c，和?b的具体是什么无关的。

因此，我们另外构建聚合索引，每个索引只存储三元组的三个列中的两个。更确切地说，它们存储两个条目（例如，主体和对象）以及聚合计数，即，该对在三元组的全集中的对数的数量。这对于三个可能的三个对中的每一个以及在每个排序顺序（SP，PS，SO，OS，PO，OP）中进行，从而添加另外六个索引。

计数是必要的，因为SPARQL语义。在输出中不会出现?b的具体值，但是需要对重复正确的计数。注意，聚合索引比全三重索引小得多;由六个附加索引导致的总数据库大小的增加是可以忽略的。

代替（值1，值2，值3），聚合索引存储（值1，值2，计数），否则它们被组织在B +树中，就像全三重压缩索引。叶编码略有不同，因为现在大多数变化包括值2中的间隙和低计数值。伪码如图4所示。

最后，除了三元组中的这些索引之外，我们还构建了所有三个包含just（value 1，count）条目的单值索引（编码类似）。虽然仅使用一个变量的三元模式可能很少，但单值索引非常小，并且它们可用简化了查询翻译。

QUERY PROCESSING AND OPTIMIZATION

Translating SPARQL Queries

编译SPARQL查询的第一步是将其转换为适合稍后优化的演算表示。我们构造一个可以被解释为关系元组演算的查询图表示。从SPARQL派生域演算会更容易，但元组演算更容易优化。

虽然SPARQL允许许多语法快捷方式来简化查询制定，但每个（连接）查询都可以被解析并扩展为一组三重模式。三元组的每个组件是文字或变量。解析器已经执行字典查找，即文字被映射到id。与域微积分类似，SPARQL指定必须为数据中每个出现的纯文本三元组生成变量绑定。当查询由单个三元模式组成时，我们可以使用第3节中的索引结构，并使用单个范围扫描回答查询。当查询由多个三元模式组成时，我们必须连接各个模式的结果。因此，我们在查询图表示上采用连接排序算法，如下面进一步讨论的。

每个三元模式对应于查询图中的一个节点。在概念上，每个节点需要对整个数据库进行适当的变量绑定和由字面量所引起的选择的扫描。虽然每个扫描都可以实现为单个索引范围扫描，但优化程序可能会选择不同的策略（见下文）。查询图中的边缘反映变量出现次数。当且仅当它们具有共同的（查询）变量时，连接两个节点。

当查询的projection子句包含distinct选项时，我们添加一个聚合运算符，以消除结果中的重复项。最后，我们添加一个字典查找操作符，将生成的ids返回到字符串。

Optimizing Join Ordering

优化SPARQL执行计划的关键问题是连接排序。关于这个问题有大量文献，通常基于各种形式的动态规划（DP）或随机化（例如，[13,15,26,34]）的解决方案。然而，RDF和SPARQL的固有特性创建了具有特别要求的属性的联接查询，这些属性没有通过现有技术直接解决：

1. PARQL查询往往包含星形子查询，用于组合同一实体的几个属性类属性。因此，必须使用可以创建浓密连接树（而不是专注于左深或右深树）的策略。
2. 这些星形连接发生在长连接路径的各个节点，通常在路径的开始和结束。 SPARQL查询可以轻松导致三元组之间的10个或更多联接（例如，参见第6节中的我们的基准查询）。因此，精确优化需要非常快速的计划枚举和成本估计，或者需要求助于启发式近似。
3. 我们希望利用我们的三重索引的特殊优势，鼓励大量使用合并连接（而不是哈希或嵌套循环连接），但这需要在生成连接计划时保持有趣的顺序非常小心。

他的第一个要求排除了不能生成所有可能的星形链组合的方法。第二个要求强烈建议快速自下而上的方法，而不是基于转换的自上而下的枚举。第三个要求排除了基于抽样的计划枚举（或随机化优化方法），因为这些不太可能为具有超过10个联接的查询生成所有顺序保留计划。事实上，我们期望最具竞争力的执行计划具有特定的形式：它们将尽可能长地使用保持顺序的合并连接，并且仅针对最后几个运算符切换到散列连接。

我们的解决方案是基于自下而上的DP框架[26]。它使用针对基本关系的扫描来生成其DP表，在我们的情况下是三重模式。播种是两步法。首先，优化器分析查询以检查在查询的其他部分中使用哪些变量绑定。如果一个变量未被使用，它可以通过使用聚合索引（参见第3.3节）被抛出。注意，该投影在概念上通过索引中的计数信息保留基数;我们在下面4.4小节中讨论这个问题。在第二步中，优化器决定使用哪些适用的索引。有两个因素影响索引选择。当三重模式中的文字形成索引键的前缀时，它们由范围扫描自动处理。否则，读取的元组太多，需要额外的选择。另一方面，不同的索引可以以适合稍后的后续合并连接的顺序产生三元组，这可能具有比读取太多元组更低的总成本。因此，优化器为所有索引生成计划，并使用计划修剪机制来决定是否早些时候可以丢弃其中的一些。

修剪主要基于估计的执行成本。也就是说，优化器为每个生成的计划调用成本模型，并修剪由廉价替代品支配的等价计划。这种修剪机制依赖于订单优化[35]来决定计划是否可以被另一个计划支配。由于优化器可以对所有三重排列使用索引，它可以按任意顺序生成元组，这使得合并连接非常有吸引力。因此，如果计划更昂贵，但产生可以在以后使用的有趣的顺序，则保留计划。注意，排序不仅通过索引扫描创建，而且还通过选择引起的功能依赖性创建，因此顺序优化组件是不重要的[35]。从种子开始，通过连接较小问题的最佳解决方案创建更大的计划。在此过程中，所有属性处理逻辑实现为对可用等价类的推理，而不是单个变量绑定。每个计划将为每个等价类产生至多一个绑定。这既简化了流水线断路器前面的隐式投影，并允许自适应传递连接条件的检测（即a = b ^ b = c⇒a = c）。

从种子开始，通过连接在查询图[26]中相邻的较小问题的最优解来创建更大的计划。 当查询包含由于FILTER谓词而产生的其他选择时，它们将尽快置于贪婪，因为它们通常价格不贵。 如果选择真的很昂贵，可以更好地将其集成到[9]中提出的DP运算符放置，但是我们没有进一步调查。 我们沿着这些线实现的DP方法非常快，并且能够为具有多达20个三元模式的连接查询计算精确的成本最优解。 我们测量了典型SPARQL场景的优化时间（以毫秒为单位），其中两个实体由星形子查询选择并通过连接模式链连接。 结果示于图5中。

Handling Disjunctive Queries

虽然连接查询更常用，但SPARQL还允许某些形式的析取。 UNION表达式返回由两个或多个模式组生成的绑定的并集。如果有任何结果，OPTIONAL表达式返回模式组的绑定，否则返回NULL值。在这种情况下，模式组是三重模式的集合，可能包含UNION和OPTIONAL表达式本身。

在优化期间，我们将UNION和OPTIONAL中的模式组视为嵌套子查询。也就是说，我们首先优化嵌套模式组（可能递归地），然后在外部查询的优化期间将它们视为具有特殊成本/基数的基本关系。对于UNION，我们添加模式组结果的并集，就像它是一个基本关系一样，对于OPTIONAL，我们使用外连接将结果添加为基本关系。

原则上，可以更积极地优化这些查询，但是最有趣的优化需要使用旁路计划[37]或其他非树结构的执行计划，这超出了本工作的范围。这些优化只会为复杂的查询付出代价;当分离元素很简单时，我们的嵌套优化方案产生最优解。

Preserving Result Cardinality

标准SPARQL语义要求产生正确数量的变量绑定，即使它们中有许多是重复的。 然而，从处理的角度来看，应该避免生产和保留重复的额外工作。

我们通过在查询处理期间跟踪每个元组的多重性来解决这个问题。 对非聚集索引的扫描总是产生1的多重性，而聚合索引将复制的数量报告为多重性。 连接运算符乘以多项式以获得每个输出元组的重复数。 注意，如果我们可以静态地推导出它在子计划中必须是1，我们可以可选地关闭多重跟踪。 当结果呈现给应用程序/用户时，输出运算符根据指定的查询语义（distinct，reduced或standard）解释多重性。

Implementation Issues

我们的运行时系统包括典型的代数运算符（merge-join，hash-join，filter，aggregation等）。与其他系统的一个显着区别是，我们的运行时系统是非常RISC风格的：大多数运算符只处理整数编码的id，消费和产生id元组流，比较id等。除了简化代码，这种减少的复杂性允许整洁的实现技巧。

例如，考虑使用B +树迭代器访问物理数据的索引扫描算子，将三元模式与数据进行比较。三元组中的每个条目都是必须生成或绑定到文字的id属性，如果它在前缀中会影响开始/停止条件，或者如果未绑定的条目先到达，则意味着选择。而不是在运行时检查这些不同的条件，我们可以在查询编译时处理它们。每个条目都是id属性或文字。在三元组中有三个条目，这意味着有八种可能的组合。使用具有索引扫描算子的八个不同实现的单个方法接口，我们可以大大减少系统代码中的条件分支的数量。除了速度更快，每个专业操作员都更简单，因为它现在只实现其设置所需的逻辑。注意，我们只需要专门化步骤逻辑，每个专业化的代码少于10行。

这种RISC风格的简化型系统和简单，快速的操作系统的组合导致非常好的CPU性能。在我们的第6部分的评估中，我们包括温热缓存时间来演示这些效果。我们意识到这些类型的代码调优问题通常不被重视，但对于现代硬件的高性能至关重要。

SELECTIVITY ESTIMATES

查询优化器在寻找最低成本执行计划时依赖其成本模型。 特别地，估计的基数（以及因此选择性）对计划生成具有巨大的影响。 虽然这是数据库系统中的标准问题，但RDF数据的无模式性质使统计数据生成复杂化。 我们提出两种统计。 第一个，专门的直方图，是通用的，可以处理任何种类的三重模式和联接。 它的缺点是它假定谓词之间的独立性，这通常在紧密耦合的三元模式中不成立。 因此，第二个统计量计算数据中的频繁连接路径，并为大型连接提供这些路径的更准确的预测。 在查询优化期间，我们使用连接路径基数（如果可用），否则假设独立性并使用直方图。

Selectivity Histograms

虽然三元组在概念上形成具有三个列的单个表，但是在各个列上的直方图不是非常有用，因为大多数查询模式接触三元组的至少两个属性。相反，我们利用我们的聚合索引，这完全适合于计算三种模式选择性：对于每个文字或字面对，我们可以得到匹配三元组的确切数量与一个索引查找。不幸的是，这不足以估计连接选择性。此外，我们希望将成本模型的所有辅助结构保留在主存储器中。因此，我们进一步聚合索引，使得每个索引适合单个数据库页面并包括有关连接选择性的信息。

就像聚合索引一样，我们构建六个不同的统计信息，一个用于三元组中条目的每个顺序。从聚合索引开始，我们将具有长度为2的相同前缀的所有三元组放置在一个桶中，然后合并最小的两个相邻桶，直到总直方图足够小。这近似于等深度直方图，但避免将桶边界置于具有相同前缀的三元组之间（预期相似）。

对于每个桶，然后计算图6所示的统计量。前三个值 - 三元组的数量，不同的2-前缀的数量和不同的1-前缀的数量 - 被用于估计单个三元模式的基数。注意，这仅仅给出扫描基数，即，所扫描的三元组的数量，其确定索引扫描的成本。当字面量不是索引前缀的一部分并且稍后通过选择测试时，真正的结果基数（其影响后续运算符）实际上可能会降低。在这种情况下，我们通过重新排序文字来导出结果基数（并获得准确的预测），使所有文字都在前缀中。

如果桶中的三元组根据指定的连接条件连接到数据库中的所有其他三元组，则下一个值是连接伙伴的数量（即结果基数）。由于有九种方法来组合来自两个三元组的属性，我们预先计算了九个基数。例如，条目o = s是有效的

|{b|b ∈ current bucket} 1 b.object=t.subject {t|t ∈ all triples}|

这些值在连接与桶完全匹配的模式时会提供完美的连接大小预测。通常情况不是这样，因此我们假定查询条件之间是独立的，并且乘以所涉及的谓词的选择性。 （这种独立性假设是用于可追踪性的最先进的查询优化器的标准）。

Frequent Paths

上面讨论的直方图具有相当的准确性，并且适用于所有种类的谓词。他们的主要弱点是他们假设谓词之间的独立性。两种相关谓词通常出现在SPARQL查询中。首先，三种模式的“星”，其中具有不同谓词的多个三元模式共享相同的主题。这些用于选择特定主题（即，基于相同实体的不同属性的实体）。第二，三元模式的“链”，其中第一模式的对象是下一模式的主题，同样具有给定的谓词。这些链对应于长连接路径（跨不同实体）。由于这两种情况是常见的，我们另外构建专用统计信息以具有用于这样的查询的更准确的估计量。

为此，我们预先计算数据图中的频繁路径，并为它们保留精确的连接统计信息。这里的频率指的是具有相同标签序列的路径。注意，我们对于链和星使用术语路径，在两种情况下结构是相似的。我们通过谓词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 )}

星形路径定义类似，p 1 , . . . , p n在这种情况下是不排序的。我们计算最频繁的路径，即具有最大基数的路径，并实现它们的结果基数和路径描述p 1，…。 。 。 ，p n。使用此信息，我们可以准确地预测查询中出现的频繁路径的连接基数。同样，我们希望将这些统计信息保存在主内存中，从而计算最常见的路径，以便它们仍然适合单个数据库页面。在我们的实验中，我们可以在一个16KB页面上存储大约1000个路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

找到最常见的路径需要小心。虽然看起来这是一个标准的图表挖掘问题，但是该研究线中的普遍方法[16,44,49]，例如基于众所周知的Apriori频繁项目集挖掘算法，不是直接适用的。

与Apriori设置不同，我们的RDFpath意义上的常见路径不一定包含频繁的子路径。考虑具有两个星形链路群集的图，其中所有端节点分别通过谓词（边缘标记）p 1和p 2连接到它们各自的星形中心。现在考虑在两个星形中心之间具有谓词p 3的单个边。在这种情况下，路径P p 3将不频繁，而路径P p 1，p 3，p 2将是频繁的。因此，我们不能简单地使用Apriori算法。

我们的RDF设置中的另一个问题是周期，这可能导致看似无限长，无限频繁的路径。我们通过两种手段解决这个问题。首先，我们要求如果要保持频繁路径P，其所有子路径也必须保持。这对于查询优化目的是必需的，因为我们可能必须将长连接路径分解成较小的连接，并且它简化了频繁路径计算。第二，我们不是通过它们的结果基数而是通过它们的不同节点的数量对频繁路径进行排序。在树中，这两个是相同的，但是在循环的存在下，我们不对节点计数两次。

路径挖掘算法的伪代码如图7所示。它从长度为1的频繁路径开始，通过附加或前置谓词来放大它们。当新路径本身频繁并且其所有子路径仍然保持时，我们添加它。当没有新的路径可以添加时，我们停止。请注意，虽然伪代码显示了一个嵌套循环以方便表示，但我们实际上在实现中使用了一个join和一个group-by操作符。对于我们在实验中考虑的数据集，1000个最常见的路径可以在几分钟内确定。

Estimates for Composite Queries

为了估计整个复合查询的整体选择性，我们将直方图与频繁路径统计相结合。具有具有对象字面量的三元模式的中间节点的长连接链被分解为最大长度的子链，使得只有它们的末端节点具有带有文字的三元模式。例如，像

1
2

?x 1 a 1 v 1 . ?x 1 p 1 ?x 2 . ?x 2 p 2 ?x 3 . ?x 3 p 3 ?x 4 .
?x 4 a 4 v 4 . ?x 4 p 4 ?x 5 . ?x 5 p 5 ?x 6 . ?x 6 a 6 v 6

具有属性谓词a 1，a 4，a 6，v 1，v 4，v 6和关系谓词p 1至p 5的将被分解为p 1 -p 2 -p 3和p 4 -p 5和每个主题选择a 1 -v 1，a 4 -v 4和a 6 -v 6。我们使用频繁路径统计来估计两个连接子链的选择性以及用于选择的直方图。然后，在没有任何其他统计量的情况下，我们假设不同的估计量在概率上是独立的，导致具有每个子链和每个选择估计的乘积公式作为因子。如果不是像?x 6 a 6 v 6这样的简单属性值选择，我们具有星形图案诸如?x 6 a 6 u 6 . ?x 6 b 6 v 6 . ?x 6 c 6 w 6具有属性a 6 ,b 6 , c 6和对应的对象文字u 6，v 6，w 6，我们将首先使用星的频繁路径统计调用星形模式的估计器，然后将它们与产品形式中的其他估计值组合。

EVALUATION

General Setup

为了评估RDF-3X的性能，我们使用了具有不同特性的三个大数据集，并将查询运行时与其他方法（下面讨论）进行比较。所有实验在具有2Ghz Core 2 Duo处理器，2GBytes内存并运行64位Linux 2.6.24内核的Dell D620 PC上进行。对于冷缓存实验，我们使用/ proc / sys / vm / drop caches内核接口删除所有文件系统缓存，然后重新启动各个被测试的系统。我们重复了所有查询五次（包括删除缓存和系统重新启动），并获得最佳结果，以避免操作系统活动造成的工件。对于温暖的缓存，我们运行查询五次，而不删除缓存，再次采取最佳的运行时。
我们的主要比较是在[1]中提出的基于列存储的方法，已经被证明是高度优于所有其他基于DBMS的方法在该文件。我们实现了[1]中描述的方法，但使用MonetDB 5.2.0 [27]作为后端，而不是CStore，因为C-Store不再维护，不在我们的硬件/操作系统平台上运行。 C-Store网页http://db.csail.mit.edu/projects/cstore/建议使用MonetDB，而MonetDB工作正常。注意，我们的设置使用的硬件比[1]特别是硬盘是比在[1]中使用的非常快的RAID慢6倍，传输ca.顺序读取中为32 MB / s。考虑到这个因素6，MonetDB的性能数据与[1]中的C-Store数字相当。对于一个查询（Q6），MonetDB明显快于6（14s对10s），而另一个（Q7）明显更慢（61s对1.4s），但是MonetDB的整体性能比预期的要慢，因为硬盘较慢。

作为RDF-3X的第二个对手，我们使用PostgreSQL 8.3作为字符串字典和（主语，谓词，对象），（谓词，主语，对象）和（谓词，对象，主语）索引的三重存储。这模拟了Sesamestyle [8]存储系统。我们还尝试了当前版本的具有内置RDF支持的领先商业数据库系统，但是在其他系统的运行时间附近无法获得可接受的性能。当使用自己的RDF查询语言，尽管尝试几个自动调整选项，它执行速度比PostgreSQL三元组存储，即使对于简单的查询，并且无法在合理的时间执行更复杂的查询。因此，我们从演示中省略了它。
除了这些基于DBMS的对手之外，我们尝试了来自语义网络社区的几个可用作开源代码的系统。不幸的是，没有一个缩放到我们使用的数据集大小。我们首先尝试了惠普实验室语义网计划中出现的流行的Jena2系统[46]。我们使用Jena版本2.5.5与SDB 1.0包装程序和Apache Derby 10.3.2.1，但无法在24小时内导入我们的三个数据集。从文件增长来看，系统持续变慢，似乎没有在合理的时间内终止。我们还尝试了Yars2 [19,48]，但是再次无法在24小时内导入我们的任何数据集。最后，我们尝试了Sesame 2.0 [8,28]，它应该是最快的语义Web系统之一。 Sesame 2.0能够在13小时内导入Barton数据集，但后来需要ca.对于前两个查询中的每个查询为15分钟，并且由于更复杂的查询的过多的内存使用而崩溃。

请注意，MonetDB和RDF-3X都可以在不到半小时内导入数据集，并且可以按秒的顺序运行查询。 其他语义Web方法通常假定RDF数据适合主存储器，这不是这里的情况。 因此，下面的所有实验都只考虑RDF-3X，基于列存储的MonetDB顶层方法和基于PostgreSQL的三元组存储。 独立于数据库系统，下面讨论的每个数据集首先被带入因子分解形式：一个文件具有表示为整数三元组的RDF三元组和一个从整数到字面量的字典文件映射。 所有三个系统使用相同的文件作为输入，将它们加载到事实表和字典中。 第二阶段的加载时间和数据库大小如图8所示.MonetDB大小是加载后的初始大小。 运行基准后，大小为2.0 / 2.4 / 6.9 GB。 显然MonetDB根据需要构建一些索引结构。

Barton Dataset

对于第一个实验，我们使用Barton库数据集和在[1]中提出的查询作为基准。我们按照[1]中所述处理数据，使用Redland解析器将其转换为三元形式，然后将三元组导入我们的RDF-3X系统。在[1]中，作者修剪了数据，由于C-Store的限制（他们删除所有三元组包含超过127字节的字符串和一些三元组与大量的加入合作伙伴）。我们保留完整的数据，并将其直接导入所有三个系统。总体上，数据包括51,598,328个不同的三元组和19,344,638个不同的字符串。原始数据为RDF（XML）格式的4.1 GB，三重形式的7.7 GB，以及包含所有索引和字符串字典的RDF-3X存储库中的2.8 GB。
我们使用[1]的查询作为我们的实验，但是由于它们在SQL中给出，我们不得不在SPARQL for RDF-3X中重新组织它们。附录A显示所有查询。我们的测量结果如图9所示。我们还包括查询集的几何平均值，它通常用作基准（例如，TPC）中的工作负载平均值度量，并且比极端异常值比算术平均值更具弹性。
第一个观察是，RDF-3X对所有查询执行得比MonetDB好多了，MonetDB本身的性能比PostgreSQL好得多（如[1]中所述）。我们首先讨论RDF-3X与MonetDB的结果。在比较冷缓存时间和热缓存时间时，很明显，磁盘I / O对总体运行时间有很大的影响。 RDF-3X由于其高度压缩的索引结构而简单地读取较少的数据，因此在冷高速缓存的情况下优于MonetDB的典型因子为2至5，有时超过10。在暖缓存的情况下，差异通常较小但仍然很大（因子2，有时高得多）。一个有趣的数据点是查询Q4，其在构造的连接对方面相对昂贵，并且其中RDF-3X甚至在CPU主导的热缓存情况下表现非常好。此外，我们观察到除了I / O和CPU使用率之外的第三个关键方面是内存消耗。查询Q5有一个非常大的中间结果。 MonetDB显然在主存储器中实现这些中间结果的部分。因此，只有少数数据库页面可以进行缓冲，这极大地损害了热缓存行为。

PostgreSQL对此数据集有问题，因为此基准的查询的性质。 几乎所有查询都是聚合查询（通常通过谓词聚合），结果基数很大，这需要昂贵的字典查找。 对于其他更自然的RDF查询，PostgreSQL的性能更好，我们将在接下来的两个小节中看到。
为了了解Yars2风格的系统如何扩展，我们实验禁用所有聚合索引。 这使几何平均值增加到9.52秒（冷）和1.04秒（暖），这显着慢于RDF-3X。 这仍然比其他系统快得多，特别是由于我们的运行时系统和查询优化器。

Yago Dataset

Barton数据集是相对同质的，因为它描述了库数据。作为第二个数据集，我们因此使用Yago [40]，它包括从维基百科提取的事实（利用维基百科的信息框和类别系统），并与WordNet词库集成。 Yago数据集包含40,114,899个不同的三元组和33,951,636个不同的字符串，消耗3.1 GB作为（因式分解）三元组转储。 RDF-3X需要2.7 GB的所有索引和字符串字典。作为查询，我们考虑了三种不同的应用场景 - 面向实体，面向关系，以及具有未知谓词的查询 - 并导出八个基准查询，如附录A所示。这些查询比Barton查询更“自然”，因为它们是标准的SPARQL没有任何聚合和明确给定的谓词。另一方面，查询要大得多（需要更多的多对多连接），因此更难以优化和执行。
结果如图10所示。再次，RDF-3X显然胜过冷和暖缓存的其他两个系统，典型的因子为5到10.这里的PostgreSQL执行得比MonetDB好多了。这很可能是由于MonetDB中的连接顺序差。 warmcache运行时间几乎与冷缓存时间一样高，这表明MonetDB创建了大量的中间结果。
一般来说，这个数据集对于查询优化器来说更具挑战性，因为查询更复杂，选择性估计非常重要。在测试我们的系统时，我们注意到选择性误估可以很容易导致这个数据集减速10-100倍。 RDF-3X在运行时执行和优化器选择执行计划方面表现出极好的性能。

LibraryThing Dataset

作为第三个数据集，我们使用了LibraryThing书籍社交网络www.librarything.com的部分爬网。它包含9989个用户，5,973,703个不同的图书（由这些用户个人拥有）以及用户分配给这些图书的标记。总的来说，数据集由36,203,751个三元组和9,352,954个不同的字符串组成，其原始格式为1.8 GB，RDF-3X为1.6 GB。这个数据集的一个特殊性是具有异构链接结构。在我们的RDF表示中，每个标记都映射到一个谓词，将用户链接到她标记的图书。由于不同标签的数量非常大，数据集包含338,824个不同的谓词，而其他两个数据集分别仅包含285和93个不同的谓词。虽然其他映射到RDF可能是可能的，但我们使用这种非示意性方法作为所有竞争系统的压力测试。
此数据使得RDF-3X的压缩更加困难，并且对MonetDB造成严重的问题。 MonetDB无法处理338,824个表，在文件系统中创建数百万个文件，并一直交换。因此，我们为此数据集使用MonetDB的混合存储方案。我们分割了[1]中描述的1000个最常用的谓词，并将剩余的三元组（大约12％）放在一个大的三元组表中。我们再次构造了三种查询：面向书，面向用户，浏览书和用户链（参见附录A）。与Yago数据集相反，几百万三元组中出现的谓词很少，这降低了连接排序决策的影响。另一方面，数据本身是非常不均匀的，使得选择性更难以预测。

结果如图11所示。在某些情况下，RDF-3X表现很好，优于对手的典型因素为至少5和大于30。 MonetDB和PostgreSQL之间没有明确的赢家。总体MonetDB似乎表现更好，但它崩溃了两次。它拒绝执行查询B3（“太多变量”），可能是因为它包括三个模式与可变谓词（因此至少3000次扫描）。在查询C2中，由于缺少磁盘空间，它在15分钟后崩溃，因为它实现了一个20 GB的中间结果（这是整个数据库大小的10倍）。查询A3由于其高运行时间而突出。
它与相对非选择性的谓词（书籍作者等）执行许多连接，这是昂贵的。其他“困难”查询（B3，C1，C2）本身并不那么难，他们只是需要正确的执行计划选择。例如，B3会找到所有标记为英语，法语和德语的图书的用户。 PostgreSQL通过收集用户拥有的所有图书对来启动此查询，这是非常昂贵的。另一方面，RDF-3X的优化器选择一个计划，收集每个标签的用户与这些书，然后加入结果，这是更有效率。

CONCLUSION

本文提出了RDF-3X引擎，一个RISCstyle架构，用于对大型RDF三元组存储库执行SPARQL查询。正如我们的实验表明，RDF-3X的性能优于以前最好的系统。特别地，它解决了模式数据的挑战，并且与其对手不同，非常好地处理具有大量多样性的属性名称的数据。导致这些性能提高的RDF-3X的显着特征是：1）详尽但非常节省空间的三重索引，消除了对物理设计调整的需要，2）以非常快的合并连接为中心的简化的执行引擎，3）智能查询优化器，它选择成本最优的连接排序，并且甚至对于长连接路径（涉及10到20个连接）也可以有效地执行此操作; 4）基于提供给优化器成本模型的频繁路径的统计信息的选择性估计器。
我们未来的工作包括进一步改进查询优化器（例如，基于魔术集）以及支持超出当前SPARQL标准的RDF搜索功能。沿着后一行，一个方向是允许更强大的通配符模式的整个路径，在XPath后代轴的精神，但图形而不是树。已经提出了扩展SPARQL的建议[3]，但还没有实现。第二个方向是基于应用特定的评分模型提供查询结果的排名。这需要top-k查询处理，并对算法和查询优化提出具有挑战性的问题。最后，完整的SPARQL支持需要一些额外的信息，特别是打字信息。我们认为这可以包括在字典中，但确定最佳编码相对于运行时性能和压缩率需要更多的工作。

总结

现有的储存方式

• RDF Triples
• by predicates

RDF3X

• B+ tree
• string/literal -> id ,Dictionary
• RISC style reduced complexity
• 6-index && compressed index (chunk to leaf level compressed ?) && store changes between index because of the neighboring index are similar
• aggregated index

施佳鑫 orz

现状

分布式图计算

分布式图查询

RDF / SPARQL 与图查询关系

TriAD是当前最好的分布式内存RDF查询系统 利用提前剪枝和异步消息传递来优化系统性能。SHAPE[17]是一个分布式RDF查询系统，基于单机系统RDF-3X[18]实现，利用预取数据来提高性能。最近的一项研究SQLGraph[19]则是使用关系模型存储RDF数据，但是使用图搜索完成查询。

吐槽

竟然不能被jekyll 解析

收到邮件说 两个花括号内的不能被解析

然后我把所有三层括号换成了1个{

词法

字符和字符串

1
2
3
4
5

<single character> ::= <input character> except ' and \
<character literal> ::= ' <single character> ' | ' <escape sequence> '
<string character> ::= <input character> except " and \ | <escape character>
<string characters> ::= <string character> | <string characters> <string character>
<string literal> ::= " <string characters>? "

数字

1
2
3
4
5
6
7
8
9

<sign> ::= '+' | '-'
<digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 
<digits> ::= <digit> { <digit> }
<unsigned integer> ::= <digits>
<unsigned floating point literal> ::= <digits> . <digits>
<unsigned number> = <unsigned integer> | <unsigned floating point literal>
<signed integer> ::= <sign>? <unsigned integer>
<signed floating point literal> = <sign>? <unsigned floating point literal>
<signed number> = <signed integer> | <signed floating point literal>

符号

1
2
3
4
5
6
7
8
9
10
11
12
13
14

<null literal> ::= '_null'
<boolean literal> ::= '_true' | '_false'
<word symbol> ::= '_and' | '_or' | '_not' | '_public' | '_const' | '_class' | '_para' | '_var' | '_pro' | '_while'| '_for' | '_foreach' | '_func' | '_if' | '_in' | '_return' | '_beark' | '_papa' | <null literal> | <boolean literal> | <basic type>
<special symbol> = '+' | '-' | '*' | '/' | '\' | '%' | '=' | '<' | '>' | '<=' | '>=' | '==' | '<>' | '(' | ')' | '[' | ']' | '{' | '}' | '.' | ',' | ';' | '"' | <word symbol>
<letter> = 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' | 'k' | 'l' | 'm' | 'n' | 'o' | 'p' | 'q' | 'r' | 's' | 't' | 'u' | 'v' | 'w' | 'x' | 'y' | 'z' | 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' | 'J' | 'K' | 'L' | 'M' | 'N' | 'O' | 'P' | 'Q' | 'R' | 'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z'
<identifier> = <letter> { <letter> | <digit> }
<directive> = <letter> { <letter> | <digit> }
<user type> ::= <identifier>
<simple type name> ::= <identifier>
<expression name> ::= <identifier> | <ambiguous name> . <identifier>
<method name> ::= <identifier> | <ambiguous name>. <identifier>
<ambiguous name>::= <identifier> | <ambiguous name>. <identifier>
<unsigned literal> ::= <unsigned number> | <boolean literal> | <character literal> | <string literal> | <null literal>
<literal> ::= <signed number> | <boolean literal> | <character literal> | <string literal> | <null literal>

#句法

##语句

1
2
3
4
5
6
7
8
9

<symbol> ::= <identifier> | <symbol> ( '.'<identifier> | '[' <unsigned integer> ']')*
<!-- sign???? -->
<term> ::= <literal> | <symbol> | <term> ('*' | '/') <term> | '('<term>')' 
<condition> ::= <term> | <condition> ('+' | '-') <condition> | '(' <condition> ')'
<compare> ::= <condition> | <compare> ('==' | '<>' | '>' | '<' | '>=' | '<=' ) <compare> | '(' <compare> ')'
<expression> ::= <compare> | '_not' <expression>  | <expression> ('_and' | '_or') <expression> 
<left value> = <symbol>
<basic type> ::= '_void' | '_int' | '_char' | '_double' | '_boolean' 
<type> ::= <user type> | <basic type>

控制

1
2
3
4
5

<if statement> ::= '_if(' <expression> '){' <statement> '}{' <statement> '}'
<!-- break -->
<for statement> ::= '_for (' <assignment block>? ';' <expression>? ';' <assignment block>? '){'<statement>'}'
<foreach statement> ::= '_foreach (' <var name> '_in' <array name>') {'<statement>'}'
<while statement> ::= '_while (' <expression> '){' <statement>'}' 

##各个执行块

1
2
3
4

<judge block> ::= <if statement>
<cycle block> ::= <for statement> | <foreach statement> | <while statement>
<call block> ::= <function name> '(' (<expression> { ',' <expression> })? ')'
<assignment block> ::= <left value> '=' <expression> 

##各个语句块

1
2
3
4
5
6
7
8
9

<var name> ::= <identifier> 
<const name> ::= <identifier>
<function name> ::= <identifier>
<class name> ::= <identifier>
<const definition> ::= <basic type> ' ' <const name>  '=' <literal> ';'
<para definition> ::= <type> '[]'? <var name> ';'
<var definition> ::= <type> '[]'? <var name> { ','  '[]'? <var name> } ';'
<statement sentence> ::=  <judge block> | <cycle block> | <call block> | <assignment block> ';'
<statement> ::=  <statement sentence>+ 

##各个模块

1
2
3
4
5

<const block> ::= '_const{' <const definition>+ '};'
<para block> ::= '_para{' <para definition>+ '};'
<var block> ::= '_var{' <var definition>+ '};'
<pro block> ::= '_pro{' <statement> '};'
<class block> ::= '_class <class name>{'('_papa{'<class name>'};')? <const block>? <var block>? <function unit>+ '};'

##各个单元

1
2
3

<public unit> ::= '_public{' <const block>? <class block>* <var block>? '};'
<function unit> ::= '_func <type> <function name>{' <const block>? <para block>? <var block>? <pro block>?'};'
<main unit> ::= '_main{'<const block>? <var block>? <pro block>? '};'

##最终code

1

<compilation unit> ::= <public unit>? <function unit>? <main unit>?

类型

Booleans

1

_bool bianliang;

1
2

_true
_false

Numbers

1
2

_int bianliang;
_double bianliang;

1
2
3
4

123
-123
12.3
-12.3

Characters

1

_char bianliang;

1
2
3
4

'1'
'\t'
'\''
'\\'

Strings

1

_char [] bianliang;

1
2
3

""
"1"
"123"

Void

1
2
3

_func _void f{
    return ;
}

Null

1
2

<!-- ??? -->
if(a == _null){}{};

lists

1
2
3
4

<type> '[]' <listname>
_int [] a;
Symbols[<unsigned integer>]
a[2]

Symbols

start with letter ,including letter and number, Not case sensitive

1
2

bianliang
feifeifeifeichangmeilidejutu12138

运算

控制块

选择块

1
2

_if(<condition>){true <statements>}{false <statements>};
_if(1==1){a=1;}{};

循环块

1
2

_for(<for init>;<condition>;<for update>){<statements>};
_for(i=1;i<5;i=i+1){a=a+i;_break;};

1
2

_foreach(<item> _in <array>){<statements>};
_foreach(a _in b){s=s+a;};

1
2

_while(<condition>){<statements>};
_while(1==1){a=a+1;_break;};

break from _for or _while

1

_break;

语句块

const

1
2
3
4

_const{
_int a = 2;
_char b = '2';
}

var

1
2
3
4
5
6

_var{
_int a;
_char b;
_double c,d,e;
_int [] c, [] d;
}

执行部分

1
2
3

_pro{
{<control block> | <assignment block>}+
}

Functions

定义

1
2
3
4
5
6
7
8
9
10

_func _int f{
_const{};
_para{
_int [] a;
_int b;
_int c;
}
_var{};
_pro{};
};

调用

f(a,1,2)

类

定义

1
2
3
4
5
6

_class yourclass{
_papa{fulei};
_const{};
_var{};
(_func <type> <function name>{};)*
};

声明变量

1
2

yourclass a;
yourclass [] a;

调用

1
2
3

a.f;
a.q();
a.p(1,2,3);

注释

1
2
3
4
5

#12138

^#{
块注释
^#}

空语句

1
2

{}
;

样例程序

快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

_func _void quickSort{
    _para{
        _int [] s;
        _int l
        _int r;
    };
    _var{
        _int i;
    };
    _pro{
        _if (l< r){
            i = l;
            j = r;
            x = s[l];
            _while (i < j){
                _while(i < j _and s[j]>= x){
                    j=j-1;
                };
                _if(i < j){
                    s[i] = s[j];
                    i=i+1;
                }{};
                _while(i < j _and s[i]< x){
                    i=i+1;
                };
                _if(i < j){
                    s[j] = s[i];
                    j=j-1;
                }{};
            };
            s[i] = x;
            quickSort(s, l, i - 1); 
            quickSort(s, i + 1, r);
        }{};
    };
};

_main{
    _const{
        _int printi 0;#print int
        _int prints 1;#print string
    };
    _var{
        _int [] array;
        _int len,k;
    };
    _pro{
        array[]=[34,65,12,43,67,5,78,10,3,70];
        len = 10;#len=sizeof(array)/sizeof(int);
        print(prints,"The orginal arrayare:\n");
        _for(k=0;k<len;k=k+1){
            print(printi,array[k]);
            print(prints,",");
        };
        print(prints,"\n");
        quickSort(array,0,len-1);
        print(prints,"The sorted arrayare:\n");
        _for(k=0;k<len;k=k+1){
            print(printi,array[k]);
            print(prints,",");
        };
        print(prints,"\n");
        return 0;
    };
};

Rowhammer.js: A Remote Software-Induced Fault Attack in JavaScript阅读整理

• 非逐字逐句翻译
• 序号不完全代表段落

Abstract

1. 概述Rowhammer.
2. 别人要cache flush 指令以及高频率搞DRAM,但我们克服了这个限制,通过利用cache替换法来诱发Rowhammer,并且只用了常规内存访问,这让rowhammer在高严格甚至脚本环境里都能被触发.
3. 我们将演示完全自动攻击,仅需要带JS的网页来引起远端硬件出错,由此我们可以自由的访问网络浏览者的系统,我们表明,攻击在现成的系统上工作。现有对策无法抵御这一新的Rowhammer攻击

Introduction

1. 利用硬件错误攻击通常需要物理访问改变设备的状态,然而软件诱导是可行的,85% 的 DDR3 块被Kim测试可以诱发位翻转,最近DDR4 也被发现可以被诱发,Seaborn证明了位翻转可以用来提升权限,但这些都用了底层代码并且使用了特殊指令——把cache刷入内存.
2. 如果DRAM是有弱点的,我们可以不用任何特殊指令,仅仅利用常规访问和cache剔除法则在所有架构上实现。因此这是一个通用的,可以被部署在任何体系结构,编程语言,运行环境,只要它允许产生巨大的内存访问流,因此如移除clflush指令的抵抗手段并没有任何卵用。更吊的是,我们将向你展示用JS对远端有弱点的模块上进行攻击。
3. 因为这个攻击通过网页同时并偷偷攻击数以亿计的设备,所以它是个严峻的安全威胁,rowhammer.js 不依赖任何CPU指令,他是第一个远端硬件错误攻击.为了证明我们实现了一个能在所有ff和chrome上运行的js代码.
4. 我们用了4步, 1找两个不同的行的两个地址,2高频率剔除再重载这两个地址,3找寻可利用的位翻转,4利用它(控制页表 远端代码执行)
5. 第3,4 步最近已经解决………但第一二步保持开放的挑战[毕竟要做到任意性还要ff和chrome的解析器适应性和ff和chrome的更新吧orz]
6. 第一步挑战是用js收集物理地址的信息,它是严格沙箱,没可能收集虚拟或物理地址。为了应对这个挑战,我们决定部分物理地址使用大数组,它们被操作系统分配到大页上,我们因此不利用任何的JavaScript或浏览器的弱点,只有利用系统级别的优化.
7. 第二步是找到能替代clflush指令的cache替代策略,老版本CPU简单的访问n+1个地址就足够剔除n路cache。 过去4年 Intel CPU生产的CPU使用Sandy Bridge,替换法则变化了并且没文档.因此已知的剔除策略的乘剔除率降低或者需要相当多的执行时间。为了应对这个挑战，我们提出一个通用的方法来找cache替换策略以此来达到时间和剔除概率的最好性能.我们提出的是目前最好的剔除策略，在现在Intel架构上比以往的一切都做得要好

实验装置:

羡慕 别人的玩具比我日常使用的电脑还好

1. 基于这些方法我们使用两阶段攻击未知配置的远端硬件
2. 我们对比了上表列出的机器在固定配置rowhammer攻击下的状况，一些有和期望的样(挂了),另一些降低了刷新速率
3. 至今软件对Rowhammer本机代码袭击的反抗也只是针对特定的利用,如我们所展示的，不足以保护JS的攻击，硬件防护难以部署,因为他们不影响传统的硬件,包括最近脆弱DDR4,BIOS更新可以用来解决这个问题在商品系统中,然而这仅仅是一个高端玩家的实际的解决方案
4. 总之我们的贡献是:

• 我们提供第一个完全获取Intel CPU的cache剔除规则的方法,这也有益于更广阔的领域。缓存攻击,缓存无关算法、缓存替换策略。
• 我们用只访问内存的本地代码实现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的指令,低剔除率

2阶段剔除策略

这是一个完全自动找 Sandy Bridge的cache剔除策略的方法

基于Prime+Probe并显著提升了cache攻击

CPU 替换法不同影响了剔除集合的大小，访问模式需要建立一个高效的回收策略

对于伪LRU,访问很多L3 cache相互冲突的目标地址,高可能的剔除,但对于适应性替换法,一个剔除策略可能在一个替换法下有效,在另一个替换法无效, 因此有必要搞一个理想的对两个都有效的并且不会有明显的时间开销

1. 静态集合和静态访问:用极短的时间利用cache片函数和物理地址并生成一个预序列.见3.2 3.3
2. 动态集合和静态访问: 自动计算驱逐模式,不用任何系统的知识,例如的核心。良好的访问模式去匹配到目标系统的替换法对于一个成功的攻击是必要的。见3.3
3. 动态集合和动态访问: 自动计算驱逐模式,不用任何系统知识,但需要大量的测试,并可自动攻击未知系统。见3.3
4. 静态集合和动态访问: 使用预定义的集合 但顺序是自动化计算的 在理论上可行[这很理论:-)] 但并没有任何优势. [羡慕严谨_(:з」∠)_非要把四个列出来]

搞了离线[没有文档]和在线[未知系统]

剔除模型

成功率来自很多一个mem是否被剔除了的测试

1. 在同一个cache上的命中和不命中有可观的影响,我们通过一个剔除算法和添加不一致的随机内存访问来验证,剔除率=剔除函数的平均成功率,并且只要时间正常,剔除函数成功率并不会收到添加了随机访问影响,因此,驱逐集只包含一致地址和驱逐策略的有效性取决于驱逐集合大小。
2. cache无法区别缓存,我们用a_i来表示访问序列,每一个a_i表示一个(一一对应),因此每次通过控制序列来决定访问哪个地址,a_1 a_2 a_3 序列等于任意一个 a_i a_j a_k 只要i,j,k 两两不等,如果在一个循环中运行,不同的内存地址的数量影响驱逐策略的有效性
3. 重复访问同一个地址有必要把它留在cache 里,因为替换法会把旧的cache line 用新的cache line 替换掉 ,把a_1 … a_17序列变成a_1 … a_17 a_17 在Haswell上快了33%,如果重复执行它显著的提升乐剔除率,因为 cache 被我们的驱逐集填满了,但为我们发现一个随着访问同一个地址增多的边际效应递减,对所有地址我们发现到达一个阈值以后随访问增多剔除率在下降,因此 我们搞了S大小的集合剔除策略,但每轮只是该集合D大小的子集访问,再通过一个参数L来引起循环中能有重复的地址访问。
4. 虽然在实际时间(第二类Stirling数 是很好的估计值)内测试所有可能序列甚至很短的序列不太可能,但探索能影响系统的参数是可能的,根据理论,更好的剔除策略不能被这种减少搜索空间方法找到。但用这种方法,我们可以找到有效的能引起rowhammer的驱逐策略.通过系统的比较驱逐策略,我们使用以下代码展示的方法, P:C-D-L-S, C决定每轮循环访问每一个内存的次数,D决定每轮访问不同的地址的个数,L是大循环的跳动步长,S是集合大小,比如LRU剔除序列是P:1-1-1-S,也就是a1 a2 a3…aS

1
2
3
4

for (s = 0; s <= S -D ; s += L)
  for (c = 0; c <= C; c += 1)
    for (d = 0; d <= D; d += 1)
      *a[ s+d ];

离线测试

在离线阶段,攻击者试图学习他控制的一组机器每台最接近的驱逐策略相匹配的替代法。这不是严格意义上的替代法的逆向工程,通过找到最好的剔除策略,攻击者就弄清了系统。在这个阶段,攻击者没有时间限制
我们讨论对Haswell platform 单DIMM单channel 的具体评测,我们测试了6阶 不同的C D L 参数和23种不同的 剔除集合大小,为了找到快且足够有效引起rowhammer的剔除策略,包括相同的剔除策略,我们在我们的3个平台上测试了18293种策略,我们用20 双向 rowhammer 测试测试了每个剔除策略2百万轮(每个策略8千万次) 且 用不同的评估标准对它们进行评估,包括 剔除率 运行时间 cache命中/不命中率.总运行时间大于6天. hammering 是对一组固定的物理地址的一个特定的缓存设置的驱逐策略的公平比较.在进行到一半的时候(4千万) 我们测试了剔除率,命中/不命中,后一半我们测试剔除的平均时间,我们通过足够多的样本容量验证了可重复的测量
位翻转的数量并不适合作为剔除策略有效性的评判标准,只有判断是否以及如何让cache命中不命中才是有用的,执行时间和剔除率影响一个位翻转的可能性,位翻转在内存位置是可重现的,但是需要的时间和需要访问的次数变化很大,为了测了一个剔除策略的平均访问次数,我们需要用很多小时测试每一个剔除策略,这很难…,它也不会产生可重复的结果,并已经观察到如果一个DRAM被hammer很长时间 它就会永久损坏.
长执行时间引起位翻转太慢,短时间没有好的剔除效率也没什么作用。剔除策略的执行时间和两个victim address的访问次数直接相关,因此它直接影响一个bit的翻转概率,在我们默认配置的Ivy Bridge书上我们观察到每轮hammer导致的位翻转要用1.5ms的执行时间,也就是在总的刷新时间64ms内大约对每个地址21500次访问的数据结果。这与刷新间隔tREFI有关(把64ms分成8192份？),在我们的Haswell测试系统上两路rowhammer只需要60ns通过clfLUSH,也就是64ms进行了每个地址60万次的访问(解释图1a)
解释图1b.99.75%剔除率可以导致81%的位翻转(你们考虑过 Haswell system的感受吗)就是说 剔除率越高越好
解释图1c 1d 的cache hit和cache miss 对位翻转的影响相关性小，真正相关的还是剔除策略
4个图得出的结论是剔除率是一个剔除算法的好的指标,然后再在中间找执行时间少的,并且这种方法需要js这类不需要任何系统接口的

Haswell test system 上的 和clfLUSH(第一行)比较

以上测试结果是在LRU上 5-2-2-18和2-2-1-17 只用180ns左右 比较优秀 而并不是1-1-1-20 无论是率还是时间

并且在eviction 循环里增加内存访问 可以减少时间

总之新找到的比原来的 时间 和 效率都要强

然后 还进行了Ivy bridge上的测试 也能高达99%的剔除率 然后也列了相关测试性能好的表

Skylake DDR4 上测试不太一样 但它很容易被8核逆向工程函数突破 并且再次发现 LRU剔除方案工作得更糟(1-1-1-X ?)

在线测试

目标是未知系统,特别的微体系结构和数量的CPU核都是未知的,攻击者只有离线测试所储备的知识,他在目标机器上没有特权也没有时间去运行广泛的搜索,在线攻击通过两种/步:以假设为基础的攻击 和一个备用攻击(如果第一个没有效果的话),这两种 都需要花一些时间 并且没有系统的特殊接口

23: Liu, F., Yarom, Y., Ge, Q., Heiser, G., Lee, R.B.: Last-Level Cache Side-Channel Attacks are Practical. In: S&P’15(2015)

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)

Assumption-based Attack

首先通过时间表现 看看是不是离线测试过的机器中的一种或类似(因为并不能调系统函数来知道是啥) 只要匹配到了 就把之前离线得到的方案拿来试一试 这只需要很短的时间,并且 eviction 集合 可以静态或者动态计算处 我们在别人的基础上搞了一个动态生成集合算法 因此我们的静态算法产生的动态序列能最小化执行时间.

一个假设是大大数组占大页,基于这个假设他们用下面这种 slice pattern 来判断 4核/2核 4KB 的slice 和 2MB的page 的映射法

0123 0123 0123 0123 1032 1032 1032 1032 2301 2301 2301 2301 3210 3210 3210 3210
1032 1032 1032 1032 0123 0123 0123 0123 3210 3210 3210 3210 2301 2301 2301 2301
2301 2301 2301 2301 3210 3210 3210 3210 0123 0123 0123 0123 1032 1032 1032 1032
3210 3210 3210 3210 2301 2301 2301 2301 1032 1032 1032 1032 0123 0123 0123 0123

针对Sandy Bridge architecture

Oren et al. [27] or Liu et al. [23] 的算法 只能找到 在同一个cache slice 和cache set 的地址

我们用它可以找到 eviction set 在2mb 一致对齐的地址cache集合 同slice的

子驱逐集 的计算 静态的取决于 复杂的地址函数 和 确定的2MB offset

Fall-back Attack

如果上一个攻击失效了 也就是说 目标机器并不属于离线测的机器中的一种类型 ，那么我们将用另一个方法来找能触发 位翻转rowhammer的剔除策略

我们扩展了 Oren et al. [27] or Liu et al. [23]的 1-1-1-X算法 来计算剔除策略 通过利用 动态的集合 和 动态的序列

1. 我们不断的给策略集合增加很多地址,让它足够访问同一个地址有驱逐策略,我们已经知道 当策略集合足够大时我们就能清晰的测试出 剔除的目标物理地址的大小
2. 当剔除率大于设置的阈值 通过利用集合里的地址相互替代 并不会降低剔除率的话 这样 访问次数不下降但是 集合大小下降 因此降低了个数和执行时间,最后移除不会降低剔除率也不会增加时间的元素,再一次减少了不必要的 hit 也就减少了执行时间。

这样找到的集合 既不会访问很少访问的地址 每一个重复访问都对驱逐率有贡献。因此它们接近于静态剔除策略 这样找到的访问集合的剔除率完全接近攻击者设置的剔除率阈值中低运行时间的,如果把阈值设定得足够高,那么在时间中就很可能引起位翻转,那么这种用fall-back找到的剔除策略就能用来攻击
这种算法要用一个函数cached(p) :这是尝试驱逐一个目标地址p的函数 通过现在的驱逐策略,集合以及通过访问时间时间判断p是否被cache了,解决方案的优劣取决于这个函数在测试中的表现,如果驱逐率低于攻击者设定的阈值那么函数返回真,大量的测试增加了执行时间和二元决策性的正确性，解释图4 时间 和剔除率的关系,如果高剔除率是十分必要的,那么执行时间可以超过40min,因此我们的算法预计算剔除策略一次,之后的剔除集合用固定的剔除算法在几秒内完成。

实现以剔除为基础的rowhammer

下面开始我们的表演:-)

首先我们证明 只要攻击者能用native code 攻击 我们就能攻击

然后我们通过拥有物理地址的知识，证明用js引发远端机器位翻转的可能性

最后我们证明仅用js(不用额外信息)可以完成完整的rowhammer攻击

Rowhammer in Native Code

我们用我们找到的最好剔除策略扩张了Dullien的 double_sided_rowhammer 程序,首先clflush 用p:2-2-1策略替代了,这个剔除集合是既有预先的静态计算物理地址映射关系，也有完全地址函数以及动态剔除策略计算算法。通过这样我们可以在前文说到的四种机器上可重复的产生位翻转

但是Haswell 我们以及clflUSH都不太能搞定，因为我们调高了刷新频率的参数tREFI,是一个游戏爱好者和超频社区用来提高性能会改变的.当然这是一个很有趣的课题,我们甚至想分析刷新率对rowhammer攻击适应性的影响.Kim[见论文20]勘探出刷新率直接影像位翻转数.这个参数对js引起的rowhammer同样适用。

降低刷新率并对于真实攻击并不现实,已有的工作已经研究了Rowhammer的可攻击流行度, 发现85%DDR3被测试是易受到rowhammer 位翻转进攻的.只有Haswell test system and the G.Skill DIMMs in the Skylake test system在默认设置下是不易收到进攻的。因此我们的结论并不否定之前的预测,并且我们必须假设还有百万数量级的系统依旧脆弱.

rowhammer剔除策略被google native client 用在native code开发重现 这回允许在google chrome的权限提升,clfLUSH 指令已经被列入黑名单,然而这并没有卵用,我们用剔除法任然在GNC上引起了位翻转，从沙箱中脱离任然可能。

Js Rowhammer

用js引起rowhammer更难,因为js没有虚拟地址或者指针,没有对物理地址的映射,我们观察到在最近版本的ff和chrome的linux版本上js会把大数组分配到1MB对齐并使用匿名2MB大小 只要可以。这个原因在于由操作系统实现的内存分配机制，任何内存分配 在类似脚本语言和环境也会导致为大数组分配匿名的2MB页的。

通过一个类似Gruss 的一个时间攻击表现,我们推断出了浏览器的2MB页框,在这种攻击中,我们遍历一个数组和测量的访问延迟,延迟的峰值,在内存初始化的时候发生,由缺页引起,它发生在每一个新的2MB页 (见图5),在最新版本的浏览器也是这样的 ,尽管被Oren提出了减少时间精度并被W3C加入了HTML5标准,因此,我们知道虚拟和物理地址的最低21位知道数组中的偏移量。

证明第一个概念,我们用js在ff上重现了native code 能做的准确物理地址rowhammer,为了做这个我们造了一个工具来把物理地址转换为虚拟地址，为了计算驱逐集我们用假设基础的算法,我们观察到简单的内存访问例如我们的native code 实现的那样没有被即时编译器优化。
最终以js为基础的攻击 不需要任何外界的计算 因此它运行完全不需要用户交互。它利用大数组被分配到2MB大页的西现实，因此我们知道每一个我们的数组在2MB 页里面被分成了16行偏移的每行128KB(取决于低位的index位).我们现在来展示double-sided hammering 在这些2MB区域来诱发位翻转,或者提升单向hammering 在每2 mb的页面的外两行来引导另一个2MB区域的位翻转,这是史前第一个用JS实现的网站远端硬件错误攻击。

攻击评值

如Kim 论文[20]所描述的,DRAM里的地址能被位翻转的可能性不同,因此为了公平的比较不同的技术，我们测试了位翻转的数量对一个已知易感染的固定地址对。(图6)显示了在固定时间间隔内不同设置，不同的刷新频率如何影响位翻转。系统在测试时有轻微的使用(浏览,在编辑器里打字等等),如果刷新间隔设置得让clfLUSH指令可以引发位翻转,他们也就能被native code 剔除引发。为了用js引发位翻转略高的刷新间隔是必要的,再一次,如果特殊的DIMM刷新率设置得当,那么一次位翻转都不会发啊生。

js的位翻转的概率略低于native code.并且native code 稍微快一些，然而,只要一个机器可以被native code 实现易受害的,那也有被js 实现的能力。我们通过测试在不同的几个机器上验证了这种情况。

虽然DDR4被认为对rowhammering对策,对策不是最终DDR4标准的一部分。使用严格的DDR4 DIMM 我们也能诱发位翻转在默认情况下 在最新的BIOS版本中,(用了反向工程后)。在G.Skill DDR4 DIMMs我们只有增加刷新间隔才能引发位翻转。所以说在最近的系统 硬件 软件 都没有对rowhammer的有效对策。是否会受到rowhammer的攻击的关键在于DIMM的刷新时间间隔的值

讨论和相关工作

现有的攻击假定页表被映射在攻击者占据的两行之间的行中，然而我们发现在实践中几乎不会发生。操作系统喜欢用大页来减少TLB的压力，为了让操作系统易于组织和易于做物理地址的映射,这操作系统还把小的页装进了相同的物理组织框。在near-out-of-memory的情况页表只被分配在两个用户页。因此利用几乎所有系统内存才能强行造出这样的情况。然而换页在主流操作系统中是默认可用的，因此系统由于换页会产生严重的迟钝。在我们的利用的概念证明中，我们演示了放大单向rowhammer.通过锤击两个相邻行，和单面锤击相比我们显著的增加了位翻转的可能性。这允许甚至具有高概率在的2MB物理地址相邻区域的跨越边界引起位翻转，当我们已经能够用js引发位翻转我们就将目光集中在怎么类似之前的利用方法来利用页表，攻击者可以重复任何攻击步骤只要有必要就能成功。

第一步 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.

限制

在js中我们用2MB页来找到冲突地址和相邻的行，如果操作系统不提供2MB页我们就不能演示double-sided或提神 single-sided hammering.然而single-sided hammering 的一位翻转的可能性显著降低. 通过2MB页利用 double-sided hammering 也就不可能，因为我们只能引发在我们自己memory的位翻转. 因此攻击只可能放大single-sided hammering 来引发位翻转在相邻2MB页的相邻行，这是一个在这样行系统中的一个限制值.

尽管搜寻一个可利用的位翻转可能要耗上好几个小时，尤其是js的位翻转比native code 的更低， 此外,如果我们不能猜出对这个系统最好的剔除策略,它将会耗上一个多小时来预计算来找寻一个好的剔除策略. 所以这对于现实的攻击也就不实际.

对策

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.

将来的工作

我们仅仅研究js在linux的ff和chrome上造成rowhammer攻击的可能性，攻击利用内置的硬件和操作系统的工作方式的基本概念运作.无论系统是否用 4KB 页, 页表是需要的，并在一个属于这个页表的页被访问时被创建的. 因此, 操作系统不能防止1/3 内存被用来分配页表.
相同的攻击方法可以应用到4 kb页分配给虚拟机的虚拟机监控程序, 他们甚至适用于Linux内核相似的分配机制.虽然看起来不合理和不现实的虚拟机监控程序分配4 kb页, 在实际上使得cross-VM页面重复数据删除技术变得更加容易. 根据 Barresi et al. [7], 页面重复数据删除实际上是仍然广泛应用于公共云. 我们的问题不是工作页面打开的可能性进一步调查是否重复数据删除实际上不仅是对虚拟机的安全和隐私, 而是程序本身的安全问题

总结

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.

总结

证实只用访问内存就能引发 位翻转 不需要clflush指令 [并提供较为暴力的算法 和 实验数据比对]
证实js 可以引发 [匹配 和 用动态动态算(先增到平衡再替换减少 到最快)]并引发任何语言/环境/CPU/cache攻击的可能性疑问 [当下无法被立刻化解 硬件/软件 占有量]
证实利用ff的大页分配 2MB相邻 等 可实现引发+控制
DDR3 DDR4 都没能应对 但是 有一些可用的应对方法