A Privacy-Preserving Approach to Conformance Checking

1. Enunciato del Problema

Il conformance checking è un'operazione fondamentale nel process mining che confronta un modello di processo (comportamento atteso) con un registro di eventi (comportamento osservato) per identificare le discrepanze. Tradizionalmente, sia il modello che il registro sono accessibili all'analista. Tuttavia, in contesti sensibili (ad esempio, produzione su misura o linee di produzione proprietarie), il proprietario del modello di processo deve proteggere la propria proprietà intellettuale, mentre il cliente (proprietario del registro) deve proteggere i propri dati operativi.

Il problema centrale affrontato è: Come eseguire il conformance checking tra un modello di processo e un registro di eventi senza rivelare il modello al proprietario del registro, o il registro al proprietario del modello?

2. Metodologia

Gli autori propongono una tecnica di Secure Conformance Checking basata su un'architettura Client-Server, che utilizza la Crittografia Omomorfa Completa (FHE) e algoritmi di elaborazione delle stringhe.

A. Concetti Chiave

• Reti di Petri e Svolgimento (Unfolding): Il modello di processo è rappresentato come una rete di Petri. Per convertirlo in un formato adatto alla ricerca di stringhe, gli autori utilizzano lo svolgimento del prefisso causalmente completo. Questo trasforma il comportamento potenzialmente infinito di una rete di Petri (dovuto ai cicli) in una struttura finita e aciclica contenente tutte le possibili "esecuzioni" (run completi).
• Rappresentazione in Stringa: Le esecuzioni derivanti dallo svolgimento vengono linearizzate e concatenate in un'unica stringa di testo, separate da delimiteri speciali.
• FM-Index e Ricerca all'Indietro: La stringa concatenata viene indicizzata utilizzando l'FM-Index (basato sulla Trasformata di Burrows-Wheeler e sulla Matrice delle Onde). Ciò consente una ricerca efficiente di sottostringhe (individuare se una traccia esiste all'interno delle esecuzioni del modello) in tempo $O(m)$.
• Crittografia Omomorfa (FHE): Il sistema utilizza uno schema di crittografia a chiave pubblica (nello specifico, ElGamal sollevato) che permette di eseguire calcoli (addizione e moltiplicazione) direttamente sui dati cifrati.

B. Il Protocollo Sicuro

L'approccio mappa il problema della ricerca di allineamenti ottimali (minimizzando le deviazioni) sulla corrispondenza approssimata di sottostringhe.

1. Lato Server (Proprietario del Modello):

   • Prende il modello di processo, lo svolge, concatena le esecuzioni e costruisce l'FM-Index (BWT e Matrice delle Onde).
   • Memorizza le strutture dati dell'indice (in particolare i vettori 0-RANK e 1-SRANK) in memoria.
   • Non vede la traccia del cliente.

2. Lato Client (Proprietario del Registro):

   • Detiene la traccia di eventi da verificare.
   • Cifra i dati della traccia e lo stato di ricerca (indici) prima di inviare le query al server.

3. L'Interazione (Ricerca Sicura all'Indietro):

   • Il cliente itera attraverso i caratteri della traccia in ordine inverso.
   • Per ogni carattere, il cliente esegue una Ricerca all'Indietro sull'FM-Index. Ciò comporta l'attraversamento della Matrice delle Onde riga per riga (a livello di bit) per aggiornare l'intervallo di ricerca $[f, g]$.
   • Meccanismo di Privacy:
     • Il cliente invia vettori cifrati che rappresentano gli indici di ricerca correnti.
     • Il server esegue prodotti scalari omomorfici e addizioni per aggiornare questi indici in base alle righe della Matrice delle Onde.
     • Per impedire al cliente di apprendere gli intervalli intermedi (che potrebbero rivelare informazioni sul modello), il server aggiunge un offset casuale ai risultati prima di restituirli.
   • Gestione delle Incongruenze (Movimenti del Registro):
     • Se un carattere nella traccia non corrisponde al modello (un "log move"), il cliente ripristina gli indici di ricerca precedenti (memorizzati prima dell'iterazione) e inserisce un'operazione di "salto" nell'allineamento.
     • Ciò avviene senza che il server sappia quale carattere abbia causato l'incongruenza, poiché il cliente controlla il flusso logico basandosi sui risultati decifrati (ma offuscati).

3. Contributi Chiave

1. Prima Applicazione della FHE al Conformance Checking: Il paper afferma di essere il primo lavoro ad applicare la crittografia omomorfa specificamente al problema del conformance checking.
2. Allineamento Sicuro tramite Corrispondenza di Stringhe: Mappa in modo innovativo il complesso problema dell'allineamento delle tracce sulla corrispondenza di sottostringhe utilizzando l'FM-Index, consentendo l'uso di algoritmi di stringa efficienti in un dominio cifrato.
3. Modello di Privacy Client-Server: Stabilisce un protocollo in cui il proprietario del modello non vede mai la traccia e il proprietario del registro non vede mai il modello, eppure è possibile calcolare un punteggio di allineamento (e lo stesso allineamento).
4. Gestione dei Movimenti del Registro: L'algoritmo supporta specificamente i "log move" (deviazioni in cui il registro ha un evento non presente nel modello) permettendo al cliente di ripristinare gli stati di ricerca in modo sicuro.

4. Risultati e Valutazione

Il metodo è stato implementato in C++ utilizzando la libreria mcl per la crittografia omomorfa e valutato su una workstation laptop standard.

• Dataset: Valutato utilizzando un registro di eventi reale e due registri sintetici (di piccole e medie dimensioni, con concorrenza, scelte e cicli).
• Prestazioni:
  • Accuratezza: Il metodo ha calcolato con successo allineamenti per tracce che corrispondevano al modello e per quelle con deviazioni inserite.
  • Sovraccarico: Il collo di bottiglia principale è il costo computazionale delle operazioni omomorfiche.
  • Complessità: La complessità teorica è $O(C \cdot |q| \cdot |T|)$, dove $C$ è la costante grande per cifratura/decifratura, $|q|$ è la lunghezza della traccia e $|T|$ è la dimensione delle esecuzioni del modello indicizzate.
  • Tempo di Esecuzione: Per un modello piccolo con 144 esecuzioni e 9 eventi per traccia, il tempo medio di allineamento è stato di 1,12 minuti. Il tempo per simbolo è stato di circa 0,11 minuti.
  • Scalabilità: Il tempo di esecuzione ha mostrato una tendenza quasi lineare rispetto alla lunghezza della traccia, ma i tempi assoluti sono attualmente troppo elevati per applicazioni industriali in tempo reale su larga scala a causa del pesante sovraccarico crittografico.

5. Significato e Lavori Futuri

• Significato: Questo lavoro colma il divario tra Process Mining e Data Mining che preserva la privacy. Dimostra che i processi aziendali sensibili possono essere auditati senza esporre logica proprietaria o dati operativi, un requisito critico per settori come la produzione su misura e la sanità.
• Limitazioni:
  • Attualmente supporta solo i movimenti del registro (salto di eventi nel registro). Non supporta ancora i movimenti del modello (salto di eventi nel modello), che richiederebbero una logica più complessa.
  • I requisiti elevati di memoria e elaborazione lo rendono attualmente poco pratico per modelli molto grandi o sistemi in tempo reale.
• Direzioni Future:
  • Estendere l'approccio per gestire i movimenti del modello.
  • Migliorare la gestione dei cicli (attualmente limitata dalla profondità dello svolgimento).
  • Ottimizzare l'implementazione crittografica per ridurre il divario computazionale tra l'esecuzione in chiaro e quella cifrata.

In conclusione, il paper presenta un prototipo teoricamente solido e tecnicamente fattibile per il conformance checking sicuro, dimostrando che la privacy può essere preservata a scapito di risorse computazionali significative.