CacheSolidarity: Preventing Prefix Caching Side Channels in Multi-tenant LLM Serving Systems

이 논문은 멀티테넌트 LLM 서빙 시스템에서 자동 접두사 캐싱 (APC) 으로 인한 타이밍 사이드 채널 공격을 방지하면서도 기존 방어 기법보다 캐싱 재사용률을 70% 높이고 추론 지연을 30% 줄이는 'CacheSolidarity'라는 새로운 시스템을 제안합니다.

핵심

🍕 비유: "공짜 피자가 있는 식당"과 "도둑"

1. 배경: 자동 접시 공유 시스템 (APC)

가상 식당 (LLM 서비스) 이 있다고 상상해 보세요. 이 식당은 주문이 들어오면 **이미 만들어 둔 접시 (캐시)**를 재사용해서 요리를 빨리 내줍니다.

• 상황: 손님이 A 씨가 "치즈 피자"를 주문하고, B 씨도 "치즈 피자"를 주문하면, B 씨는 처음부터 다시 만들지 않고 A 씨가 만든 치즈 피자를 바로 가져갑니다.
• 이점: 요리사 (컴퓨터) 가 일을 덜어서 속도가 매우 빨라지고, 식당은 더 많은 손님을 받습니다. 이를 논문의 **APC(자동 접시 공유)**라고 합니다.

2. 문제: 시간으로 비밀을 알아내는 도둑 (사이드 채널 공격)

하지만 이 시스템에는 치명적인 구멍이 생겼습니다.

• 도둑의 전략: 도둑 (공격자) 이 식당에 와서 "치즈 피자"를 주문합니다.
  • 만약 접시가 이미 준비되어 있다면 (Hit): 요리사가 바로 내주므로 시간이 매우 짧습니다.
  • 만약 접시가 없다면 (Miss): 요리사가 다시 만들어야 하므로 시간이 조금 깁니다.
• 공격: 도둑은 자신의 주문이 "치즈 피자"인지, "페퍼로니 피자"인지, "초콜릿 피자"인지 계속 바꿔가며 주문합니다. 그리고 요리가 나오는 시간을 재봅니다.
  • "아, 페퍼로니를 주문했을 때 시간이 짧네? 그럼 A 씨가 페퍼로니 피자를 주문한 게 틀림없다!"
  • 이렇게 시간 차이를 이용해 다른 손님이 주문한 **비밀 정보 (이름, 주소, 비밀번호 등)**를 하나씩 알아내서 복원해 버립니다.

3. 기존 해결책: "모두를 격리하라" (속도 저하)

이 문제를 해결하기 위해 식당 주인은 "도둑이 들어올까 봐 손님끼리 아예 접시를 공유하지 말자"라고 결정했습니다.

• 결과: A 씨는 A 씨만의 접시만, B 씨는 B 씨만의 접시만 씁니다. 도둑은 다른 손님의 접시를 볼 수 없으니 안전합니다.
• 단점: 하지만 이렇게 하면 요리사가 매번 처음부터 다시 만들어야 하므로 속도가 매우 느려집니다. 정직한 손님들 (일반 사용자) 이 불평을 하게 됩니다.

4. 새로운 해결책: "캐시 솔리다리티 (CacheSolidarity)"

이 논문에서 제안한 CacheSolidarity는 "모두를 격리하는 건 너무 과한 조치"라고 말합니다. 대신 **"비밀이 드러날 만한 부분만 조심하자"**는 지혜로운 방법을 썼습니다.

핵심 아이디어: "공유는 하되, 의심스러운 부분만 잠그자"

1. 소유자 표시 (Owner ID):
   • A 씨가 만든 접시에는 "이건 A 씨 것"이라고 스티커를 붙입니다.
2. 의심스러운 공유 감지 (Detector):
   • B 씨가 A 씨의 접시를 가져가려 할 때, 시스템은 "아, 이건 다른 사람이 만든 거네?"라고 확인합니다.
   • 만약 B 씨가 A 씨의 접시를 공통된 부분 (예: '치즈 피자'라는 말) 까지는 가져가도 되지만, **그 뒤에 숨겨진 비밀 (예: 'A 씨의 전화번호')**이 있는 부분까지 가져가려 하면 시스템이 "STOP!" 신호를 보냅니다.
3. 선택적 격리:
   • 시스템은 A 씨와 B 씨가 공유하는 '치즈 피자' 부분까지는 계속 공유하게 둡니다 (속도 유지).
   • 하지만 비밀이 숨겨진 부분부터는 B 씨가 다시 새로 만들어 먹게 합니다 (격리).
   • 이렇게 하면 도둑은 "아, 이 부분에서는 시간이 길어지네?"라고 알 수 없게 됩니다.

마치 이런 상황과 같습니다:

식당에서 "치즈 피자"라는 공통 메뉴는 모두 공유해서 빠르게 내주고, 하지만 "내 전화번호가 적힌 쪽지"가 붙은 부분은 각자 따로 준비해서 내주는 것입니다. 도둑은 공통 메뉴만 공유되므로 속도가 빠르고, 비밀이 적힌 쪽지 부분만 격리되어 도둑이 그걸로 비밀을 알아낼 수 없게 됩니다.

5. 더 똑똑한 기능: "상황에 따라 켜고 끄기" (Activator)

이 시스템은 또 하나 더 똑똑합니다.

• 상황: 식당이 너무 붐비면 (시스템 부하가 높으면), 요리사가 바빠서 접시를 공유하든 말든 내는 시간이 비슷해집니다. 이때는 도둑이 시간 차이를 알아내기가 어렵습니다.
• 적응: 시스템은 "지금 식당이 너무 붐비니까 도둑이 시간 차이를 알아내기 어렵네? 그럼 격리 기능을 잠시 끄고 모두 공유해서 속도를 높이자!"라고 판단합니다.
• 반대로, 식당이 한산하고 도둑이 시간 차이를 쉽게 알아낼 수 있을 때는 자동으로 격리 기능을 켭니다.

🏆 결론: 왜 이 연구가 중요한가요?

기존의 해결책은 **"안전하니까 속도를 포기하자"**였다면, CacheSolidarity는 **"안전도 지키면서 속도도 지키자"**는 것입니다.

• 성능: 기존 격리 방식보다 속도가 30% 더 빠르고, 접시 (캐시) 를 70% 더 많이 재사용합니다.
• 보안: 도둑이 다른 사람의 비밀을 시간 차이를 통해 알아내는 공격을 완벽하게 막아냅니다.
• 부담: 시스템에 거의 부담을 주지 않습니다 (매우 가볍습니다).

즉, 이 기술은 여러 사람이 함께 사용하는 AI 서비스에서, 속도는 빠르지만 남의 비밀은 절대 훔쳐보지 못하게 하는 완벽한 균형을 찾아낸 것입니다.

기술 요약

1. 문제 정의 (Problem Statement)

배경:
대규모 언어 모델 (LLM) 서비스는 처리량 (Throughput) 을 높이고 지연 시간 (Latency) 을 줄이기 위해 자동 접두어 캐싱 (Automatic Prefix Caching, APC) 기술을 광범위하게 사용합니다. APC 는 이전 요청의 시작 부분 (접두어) 과 동일한 텍스트로 시작하는 새로운 요청이 들어왔을 때, 이미 계산된 모델 상태 (KV Cache) 를 재사용하여 불필요한 계산을 방지합니다.

위협 (Timing Side-Channel):
APC 는 성능을 향상시키지만, 타이밍 사이드 채널 (Timing Side Channel) 취약점을 초래합니다.

• 메커니즘: 캐시 히트 (Cache Hit) 시에는 재계산이 필요 없어 응답 시간 (TTFT, Time-to-First-Token) 이 짧고, 캐시 미스 (Cache Miss) 시에는 재계산이 필요해 응답 시간이 깁니다.
• 공격 시나리오: 멀티 테넌트 환경에서 공격자는 특정 템플릿을 기반으로 다양한 후보 단어를 가진 요청을 보내고 TTFT 를 측정합니다. 공격자가 victim 의 요청과 접두어가 일치하는지 (히트) 또는 일치하지 않는지 (미스) 를 관측함으로써, victim 의 민감한 프롬프트 (예: 이름, 의료 기록 등) 를 한 글자씩 점진적으로 복원 (Prompt Stealing) 할 수 있습니다.

기존 방어책의 한계:
기존 방어책은 다음과 같은 심각한 단점이 있습니다.

1. 완전 격리 (User-level Isolation): 사용자 간 캐시 공유를 완전히 차단합니다. 보안은 강화되지만, APC 의 성능 이점 (지연 시간 감소, 처리량 증가) 이 사라져 정상 사용자의 성능이 크게 저하됩니다.
2. 타이밍 난독화 (Obfuscation): 모든 요청에 노이즈를 추가하여 히트/미스 차이를 흐리게 합니다. 이는 모든 사용자에게 불필요한 지연을 유발하며, 공격자가 미세한 차이를 증폭하여 우회할 수 있습니다.
3. 선택적 격리 (Semantic Analysis): LLM 을 이용해 프롬프트의 민감성을 분석하여 격리합니다. 이는 계산 비용이 매우 높고, 오분류 (Misclassification) 로 인해 보안이 누락될 수 있습니다.

---

2. 방법론: CacheSolidarity (Methodology)

핵심 통찰:
전체 사용자를 격리할 필요는 없으며, 공격이 발생할 수 있는 '공유된 접두어 (Shared Prefix)'만 선택적으로 격리하면 됩니다. 즉, 악의적인 공유가 감지될 때만 격리하고, 그 외에는 효율적인 공유를 유지하는 협력적 효율성 (Cooperative Efficiency) 원칙을 따릅니다.

시스템 아키텍처:
CacheSolidarity 는 vLLM 과 같은 최신 LLM 서빙 시스템 위에 구축되며, 다음 세 가지 경량 구성 요소로 이루어집니다.

1. KV Cache 확장 (KV Cache Extension):

   • 각 캐시 엔트리에 최소한의 메타데이터 (OwnerID, AttackFlag) 를 추가합니다.
   • OwnerID: 해당 캐시 엔트리를 처음 생성한 사용자의 ID.
   • AttackFlag: 여러 사용자가 이 접두어를 공유할 때 설정되는 플래그로, 이후 비소유자의 재사용을 차단합니다.

2. 검출기 (Detector):

   • 요청이 들어왔을 때 캐시 히트가 발생하면, 해당 접두어의 소유자가 요청자와 일치하는지 확인합니다.
   • 소유자 일치: 정상 재사용 허용.
   • 소유자 불일치 (새로운 사용자): 해당 접두어를 AttackFlag 로 표시하고, 이후 비소유자가 해당 접두어를 넘어가려 할 경우 재사용을 중단하고 나머지 토큰을 새로 계산 (Partial Hit) 합니다. 이를 통해 공격자가 victim 의 접두어 정보를 추론하는 것을 차단합니다.

3. 활성화기 (Activator):

   • 동적 활성화: APC 타이밍 사이드 채널이 실제로 추론 가능한지 (히트와 미스의 TTFT 차이가 통계적으로 유의미한지) 를 실시간으로 모니터링합니다.
   • KDE Overlap: 히트와 미스의 TTFT 분포 간 커널 밀도 추정 (KDE) 중첩도를 계산합니다.
     • 중첩도 높음 (차이 불분명): 시스템 부하가 높거나 모델이 작아 차이가 모호할 때 -> 격리 기능 비활성화 (성능 최적화).
     • 중첩도 낮음 (차이 명확): 공격이 가능할 때 -> 격리 기능 활성화 (보안 강화).
   • 이는 불필요한 오버헤드를 방지하고, 공격이 가능한 환경에서만 보안을 적용합니다.

---

3. 주요 기여 (Key Contributions)

1. APC 타이밍 사이드 채널에 대한 심층 분석: 프롬프트 길이, LLM 모델 크기, 시스템 부하 (RPS), 하드웨어 플랫폼 등 사이드 채널의 취약성을 결정하는 핵심 파라미터들을 정량적으로 분석했습니다.
2. CacheSolidarity 시스템 설계: 사용자 전체를 격리하지 않고, 위험한 접두어만 선택적으로 격리하는 경량 시스템을 제안했습니다. 이는 보안과 성능의 균형을 이룹니다.
3. 엄밀한 보안 분석 및 검증: 프롬프트 탈취 공격 (Prompt Stealing) 에 대한 이론적 보안 보장을 제공하며, 실험을 통해 타이밍 누수가 차단됨을 입증했습니다.
4. 광범위한 평가: 다양한 워크로드와 9 가지 LLM 모델 (0.5B~13B 파라미터) 에 대한 평가를 통해 기존 방어책 대비 캐시 재사용률 70% 증가, 추론 지연 시간 30% 감소를 달성했음을 보였습니다.

---

4. 실험 결과 (Results)

• 성능 향상:
  • 기존 '사용자 격리 (User Cache Isolation)' 방식 대비 최대 70% 더 높은 캐시 재사용률을 기록했습니다.
  • 30% 낮은 추론 지연 시간 (TTFT) 을 달성하여, APC 의 성능 이점을 유지하면서도 보안을 확보했습니다.
  • '접두어 캐싱 (Prefix Caching, 보안 없음)' 방식과 비교해도 성능 저하는 5~10% 수준으로 매우 미미했습니다.
• 다양한 모델 및 워크로드:
  • 다양한 크기의 LLM 모델 (Gemma, Llama, Qwen 등) 에서 일관된 성능 향상을 보였습니다.
  • 고부하 (High RPS) 상황에서는 타이밍 차이가 자연스럽게 사라지므로 Activator 가 격리를 비활성화하여 성능을 최적화했습니다.
• 보안 검증:
  • 공격자가 victim 의 비밀 정보를 추측하는 시나리오에서, CacheSolidarity 가 적용된 시스템은 공격자의 TTFT 패턴에서 히트/미스 차이를 관측할 수 없게 만들었습니다. (공격자의 요청 9 번째에서 정답을 맞췄을 때에도 TTFT 스파이크가 발생하지 않음).
• 오버헤드:
  • 지연 시간 오버헤드: 요청당 약 0.007ms (Detector 0.004ms + Activator 0.003ms) 로 거의 무시할 수준입니다.
  • 메모리 오버헤드: 캐시 엔트리를 당 32 바이트 증가시킵니다.

---

5. 의의 및 결론 (Significance)

이 논문은 LLM 서빙 시스템에서 보안과 성능이 상충 관계 (Trade-off) 가 아니라는 점을 증명했습니다.

• 실용성: 무거운 보안 조치 (전체 격리, 노이즈 주입) 대신, 공격이 실제로 발생할 수 있는 조건과 영역만 정밀하게 차단하는 정밀 타격 (Precision Defense) 방식을 제시했습니다.
• 적응형 보안: 시스템 부하와 환경에 따라 보안 강도를 동적으로 조절하여, 공격이 불가능한 상황에서는 성능 저하 없이 APC 의 이점을 온전히 누릴 수 있게 합니다.
• 미래 지향성: 멀티 테넌트 LLM 서비스의 보안 표준을 제시하며, 오픈소스 (vLLM 기반) 로 공개되어 커뮤니티의 채택과 확장성을 기대할 수 있습니다.

결론적으로, CacheSolidarity는 멀티 테넌트 LLM 환경에서 타이밍 사이드 채널 공격을 효과적으로 차단하면서도, 기존 시스템의 고효율성을 유지하는 경량화된 솔루션입니다.