Revisiting the Robustness of Watermarking to Paraphrasing Attacks

We assume access to only generations from the watermarked model, with no access to model weights or its tokenizer. To decipher the green list, we use a simple counting-based algorithm similar to the ones used in prior work Zhao et al. (2023); Sadasivan et al. (2024). Specifically, we compare the relative frequencies of tokens in a corpus generated by the watermarked model against their relative frequencies in a corpus of human-written text. Tokens that exhibit a higher relative frequency in the watermarked corpus compared to the reference corpus are classified as green tokens. We present the detailed algorithm in Appendix A.

This approach is similar to the one proposed in a contemporaneous work Jovanović et al. (2024), where for each token, they compute two conditional probabilities: probability of a token given its preceding context in a watermarked corpus and the same probability in a base corpus. They investigate two scenarios for obtaining the base corpus: using a non-watermarked version of the same language model or using a different language model as a proxy for the base distribution. In contrast, our approach does not require access to the unwatermarked language model for the base distribution; instead, we derive our base distribution from the OpenWebText corpus.²²2 To demonstrate the robustness of our algorithm across different base distributions, we present additional results in the appendix, where we estimate the green list using the RealNewsLike subset of the C4 dataset Raffel et al. (2020). Furthermore, our approach assigns binary scores of 0 and 1 for tokens in the red and green lists, respectively. Please note that the green list once estimated using the algorithm can be used to launch paraphrasing attacks on a variety of downstream datasets (details in §4.1).

One can imagine that incorporating prior knowledge about green lists should be able to improve the efficiency of off-the-shelf paraphrasers to remove the watermark signal and evade detection. Since many paraphrasing models are also auto-regressive generative models Krishna et al. (2023); Lewis et al. (2020); Lin et al. (2021); Witteveen and Andrews (2019),

one can introduce an inverse watermarking signal into the generated text. Specifically, at every generation timestep, we subtract a small positive $\delta$ from the logits corresponding to tokens predicted to be in the green list.

We primarily consider two watermarking schemes that are designed and thought to be robust against paraphrasing, namely, the semantic-invariant robust (SIR) watermarking Liu et al. (2024) and watermarking with a fixed green list, which is referred as UNIGRAM WATERMARKING in a recent study that analyzes the robustness of this approach Zhao et al. (2023). We use the LLaMA-7B model Touvron et al. (2023) and apply the two watermark algorithms with hyperparameters of $\gamma=0.5$ (fraction of green tokens) and $\delta=2.0$ (value used to boost the logits for green tokens) for all results presented in the main paper. Additional results using the Pythia model and other watermark hyperparameter choices are presented in Appendix B.

To evaluate the watermarking schemes and their robustness to paraphrasing, we use $50$-token prompts from Wikipedia articles Foundation (2022) to generate $200$-token completions. (Note that this dataset is different from the one used to estimate the green list.) We consider the subsequent $200$ tokens from the Wikipedia articles as human-written text for comparison. Additionally, we present results on prompts from arXiv papers Cohan et al. (2018) and Booksum Kryscinski et al. (2022) dataset in the Appendix (§B.3) to demonstrate the effectiveness of our attack on generations using prompts from diverse domains.

The results for each attack setting are aggregated across $500$ generations from the LLM. We use the DIPPER paraphrasing model Krishna et al. (2023) and incorporate the knowledge of (estimated) green list tokens (as described in §3.2). To evaluate the detection accuracy of watermarking algorithms, we follow prior work and measure the True Positive Rate (TPR) at a low False Positive Rate (FPR) of 1% and 10%. The False Positive Rate is set to low values to avoid falsely accusing someone of plagiarism. We use the P-SP metric Wieting et al. (2022) to assess the semantic similarity of paraphrases, past work considers the semantics of the paraphrase to be preserved if the P-SP value exceeds 0.76 Krishna et al. (2023). Additionally, we assess the quality of produced text by calculating the perplexity (PPL) using LLaMA-13B, which we consider as an oracle model.

We show that with just as few as $200$K tokens, we can accurately predict whether a token belongs to green list (Figure 1). It may be unsurprising that one can decipher the fixed green list used in the UNIGRAM WATERMARKING, as also documented by Jovanović et al. (2024). However, is noteworthy and surprising that even semantic-invariant watermarking (SIR) scheme, which dynamically produces a green list (based on the embeddings of the context) is just as vulnerable.

While the SIR approach aspires to produce similar watermarking logits for similar contexts and dissimilar ones for dissimilar contexts, we discover that this is not the case in practice. In Figure 2, we plot the cosine similarity of the context embeddings vs the cosine similarity of the watermarking logits. Interestingly, we notice that the aspired notion of producing similar watermarking logits for only similar contexts holds true only for in-domain samples and breaks for out-of-domain (OOD) samples. For OOD samples, the produced watermarking logits are highly similar regardless of the similarity in contexts (Figure 2(b)), suggesting that the green lists in SIR are not as dynamic as previously believed and are susceptible to be deciphered. Our findings suggest that other (future) watermarking algorithms that use machine learning to generate the watermarking logits might suffer from similar generalization concerns.

From Figure 1, we can also observe that the vanilla F1 scores present an overly optimistic picture about the security of watermarking approaches. As discussed in §3.2, the vanilla F1 metric weighs in all tokens uniformly. This approach fails to account for the long tail of rare tokens—whose presence in green or red list is hard to predict—which (by definition) occur infrequently in practical application. However, tokens that are actually generated can be predicted far more accurately, as can be clearly seen through about a $50$% higher generation-based F1 score in Figure 1.

Finally, we present results showing how the two watermarking schemes hold up against paraphrasing attacks (Table 1). We notice that the default DIPPER attack reduces the performance of both watermarking schemes. For FPR of $1$%, it brings down the TPR to $88$% (from $99.3$%) for UNIGRAM-WATERMARK and to $45.5$% (from $93.3$%) for SIR. When we empower the attack with the knowledge of (estimated) green lists, the TPR values plummet to below $10$%, rendering the watermarking schemes unusable. Across all setups, we confirm that the quality of LMs (measured through PPL) and the semantic meaning of paraphrases (evaluated via P-SP scores) is largely preserved. Interestingly, our attack is slightly less effective for SIR than UNIGRAM-WATERMARK as our estimates for green lists are less accurate for SIR.