Linear Model Extraction via Factual and Counterfactual Queries

Dit paper analyseert hoe het gebruik van factuele, counterfactuele en robuuste counterfactuele queries de veiligheid van lineaire modellen beïnvloedt, en toont aan dat de keuze voor de afstandsmeting en robuustheid bepaalt of het model met één query kan worden gereconstrueerd of dat het aantal benodigde queries lineair groeit met de dimensie.

De kern

Stel je voor dat je een zwarte doos hebt. Dit is een slimme computer die beslissingen neemt, bijvoorbeeld: "Goedkeuring voor een lening" of "Afwijzing". Je ziet niet hoe hij binnenin werkt, maar je kunt wel vragen stellen.

De auteurs van dit artikel onderzoeken hoe makkelijk het is om de geheime recepten (de parameters) van deze zwarte doos te stelen door slimme vragen te stellen. Ze kijken naar drie soorten vragen:

1. Feitelijke vragen: "Wat is het antwoord voor deze specifieke persoon?"
2. Tegenwerkelijke vragen (Counterfactuals): "Wat is het kleinste veranderingetje dat ik moet maken aan deze persoon, zodat het antwoord omdraait?" (Bijv. "Als je inkomen €500 hoger was, kreeg je dan wel een lening?")
3. Robuuste tegenwerkelijke vragen: "Wat is de verandering die niet alleen het antwoord omkeert, maar ook nog eens veilig is? Zelfs als er een klein beetje ruis of onzekerheid in de data zit, moet het antwoord nog steeds omkeren."

Hier is de kern van hun ontdekkingen, vertaald naar alledaagse taal:

1. De "Slijpsel" van de Vragen (De Afstandsmeting)

Stel je voor dat je een potlood hebt om de grens van de zwarte doos te tekenen. Hoe je die potloodstrepen meet, is cruciaal.

• De soepele lijn (Differentieerbare normen): Stel je voor dat je een gladde, ronde bal gebruikt om te meten. Als je een vraag stelt met zo'n "gladde" meetlat, is het antwoord heel duidelijk.
  • Het geheim: Met slechts één slimme tegenwerkelijke vraag (en een beetje extra check) kun je het hele recept van de zwarte doos volledig reconstrueren. Het is alsof je met één raadsel het hele raadsel oplost.
• De hoekige lijn (Niet-differentieerbare normen): Stel je nu voor dat je een blokje of een ster gebruikt om te meten. Deze hebben scherpe hoeken.
  • Het geheim: Omdat de hoeken onzekerheid creëren, heb je veel meer vragen nodig. Je moet de hoekige blokken van alle kanten benaderen. In een ruimte met $p$ dimensies (bijvoorbeeld 10 eigenschappen van een klant), heb je ongeveer $p + 1$ vragen nodig om het recept te vinden. Het is alsof je een doos met veel hoeken moet omcirkelen voordat je weet hoe hij er precies uitziet.

Conclusie: Als je privacy wilt beschermen, gebruik dan een "hoekige" meetlat (zoals de $\ell_1$- of $\ell_\infty$-norm). Dat maakt het voor hackers veel moeilijker en duurder om je model te stelen.

2. De "Veiligheidsbuffer" (Robuustheid)

Soms willen bedrijven niet alleen een antwoord geven, maar ook zeggen: "Zelfs als je data een beetje onnauwkeurig is, blijft mijn advies geldig." Dit noemen ze robuustheid.

• Het effect: Als je deze extra "veiligheidsbuffer" toevoegt aan je vragen, wordt het voor de hacker nog moeilijker.
• De prijs: Om het recept te stelen, moet de hacker nu dubbel zoveel vragen stellen. Hij moet niet alleen de tegenwerkelijke vraag beantwoorden, maar ook nog eens een feitelijke vraag stellen om te checken welke kant van de grens hij precies op zit.
• De les: Robuuste uitleggen (die zeggen "dit is veilig, zelfs als er ruis is") zijn eigenlijk een extra slot op de deur. Ze beschermen je intellectueel eigendom beter, omdat ze de hacker dwingen om twee keer zo hard te werken.

3. Wat kun je al weten zonder te vragen?

De auteurs laten ook zien dat je met een paar vragen al veel kunt afleiden zonder de doos opnieuw te openen.

• Als je weet dat groep A "Nee" krijgt en groep B "Ja", dan weet je automatisch dat iedereen die tussen groep A zit ook "Nee" krijgt.
• Maar met slimme tegenwerkelijke vragen kun je veel verder kijken dan alleen het gebied tussen de punten. Je kunt de "Nee-gebieden" en "Ja-gebieden" als het ware uitbreiden en preciezer in kaart brengen, zelfs als je de exacte formule nog niet kent.

Samenvatting in één zin

Als je een slimme computer wilt beschermen tegen spionage: Gebruik "hoekige" meetlaten voor je uitleggen en zorg dat je uitleggen robuust zijn; dan moet een hacker veel meer tijd en energie steken om je geheimen te kraken, terwijl een "gladde" meetlat hem het werk heel makkelijk maakt.

Technische samenvatting

Probleemstelling

Het paper adresseert het veiligheidsrisico van model-extractie-aanvallen op lineaire machine learning-modellen. In dergelijke aanvallen probeert een attacker de parameters van een "black-box" model te reconstrueren door het model te bevragen met specifieke datapunten.

De kern van dit onderzoek ligt in de toenemende vraag om verklarende kunstmatige intelligentie (XAI), specifiek counterfactual explanations (tegenfeitelijke verklaringen). Een counterfactual is een minimale wijziging van een datapunt die de voorspelling van het model doet omslaan (bijv. van "Nee" naar "Ja"). Hoewel deze verklaringen transparantie bieden, introduceren ze een nieuw veiligheidsrisico: attackers kunnen deze counterfactuals misbruiken om de onderliggende modelparameters (de hyperplaat) exact te achterhalen.

Het paper onderzoekt drie soorten query-mechanismen:

1. Factual queries: Het opvragen van de classificatie van een punt.
2. Counterfactual (CF) queries: Het opvragen van het minimale punt dat de classificatie omkeert.
3. Robust Counterfactual (RCF) queries: Het opvragen van een punt waarbij de classificatieomkering ook geldig blijft voor alle verstoringen binnen een bepaalde robuustheidsset (een "bal" rond het punt).

Het doel is om te bepalen hoeveel informatie deze queries onthullen over de classificatiegebieden en hoeveel queries nodig zijn om de exacte parameters van het lineaire model te extraheren.

Methodologie

De auteurs analyseren lineaire classifiers van de vorm $h_{a,b}(x) = \text{sign}(a^\top x - b)$ in een $p$-dimensionale ruimte. Ze gebruiken technieken uit robuste optimalisatie en convexe analyse om de onzekerheidsgebieden van de parameters $(a, b)$ te karakteriseren op basis van de verkregen query-resultaten.

De analyse onderscheidt zich door de focus op het type norm die wordt gebruikt voor de afstandsberekening in de counterfactual-query:

• Differentieerbare normen: Bijvoorbeeld de $\ell_2$-norm (waar de afgeleide overal bestaat).
• Niet-differentieerbare normen: Bijvoorbeeld de $\ell_1$-norm en $\ell_\infty$-norm (waar de afgeleide niet overal bestaat, wat leidt tot een subdifferentiaal die een verzameling is in plaats van een enkel punt).

De methode omvat:

1. Formulering van classificatiegebieden: Het afleiden van wiskundige formuleringen voor de gebieden waarvoor de classificatie bekend is ("Yes" en "No" regio's) zonder het model opnieuw te bevragen. Dit wordt gedaan door het oplossen van lineaire of conische kwadratische optimalisatieproblemen.
2. Afhankelijkheid van optimaliteitsvoorwaarden: Het gebruik van de optimaliteitsvoorwaarden van de counterfactual-problemen (subdifferentiaals) om de richting van de vector $a$ te bepalen.
3. Constructie van lineaire systemen: Voor niet-differentieerbare normen wordt een strategie ontwikkeld om een set van lineair onafhankelijke punten op de hyperplaat te genereren, waardoor een lineair stelsel vergelijkingen ontstaat dat opgelost kan worden voor $a$ en $b$.

Belangrijkste Bijdragen

1. Nieuwe wiskundige karakterisaties: De auteurs leiden nieuwe, computationeel hanteerbare formuleringen af voor de classificatiegebieden ("Yes" en "No") gegeven een willekeurige set van factuals, exacte counterfactuals of robuuste counterfactuals. Dit breidt de huidige literatuur uit, die vaak uitgaat van specifieke query-strategieën.
2. Theoretische bovengrenzen voor query-aantallen: Het paper levert strikte bovengrenzen voor het aantal benodigde queries om een lineair model exact te extraheren, afhankelijk van het gekozen afstandsmaatstaf (norm) en het type query.
3. Analyse van robuustheid: Het onderzoek toont aan hoe het toevoegen van robuustheid aan counterfactuals (RCF) de privacy van het model beïnvloedt en hoeveel extra queries nodig zijn voor extractie.

Resultaten

De resultaten worden samengevat in de relatie tussen het type norm en het benodigde aantal queries:

1. Factual Queries

• Alleen factual queries leiden tot een benadering van de parameters. De classificatiegebieden worden beperkt tot de convexe hull van de bekende punten, maar kunnen worden uitgebreid via lineaire optimalisatie (Theorema 5).

2. Counterfactual Queries (CF)

• Differentieerbare normen (bijv. $\ell_2$):
  • Resultaat: Slechts één counterfactual query is voldoende om de volledige hyperplaat te extraheren.
  • Reden: De subdifferentiaal is een singleton (de gradiënt), wat direct de richting van de vector $a$ onthult.
• Niet-differentieerbare normen (bijv. $\ell_1, \ell_\infty$):
  • Resultaat: Er zijn $p + 1$ counterfactual queries nodig.
  • Reden: De subdifferentiaal is een verzameling, waardoor de richting van $a$ niet direct bekend is. De auteurs tonen aan dat men strategisch punten kan kiezen om een basis te vormen van $p$ lineair onafhankelijke punten op de hyperplaat, waarna het stelsel opgelost kan worden.

3. Robust Counterfactual Queries (RCF)

• Differentieerbare normen:
  • Resultaat: 1 RCF-query + 1 factual-query is nodig.
  • Reden: De RCF geeft de richting van $a$, maar omdat de robuuste regio niet exact op de hyperplaat ligt, is een extra factual query nodig om de kant van de classificatie (de bias $b$) te bepalen.
• Niet-differentieerbare normen:
  • Resultaat: $p + 1$ RCF-queries + $p + 1$ factual-queries zijn nodig.
  • Reden: In tegenstelling tot standaard CF's liggen RCF-punten niet op de hyperplaat, maar op een afstand ervan. Om het stelsel op te lossen, moet voor elk van de $p+1$ punten ook de oorspronkelijke classificatie (factual) bekend zijn om de vergelijkingen correct te stellen.

Significantie en Conclusie

Het paper biedt cruciale inzichten voor de beveiliging van lineaire modellen in reguliere sectoren (zoals bankwezen en gezondheidszorg), waar interpretatie vaak vereist is en niet-lineaire modellen soms verboden zijn.

• Privacy-implicaties: De keuze van de afstandsmetriek heeft een enorme impact op de veiligheid. Het gebruik van niet-differentieerbare normen (zoals $\ell_1$ of $\ell_\infty$) voor het genereren van counterfactuals biedt aanzienlijk meer privacy dan differentieerbare normen, omdat het aantal benodigde queries voor een succesvolle aanval lineair groeit met de dimensie van de data ($p$).
• Rolle van Robuustheid: Het aanbieden van robuuste counterfactuals voegt een extra laag van privacy toe. Hoewel het voor een attacker mogelijk is om het model te extraheren, vereist dit in het geval van niet-differentieerbare normen een verdubbeling van het aantal queries (zowel RCF als factual) vergeleken met standaard counterfactuals.
• Praktische Toepassing: De afgeleide wiskundige formuleringen maken het mogelijk om voor een gegeven set van queries te berekenen welke datapunten zeker als "Ja" of "Nee" worden geclassificeerd zonder het model opnieuw te raadplegen. Dit is nuttig voor het begrijpen van de grenzen van modelkennis in een privacy-context.

Kortom, de auteurs bewijzen dat de keuze van de afstandsmetriek en het niveau van robuustheid in verklaringen directe en kwantificeerbare gevolgen heeft voor de weerbaarheid van een lineair model tegen extractie-aanvallen.