Secure Conformance Checking using Token-based Replay and Homomorphic Encryption

"Secure Conformance Checking using Token-based Replay and Homomorphic Encryption" 논문에 대한 상세한 기술 요약입니다.

1. 문제 제기

준수성 검증 (Conformance checking) 은 프로세스 마이닝의 핵심 연산으로, 이벤트 로그 (실제 행동) 와 프로세스 모델 (기대 행동) 을 비교하여 편차를 식별합니다. 전통적으로 이 작업은 모델 소유자와 로그 소유자가 모두 비즈니스 분석가에게 데이터를 평문으로 공유해야 합니다.

그러나 맞춤형 제조 또는 조직 간 협력과 같은 시나리오에서는 당사자들이 민감한 정보를 보호하기를 원합니다.

• 모델 소유자는 독점적인 프로세스 로직 (예: 생산 워크플로우) 을 비밀로 유지하고자 할 수 있습니다.
• 로그 소유자는 모델 소유자에게서 민감한 실행 데이터 (예: 고객 주문 세부 사항) 를 보호하고자 할 수 있습니다.

과제는 다른 당사자에게 기본 프로세스 모델이나 이벤트 로그를 노출하지 않으면서 암호화된 데이터에 대해 준수성 검증 (특히 토큰 기반 재생) 을 수행하고, 적합도 지표 (편차) 를 계산할 수 있는 능력을 유지하는 것입니다.

2. 방법론

저자들은 **동형 암호화 (Homomorphic Encryption, HE)**를 사용하고 선형 대수 (행렬 및 벡터 연산) 를 사용하여 토큰 기반 재생 알고리즘을 재구성한 안전한 프레임워크를 제안합니다.

핵심 개념

• 토큰 기반 재생: 이벤트 로그 트레이스를 페트리 넷 (Petri net) 에서 "재생"하는 알고리즘입니다. 이는 소비된 토큰, 생성된 토큰, 전이를 활성화하기 위해 필요한 누락 토큰, 그리고 끝남에 남아있는 토큰을 추적합니다.
• 동형 암호화 (HE): 구체적으로 저자들은 TFHE 기반인 Zama 의 Concrete를 활용합니다. 이는 복호화 없이 암호화된 정수에서 산술 연산 (덧셈, 뺄셈, 곱셈) 과 비교 (최소/최대) 를 지원합니다.
• 클라이언트 - 서버 아키텍처:
  • 클라이언트 (로그 소유자): 이벤트 로그를 보유합니다. 현재 마킹과 발사할 다음 이벤트 (전이) 를 암호화하여 서버로 전송합니다.
  • 서버 (모델 소유자): 페트리 넷 모델을 보유합니다. 사전 계산된 행렬을 사용하여 암호화된 데이터에서 재생 단계를 수행합니다. 새로운 암호화된 마킹과 로컬 카운터를 반환합니다.
  • 개인정보 보호: 서버는 평문 로그를 결코 보지 않으며, 클라이언트는 재생 결과에서 추론되는 것 이상으로 평문 모델 구조를 보지 않습니다.

알고리즘적 재구성

토큰 기반 재생을 HE 와 호환되게 만들기 위해 저자들은 조건부 논리와 분기에 의존하는 전통적인 "토큰 게임"을 행렬 곱셈 및 벡터 연산으로 대체했습니다.

1. 사전 계산 (서버 측):

   • 페트리 넷은 **연결 행렬 (Incidence Matrix, $N$)**로 변환됩니다.
   • 모든 가능한 "활성화 (enablements)"(현재 마킹과 전이의 조합) 를 나타내는 **동역학 행렬 (Dynamics Matrix, $E$)**이 구성됩니다.
   • 유효한 발사 시퀀스에 대한 파라키 벡터 (전이 횟수) 를 저장하는 **발사 시퀀스 행렬 (Firing Sequences Matrix, $S$)**이 있습니다.
   • 모든 전이에 대한 입력 장소를 저장하는 **프리셋 행렬 (Preset Matrix, $P$)**이 있습니다.

2. 재생 단계 (안전한 실행):

   • 활성화 확인: 클라이언트는 암호화된 현재 마킹 ($M$) 과 암호화된 다음 이벤트 ($t$) 를 보냅니다. 서버는 행렬 곱셈 $E \cdot [M, t]^T$를 사용하여 **선택자 벡터 (selector vector, $sel$)**를 계산합니다. 이는 전이가 직접 활성화되는지 아니면 침묵 전이 ($\tau$) 가 필요한지 결정합니다.
   • 누락 토큰 처리: 전이가 활성화되지 않은 경우, 알고리즘은 프리셋 행렬 $P$에서 필요한 "누락 토큰"($\pi$) 을 계산합니다.
   • 통합 마킹 업데이트: HE 에서 정보를 누출하는 조건부 if/else 문장을 피하기 위해 저자들은 "적합" 및 "부적합" 논리를 단일 방정식으로 결합합니다:
     $$M' = (M + N \cdot \sigma^T) \cdot \text{sum}(sel) + (M + \pi^T + N \cdot t^T) \cdot (1 - \text{sum}(sel))$$
     여기서 $\text{sum}(sel)$은 이진 스위치 (활성화 시 1, 비활성화 시 0) 로 작용합니다.
   • 카운터 계산: 알고리즘은 벡터 차이와 조건부 마스킹 (스위치를 기반으로 0 또는 1 을 곱함) 을 사용하여 누락 ($m$), 소비 ($c$), 생성 ($p$), 그리고 잔여 ($r$) 토큰을 계산합니다.

3. 적합도 계산:

   • 트레이스의 모든 이벤트를 처리한 후, 클라이언트는 최종 카운터를 복호화하고 표준 공식을 사용하여 적합도 점수를 계산합니다:
     $$f = \frac{1}{2}\left(1 - \frac{m}{c}\right) + \frac{1}{2}\left(1 - \frac{r}{p}\right)$$

3. 주요 기여

1. 최초의 안전한 토큰 기반 재생: 이는 동형 암호화를 토큰 기반 재생 준수성 검증 알고리즘에 적용한 첫 번째 작업입니다.
2. 행렬 기반 재구성: 저자들은 비선형적이고 상태 의존적인 토큰 게임을 동형 암호화에 적합한 선형 대수적 형식으로 성공적으로 변환하여 분기 논리의 필요성을 제거했습니다.
3. 개인정보 보호 아키텍처: 모델 소유자가 트레이스 내용을 학습하지 않고 암호화된 트레이스를 처리하고, 로그 소유자가 재생 결과 이상으로 모델 구조에 대해 아무것도 학습하지 않는 클라이언트 - 서버 프로토콜입니다.
4. 구현 및 평가: Zama 의 Concrete 프레임워크를 사용하여 Python 으로 구현된 작동 프로토타입으로, 이 접근 방식의 실현 가능성을 입증했습니다.

4. 결과

저자들은 Process Mining 책과 PM4Py 튜토리얼에서 가져온 페트리 넷 모델과 합성 이벤트 로그를 사용하여 프로토타입을 평가했습니다.

• 성능 (평문 vs 암호화):
  • 평문 데이터 (CLR): 실행 시간은 밀리초 단위였습니다.
  • 암호화된 데이터 (SEC): 토큰 카운터 계산이 없는 트레이스의 경우 실행 시간은 7.8 초에서 15.8 초 사이였습니다.
  • 카운터 포함 암호화 (SEC+): 실행 시간은 19.3 초에서 37.4 초 사이였습니다.
• 최적화 통찰:
  • 서버 측 함수 내부에서 카운터 ($p, c, m, r$) 를 계산한 초기 버전은 35 분에서 84 분이 소요되었습니다.
  • 저자들은 이 지연이 HE 컴파일러 (Concrete) 가 반환값에 대해 기본적으로 16 비트 정수를 사용하여 막대한 오버헤드를 발생시켰기 때문임을 확인했습니다. 카운터 누적을 클라이언트 측으로 이동하여 (중간 결과를 복호화) 시간을 40 초 미만으로 단축했습니다.
• 확장성: 이 방법은 다양한 길이 (4 개에서 13 개의 이벤트) 의 트레이스와 적합 및 부적합 트레이스를 모두 성공적으로 처리했습니다.

5. 의의 및 향후 작업

• 의의: 이 논문은 안전한 준수성 검증이 실제로 실현 가능함을 입증합니다. 이는 조직이 기밀이나 환자 프라이버시를 훼손하지 않고 공급망이나 의료 분야에서 프로세스 준수를 검증할 수 있게 합니다. 분기 논리에서 행렬 연산으로의 전환은 프로세스 마이닝에 HE 를 적용하기 위한 중요한 이론적 기여입니다.
• 한계:
  • 성능: 1 분 미만이지만 암호화된 실행은 평문에 비해 현저히 느립니다 (수십 배 이상).
  • 토큰 홍수: 현재 구현은 암호화 도메인에서 장소가 1 개 이상의 토큰을 축적하는 "토큰 홍수" 문제를 완전히 해결하지 못합니다.
  • 정밀도: HE 프레임워크의 정수 정밀도에 대한 의존성은 연산의 복잡성을 제한합니다.
• 향후 방향:
  • 실제 생활 이벤트 로그를 통한 테스트.
  • 암호화 도메인에서 토큰 홍수 문제 해결.
  • 정밀도와 성능 간의 균형을 최적화하기 위한 다른 HE 플랫폼 탐색.
  • 통신 비용을 분석하기 위한 전체 클라이언트 - 서버 네트워크 버전 구현.

결론적으로, 이 논문은 안전한 프로세스 마이닝에 대한 견고한 개념 증명 (proof-of-concept) 을 제공하며, 동형 암호화가 대수적 재구성을 통해 토큰 기반 재생과 같은 복잡한 알고리즘 작업에 효과적으로 적응될 수 있음을 보여줍니다.