Look Who’s Talking Now: Covert Channels From Biased LLM s (2024)

Abstract: Large language model-based steganography encodes hidden messages into model-generated tokens. The key tradeoff is between how much hidden information can be introduced and how much the model can be perturbed. To address this tradeoff, we show how to adapt strategies previously used for LLM watermarking to encode large amounts of information. We tackle the practical (but difficult) setting where we do not have access to the full model when trying to recover the hidden information. Theoretically, we study the fundamental limits in how much steganographic information can be inserted into LLM-created outputs. We provide practical encoding schemes and present experimental results showing that our proposed strategies are nearly optimal.

## introduction steganography is the art of hiding information within other non-secret text or data, commonly referred to as covertext. this technique ensures that only someone with the appropriate decoding key can access the hidden information, thus providing a layer of security. initially used in historical contexts for espionage and secret communications, steganography has evolved with technological advancements. when coupled with large language models (llms), steganography embeds hidden information into text generated by these models. our approach is to bias the output distribution of the llm in order to allow for the encoding of the hidden message (the stegotext). however, in order to maintain secrecy, we bound the maximum bias allowed for each sampled token. we study the central challenge for such techniques: the tradeoff between the secrecy of the scheme, which is usually measured in terms of how statistically similar the stegotext and the covertext are, and how much information can be communicated by the stegotext. to recover the stegotext, we must use a decoding function. one key aspect of our work is that we do not necessarily assume that this function has access to the underlying llm. instead, we consider the following two scenarios: (i) the llm is only accessible during encoding, (ii) the llm is accessible during encoding and a quantized version of the model is accessible for the decoding. we also consider a third scenario where the encoder and decoder both have access to the same model and show that under this (much simpler) setting, nearly optimal steganogographic schemes exist. we assume in all three cases that the encoder always initially samples from the unquantized llm before potentially biasing its output distribution. our contributions are the following. first, we introduce a simple encoding model whose structure is an extension of previous techniques used in watermarking, but with the goal of encoding larger quantities of information. we propose encoding schemes for each of the three scenarios and evaluate these in light of theoretical bounds we develop. experimentally, using data extracted from several large language models, we show that when the maximum bias is at least two, positive information rate schemes are achievable, and that in many cases, our schemes empirically appear to approach the optimum information rate. ## related works we briefly present some related work, predominantly focusing on steganography and watermarking with large language models. ## problem formulation a language model is a function f that accepts as input a sequence of tokens x (-np) , . . . , x (t-1) . this sequence can be partitioned into two disjoint subsequences consisting of: (i) the prompt x @xmath0, . . . , x (-1) ), and (ii) the sequence x t-1 = (x (1) , . . . , x (t-1) ), which is the first t -1 tokens previously produced by the model. given the input (x p , x t-1 ), the model outputs a vector of v logits, one for each word of the vocabulary @xmath1. these logits are passed into a softmax function producing a distribution over v. the next token at time t is then sampled according to the resulting distribution. we refer to the probability that the t-th token is equal to the k-th element from the vocabulary v as p (t) k and represent the distribution at time t as the vector p for inputs x (-np) , . . . , x (t-1) , f outputs f (x p , x t-1 ) = p (t) . for a distribution @xmath2, p 2 , . . . , p v ) over the set of tokens, we use the notation z ∼ p to denote the fact that z is sampled from the distribution p so that the probability that z is equal to the k-th token is p k if z ∼ p. recall x @xmath3, x (-np+1) , . . . , x (-1) is our input prompt. our goal is to develop an embedding function denoted f that can hide a message in the tokens produced by the llm. to obtain the hidden message, we also need an efficient decoder d. for a given a binary message to be hidden @xmath4, 1} m and a starting prompt x p , the embedding function and decoder must satisfy a pair of properties detailed below. let y 1 ∼ f (x p , u) and recursively define y t as requirements. we have two requirements: the first condition ensures that we can recover our information bits with vanishing levels of error. the second condition seeks to ensure f makes the generated stegotext similar to the covertext. the level of similarity is controller by the parameter β. we will study the properties of β in the following. approach. we use a simple strategy to encode the binary information from u into the tokens. at each generation step, we partition the token vocabulary into two parts, so that the tokens in one part represent 1, and the others represent 0. since we do not directly control the choice of next token, to make it more likely a token from the correct part (the one representing the next bit of u we wish to hide), we bias the probabilities of tokens in this part. this makes it easier to achieve reliability. however, to meet the security property, we can only bias up to a level β. in some scenarios, this will lead to a decoding error probability that is too high (violating reliability). to account for this case, we first encode u with an error-correcting code, which protects against such errors. however, by coding, we may sacrifice efficiency (so that we may need many more tokens to hide a message compared to its length). we address this tradeoff next. ## insights and methods in order to achieve our goals, we must (i) select a partition function and (ii) choose an errorcorrecting code that help us meet the two properties and maximize information rate. in this section, we first obtain some insights into the properties of our problem to help us with these tasks. equipped with these, we propose a family of partition function techniques and make our choice of error-correcting code. we defer proofs and a full set of theoretical results (including a coding-theoretic analysis on the maximum rate of an (n, m, β)-stego code and an achievability argument) to the appendix. we begin by considering the effect that β (the maximum bias in the security property) has on the the relationship between our biased and unbiased language model distributions. a simple result (lemma 1), stated in the appendix, helps us understand the behavior of d p (t) ||p (t) , the kl divergence between the original and biased distributions. we illustrate this quantity as a function of p (0) in figure 1 . we observe some trends. first, for a fixed β, d(p (t) ||p (t) ) is symmetric about the point p 0 = foot_0 2 . this is intuitive, as p 0 = p 1 = 1 -p 0 results in the same partition (with a reversal of the labels of the parts). as expected, the kl divergence grows as a function of β except in the interval near 1 2 . in particular, when p 0 ∈ ( 1 3 , 2 3 ), the kl-divergence does not depend on β, which implies that a key ingredient are partition functions that produce p max close to 1 2 . more concretely, notice if we can develop partition functions that guarantee with high probability p 0 lies within a small range around 1 2 , then there is no need to use larger values of β. our second insight comes from our development of upper bounds on the achievable rate of an (n, m, β)-stego code (theorem 1 in the appendix). the maximum rate is reached whenever βp (t) @xmath5. this is intuitive, as when βp (t) @xmath6, we can deterministically bias the tokens in such a manner that we are guaranteed to extract the correct part for each output token. one of the challenges which we will encounter, however, is that the behavior of p (t) max is highly variable, and it can fluctuate significantly between 1 2 and 1. this motivates our error-correcting code approach: we allow a certain number of tokens to be incorrectly sampled and then rely on the properties of c to correct the incorrectly sampled tokens. ## experimental results we evaluated the performance of our coding schemes, focusing on determining the highest achievable information rate given a fixed level of bias. figure 5: kl divergence of hga and hash. setup. we use opt-1.3b with prompts from the c4 dataset's realnewslike subset where 200 output tokens are generated per prompt @xcite . to address both scenarios, we simulated the performance of two code designs: the hash function at time t is seeded with the output token from time t -1 or the last token of the input prompt when @xmath7. (du) 2. hash greedy ascending (hga): the function f t is constructed using a two step labeling process that relies on a combination of a hash function along with a simple greedy algorithm as described in section 4.1. (di) in order to accommodate the length of our ldpc code, we coded across a sequence of outputs taken from various prompts. since under our setting there are 200 tokens per output prompt, our codewords were embedded in the concatenation of 64800 200 = 324 prompts. for both the hash and hga settings, the decoding is straightforward. for hash, we simply use the previously generated token to recover the hash. once we know f t , the recovery process amounts to decoding an ldpc code over a channel whose llrs are given by (3). similarly, for hga, we use the quantized version of the model to determine f t and then perform decoding. to determine the highest information rate, we let β vary from 1 to 7. we encoded up to 100 codewords and if each of the 100 codewords was recovered error-free, we consider the rate of the resulting code achievable. ## conclusion we studied large language-model based steganography with the goal of maximizing the amount of information that can be hidden in llm generated text. we studied the fundamental limits of this problem and proposed simple techniques that are close to optimal, including in challenging settings where, when decoding, we do not have access to the decoder, or only to a quantized version. zachary ziegler, yuntian deng, and alexander rush. 2019. neural linguistic steganography. in proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (emnlp-ijcnlp), pages 1210-1215, hong kong, china. association for computational linguistics.