Resumo Técnico: GRAF - Fuzzing Consciente de Grafos para Sistemas de Gerenciamento de Bancos de Dados em Grafo

1. Declaração do Problema

Sistemas de Gerenciamento de Bancos de Dados em Grafo (GDBMSs) são infraestruturas críticas para o gerenciamento de dados interconectados, mas seu teste permanece subexplorado em comparação com bancos de dados relacionais. Os métodos de teste existentes dependem primordialmente de testes diferenciais e metamórficos, que dependem de oráculos de consistência de resultados. Essas abordagens restringem os inputs a consultas que são comparáveis entre motores ou semanticamente transformáveis, o que estreita o espaço de entrada para consultas bem definidas que produzem resultados. Consequentemente, falhas de execução específicas do motor — como crashes, corrupção de memória e exaustão de recursos — permanecem insuficientemente exploradas.

O desenvolvimento de fuzzers dedicados para GDBMSs enfrenta dois desafios específicos:

1. Gerar Consultas Válidas e Estruturalmente Diversas: Consultas Cypher válidas devem satisfazer restrições sintáticas e semânticas complexas e interdependentes (ex: escopo de variáveis, compatibilidade de tipos e adesão ao esquema do grafo). Fuzzers genéricos de nível de byte corrompem a sintaxe, enquanto geradores baseados em gramática frequentemente produzem consultas estruturalmente simples que falham em exercitar a lógica profunda do motor.
2. Guiar a Exploração sob Execução Dependente de Topologia: O feedback de cobertura tradicional captura o fluxo de controle, mas falha em capturar comportamentos de fluxo de dados dependentes de topologia. A execução de consultas de grafo é altamente sensível a hubs, ciclos e profundidade de travessia; pequenas mudanças de parâmetros podem causar picos exponenciais de recursos (ex: o tempo de execução aumentando 320x) sem alterar os caminhos de fluxo de controle. Métodos existentes carecem de mecanismos de feedback para distinguir entre resultados vazios improdutivos, travessias caras e falhas anormais.

2. Metodologia: O Framework GRAF

Os autores propõem o GRAF, um framework de fuzzing orientado por feedback e de caixa-preta (black-box), projetado para enfrentar esses desafios. O GRAF opera inteiramente como uma caixa-preta, baseando-se em resultados visíveis externamente em vez de cobertura de código tradicional para orientação.

A. Geração de Consultas Consciente do Contexto de Grafo

O GRAF desacopla a estrutura abstrata da consulta do dado concreto do grafo para garantir validade enquanto mantém a diversidade.

• Geração de Esqueleto: Um Modelo de Linguagem de Grande Escala (LLM) sintetiza um conjunto de esqueletos Cypher parametrizados com combinações diversas de cláusulas e padrões de travessia. Esses esqueletos utilizam identificadores e placeholders padronizados, mas não contêm valores concretos.
• Resolução de Dependência em Cascata: Em vez de instanciação aleatória, o GRAF resolve os placeholders contra o estado ativo do grafo em três fases em cascata:
  1. Resolução de Topologia: Ele amostra rótulos de nós (node labels) e tipos de relacionamento baseando-se em metadados do esquema (ex: se um rótulo de origem é Customer, apenas relacionamentos de saída válidos como Order são selecionados).
  2. Resolução de Propriedade e Valor: Ele vincula chaves de propriedades e gera valores concretos (observados, de limite ou anômalos) compatíveis com os tipos de entidade.
  3. Alinhamento de Parâmetros Globais: Ele ajusta parâmetros globais (ex: LIMIT ou limites de travessia) proporcionalmente à escala do grafo para evitar timeouts imediatos.
     Este processo elimina violações sintáticas e semânticas antes da execução, garantindo que as consultas alcancem a lógica de otimização e execução.

B. Mutação de Consulta Guiada pelo Estado de Execução

O GRAF emprega um vetor de feedback dinâmico $F = \langle t, |R|, s \rangle$, onde $t$ é o tempo de execução, $|R|$ é o tamanho do resultado e $s$ é o status do sistema. Este feedback guia cinco operadores de mutação específicos de grafos:

• Mutação de Topologia: Insere, remove ou reconecta padrões.
• Mutação de Profundidade e Volume: Modula limites de caminho e configurações de LIMIT.
• Mutação de Predicado: Manipula expressões WHERE para alterar a seletividade.
• Inserção de Cláusula: Injeta componentes de pipeline (ex: WITH, agregações).
• Mutação de Valor: Substitui literais por valores de limite ou anômalos.

Estratégias de Feedback:

• Resultados Vazios: Se uma consulta retorna rapidamente sem resultados, o GRAF relaxa os predicados ou ajusta a topologia para garantir a materialização dos dados.
• Alto Custo/Timeouts: Para consultas próximas ao timeout, o GRAF penaliza a expansão de profundidade e favorece reduções limitadas para evitar explorações improdutivas.
• Terminações Anormais: Crashes ou OOMs (Out-of-Memory) disparam análise de prioridade e mutações localizadas para isolar a causa da falha.

3. Principais Contribuições

O artigo reivindica as seguintes contribuições:

1. Framework GRAF: Um fuzzer de caixa-preta que utiliza feedback de execução em vez de cobertura de código para testar diversos motores de GDBMS.
2. Estratégia de Geração Desacoplada: Uma abordagem inovadora que separa a estrutura abstrata (gerada via LLM) do dado concreto (resolvido via dependência em cascata), permitindo a geração de consultas complexas e válidas.
3. Mutação Guiada por Estado: Uma estratégia de mutação que adapta operadores com base no tempo de execução, tamanho do resultado e status do sistema para direcionar a exploração para a lógica profunda do motor.
4. Validação Empírica: Avaliação extensiva em seis GDBMSs demonstrando melhorias significativas em cobertura e descoberta de bugs.

4. Resultados Experimentais

Os autores avaliaram o GRAF contra três baselines (Dinkel, BUZZBEE e AFL++) em seis GDBMSs: Memgraph, FalkorDB, Neo4j, KuzuDB, NebulaGraph e RedisGraph.

• Cobertura de Código: O GRAF melhorou consistentemente a cobertura de linhas em 31,6% a 41,1% sobre o baseline mais forte em cada alvo. Ele cobriu significativamente mais linhas únicas, particularmente em regiões profundas de implementação, comparado aos baselines que se sobrepunham amplamente na lógica do parser de frontend.
• Validade de Consulta: O GRAF manteve uma taxa de consulta válida de 61,8% a 76,7%, significativamente maior que a do AFL++ (2%) e BUZZBEE (50-60%), embora ligeiramente inferior ao conservador Dinkel.
• Descoberta de Bugs:
  • O GRAF descobriu 34 bugs anteriormente desconhecidos nos seis sistemas.
  • 32 bugs foram confirmados pelos desenvolvedores, e 23 receberam identificadores CVE.
  • Em uma avaliação controlada de 12 horas, o GRAF disparou 25 bugs únicos, enquanto os três baselines combinados dispararam apenas 6.
  • Os bugs abrangeram componentes críticos, incluindo correspondência de padrões (pattern matching), expansão de caminho, agregação e gerenciamento de transações, com tipos incluindo falhas de segmentação (segmentation faults), uso após liberação (use-after-free), estouro de pilha (stack overflows) e falta de memória (out-of-memory errors).

5. Significância e Alegações

O artigo afirma que o GRAF demonstra a eficácia de desacoplar a estrutura da consulta do contexto de execução e utilizar feedback de execução externo para testar motores de banco de dados complexos. Ao abordar os desafios específicos de topologia de grafo e restrições semânticas, o GRAF consegue contornar a validação de frontend para testar a lógica de execução do backend. Os resultados sugerem que métricas de cobertura tradicionais são insuficientes para bancos de dados em grafo e que sinais de estado de execução (tempo, tamanho, status) são críticos para guiar o fuzzing em direção a defeitos latentes profundos. Os autores concluem que sua abordagem fornece um método robusto para descobrir falhas de execução que testes diferenciais e metamórficos não detectam.