기술 요약: OTRO – Square-Root ORAM을 이용한 Oblivious Tokenization 경로

1. 문제 정의

본 논문은 기밀 LLM(Large Language Model) 서빙의 핵심적인 보안 격차인 토크나이저(tokenizer) 문제를 식별한다. Intel TDX 및 NVIDIA GPU TEE와 같은 신뢰 실행 환경(TEE)은 메모리 내용과 연산을 보호하지만, 메모리 액세스 패턴까지 본질적으로 숨기지는 못한다.

• 취약점: 현대적 LLM은 바이트 쌍 인코딩(BPE) 토크나이저를 사용하며, 이는 원시 텍스트를 토큰 ID로 변환하기 위해 결정론적인 테이블 기반 조회(어휘집 및 병합 테이블)에 의존한다. 토큰에서 메모리 주소로의 매핑은 초기화 후 고정되어 있기 때문에, 하이퍼바이저를 제어하거나 서버에 물리적 접근 권한이 있는 공격자는 DRAM 액세스 패턴(페이지 폴트 또는 캐시 사이드 채널을 통해)을 관찰할 수 있다.
• 결과: 최근 연구(TDXRay)는 이러한 액세스 패턴을 통해 사용자 프롬프트를 90% 이상의 유사도로 엔드 투 엔드 재구성할 수 있음을 입증했으며, 이는 TEE 보호를 사실상 무력화한다.
• 완화의 어려움: PathORAM과 같은 표준 Oblivious RAM(ORAM) 솔루션은 과도한 지연 시간을 유발한다. PathORAM을 단순하게 통합하면 첫 토큰 생성 시간(TTFT)이 약 13배 증가하며, 단순한 Square-Root ORAM(SqrtORAM)은 $\sqrt{N}$ 액세스마다 발생하는 비용이 큰 $O(N \log^2 N)$ 재구축(rebuild) 비용으로 인해 TTFT를 약 323배 증가시킨다. 이러한 오버헤드는 지연 시간에 민감한 LLM 추론에 있어 수용 불가능한 수준이다.

2. 방법론: OTRO 아키텍처

저자들은 LLM 서빙에 최적화된 효율적인 oblivious tokenization 경로인 OTRO(Oblivious Tokenization Path)를 제안한다. 핵심 통찰은 토크나이저 테이블이 추론 중에 **읽기 전용(read-only)**이라는 점이다. 이 특성 덕분에 OTRO는 비용이 많이 드는 재구축 작업을 임계 경로(critical path)에서 분리할 수 있다.

OTRO는 다음 세 가지 핵심 혁신을 통해 이를 달enc한다:

A. 풀링된 SqrtORAM 복제 (Pooled SqrtORAM Replication)

$\sqrt{N}$ 액세스 후에 반드시 재구축해야 하는 단일 SqrtORAM 인스턴스 대신, OTRO는 복제된 읽기 전용 SqrtORAM 인스턴스 풀을 유지한다.

• 각 인스턴스는 동일한 어휘 및 병합 데이터를 보유하지만, 서로 다른 무작위 순열(random permutation)을 가진다.
• 데이터가 읽기 전용이므로 인스턴스 간에 업데이트를 조정할 필요가 없으며, 단지 obliviousness를 유지하기 위해 재배열(reshuffle)되기만 하면 된다.
• 하나의 인스턴스가 재구축되는 동안에도 다른 인스턴스들이 요청을 계속 처리할 수 있다.

B. 에포크 기반 로테이션 및 패딩 (Epoch-Based Rotation and Padding)

OTRO는 풀을 관리하기 위해 에포크 기반 로테이션 정책을 구현한다:

• 로테이션(Rotation): 각 인스턴스는 정확히 $\sqrt{N}$ 번의 액세스를 수행한다(한 에포크). 한계치에 도달하면 해당 인스턴스는 비동기 백그라운드 재구축 대상으로 표시되며, 시스템은 새로운 인스턴스로 로테이션한다.
• 패딩(Padding): 에포크 내의 정확한 액세스 횟수가 정보를 누설하는 것을 방지하기 위해, OTRO는 각 에포크를 더미 액세스로 패딩하여 $\sqrt{N}$ 경계에 도달하도록 한다. 이를 통해 관찰 가능한 트랜스크립트는 특정 룩업의 정밀한 횟수가 아닌 에포크 횟수(즉, 거친 수준의 액세스 횟수)만을 드러내게 된다.
• 보안: 인스턴스 선택은 액세스되는 논리적 주소와 독립적인 글로벌 액세스 횟수의 결정론적 함수이며, 이를 통해 액세스 패턴의 구별 불가능성을 보장한다.

C. KV-캐시를 고려한 청크 단위 토크나이제이션 (Chunked Tokenization with KV-Cache Awareness)

풀 크기를 최소화하여 스톨(stall)을 방지하고 재구축 지연 시간을 숨기기 위해, OTRO는 청크 단위 토크나이제이션을 도입한다:

• 긴 입력 프롬프트는 사전 토크나이제이션 경계(공백으로 구분된 단어)에서 작은 청크로 분할된다.
• 청크의 토크나이제이션은 GPU의 프리필(prefill) 단계와 인터리빙(interleaved)된다.
• 시스템은 GPU가 청크를 처리하는 데 걸리는 시간($T_{gpu, prefill}$)이 SqrtORAM 인스턴스를 재구축하는 데 걸리는 시간($T_{reshuffle}$)보다 크도록 튜닝된다.
• 이러한 중첩(overlap)을 통해 재구축이 GPU 연산 중에 백그라운드에서 발생할 수 있게 하며, 이를 통해 재구축 비용을 상쇄하고 필요한 SqrtORAM 인스생스 수를 줄인다.

D. 디토크나이제이션 (Detokenization)

OTRO는 디토크나이제이션 경로(토큰 ID를 다시 텍스트로 변환)에도 ORAM 보호를 적용한다. 디코드 단계의 특성상(토큰이 시간이 지남에 따라 느리게 생성됨), 재구축을 디코드 커널과 중첩시키기에 소수의 풀(예: 2개 인스턴스)만으로도 충분하다.

3. 주요 기여

1. 비용 특성화: 저자들은 네이이브(naive) ORAM 방어책이 매우 과도한 비용(13배~323배 속도 저하)을 초래함을 입증한다. 재구축을 임계 경로에서 제거함으로써, OTRO는 보호되지 않은 베이스라인과 거의 유사한 성능을 유지한다.
2. Oblivious 아키텍처: 복제된 읽기 전용 SqrtORAM 인스턴스 풀, 에포크 기반 로테이션, 액세스 횟수 패딩을 활용하여 재구축을 임계 경로에서 제거하는 새로운 아키텍처를 제시한다.
3. 지연 시간 인식 통합: 청크 단위 토크나이제이션을 GPU 프리필 및 KV-캐시 메커니즘과 결래하여 CPU 측 재구축을 GPU 연산과 중첩시킴으로써, 메모리 점유율과 인스턴스 수를 최소화한다.
4. 엔드 투 엔드 프로토타입: TDX가 활성화된 기밀 가상 머신(CVM) 및 NVIDIA H100 GPU 환경에서 HuggingFace Tokenizers와 nano-vLLM 내에 OTRO를 구현하였다.
5. 누설 감소: OTRO의 액세스 패턴이 접촉된 특정 테이블 항목에 대해 아무것도 드러내지 않음을 공식적으로 증명한다. 패딩을 사용할 경우, 유일하게 피할 수 없는 누설은 입력 프롬프트 길이(바이트 길이)뿐이며, 이는 실용적인 모든 ORAM 설계에서 나타나는 현상이다.

4. 실험 결과

시스템은 Intel Xeon Gold CPU와 NVIDIA H100 GPU를 사용하여 Llama-3.1, Qwen3, Gemma-3, Phi-3 모델에 대해 평가되었다.

• 지연 시간 (TTFT): OTRO는 보호되지 않은 베이스라인 대비 TTFT 오버헤드를 최대 **4.5%**로 제한한다.
  • PathORAM은 TTFT를 약 1.48배 증가시켰다.
  • 네이티브 SqrtORAM은 TTFF를 약 11.12배 증가시켰다.
  • 청킹을 적용한 OTRO는 "이상적인" SqrtORAM 시나리오(재구축 페널티가 없는 경우)에 근접한 성능을 보이며, 토크나이저로 인한 지연 시간을 전체 TTFT의 10% 미만으로 유지한다.
• 메모리 오버헤드: OTRO는 클라이언트당 0.5 GB 미만의 메모리 오버헤드를 추가한다 (예: 48개 인스턴스 사용 시 Llama-3.1 기준 약 286 MB). 이는 일부 구성에서의 PathORAM 오버헤드보다 훨씬 낮으며, 256 GB CVM이 수십 명의 동시 접속 클라이언트를 지원할 수 있게 한다.
• 초기화: 초기화 비용은 모델에 따라 35~350% 증가하지만, 이는 모델 로드 시 발생하는 일회성 비용이므로 시스템 병목으로 간주되지 않는다.
• 누설 분석:
  • ORAM이 없는 경우, 공격자는 잔여 불확실성이 0 비트인 상태로 프롬프트를 재구성할 수 있다.
  • OTRO (패딩 없음)의 경우, 잔여 불확실성은 1.60 비트이다.
  • OTRO (액세스 횟수 패딩 포함)의 경우, 잔여 불확실성은 5.49 비트로 상승하며, 이는 원래 프롬프트 엔트로피의 38.4%를 회복함을 의미한다. 남은 누설은 주로 입력 바이트 길이와 액세스 횟수 사이의 피할 수 없는 상관관계에서 기인한다.

5. 의의 및 주장

본 논문은 OTRO가 생산 환경의 LLM 서빙 스택에서 엔드 투 엔드 기밀성을 확보할 수 있는 실행 가능한 경로를 제공한다고 주장한다. 이는 표준 TEE 보호를 우회하는 특정 고충실도 사이드 채널(토크나이저 액세스 패턴)을 해결한다.

• 실용성: 이론적인 ORAM 솔루션이나 다른 위협 모델(예: 메모리 제약이 있는 SGX)을 위해 설계된 것과 달리, OTRO는 현대적인 GPU 지원 CVM의 지연 시간에 민감한 읽기 전용 성격의 LLM 토크나이제이션을 위해 특별히 설계되었다.
• 보안과 성능의 트레이드오프: 본 연구는 강력한 액세스 패턴 기밀성(어떤 토큰이 액세스되는지를 숨김)을 달성하면서도 성능 영향(TTFT < 5%)을 무시할 만한 수준으로 유지하는 것이 가능함을 보여준다. 이는 이전에는 매우 어렵다고 여겨졌던 트레이드오프이다.
• 범위: 저자들은 OTRO가 토크나이저 테이블의 메모리 액세스 패턴을 보호한다고 명시한다. 이는 모든 사이드 채널(예: 특정 코드 패턴의 타이밍 가변성)을 제거하거나, 실용적인 ORAM 배포에서 불가피한 기초값으로 취급되는 입력 길이 누설을 방지한다는 것을 의미하지 않는다.

요약하자면, OTRO는 복제와 스케줄링을 통해 SqrtORAM의 급격한 임계 경로 재구축 비용을 백그라운드 작업으로 전환함으로써, 강력하고 특권이 있는 공격자가 존재하는 상황에서도 저지연의 보안 LLM 추론을 가능하게 한다.