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

CacheSolidarity is a lightweight system that secures multi-tenant LLM serving against Automatic Prefix Caching side-channel attacks by selectively isolating suspicious cache reuse, thereby achieving significantly higher cache efficiency and lower latency compared to existing all-or-nothing isolation defenses.

The Gist

Here is an explanation of the paper CacheSolidarity using simple language and everyday analogies.

The Problem: The "Fast Lane" That Leaks Secrets

Imagine a massive, high-speed library (the LLM Serving System) where people come to ask questions and get answers. To make things super fast, the librarians use a trick called Automatic Prefix Caching (APC).

Think of this like a reusable template.

• If User A asks, "Write a story about a dragon named Sparky," the librarian writes the first half of the story ("Once upon a time, there was a dragon...") and saves it in a "Fast Lane" cache.
• If User B comes along and asks, "Write a story about a dragon named Rex," the librarian sees the start is the same. Instead of rewriting the whole intro, they just grab the saved "Fast Lane" template and only write the part about "Rex."

This is great for speed. It saves time and energy.

But here is the security flaw:
Because the "Fast Lane" is so much quicker than writing from scratch, the time it takes to get the first word of the answer tells you something.

• Fast response: "Oh, you used the template! You must have asked about a dragon."
• Slow response: "You didn't use the template. You asked about something totally new."

A sneaky attacker (the Bad Guy) can exploit this. They can guess secrets by asking questions like, "Is the dragon's name Sparky?" and "Is the dragon's name Rex?"

• If the answer comes back fast, the Bad Guy knows, "Aha! The victim's prompt actually said 'Sparky'!"
• By guessing word-by-word and watching the clock, the Bad Guy can steal the victim's private secrets (like names, passwords, or medical conditions) without ever seeing the actual data.

The Old Solutions: The "Sledgehammer" Approach

Previously, to stop this, security experts used a "sledgehammer" approach. They said: "This is too dangerous. Let's just ban the Fast Lane entirely for everyone."

• The Result: No one shares templates anymore. Everyone has to write from scratch.
• The Downside: The library becomes incredibly slow. Honest, innocent users suffer because the system is too cautious. It's like banning all cars from a highway because one person might speed.

The New Solution: CacheSolidarity

The authors of this paper built CacheSolidarity. Instead of banning the Fast Lane for everyone, they built a smart security guard that only stops the Bad Guy when they try to cheat.

Here is how it works, using a Hotel Analogy:

1. The "Owner" Badge

When a user (User A) creates a new template (a "prefix"), the system puts a digital Owner Badge on it.

• Analogy: Imagine User A writes a recipe and puts a name tag on the card: "Created by Alice."

2. The "Suspicious" Flag

If User B (a stranger) tries to use Alice's recipe, the system checks the badge.

• Scenario A (Benign): User B is just using the same recipe Alice wrote. The system says, "Okay, you can use the first part, but since you aren't Alice, we stop sharing the secret ingredients right here."
• Scenario B (The Attack): User B tries to guess a secret word in the recipe. The system sees User B is trying to reuse a part of the recipe that belongs to someone else. It immediately slaps a "SUSPICIOUS" Flag on that specific part of the recipe.

3. The "Selective Isolation"

Once a part is flagged as suspicious:

• For the Owner (Alice): She can still use her own recipe perfectly. No slowdown.
• For the Stranger (User B): The system says, "Stop! You can't use the shared part anymore. You have to write your own version from scratch."

The Magic: The system only isolates the specific suspicious part of the conversation. It doesn't lock out the whole user. It's like a bouncer who only kicks out the person trying to sneak into the VIP section, while letting everyone else enjoy the party.

4. The "Smart Switch" (The Activator)

The paper also noticed something important: The "Fast Lane" timing leak only works when the library is quiet. If the library is super busy (high traffic), the noise of the crowd masks the difference between a fast and slow response.

So, CacheSolidarity has a Smart Switch:

• Busy Time: The system knows the timing leak is hidden by the noise. It turns off the strict security checks to keep things running super fast.
• Quiet Time: The system knows the timing leak is visible. It turns the security checks ON to catch the Bad Guy.

Why This Matters

• For the Good Guys: They get the speed of the "Fast Lane" (caching) most of the time. They don't suffer from the slow "Sledgehammer" approach.
• For the Bad Guys: They can't steal secrets anymore because the system stops them the moment they try to guess a shared secret.
• For the System: It's lightweight. It doesn't need to read the content of the messages to know if they are dangerous; it just looks at who is using whose template.

Summary in One Sentence

CacheSolidarity is like a smart librarian who lets everyone share a common starting point to save time, but instantly locks the door if a stranger tries to peek at a secret part of someone else's story, all while keeping the library running at full speed.

Technical Summary

Here is a detailed technical summary of the paper "CacheSolidarity: Preventing Prefix Caching Side Channels in Multi-tenant LLM Serving Systems."

1. Problem Statement

Large Language Model (LLM) serving systems rely on Automatic Prefix Caching (APC) to accelerate inference. APC works by reusing Key-Value (KV) cache states for the beginning of a request (the prefix) if another request shares the same text. While this significantly improves throughput and reduces latency, it introduces a timing side-channel vulnerability in multi-tenant environments.

• The Vulnerability: Cache hits (reusing cached states) are significantly faster than cache misses (recomputing states). This creates observable differences in Time-to-First-Token (TTFT).
• The Attack: In a multi-tenant setting, an attacker can send crafted prompts with varying candidate secrets (e.g., names, medical conditions) and measure the TTFT. By observing whether the system returns a "hit" (fast) or "miss" (slow), the attacker can incrementally reconstruct a victim's private prompt without direct access to the cache.
• Limitations of Current Defenses: Existing solutions are "sledgehammer" approaches that sacrifice performance:
  • User-level Isolation: Disables APC entirely or partitions caches per user, eliminating cross-user reuse and drastically reducing efficiency.
  • Timing Obfuscation: Injects noise to mask latency differences, penalizing benign users with uniform delays.
  • Semantic Analysis: Uses heavy LLM-based analysis to classify sensitive prompts, which is computationally expensive and prone to misclassification.

2. Methodology: CacheSolidarity

The authors propose CacheSolidarity, a system-level solution that secures APC against timing side channels without sacrificing performance. The core insight is that isolating entire users is unnecessary; instead, the system should only isolate specific prefixes that are being suspiciously reused across different security domains.

Core Components

1. KV Cache Extension:

   • Extends each cache entry with minimal metadata:
     • OwnerID: The ID of the user who first created the entry.
     • AttackFlag: A marker indicating the prefix is shared by multiple users and should be isolated for non-owners.
   • This adds negligible memory overhead (approx. 32 bytes per entry).

2. Detector (Selective Isolation):

   • Monitors cache hits in real-time.
   • Logic:
     • If a request hits a cache entry owned by a different user, the system flags that entry.
     • For subsequent requests, if a non-owner attempts to reuse a flagged prefix, the system stops reuse at that point.
     • The system recomputes the remaining tokens for the non-owner, creating a new cache path.
   • Result: Benign users (owners) continue to enjoy full reuse. Attackers (non-owners) are forced to recompute, breaking the timing correlation needed to infer secrets.

3. Activator (Dynamic Adaptation):

   • Recognizes that timing side channels are not always exploitable. The distinguishability of hits vs. misses depends on:
     • Prefix Length: Longer prefixes create larger latency gaps.
     • Model Size: Larger models have larger latency gaps.
     • System Load: High load (high Requests Per Second) introduces queuing delays that mask timing differences.
   • Mechanism: The Activator continuously monitors the Kernel Density Estimation (KDE) overlap between the TTFT distributions of hits and misses.
     • If the overlap is high (distributions are indistinguishable), isolation is disabled to maximize performance.
     • If the overlap is low (distributions are distinct), isolation is enabled.
   • This ensures security is only applied when the side channel is actually exploitable.

3. Key Contributions

• Analysis of APC Exploitability: The paper provides a detailed characterization of how prefix length, model size, system load, and hardware affect the strength of the timing side channel, proving that the threat is conditional, not uniform.
• Novel Defense Mechanism: Introduces a lightweight, selective isolation strategy that protects shared prefixes rather than entire users, preserving the efficiency of APC.
• Dynamic Activation: Proposes a threshold-based mechanism to toggle security measures based on real-time system conditions, avoiding unnecessary overhead.
• Open-Source Implementation: The system is implemented on top of vLLM (a state-of-the-art serving framework) and is designed to be open-sourced.

4. Evaluation Results

The authors evaluated CacheSolidarity on an NVIDIA A100 GPU using various LLMs (ranging from 0.5B to 13B parameters) and diverse multi-tenant workloads.

• Performance Gains:
  • Compared to User-level Isolation (the current secure baseline), CacheSolidarity achieves up to 70% higher cache reuse and 30% lower inference latency.
  • Compared to Unprotected APC, CacheSolidarity maintains performance within 5–10% (depending on the workload) while providing security.
• Overhead:
  • Latency: Adds only 0.007 ms per request (0.004 ms for Detector, 0.003 ms for Activator).
  • Memory: Adds 32 bytes per cache entry.
• Security Validation:
  • In "prompt-stealing" attack simulations, the unprotected system showed clear TTFT spikes when the attacker guessed the secret correctly.
  • Under CacheSolidarity, the attacker's TTFT remained uniform across all attempts, effectively closing the side channel and preventing secret reconstruction.

5. Significance

CacheSolidarity represents a paradigm shift in securing LLM infrastructure. It demonstrates that security and performance are not mutually exclusive in multi-tenant LLM serving. By moving from coarse-grained user isolation to fine-grained, context-aware prefix isolation, the system allows benign users to benefit from shared caching (solidarity) while neutralizing malicious actors. This approach enables high-throughput, low-latency LLM services to be deployed securely in public, multi-tenant environments without the prohibitive costs of previous defense mechanisms.