I Know What You Asked: Prompt Leakage via KV-Cache Sharing in Multi-Tenant LLM Serving

I Know What You Asked: Prompt Leakage via KV-Cache Sharing in Multi-Tenant LLM Serving

Speakers: Guanlong Wu

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=4TXYdFv8NdQ

Overview

This talk, presented by Guanlong Wu from Southern University of Science and Technology (SUST), uncovers a critical vulnerability in multi-tenant Large Language Model (LLM) serving systems: prompt leakage via KV-cache sharing. The research, a collaboration with graduate students from SUST and colleagues from Bytedance, identifies a novel side channel attack that exploits the memory optimization techniques commonly employed in LLM inference engines. Specifically, the attack targets the Key-Value (KV) cache, a component designed to store intermediate computations for efficiency, and the scheduling policies that govern its use across multiple users.

The core problem arises when multiple users share the same GPU resources and the LLM serving system attempts to optimize performance by sharing common prefixes in their prompts within the KV cache. While this shared caching mechanism significantly boosts inference speed and reduces memory footprint, the researchers demonstrate how an adversary can meticulously observe the system's behavior—specifically, the prioritization of requests—to infer the exact prompts or parts of prompts being used by other users. This capability has significant implications for data privacy and the security of sensitive information processed by multi-tenant LLM services, ranging from intellectual property in specialized prompts to personal data.

The significance of this work lies not in targeting specific deployed systems, but in systematically studying and characterizing a fundamental security flaw inherent in a widely adopted optimization strategy. By detailing the attack methodology, evaluating its effectiveness under various conditions, and proposing concrete mitigation strategies, the researchers provide crucial guidance for developers and designers of LLM serving frameworks. Their findings underscore the need for careful security considerations when implementing performance optimizations in shared AI infrastructures, highlighting that what appears to be a benign system optimization can inadvertently create a potent information leakage channel.

Background

▶ Watch: Introduction: LLM inference and KV cache memory problem (0:00)

Large Language Models operate recursively, generating output tokens one by one, where the output of a previous iteration often becomes part of the input for the next. At the heart of this process lies the attention mechanism, which requires computing Key (K) and Value (V) vectors for each token. This computation is highly intensive, representing the most demanding part of LLM inference. To mitigate this computational overhead and improve throughput, modern LLM serving systems universally adopt a KV-cache mechanism. This technique, a classic space-for-time optimization, stores previously computed KV vectors, allowing them to be reused in subsequent iterations without re-computation.

However, the KV-cache itself can become a significant memory bottleneck. For instance, in a Llama 2 7B model processing a prompt of merely 128,000 tokens, the model weights might occupy only 17% of the GPU memory, while the KV-cache for the prompts consumes the majority of the remaining memory. This substantial memory footprint necessitates further optimization, leading to the adoption of KV-cache sharing across different user requests. The idea is that if two users submit requests with sufficiently similar prefixes, the common part of their KV vectors can be stored once and shared, reducing redundant computation and memory usage. A critical restriction for this sharing to occur is that the prefixes must be exactly the same. If a single token differs, even a seemingly innocuous word like "please" inserted into a prefix, the KV-cache cannot be shared for that common segment.

The architecture of typical LLM inference systems involves several key components. End users send requests to the LLM server engines. The first component to handle these requests is the Query Scheduler, which, much like schedulers in operating systems, determines the order in which requests are processed. Different LLM serving engines may implement varying scheduling policies. The researchers specifically studied SGLAN, a popular LLM serving system known for its longest prefix matching policy. This policy prioritizes requests that have the longest matching prefix with data already present in the KV-cache, aiming to maximize KV-cache reuse. Following scheduling, the Batch Handler groups requests into batches for parallel processing, often employing dynamic batching algorithms that allow new batches to start before previous ones are fully completed. Finally, the LLM Handler performs the actual inference and manages the KV-cache. SGLAN, in particular, utilizes a radix tree structure for its KV-cache, which enables highly efficient management and fast lookup of token KV entries, making it a prime target for side-channel analysis due to its predictable behavior.

Key Findings

▶ Watch: SGLAN architecture: longest prefix matching and Radix tree (2:10)

The central discovery of this research is the identification and demonstration of a novel prompt leakage side channel in multi-tenant LLM serving systems, specifically exploiting the interaction between KV-cache sharing and predictable query scheduling policies. The attack allows an adversary to reconstruct parts or even entire prompts of other users sharing the same GPU resources.

The fundamental mechanism of the attack hinges on the adversary's ability to infer whether KV-cache sharing has been triggered for a specific prefix. When a victim user's prompt is stored in the KV-cache, and the attacker sends a request with a prefix that exactly matches a segment of the victim's prompt, the system's longest prefix matching policy (as found in SGLAN) will prioritize the attacker's request. By carefully crafting requests and observing the order and timing of responses, the attacker can deduce which of their candidate prefixes resulted in prioritization, thereby revealing a segment of the victim's prompt.

The attack operates in a token-by-token extraction manner. An attacker, having identified a partial prefix, uses a local LLM (which only needs to share the same tokenizer as the target system, a non-secret component) to predict plausible next tokens. For example, if "imagine you are" is known, candidates like "imagine you are n", "imagine you are a", or "imagine you are d" are generated. The attacker then strategically injects these candidate requests, along with specially designed "dummy" requests (e.g., using an impossible token like "%"), into the system. The dummy requests serve to fill the query queue and establish a baseline for comparison. The system's scheduler, guided by the longest prefix matching, will then process requests in an order that reveals which candidate matched a victim's KV-cache entry. The attacker observes this order to confirm the correct token.

The researchers identified three distinct attack scenarios:

1. Unknown Prompt: The attacker knows nothing about the victim's prompt and must infer it token by token from scratch. This is the most general and challenging scenario.
2. Known Template (Cloze Test): The attacker knows the general structure or template of the victim's prompt but needs to extract sensitive information used to fill in the blanks. This is akin to a cloze test, where the attacker focuses on specific, variable parts of the prompt.
3. Unknown Template: The attacker knows the input content provided by the victim but does not know which specific prompt template the victim is using. The goal here is to learn the template itself, which can be valuable in understanding how an application generates its prompts.

The effectiveness of the attack is influenced by several factors, including the GPU memory capacity (larger memory allows for longer prompt extraction before the cache fills), the number of concurrent users (too many users, exceeding ~250, can reduce the attack's reliability), and the attacker's batch size (a trade-off between attack reliability and the risk of prematurely filling the KV-cache). The attack, while powerful, is acknowledged by the researchers as "fragile," meaning its success is highly dependent on specific system configurations and scheduling policies. The cost of the attack, measured by the number of candidates needed to infer a token, was found to be less than 10 candidates for most tokens, though some proved harder to guess.

Technical Deep Dive

▶ Watch: Attack overview: leveraging KV-cache sharing for leakage (4:00)

The KV-cache prompt leakage attack hinges on exploiting specific architectural and algorithmic choices within multi-tenant LLM serving systems. A detailed understanding of these components is crucial to grasp the attack's mechanics.

KV-Cache and Attention Mechanics:

In transformer-based LLMs, the attention mechanism is fundamental. For each input token, the model computes a query (Q), key (K), and value (V) vector. When generating an output token, the query vector of the current token is compared against the key vectors of all preceding tokens to determine their relevance (attention scores). These scores are then used to weight the value vectors, producing the context vector for the current token. The KV-cache stores the K and V vectors of previously processed tokens. Instead of recomputing K and V for every token at each generation step, the system retrieves them from the cache, significantly speeding up inference. As noted, this cache can consume a substantial portion of GPU memory, making KV-cache sharing an attractive optimization. When multiple requests share a common prefix (e.g., "Imagine you are an IT expert and tell me how to install"), the K and V vectors for this prefix can be computed once and stored in a shared segment of the radix tree, accessible by all requests using that prefix.

SGLAN's Architecture and Vulnerabilities:

The researchers focused on SGLAN, a popular open-source LLM serving system, because its specific design choices create the exploitable side channel. SGLAN's key components are:

1. Query Scheduler: This component determines the order of requests. SGLAN implements a longest prefix matching policy. This means if a request's prefix matches a longer sequence of tokens already present in the KV-cache, it receives higher priority. This policy is the cornerstone of the attack, as it creates a measurable difference in processing order based on KV-cache hits.
2. Batch Handler: SGLAN uses dynamic batching, where requests are grouped and processed in parallel. The attacker leverages this by sending multiple crafted requests in batches.
3. LLM Handler: Manages the LLM inference and, critically, the KV-cache. SGLAN's KV-cache is structured as a radix tree. This data structure is highly efficient for prefix-based lookups and insertions, making it ideal for KV-cache sharing. However, the deterministic nature of how the radix tree is traversed and how matches are identified directly feeds into the predictability of the longest prefix matching scheduler.

Token-by-Token Prompt Extraction:

The attack proceeds iteratively to reconstruct the victim's prompt one token at a time:

1. Initial State: A victim user sends a prompt (e.g., "Imagine you are an IT expert and tell me how to install Windows") to the LLM server. The KV-cache stores the K and V vectors for this prompt, organized within SGLAN's radix tree structure.
2. Attacker's Goal: The attacker aims to discover the next unknown token in the victim's prompt. Let's assume the attacker has already learned "Imagine you are an". The next token could be "IT", "a", "d", etc.
3. Candidate Generation: The attacker uses a local, auxiliary LLM. This model doesn't need to be the same as the target LLM, but it must share the same tokenizer. Tokenizers are generally not considered secret and are often publicly available, even for closed-source models. The local LLM predicts several plausible next tokens given the known prefix. For "Imagine you are an", candidates might be "Imagine you are an IT", "Imagine you are an experienced", etc. The attacker also generates "dummy" requests, using an unlikely or impossible token (e.g., "Imagine you are an %").
4. Strategic Batching and Submission:

• Batch 1 (Dummy Requests): The attacker first sends a batch of dummy requests (e.g., "Imagine you are an %"). These requests serve two purposes: to establish a known entry in the attacker's own KV-cache (for the prefix "Imagine you are an %") and to partially fill the query queue.
• Batch 2 (Candidate Requests): Subsequently, the attacker sends a batch containing the candidate requests (e.g., "Imagine you are an IT", "Imagine you are an experienced").
• Batch 3 (More Dummy Requests): Optionally, another batch of dummy requests can be sent to further manipulate the queue.

1. Scheduler Exploitation: The SGLAN Query Scheduler, with its longest prefix matching policy, now comes into play.

• If a candidate request (e.g., "Imagine you are an IT") perfectly matches a prefix within the victim's KV-cache entry (i.e., the victim's prompt actually contains "Imagine you are an IT"), this request will have a longer matching prefix with an existing KV-cache entry (the victim's) than other candidates or the initial dummy requests.
• Requests that match the attacker's own previously sent dummy requests will also show a long prefix match (e.g., "Imagine you are an %" matches "Imagine you are an %" in the attacker's KV-cache).
• The scheduler will prioritize requests that achieve the longest prefix match. By observing the order in which responses are returned, the attacker can deduce which candidate request was prioritized due to sharing with the victim's KV-cache. This reveals the correct next token.

1. Iteration and Cache Flushing: The attacker repeats this process token by token until the full prompt is extracted. However, the KV-cache has a finite capacity. If the cache becomes full, the attacker may no longer be able to reuse entries or infer new tokens. In such cases, the attacker might need to "flush" the entire KV-cache to start over with a new target prompt. This can be achieved either through a dedicated flush_cache function (if available, as in SGLAN) or by more complex, documented methods involving overwhelming the cache with new data.

Attack Scenarios in Detail:

• Scenario 1 (Unknown Prompt): The attacker starts with a minimal prefix (e.g., "I") and iteratively guesses subsequent tokens, building out the prompt. This requires more iterations and candidate evaluations.
• Scenario 2 (Known Template): If the attacker knows the general structure (e.g., "Summarize this document: [DOCUMENT_CONTENT]"), they can focus their candidate generation on the variable parts ([DOCUMENT_CONTENT]), making the attack more efficient and targeted.
• Scenario 3 (Unknown Template): The attacker might know a user is inputting "product review data" but not the template (e.g., "Analyze sentiment for: [DATA]" vs. "Extract key entities from: [DATA]"). The attack helps determine the template by observing which common prefixes are triggered.

The attack's success is a delicate balance. A larger attacker batch size makes the side-channel observation more reliable (fewer false positives) but also fills the GPU's KV-cache faster, potentially leading to attack failure. Conversely, a smaller batch size is less reliable but less likely to prematurely exhaust cache capacity. The number of concurrent users also plays a role; while some concurrency is needed for multi-tenancy, an excessively high number of users (e.g., over 250 in the evaluation) can introduce too much noise and unpredictability, reducing the attack's effectiveness.

Demo / Proof of Concept

▶ Watch: Token-by-token extraction: using dummy requests and order (4:45)

While the talk did not feature a live demonstration, the researchers conducted a comprehensive evaluation to serve as a proof of concept, systematically quantifying the attack's effectiveness and cost under various conditions. Their evaluation aimed to answer two primary research questions: "How effective is the attack?" and "What is the cost of each attack?"

To assess effectiveness, the researchers identified and varied three key factors:

1. GPU Memory Capacity: Unsurprisingly, the capacity of the GPU memory significantly impacts the attack's success. A larger GPU memory allows the KV-cache to store more KV vectors, meaning the attacker can extract longer prompts before the cache becomes full and requires flushing. The evaluation demonstrated a direct correlation between GPU size and the likelihood of extracting a full prompt.
2. Number of Concurrent Users/Requests: The level of concurrency in the multi-tenant system also plays a critical role. The study found that if the number of concurrent user requests exceeds a certain threshold (around 250 in their experiments), the likelihood of successfully extracting a full prompt begins to decrease. This suggests that while multi-tenancy is necessary for the attack, an overly saturated environment can introduce too much noise or contention, making the side channel harder to exploit reliably.
3. Attacker Strategy (Batch Size): The attacker's choice of batch size for their crafted requests presents a trade-off. A larger batch size generally makes the side-channel observation more reliable, leading to fewer false positives and a near 100% accurate detection of the KV-cache hit. However, a larger batch size also consumes GPU memory and fills the KV-cache more quickly, which can lead to the attacker failing to extract the full prompt because the cache is exhausted. The researchers highlighted this as a delicate balance an attacker must manage.

Regarding the cost of the attack, the evaluation focused on the number of candidate tokens required to infer a single correct token. The findings indicated that, for most tokens, less than 10 candidates were needed to correctly infer the next token in the victim's prompt. This suggests that the attack is relatively efficient in terms of the number of queries an attacker needs to send per token. However, the researchers also acknowledged that some tokens are inherently "harder to guess" than others, potentially requiring more candidates or iterations.

The evaluation served as a robust proof of concept, validating the theoretical underpinnings of the prompt leakage attack and providing empirical data on its practical feasibility and limitations. The detailed figures and additional analysis are available in the full research paper, which the speaker strongly encouraged interested individuals to read for a deeper understanding of the experimental results.

Defensive Implications

▶ Watch: Attack workflow: full extraction and flushing KV cache (6:45)

The research provides crucial insights for developers and operators of multi-tenant LLM serving systems, highlighting specific vulnerabilities and suggesting countermeasures. The speaker acknowledged that the attack, while potent, is somewhat "fragile" and highly dependent on specific system configurations and policies. This fragility also implies that relatively small changes to the system's design can significantly impact the attack's viability.

The primary defensive implication revolves around the query scheduling policy. The attack fundamentally exploits SGLAN's longest prefix matching policy, which deterministically prioritizes requests based on KV-cache hits. Modifying or replacing this policy can effectively neutralize the side channel. The researchers confirmed that they engaged with the SGLAN authors, who expressed significant interest in the findings and subsequently made changes to their scheduling policy. Specifically, SGLAN authors indicated a shift towards a random scheduling policy when the query queue is filled up. This change would introduce unpredictability, making it much harder for an attacker to reliably infer KV-cache hits by observing request prioritization.

Beyond specific scheduling policies, broader defensive strategies include:

• Isolation of KV-Cache: The most direct way to prevent this attack is to avoid sharing KV-cache segments across different users, especially for sensitive data. While this might negate some performance benefits, it guarantees strong isolation. Alternatively, implementing more granular access controls or encryption for KV-cache segments could be explored, though these are more complex to implement efficiently.
• Jitter and Noise Injection: Introducing random delays or non-deterministic elements into the request processing pipeline can obscure the timing and ordering signals that the attacker relies upon. This "noise" makes it difficult for the attacker to reliably distinguish true KV-cache hits from other system variations.
• Monitoring and Anomaly Detection: Systems could monitor for unusual patterns of requests, such as a single user sending many small batches of requests with varying prefixes, which might indicate an attempted side-channel attack.
• Careful Design of Multi-Tenancy: For LLM serving framework designers, the key takeaway is to deeply consider the security implications of performance optimizations. While KV-cache sharing is a powerful technique, its implementation must be carefully balanced against potential information leakage risks. The goal of this research was to provide guidance to avoid these problems in real-world deployments, not to target existing ones.

It's also important to note the practical difficulties for a targeted attack against a specific user. As highlighted in the Q&A, for such an attack to succeed, the adversary would likely need to be collocated with the victim on the same node or even the same GPU. This implies a need for privileged access or the ability to influence workload placement, making targeted attacks significantly more challenging to execute in practice, especially against robust cloud environments with strong isolation. However, the risk of a "random" prompt being leaked, where the attacker doesn't care whose prompt it is, remains a concern for general data privacy.

Key Takeaways

• KV-Cache Sharing Creates a Side Channel: Multi-tenant LLM serving systems that employ KV-cache sharing for performance optimization can inadvertently create a side channel vulnerability, allowing for the leakage of other users' prompts.
• Exploitation of Scheduling Policies: The attack specifically leverages deterministic query scheduling policies, such as "longest prefix matching" (found in SGLAN), to infer KV-cache hits and, consequently, parts of victim prompts.
• Token-by-Token Prompt Reconstruction: Adversaries can reconstruct prompts iteratively, token by token, by strategically crafting batches of candidate requests and observing the order in which the LLM serving system processes them.
• Factors Influencing Attack Effectiveness: The success and efficiency of the attack are influenced by GPU memory capacity, the number of concurrent users, and the attacker's chosen batch size, presenting trade-offs between reliability and resource consumption.
• Defensive Strategies Focus on Scheduling: Effective mitigations involve changing predictable scheduling policies (e.g., to random scheduling when queues are full) and implementing careful KV-cache management to prevent cross-user information leakage.
• Guidance for Framework Designers: This research serves as critical guidance for LLM serving framework designers, emphasizing the need to consider security implications alongside performance optimizations to prevent similar vulnerabilities in future deployments.

About the Speaker(s)

Guanlong Wu is associated with Southern University of Science and Technology (SUST). He presented this talk on behalf of the first author, who was unable to attend the conference. His work, as detailed in this presentation, involves collaboration with graduate students from SUST and colleagues from Bytedance, focusing on identifying and analyzing security vulnerabilities in large language model inference systems. His research contributes to understanding the security implications of performance optimizations in AI infrastructure.