Technische Samenvatting: Statistisch Ondetecteerbare Backdoors in Deep Neural Networks

1. Probleemstelling

Het artikel behandelt de implicaties voor veiligheid en vertrouwen van het "Machine-Learning-as-a-Service" (MLaaS) paradigma, waarbij een klein aantal instellingen diepe neurale netwerken (DNN's) traint voor de massa. De centrale vraag is of een tegenstander (de modeltrainer) een "backdoor" in een DNN kan inbedden die hen exclusieve controle geeft over specifieke modeloutputs (specifiek, het vermogen om adversariële voorbeelden te genereren), terwijl deze statistisch ononderscheidbaar blijft van een eerlijk getraind model, zelfs wanneer de volledige modelparameters (white-box toegang) beschikbaar zijn voor de gebruiker.

De auteurs richten zich op invariantie-gebaseerde adversariële voorbeelden, waarbij grote, adversariële wijzigingen aan de input resulteren in ongewoon kleine wijzigingen aan de output (d.w.z. $M(x) \approx M(x')$ voor $x \neq x'$). Het doel is om een machtsasymmetrie aan te tonen waarbij de trainer efficiënt dergelijke botsingen (collisions) kan genereren, terwijl elke polynomiale-tijd tegenstander zonder de backdoor dat niet kan.

2. Methodologie en Constructie

2.1 Modelbeperkingen

De constructie is van toepassing op een specifieke klasse van feedforward DNN's die aan drie beperkingen voldoet:

1. Bevroren Comprimerende Eerste Laag: De eerste laag is een willekeurige $m \times n$ Gaussische matrix ($m < n$) die niet wordt bijgewerkt tijdens de training. Dit fungeert als een willekeurige feature map.
2. Bi-Lipschitz Samenstelling: De samenstelling van alle daaropvolgende lagen is bi-Lipschitz (met distortie $\beta_{upper}$). Dit zorgt ervoor dat kleine wijzigingen in de input niet leiden tot arbitrair grote wijzigingen in de output, en vice versa. Dit wordt bereikt met bi-Lipschitz activatiefuncties (bijv. Leaky ReLU) en goed geconditioneerde gewichtsmatrices.
3. Discrete Inputs: Inputs zijn gehele getallen uit een begrensde range (bijv. pixelwaarden).

2.1 Het Backdoor Mechanisme

De kern van de constructie berust op het planten van een "backdoor" vector $z \in \{\pm 1\}^n$ in de Gaussische matrix $A$ van de eerste laag.

• Generatie: De trainer samplet een willekeurige $z$ en samplet vervolgens de rijen van $A$ zodanig dat $\|Az\|_\infty$ extreem klein is (specifiek $\leq \kappa\sqrt{n}$). Dit wordt bereikt via een rejection sampling proces (of directe conditionele sampling) waarbij rijen $a_i$ worden gesampled uit een Gaussische distributie geconditioneerd op $|a_i^\top z| \leq \kappa\sqrt{n}$.
• Activatie: Om een adversarieel voorbeeld voor een willekeurige input $x$ te genereren, berekent de trainer simpelweg $x' = x + z$. Vanwege de lineariteit van de eerste laag geldt $A(x+z) = Ax + Az \approx Ax$. Omdat de daaropvolgende lagen bi-Lipschitz zijn, blijft de uiteindelijke output $M(x')$ dicht bij $M(x)$.
• Ondetecteerbaarheid: De auteurs bewijzen dat de distributie van de backdoored matrix $A$ statistisch dicht bij een standaard i.i.d. Gaussische matrix $N(0, 1)^{m \times n}$ ligt in termen van Total Variation (TV) afstand. Deze nabijheid wordt vastgesteld door de concentratie van het aantal oplossingen $N(A)$ (het aantal $z$ waarvoor $\|Az\|_\infty$ klein is) te analyseren. Ze tonen aan dat het tweede moment van $N(A)$ dicht bij het kwadraat van het eerste moment ligt, wat impliceert dat de dichtheid van de backdoored matrix slechts een verwaarloosbare multiplicatieve factor verschilt van de eerlijke Gaussische matrix.

2.3 Cryptografische Hardheid

De veiligheid van de backdoor berust op de computationele hardheid van het vinden van een dergelijke vector $z'$ gegeven de matrix $A$. Dit probleem is equivalent aan het vinden van een korte vector in een rooster of het oplossen van het Symmetric Binary Perceptron (SBP) probleem. Onder standaard cryptografische aannames (specifiek, de worst-case hardheid van roosterproblemen zoals LWE), is het computationeel onhaalbaar voor elk polynomiale-tijd algoritme om een vector $z'$ te vinden waarvoor $\|Az'\|_\infty$ even klein is als de geplante $\|Az\|_\infty$.

3. Belangrijkste Bijdragen en Resultaten

3.1 Statistische Ondetecteerbaarheid

Het artikel bewijst dat voor elke efficiënte trainingsalgoritme $A$ die een model $M_A$ produceert onder de gestelde beperkingen, er een backdoored algoritme $B$ bestaat dat $M_B$ produceert en een backdoor $z$ heeft, zodanig dat:

• De Total Variation afstand tussen de beschrijvingen van $M_A$ en $M_B$ (inclusief alle gewichten) $\epsilon = \tilde{O}(\sqrt{m/n})$ is.
• Geen enkel algoritme, ongeacht de rekenkracht, $M_A$ en $M_B$ kan onderscheiden met een voordeel groter dan $\epsilon$. Dit is een statistische garantie, sterker dan de computationele ondetecteerbaarheid gevonden in eerdere werken (bijv. [GKVZ22]).

3.2 Exponentiële Machtsasymmetrie

Het artikel definieert backdoor strength als de ratio tussen de beste botsing die een tegenstander kan vinden en de botsing die de backdoor houder kan vinden.

• Theorem 7: Voor modellen die aan de beperkingen voldoen, is de backdoor strength ten minste $\tilde{\Omega}\left(\frac{2^{n/m}}{\sqrt{nm} \cdot \beta_{upper}}\right)$.
• Dit impliceert een exponentieel voordeel (in de compressieratio $n/m$) voor de backdoor houder. Terwijl de trainer botsingen kan genereren met afstand $\delta_0 \approx 2^{-n/m}$, is elke polynomiale-tijd tegenstander beperkt tot botsingen met afstand $\delta_1 \approx \text{negl}(n)$ (of aanzienlijk groter afhankelijk van de hardheidsaanname), waardoor de capaciteit van de backdoor houder exponentieel sterker is.

3.3 Authenticatiemechanisme

De auteurs interpreteren deze backdoors als een "ingebouwd" authenticatiemechanisme. Aangezien de backdoor vector $z$ de generatie van een bewijs mogelijk maakt (een paar $x, x+z$ met kleine output afstand) dat computationeel onhaalbaar is voor anderen om te vervalsen, kan de trainer het eigendom van het modeltrainingsproces bewijzen zonder de input/output gedrag van het model te wijzigen.

3.4 Empirische Validatie

Het artikel bevat een proof-of-concept implementatie op de Fashion-MNIST dataset:

• Architectuur: Een DNN met een bevroren $256 \times 784$ Gaussische eerste laag en daaropvolgende bi-Lipschitz lagen.
• Resultaten: Het backdoored model bereikte $\approx 86,5\%$ nauwkeurigheid (iets lager dan het eerlijke model door de distributieverschuiving bij het schalen van inputs).
• Collision Strength: Experimenten toonden aan dat de geplante oplossing $z$ resulteerde in $\|Az\| \approx 10^{-10}$, terwijl de beste oplossingen gevonden door standaard algoritmen (inclusief LLL en heuristische methoden) vele grootteordes groter waren ($\approx 0.1$), wat een backdoor strength van ongeveer $10^9$ demonstreert.
• Ondetecteerbaarheid: Statistische tests (D'Agostino-Pearson) op de rijen van de backdoored matrix toonden geen significante afwijking van normaliteit, wat de theoretische claims van ondetecteerbaarheid ondersteunt.

4. Betekenis en Claims

Het artikel beweert aan te tonen dat er een fundamentele machtsasymmetrie bestaat tussen modeltrainers en gebruikers in de context van DNN's.

• Theoretische Doorbraak: Het stelt vast dat natuurlijke machine learning componenten (specifiek willekeurige Gaussische projecties gebruikt in random feature learning) inherent cryptografische hardheidseigenschappen bezitten (gerelateerd aan roosterproblemen) die kunnen worden geëxploiteerd om statistisch ondetecteerbare backdoors te creëren.
• White-Box Security: In tegenstelling tot eerdere werken die alleen computationele ondetecteerbaarheid bereikten of black-box toegang vereisten, bereikt dit werk statistische ondetecteerbaarheid, zelfs wanneer de tegenstander volledige white-box toegang heeft tot de modelgewichten.
• Beperkingen en Bescheidenheid: De auteurs erkennen dat hun constructie rust op specifieke architecturale beperkingen (bevroren eerste laag, bi-Lipschitz daaropvolgende lagen). Ze merken op dat hoewel hun theoretische grenzen logaritmische factoren nauwkeurig zijn, hun empirische resultaten suggereren dat de werkelijke backdoor strength zelfs hoger kan zijn dan de theoretische ondergrenzen, mogelijk omdat de statistische afstand pas niet-verwaarloosbaar wordt bij extreem kleine $\kappa$-waarden waar computationele tests falen. Ze beweren niet de standaard cryptografische primitieven te breken, maar laten zien dat de hardheidsaannames die eraan ten grondslag liggen natuurlijk ingebed zijn in bepaalde DNN-architecturen.

Het artikel concludeert dat als deze beperkingen in de praktijk gebruikelijk zijn (zoals in random feature learning en Lipschitz-geregulariseerde netwerken), de robuustheid van dergelijke DNN's niet volledig gecertificeerd kan worden tegen een kwaadwillende trainer die deze backdoors kan planten.