treeedb

treeedb makes it easier to start writing a source-level program analysis in Soufflé Datalog. First, treeedb generates Soufflé types and relations that represent a program's AST. Then, treeedb parses source code and emits facts that populate those relations.

treeedb currently supports analysis of these languages:

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

treeedb's parsers and ASTs are based on tree-sitter grammars, and it's very easy to add support for any language with a tree-sitter grammar.

The name treeedb is a portmanteau of "tree-sitter" with "EDB", where EDB stands for "extensional database" and refers to the set of facts in a Datalog program.

Installation

You'll need two artifacts for each programming language you want to analyze:

1. A Soufflé file with the types and relations defining the AST
2. The executable that parses that language and emits facts

For instance, for Java these are called treeedb-java.dl and treeedb-java, respectively.

To actually analyze some code, you'll also need to install Soufflé.

Install From a Release

Navigate to the most recent release on the releases page and download the artifacts related to the language you want to analyze. The pre-built executables are statically linked, but are currently only available for Linux.

Build From crates.io

You can build a released version from crates.io. You'll need the Rust compiler and the Cargo build tool. rustup makes it very easy to obtain these. Then, to install the tools for the language <LANG>, run:

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

This will install binaries to ~/.cargo/bin. To generate the Datalog file, run the treeedbgen-souffle-<LANG> binary.

Unfortunately, the Java-related binaries are not yet available on crates.io.

Build From Source

To build from source, you'll need the Rust compiler and the Cargo build tool. rustup makes it very easy to obtain these.

Then, get the source:

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

Finally, build everything:

cargo build --release

You can find the treeedb-<LANG> binaries in target/release. To generate the Datalog file, run the corresponding treeedbgen-souffle-<LANG> binary.

Example: Analyzing Java Code

To follow along with this example, follow the installation instructions for Java. Then, create a Java file named Main.java:

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

(The files shown in this section are also available in examples/java/.)

Create a Datalog file named const-binop.dl that includes treeedb-java.dl and has a rule to find constant-valued binary expressions:

#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)

Generate the input files (node.csv and field.csv):

treeedb-java Main.java

Finally, run the analysis with Soufflé:

souffle const-binop.dl

You'll see something like this:

---------------
const_binop
===============
94001952741472
===============
---------------
show_const_binop
===============
2 + 2
===============

Digging Deeper

To see what type and relation names are available, look at treeedb-<LANGUAGE>.dl. If it's not evident which part of the language a given type or relation corresponds to, take a look at the tree-sitter grammar (e.g. grammar.js in the tree-sitter-java repo for Java).

Motivation and Comparison to Other Tools

Before writing a program analysis in Datalog, you need to figure out (1) how to represent the program as relations, and (2) how to ingest programs into that representation. State-of-the-art Datalog projects do all this "by hand":

• cclyzer++ has a "schema" directory (1) and the FactGenerator (2).
• Doop has a big imports.dl file (1) and a variety of generators (2).
• ddisasm has the gtirb-decoder (2).
• securify has analysis-input.dl (1).

Writing these representations and ingestion tools takes up valuable time and distracts from the work of writing analyses. treeedb aims to automate it, fitting in the same niche as these tools.

Repository Structure

• treeedb: Generate Datalog facts from tree-sitter parse trees
• treeedb-c: Generate Datalog facts from C source code
• treeedb-csharp: Generate Datalog facts from C# source code
• treeedbgen: Parse node-types.json from a tree-sitter grammar
• treeedbgen-souffle: Generate Soufflé types and relations from tree-sitter grammars
• treeedbgen-souffle-c: Generate Soufflé types and relations from the C tree-sitter grammar
• treeedbgen-souffle-csharp: Generate Soufflé types and relations from the C# tree-sitter grammar
• treeedbgen-souffle-java: Generate Soufflé types and relations from the Java tree-sitter grammar
• treeedbgen-souffle-javascript: Generate Soufflé types and relations from the JavaScript tree-sitter grammar
• treeedbgen-souffle-rust: Generate Soufflé types and relations from the Rust tree-sitter grammar
• treeedbgen-souffle-souffle: Generate Soufflé types and relations from the Soufflé tree-sitter grammar
• treeedbgen-souffle-swift: Generate Soufflé types and relations from the Swift tree-sitter grammar
• treeedb-java: Generate Datalog facts from Java source code
• treeedb-javascript: Generate Datalog facts from JavaScript source code
• treeedb-rust: Generate Datalog facts from Rust source code
• treeedb-souffle: Generate Datalog facts from Soufflé source code
• treeedb-swift: Generate Datalog facts from Swift source code

Contributing

Thank you for your interest in treeedb! We welcome and appreciate all kinds of contributions. Please feel free to file and issue or open a pull request.

Adding a Language

As explained in Installation, there are two tools involved in supporting analysis of each programming language: One to generate Soufflé types and relations (e.g., treeedbgen-souffle-c), and another to parse the language being analyzed and emit facts (e.g., treeedb-c).

To add a new language:

• Create new directories treeedb-<LANG> and treeedbgen-souffle-<LANG> with the same structure as an existing one (it might be easiest to just recursively copy existing ones).
• Add the new directories to the top-level Cargo.toml.
• Add the language to .github/workflows/release.yml by copying and modifying existing lines for other languages.

See PR #9 for a complete example.

The script ./scripts/add-language.sh automates a few of these steps - but it is not necessarily a turn-key solution. Usage example:

bash scripts/add-language.sh python Python