NESA: Relational Neuro-Symbolic Static Program Analysis

Resumo Técnico: NESA – Análise Estática Neuro-Simbólica Relacional

1. O Problema

A análise estática de programas é fundamental para otimização, detecção de bugs e depuração. No entanto, sua adoção na indústria é limitada por duas barreiras principais:

1. Dependência de Compilação: A maioria das ferramentas tradicionais (como FlowDroid e Infer) requer a compilação do código fonte para representações intermediárias (IR). Isso impede a análise em ambientes de desenvolvimento onde o código está incompleto ou em constante mudança. Além disso, a compatibilidade com diferentes sistemas de build e versões de compiladores é complexa.
2. Falta de Personalização: Ferramentas existentes oferecem suporte limitado à customização para requisitos específicos dos desenvolvedores. Adaptá-las exige conhecimento profundo de infraestrutura de compiladores e linguagens de consulta complexas (como Datalog ou CodeQL), criando uma barreira de entrada alta.

Embora os Grandes Modelos de Linguagem (LLMs) ofereçam uma alternativa promissora para análise sem compilação e altamente customizável, eles sofrem de alucinações (geração de informações incorretas), o que resulta em altos índices de falsos positivos e negativos, tornando-os pouco confiáveis para tarefas de análise estática rigorosa.

2. Metodologia: A Abordagem NESA

O NESA (Neuro-Symbolic Static Program Analysis) propõe uma abordagem neuro-simbólica composicional que combina a precisão da análise baseada em parsing (sintática) com a flexibilidade semântica dos LLMs, mitigando as alucinações através de três pilares principais:

• Linguagem de Política de Análise (Analysis Policy Language):

  • Utiliza uma forma restrita de Datalog para decompor problemas complexos de análise estática em subproblemas menores.
  • Define três tipos de relações:
    • Relações Simbólicas ($R_S$): Capturam propriedades sintáticas (ex: localização de expressões, dependências de controle, argumentos de funções) derivadas deterministicamente de uma árvore de sintaxe abstrata (AST) via parser.
    • Relações Neurais ($R_N$): Capturam propriedades semânticas complexas (ex: dependências de dados, propagação de taint) que são difíceis de formalizar sintaticamente. Estas são preenchidas via prompting de LLMs.
    • Relações Intensionais ($R_I$): O resultado final da análise, derivado das relações anteriores.

• Estratégias de Mitigação de Alucinações:
  O NESA introduz duas técnicas inovadoras para reduzir o custo de tokens e as alucinações dos LLMs:

  1. Prompting Preguiçoso (Lazy Prompting): Em vez de solicitar ao LLM que preencha uma relação neural imediatamente, o sistema primeiro resolve as relações simbólicas e intensionais. Isso "vincula" (bound) os termos da relação neural, restringindo o espaço de busca do LLM. O LLM só é acionado quando o contexto é o mais restrito possível, focando em subproblemas gerenciáveis e reduzindo erros.
  2. Prompting Incremental (Incremental Prompting): Para evitar chamadas redundantes ao LLM durante a iteração até o ponto fixo (fixed-point), o sistema rastreia quais tuplas já foram processadas. O LLM só é chamado para gerar novas tuplas que ainda não existem na relação, evitando repetições desnecessárias.

• Construtores Confinados (Constrained Neural Constructors):
  O sistema seleciona automaticamente o "construtor neural" (o tipo de prompt) com maior aridade possível baseado nos termos já vinculados. Por exemplo, em vez de pedir ao LLM para listar todos os pares com dependência de dados (0-ary), ele pede para listar dependências para um par específico já identificado (2-ary), o que é estatisticamente mais preciso.

3. Contribuições Chave

1. Framework Neuro-Simbólico Relacional: Um novo paradigma que permite análise estática sem compilação e altamente customizável, onde os usuários definem políticas de análise usando Datalog e exemplos de few-shot em linguagem natural, sem precisar conhecer a infraestrutura do compilador.
2. Estratégias de Avaliação Otimizadas: A introdução de lazy prompting e incremental prompting para mitigar alucinações e reduzir custos computacionais, permitindo que LLMs sejam usados de forma confiável em tarefas de análise estática.
3. Desempenho Superior e Validado: Demonstração experimental de que o NESA atinge desempenho comparável ou superior às técnicas de ponta (SOTA), tanto em benchmarks padrão quanto em programas do mundo real, com um esforço de customização mínimo.

4. Resultados Experimentais

O NESA foi avaliado em tarefas de program slicing (fatiamento de programa) e detecção de bugs em diversos conjuntos de dados (Juliet Test Suite, TaintBench, projetos reais).

• Program Slicing:
  • Precisão: 91.50%, Recall: 84.61%, F1-Score: 0.88.
  • Superou o NS-Slicer (SOTA baseado em aprendizado de máquina) em 0.06 pontos de F1.
• Detecção de Bugs (Juliet Test Suite):
  • Desempenho consistente em 6 tipos de bugs (XSS, APT, DBZ, NPD, RE, UOWH).
  • Exemplo em XSS: Precisão de 98.95% e Recall de 94.00%.
  • Em comparação com end-to-end prompting (sem decomposição), o NESA superou significativamente os modelos GPT-3.5, GPT-4 e Claude em precisão e recall, especialmente em bugs que exigem raciocínio complexo sobre caminhos de execução.
• Cenários do Mundo Real:
  • TaintBench (Malware Android): Detectou 55 de 70 vulnerabilidades de taint, com F1 de 0.72, superando uma ferramenta industrial em 0.20 pontos de F1.
  • Projetos Reais (h3 e dynamips): O NESA identificou 13 bugs reais de vazamento de memória que foram confirmados e corrigidos pelos desenvolvedores. Ferramentas puramente baseadas em LLM (como Cursor) falharam em detectar esses bugs.
• Eficiência:
  • Embora o custo por caso seja maior que o prompting direto, o custo por bug verdadeiro detectado (normalizado pelo recall) é significativamente menor, tornando-o mais eficiente economicamente para detecção real.

5. Significado e Impacto

O NESA representa um avanço significativo na interseção entre Inteligência Artificial e Engenharia de Software:

• Democratização da Análise Estática: Remove a barreira da compilação e a necessidade de especialistas em compiladores, permitindo que desenvolvedores criem analisadores personalizados usando linguagem natural e exemplos simples.
• Viabilidade Prática de LLMs: Demonstra que é possível utilizar LLMs para tarefas críticas de segurança e análise de código sem sacrificar a precisão, desde que as alucinações sejam controladas através de métodos neuro-simbólicos rigorosos.
• Descoberta de Bugs Reais: A capacidade de encontrar bugs em código incompleto e em grandes projetos de produção, que outras ferramentas falharam em detectar, valida a utilidade prática da abordagem para o ciclo de vida de desenvolvimento de software moderno.

Em suma, o NESA redefine a análise estática ao torná-la acessível, adaptável e precisa, superando as limitações das abordagens puramente simbólicas e puramente neurais.