A Privacy-Preserving Approach to Conformance Checking

"A Privacy-Preserving Approach to Conformance Checking" 논문에 대한 상세한 기술적 요약은 다음과 같습니다.

1. 문제 정의

준수성 검증 (Conformance checking) 은 프로세스 모델 (기대 행동) 과 이벤트 로그 (관측된 행동) 를 비교하여 불일치를 식별하는 프로세스 마이닝의 핵심 작업입니다. 전통적으로 모델과 로그 모두 분석가가 접근할 수 있었습니다. 그러나 민감한 맥락 (예: 맞춤형 제조 또는 독점 생산 라인) 에서는 프로세스 모델 소유자가 지적 재산을 보호해야 하는 반면, 클라이언트 (로그 소유자) 는 운영 데이터를 보호해야 합니다.

해결하려는 핵심 문제는 다음과 같습니다: 모델 소유자에게 로그를, 로그 소유자에게 모델을 노출하지 않고 프로세스 모델과 이벤트 로그 간에 준수성 검증을 수행하는 방법은 무엇인가?

2. 방법론

저자들은 완전 동형 암호화 (Fully Homomorphic Encryption, FHE) 와 문자열 처리 알고리즘을 활용하는 클라이언트 - 서버 아키텍처 기반의 보안 준수성 검증 (Secure Conformance Checking) 기법을 제안합니다.

A. 핵심 개념

• 페트리 넷 (Petri Nets) 및 언폴딩: 프로세스 모델은 페트리 넷으로 표현됩니다. 문자열 검색에 적합한 형식으로 변환하기 위해 저자들은 인과적으로 완전한 접두사 언폴딩 (causally complete prefix unfolding) 을 사용합니다. 이는 루프로 인해 발생할 수 있는 페트리 넷의 무한한 행동을 모든 가능한 "런 (완전한 실행)"을 포함하는 유한한 비순환 구조로 변환합니다.
• 문자열 표현: 언폴딩에서 얻은 런들은 선형화되어 특수 구분자로 분리된 단일 텍스트 문자열로 연결됩니다.
• FM-Index 및 역방향 검색: 연결된 문자열은 FM-Index(Burrows-Wheeler Transform 및 Wavelet Matrix 기반) 를 사용하여 인덱싱됩니다. 이를 통해 $O(m)$ 시간에 부분 문자열 검색 (모델의 런 내에 트레이스가 존재하는지 확인) 을 효율적으로 수행할 수 있습니다.
• 동형 암호화 (FHE): 시스템은 암호화된 데이터에 직접 연산 (덧셈 및 곱셈) 을 수행할 수 있는 공개키 암호화 방식 (구체적으로 리프트된 ElGamal) 을 사용합니다.

B. 보안 프로토콜

이 접근법은 최적 정렬 (최소 편차) 을 찾는 문제를 근사 부분 문자열 매칭 문제로 매핑합니다.

1. 서버 측 (모델 소유자):

   • 프로세스 모델을 가져와 언폴딩하고, 런들을 연결하며, FM-Index(BWT 및 Wavelet Matrix) 를 구축합니다.
   • 인덱스 데이터 구조 (특히 0-RANK 및 1-SRANK 벡터) 를 메모리에 저장합니다.
   • 클라이언트의 트레이스를 보지 않습니다.

2. 클라이언트 측 (로그 소유자):

   • 검증할 이벤트 트레이스를 보유합니다.
   • 서버에 쿼리를 보내기 전에 트레이스 데이터와 검색 상태 (인덱스) 를 암호화합니다.

3. 상호작용 (보안 역방향 검색):

   • 클라이언트는 트레이스 문자를 역순으로 반복합니다.
   • 각 문자에 대해 클라이언트는 FM-Index 에서 역방향 검색 (Backward Search) 을 수행합니다. 이는 검색 구간 $[f, g]$를 업데이트하기 위해 Wavelet Matrix 의 행을 비트 단위로 행별로 탐색하는 과정을 포함합니다.
   • 개인정보 보호 메커니즘:
     • 클라이언트는 현재 검색 인덱스를 나타내는 암호화된 벡터를 서버로 전송합니다.
     • 서버는 Wavelet Matrix 행을 기반으로 이러한 인덱스를 업데이트하기 위해 동형 점곱 (homomorphic dot products) 및 덧셈을 수행합니다.
     • 클라이언트가 중간 구간을 학습하여 모델 정보를 유출하는 것을 방지하기 위해, 서버는 결과를 반환하기 전에 무작위 오프셋을 추가합니다.
   • 불일치 처리 (로그 이동):
     • 트레이스의 문자가 모델과 일치하지 않는 경우 ("로그 이동"), 클라이언트는 이전 검색 인덱스 (반복 전에 저장된) 를 복원하고 정렬에 "스킵" 연산을 삽입합니다.
     • 이는 클라이언트가 복호화되었으나 모호하게 처리된 결과를 기반으로 논리 흐름을 제어하기 때문에, 서버가 어떤 문자가 불일치를 일으켰는지 알지 못하는 상태에서 수행됩니다.

3. 주요 기여

1. 준수성 검증에 대한 FHE 의 첫 적용: 이 논문은 동형 암호화를 구체적으로 준수성 검증 문제에 적용한 최초의 작업이라고 주장합니다.
2. 문자열 매칭을 통한 보안 정렬: 복잡한 트레이스 정렬 문제를 FM-Index 를 사용하여 부분 문자열 매칭 문제로 혁신적으로 매핑하여, 암호화된 도메인에서 효율적인 문자열 알고리즘을 사용할 수 있게 합니다.
3. 클라이언트 - 서버 개인정보 보호 모델: 모델 소유자는 트레이스를, 로그 소유자는 모델을 결코 보지 않으면서도 정렬 점수 (및 정렬 자체) 를 계산할 수 있는 프로토콜을 확립합니다.
4. 로그 이동 처리: 클라이언트가 검색 상태를 안전하게 되돌릴 수 있도록 함으로써, 로그에 모델에 없는 이벤트가 있는 경우인 "로그 이동"을 알고리즘이 명시적으로 지원합니다.

4. 결과 및 평가

이 방법은 동형 암호화를 위한 mcl 라이브러리를 사용하여 C++ 로 구현되었으며, 표준 노트북 워크스테이션에서 평가되었습니다.

• 데이터셋: 하나의 실제 세계 이벤트 로그와 두 개의 합성 로그 (동시성, 선택, 루프를 포함하는 소형에서 중형 크기) 를 사용하여 평가되었습니다.
• 성능:
  • 정확도: 이 방법은 모델에 부합하는 트레이스와 주입된 편차가 있는 트레이스에 대한 정렬을 성공적으로 계산했습니다.
  • 오버헤드: 주요 병목 현상은 동형 연산의 계산 비용입니다.
  • 복잡도: 이론적 복잡도는 $O(C \cdot |q| \cdot |T|)$이며, 여기서 $C$는 암호화/복호화를 위한 큰 상수, $|q|$는 트레이스 길이, $|T|$는 인덱싱된 모델 런의 크기입니다.
  • 실행 시간: 144 개의 런과 트레이스당 9 개의 이벤트를 가진 소형 모델의 경우, 평균 정렬 시간은 1.12 분이었습니다. 문자당 소요 시간은 약 0.11 분이었습니다.
  • 확장성: 실행 시간은 트레이스 길이에 대해 준선형 (quasi-linear) 추세를 보였으나, 무거운 암호학적 오버헤드로 인해 현재로서는 실시간 대규모 산업 응용 분야에는 절대 시간이 너무 깁니다.

5. 의의 및 향후 작업

• 의의: 이 작업은 프로세스 마이닝과 개인정보 보호 데이터 마이닝 간의 간극을 해소합니다. 이는 맞춤형 제조 및 의료와 같은 산업의 필수 요구 사항인 독점 로직이나 운영 데이터를 노출하지 않고도 민감한 비즈니스 프로세스를 감사할 수 있음을 보여줍니다.
• 한계:
  • 현재는 로그 이동(로그에서 이벤트 건너뛰기) 만 지원합니다. 모델에서 이벤트를 건너뛰는 모델 이동은 아직 지원하지 않으며, 이는 더 복잡한 논리가 필요합니다.
  • 높은 메모리 및 처리 요구 사항으로 인해 현재 매우 큰 모델이나 실시간 시스템에는 실용적이지 않습니다.
• 향후 방향:
  • 모델 이동을 처리할 수 있도록 접근 방식을 확장합니다.
  • 루프 처리를 개선합니다 (현재는 언폴딩 깊이에 의해 제한됨).
  • 평문 실행과 암호화된 실행 간의 계산 격차를 줄이기 위해 암호학적 구현을 최적화합니다.

결론적으로, 이 논문은 상당한 계산 자원 비용을 치러야 하지만 개인 정보를 보호할 수 있음을 입증하는, 이론적으로 타당하고 기술적으로 실현 가능한 안전한 준수성 검증 프로토타입을 제시합니다.