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:
- A Soufflé file with the types and relations defining the AST
- 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 treestreeedb-c
: Generate Datalog facts from C source codetreeedb-csharp
: Generate Datalog facts from C# source codetreeedbgen
: Parse node-types.json from a tree-sitter grammartreeedbgen-souffle
: Generate Soufflé types and relations from tree-sitter grammarstreeedbgen-souffle-c
: Generate Soufflé types and relations from the C tree-sitter grammartreeedbgen-souffle-csharp
: Generate Soufflé types and relations from the C# tree-sitter grammartreeedbgen-souffle-java
: Generate Soufflé types and relations from the Java tree-sitter grammartreeedbgen-souffle-javascript
: Generate Soufflé types and relations from the JavaScript tree-sitter grammartreeedbgen-souffle-rust
: Generate Soufflé types and relations from the Rust tree-sitter grammartreeedbgen-souffle-souffle
: Generate Soufflé types and relations from the Soufflé tree-sitter grammartreeedbgen-souffle-swift
: Generate Soufflé types and relations from the Swift tree-sitter grammartreeedb-java
: Generate Datalog facts from Java source codetreeedb-javascript
: Generate Datalog facts from JavaScript source codetreeedb-rust
: Generate Datalog facts from Rust source codetreeedb-souffle
: Generate Datalog facts from Soufflé source codetreeedb-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>
andtreeedbgen-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