treeedb

árvore

treeedb facilita o início de escrever uma análise de programa de nível de origem no Soufflé Datalog. Primeiro, treeedb gera tipos e relações suflé que representam o AST de um programa. Em seguida, treeedb analisa o código -fonte e emite fatos que povoam essas relações.

Atualmente, treeedb suporta a análise desses idiomas:

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

Os analisadores e ASTs da treeedb são baseados em gramáticas de árvore de árvores, e é muito fácil adicionar suporte a qualquer idioma com uma gramática de uma árvore.

O nome treeedb é um portmanteau de "Sitter de Árvore" com "EDB", onde o EDB significa "Banco de Dados Extensional" e se refere ao conjunto de fatos em um programa de dados.

Instalação

Você precisará de dois artefatos para cada linguagem de programação que deseja analisar:

1. Um arquivo suflé com os tipos e relações que definem o AST
2. O executável que analisa essa linguagem e emite fatos

Por exemplo, para Java, eles são chamados treeedb-java.dl e treeedb-java , respectivamente.

Para realmente analisar algum código, você também precisará instalar o soufflé.

Instale de uma versão

Navegue até a liberação mais recente na página de lançamentos e faça o download dos artefatos relacionados ao idioma que você deseja analisar. Os executáveis ​​pré-criados estão estaticamente vinculados, mas atualmente estão disponíveis apenas para o Linux.

Construir a partir de crates.io

Você pode criar uma versão lançada em Crates.io. Você precisará do compilador de ferrugem e da ferramenta de construção de carga. Rustup facilita muito obtê -los. Então, para instalar as ferramentas para o idioma <LANG> , execute:

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

Isso instalará binários a ~/.cargo/bin . Para gerar o arquivo Datalog, execute o treeedbgen-souffle-<LANG> binário.

Infelizmente, os binários relacionados a Java ainda não estão disponíveis em Crates.io.

Construir a partir da fonte

Para construir a partir da fonte, você precisará do compilador de ferrugem e da ferramenta de construção de carga. Rustup facilita muito obtê -los.

Então, obtenha a fonte:

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

Finalmente, construa tudo:

cargo build --release

Você pode encontrar os binários treeedb-<LANG> no target/release . Para gerar o arquivo Datalog, execute o binário correspondente treeedbgen-souffle-<LANG> .

Exemplo: Analisando o código Java

Para acompanhar este exemplo, siga as instruções de instalação para Java. Em seguida, crie um arquivo java chamado Main.java :

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

(Os arquivos mostrados nesta seção também estão disponíveis em examples/java/ .)

Crie um arquivo de dados chamado const-binop.dl que inclua treeedb-java.dl e possui uma regra para encontrar expressões binárias com valor constante:

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

Gere os arquivos de entrada ( node.csv e field.csv ):

treeedb-java Main.java

Finalmente, execute a análise com suflé:

souffle const-binop.dl

Você verá algo assim:

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

Cavando mais fundo

Para ver que tipo e nomes de relações estão disponíveis, consulte treeedb-<LANGUAGE>.dl . Se não for evidente a que parte do idioma um determinado tipo ou relação corresponde, dê uma olhada na gramática da árvore-sitter (por exemplo, Grammar.js no repositório de Java).

Motivação e comparação com outras ferramentas

Antes de escrever uma análise do programa no Datalog, você precisa descobrir (1) como representar o programa como relações e (2) como ingerir programas nessa representação. Os projetos de datalog de última geração fazem tudo isso "manualmente":

• O CCLYZER ++ possui um diretório de "esquema" (1) e o FactGenerator (2).
• O DOOP tem um grande arquivo.dl (1) e uma variedade de geradores (2).
• DDISASM possui o decodificador GTIRB (2).
• Securify possui analysis-input.dl (1).

A escrita dessas representações e as ferramentas de ingestão realiza um tempo valioso e distrai o trabalho de escrever análises. treeedb pretende automatizá -lo, encaixando -se no mesmo nicho que essas ferramentas.

Estrutura do repositório

• treeedb : gerar fatos de dados de datalog das árvores de análise de árvores
• treeedb-c : Gere fatos do Datalog a partir do código-fonte C
• treeedb-csharp : Gere fatos de dados do Datalog a partir do código-fonte C#
• treeedbgen : análise de nó-de forma
• treeedbgen-souffle : gerar tipos e relações de suflê de gramáticas de árvore-sibra
• treeedbgen-souffle-c : gerar tipos e relações de suflê a partir da gramática C Tree-sitter
• treeedbgen-souffle-csharp : gerar tipos de suflê e relações da gramática C# Tree-sitter
• treeedbgen-souffle-java : gerar tipos e relações suflé da gramática Java-Setter
• treeedbgen-souffle-javascript : gerar tipos de suflê e relações a partir da gramática Javascript-Sitter
• treeedbgen-souffle-rust : gerar tipos e relações de suflê da gramática da árvore da árvore de ferrugem
• treeedbgen-souffle-souffle : gerar tipos e relações de suflê a partir da gramática de suflê-sibra de árvore
• treeedbgen-souffle-swift : gerar tipos de suflê e relações da gramática Swift Tree-sitter
• treeedb-java : gerar fatos de dados do Java Código
• treeedb-javascript : Gere fatos do Datalog a partir do código-fonte JavaScript
• treeedb-rust : Gere fatos do Datalog do código-fonte da ferrugem
• treeedb-souffle : Gere fatos do Datalog a partir do código fonte de Soufflé
• treeedb-swift : Gere fatos do Datalog a partir do código-fonte Swift

Contribuindo

Obrigado pelo seu interesse no treeedb ! Congratulamo -nos com todos os tipos de contribuições. Sinta -se à vontade para arquivar, emitir ou abrir uma solicitação de tração.

Adicionando um idioma

Conforme explicado na instalação, existem duas ferramentas envolvidas no suporte à análise de cada linguagem de programação: uma para gerar tipos e relações suflê (por exemplo, treeedbgen-souffle-c ) e outra para analisar o idioma que está sendo analisado e emite fatos (por exemplo, treeedb-c ).

Para adicionar um novo idioma:

• Crie novos diretórios treeedb-<LANG> e treeedbgen-souffle-<LANG> com a mesma estrutura que uma existente (pode ser mais fácil copiar apenas as existentes recursivamente).
• Adicione os novos diretórios à Cargo.toml de nível superior.toml.
• Adicione o idioma a .github/workflows/release.yml copiando e modificando linhas existentes para outros idiomas.

Veja PR #9 para um exemplo completo.

O script ./scripts/add-language.sh automatiza algumas dessas etapas-mas não é necessariamente uma solução de chave. Exemplo de uso:

bash scripts/add-language.sh python Python