💻 computer science

Differential Zonotopes for Verifying Global Robustness of DNNs

Dieses Paper führt TwoSafe ein, ein neuartiges statisches Analysewerkzeug, das differenzielle Halo-Zonotope nutzt, um die globale Robustheit tiefer neuronaler Netze effizient zu verifizieren, wobei es bestehende State-of-the-Art-Techniken sowohl in der Präzision als auch in der Skalierbarkeit signifikant übertrifft.

Ursprüngliche Autoren: Anagha Athavale, Samuel Teuber, Matteo Maffei, Ezio Bartocci, Dejan Nickovic, Georg Weissenbacher

Veröffentlicht 2026-06-23

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Anagha Athavale, Samuel Teuber, Matteo Maffei, Ezio Bartocci, Dejan Nickovic, Georg Weissenbacher

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben einen sehr intelligenten Roboter (ein tiefes neuronales Netz) gebaut, der wichtige Entscheidungen trifft, wie etwa das Identifizieren von Teilchen in einem Physikexperiment oder das Erkennen, ob eine Person geht oder steht, basierend auf Sensordaten. Sie möchten absolut sicher sein, dass Ihr Roboter nicht verwirrt wird, wenn die Eingabedaten etwas „verrauscht“ oder unvollkommen sind – wie ein Sensorfehler oder ein Fleck auf einer Kameralinse.

In dieser Arbeit geht es um eine neue, super-effiziente Methode, um zu testen, ob diese Roboter „robust“ genug sind, um mit diesem Rauschen umzugehen, ohne einen Fehler zu machen.

Hier ist die Aufschlüsselung ihrer Arbeit unter Verwendung einfacher Analogien:

1. Das Problem: Jedes mögliche Szenario prüfen

Normalerweise, wenn wir einen Roboter testen, prüfen wir, ob er für ein spezifisches Bild funktioniert, und prüfen dann, ob er für dasselbe Bild mit ein wenig hinzugefügtem Rauschen ebenfalls funktioniert. Dies wird als Lokale Robustheit bezeichnet. Es ist wie die Prüfung, ob eine Brücke hält, wenn ein einzelnes Auto darüberfährt.

Aber die Autoren wollten Globale Robustheit prüfen. Das ist viel schwieriger. Es ist wie die Frage: „Wenn irgendwelche zwei Autos gleichzeitig über die Brücke fahren und sie nah beieinander liegen, wird die Brücke dann immer noch halten?“

Die Herausforderung: Das Prüfen jedes möglichen Paares von Eingaben ist wie der Versuch, jedes Sandkorn an einem Strand zu zählen. Es verbraucht so viel Rechenleistung, dass ältere Werkzeuge nur winzige, einfache Roboter (mit sehr wenigen „Neuronen“) bewältigen konnten.

2. Der alte Weg vs. der neue Weg

Der alte Weg (Der „Brute-Force“-Ansatz):
Frühere Werkzeuge versuchten dies zu lösen, indem sie zwei Roboter separat prüften und dann deren Ergebnisse voneinander subtrahierten. Stellen Sie sich vor, Sie versuchen, den Unterschied zwischen zwei Läufern zu messen, indem Sie sie separat stoppen und die Mathematik später durchführen. Das Problem ist, dass der „Mathematik“-Teil Fehler einführt, was das Ergebnis zu vage macht, um nützlich zu sein, wenn es um große Roboter geht.

Der neue Weg (Der „Schritt-für-Schritt“-Ansatz):
Die Autoren haben ein neues Werkzeug namens TwoSafe entwickelt. Anstatt die beiden Prüfungen separat durchzuführen, lassen sie sie zusammen, Seite an Seite, in perfekter Synchronisation laufen.

Die Analogie: Stellen Sie sich zwei Zwillinge vor, die ein Rennen laufen. Anstatt sie separat zu stoppen und ihre Zeiten später zu vergleichen, lassen Sie sie Hand in Hand (oder verbunden durch ein Seil) laufen. Sie messen den Abstand zwischen ihren Händen, während sie laufen.
Die Innovation: Sie verwenden eine mathematische Form namens Zonotop (denken Sie an einen flexiblen, mehrdimensionalen Ballon), um die Zwillinge zu verfolgen. Sie haben eine spezielle Version namens Differential Halo Zonotope erfunden.
- Das „Halo“ (der Heiligenschein) ist wie eine Sicherheitsblase um die Zwillinge. Es erlaubt ihnen, sich leicht voneinander zu entfernen (was das Rauschen/die Störung simuliert), hält aber die Kontrolle darüber, wie weit sie genau auseinanderdriften können. Dies verhindert die „vagen Mathematik“-Fehler der alten Methode.

3. Eine klügere Regel: Das „Konfidenz“-Schlupfloch

Das Paper führt auch eine neue Regel ein, was als „Fehler“ gilt.

Die strenge Regel (Asymmetrisch): Wenn der Roboter ein klares Bild eines „Hundes“ sieht (99 % sicher) und ein wenig Rauschen ihn dazu bringt, „Katze“ zu sagen (selbst wenn er sich nur zu 10 % sicher ist), sagt die strenge Regel: FEHLGESCHLAGEN. Es spielt keine Rolle, dass der Roboter sich über das „Katze“-Label unsicher war; er hat seine Meinung geändert, also ist er defekt.
Die klügere Regel (Symmetrisch): Die Autoren sagen: „Warten Sie mal.“ Wenn der Robot ein „Hund“-Bild sieht (99 % sicher) und das Rauschen ihn zu „Katze“ macht (10 % sicher), dann ist das eigentlich in Ordnung! Der Roboter sagt im Grunde: „Ich denke, es ist ein Hund, aber wenn Sie mich zwingen zu raten, bin ich mir wirklich unsicher über die Katze.“
- Die Analogie: Stellen Sie sich einen Sicherheitsmann vor. Wenn er zu 99 % sicher ist, dass eine Person ein Mitarbeiter ist, aber ein wenig Nebel ihn dazu bringt, zu zögern und „Vielleicht ein Fremder?“ zu sagen (mit geringer Konfidenz), sollte er nicht gefeuert werden. Er sollte nur in Schwierigkeiten geraten, wenn er selbstbewusst „FREMDER!“ ruft, obwohl es eigentlich ein Mitarbeiter ist.
- Diese neue Symmetrische Regel erlaubt es, viel komplexere Roboter zu verifizieren, da sie „Low-Confidence“-Fehler ignoriert, die Menschen natürlich erkennen oder ignorieren würden.

4. Die Ergebnisse: Skalierung nach oben

Die Autoren haben ihr neues Werkzeug, TwoSafe, an realen Robotern getestet, die in der Praxis eingesetzt werden:

Teilchenphysik (LHC): Sortieren von Teilchen in einem massiven Collider.
Human Activity Recognition (HAR): Feststellen, ob eine Person geht oder sitzt, mithilfe von Wearable-Sensoren.
Flugsicherung (ACAS): Vermeidung von Flugzeugkollisionen.

Das Ergebnis:

Geschwindigkeit: TwoSafe war signifikant schneller als die bisher besten Werkzeuge.
Größe: Während alte Werkzeuge nur winzige Roboter (etwa 15 Neuronen) handhaben konnten, verifizierte TwoSafe erfolgreich Roboter mit 500 Neuronen und Eingaben mit 561 Dimensionen. Das ist wie der Übergang von der Überprüfung eines Fahrrads zur Überprüfung eines riesigen Containerschiffs.
Genauigkeit: Die alten Werkzeuge lösten oft „Fehlalarme“ aus (indem sie dachten, ein Roboter sei defekt, obwohl er es nicht war), weil ihre Mathematik zu grob war. TwoSafe war viel präziser und bewies Sicherheit dort, wo andere scheiterten.

Zusammenfassung

Das Paper präsentiert ein neues mathematisches „Sicherheitsgeschirr“ (Differential Halo Zonotopes), das es uns ermöglicht, zu testen, ob komplexe KI-Systeme über ihren gesamten Betriebsbereich hinweg robust gegenüber Rauschen sind. Durch das synchrone Durchführen von Tests und die Annahme einer realistischeren Definition von „Konfidenz“ gelang es ihnen, KI-Systeme zu verifizieren, die zuvor zu groß und komplex waren, um geprüft zu werden.

Technisches Resümee: Differenzielle Zonotope zur Verifizierung globaler Robustheit von DNNs

1. Problemstellung

Tiefe neuronale Netze (DNNs) werden zunehmend in sicherheitskritischen Bereichen wie dem Transportwesen und dem Gesundheitswesen eingesetzt, in denen deren Robustheit gegenüber Eingabestörungen essenziell ist. Während lokale Robustheit (die Gewährleistung, dass Vorhersagen bei kleinen Störungen um einen spezifischen Input herum unverändert bleiben) eine gut untersuchte Sicherheitseigenschaft ist, stellt die globale Robustheit eine strengere Anforderung dar. Globale Robustheit verlangt, dass für alle Paare von Eingaben innerhalb eines gewissen Abstands die Vorhersagen des Modells konsistent bleiben.

Formal gesehen handelt es sich bei der globalen Robustheit um eine 2-Sicherheitseigenschaft, die die Verifizierung einer Relation zwischen zwei universell quantifizierten Ausführungspfaden erfordert, statt nur eines einzelnen Pfades. Diese Komplexität macht die globale Verifizierung signifikant anspruchsvoller als die lokale Verifizierung. Bestehende Methoden für die konfidenzbasierte globale Robustheit (welche die Garantien auf hochkonfidente Vorhersagen beschränkt, um Entscheidungsgrenzen zu vermeiden) nutzen spezialisierte Erfüllbarkeitssolver, leiden jedoch unter mangelnder Skalierbarkeit und sind derzeit auf Netzwerke mit nur einigen Dutzend Neuronen beschränkt.

2. Methodik

Die Arbeit schlägt ein neuartiges statisches Analyse-Framework vor, das auf differenziellen Halo-Zonotopen basiert, um die globale Robustheit effizient zu verifizieren.

2.1 Differenzielle Halo-Zonotope

Die zentrale technische Innovation ist die Erweiterung des Zonotop-Abstrakten-Domains. Standard-Zonotope repräsentieren Punktmengen über ein Zentrum und eine Generator-Matrix. Um globale Robustheit zu verifizieren, müssen die Autoren zwei Ausführungen desselben DNN mit unterschiedlichen Inputs gleichzeitig verfolgen.

Herausforderung: Naive Adaptionen differenzieller Zonotope (die zuvor für die DNN-Äquivalenzverifizierung verwendet wurden, bei denen die Inputs identisch sind) scheitern bei der globalen Robustheit. Die Initialisierung der Inputs als identisch oder die Verwendung vollständig unabhängiger Generatoren führt entweder zu Unsoundness oder zu übermäßiger Überapproximation (Verlust an Präzision).
Lösung: Die Autoren führen differenzielle Halo-affine Formen ein. Diese Kodierung verteilt die Störungsgrenze $\epsilon$ $ϵ$ auf zwei Generatoren:
1. Ein primärer Generator, der zwischen den beiden Ausführungen geteilt wird, um die Korrelation aufrechtzuerhalten.
2. Sekundäre Generatoren, die für jede Ausführung unabhängig sind, um die Störung zu modellieren.
Mechanismus: Diese „Halo“-Struktur ermöglicht es dem System, sound und präzise zu kodieren, dass zwei Inputs $x$ und $y$ innerhalb einer Bounding Box $[l, u]$ liegen und die Bedingung $|x - y| \le \epsilon$ erfüllen. Das differenzielle Zonotop $\mathcal{Z}_\Delta$ verfolgt die Differenz zwischen den Ausführungen im Gleichschritt, was engere Schranken für die Divergenz liefert als die Subtraktion einzelner Zonotope.

2.2 Symmetrische konfidenzbasierte globale Robustheit

Das Paper identifiziert eine Einschränkung in der bestehenden Definition der konfidenzbasierten globalen Robustheit (der asymmetrischen Variante), welche fordert, dass ein hochkonfidenter Input $x$ nicht zu einem anderen Klassifikationsergebnis $y$ gestört werden darf, ungeachtet der Konfidenz von $y$ . Die Autoren argumentieren, dass dies zu restriktiv ist, da eine Störung, die zu einer niedrigkonfidenten, anderen Vorhersage führt, praktisch akzeptabel ist (z. B. durch Auslösung einer manuellen Überprüfung).

Sie schlagen eine symmetrische Variante vor:

Definition: Für alle zwei Inputs $x, y$ innerhalb der Distanz $\epsilon$ gilt: Wenn beide mit einer Konfidenz größer als ein Schwellenwert $\tau$ klassifiziert werden, müssen sie zur selben Klasse gehören.
Vorteil: Diese Lockerung erlaubt einer breiteren Klasse von Netzwerken, als „robust“ zu gelten, während sie für sicherheitskritische Anwendungen, in denen Low-Confidence-Outputs über Fallback-Mechanismen gehandhabt werden, weiterhin sinnvoll bleibt.

2.3 Verifizierungsalgorithmus

Der Verifizierungsprozess (implementiert im Tool TwoSafe) folgt diesen Schritten:

Initialisierung: Konstruktion eines differenziellen Halo-Zonotops, das den Eingaberaum und die Störungsbeschränkungen repräsentiert.
Propagation: Propagation des Zonotops durch die DNN-Schichten. Für ReLU-Aktivierungen führt die Methode neue Generatoren ein, um die Nichtlinearität zu überapproximieren und dabei die differenzielle Struktur beizubehalten.
Eigenschaftsprüfung: Am Ausgang formuliert das System ein Lineares Programmierproblem (LP), um zu prüfen, ob Paare von Outputs existieren, bei denen die Klassen divergieren, während beide den Konfidenzschwellenwert $\tau$ erfüllen.
Verfeinerung: Falls die Prüfung aufgrund von Überapproximation nicht schlüssig ist, führt der Algorithmus ein Generator-Splitting durch. Im Gegensatz zum Standard-Input-Splitting spaltet dies die Generatoren des differenziellen Halo-Zonotops auf, um die Approximation zu verfeinern, ohne die Abdeckung des Störungsraums zu verlieren.

3. Zentrale Beiträge

Differenzielle Halo-Zonotope: Ein neues abstraktes Domain, das Zonotope erweitert, um Paare gestörter Inputs gemeinsam im Gleichschritt zu propagieren und so deren Divergenz eng zu begrenzen. Dies ermöglicht die Verifizierung globaler 2-Sicherheitseigenschaften mit höherer Präzision als eine Einzelanalyse.
Symmetrische konfidenzbasierte globale Robustheit: Eine neue Definition der globalen Robustheit, die Konsistenz nur zwischen hochkonfidenten Vorhersagen erfordert. Diese Definition ist strikt weniger restriktiv als die asymmetrische Variante und ermöglicht eine effiziente Verifizierung innerhalb des vorgeschlagenen Frameworks.
Soundness-Beweis: Ein formaler Beweis der Soundness der differenziellen Zonotop-basierten statischen Analyse, wobei die Kernergebnisse in Isabelle formalisiert wurden.
TwoSafe Tool & Evaluation: Implementierung des Ansatzes in einem neuen Tool, TwoSafe, das den Stand der Technik (CGR-Baseline) sowohl in der Präzision als auch in der Skalierbarkeit deutlich übertrifft.

4. Experimentelle Ergebnisse

Die Autoren evaluierten TwoSafe anhand von vier Benchmarks: Law (klein), LHC (Teilchenklassifizierung), ACAS Xu (Kollisionsvermeidung) und HAR (menschliche Aktivitätserkennung).

Skalierbarkeit: TwoSafe verifizierte erfolgreich die globale Robustheit auf Netzwerken mit bis zu 500 ReLU-Neuronen und 561 Eingangsdimensionen (HAR-Benchmark). Im Gegensatz dazu kam die Baseline (CGR) bei diesen größeren Netzwerken zu einem Timeout oder erschöpfte den Speicher.
Präzision: Die Baseline lieferte häufig spurenechte Gegenbeispiele (spurious counterexamples) aufgrund grober Softmax-Approximationen, insbesondere bei Netzwerken mit vielen Output-Klassen. TwoSafe vermied diese False Positives.
Performance: TwoSafe demonstrierte signifikante Beschleunigungen. Beispielsweise verifizierte es die Robustheit beim LHC-Benchmark in unter 3 Sekunden, während die Baseline nach 2 Stunden Zeitüberschreitung abbrach.
Symmetrisch vs. Asymmetrisch: Die symmetrische Eigenschaft ermöglichte die erfolgreiche Verifizierung in Parameterregimen, in denen die asymmetrische Eigenschaft unschlüssig war oder fehlschlug. Beispielsweise war beim HAR-Benchmark mit $\epsilon=0.01$ die symmetrische Eigenschaft verifizierbar, während die asymmetrische Variante einen Timeout verursachte.

5. Bedeutung und Ansprüche

Das Paper behauptet, das inhärente Spannungsverhältnis zwischen der Stärke der Robustheitsgarantien und der Skalierbarkeit von Verifizierungswerkzeugen gelöst zu haben. Durch den Wechsel von lokaler zu globaler Robustheitsverifizierung und die Nutzung differenzieller Halo-Zonotope zeigen die Autoren, dass es möglich ist, wesentlich breitere und tiefere Netzwerke zu verifizieren als bisher möglich.

Die Einführung der symmetrischen konfidenzbasierten globalen Robustheit wird als praktischer Fortschritt präsentiert, der eine „bedeutsame Vorstellung von Robustheit“ bietet, indem er anerkennt, dass Low-Confidence-Vorhersagen in realen Systemen oft anders gehandhabt werden. Die Arbeit etabliert, dass die differenzielle Verifizierung, wenn sie für 2-Sicherheitseigenschaften angepasst wird, auf Netzwerke skalieren kann, die um eine Größenordnung größer sind als bisherige Techniken, was die Zertifizierung der globalen Robustheit für real eingesetzte Modelle praktikabel macht.