Formulating Subgroup Discovery as a Quantum Optimization Problem for Network Security

Dieser Beitrag stellt eine neuartige, quantenverstärkte Pipeline vor, die die Subgruppenentdeckung zur Netzwerk-Intrusion-Erkennung als quadratisches ungebundenes binäres Optimierungsproblem (QUBO) formuliert und nachweist, dass der Quantum Approximate Optimization Algorithm (QAOA) auf IBM-Hardware wettbewerbsfähige, interpretierbare Multi-Feature-Angriffsmuster identifizieren kann, die klassische Heuristiken häufig übersehen, während gleichzeitig die durch Rauschen begrenzte Skalierungsgrenze von NISQ-Geräten empirisch ermittelt wird.

Das Wesentliche

Stellen Sie sich vor, Sie sind ein Sicherheitsbeamter, der versucht, einen Dieb in einem riesigen, überfüllten Bahnhof zu orten. Der Bahnhof verfügt über Tausende von Kameras, Sensoren und Ticketscannern, die alle einen ständigen Datenstrom erzeugen.

Das Problem: Der „Black-Box"-Wächter
Derzeit sind die meisten Sicherheitssysteme (sogenannte Intrusion Detection Systems) wie hochtrainierte, aber stumme Wächter. Sie sind hervorragend darin, den Dieb zu orten und Alarm zu schlagen. Allerdings können sie nicht erklären, warum. Sie sagen einfach nur „Dieb!", ohne Ihnen zu verraten, ob es daran lag, dass die Person lief, einen roten Hut trug oder eine bestimmte Art von Tasche bei sich hatte. In der Cybersicherheit macht dieses Fehlen von Erklärungen es für menschliche Analysten schwierig zu verstehen, wie der Angriff stattfand oder wie man ihn beim nächsten Mal verhindern kann.

Die Lösung: Das „Rezept" für einen Dieb finden
Diese Arbeit stellt eine neue Methode namens Subgroup Discovery vor. Anstatt nur zu fragen „Ist das ein Dieb?", fragt sie: „Welche spezifische Kombination von Merkmalen lässt jemanden wie einen Dieb aussehen?"

• Analogie: Anstatt nur eine Person zu markieren, versucht das System, eine Regel wie diese zu finden: „Wenn jemand einen roten Hut TRÄGT UND einen Rucksack TRÄGT UND läuft, dann ist die Wahrscheinlichkeit, dass er ein Dieb ist, 99 %."
• Das Ziel ist es, diese für Menschen leicht verständlichen „Rezepte" (Regeln) zu finden.

Die Herausforderung: Die Nadel im Heuhaufen
Das Problem besteht darin, dass es zu viele mögliche Kombinationen gibt. Wenn Sie 41 verschiedene Merkmale haben (wie Hutfarbe, Geschwindigkeit, Taschentyp usw.), ist die Anzahl möglicher Regeln astronomisch.

• Analogie: Stellen Sie sich vor, Sie versuchen, das perfekte Kuchenrezept zu finden, indem Sie jede mögliche Kombination von Zutaten testen. Ein herkömmlicher Computer versucht dies, indem er ein Rezept probiert, dann eine Zutat hinzufügt, erneut probiert und nur die besten behält. Das ist schnell, aber es ist „gierig". Wenn eine einzelne Zutat für sich allein schlecht schmeckt (wie Salz in einem Kuchen), wirft der Computer sie weg, selbst wenn dieses Salz den Kuchen später in Kombination mit Schokolade fantastisch machen würde. Es verpasst die Kombinationen der „Geheimzutat".

Die Quanten-Drehung: Der „magische Super-Scanner"
Die Autoren versuchten, einen Quantencomputer zur Lösung dieses Problems einzusetzen.

• Analogie: Während der herkömmliche Computer Rezepte nacheinander probiert, ist der Quantencomputer wie ein magischer Scanner, der alle möglichen Rezepte gleichzeitig probieren kann (unter Verwendung eines Konzepts namens Superposition). Er bleibt nicht stecken und wirft „schlechte" Zutaten weg, nur weil sie allein schlecht aussehen; er sieht, wie sie in der gesamten Mischung zusammenwirken.

Wie sie es taten

1. Die Karte (QUBO): Sie übersetzten das Problem, das beste „Dieb-Rezept" zu finden, in eine mathematische Karte namens QUBO. Stellen Sie sich dies vor als die Umwandlung der Suche nach dem besten Kuchenrezept in eine Landschaft aus Hügeln und Tälern, wobei das tiefste Tal die beste Regel darstellt.
2. Der Algorithmus (QAOA): Sie verwendeten einen spezifischen Quantenalgorithmus (QAOA), um einen Ball durch diese Landschaft zu rollen, um das tiefste Tal zu finden.
3. Die Hardware: Sie führten dies auf einem echten Quantencomputer (IBM's „Pittsburgh"-Maschine) aus, der in der Cloud verfügbar war.

Was sie fanden

• Im kleinen Maßstab funktioniert es gut: Als sie es mit einer kleinen Anzahl von Merkmalen testeten (10 bis 15 „Zutaten"), fand der Quantencomputer Regeln, die fast so gut waren wie die perfekte Antwort (98 % bis 99 % Genauigkeit).
• Die Rausch-Wand: Als sie mehr Merkmale hinzufügten (bis zu 30), begann der Quantencomputer, Fehler zu machen.
  • Analogie: Stellen Sie sich vor, der Quantencomputer ist ein sehr empfindliches Instrument. Je größer das Experiment wird, desto lauter wird das „statische Rauschen" im Raum, das das Signal übertönt. Bei 30 Merkmalen war das Rauschen so laut, dass der Computer die richtige Antwort nicht mehr finden konnte.
• Die Geheimzutat: Der aufregendste Teil ist, dass der Quantencomputer einige „Dieb-Rezepte" fand, die der herkömmliche Computer vollständig übersehen hatte.
  • Beispiel: Der herkömmliche Computer ignorierte eine bestimmte Kombination aus „Diensttyp" und „Anzahl der Verbindungen", weil weder für sich allein verdächtig aussah. Der Quantencomputer sah, dass sie zusammen ein perfekter Indikator für einen Angriff waren. Eine dieser einzigartigen Regeln war zu 99,6 % genau beim Aufspüren einer bestimmten Art von Cyberangriff (genannt R2L).

Das Fazit
Diese Arbeit behauptet nicht, dass Quantencomputer derzeit schneller oder besser darin sind, Hacker aufzuhalten als herkömmliche Computer. Tatsächlich dauerte die Ausführung auf dem Quantencomputer viel länger.

Stattdessen beweist sie, dass Quantencomputer Muster finden können, die herkömmliche Computer übersehen. Sie zeigte, dass durch das gleichzeitige Betrachten aller Möglichkeiten Quantenmethoden komplexe, versteckte Regeln entdecken können, die Menschen helfen, Cyberangriffe besser zu verstehen. Damit dies jedoch mit realen, massiven Daten funktioniert, müssen Quantencomputer jedoch viel leiser (weniger verrauscht) und leistungsfähiger werden.

Zusammenfassung in einem Satz:
Die Forscher nutzten einen Quantencomputer, um versteckte „Rezepte" für Cyberangriffe zu finden, die herkömmliche Computer übersehen hatten, und bewiesen, dass Quantenmethoden komplexe Muster aufdecken können, obwohl die aktuelle Hardware noch zu verrauscht ist, um sehr große Probleme zu bewältigen.

Technische Zusammenfassung

1. Problemstellung

Netzwerk-Intrusion-Detection-Systeme (IDS) verlassen sich typischerweise auf Black-Box-Machine-Learning-Modelle, die zwar eine hohe Klassifizierungsgenauigkeit erreichen, aber keine Erklärbarkeit bieten. Cybersecurity-Analysten benötigen interpretierbare Regeln, um zu verstehen, warum bestimmter Datenverkehr als bösartig gekennzeichnet wird.

Subgroup Discovery (SD) adressiert dies, indem es interpretierbare konjunktive Regeln (Subgruppen) findet, die Feature-Interaktionen charakterisieren, die mit Angriffsverkehr assoziiert sind. Das Finden optimaler Subgruppen ist jedoch ein NP-schweres kombinatorisches Optimierungsproblem.

• Die Herausforderung: Mit zunehmender Anzahl von Features ($n$) wächst der Suchraum exponentiell ($C(n, k)$).
• Klassische Einschränkung: Standard-klassische Heuristiken wie Beam Search verwenden gieriges Beschneiden (greedy pruning). Sie erweitern Subgruppen Feature für Feature und behalten nur die am besten bewerteten Kandidaten bei. Dieser Ansatz übersieht oft kritische Multi-Feature-Interaktionsmuster, bei denen einzelne Features isoliert betrachtet schwach erscheinen, aber in Kombination hochgradig diskriminierend sind.
• Das Ziel: SD als kombinatorisches Optimierungsproblem zu formulieren, das durch Quantenalgorithmen lösbar ist, mit dem spezifischen Ziel, interpretierbare, hochpräzise Angriffsregeln zu entdecken, die von klassischen Heuristiken herausgeschnitten werden.

2. Methodik

Die Autoren schlagen eine quantenverstärkte Pipeline vor, die das SD-Ziel in ein Quadratic Unconstrained Binary Optimization (QUBO)-Problem kodiert und es mit dem Quantum Approximate Optimization Algorithm (QAOA) auf IBM-Quantenhardware (ibm_pittsburgh) löst.

A. Datenvorverarbeitung (NSL-KDD)

• Datensatz: Verwendung des NSL-KDD-Benchmarks (41 Features, 4 Angriffstypen: DoS, Probe, R2L, U2R).
• Binärisierung: Features werden standardisiert und durch Schwellenwertbildung in Binärwerte $\{0, 1\}$ umgewandelt. Kategorische Features werden mittels One-Hot-Encoding mit kardinaleitungsabhängiger Filterung verarbeitet, um das Qubit-Budget zu managen.
• Ziel: Binäres Label (Normal vs. Angriff).

B. QUBO-Formulierung

Die Kerninnovation besteht darin, die Metrik Weighted Relative Accuracy (WRAcc) in eine QUBO-Matrix zu kodieren.

• Ziel: Maximierung von WRAcc, die Abdeckung (Anzahl der Datensätze) und Kontrast (Abweichung von der Basisangriffsrate) ausbalanciert.
• Least-Squares-Fit: Da WRAcc inhärent nicht quadratisch ist, passen die Autoren ein Least-Squares-Regressionmodell an, um die WRAcc-Landschaft über Feature-Teilmengen zu approximieren.
  • $Q^* = \arg\min_Q \sum (x^T Q x - (-WRAcc(x)))^2$
• Kardinalitätsstrafe: Ein additiver Strafterm wird eingefügt, um die Lösung zu zwingen, genau $K$ Features auszuwählen.
• Ising-Mapping: Das QUBO wird in einen Ising-Hamiltonian ($H_C$) mit lokalen Feldern ($h_i$) und Kopplungstermen ($J_{ij}$) umgewandelt, was die Generierung nicht-trivialer Zwei-Qubit-Verflechtungsgatter (ZZ-Terme) auf der Hardware ermöglicht.

C. Quantenausführung (QAOA)

• Algorithmus: QAOA mit Tiefe $p$ (Schichten).
• Hardware: Ausgeführt auf ibm_pittsburgh (supraleitende Qubits) für Qubit-Anzahlen im Bereich von 10 bis 30.
• Optimierung: Verwendung des klassischen Optimierers COBYLA mit Warm-Start (Verwendung von Parametern aus Tiefe $p$ zur Initialisierung von $p+1$) und Multi-Start-Strategien.
• Fehlerminderung: Einsatz von Dynamical Decoupling (XY4-Sequenz) und Pauli-Gate-Twirling zur Minderung von Rauschen.

D. Evaluierungsrahmen

Das Papier führt einen Dual Approximation Ratio-Rahmen ein:

1. $r_5$ (Hamiltonian Quality): Verhältnis der besten gesampelten Ising-Energie zur wahren Grundzustandsenergie.
2. $r_6$ (Application Quality): Verhältnis der besten von QAOA gefundenen WRAcc (bei Zielkardinalität) zur exhaustiven Ground-Truth-WRAcc.

• Basislinien: Vergleich mit Exhaustive Enumeration (Ground Truth für kleines $n$) und Beam Search (Standardheuristik).

3. Hauptbeiträge

1. Erste QUBO-Formulierung für SD: Dies ist die erste Arbeit, die Subgroup Discovery als QUBO-Problem darstellt, wodurch Quantenalgorithmen direkt die Qualität interpretierbarer Regeln (WRAcc) optimieren können und nicht nur die Klassifizierungsgenauigkeit.
2. Neuartige QUBO-zu-WRAcc-Mapping: Entwicklung eines Least-Squares-Regressionansatzes zur Anpassung der WRAcc-Landschaft, wodurch sichergestellt wird, dass der resultierende Hamiltonian ausreichende off-diagonale Kopplungen besitzt, um auf der Hardware Verschränkung zu erzeugen.
3. Empirische NISQ-Skalierungsgrenze: Bereitstellung gemessener Daten darüber, wie sich die QAOA-Leistung auf echter Hardware mit der Qubit-Anzahl verschlechtert, wodurch eine praktische Fidelitätsgrenze für dichte QUBO-Instanzen etabliert wird.
4. Entdeckung "quanten-spezifischer" Subgruppen: Demonstration, dass QAOA Multi-Feature-Interaktionsmuster finden kann, die gieriger Beam Search aufgrund ihrer schwachen Zwischenbewertungen systematisch ausschließt.

4. Hauptergebnisse

• QUBO-Fit-Qualität: Die Least-Squares-Approximation erreichte ein $R^2 = 0,989$ und eine Spearman-Korrelation $\rho = 0,899$ gegenüber der wahren WRAcc-Landschaft, was die Validität der quadratischen Kodierung bestätigt.
• Hardware-Skalierungsleistung (bei Tiefe $p=1$):
  • 10 Qubits: $r_6 = 0,983$ (Hochgradig konkurrenzfähig mit Ground Truth).
  • 15 Qubits: $r_6 = 0,971$.
  • 20 Qubits: $r_6 = 0,855$.
  • 25 Qubits: $r_6 = 0,624$.
  • 30 Qubits: $r_6 = 0,039$ (Leistung bricht aufgrund von Rauschdominanz zusammen).
  • Beobachtung: Der rauschfreie Simulator behielt über alle Skalen hinweg $r_6 = 1,0$ bei, was bestätigt, dass die Verschlechterung auf Hardware-Rauschen und nicht auf algorithmisches Versagen zurückzuführen ist.
• QAOA-eindeutige Subgruppen:
  • QAOA entdeckte 6-Feature-Subgruppen, die Kombinationen von dst_host_srv_diff_host_rate, service_ftp_data und Verbindungszahlen umfassten, die Beam Search verpasste.
  • Präzision: Diese einzigartigen Subgruppen erreichten eine Test-Präzision von 99,6 % bei R2L-Angriffen (was bedeutet, dass 99,6 % der übereinstimmenden Verbindungen als bestätigte Angriffe identifiziert wurden).
  • Hybrides IDS: In einem zweistufigen hybriden System (QAOA-Regeln + XGBoost) erreichte das quantenverstärkte System eine Erkennungsrate (DR) von 12,61 % für R2L-Angriffe und übertraf damit die klassische Basislinie (9,32 %).

5. Bedeutung und Einschränkungen

Bedeutung:

• Erklärbarkeit: Die Arbeit verlagert den Fokus von der "Black-Box"-Vorhersage zur "White-Box"-Regelentdeckung und bietet Analysten handlungsrelevante, hochpräzise Logik zur Erkennung spezifischer Angriffstypen.
• Suchvollständigkeit: Sie demonstriert, dass Quantenüberlagerung den gesamten kombinatorischen Raum gleichzeitig erkunden kann und "Nadel-im-Heuhaufen"-Muster findet, die von gierigen klassischen Heuristiken herausgeschnitten werden.
• Benchmarking: Sie etabliert eine rigorose, gemessene Basislinie für die quantenbasierte kombinatorische Optimierung in der Cybersicherheit und geht über theoretische Projektionen hinaus zu empirischen Hardwaredaten.

Einschränkungen:

• Hardware-Rauschen: Aktuelle Noisy Intermediate-Scale Quantum (NISQ)-Geräte begrenzen die praktische Problemgröße auf etwa 20–25 Qubits für dichte QUBOs. Darüber hinaus überlagert Rauschen das Signal.
• Laufzeit: Die End-to-End-Pipeline (einschließlich Cloud-Wartezeiten und Transpilierung) dauert Minuten bis Stunden, während klassische Beam Search Millisekunden benötigt. Der Vorteil liegt derzeit in der Abdeckung/Vollständigkeit, nicht in der Geschwindigkeit.
• Alter des Datensatzes: Die Studie stützt sich auf NSL-KDD, einen etwas veralteten Datensatz. Zukünftige Arbeiten erfordern eine Validierung an modernen, hochdimensionalen Datensätzen (z. B. CICIDS2017).

Fazit:
Obwohl die Pipeline noch keinen rechnerischen Geschwindigkeitsvorteil gegenüber klassischen Methoden bietet, beweist sie die Durchführbarkeit der Verwendung quantenbasierter Optimierung zur Entdeckung interpretierbarer, hochpräziser Sicherheitsregeln, die klassische Heuristiken übersehen. Die Arbeit liefert eine kritische Roadmap dafür, wie quantenbasierter Vorteil in der Cybersicherheit schließlich manifestiert werden könnte: nicht durch schnellere Klassifizierung, sondern durch überlegene Entdeckung komplexer, Multi-Feature-Angriffssignaturen.