A Privacy-Preserving Approach to Conformance Checking

1. Declaração do Problema

A verificação de conformidade é uma operação central de mineração de processos que compara um modelo de processo (comportamento esperado) contra um registro de eventos (comportamento observado) para identificar discrepâncias. Tradicionalmente, tanto o modelo quanto o registro são acessíveis ao analista. No entanto, em contextos sensíveis (por exemplo, manufatura sob medida ou linhas de produção proprietárias), o proprietário do modelo de processo deve proteger sua propriedade intelectual, enquanto o cliente (proprietário do registro) deve proteger seus dados operacionais.

O problema central abordado é: Como realizar a verificação de conformidade entre um modelo de processo e um registro de eventos sem revelar o modelo ao proprietário do registro, ou o registro ao proprietário do modelo?

2. Metodologia

Os autores propõem uma técnica de Verificação de Conformidade Segura baseada em uma arquitetura Cliente-Servidor, utilizando Criptografia Homomórfica Total (FHE) e algoritmos de processamento de strings.

A. Conceitos Centrais

• Redes de Petri & Desdobramento: O modelo de processo é representado como uma Rede de Petri. Para convertê-lo em um formato adequado para busca em strings, os autores utilizam o desdobramento de prefixo causalmente completo. Isso transforma o comportamento potencialmente infinito de uma Rede de Petri (devido a loops) em uma estrutura finita e acíclica contendo todas as possíveis "execuções" (execuções completas).
• Representação em String: As execuções do desdobramento são linearizadas e concatenadas em uma única string de texto, separadas por delimitadores especiais.
• FM-Index & Busca Reversa: A string concatenada é indexada usando o FM-Index (baseado na Transformação Burrows-Wheeler e na Matriz Wavelet). Isso permite a busca eficiente de substrings (encontrar se uma trilha existe dentro das execuções do modelo) em tempo $O(m)$.
• Criptografia Homomórfica (FHE): O sistema utiliza um esquema de criptografia de chave pública (especificamente ElGamal elevado) que permite que computações (adição e multiplicação) sejam realizadas diretamente sobre dados criptografados.

B. O Protocolo Seguro

A abordagem mapeia o problema de encontrar alinhamentos ótimos (minimizando desvios) para correspondência aproximada de substrings.

1. Lado do Servidor (Proprietário do Modelo):

   • Recebe o modelo de processo, desdobra-o, concatena as execuções e constrói o FM-Index (BWT e Matriz Wavelet).
   • Armazena as estruturas de dados do índice (especificamente os vetores 0-RANK e 1-SRANK) na memória.
   • Não vê a trilha do cliente.

2. Lado do Cliente (Proprietário do Registro):

   • Possui a trilha de eventos a ser verificada.
   • Criptografa os dados da trilha e o estado da busca (índices) antes de enviar consultas ao servidor.

3. A Interação (Busca Reversa Segura):

   • O cliente itera através dos caracteres da trilha em ordem reversa.
   • Para cada caractere, o cliente realiza uma Busca Reversa no FM-Index. Isso envolve percorrer a Matriz Wavelet linha por linha (bit a bit) para atualizar o intervalo de busca $[f, g]$.
   • Mecanismo de Privacidade:
     • O cliente envia vetores criptografados representando os índices de busca atuais.
     • O servidor realiza produtos escalares homomórficos e adições para atualizar esses índices com base nas linhas da Matriz Wavelet.
     • Para impedir que o cliente aprenda os intervalos intermediários (o que poderia vazar informações sobre o modelo), o servidor adiciona um deslocamento aleatório aos resultados antes de devolvê-los.
   • Tratamento de Incompatibilidades (Movimentos de Registro):
     • Se um caractere na trilha não corresponder ao modelo (um "movimento de registro"), o cliente restaura os índices de busca anteriores (armazenados antes da iteração) e insere uma operação de "pular" no alinhamento.
     • Isso é feito sem que o servidor saiba qual caractere causou a incompatibilidade, pois o cliente controla o fluxo lógico com base nos resultados descriptografados (mas ofuscados).

3. Contribuições Principais

1. Primeira Aplicação de FHE à Verificação de Conformidade: O artigo afirma ser o primeiro trabalho a aplicar criptografia homomórfica especificamente ao problema de verificação de conformidade.
2. Alinhamento Seguro via Correspondência de Strings: Mapeia inovadoramente o problema complexo de alinhamento de trilhas para correspondência de substrings usando o FM-Index, permitindo o uso de algoritmos de strings eficientes em um domínio criptografado.
3. Modelo de Privacidade Cliente-Servidor: Estabelece um protocolo onde o proprietário do modelo nunca vê a trilha, e o proprietário do registro nunca vê o modelo, ainda que uma pontuação de alinhamento (e o próprio alinhamento) possa ser computada.
4. Tratamento de Movimentos de Registro: O algoritmo suporta especificamente "movimentos de registro" (desvios onde o registro possui um evento não presente no modelo), permitindo que o cliente reverta estados de busca de forma segura.

4. Resultados e Avaliação

O método foi implementado em C++ usando a biblioteca mcl para criptografia homomórfica e avaliado em uma estação de trabalho de laptop padrão.

• Conjuntos de Dados: Avaliado usando um registro de eventos do mundo real e dois registros sintéticos (tamanho pequeno a médio com concorrência, escolha e loops).
• Desempenho:
  • Precisão: O método computou com sucesso alinhamentos para trilhas que se ajustam ao modelo e aquelas com desvios injetados.
  • Sobrecarga: O principal gargalo é o custo computacional das operações homomórficas.
  • Complexidade: A complexidade teórica é $O(C \cdot |q| \cdot |T|)$, onde $C$ é a constante grande para criptografia/descriptografia, $|q|$ é o comprimento da trilha e $|T|$ é o tamanho das execuções do modelo indexado.
  • Tempo de Execução: Para um modelo pequeno com 144 execuções e 9 eventos por trilha, o tempo médio de alinhamento foi de 1,12 minutos. O tempo por símbolo foi de aproximadamente 0,11 minutos.
  • Escalabilidade: O tempo de execução mostrou uma tendência quase linear em relação ao comprimento da trilha, mas os tempos absolutos são atualmente altos demais para aplicações industriais em tempo real e em grande escala devido à pesada sobrecarga criptográfica.

5. Significado e Trabalho Futuro

• Significado: Este trabalho preenche a lacuna entre Mineração de Processos e Mineração de Dados com Preservação de Privacidade. Demonstra que processos comerciais sensíveis podem ser auditados sem expor lógica proprietária ou dados operacionais, um requisito crítico para indústrias como manufatura sob medida e saúde.
• Limitações:
  • Atualmente suporta apenas movimentos de registro (pulando eventos no registro). Ainda não suporta movimentos de modelo (pulando eventos no modelo), o que exigiria lógica mais complexa.
  • Os altos requisitos de memória e processamento tornam-no atualmente impraticável para modelos muito grandes ou sistemas em tempo real.
• Direções Futuras:
  • Estender a abordagem para lidar com movimentos de modelo.
  • Melhorar o tratamento de loops (atualmente limitado pela profundidade do desdobramento).
  • Otimizar a implementação criptográfica para reduzir a lacuna computacional entre a execução em texto plano e a criptografada.

Em conclusão, o artigo apresenta um protótipo teoricamente sólido e tecnicamente viável para verificação de conformidade segura, provando que a privacidade pode ser preservada ao custo de recursos computacionais significativos.