Resumo Técnico: Busca Guiada por Difusão via Inclinação Exponencial (DIFFTILT)

Declaração do Problema

A verificação e validação de sistemas autônomos e sistemas ciber-físicos (CPS) enfrentam um desafio fundamental: descobrir falhas raras e críticas à segurança. Essas falhas são frequentemente caracterizadas por uma raridade multiplicativa, onde um evento de falha requer a ocorrência simultânea de um cenário de entrada raro e um traço de execução do sistema raro.

As abordagens de falsificação existentes baseiam-se tipicamente em estratégias de amostragem condicional. Esses métodos fatoram a distribuição conjunta de ambientes e execuções, amostrando primeiro os inputs e, em seguida, gerando traços condicionais a esses inputs. O artigo argumenta que essa abordagem sofre de um efeito de raridade multiplicativa: mesmo com modelos condicionais precisos, a probabilidade de observar uma falha é o produto da raridade do input ($\delta$) e da raridade do traço dado esse input ($\epsilon$). Consequentemente, o número esperado de amostras necessárias para encontrar uma falha escala como $O(1/(\delta\epsilon))$, tornando a busca exaustiva proibitivamente cara. Além disso, os métodos clássicos de amostragem de importância (IS - Importance Sampling) frequentemente exigem acesso a distribuições de referência ideais ou modelos de verossimilhança explícitos, que são raramente disponíveis em pipelines de teste de caixa-preta realistas.

Metodologia: DIFFTILT

O artigo propõe o DIFFTILT (Diffusion-Guided Search via Exponential Tilting), um framework que reformula a falsificação como a inclinação exponencial (exponential tilting) de uma distribuição conjunta aprendida sobre ambientes e execuções.

1. Modelagem Generativa Conjunta

Em vez de modelar inputs e traços separadamente, o DIFFTILT aprende um modelo de difusão conjunto $p_\theta(x, y)$, onde $x$ representa os inputs do ambiente e $y$ representa os traços de execução do sistema. Este modelo serve como um prior reutilizável sobre os cenários. Crucialmente, o modelo generativo atua como uma densidade base e não precisa representar fielmente a dinâmica real do sistema; ele meramente fornece um suporte para o amostrador.

2. Inclinação Exponencial como Amostragem de Importância

O mecanismo central envolve o reponderamento da distribuição conjunta usando uma função de score substituta $S(x, y)$ (por exemplo, um preditor de robustez ou uma função de recompensa) que correlaciona com a falha. A distribuição inclinada é definida como:
$$p_{\theta, \beta}(x, y) \propto p_\theta(x, y) \exp(\beta S(x, y))$$
onde $\beta$ é o parâmetro de inclinação.

O artigo estabelece que essa amostragem guiada por difusão admite uma interpretação exata como amostragem de importância no espaço conjunto. Os scores de orientação atuam como tilts de razão de verossimilhança que realocam a massa de probabilidade em direção a comportamentos relevantes para a falha. Os autores provam que este reponderamento é a distribuição enviesada KL-ótima (minimizadora da divergência de Kullback-Leibler) que satisfaz uma restrição sobre o score esperado, amplificando assim a probabilidade de falha sob suposições brandas.

3. Garantias Teóricas

• Amplificação da Probabilidade de Falha: O artigo prova que a inclinação exponencial aumenta comprovadamente a probabilidade de amostrar uma falha se a função de score $S$ classificar comportamentos de falha acima de comportamentos de não-falha em um sentido distributivo (especificamente, sob uma suposição de Dominância Estocástica de Primeira Ordem).
• Superação da Raridade Multiplicativa: Ao contrário da amostragem condicional, que é limitada pela taxa de falha dentro de um input específico, a inclinação conjunta pode reponderar todo o espaço conjunto. Isso permite superar o gargalo da raridade multiplicativa ao deslocar a massa diretamente para as regiões conjuntas onde as falhas são prováveis.
• Sistemas Determinísticos: Para sistemas dinâmicos determinísticos onde $y = \Phi(x)$, a inclinação conjunta reduz-se à amostragem de importância ótima sobre os inputs ao longo da variedade (manifold) da dinâmica. Isso garante que, mesmo que o traço previsto $\hat{y}$ seja imperfeito, o método permaneça válido porque o simulador real é invocado apenas no input $x$ selecionado.

4. Pipeline Algorítmico

O pipeline DIFFTILT opera em duas fases:

• Offline: Um modelo de difusão conjunto é treinado em dados pareados $(x, y)$. Este prior é congelado e reutilizado entre diferentes especificações sem necessidade de retreinamento.
• Online:
  1. Uma função de score substituta $S_k$ é treinada sobre os dados de simulação acumulados para aproximar a verossimilhança da falha.
  2. Candidatos são gerados via difusão reversa guiada por gradiente, onde o gradiente do score $\nabla S_k$ enviesa o processo de denoising em direção a regiões de alto score (propensas a falhas).
  3. Um candidato é selecionado, executado no simulador de caixa-preta para obter o traço real e a robustez, e o resultado é usado para refinar o substituto.
  4. Este ciclo continua até que uma falsificação seja encontrada ou o orçamento de simulação seja esgotado.

Contribuições Principais

1. Fundamentação Formal: O artigo fornece uma base formal para a falsificação guiada por difusão, interpretando-a como geração de contraexemplos baseada em princípios via inclinação exponencial de uma distribuição conjunta.
2. Análise Teórica: Estabelece condições necessárias e suficientes sob as quais a inclinação exponencial amplifica a probabilidade de falha, demonstrando via Dominância Estocástica de Primeira Ordem (FOSD) que o método é eficaz quando o score classifica falhas acima de não-falhas.
3. Limitação da Amostragem Condicional: O trabalho caracteriza a limitação fundamental da amostragem condicional (raridade multiplicativa) e mostra como a inclinação conjunta supera isso ao realocar a massa no espaço conjunto.
4. Redução para IS no Espaço de Input: Para sistemas determinísticos, os autores mostram que a inclinação conjunta reduz-se à amostragem de importância ótima sobre os inputs, conectando o framework aos fluxos de trabalho de verificação baseados em simulação existentes.
5. Novo Benchmark: O artigo introduz o benchmark de trator-carreta TT2D, adaptado de trabalhos existentes, para avaliar a falsificação sob especificações bem definidas e objetivos de nível de trajetória, destacando cenários onde recompensas baseadas em especificações diferem de custos de nível de trajetória.

Resultados Experimentais

Os autores avaliaram o DIFFTILT contra o FReaK, um método de estado da arte baseado na linearização do operador Koopman, através de três suítes de benchmarks: Automatic Transmission (AT), Chasing Cars (CC) e o proposto Tractor-Trailer (TT2D).

• Automatic Transmission (AT): O DIFFTILT foi menos competitivo que o FReaK em especificações envolvendo sinais de engrenagem discretos (ex: AT51, AT54). Os autores atribuem isso ao panorama de robustez "achatado" causado pelas dinâmicas discretas, o que torna a orientação baseada em gradiente pouco informativa. No entanto, teve desempenho competitivo em especificações contínuas.
• Chasing Cars (CC): Em especificações de longo horizonte e aninhadas (CC4, CC5, CCx), o DIFFTL T demonstrou vantagens significativas. Enquanto a otimização do FReaK torna-se cara e menos precisa conforme o horizonte e a profundidade de aninhamento aumentam, o DIFFTILT manteve altas taxas de falsificação com menos simulações, pois depende do score substituto de traços realizados em vez da codificação de fórmulas lógicas.
• Tractor-Trailer (TT2D): O DIFFTILT alcançou uma taxa de falsificação de 100% em todos os seis cenários (incluindo aqueles com obstáculos e tolerâncias apertadas) usando 4000 pontos de treinamento, superando significativamente o FReaK tanto em taxa de sucesso quanto em eficiência de simulação. Os resultados sugerem que o DIFFTILT se beneficia de sinais de orientação mais ricos em nível de trajetória (custos de alcance de meta) que são difíceis de codificar em frameworks de otimização padrão de STL.

Significância e Alegações

O artigo afirma que o DIFFTILT oferece um melhoramento robusto e consciente da distribuição para a geração de contraexemplos. Sua principal significância reside em:

• Desacoplamento do Prior do Sistema: O modelo generativo serve apenas como uma densidade base e não precisa ser um modelo perfeito do sistema sob teste. As avaliações reais do sistema são limitadas ao aprendizado da função de score, permitindo o uso seletivo e adaptativo de simulações caras.
• Generalização: Embora focado em falsificação, o framework é geral e aplicável a outros problemas de geração de cenários, como planejamento e síntese. Ele permite a exploração consciente da distribuição em espaços de cenários complexos além de simples violações de segurança.
• Rigor Teórico: Ao fundamentar a busca guiada por difusão na teoria de amostragem de importância e análise de ordem estocástica, o artigo fornece garantias prováveis sobre a amplificação das probabilidades de falha, indo além de estratégias de busca heurísticas.

Os autores reconhecem limitações, particularmente em relação ao desempenho em sistemas com dinâmicas discretas onde os gradientes desaparecem, e observam que a força de inclinação $\beta$ atualmente requer ajuste manual. Eles sugerem trabalhos futuros no ajuste adaptativo de $\beta$, tratamento de dinâmicas híbridas e extensão da análise para sistemas estocásticos.