Technische Samenvatting: Diffusion-Guided Search via Exponential Tilting (DIFFTILT)

Probleemstelling

De verificatie en validatie van autonome en cyber-fysieke systemen (CPS) staan voor een fundamentele uitdaging: het ontdekken van zeldzame, veiligheidskritische fouten. Deze fouten worden vaak gekenmerkt door multiplicatieve zeldzaamheid, waarbij een foutgebeurtenis de gelijktijdige aanwezigheid vereist van een zeldzaam inputscenario en een zeldzaam systeemuitvoeringsspoor (execution trace).

Bestaande falsificatiebenaderingen vertrouwen doorgaans op conditionele bemonsteringsstrategieën. Deze methoden factoriseren de gezamenlijke verdeling van omgevingen en uitvoeringen, waarbij eerst inputs worden gesampled en vervolgens sporen worden gegenereerd die geconditioneerd zijn op die inputs. Het artikel betoogt dat deze aanpak lijdt onder een multiplicatief zeldzaamheidseffect: zelfs met nauwkeurige conditionele modellen is de kans op het observeren van een fout het product van de zeldzaamheid van de input ($\delta$) en de zeldzaamheid van het spoor gegeven die input ($\epsilon$). Bijgevolg schaalt het verwachte aantal samples dat nodig is om een fout te vinden als $O(1/(\delta\epsilon))$, waardoor een exhaustieve zoektocht evenredig duur wordt. Bovendien vereisen klassieke importance sampling (IS) methoden vaak toegang tot ideale referentieverdelingen of expliciete waarschijnlijkheidsmodellen, die zelden beschikbaar zijn in realistische black-box testpipelines.

Methodologie: DIFFTILT

Het artikel stelt DIFFTILT (Diffusion-Guided Search via Exponential Tilting) voor, een framework dat falsificatie herformuleert als de exponentiële kanteling (exponential tilting) van een geleerde gezamenlijke verdeling over omgevingen en uitvoeringen.

1. Gezamenlijke Generatieve Modellering

In plaats van inputs en sporen afzonderlijk te modelleren, leert DIFFTILT een gezamenlijk diffusiemodel $p_\theta(x, y)$, waarbij $x$ de omgeving-inputs vertegenwoordigt en $y$ de systeemuitvoeringssporen vertegenwoordigt. Dit model dient als een herbruikbare prior over scenario's. Cruciaal is dat het generatieve model fungeert als een basisdichtheid en niet noodzakelijkerwijs de werkelijke systeemdynamica getrouw hoeft te representeren; het biedt enkel een ondersteuning (support) voor de sampler.

2. Exponential Tilting als Importance Sampling

Het kernmechanisme houdt in dat de gezamenlijke verdeling wordt hergewogen met behulp van een surrogaat scorefunctie $S(x, y)$ (bijv. een robuustheidsvoorspeller of beloningsfunctie) die correleert met fouten. De gekantelde verdeling wordt gedefinieerd als:
$$p_{\theta, \beta}(x, y) \propto p_\theta(x, y) \exp(\beta S(x, y))$$
waarbij $\beta$ de kantelparameter is.

Het artikel stelt vast dat deze diffusie-gestuurde bemonstering een exacte interpretatie heeft als importance sampling in de gezamenlijke ruimte. De guidance scores fungeren als likelihood-ratio kantelingen die de waarschijnlijkheidsmassa herverdelen naar foutrelevante gedragingen. De auteurs bewijzen dat deze herweging de KL-optimale (Kullback-Leibler divergentie minimaliserende) verdrongen verdeling is die voldoet aan een beperking op de verwachte score, waardoor de kans op fouten wordt versterkt onder milde aannames.

3. Theoretische Garanties

• Versterking van de Foutkans: Het artikel bewijst dat exponentiële kanteling de kans op het samplen van een fout aantoonbaar vergroot als de scorefunctie $S$ falende gedragingen hoger rangschikt dan niet-falende gedragingen in een distributionele zin (specifiek, onder een First-Order Stochastic Dominance aanname).
• Overwinnen van Multiplicatieve Zeldzaamheid: In tegenstelling tot conditionele bemonstering, wat beperkt wordt door de foutratio binnen een specifieke input, kan gezamenlijke kanteling de gehele gezamenlijke ruimte herwegen. Dit maakt de methode in staat om de multiplicatieve zeldzaamheid-bottleneck te overwinnen door de massa direct te verschuiven naar de gezamenlijke regio's waar fouten waarschijnlijk zijn.
• Deterministische Systemen: Voor deterministische dynamische systemen waar $y = \Phi(x)$, reduceert de gezamenlijke kanteling tot optimale importance sampling over inputs langs de dynamica-manifold. Dit zorgt ervoor dat zelfs als de voorspelde trace $\hat{y}$ imperfect is, de methode geldig blijft omdat de ware simulator alleen wordt aangeroepen op de geselecteerde input $x$.

4. Algoritmische Pipeline

De DIFFTILT-pipeline werkt in twee fasen:

• Offline: Een gezamenlijk diffusiemodel wordt getraind op gepaarde $(x, y)$ data. Deze prior is bevroren en wordt hergebruikt voor verschillende specificaties zonder hertraining.
• Online:
  1. Een surrogaat scorefunctie $S_k$ wordt getraind op geaccumuleerde simulatiedata om de foutwaarschijnlijkheid te benaderen.
  2. Kandidaten worden gegenereerd via gradient-guided reverse diffusion, waarbij de score-gradiënt $\nabla S_k$ het denoising-proces stuurt naar hoog-scorende (foutgevoelige) regio's.
  3. Een kandidaat wordt geselecteerd, uitgevoerd in de black-box simulator om het ware spoor en de robuustheid te verkrijgen, en het resultaat wordt gebruikt om de surrogaat te verfijnen.
  4. Deze lus gaat door totdat een falsificatie is gevonden of het simulatiebudget is uitgeput.

Belangrijkste Bijdragen

1. Formele Fundering: Het artikel biedt een formele fundering voor diffusie-gestuurde falsificatie door het te interpreteren als principiële tegenvoorbeeldgeneratie via de exponentiële kanteling van een gezamenlijke verdeling.
2. Theoretische Analyse: Het stelt noodzakelijke en voldoende voorwaarden vast waaronder exponentiële kanteling de foutkans versterkt, waarbij via First-Order Stochastic Dominance (FOSD) wordt aangetoond dat de methode effectief is wanneer de score fouten boven niet-fouten rangschikt.
3. Beperking van Conditionele Bemonstering: Het werk karakteriseert de fundamentele beperking van conditionele bemonstering (multiplicatieve zeldzaamheid) en laat zien dat gezamenlijke kanteling dit overwint door de massa in de gezamenlijke ruimte te herverdelen.
4. Reductie tot Input-Ruimte IS: Voor deterministische systemen tonen de auteurs aan dat gezamenlijke kanteling reduceert tot optimale importance sampling over inputs, waardoor het framework een brug slaat met bestaande simulatie-gebaseerde verificatiewerkstromen.
5. Nieuwe Benchmark: Het artikel introduceert de TT2D tractor-trailer benchmark, aangepast van bestaand werk, om falsificatie te evalueren onder goed gedefinieerde specificaties en traject-niveau doelstellingen, waarbij scenario's worden belicht waarin specificatie-gebaseerde beloningen verschillen van traject-niveau kosten.

Experimentele Resultaten

De auteurs evalueerden DIFFTILT tegenover FReaK, een state-of-the-art falsificatiemethode gebaseerd op Koopman operator linearisatie, over drie benchmark-suites: Automatic Transmission (AT), Chasing Cars (CC) en de voorgestelde Tractor-Trailer (TT2D).

• Automatic Transmission (AT): DIFFTILT was minder competitief dan FReaK op specificaties met discrete schakelsignalen (bijv. AT51, AT54). De auteurs schrijven dit toe aan het "afgevlakte" robuheidslandschap veroorzaakt door discrete dynamica, wat gradient-gebaseerde guidance minder informatief maakt. Echter, het presteerde competitief op continue specificaties.
• Chasing Cars (CC): Op langdurige en geneste specificaties (CC4, CC5, CCx) toonde DIFFTILT significante voordelen. Terwijl de optimalisatie van FReaK duurder en minder accuraat wordt naarmate de horizon en de nestingsdiepte toenemen, behield DIFFTILT hoge falsificatiegraden met minder simulaties, aangezien het vertrouwt op de surrogaat score van gerealiseerde sporen in plaats van logische formule-encodering.
• Tractor-Trailer (TT2D): DIFFTILT bereikte een 100% falsificatiepercentage over alle zes de scenario's (inclusclusief scenario's met obstakels en nauwe toleranties) met 4000 trainingspunten, waarmee het FReaK aanzienlijk versloeg in zowel succespercentage als simulatie-efficiëntie. De resultaten suggereren dat DIFFTILT profiteert van rijkere traject-niveau guidance-signalen (doelbereikingskosten) die moeilijk te encoderen zijn in standaard STL-gebaseerde optimalisatieframeworks.

Betekenis en Claims

Het artikel claimt dat DIFFTILT een sound, distributie-bewuste verbetering biedt aan de generatie van tegenvoorbeelden. De primaire betekenis ligt in:

• Ontkoppeling van de Prior van het Systeem: Het generatieve model dient slechts als een basisdichtheid en hoeft geen perfect model van het te testen systeem te zijn. De ware systeemevaluaties zijn beperkt tot het leren van de scoringfunctie, wat selectief en adaptief gebruik van dure simulaties mogelijk maakt.
• Generaliseerbaarheid: Hoewel gericht op falsificatie, is het framework algemeen en toepasbaar op andere scenario-generatieproblemen zoals planning en synthese. Het maakt een distributie-bewuste exploratie van complexe scenario-ruimtes mogelijk die verder gaat dan eenvoudige veiligheidschendingen.
• Theoretische Rigor: Door diffusie-gestuurde zoektocht te funderen in importance sampling theorie en stochastische orde-analyse, biedt het artikel bewijsbare garanties met betrekking tot de versterking van foutkansen, wat verder gaat dan heuristische zoekstrategieën.

De auteurs erkennen beperkingen, met name met betrekking tot de prestaties op systemen met discrete dynamica waar gradiënten verdwijnen, en merken op dat de kantelsterkte $\beta$ momenteel handmatige afstemming vereist. Ze stellen toekomstig werk voor in de adaptieve afstemming van $\beta$, het afhandelen van hybride dynamica en het uitbreiden van de analyse naar stochastische systemen.