Contract And Conquer: How to Provably Compute Adversarial Examples for a Black-Box Model?

Dit paper introduceert Contract And Conquer (CAC), een methode die via kennisdistillatie en een bewezen overdraagbaarheidsgarantie het zoekruimte voor adversariële voorbeelden in een black-box model contracteert om zo binnen een vast aantal iteraties een gegarandeerd adversariaal voorbeeld te vinden.

De kern

Stel je voor dat je een zeer slimme, maar geheimzinnige robot hebt die foto's herkent. Als je hem een foto van een panda laat zien, zegt hij "Panda". Als je hem een foto van een gitaar laat zien, zegt hij "Gitaar". Dit is je zwarte doos-model: je kunt erin kijken, maar je mag niet weten hoe zijn hersenen precies werken. Je kunt alleen foto's inwerpen en de antwoorden opvangen.

Nu is er een probleem: deze robot is kwetsbaar. Als je een paar onzichtbare pixels op de foto verandert (zoals een heel klein beetje ruis), kan de robot plotseling denken dat de panda een gitaar is. Dit noemen we een adversariaal voorbeeld (een "truuks").

Het grote probleem met de bestaande methoden om deze truuks te vinden, is dat ze gissen. Ze gooien duizenden foto's naar de robot en hopen dat ze er eentje vinden die werkt. Er is geen garantie dat ze het ooit vinden, zelfs niet als het mogelijk is.

De auteurs van dit papier hebben een nieuwe methode bedacht, genaamd Contract and Conquer (in het Nederlands: Inpakken en Veroveren). Laten we uitleggen hoe dit werkt met een paar creatieve analogieën.

De Analogie: De Zoektocht naar de Sleutel

Stel je voor dat je een sleutel zoekt die past in een zeer complex slot (de zwarte doos-robot), maar je mag het slot niet openmaken om naar het binnenwerk te kijken.

1. De oude manier (Goochelen): Je probeert duizenden willekeurige sleutels. Soms werkt het, soms niet. Je weet niet of er überhaupt een sleutel bestaat die past, of dat je gewoon nog niet geluk had.
2. De nieuwe manier (Contract and Conquer):
   • Stap 1: De Kopie maken (Knowledge Distillation): In plaats van direct met het echte slot te worstelen, maak je een perfecte kopie van het slot. Je leert deze kopie (een "surrogaat-model") precies hoe het echte slot reageert op duizenden verschillende sleutels. Omdat je de kopie wel mag openmaken, zie je precies hoe de tandjes eruitzien.
   • Stap 2: De aanval op de kopie: Je gebruikt je kennis van de kopie om een perfecte "truuksleutel" te maken die de kopie laat denken dat het een andere sleutel is.
   • Stap 3: De Test: Je probeert deze truuksleutel in het echte slot.
     • Werkt het? Groot succes! Je hebt de robot om de tuin geleid.
     • Werkt het niet? Geen probleem. Dan weet je dat je kopie nog niet 100% perfect was op dat specifieke punt.

Het Magische Trucje: "Inpakken" (Contraction)

Hier komt de slimme kant van de methode. Als de truuksleutel niet werkt in het echte slot, doe je twee dingen:

1. Je leert je kopie de fout die hij maakte (je voegt de nieuwe sleutel toe aan de leerstof).
2. Je maakt de zoekruimte kleiner.

Dit is het "Inpakken" (Contraction). Stel je voor dat je eerst zocht in een heel groot park om de sleutel te vinden. Als je faalt, zeg je: "Oké, de sleutel zit niet in het hele park, hij zit zeker niet verder dan 10 meter van de plek waar we net waren." Je maakt de zoekruimte dus kleiner en concentreert je op een kleiner gebied.

Je herhaalt dit proces:

• Kopie leren.
• Truuksleutel maken.
• Testen.
• Als het faalt: Leer de kopie bij en pak de zoekruimte nog kleiner in.

Waarom is dit zo speciaal?

De auteurs bewijzen wiskundig dat dit proces altijd werkt binnen een bepaald aantal stappen.

• Omdat je de zoekruimte elke keer een beetje kleiner maakt (je "inpakt"), en je kopie steeds beter wordt, kun je niet oneindig doorgaan zonder succes.
• Het is alsof je een ballon langzaam leeglaat. Uiteindelijk moet hij op een punt zijn waar je de sleutel moet vinden. Je hebt een garantie dat je het binnen een vast aantal pogingen zult vinden.

Wat hebben ze bewezen?

Ze hebben deze methode getest op bekende datasets (zoals ImageNet, waar miljoenen foto's van dieren en objecten staan) en op verschillende soorten robots (zoals ResNet en Vision Transformers).

De resultaten zijn indrukwekkend:

• Succes: Hun methode werkt bijna altijd (100% succes in hun tests), terwijl andere methoden soms vastlopen.
• Efficiëntie: Ze vinden de "truuks" met minder pogingen dan de concurrenten.
• Nauwkeurigheid: De truuks die ze vinden, zijn vaak heel subtiel (ze veranderen de foto heel weinig), wat betekent dat de truuks heel goed verborgen zijn.

Conclusie

Contract and Conquer is als een slimme detective die niet blindelings rondloopt in een donker huis. Hij maakt eerst een perfecte plattegrond van het huis (de kopie), zoekt daar de uitgang, en als hij vastloopt, maakt hij de zoekruimte kleiner en leert hij van zijn fouten.

Dit is belangrijk voor de veiligheid van AI-systemen (zoals in auto's of ziekenhuizen). Het geeft ons een manier om bewezen te zeggen: "Ja, dit systeem is kwetsbaar, en hier is precies hoe je het kunt misleiden." Dat is een krachtig hulpmiddel om AI veiliger te maken voordat het in de echte wereld wordt ingezet.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Contract And Conquer: How to Provably Compute Adversarial Examples for a Black-Box Model?" in het Nederlands.

Probleemstelling

Adversarial attacks (tegenstrijdige aanvallen) worden gebruikt om de robuustheid van diepe neurale netwerken te testen tegen kwaadwillende verstoringen van invoergegevens. Hoewel bestaande black-box aanvalsmethoden (waarbij de aanvrager geen toegang heeft tot de interne gewichten of gradiënten van het model, maar alleen query's kan sturen) empirisch effectief zijn, missen ze een cruciaal aspect: wiskundige garanties.

• Bestaande methoden kunnen niet garanderen dat er voor een specifiek model een adversarial voorbeeld gevonden kan worden.
• Er is een groeiende behoefte aan certificering van robuustheid vanwege nieuwe AI-regelgeving (zoals de EU AI Act).
• Bestaande methoden voor gecertificeerde robuustheid (zoals randomized smoothing) zijn vaak computationeel te duur of leiden tot een significante daling in prestaties op normale data, waardoor ze minder geschikt zijn voor praktische implementatie.

Het doel van dit paper is een methode te ontwikkelen die wiskundig bewijst dat een adversarial voorbeeld kan worden gevonden voor een black-box model binnen een vastgesteld aantal iteraties.

Methodologie: Contract And Conquer (CAC)

De voorgestelde methode, Contract And Conquer (CAC), is een iteratief proces dat kennisdistillatie combineert met een witte-doos-aanval op een surrogaatmodel. Het proces bestaat uit twee hoofdcomponenten die afwisselend worden uitgevoerd:

1. Kennisdistillatie (Knowledge Distillation):

   • Er wordt een klein surrogaatmodel ($S$) getraind om het gedrag van het doelwit black-box model ($T$) na te bootsen.
   • De distillatie-dataset ($D(S)$) wordt dynamisch uitgebreid. Deze begint met een subset van een hold-out dataset die dicht bij het doelwitpunt $x$ ligt, inclusief het punt $(x, T(x))$.
   • Het surrogaatmodel wordt getraind om de voorspellingen van $T$ op deze dataset te repliceren met een hoge zekerheid (confidence).

2. Witte-doos-aanval en Ruimte-contractie:

   • Op het getrainde surrogaatmodel $S$ wordt een witte-doos-aanval (bijvoorbeeld MI-FGSM) uitgevoerd binnen een zoekruimte rondom $x$ (de $L_\infty$-bal).
   • Als het gevonden adversarial voorbeeld $z_j$ overdraagbaar is naar het black-box model $T$ (d.w.z. $T(z_j) \neq T(x)$), stopt het algoritme.
   • Indien niet overdraagbaar:
     • Het paar $(z_j, T(z_j))$ wordt toegevoegd aan de distillatie-dataset om het surrogaatmodel in de volgende iteratie beter te laten leren.
     • De zoekruimte voor het adversarial voorbeeld wordt gecontracteerd. De nieuwe zoekruimte $U_{\delta}(x)_j$ is het snijpunt van de oorspronkelijke ruimte en een nieuwe, kleinere omgeving rondom het mislukte punt $z_j$.
     • De contractie-straal $\rho_j$ wordt bepaald door de afstand tussen het huidige en het vorige mislukte punt, vermenigvuldigd met een contractieparameter $t$ (waarbij $0 < t < 1$).

Dit proces herhaalt zich totdat een overdraagbaar voorbeeld wordt gevonden of het maximum aantal query's is bereikt.

Belangrijkste Bijdragen

1. Nieuwe Iteratieve Aanval: CAC introduceert een nieuwe transfer-based aanval die kennisdistillatie combineert met een gecontroleerde contractie van de zoekruimte.
2. Wiskundige Convergentiegarantie: Het paper levert een theoretisch bewijs (Lemma 3.4) dat onder milde aannames (begrensde gradiënten van het surrogaatmodel en voldoende leercapaciteit) de methode garandeert dat een adversarial voorbeeld voor het black-box model wordt gevonden binnen een vastgesteld aantal iteraties. Het bewijs toont aan dat het aantal benodigde iteraties afhangt van de initiële straal $\delta$, de vereiste precisie $\epsilon$ en de gradiëntbegrenzing.
3. Empirische Superioriteit: De methode presteert beter dan de state-of-the-art black-box aanvalsmethoden op populaire benchmarks (ImageNet en CIFAR-10) voor verschillende doelmodellen, waaronder Vision Transformers (ViT).

Resultaten

De experimenten zijn uitgevoerd op ImageNet en CIFAR-10 met doelmodellen zoals ResNet-50 en ViT-B. De resultaten worden vergeleken met bestaande methoden zoals HopSkipJump, Sign-OPT, GeoDA, SquareAttack en AdvViT.

• Aanvalsuccespercentage (ASR): CAC bereikt consistent een ASR van 1.00 (100%) in zowel hard-label als soft-label settings, terwijl sommige concurrenten (zoals AdvViT op ViT-B) lager scoren (0.75).
• Query-efficiëntie: CAC vereist gemiddeld minder query's naar het doelwitmodel dan veel concurrenten om een succesvolle aanval te voltooien (bijv. ~488 query's voor ImageNet ResNet-50 vs. ~500+ voor HopSkipJump).
• Kwaliteit van de aanval (Nabijheid): CAC genereert adversarial voorbeelden die dichter bij het originele punt liggen (kleinere $L_2$ en $L_\infty$ afstanden) dan andere methoden. Dit betekent dat de verstoringen minder zichtbaar zijn en de aanval efficiënter is.
• Robuustheid: De methode werkt effectief op zowel CNN-architecturen (ResNet) als Transformer-architecturen (ViT).

Betekenis en Impact

• Verificatie van Robuustheid: CAC biedt een praktisch instrument om te bewijzen dat een black-box model niet robuust is. Dit is essentieel voor compliance met toekomstige AI-wetgeving die eist dat systemen getest worden op kwetsbaarheden.
• Alternatief voor Gecertificeerde Defensie: Waar gecertificeerde defensiemethoden vaak te traag zijn voor productieomgevingen, biedt CAC een snelle, wiskundig onderbouwde manier om de grenzen van een model te testen zonder de interne architectuur te hoeven kennen.
• Theoretische Fundamenten: Het paper sluit de kloof tussen empirische black-box aanvallen (die vaak hopen op succes) en theoretische certificering, door een methode te bieden die beide combineert: een black-box setting met een witte-doos-garantie via een surrogaatmodel.

Kortom, Contract And Conquer is een doorbraak die het mogelijk maakt om op een betrouwbare, wiskundig onderbouwde manier de kwetsbaarheid van black-box AI-systemen te evalueren, wat cruciaal is voor de veiligheid en regulering van AI in kritieke toepassingen.