Formulating Subgroup Discovery as a Quantum Optimization Problem for Network Security

Dit artikel introduceert een nieuwe quantum-geïmplementeerde pijplijn die subgroepontdekking voor netwerkintrusiedetectie formuleert als een kwadratisch ongeremd binair optimalisatieprobleem (QUBO), en aantoont dat het Quantum Approximate Optimization Algorithm (QAOA) op IBM-hardware concurrerende, interpreteerbare multi-kenmerk aanvalspatronen kan identificeren die klassieke heuristieken vaak missen, terwijl het empirisch de door ruis beperkte schaalgrens van NISQ-apparaten vaststelt.

De kern

Stel je voor dat je een beveiliger bent die probeert een dief te spotten in een enorm, druk treinstation. Het station heeft duizenden camera's, sensoren en kaartlezers, die allemaal een constante stroom aan data genereren.

Het Probleem: De "Black Box"-beveiliger
Op dit moment zijn de meeste beveiligingssystemen (zogenaamde Intrusion Detection Systems) als zeer getrainde maar stille beveiligers. Ze zijn uitstekend in het spotten van de dief en het afgeven van een alarm. Ze kunnen echter niet uitleggen waarom. Ze zeggen gewoon: "Dief!", zonder je te vertellen of het was omdat de persoon rende, een rode hoed droeg of een specifiek type tas bij zich had. In de cyberbeveiliging maakt dit gebrek aan uitleg het voor menselijke analisten moeilijk om te begrijpen hoe de aanval plaatsvond of hoe deze de volgende keer kan worden voorkomen.

De Oplossing: De "Receptuur" voor een Dief Vinden
Dit artikel introduceert een nieuwe methode genaamd Subgroepontdekking. In plaats van alleen te vragen "Is dit een dief?", vraagt het: "Welke specifieke combinatie van eigenschappen maakt dat iemand eruitziet als een dief?"

• Analogie: In plaats van alleen een persoon te markeren, probeert het systeem een regel te vinden zoals: "Als iemand een rode hoed draagt EN een rugzak bij zich heeft EN rent, dan is de kans 99% dat het een dief is."
• Het doel is om deze "recepten" (regels) te vinden die voor mensen makkelijk te begrijpen zijn.

De Uitdaging: De Naald in de Hooiberg
Het probleem is dat er te veel mogelijke combinaties zijn. Als je 41 verschillende eigenschappen hebt (zoals hoedkleur, snelheid, tastype, enz.), is het aantal mogelijke regels astronomisch.

• Analogie: Stel je voor dat je probeert het perfecte cake-recept te vinden door elke mogelijke combinatie van ingrediënten te testen. Een traditionele computer probeert dit door één recept te proeven, dan één ingrediënt toe te voegen, opnieuw te proeven, en alleen de beste te houden. Dit is snel, maar het is "gierig". Als een enkel ingrediënt op zichzelf slecht smaakt (zoals zout in een cake), gooit de computer het weg, zelfs als die zout de cake later geweldig zou maken wanneer het met chocolade wordt gemengd. Het mist de "geheime saus"-combinaties.

De Quantum-Twist: De "Magische Super-Scanner"
De auteurs probeerden een Quantumcomputer te gebruiken om dit op te lossen.

• Analogie: Terwijl de traditionele computer recepten één voor één proeft, is de quantumcomputer als een magische scanner die alle mogelijke recepten tegelijk kan proeven (met behulp van een concept genaamd superpositie). Het raakt niet vast in het weggooien van "slechte" ingrediënten alleen omdat ze op zichzelf slecht lijken; het ziet hoe ze samenwerken in het hele mengsel.

Hoe Ze Het Dedden

1. De Kaart (QUBO): Ze vertaalden het probleem van het vinden van het beste "dief-recept" naar een wiskundige kaart genaamd een QUBO. Denk hierbij aan het omzetten van de zoektocht naar het beste cake-recept in een landschap van heuvels en valleien, waarbij de diepste vallei de beste regel is.
2. Het Algorithm (QAOA): Ze gebruikten een specifiek quantumalgoritme (QAOA) om een bal over dit landschap te rollen om de diepste vallei te vinden.
3. De Hardware: Ze draaiden dit op een echte quantumcomputer (IBM's "Pittsburgh"-machine) die beschikbaar was in de cloud.

Wat Ze Vonden

• Kleine Schaal Werkt Goed: Toen ze testten met een klein aantal eigenschappen (10 tot 15 "ingrediënten"), vond de quantumcomputer regels die bijna net zo goed waren als het perfecte antwoord (98% tot 99% nauwkeurigheid).
• De Ruis-muur: Toen ze meer eigenschappen toevoegden (tot 30), begon de quantumcomputer fouten te maken.
  • Analogie: Stel je voor dat de quantumcomputer een zeer gevoelig instrument is. Naarmate het experiment groter wordt, wordt het "statische ruis" in de kamer harder, waardoor het signaal wordt overschreeuwd. Bij 30 eigenschappen was de ruis zo luid dat de computer het juiste antwoord niet meer kon vinden.
• De Geheime Saus: Het meest spannende deel is dat de quantumcomputer enkele "dief-recepten" vond die de traditionele computer volledig had gemist.
  • Voorbeeld: De traditionele computer negeerde een specifieke combinatie van "service-type" en "aantal verbindingen" omdat er afzonderlijk niets verdachts aan was. De quantumcomputer zag dat ze samen een perfecte indicator waren voor een aanval. Een van deze unieke regels was 99,6% nauwkeurig in het spotten van een specifiek type cyberaanval (genaamd R2L).

De Conclusie
Dit artikel beweert niet dat quantumcomputers momenteel sneller of beter zijn in het stoppen van hackers dan gewone computers. Sterker nog, de quantumcomputer deed er veel langer over om te draaien.

In plaats daarvan bewijst het dat quantumcomputers patronen kunnen vinden die traditionele computers missen. Het toonde aan dat door alle mogelijkheden tegelijk te bekijken, quantummethoden complexe, verborgen regels kunnen ontdekken die mensen helpen cyberaanvallen beter te begrijpen. Echter, om dit te laten werken op echte, massale data, moeten quantumcomputers veel stiller worden (minder ruis) en krachtiger.

Samenvatting in één zin:
De onderzoekers gebruikten een quantumcomputer om verborgen "recepten" voor cyberaanvallen te vinden die traditionele computers hadden gemist, wat bewijst dat quantummethoden complexe patronen kunnen blootleggen, ook al is de huidige hardware nog te luidruchtig om zeer grote problemen aan te kunnen.

Technische samenvatting

1. Probleemstelling

Netwerk-intrudedetectiesystemen (IDS) vertrouwen doorgaans op black-box machine learning-modellen die een hoge classificatie-accuraatheid bereiken, maar geen verklaarbaarheid bieden. Cybersecurity-analisten hebben interpreteerbare regels nodig om te begrijpen waarom specifiek verkeer als kwaadaardig wordt gemarkeerd.

Subgroepontdekking (Subgroup Discovery - SD) lost dit op door interpreteerbare conjunctieve regels (subgroepen) te vinden die kenmerkende feature-interacties beschrijven die geassocieerd zijn met aanvalstrafiek. Het vinden van optimale subgroepen is echter een NP-hard combinatorisch optimalisatieprobleem.

• De Uitdaging: Naarmate het aantal features ($n$) toeneemt, groeit de zoekruimte exponentieel ($C(n, k)$).
• Klassieke Beperking: Standaard klassieke heuristieken, zoals Beam Search, gebruiken een greedige pruning. Ze breiden subgroepen één feature per keer uit en behouden alleen de best scorende kandidaten. Deze aanpak mist vaak kritieke multi-feature interactiepatronen waarbij individuele features op zichzelf zwak lijken, maar sterk discriminerend zijn wanneer ze gecombineerd worden.
• Het Doel: SD te formuleren als een combinatorisch optimalisatieprobleem dat oplosbaar is met quantumalgoritmen, met name gericht op het ontdekken van interpreteerbare, hoogprecisie aanvalsregels die door klassieke heuristieken worden weggepruned.

2. Methodologie

De auteurs stellen een quantum-gestuurde pijplijn voor die het SD-doelwit codeert in een Quadratic Unconstrained Binary Optimization (QUBO) probleem en dit oplost met het Quantum Approximate Optimization Algorithm (QAOA) op IBM Quantum-hardware (ibm_pittsburgh).

A. Data Preprocessing (NSL-KDD)

• Dataset: Gebruik van de NSL-KDD-benchmark (41 features, 4 aanvalstypes: DoS, Probe, R2L, U2R).
• Binarisatie: Features worden gestandaardiseerd en via drempelwaarden omgezet naar binair $\{0, 1\}$. Categorieële features ondergaan one-hot encoding met cardinaliteitsbewuste filtering om het qubit-budget te beheren.
• Doelwit: Binaire label (Normaal vs. Aanval).

B. QUBO Formulering

De kerninnovatie is het coderen van de Weighted Relative Accuracy (WRAcc)-metriek in een QUBO-matrix.

• Doelwit: WRAcc maximaliseren, wat een balans houdt tussen dekking (aantal records) en contrast (afwijking van de basisaanvalsrate).
• Kwadratische Minderste-Kwadraten-aanpassing: Omdat WRAcc van nature niet kwadratisch is, passen de auteurs een regressiemodel voor kleinste-kwadraten toe om het WRAcc-landschap over feature-subsets te benaderen.
  • $Q^* = \arg\min_Q \sum (x^T Q x - (-WRAcc(x)))^2$
• Cardinaliteitsstraf: Een additieve strafterm is opgenomen om de oplossing te dwingen precies $K$ features te selecteren.
• Ising Mapping: De QUBO wordt omgezet in een Ising-Hamiltoniaan ($H_C$) met lokale velden ($h_i$) en koppeltermen ($J_{ij}$), wat de generatie van niet-triviale twee-qubit verstrengelende poorten (ZZ-termen) op hardware mogelijk maakt.

C. Quantum Executie (QAOA)

• Algoritme: QAOA met diepte $p$ (lagen).
• Hardware: Uitgevoerd op ibm_pittsburgh (supergeleidende qubits) voor qubit-aantallen variërend van 10 tot 30.
• Optimalisatie: Gebruik van de COBYLA klassieke optimizer met warm-start (het gebruik van parameters van diepte $p$ om $p+1$ te initialiseren) en multi-start strategieën.
• Foutmitigatie: Toepassing van Dynamical Decoupling (XY4-sequentie) en Pauli Gate Twirling om ruis te mitigeren.

D. Evaluatiekader

Het artikel introduceert een Dual Approximation Ratio-kader:

1. $r_5$ (Hamiltoniaan Kwaliteit): Ratio van de best gesampleerde Ising-energie tot de ware grondtoestandsenergie.
2. $r_6$ (Toepassing Kwaliteit): Ratio van de beste WRAcc gevonden door QAOA (bij de doelcardinaliteit) tot de exhaustieve grond-waarheid WRAcc.

• Baselines: Vergelijking met Exhaustive Enumeration (grond-waarheid voor kleine $n$) en Beam Search (standaard heuristiek).

3. Belangrijkste Bijdragen

1. Eerste QUBO Formulering voor SD: Dit is het eerste werk dat Subgroepontdekking als een QUBO-probleem presenteert, waardoor quantumalgoritmen direct kunnen optimaliseren voor de kwaliteit van interpreteerbare regels (WRAcc) in plaats van slechts classificatie-accuraatheid.
2. Nieuwe QUBO-naar-WRAcc Mapping: Ontwikkeling van een regressie-aanpak voor kleinste-kwadraten om het WRAcc-landschap te benaderen, zodat de resulterende Hamiltoniaan voldoende off-diagonale koppeling heeft om verstrengeling op hardware te genereren.
3. Empirische NISQ-schaalgrens: Geleverde gemeten data over hoe QAOA-prestaties verslechteren met het qubit-aantal op echte hardware, waarmee een praktische trouw-grens wordt vastgesteld voor dichte QUBO-instanties.
4. Ontdekking van "Quantum-unieke" Subgroepen: Aangetoond dat QAOA multi-feature interactiepatronen kan vinden die door greedige Beam Search systematisch worden weggepruned vanwege hun zwakke tussenliggende scores.

4. Belangrijkste Resultaten

• QUBO Fit Kwaliteit: De benadering voor kleinste-kwadraten bereikte een $R^2 = 0,989$ en Spearman-correlatie $\rho = 0,899$ tegenover het ware WRAcc-landschap, wat de geldigheid van de kwadratische codering bevestigt.
• Hardware Schaalprestaties (bij diepte $p=1$):
  • 10 Qubits: $r_6 = 0,983$ (Zeer concurrerend met grond-waarheid).
  • 15 Qubits: $r_6 = 0,971$.
  • 20 Qubits: $r_6 = 0,855$.
  • 25 Qubits: $r_6 = 0,624$.
  • 30 Qubits: $r_6 = 0,039$ (Prestaties storten in door ruisdominantie).
  • Observatie: De ruisvrije simulator behield $r_6 = 1,0$ over alle schalen, wat bevestigt dat de degradatie het gevolg is van hardware-ruis en niet van een falen van het algoritme.
• QAOA-unieke Subgroepen:
  • QAOA ontdekte 6-feature subgroepen met combinaties van dst_host_srv_diff_host_rate, service_ftp_data en verbindingsaantallen die Beam Search miste.
  • Precisie: Deze unieke subgroepen behaalden 99,6% testprecisie op R2L-aanvallen (wat betekent dat 99,6% van de gematchte verbindingen bevestigde aanvallen waren).
  • Hybride IDS: In een tweelaags hybride systeem (QAOA-regels + XGBoost) bereikte het quantum-gestuurde systeem een Detectierate (DR) van 12,61% voor R2L-aanvallen, beter dan de klassieke baseline (9,32%).

5. Betekenis en Beperkingen

Betekenis:

• Verklaarbaarheid: Het werk verschuift de focus van "black-box" voorspelling naar "white-box" regelontdekking, waardoor analisten actievere, hoogprecieze logica krijgen voor het detecteren van specifieke aanvalstypes.
• Zoekvolledigheid: Het toont aan dat quantum-superpositie de volledige combinatorische ruimte gelijktijdig kan verkennen, waardoor "naald-in-hooiberg"-patronen worden gevonden die door greedige klassieke heuristieken worden weggepruned.
• Benchmarking: Het vestigt een rigoureuze, gemeten baseline voor quantum combinatorische optimalisatie in cybersecurity, verdergaand dan theoretische projecties naar empirische hardware-data.

Beperkingen:

• Hardware Ruis: Huidige Noisy Intermediate-Scale Quantum (NISQ)-apparaten beperken de praktische probleemgrootte tot ongeveer 20–25 qubits voor dichte QUBO's. Daarboven overheerst ruis het signaal.
• Uitvoeringstijd: De end-to-end pijplijn (inclusief wachttijden in de cloud en transpilatie) duurt minuten tot uren, terwijl klassieke Beam Search milliseconden kost. Het voordeel zit momenteel in dekking/volledigheid, niet in snelheid.
• Dataset Ouderdom: De studie vertrouwt op NSL-KDD, een wat verouderde dataset. Toekomstig werk vereist validatie op moderne, hoogdimensionale datasets (bijv. CICIDS2017).

Conclusie:
Hoewel de pijplijn nog geen rekenkundige versnelling biedt ten opzichte van klassieke methoden, bewijst het de haalbaarheid van het gebruik van quantumoptimalisatie om interpreteerbare, hoogprecieze beveiligingsregels te ontdekken die klassieke heuristieken missen. Het werk biedt een cruciale routekaart voor hoe quantumvoordeel in cybersecurity zich uiteindelijk kan manifesteren: niet door snellere classificatie, maar door superieure ontdekking van complexe, multi-feature aanvalssignaturen.