Time Will Tell: Timing Side Channels via Output Token Count in Large Language Models
Tianchen Zhang Gururaj Saileshwar David Lie · 2024
Read Time Will Tell: Timing Side Channels via Output Token Count in Large Language Models by Tianchen Zhang Gururaj Saileshwar David Lie (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15431.txt.
Introduction
Tianchen Zhang, Gururaj Saileshwar, and David Lie reveal a timing leak in large language models in a 2024 paper. The number of output tokens in a reply can betray facts about the hidden input. Because models generate text one token at a time, an attacker can infer that count from response timing, even over a network.
The team builds attacks on translation and classification tasks. From timing alone, they recover the target language of a translation with high precision across three models. For classification, they leak the input class from both open models and a major commercial one. Precision passed seventy percent in both settings. The authors propose defenses at the tokenizer, system, and prompt levels to blunt the leak.
Catalog record
| CREATOR | Tianchen Zhang Gururaj Saileshwar David Lie |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-15431
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Time Will Tell: Timing Side Channels via Output Token Count in Large Language Models Tianchen Zhang Gururaj Saileshwar David Lie Abstract This paper demonstrates a new side-channel that enables an adversary to extract sensitive information about inference inputs in large language models (LLMs) based on the number of output tokens in the LLM response. We construct attacks using this side-channel in two common LLM tasks: recovering the target language in machine translation tasks and recovering the output class in classification tasks. In addition, due to the auto-regressive generation mechanism in LLMs, an adversary can recover the output token count reliably using a timing channel, even over the network against a popular closed-source commercial LLM. Our experiments show that an adversary can learn the output language in translation tasks with more than 75% precision across three different models (Tower, M2M100, MBart50). Using this side-channel, we also show the input class in text classification tasks can be leaked out with more than 70% precision from open-source LLMs like Llama-3.1, Llama-3.2, Gemma2, and production models like GPT-4o. Finally, we propose tokenizer-, system-, and prompt-based mitigations against the output token count side-channel. I Introduction Large language models (LLMs) [ 1 , 2 ] are gaining rapid adoption through web applications such as OpenAI’s ChatGPT [ 3 ] , Microsoft’s Copilot [ 4 ] , and Amazon’s Rufus [ 5 ] . The wide use of LLMs in our daily lives has been driven by their strong performance on tasks such as question-answer, code generation, translation, etc.. However, this also raises concerns about the ability of LLM-based applications to safeguard the privacy of users interacting with them. Previous work has demonstrated privacy breaches in machine learning systems using attacks such as membership inference [ 6 , 7 ] , training data extraction [ 8 ] , and prompt injection attacks [ 9 ] . More recently, researchers have also started to study privacy breaches via side-channels in LLMs, which leak information by monitoring only the metadata of responses [ 10 , 11 ] . For instance, [ 10 ] demonstrates that the size of the plaintext representation of each token (i.e. the token length) can be used to recover the contents of LLM messages. An LLM implementation that streams responses back token-by-token enables a network adversary to recover such token lengths and statistically guess the content of the responses. Other work on side-channels has exploited performance optimizations in LLMs such as speculative decoding [ 12 ] , and shared semantic caches and KV Caches [ 11 ] to leak user prompts based on variations in packet sizes and execution time respectively. In this paper, we propose the first output token count side-channel in LLMs to leak information during inference. Our key observation is that applications based on LLMs, such as translation or text classification with explanation, can have variations in their output token counts based on private attributes, such as output language in translation or output class in classification. While some of these variations have been observed by others, such as biases in tokenizers due to resource-poor languages [ 13 , 14 ] ; others are newly discovered in this paper, such as natural biases in the explanation for a particular classification. In the case of the previously observed biases in languages, we are the first to take advantage of them to leak sensitive information. To record the output token count, we propose that an attacker can either rely on the LLM implementation to leak it, by observing the tokens streaming one at a time over a network, or by exploiting a newly proposed timing side-channel, that exploits the autoregressive mechanism that LLMs use to generate output to recover the number of output tokens. The autoregressive mechanism in LLMs generates each output token one at a time, with a constant time per token. This autoregressive generation is an inherent feature of all modern transformer-based LLMs [ 1 , 2 ] , making them all potentially vulnerable to this side-channel. An attacker can thus learn the number of output tokens by just measuring the time an LLM takes to respond to a query, as the autoregressive loop dominates the LLM response generation time. Moreover, as the length of the input prompt can also affect the length of the LLM output, we find that our attacks can be further improved by taking the input length into account, if it is available to the adversary. Fig. 1: Example of our side-channel attacks on text sentiment classification with an LLM. (a) For a given text input, the LLM outputs the classified sentiment and also provides an explanation that can vary in length. (b) Our token-count side-channel attack leaks the output class (sentiment) based on the bias in the output token counts, or by measuring the execution time, as a proxy for the output token count. Effectiveness of our Attacks. As LLMs exhibit biases in the token encoding efficiency across languages, using the output token count to compute the output token density (output-bytes/token) and output/input byte ratio, enables our attack to identify over 12 languages across three different multilingual models, Tower, M2M100, MBart50, with an average precision of 82.5%, 77.2%, 80.5% respectively. Moreover, languages with distinctive morphology, such as Chinese, Russian, Hindi, Korean, and Arabic, reach almost 100% precision. Similarly, our end-to-end remote attack over the network on AWS-server hosted models, using response times instead of token counts, has high average precision for Tower (83.2%), M2M100 (75.8%) and MBart50 (81.3%). We also observe that LLMs exhibit inherent bias in explanation lengths in a range of text classification tasks. For instance, as shown in Figure 1 , an LLM performing sentiment analysis and generating explanations may produce longer responses for one class over the other. When profiled at scale, we see that such biases exist in a task-dependent manner across tens of tasks in all LLMs we profile (Llama-3, Gemma2, GPT4). This bias enables an adversary observing output token counts to infer the output class of the classification task. Moreover, we show that these biases can be exacerbated if there is accompanying bias in the in-context few-shot prompting examples, which amplifies the output token count signal and increases our attack success rates by 15% on average. In this scenario, our output token side-channel attack has a success rate of 81.4% for Gemma2-9B, 72.3% for Llama3.2-3B, and 86.9% for GPT-4o. In the end-to-end timing attack, an attack on a Gemma2-9B model achieves a similar success rate of 79.7%, while a remote timing attack over the internet on production GPT-4o model, hosted on OpenAI servers, has 74.7% success rate. Summary of Contributions: 1. New Timing Side-Channel: We identify a new timing side-channel in LLMs due to variations in output token counts. These variations, correlated with task-specific sensitive attributes, can be exploited due to the autoregressive nature of LLMs, enabling attackers to infer private information using execution time measurements. 2. Demonstrate Tokenizer Bias is a Privacy Risk: We show that language-based differences in token density and output token counts can leak language preferences through our side-channel, reframing these biases as a privacy risk rather than solely a fairness issue. 3. Highlight Token-Count Bias in Text Classification: We demonstrate that inherent biases in the token