💻 computer science

A Privacy-Preserving Approach to Conformance Checking

Dit artikel stelt een privacybehoudende conformance-checkingbenadering voor die homomorfische encryptie en stringverwerkingsalgoritmen gebruikt om discrepanties tussen een procesmodel en een gebeurtenislog veilig te identificeren zonder dat deze aan de andere partij worden onthuld, zij het ten koste van hoge reken- en geheugeneisen.

Oorspronkelijke auteurs: Luis Rodríguez-Flores, Luciano García-Bañuelos, Abel Armas-Cervantes, Astrid Rivera-Partida

Gepubliceerd 2026-05-04

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Luis Rodríguez-Flores, Luciano García-Bañuelos, Abel Armas-Cervantes, Astrid Rivera-Partida

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: Een Recept Controleren Zonder De Ingrediënten Te Zien

Stel je voor dat je een klant bent die een op maat gemaakt taart hebt besteld. Je wilt er zeker van zijn dat de bakker je specifieke recept (het Procesmodel) volgt en dat de stappen die ze daadwerkelijk in de keuken nemen overeenkomen met wat je hebt gevraagd (het Gebeurtenislogboek).

Normaal gesproken zou de bakker je zijn geheime receptenboek moeten laten zien om dit te controleren, en zou jij hen je geheime bestelformulier moeten tonen. Maar wat als de bakker bang is dat je zijn geheime recept steelt, of als jij bang bent dat ze je geheime bestelgegevens zien?

Dit artikel stelt een manier voor om te controleren of de taart correct wordt gemaakt zonder dat een van de partijen ooit de geheime informatie van de ander ziet.

Het Probleem: Privacy versus Controleren

In de wereld van zakelijke software is "Conformance Checking" (overeenstemmingscontrole) het proces van het vergelijken van een geplande workflow (zoals een recept) met een verslag van wat er daadwerkelijk is gebeurd (zoals een keukenlogboek).

Het Model: Het "Verwachte" pad (het recept).
Het Logboek: Het "Feitelijke" pad (wat de chefkok daadwerkelijk heeft gedaan).

Traditioneel bekijkt een derde partij (of de eigenaar van de gegevens) beide om fouten te vinden. Maar in gevoelige sectoren (zoals high-tech productie) willen bedrijven hun geheime blauwdrukken niet delen, en willen klanten hun privé-bestelgegevens niet delen.

De Oplossing: Een "Magische Doos" en een "Zoekmachine"

De auteurs hebben een systeem ontwikkeld dat twee belangrijkste hulpmiddelen gebruikt om dit privacypuzzel op te lossen:

1. De Magische Doos (Homomorf Versleuteling)

Denk aan Homomorf Versleuteling als een speciale "Magische Doos".

Je kunt een geheim getal in de doos doen.
Je kunt iemand vragen om 5 bij dat getal op te tellen zonder dat ze de doos openen of het getal zien.
Ze voeren de wiskunde uit op het "versleutelde" getal in de doos en geven het terug.
Als je de doos opent, is het resultaat het juiste antwoord (Origineel Getal + 5).

In dit artikel plaatst de "Klant" (de persoon met de trace) hun gegevens in deze Magische Doos. De "Server" (de eigenaar van het model) voert de controle-wiskunde uit binnen de doos zonder ooit de werkelijke gegevens te zien.

2. De Zoekmachine (FM-Index & Tekstverwerking)

Om te controleren of de stappen overeenkomen, verandert het systeem het hele procesmodel in één enorme tekststring (zoals het omzetten van een recept in een lange zin). Vervolgens bouwt het een supersnelle Zoekmachine (een FM-Index genaamd) bovenop die tekst.

Normaal gesproken kun je in een zoekmachine een woord typen en direct vinden waar het in de tekst voorkomt. Hier gebruikt het systeem deze zoekmachine om te zien of de "stappen" in het logboek van de klant bestaan binnen de "stappen" van de tekst van het model.

Hoe Het Werkt: Het "Terugwaarts Zoeken" Spel

Het artikel beschrijft een specifiek spel dat wordt gespeeld tussen de Klant en de Server om de overeenkomst te controleren:

Voorbereiding: De Server neemt hun geheime model, verandert het in een lange tekststring en bouwt de Zoekmachine (FM-Index) daarop. Ze houden dit geheim.
De Query: De Klant heeft een geheime lijst met stappen (een trace). Ze willen weten of deze stappen in het model passen.
De Geheime Zoektocht:
- De Klant kijkt naar hun lijst met stappen achterwaarts (van de laatste stap naar de eerste).
- In plaats van de stap direct te sturen, stuurt de Klant een "vergrendeld" verzoek naar de Server.
- De Server gebruikt de Zoekmachine om die stap in het model te zoeken.
- Cruciaal: De Server doet deze wiskunde binnen de "Magische Doos". De Server ziet alleen versleutelde getallen, niet de daadwerkelijke stapnamen.
- De Server stuurt het resultaat terug naar de Klant.
- De Klant ontgrendelt het resultaat om te zien of de stap is gevonden.
Omgaan met Fouten (Log Moves): Als een stap in de lijst van de Klant niet overeenkomt met het model, staat het systeem een "overslaan" toe (een Log Move genoemd). Het is alsof je zegt: "Oké, deze stap stond niet in het recept, maar laten we zien of de volgende stap past." Het systeem onthoudt waar het was voor de fout, zodat het opnieuw kan proberen zonder de fout aan de Server te onthullen.

De Haken: Het Is Traag en Zwaar

Het artikel geeft toe dat hoewel dit een briljante privacyoplossing is, het een hoge prijs heeft: Snelheid en Geheugen.

De Analogie: Stel je voor dat je een simpele rekensom op een stuk papier maakt. Dat duurt één seconde. Stel je nu voor dat je dat papier in een loodgelijnde kluis moet doen, het naar een vriend moet sturen, ze de rekensom door een dik glasvenster moeten doen en het terugsturen. Het duurt veel langer.
Het Resultaat: De auteurs hebben dit getest op echte en neppe gegevens. Ze ontdekten dat het controleren van een proces ongeveer 1,12 minuut per trace duurde. Hoewel het accuraat is, is het veel trager dan controleren zonder versleuteling. De "Magische Doos" (versleuteling) vereist veel rekenkracht en geheugen.

Samenvatting van Beweringen

Wat ze deden: Ze bouwden een systeem om te controleren of een proceslogboek overeenkomt met een procesmodel zonder dat een van beide kanten de gegevens van de ander ziet.
Hoe ze het deden: Door een snelle tekstzoekalgoritme (FM-Index) te combineren met een "Magische Doos" versleutelingsmethode (Homomorf Versleuteling).
Wat ze vonden: Het werkt! Je kunt veilig controleren op mismatches.
De Beperking: Het is momenteel zeer traag en gebruikt veel geheugen omdat de versleutelingswiskunde zwaar is. Het behandelt ook alleen "Log Moves" (stappen overslaan in het logboek) en nog niet "Model Moves" (stappen overslaan in het model).

Kortom, het artikel bewijst dat je een geheim recept kunt controleren tegen een geheim bestelling zonder een van beide te onthullen, maar dat het momenteel lang duurt om de wiskunde te doen.

1. Probleemstelling

Conformance checking is een kernoperatie binnen procesmining die een procesmodel (verwacht gedrag) vergelijkt met een gebeurtenislogboek (waargenomen gedrag) om afwijkingen te identificeren. Traditioneel zijn zowel het model als het logboek toegankelijk voor de analist. In gevoelige contexten (bijvoorbeeld op maat gemaakte productie of propriëtaire productielijnen) moet de eigenaar van het procesmodel echter zijn intellectuele eigendom beschermen, terwijl de klant (eigenaar van het logboek) zijn operationele data moet beschermen.

Het kernprobleem dat wordt aangepakt is: Hoe conformance checking uit te voeren tussen een procesmodel en een gebeurtenislogboek zonder het model aan de eigenaar van het logboek te onthullen, of het logboek aan de eigenaar van het model?

2. Methodologie

De auteurs stellen een techniek voor Secure Conformance Checking voor, gebaseerd op een Client-Server-architectuur, waarbij gebruik wordt gemaakt van Fully Homomorphic Encryption (FHE) en algoritmen voor stringverwerking.

A. Kernconcepten

Petri-netten & Ontvouwing: Het procesmodel wordt weergegeven als een Petri-net. Om dit om te zetten in een formaat geschikt voor stringzoekopdrachten, gebruiken de auteurs een causale complete prefix-ontvouwing. Dit transformeert het potentieel oneindige gedrag van een Petri-net (door loops) in een eindige, acyclische structuur die alle mogelijke "runs" (volledige uitvoeringen) bevat.
Stringrepresentatie: De runs uit de ontvouwing worden linearisatie en samengevoegd tot één tekststring, gescheiden door speciale scheidingstekens.
FM-Index & Achterwaartse Zoekopdracht: De samengevoegde string wordt geïndexeerd met de FM-Index (gebaseerd op de Burrows-Wheeler-transformatie en Wavelet Matrix). Dit maakt efficiënt zoeken naar substrings mogelijk (bepalen of een trace voorkomt binnen de runs van het model) in $O(m)$ tijd.
Homomorf Versleuteling (FHE): Het systeem maakt gebruik van een publieke-sleutelversleutelingsschema (specifiek een verheven ElGamal) dat berekeningen (optelling en vermenigvuldiging) direct op versleutelde data toestaat.

B. Het Secure Protocol

De aanpak koppelt het probleem van het vinden van optimale aligneringen (het minimaliseren van afwijkingen) aan benaderende substringmatching.

Serverkant (Eigenaar van het model):
- Neemt het procesmodel, vouwt het uit, voegt runs samen en bouwt de FM-Index (BWT en Wavelet Matrix).
- Bewaart de indexdatastructuren (specifiek de 0-RANK en 1-SRANK vectoren) in het geheugen.
- Ziet niet de trace van de klant.
Clientkant (Eigenaar van het logboek):
- Bezit de gebeurtenistrace die moet worden gecontroleerd.
- Versleutelt de trace-data en de zoekstatus (indices) voordat het vragen naar de server stuurt.
De Interactie (Secure Achterwaartse Zoekopdracht):
- De client doorloopt de tracekarakters in omgekeerde volgorde.
- Voor elk karakter voert de client een Achterwaartse Zoekopdracht uit op de FM-Index. Dit omvat het doorlopen van de Wavelet Matrix rij voor rij (bit voor bit) om het zoekinterval $[f, g]$ bij te werken.
- Privacymechanisme:
  - De client stuurt versleutelde vectoren die de huidige zoekindices vertegenwoordigen.
  - De server voert homomorphe dot-producten en optellingen uit om deze indices bij te werken op basis van de rijen van de Wavelet Matrix.
  - Om te voorkomen dat de client tussentijdse intervallen leert kennen (wat informatie over het model zou kunnen onthullen), voegt de server een willekeurige offset toe aan de resultaten voordat deze worden teruggegeven.
- Omgaan met Mismatches (Log Moves):
  - Als een karakter in de trace niet overeenkomt met het model (een "log move"), herstelt de client de vorige zoekindices (opgeslagen voor de iteratie) en voegt een "skip"-operatie toe in de alignering.
  - Dit gebeurt zonder dat de server weet welk karakter de mismatch veroorzaakte, aangezien de client de logica stuurt op basis van versleutelde (maar geobfuscueerde) resultaten.

3. Belangrijkste Bijdragen

Eerste Toepassing van FHE op Conformance Checking: Het artikel claimt het eerste werk te zijn dat homomorf versleuteling specifiek toepast op het probleem van conformance checking.
Secure Alignering via Stringmatching: Het koppelt op innovatieve wijze het complexe probleem van trace-alignering aan substringmatching met behulp van de FM-Index, waardoor efficiënte stringalgoritmen in een versleuteld domein kunnen worden gebruikt.
Client-Server Privacymodel: Het vestigt een protocol waarbij de eigenaar van het model de trace nooit ziet, en de eigenaar van het logboek het model nooit ziet, terwijl toch een aligneringsscore (en de alignering zelf) kan worden berekend.
Omgaan met Log Moves: Het algoritme ondersteunt specifiek "log moves" (afwijkingen waarbij het logboek een gebeurtenis heeft die niet in het model staat) door de client in staat te stellen zoekstatussen veilig terug te draaien.

4. Resultaten en Evaluatie

De methode is geïmplementeerd in C++ met de mcl-bibliotheek voor homomorf versleuteling en geëvalueerd op een standaard laptopworkstation.

Datasets: Geëvalueerd met één real-world gebeurtenislogboek en twee synthetische logboeken (klein tot medium formaat met concurrentie, keuzes en loops).
Prestaties:
- Nauwkeurigheid: De methode slaagde erin aligneringen te berekenen voor traces die bij het model pasten en voor die met ingevoegde afwijkingen.
- Overhead: De primaire knelpunt is de rekenkosten van homomorphe operaties.
- Complexiteit: De theoretische complexiteit is $O(C \cdot |q| \cdot |T|)$ , waarbij $C$ de grote constante is voor versleuteling/ontsleuteling, $|q|$ de trace-lengte is, en $|T|$ de grootte van de geïndexeerde modelruns is.
- Uitvoeringstijd: Voor een klein model met 144 runs en 9 gebeurtenissen per trace was de gemiddelde aligneringstijd 1,12 minuten. De tijd per symbool was ongeveer 0,11 minuten.
- Schaalbaarheid: De uitvoeringstijd vertoonde een quasi-lineaire trend ten opzichte van de trace-lengte, maar de absolute tijden zijn momenteel te hoog voor real-time, grootschalige industriële toepassingen vanwege de zware cryptografische overhead.

5. Betekenis en Toekomstig Werk

Betekenis: Dit werk overbrugt de kloof tussen Procesmining en Privacy-bewust Data Mining. Het demonstreert dat gevoelige bedrijfsprocessen kunnen worden geauditeerd zonder propriëtaire logica of operationele data bloot te leggen, een kritieke vereiste voor sectoren zoals op maat gemaakte productie en gezondheidszorg.
Beperkingen:
- Ondersteunt momenteel alleen log moves (het overslaan van gebeurtenissen in het logboek). Het ondersteunt nog geen model moves (het overslaan van gebeurtenissen in het model), wat complexere logica zou vereisen.
- Hoge geheugen- en verwerkingseisen maken het momenteel onpraktisch voor zeer grote modellen of real-time systemen.
Toekomstige Richtingen:
- Uitbreiden van de aanpak om model moves te behandelen.
- Verbeteren van de behandeling van loops (momenteel beperkt door de ontvouwingdiepte).
- Optimaliseren van de cryptografische implementatie om de rekenkundige kloof tussen platte tekst en versleutelde uitvoering te verkleinen.

Concluderend presenteert het artikel een theoretisch onderbouwde en technisch haalbare prototype voor secure conformance checking, waarmee wordt bewezen dat privacy kan worden behouden ten koste van aanzienlijke rekenresources.