Este é um cross-post do post de blog da LLVM LLVM atende code property Graphs

O cpg (code property graph, gráfico de propriedade de código) é uma estrutura de dados projetada para minerar grandes bases de código para exemplos de padrões de programação através de uma linguagem de consulta específica de domínio. Foi introduzido pela primeira vez no processo da conferência IEEE Segurança e Privacidade em 2014 (publicação, PDF) no contexto da descoberta de vulnerabilidades no código do sistema C e no kernel Linux em particular. As ideias centrais da abordagem são as seguintes:

  • o CPG combina várias representações do programa em uma
  • o CPG é armazenado em um banco de dados gráfico
  • o banco de dados gráfico vem com um DSL permitindo atravessar e consultar o CPG

Atualmente, a infraestrutura CPG é suportada por várias ferramentas:

  • Ocular - uma ferramenta proprietária de análise de código que suporta linguagens Java, Scala, C#, Go, Python e JavaScript
  • Joern - uma contrapartida de código aberto do Ocular apoiando C e C++
  • Pluma - uma ferramenta de código aberto que suporta o Java Bytecode

Este artigo apresenta a implementação de código aberto do ShiftLeft de llvm2cpg - uma ferramenta autônoma que traz suporte ao LLVM Bitcode para o Joern. Mas antes de entrarmos em detalhes, digamos mais algumas palavras sobre CPG e Joern.

Gráfico de propriedade de código

A ideia central do CPG é que diferentes representações clássicas do programa sejam incorporadas a um gráfico de propriedade, uma única estrutura de dados que contém informações sobre a sintaxe, controle e fluxo de dados intra-processuais do programa.

Graficamente falando, a seguinte peça de código:

void foo() {
  int x = source();
  if (x < MAX) {
    int y = 2 * x;
    sink(y);
  }
}

combina essas três representações diferentes:

Diferentes representações do programa

em uma única representação - Code Property Graph:

Gráfico de propriedade de código

Joern

O gráfico de propriedade é armazenado em um banco de dados gráfico e tornado acessível através de uma linguagem específica de domínio (DSL) para identificar padrões de programação com base em um DSL para travessias de gráficos. A linguagem de consulta permite uma transição perfeita entre as representações originais do código, possibilitando combinar aspectos do código a partir de diferentes pontos de vista que essas representações oferecem.

Uma das principais interfaces dos gráficos de propriedade de código é uma ferramenta chamada Joern. Ele fornece o DSL mencionado e permite consultar o CPG para descobrir propriedades específicas de um programa. Aqui estão alguns exemplos do DSL do Joern:

joern> cpg.typeDecl.name.p
List[String] = List("ANY", "int", "void")

joern> cpg.method.name.p
List[String] = List(
  "foo",
  "<operator>.multiplication",
  "source",
  "<operator>.lessThan",
  "<operator>.assignment",
  "sink"
)
joern> cpg.method("foo").ast.isControlStructure.code.p
List[String] = List("if (x < MAX)")

joern> cpg.method("foo").ast.isCall.map(c => c.file.name.head + ":" + c.lineNumber.get + "  " + c.name + ": " + c.code).p
List[String] = List(
  "main.c:2  <operator>.assignment: x = source()",
  "main.c:2  source: source()",
  "main.c:3  <operator>.lessThan: x < MAX",
  "main.c:4  <operator>.assignment: y = 2 * x",
  "main.c:4  <operator>.multiplication: 2 * x",
  "main.c:5  sink: sink(y)"
)

Além do DSL, o Joern vem com um rastreador de fluxo de dados que permite consultas mais sofisticadas, como “existe um malloc controlado pelo usuário no programa?”

O DSL é muito mais poderoso do que no exemplo, mas isso está fora de alcance deste artigo. Por favor, consulte a documentação para saber mais.

LLVM e CPG

Esta parte é dividida em duas partes menores: a primeira abrange alguns detalhes de implementação, a segunda mostra um exemplo de como usar . Se você não estiver interessado na implementação - role para baixo :)llvm2cpg

Detalhes da implementação

Quando decidimos adicionar suporte llvm para CPG, uma das primeiras perguntas foi: como mapear a representação do bitcode no CPG?

Nós tomamos uma abordagem simples - vamos fingir que a representação ssa é apenas um programa de origem plana. Em outras palavras, o bitcode a seguir

define i32 @sum(i32 %a, i32 %a) {
  %r = add nsw i32 %a, %b
  ret i32 %r
}

pode ser visto como um programa C:

i32 sum(i32 a, i32 b) {
  i32 r = add(a, b);
  return r;
}

Do ponto de vista de alto nível, a abordagem é simples, mas há alguns pequenos detalhes que tivemos que superar.

Semântica de instrução

Podemos mapear algumas das instruções LLVM de volta para as operações internas do CPG. Aqui estão alguns exemplos:

  • add, fadd -> <operator>.addition
  • bitcast -> <operator>.cast
  • fcmp eq, icmp eq -> <operator>.equals
  • urem, , sremfrem -> <operator>.modulo
  • getelementptr -> uma combinação de , , e dependendo dos tipos subjacentes do gep operand<operator>.pointerShift<operator>.indexAccess<operator>.memberAccess

A maioria deles tem semântica especial, que desempenha um papel crucial nos rastreadores de fluxo de dados embutidos joern e ocular.<operator>.*

Infelizmente, nem todas as instruções LLVM têm um operador correspondente no CPG. Nesses casos, tivemos que voltar às chamadas de funcionamento. Por exemplo:

  • select i1 %cond, i32 %v1, i32 %v3 transforma-se em select(cond, v1, v2)
  • atomicrmw add i32* %ptr, i32 1 transforma-se em (o mesmo para qualquer outro operador)atomicrmwAdd(ptr, 1)atomicrmw
  • fneg float %val transforma-se em fneg(val)

A única instrução que não conseguimos mapear para o CPG é: o CPG não tem um conceito de nó Phi. Tivemos que eliminar instruções usando máquinas.phiphireg2mem

Redundância

Para um pequeno programa C

int sum(int a, int b) {
  return a + b;
}

Clang emite um monte de instruções redundantes por padrão

define i32 @sum(i32 %0, i32 %1) {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  store i32 %0, i32* %3, align 4
  store i32 %1, i32* %4, align 4
  %5 = load i32, i32* %3, align 4
  %6 = load i32, i32* %4, align 4
  %7 = add nsw i32 %5, %6
  ret i32 %7
}

em vez de uma versão mais concisa

define i32 @sum(i32 %0, i32 %1) {
  %3 = add nsw i32 %1, %0
  ret i32 %3
}

Em geral, isso não é um problema, mas adiciona mais complexidade para o rastreador de fluxo de dados e aumenta desnecessariamente o tamanho do gráfico. Uma das considerações foi executar otimizações antes de emitir CPG para o bitcode. Ainda assim, no final, decidimos descarregar este trabalho para um usuário final: se você quiser menos instruções, então aplique as otimizações manualmente antes de emitir o CPG.

Tipo Igualdade

A outra questão está relacionada com a forma como o LLVM lida com os tipos. Se dois módulos no mesmo contexto usarem a mesma estrutura com o mesmo nome, o LLVM renomeia a outra estrutura para evitar colisões de nomes. Por exemplo

; Module1
%struct.Point = type { i32, i32 }

e

; Module 2
%struct.Point = type { i32, i32 }

quando carregado no mesmo contexto produzem dois tipos

%struct.Point = type { i32, i32 }
%struct.Point.1 = type { i32, i32 }

Queríamos desduplicar esses tipos para uma melhor experiência do usuário e apenas emitir no gráfico final.Point

A solução óbvia foi considerar duas estruturas com nomes “semelhantes” e o mesmo layout para ser o mesmo. No entanto, não pudemos confiar no porque, apesar do nome, produz resultados enganosos.llvm::StructType::isLayoutIdentical

De acordo com as estruturas e tem layout idêntico, mas não são.llvm::StructType::isLayoutIdenticalPointPairPointWrapPairWrap

; these two have identical layout
%Point = type { i32, i32 }
%Pair = type { i32, i32 }

; these two DO NOT have identical layout
%PointWrap = type { %Point }
%PairWrap = type { %Pair }

Isso acontece porque determina a igualdade com base nos ponteiros. Ou seja, se todos os elementos de estrutura são idênticos, então o layout é idêntico. Também significava que não poderíamos usar essa abordagem para comparar tipos de diferentes contextos LLVM. Tivemos que lançar nossa solução personalizada baseada no Tree Automata para resolver esse problema.llvm::StructType::isLayoutIdentical

Há poucos detalhes, mas o artigo está ficando mais longo do que precisa ser. Então vamos ver como usar com Joern.llvm2cpg

Exemplo

Uma vez que você tem Joern e llvm2cpg instalados, o uso é simples:

  1. Converta um programa em LLVM Bitcode
  2. Emitir CPG
  3. Carregue o CPG no Joern e inicie a análise

Aqui estão os passos codificados:

$ cat main.c
extern int MAX;
extern int source();
extern void sink(int);
void foo() {
  int x = source();
  if (x < MAX) {
    int y = 2 * x;
    sink(y);
  }
}
$ clang -S -emit-llvm -g -O1 main.c -o main.ll
$ llvm2cpg -output=/tmp/cpg.bin.zip main.ll

Agora você tem o CPG salvo no qual você pode carregar em Joern e descobrir se há um fluxo da função para o :/tmp/cpg.bin.zipsourcesink

$ joern
joern> importCpg("/tmp/cpg.bin.zip")
joern> run.ossdataflow
joern> def source = cpg.call("source")
joern> def sink = cpg.call("sink").argument
joern> sink.reachableByFlows(source).p
List[String] = List(
  """_____________________________________________________
| tracked               | lineNumber| method| file   |
|====================================================|
| source                | 5         | foo   | main.c |
| <operator>.assignment | 5         | foo   | main.c |
| <operator>.lessThan   | 6         | foo   | main.c |
| <operator>.shiftLeft  | 7         | foo   | main.c |
| <operator>.shiftLeft  | 7         | foo   | main.c |
| <operator>.assignment | 7         | foo   | main.c |
| sink                  | 8         | foo   | main.c |
"""
)

Que de fato existe!

Conclusão

Para concluir, vamos delinear algumas das vantagens e restrições implícitas pelo LLVM Bitcode:

  • a “superfície” da língua LLVM é menor que a de C e C++
  • muitos detalhes de alto nível não existem no nível de IR
  • o programa deve ser compilado, limitando assim a gama de programas que se pode analisar com Joern

Aqui você pode encontrar mais tutoriais e informações.

Se você receber alguma dúvida, sinta-se livre para ping Fabs ou Alex no Twitter, ou melhor vir para o bate-papo Joern.

Artigo Original