No Free Lunch in LLM Watermarking: Trade-offs in Watermarking Design Choices

Summary

This paper demonstrates that typical design choices in large language model (LLM) watermarking schemes result in significant trade-offs between robustness, utility, and usability. To navigate these challenges, this paper rigorously examines a series of straightforward yet effective attacks on prevalent LLM watermarking approaches and proposes practical guidelines and defenses to strengthen their security and practicality. Specifically, the robustness of existing watermarking, a desirable property to mitigate removal attacks, can make the systems susceptible to piggyback spoofing attacks, which makes watermarked text toxic or inaccurate through small modifications. By proposing a novel attack, it is further shown that using multiple watermarking keys can make the system susceptible to watermark removal attacks. Finally, it is identified that public watermark detection APIs can be exploited by attackers to launch both watermark-removal and spoofing attacks. The paper proposes a defense strategy leveraging techniques from differential privacy to effectively counteract spoofing attempts.

Strengths

The paper provides novel attack schemes for existing watermarking techniques and provides empirical evidence to support their claims, which help the community to better understand the tradeoff among the design of watermarking systems. In general, release detection API will always make the watermarking more vulnerable, and the proposed defense demonstrates an interesting connection to DP.

Weaknesses

One of the biggest weaknesses of this paper is that the proposed attacks mainly explore the drawbacks of existing literature in [11,14,33], and some of the tradeoffs described in the paper are tied to these algorithms or specific formulations, which are not fundamental to the watermarking problem itself. 1. The robustness issue discussed in Section 4 is mainly due to the specific definition of robustness Definition 3. As robustness is defined using editing distance, the piggyback spoofing attacks leverage the fact that we can significantly change the meaning of a sentence by editing very few tokens. One way to address this issue is to define robustness using the semantics of the generated text instead of editing distance. If the meaning of the text remains similar, the watermarking should still be detectable; otherwise, the watermarking should disappear if the edits dramatically change the meaning of the text. Conceptually, I believe that there should not exist a tradeoff between robustness and spoofing attack. Empirically, the authors could conduct additional experiments on the following semantics-based watermarking. I am curious to see if the proposed attacks still work for semantic-based watermarking. Liu, Aiwei, Leyi Pan, Xuming Hu, Shiao Meng, and Lijie Wen. "A semantic invariant robust watermark for large language models." ICLR 2024 Liu, Yepeng, and Yuheng Bu. "Adaptive Text Watermark for Large Language Models." ICML 2024 2. As shown in "Adaptive Text Watermark for Large Language Models," by adding watermarking using semantics, the ASR of a spoofing attack is quite low without using multiple secret keys. In addition, it is likely that the same prompt will generate text with similar semantics, leading to a similar biased watermarking pattern. Therefore, it would be hard to do watermarking removal using the proposed attacks. The authors are encouraged to provide more discussion regarding the applicability of their empirical findings to different types of watermarks.

Questions

I can imagine that similar issues discussed in the paper will also occur for watermarking images generated by the diffusion model. For example, the following two papers consider image watermarking removal using adversarial samples from the publicly available detection model. Saberi, Mehrdad, Vinu Sankar Sadasivan, Keivan Rezaei, Aounon Kumar, Atoosa Chegini, Wenxiao Wang, and Soheil Feizi. "Robustness of ai-image detectors: Fundamental limits and practical attacks." arXiv preprint arXiv:2310.00076 (2023). Jiang, Zhengyuan, Jinghuai Zhang, and Neil Zhenqiang Gong. "Evading watermark based detection of AI-generated content." In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pp. 1168-1181. 2023. This paper would greatly benefit from a thorough discussion of the differences and connections between these two problems by having a more thorough literature review.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

Limitations are addressed in Appendix A of the paper.

Summary

The paper details three different attacks on LLM watermarking, targeting watermark removal and spoofing: A1: spoofing by taking advantage of the robustness of the watermark A2: removal by taking advantage of multiple watermarking keys A3: removal by taking advantage of a public detector Attacks are followed by some guidelines/defenses.

Strengths

Attack A2 is very original (AFAIK). The proposed defense against A3 based on DP is interesting.

Weaknesses

W1. Relevance I have been a watermarking practitioner for years. I have never seen the following proposals: - Robust watermarking as proof of content authenticity (A1-Section 4) A robust watermarking detector distinguishes 2 hypotheses: H_0: content is not watermarked (by this technique and that secret key) H_1: content has been watermarked **and** potentially modified. So, I do not perceive A1 (Section 4) as an attack but more as a misunderstanding or a misuse of robust watermarking by the authors. I strongly disagree with Guideline #1 (line 206), which suggests lowering the robustness of robust watermarking. This hardly makes sense. The recommendation should be to combine two schemes: robust watermarking and fragile (digital-signature-based) watermarking. Robust watermarking for authenticity is wrong. Fragile watermarking for IA-gen detection is wrong as well. - Watermarking detectors should be public (A3-Section 6) This leads to oracle attacks well documented in the watermarking literature of the 200s (nowadays called black-box attacks). The authors study even the easiest case where the attacker observes a soft decision (Z statistics): he can observe if any single modification lowers the detection score. A harder and more relevant case would be a Yes/No decision. But I am not even recommending that setup for security reasons. In short, the novelty (the attack against a specific LLM watermarking) is narrow. "*It is still an open question whether watermark detection APIs should be made publicly available*". It is not an open question, and the conclusion of this section is absolutely not a surprise. W2. State-of-the-art The experimental setup considers 3 schemes with default parameters. Here default parameters mean parameters as appearing in the very first version of these papers. Yet, since then, we know that these choices were not adequate. - Use of Z-statistics. They have been shown to be suboptimal and inaccurate, leading to theoretical FPRs that are way off the empirical FPRs. I recommend using p-values (empirically validated). See "Three Bricks to Consolidate Watermarks for LLMs" from P. Fernandez. - The choice 'h=1' in KGW is not recommended (Needless to say that Unigram --where 'h=0'-- is even worse). Again, it leads to inaccurate FPR. Moreover, it is not secure (watermarking stealing attack). The question is whether your attack still holds with a larger h (with a proper hash function, not those implemented based on min of hashes). W3. Key management As far as A2 is concerned, I think the key issue is key management. The literature offers 2 flavors: randomly picking a key in a small key space (Kuditipudi) or using a hash of the previous tokens (Aaronson, Kirchenbauer). Section 5 only investigates the first option.

Questions

Q1. Attack A3. Section 6. The assumption is that the watermarked LLM provides the top-5 tokens. Although some LLM APIs like OpenAI provide this information, I have some doubts that a **watermarked** LLM would do this. Especially, what are the top-5 tokens for Exp? Are they computed before or after the Gumbel trick? Q2. I am a bit surprised that $\sigma = 4$ doesn't impact the detection performance. Without DP: I suppose that w/o watermark $Z\sim\mathcal{N}(0;1)$ and with watermark $Z\sim\mathcal{N}(\mu;1)$, with $\mu \approx 6$ (according to Fig. 3.a). With a threshold set to 4, this makes P_FP ~ 3e-5, P_TP ~ 0.98, for an accuracy of 0.99. With DP: The variances are now equal to $\sqrt{1+\sigma^2}$. This makes P_FP ~ 0.17, P_TP ~ 0.69, for an accuracy of 0.76.... Quite far away from what you get. More importantly, these two cases should be compared for a fixed P_FP so that the threshold with DP should be higher. Reporting only the accuracy is masking the fact that P_FP is way higher.

Rating

5

Confidence

5

Soundness

3

Presentation

2

Contribution

1

Limitations

The title and introduction discuss LLM watermarking in general, but the paper is based on three particular schemes. I agree that these three are the most well-known. It is questionable whether other more exotic schemes (like semantic-based) are also vulnerable. One may easily think of easy counter-attacks: forbidding querying the LLM with the same prompt repeatedly (or the same prompt plus one extra token), forbidding querying the detector with too similar text, etc.

Summary

In this work, the authors reveal new attack vectors including watermark-removal attacks and spoofing attacks that exploit common features and design choices of LLM watermarks. Besides, the authors propose a defense utilizing the ideas of differential privacy, which increases the difficulty of spoofing attacks.

Strengths

1. The research question in this paper is interesting and is a hot topic in the field of LLM watermark. 2. The paper is well-written. 3. The experimental data and results presented in this paper are extensive.

Weaknesses

1. In Sec 3.1, what are the differences between "piggyback" and "general" spoofing attacks? Specifically, what does "piggyback" refer to? 2. In Sec 3.1, regarding attacks on detection APIs, the reviewer is confused by the statement "the attacker can auto-regressively synthesize (toxic) sentences." What does this mean? 3. Regarding attacks discussed in Sec. 5, the attackers can discover watermarking rules by observing a large amount of watermarked text, thus enabling attacks. The original KGW paper in Sec. 5 mentions using a large context width h to defend against such attacks. However, this paper lacks explanation and discussion regarding the parameter h. 4. In the detection API attack, the description of the adversary's capabilities is unclear. In Sec 6.1, the authors assume the adversary can access the target watermarked LLM's API and query watermark detection results. This implies the adversary can generate watermarked text and obtain detection results for any given text. But why can the adversary generate a list of possible replacements for x_i? Does this mean the adversary can access the perturbed probability distribution and logits of tokens? If so, this seems to exceed the stated capabilities of the adversary. 5. There are some minor issues, such as the undefined notation "V^{\ast}" in the definition in Sec 3.

Questions

Please answer all points in the Weaknesses section.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors have adequately addressed the limitations.

Summary

This paper explores the vulnerabilities and trade-offs in watermarking schemes for large language models (LLMs). It highlights how common design choices in these schemes, aimed at ensuring robustness, multiple key usage, and public detection, make them susceptible to simple yet effective attacks. The authors demonstrate that robust watermarks, intended to prevent removal, can be easily exploited through piggyback spoofing attacks that insert toxic or inaccurate content while maintaining the watermark. Additionally, using multiple watermark keys to defend against watermark stealing inadvertently increases vulnerability to watermark removal attacks. Public detection APIs, while useful for verifying watermarked content, are shown to be exploitable for both removal and spoofing attacks. Through empirical evaluations on state-of-the-art watermarks (KGW, Unigram, Exp) and models (LLAMA-2-7B, OPT-1.3B), the study rigorously demonstrates these vulnerabilities and the resulting trade-offs between robustness, utility, and usability. The paper proposes potential defenses, including the use of differential privacy techniques in detection APIs, and offers guidelines for designing more secure watermarking systems. Ultimately, the study underscores the importance of carefully considering watermarking design choices to balance security and utility, calling for further research to develop robust defenses and optimize these trade-offs.

Strengths

+ The paper rigorously explores various common watermarking design choices and demonstrates their susceptibility to simple yet effective attacks. It highlights the fundamental trade-offs between robustness, utility, and usability, which are crucial for understanding the limitations of current watermarking methods. + The paper provides an insightful discussion of the inherent trade-offs in watermarking design, such as the balance between watermark robustness and vulnerability to spoofing attacks. This helps in understanding the complexities involved in creating effective watermarking. + The authors propose potential defenses and guidelines to enhance the security of LLM watermarking systems. These recommendations are valuable for practitioners looking to deploy more secure watermarking solutions in practice.

Weaknesses

+ The citation in Line 248 and Figure 2 is not correct. The authors are supposed to cite [1]. + Lack of discussions in the Publicly-Detectable Watermarking [2], which compromises robustness to defend against spoofing attacks. [1] Nikola Jovanovic, Robin Staab, and Martin Vechev. Watermark stealing in large language models. arXiv preprint arXiv:2402.19361, 2024. [2] Fairoze, Jaiden, et al. "Publicly detectable watermarking for language models." arXiv preprint arXiv:2310.18491 (2023).

Questions

+ How generalizable are the findings? Would the vulnerabilities and trade-offs identified apply to all types of LLMs, or are they specific to certain architectures or applications? + What are the limitations of the attack methods presented in this study? Are there scenarios where these attacks might not be effective? + Are there any practical considerations or potential drawbacks to implementing DP defense mechanisms in real-world systems?

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

See the weaknesses.