treeedb

treeedb 使编写源代码级别的程序分析在 Soufflé Datalog 中变得更容易。首先，treeedb 生成 Soufflé 类型和相关，这些类型和关系表示程序抽象语法树（AST）。然后，treeedb 解析源代码并生成填充这些关系的事实。

treeedb 目前支持以下语言的分析

• C
• C#
• Java
• JavaScript
• Rust
• Soufflé
• Swift

treeedb 的解析器和 AST 基于 tree-sitter 语法，并且很容易 添加对任何具有 tree-sitter 语法的语言的支持。

treeedb 的名称是 "tree-sitter" 和 "EDB" 的组合，其中 EDB 代表 "扩展数据库"，指的是 Datalog 程序中的事实集。

安装

对于您想要分析的每种编程语言，您需要两个工件

1. 一个包含定义 AST 类型和相关关系的 Soufflé 文件
2. 解析该语言并生成事实的可执行文件

例如，对于 Java，这些分别称为 treeedb-java.dl 和 treeedb-java。

要实际分析一些代码，您还需要 安装 Soufflé。

从发行版安装

转到 发行版页面 上的最新发行版，下载与您想要分析的语言相关的工件。预构建的可执行文件是静态链接的，但目前仅适用于 Linux。

从 crates.io 构建

您可以从 crates.io 构建发行版。您需要 Rust 编译器和 Cargo 构建工具。 rustup 使获取这些变得非常容易。然后，要安装语言 <LANG> 的工具，运行

cargo install treeedb-<LANG> treeedbgen-souffle-<LANG>

这将安装二进制文件到~/.cargo/bin。要生成Datalog文件，运行treeedbgen-souffle-<LANG>二进制文件。

从源码构建

要从源码构建，您需要Rust编译器和Cargo构建工具。rustup使获取这些变得非常容易。

然后，获取源码

git clone https://github.com/langston-barrett/treeedb
cd treeedb

最后，构建所有内容

cargo build --release

您可以在target/release中找到treeedb-<LANG>二进制文件。要生成Datalog文件，运行相应的treeedbgen-souffle-<LANG>二进制文件。

示例：分析Java代码

要跟随这个示例，请按照Java的安装说明进行操作。然后，创建一个名为Main.java的Java文件

class Main {
    public static void main(String[] args) {
        int x = 2 + 2;
    }
}

(本节中显示的文件也位于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-<LANGUAGE>.dl。如果尚不清楚给定的类型或关系对应于语言中的哪个部分，请查看tree-sitter语法（例如，Java中的tree-sitter-java存储库中的grammar.js）。

动机与其他工具的比较

在用Datalog编写程序分析之前，您需要确定（1）如何将程序表示为关系，以及（2）如何将程序摄入到该表示中。最先进的Datalog项目都是通过“手工”来完成这些的。

• cclyzer++有一个“模式”目录（1）和FactGenerator（2）。
• Doop有一个大的imports.dl文件（1）和各种生成器（2）。
• ddisasm有gtirb-decoder（2）。
• securify有analysis-input.dl（1）。

编写这些表示和摄取工具需要宝贵的时间，并会分散编写分析工作的注意力。《treeedb》旨在自动化这个过程，与这些工具处于相同的细分市场。

仓库结构

• treeedb：从 tree-sitter 解析树生成 Datalog 事实
• treeedb-c：从 C 源代码生成 Datalog 事实
• treeedb-csharp：从 C# 源代码生成 Datalog 事实
• treeedbgen：从 tree-sitter 语法解析 node-types.json
• treeedbgen-souffle：从 tree-sitter 语法生成 Soufflé 类型和相关关系
• treeedbgen-souffle-c：从 C tree-sitter 语法生成 Soufflé 类型和相关关系
• treeedbgen-souffle-csharp：从 C# tree-sitter 语法生成 Soufflé 类型和相关关系
• treeedbgen-souffle-java：从 Java tree-sitter 语法生成 Soufflé 类型和相关关系
• treeedbgen-souffle-javascript：从 JavaScript tree-sitter 语法生成 Soufflé 类型和相关关系
• treeedbgen-souffle-rust：从 Rust tree-sitter 语法生成 Soufflé 类型和相关关系
• treeedbgen-souffle-souffle：从 Soufflé tree-sitter 语法生成 Soufflé 类型和相关关系
• treeedbgen-souffle-swift：从 Swift tree-sitter 语法生成 Soufflé 类型和相关关系
• treeedb-java：从 Java 源代码生成 Datalog 事实
• treeedb-javascript：从 JavaScript 源代码生成 Datalog 事实
• treeedb-rust：从 Rust 源代码生成 Datalog 事实
• treeedb-souffle：从 Soufflé 源代码生成 Datalog 事实
• treeedb-swift：从 Swift 源代码生成 Datalog 事实

贡献

感谢您对《treeedb》的关注！我们欢迎并感激各种形式的贡献。请随时提交问题或打开 pull request。

添加一种语言

如安装中所述，支持每种编程语言的分析涉及两种工具：一个用于生成 Soufflé 类型和相关关系（例如，treeedbgen-souffle-c），另一个用于解析被分析的语言并发出事实（例如，treeedb-c）。

要添加一种新语言

• 创建与现有目录结构相同的新目录 treeedb-<LANG> 和 treeedbgen--souffle-<LANG>（可能最简单的方法是递归复制现有的目录）。
• 将新目录添加到顶级 Cargo.toml。
• 通过复制和修改其他语言的现有行，将语言添加到 .github/workflows/release.yml。

bash scripts/add-language.sh python Python