langston-barrett/treeedb
GitHub: langston-barrett/treeedb
treeedb 自动化将多语言 AST 转为 Soufflé Datalog 事实，填补程序分析与 Datalog 之间的生态位。
Stars: 82 | Forks: 12
# treeedb
`treeedb` 使在 [Soufflé Datalog][souffle] 中开始编写源代码级程序分析变得更加容易。
首先，`treeedb` 生成表示程序 AST 的 Soufflé 类型和关系。
然后，`treeedb` 解析源代码并生成用于填充这些关系的事实。
`treeedb` 目前支持以下语言的分析：
- Bash
- C
- C++
- C#
- Crystal
- Java
- JavaScript
- PHP
- Rust
- Soufflé
- Swift
`treeedb` 的解析器和 AST 基于 [tree-sitter][tree-sitter] 语法，
并且很容易为任何拥有 tree-sitter 语法的 [语言][tree-sitter-langs]
[添加支持](#adding-a-language)。
`treeedb` 这个名字是 “tree-sitter” 与 “EDB” 的混成词，
其中 EDB 代表 “extensional database”，指的是 Datalog 程序中的一组事实。
## 安装
要分析每种编程语言，你需要两个构件：
1. 一个 Soufflé 文件，其中包含定义 AST 的类型和关系
2. 一个解析该语言并生成事实的可执行文件
例如，对于 Java，它们分别叫做 `treeedb-java.dl` 和 `treeedb-java`。
要实际分析代码，你还需要 [安装 Soufflé][souffle-install]。
### 从发行版安装
导航到 [releases 页面][releases] 的最新版本，并下载与你想要分析的语言相关的构件。
预构建的可执行文件是静态链接的，但目前[仅][#3]适用于 Linux。
### 从 crates.io 构建
你可以从 [crates.io][crates-io] 构建发布版本。你需要 Rust 编译器以及 [Cargo][cargo] 构建工具。
[rustup][rustup] 可以轻松获取这些。然后，要安装语言 `` 的工具，运行：
```
cargo install treeedb- treeedbgen-souffle-
```
这会将二进制文件安装到 `~/.cargo/bin`。
要生成 Datalog 文件，运行 `treeedbgen-souffle-` 二进制文件。
不幸的是，与 Java 相关的二进制文件[尚未][#23]在 crates.io 上提供。
### 从源码构建
要从源码构建，你需要 Rust 编译器和 [Cargo][cargo] 构建工具。
[rustup][rustup] 可以轻松获取这些。
然后，获取源码：
```
git clone https://github.com/langston-barrett/treeedb
cd treeedb
```
最后，构建所有内容：
```
cargo build --release
```
你可以在 `target/release` 中找到 `treeedb-` 二进制文件。
要生成 Datalog 文件，运行对应的 `treeedbgen-souffle-` 二进制文件。
## 示例：分析 Java 代码
要跟随本示例，请按照 [Java 的安装说明][#installation] 进行操作。
然后，创建一个名为 `Main.java` 的 Java 文件：
```
class Main {
public static void main(String[] args) {
int x = 2 + 2;
}
}
```
（本节中的文件也位于 [`examples/java/`](./examples/java/) 中。）
创建一个名为 `const-binop.dl` 的 Datalog 文件，包含 `treeedb-java.dl` 并添加一条规则，用于查找常量值的二元表达式：
```
#include "treeedb-java.dl"
.decl const_binop(expr: JavaBinaryExpression)
const_binop(expr) :-
java_binary_expression(expr),
java_binary_expression_left_f(expr, l),
java_binary_expression_right_f(expr, r),
java_decimal_integer_literal(l),
java_decimal_integer_literal(r).
.decl show_const_binop(text: JavaNodeText)
show_const_binop(text) :-
const_binop(expr),
java_node_text(expr, text).
.output const_binop(IO=stdout)
.output show_const_binop(IO=stdout)
```
生成输入文件（`node.csv` 和 `field.csv`）：
```
treeedb-java Main.java
```
最后，使用 Soufflé 运行分析：
```
souffle const-binop.dl
```
你会看到类似如下的输出：
```
---------------
const_binop
===============
94001952741472
===============
---------------
show_const_binop
===============
2 + 2
===============
```
### 深入探索
要查看可用的类型和关系名称，请查看 `treeedb-.dl`。
如果不清楚某个类型或关系对应语言的哪一部分，
可以参考 tree-sitter 语法（例如，Java 可查看 [tree-sitter-java 仓库中的 grammar.js][java-grammar]）。
## 动机与与其他工具的对比
在编写 Datalog 程序分析之前，你需要弄清楚两件事：
(1) 如何将程序表示为关系；(2) 如何将程序导入该表示中。
目前的 Datalog 项目都是“手工”完成这些步骤：
- [cclyzer++][cclyzerpp] 有一个 ["schema" 目录][cclyzerpp-schema]（1）和
[FactGenerator][cclyzerpp-fact-generator]（2）。
- [Doop][doop] 有一个庞大的 [imports.dl][doop-imports] 文件（1）和
[多种生成器][doop-gen]（2）。
- [ddisasm][ddisasm] 有 [gtirb-decoder][ddisasm-gtirb-decoder]（2）。
- [securify][securify] 有 [`analysis-input.dl`][securify-input]（1）。
手工编写这些表示和导入工具会占用大量时间，并分散编写分析本身的精力。
`treeedb` 旨在自动化这些过程，填补与这些工具相同的生态位。
## 仓库结构
- [`treeedb`](./treeedb)：从 tree-sitter 解析树生成 Datalog 事实
- [`treeedb-c`](./treeedb-c)：从 C 源代码生成 Datalog 事实
- [`treeedb-cpp`](./treeedb-cpp)：从 C++ 源代码生成 Datalog 事实
- [`treeedb-crystal`](./treeedb-crystal)：从 Crystal 源代码生成 Datalog 事实
- [`treeedb-csharp`](./treeedb-csharp)：从 C# 源代码生成 Datalog 事实
- [`treeedb-java`](./treeedb-java)：从 Java 源代码生成 Datalog 事实
- [`treeedb-javascript`](./treeedb-javascript)：从 JavaScript 源代码生成 Datalog 事实
- [`treeedb-php`](./treeedb-php)：从 PHP 源代码生成 Datalog 事实
- [`treeedb-rust`](./treeedb-rust)：从 Rust 源代码生成 Datalog 事实
- [`treeedb-souffle`](./treeedb-souffle)：从 Soufflé 源代码生成 Datalog 事实
- [`treeedb-swift`](./treeedb-swift)：从 Swift 源代码生成 Datalog 事实
- [`treeedbgen`](./treeedbgen)：从 tree-sitter 语法解析 node-types.json
- [`treeedbgen-souffle`](./treeedbgen-souffle)：从 tree-sitter 语法生成 Soufflé 类型和关系
- [`treeedbgen-souffle-c`](./treeedbgen-souffle-c)：从 C tree-sitter 语法生成 Soufflé 类型和关系
- [`treeedbgen-souffle-cpp`](./treeedbgen-souffle-cpp)：从 C++ tree-sitter 语法生成 Soufflé 类型和关系
- [`treeedbgen-souffle-crystal`](./treeedbgen-souffle-crystal)：从 Crystal tree-sitter 语法生成 Soufflé 类型和关系
- [`treeedbgen-souffle-csharp`](./treeedbgen-souffle-csharp)：从 C# tree-sitter 语法生成 Soufflé 类型和关系
- [`treeedbgen-souffle-java`](./treeedbgen-souffle-java)：从 Java tree-sitter 语法生成 Soufflé 类型和关系
- [`treeedbgen-souffle-javascript`](./treeedbgen-souffle-javascript)：从 JavaScript tree-sitter 语法生成 Soufflé 类型和关系
- [`treeedbgen-souffle-php`](./treeedbgen-souffle-php)：从 PHP tree-sitter 语法生成 Soufflé 类型和关系
- [`treeedbgen-souffle-rust`](./treeedbgen-souffle-rust)：从 Rust tree-sitter 语法生成 Soufflé 类型和关系
- [`treeedbgen-souffle-souffle`](./treeedbgen-souffle-souffle)：从 Soufflé tree-sitter 语法生成 Soufflé 类型和关系
- [`treeedbgen-soule-swift`](./treeedbgen-souffle-swift)：从 Swift tree-sitter 语法生成 Soufflé 类型和关系
### 添加新语言
如 [安装说明][#installation] 所述，支持每种语言分析需要两个工具：
一个用于生成 Soufflé 类型和关系（例如 `treeedbgen-souffle-c`），
另一个用于解析待分析语言并生成事实（例如 `treeedb-c`）。
要添加新语言：
- 创建新目录 `treeedb-` 和 `treeedbgen-souffle-`，
结构与现有目录相同（最简单的方式是递归复制现有目录）。
- 将新目录添加到顶层 [`Cargo.toml`](Cargo.toml) 中。
- 通过复制并修改其他语言的行，将该语言添加到 `.github/workflows/release.yml`。
请参考 [PR #9][#9] 获取完整示例。
脚本 [`./scripts/add-language.sh`](`./scripts/add-language.sh`) 可以自动化其中部分步骤——
但它不一定是一个开箱即用的解决方案。
使用示例：
```
bash scripts/add-language.sh python Python
```
标签：Bash, C, C++, CMS安全, Crystal, Datalog facts, EDB, extensional database, IPv6支持, JavaScript, odt, OpenVAS, PHP, program analysis, Rust, Soufflé Datalog, Swift, treeedb, tree-sitter, 事实生成, 云安全监控, 代码分析工具, 关系生成, 可视化界面, 开源分析工具, 抽象语法树, 数据库, 数据擦除, 树解析, 源代码分析, 源码分析, 类型生成, 编译器前端, 网络流量审计, 语法树, 跨语言分析, 通知系统, 静态分析