Resumo Técnico: Autogram para Descoberta de Invariantes em Sistemas de Rede

Definição do Problema

Invariantes de rede — relações que se espera que se mantenham entre sinais medidos — são fundamentais para verificação de rede, geração de tráfego, imputação de telemetria e validação de entrada. No entanto, derivar esses invariantes para sistemas específicos é notoriamente difícil. Isso requer expertise rara tanto em lógica formal quanto em redes, e o processo é trabalhoso e propenso a erros.

Os métodos existentes de mineração automática de invariantes enfrentam duas limitações críticas:

1. Dependência de Gramática: Eles exigem que um especialista humano autore a "gramática" dos invariantes admissíveis (o conjunto de regras de produção que definem quais relações são expressáveis). Esta gramática deve codificar conhecimento semântico (ex: tipos de variáveis, agrupamentos de localidade, agregações n-árias) que os dados brutos não revelam.
2. Regras Hard vs. Soft: A maioria dos mineradores existentes aprende apenas regras "hard" que se mantêm exatamente em cada observação. Dados de rede do mundo real contêm ruído inerente (incerteza aleatória) e viés sistemático (ex: offsets de contadores), o que significa que os invariantes mais valiosos são "soft" — eles se mantêm dentro de uma tolerância na maioria, mas não em todas, as observações.

Embora os Grandes Modelos de Linguagem (LLMs) possuam o raciocínio semântico para inferir tais gramáticas a partir de nomes de variáveis e metadados, eles são não-determinísticos e propensos a alucinações, tornando sua saída direta inadequada para verificações de sistema auditáveis e garantidas.

Metodologia: Autogram

Os autores propõem o Autogram, um sistema que particiona o problema de descoberta de invariantes em duas fases distintas: uma fase de "descoberta de gramática" impulsionada por IA e uma fase de "busca" impulsionada por estatística. Essa divisão permite que o poder não-determinístico dos LLMs auxilie sem comprometer as garantias formais do resultado final.

1. Arquitetura e Fluxo de Trabalho

• Propositor LLM (Não-Determinístico): O LLM atua exclusivamente como um indutor de gramática. Ele recebe nomes de variáveis e metadados ricos (topologia, função, anotações de fornecedor) como entrada e propõe uma gramática tipada e limitada. Crucialmente, o LLM nunca afirma que uma relação específica ocorre; ele apenas define o espaço de hipóteses.
• Motor Determinístico: Uma vez que a gramática é induzida, um motor determinístico assume o controle:
  • Enumeração Exaustiva: Ele enumera todo o espaço de hipóteses limitado definido pela gramática.
  • Poda Lógica: Um solver filtra os candidatos para remover verdades triviais, autocontradições e redundâncias lógicas.
  • Validação Estatística: Um teste estatístico avalia os candidatos contra os dados. Ao contrário dos mineradores hard, o Autogram aceita invariantes "soft". Ele calcula uma tolerância por candidato baseada nos resíduos dos dados (usando bandas de predição conformal) em vez de um limiar global fixo.
• Calibração: Para evitar overfitting ou raciocínio circular, os limiares de aceitação genéricos do sistema são calibrados em conjuntos de dados proxy sintéticos com relações plantadas e ruído injetado, nunca nos invariantes reais que o sistema espera recuperar.
• Re-indução: Se o sistema falhar em recuperar invariantes conhecidos (em um split de hold-out), ele aciona uma etapa de re-indução onde o LLM propõe uma gramática estritamente mais expressiva (ex: adicionando termos de grau superior ou agregações).

2. Garantias Principais

Ao confinar o LLM à proposta de gramática e manter a busca determinística, o Autogram fornece três propriedades principais:

• Determinismo e Exaustividade: Dada uma gramática, o sistema enumera o espaço de forma idêntica em cada execução, garantindo reprodutibilidade e auditabilidade.
• Soundness (Correção): Todo invariante retornado é não-trivial (verificado por um solver) e supera uma barra de confiança conservadora.
• Completude Monótona: O sistema garante encontrar qualquer invariante desconhecido que se mantenha pelo menos tão frequentemente, em pelo menos tantos dados, quanto um invariante conhecido que o operador já confia.

Principais Contribuições

1. Desacoplamento de Semântica e Busca: O artigo demonstra que a "gramática" (julgamento semântico) e a "busca" (verificação estatística) podem ser separadas. Isso permite que os LLMs lidem com o fardo semântico de definir o espaço de hipóteses enquanto os métodos estatísticos lidem com a verificação.
2. Descoberta de Invariantes Soft: O Autogram é projetado para descobrir invariantes soft com tolerâncias baseadas em dados, abordando a realidade de que as medições de rede são ruidosas e frequentemente contêm offsets sistemáticos.
3. Indução de Gramática Baseada em Metadados: O sistema aproveita metadados existentes do operador (nomes de variáveis, topologia, funções) para induzir gramáticas, removendo a necessidade de autoria manual de gramática.
4. Integração de IA Auditável: Fornece um framework para integrar IA não-determinística em sistemas de missão crítica, garantindo que a IA apenas molde o espaço de busca, enquanto os dados e solvers determinam os resultados finais.

Resultados

Os autores avaliaram o Autogram em conjuntos de dados públicos de WAN (Abilene, GEANT) e uma WAN de produção ("WAN prod").

• Recuperação de Invariantes Conhecidos: Em conjuntos de dados públicos, o Autogram recuperou 100% dos invariantes derivados por especialistas relatados pelo sistema CrossCheck. Em contraste, um baseline de estado da arte (NetNomos), restrito a regras exatas e uma gramática escrita à mão, recuperou menos de 20% desses invariantes.
• Descoberta de Novas Relações: O Autogram descobriu relações úteis não registradas anteriormente, como simetria de presença de topologia e leis de conservação de demanda.
• Capacidade Diagnóstica: O sistema identificou com sucesso offsets sistemáticos (ex: um déficit consistente de ~2% nos relatórios de origem de tráfego em comparação com as matrizes de demanda) em vez de descartá-los como ruído. Isso destaca a utilidade dos invariantes soft para diagnósticos.
• Eficiência e Escalabilidade: Em uma rede de produção com ~100 roteadores e ~1.000 links, o Autogram descobriu 41 invariantes em dez minutos. O tempo de execução escala suavemente com o tamanho da rede.
• Expressividade: O Autogram alcançou recall total com 101 regras no dataset GEANT, enquanto o NetNomos exigiu 1.645 regras (muitas das quais eram vacuas) para alcançar um recall parcial.

Significância e Alegações

O artigo posiciona o Autogram como um "passo promissor em direção à descoberta de código aberto". Argumenta-se que o principal gargalo na descoberta de invariantes mudou da busca por relações para a definição da linguagem na qual elas podem ser expressas. Ao usar LLMs para propor gramáticas baseadas em metadados, o Autogram automatiza esse gargalo.

Os autores são modestos sobre o estado atual do sistema, reconhecendo dois limites:

1. Componibilidade: O Autogram ainda não consegue compor invariantes descobertos em estruturas relacionais que nenhum deles expressa isoladamente.
2. Teto de Decidibilidade: A expressividade do sistema é limitada pela decidibilidade dos solvers subjacentes, deixando estruturas não-lineares amplamente inexploradas.

O artigo conclui que, embora o Autogram ainda não possa alcançar a descoberta totalmente aberta sem intervenção humana, ele consegue fazer a ponte entre o raciocínio semântico dos LLMs e as garantias rigorosas exigidas pelas operações de rede, permitando a recuperação de invariantes derivados por especialistas com alta cobertura e baixos falsos positivos.