课程环境：https://tai-e.pascal-lab.net/lectures.html

课程视频：https://www.bilibili.com/video/BV1b7411K7P4

南大《软件分析》14.0 Datalog-Based Program Analysis

首先来介绍两大类范式，一类是命令式编程，另外一类是声明式编程，或许你对这个概念有所陌生，但下面这个例子一定不陌生。

这两类语言都实现了同样的功能，但是实现的方法却截然不同，可以很明显观察到的是声明式编程更加简洁，而且含义也容易理解，而这一节介绍的 datalog 就是这种类似 SQL 一样的语言。

以我们前面在指针分析中的伪代码为例，如果使用编程式语言实现，那我们需要再实现的过程中考虑到各种问题，比如说要用什么数据结构，怎么构造图节点等等各种问题。

同样的逻辑如果使用 datalog 实现，就会发现非常简洁，如上图所示，而且真正的实现和上面的代码也差不了太多。

datalog

关于 datalog 的介绍如下

起初是一种数据库语言，后来可以应用到程序分析，声明式网络，大数据，云计算等等。

下面来一一介绍datalog中常见的几个概念

Predicates

predicate 具体理解为一个可以存储数据的表就行，里面存储了一些对应关系，一个 fact 是一个事实，这个事实可以由表中的数据得到。

Atom

Atom 是 datalog 中的基本表示形式，可以用下面这个例子来理解 atom

当 p 所包含的元组可以由 X1，X2 … 描述时，可以判断 atom 是否为 true，同时 relational atom 还允许算数表达式，如 age >= 18

Datalog Rules

这里实际上定义了一条规则，即如果 body 中所包含的所有 atom 都为 true，那么可以推出 head（由 atom构成）也为 true。

上图给出了更为详细的解释，在上图中下方的例子中给出了一个例子，首先确定筛选的范围为 Age(person, age)的元组， 同时给出了 age >= 18 这一限制条件 ，下图给出了更为详细的解释。

即考虑到所有变量值的组合，并挑选出所有满足条件的元组，最后得到结果，最后满足条件的总共有三个人 Xiaoming，Xiaohong，Abao。

这里也给出了 datalog 的核心 Datalog program = Facts + Rules，即一个 datalog 程序可以理解为是一系列 Facts 和 Rules 构成。

EDB and IDB Predicates

在 datalog 中将 predicate 分为了两类，一种是 EDB(extensional database)，简单来理解就是我们初始的输入，其关系是不可变的。另外一种是 IDB(intensional database)，由于在 datalog 程序中我们还可能会生成其他的 predicate，如前面例子中的 Adult，因此我们将这类输出的 predicate 记为 IDB。

前面提到在 datalog 中 , 表示逻辑与，同理逻辑或用 ; 表示，这两者的优先级同其他编程语言一样，与 > 或。

有与或那么同时也有非。

Recursion

datalog 拥有其他声明式语言没有的特性，那就是 datalog 支持递归查找

也正是因为其支持递归，从而可以将datalog用在指针分析中，这一点可以从后面的例子来看到。

同时需要注意的是，在定义 rule 的过程中，需要考虑到制定的 rule 是否正确。

在上面这个例子中，会导致 A(x) 所包含的元组无限，原因是由于 predicate 本身是受限的，因而 B(y) 是受限的，但是满足条件的 x 就会无限，从而 A(x) 的结果就是不受限的。

一开始有提到，datalog 的易读性和简洁性，但这些其实都离不开 datalog engine，负责实现推断的具体逻辑。

Pointer Analysis via Datalog

这里我们将 datalog 应用到 指针分析中

先把这几个概念统一到一起，定义 EDB，IDB，以及对应的 Rules，具体表示形式如下。

这里给出了一个例子来方便理解

按照规则然后顺序填表就行了

上图给出了除 call 之外的四条规则，并在右侧给出了对应的 datalog 实现。

example

这里比较重要，所以结合一个例子来说明过程，理解了这个过程其实也就理解了这一节（例子本身是比较容易理解的）

首先先根据源程序得到最初的几个 EDB，即 New，Store，Assign，Load，然后我们需要根据前面的规则来实现 VarPointsTo 和 FieldPointsTo 的建立。

找到程序中的 new 语句，然后执行命令，得到 b 和 c 对应的元组。

由于程序中还存在 assign 语句，所以还会执行第二段的 VarPointsTo 命令，而且这里还会用到前面的结果。

FieldPointsTo 的执行也是同理，最终返回的结果如下

由于前面没有加入 call 规则，所以下面这部分内容加入它，具体如下

注意这里引入了三个新的 EDB，即 VCALL，Dispatch，ThisVar，这些都是最后得到 Reachable 和 CallGraph 所需要的。

这里对几种 EDB 稍作解释

VCall(l:S, x:V, k:M)，其中 l 表示函数调用点，x 表示调用对象，k 表示具体所调用的方法。

Dispath(o:O, k:M, m:M)，其中 o 表示调用的对象，k 表示 o 所属的方法，m 表示其最后真正调用的方法。

ThisVar(m:M, this:V)，m 为所调用方法，this 就是方法所属的 this（doge）。

上图已经给出了第一行 rule 所对应的 datalog 语言，下面依次给出剩余部分

整理如下

这样我们就可以得到用datalog表示的整个程序的指针分析了。

Taint Analysis via Datalog

老样子还是明确 EDB 和 IDB 然后再制定 rule。

具体解释在上图中已明确解释。

同时也基于污点分析给出了这两种 rule 所对应的 datalog 表示形式。

这一节主要就是理解怎么将 datalog 加入到程序分析这一块当中。当然这里也给出了 datalog 这一语言作为程序分析的优缺点（注意：其优点反过来其实对应的就是它的缺点）

思考题