Resumen Técnico: Búsqueda Guiada por Difusión mediante Inclinación Exponencial (DIFFTILT)

Declaración del Problema

La verificación y validación de sistemas autónomos y ciberfísicos (CPS) enfrentan un desafío fundamental: el descubrimiento de fallos raros y críticos para la seguridad. Estos fallos suelen caracterizarse por una rareza multiplicativa, donde un evento de fallo requiere la ocurrencia simultánea de un escenario de entrada raro y una traza de ejecución del sistema rara.

Los enfoques de falsificación existentes dependen típicamente de estrategias de muestreo condicional. Estos métodos factorizan la distribución conjunta de entornos y ejecuciones, muestreando primero las entradas y luego generando trazas condicionadas a dichas entradas. El artículo argumenta que este enfoque sufre un efecto de rareza multiplicativa: incluso con modelos condicionales precisos, la probabilidad de observar un fallo es el producto de la rareza de la entrada ($\delta$) y la rareza de la traza dado esa entrada ($\epsilon$). En consecuencia, el número esperado de muestras requeridas para encontrar un fallo escala como $O(1/(\delta\epsilon))$, lo que hace que la búsqueda exhaustiva sea prohibitivamente costosa. Además, los métodos clásicos de muestreo de importancia (IS) a menudo requieren acceso a distribuciones de referencia ideales o modelos de verosimilitud explícitos, los cuales son raramente disponibles en procesos de pruebas de caja negra realistas.

Metodología: DIFFTILT

El artículo propone DIFFTILT (Búsqueda Guiada por Difusión mediante Inclinación Exponencial), un marco que redefine la falsificación como la inclinación exponencial de una distribución conjunta aprendida sobre entornos y ejecuciones.

1. Modelado Generativo Conjunto

En lugar de modelar entradas y trazas por separado, DIFFTILT aprende un modelo de difusión conjunto $p_\theta(x, y)$, donde $x$ representa las entradas del entorno y $y$ representa las trazas de ejecución del sistema. Este modelo sirve como un prior reutilizable sobre los escenarios. Crucialmente, el modelo generativo actúa como una densidad base y no necesita representar fielmente la dinámica real del sistema; simplemente proporciona un soporte para el muestreador.

2. Inclinación Exponencial como Muestreo de Importancia

El mecanismo central implica el reponderado de la distribución conjunta utilizando una función de puntuación (score function) subrogada $S(x, y)$ (por ejemplo, un predictor de robustez o una función de recompensa) que se correlaciona con el fallo. La distribución inclinada se define como:
$$p_{\theta, \beta}(x, y) \propto p_\theta(x, y) \exp(\beta S(x, y))$$
donde $\beta$ es el parámetro de inclinación.

El artículo establece que este muestreo guiado por difusión admite una interpretación exacta como muestreo de importancia en el espacio conjunto. Las puntuaciones de guía actúan como inclinaciones de la razón de verosimilitud que reasignan la masa de probabilidad hacia comportamientos relevantes para el fallo. Los autores demuesten que este reponderado es la distribución sesgada KL-óptima (que minimiza la divergencia de Kullback-Leibler) que satisface una restricción sobre la puntuación esperada, amplificando así la probabilidad de fallo bajo supuestos moderados.

3. Garantías Teóricas

• Amplificación de la Probabilidad de Fallo: El artículo demuestra que la inclinación exponencial aumenta de forma demostrable la probabilidad de muestrear un fallo si la función de puntuación $S$ clasifica los comportamientos de fallo con una puntuación más alta que los no fallidos en un sentido distributivo (específicamente, bajo un supuesto de Dominancia Estocástica de Primer Orden).
• Superación de la Rareza Multiplicativa: A diferencia del muestreo condicional, que está limitado por la tasa de fallo dentro de una entrada específica, la inclinación conjunta puede reponderar todo el espacio conjunto. Esto permite superar el cuello de botella de la rareza multiplicativa al desplazar la masa directamente hacia las regiones conjuntas donde los fallos son probables.
• Sistemas Deterministas: Para sistemas dinámicos deterministas donde $y = \Phi(x)$, la inclinación conjunta se reduce al muestreo de importancia óptimo sobre las entradas a lo largo de la variedad (manifold) de la dinámica. Esto asegura que, incluso si la traza predicha $\hat{y}$ es imperfecta, el método sigue siendo válido porque el simulador real solo se invoca sobre la entrada $x$ seleccionada.

4. Flujo Algorítmico

El flujo de trabajo de DIFFTILT opera en dos fases:

• Fuera de línea (Offline): Se entrena un modelo de difusión conjunto sobre datos emparejados $(x, y)$. Este prior se congela y se reutiliza en diferentes especificaciones sin necesidad de reentrenamiento.
• En línea (Online):
  1. Se entrena una función de puntuación subrogada $S_k$ sobre los datos de simulación acumulados para aproximar la verosimilitud de fallo.
  2. Se generan candidatos mediante difusión inversa guiada por gradiente, donde el gradiente de la puntuación $\nabla S_k$ sesga el proceso de eliminación de ruido hacia regiones de alta puntuación (propensas al fallo).
  3. Se selecciona un candidato, se ejecuta en el simulador de caja negra para obtener la traza y robustez reales, y el resultado se utiliza para refinar la función subrogada.
  4. Este ciclo continúa hasta que se encuentra un fallo o se agota el presupuesto de simulación.

Contribuciones Clave

1. Fundamento Formal: El artículo proporciona una base formal para la falsificación guiada por difusión, interpretándola como la generación de contraejemplos mediante la inclinación exponencial de una distribución conjunta.
2. Análisis Teórico: Establece condiciones necesarias y suficientes bajo las cuales la inclinación exponencial amplifica la probabilidad de fallo, demostrando mediante la Dominancia Estocástica de Primer Orden (FOSD) que el método es efectivo cuando la puntuación clasifica los fallos por encima de los no fallos.
3. Limitación del Muestreo Condicional: El trabajo caracteriza la limitación fundamental del muestreo condicional (rareza multiplicativa) y muestra cómo la inclinación conjunta supera esto al reasignar la masa en el espacio conjunto.
4. Reducción al IS del Espacio de Entrada: Para sistemas deterministas, los autores muestran que la inclinación conjunta se reduce al muestreo de importancia óptimo sobre las entradas, vinculando el marco con los flujos de trabajo existentes de verificación basados en simulación.
5. Nuevo Benchmark: El artículo introduce el benchmark de tractor-remolque TT2D, adaptado de trabajos existentes, para evaluar la falsificación bajo especificaciones bien definidas y objetivos a nivel de trayectoria, destacando escenarios donde las recompensas basadas en especificaciones difieren de los costes a nivel de trayectoria.

Resultados Experimentales

Los autores evaluaron DIFFTILT frente a FReaK, un método de falsificación de vanguardia basado en la linealización del operador Koopman, a través de tres conjuntos de benchmarks: Automatic Transmission (AT), Chasing Cars (CC) y el propuesto Tractor-Trailer (TT2D).

• Automatic Transmission (AT): DIFFTILT fue menos competitivo que FReaK en especificaciones que involucran señales de engranajes discretas (ej. AT51, AT54). Los autores atribuyen esto al paisaje de robustez "aplanado" causado por la dinámica discreta, lo que hace que la guía basada en gradientes sea poco informativa. Sin embargo, tuvo un desempeño competitivo en especificaciones continuas.
• Chasing Cars (CC): En especificaciones de largo horizonte y anidadas (CC4, CC5, CCx), DIFFTILT demostró ventajas significativas. Mientras que la optimización de FReaK se vuelve costosa y menos precisa a medida que el horizonte y la profundidad de anidamiento aumentan, DIFFTILT mantuvo altas tasas de falsificación con menos simulaciones, ya que depende de la puntuación subrogada de las trazas realizadas en lugar de la codificación de fórmulas lógicas.
• Tractor-Trailer (TT2D): DIFFTILT logró una tasa de falsificación del 100% en los seis escenarios (incluyendo aquellos con obstáculos y tolerancias estrechas) usando 4000 puntos de entrenamiento, superando significativamente a FReaK tanto en tasa de éxito como en eficiencia de simulación. Los resultados sugieren que DIFFTILT se beneficia de señales de guía más ricas a nivel de trayectoria (costes de llegada al objetivo) que son difíciles de codificar en los marcos de optimización estándar basados en STL.

Significado y Reivindicaciones

El artículo afirma que DIFFTILT ofrece una mejora sólida y consciente de la distribución para la generación de contraejemplos. Su principal importancia radica en:

• Desacoplamiento del Prior del Sistema: El modelo generativo sirve solo como una densidad base y no necesita ser un modelo perfecto del sistema bajo prueba. Las evaluaciones reales del sistema se limitan al aprendizaje de la función de puntuación, lo que permite un uso selectivo y adaptativo de simulaciones costosas.
• Generalizabilidad: Aunque se centra en la falsificación, el marco es general y aplicable a otros problemas de generación de escenarios, como la planificación y la síntesis. Permite una exploración consciente de la distribución en espacios de escenarios complejos más allá de las simples violaciones de seguridad.
• Rigor Teórico: Al fundamentar la búsqueda guiada por difusión en la teoría del muestreo de importancia y el análisis de orden estocástico, el artículo proporciona garantías demostrables respecto a la amplificación de las probabilidades de fallo, yendo más allá de las estrategias de búsqueda heurísticas.

Los autores reconocen limitaciones, particularmente respecto al rendimiento en sistemas con dinámicas discretas donde los gradientes se anulan, y señalan que la fuerza de inclinación $\beta$ requiere actualmente un ajuste manual. Sugieren trabajos futuros en el ajuste adaptativo de $\beta$, el manejo de dinámicas híbridas y la extensión del análisis a sistemas estocásticos.