Character-Level Perturbations Disrupt LLM Watermarks

Character-Level Perturbations Disrupt LLM Watermarks

Speakers: Zhaoxi Zhang

Conference: NDSS Symposium

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

Overview

This talk presents a systematic study demonstrating that character-level perturbations are significantly more effective at removing LLM watermarks than the token-level and sentence-level attacks previously studied in the literature. The researchers from the University of Technology Sydney, Griffith University, and MIT show that simple modifications like homoglyph substitution, typo insertion, and zero-width character insertion can disrupt the tokenization process, cascading damage through the watermark signal far more efficiently than word-level synonyms or paraphrasing.

Under two realistic threat models -- one with a private detector and one with a public detection API -- the character-level attacks consistently outperform token-level attacks across all tested watermarking schemes. The researchers further propose a genetic algorithm (GA)-based guided attack that leverages limited queries to a public watermark detector to identify optimal perturbation positions, and demonstrate that even defensive countermeasures like spell checking, OCR normalization, and Unicode cleanup fail to fully mitigate their compound character-level perturbation approach.

Background

▶ Watch: Introduction: why LLM watermark robustness matters (0:00)

As LLMs become increasingly capable, the risk of misuse for misinformation generation, automated phishing, and academic cheating has driven urgent development of AI-generated content detection methods. Existing detection approaches fall into two categories: statistical classifiers trained to distinguish human from AI writing (which suffer from training data bias and adversarial evasion), and LLM watermarking, which injects detectable features during text generation.

The most widely studied watermarking approach is logit-based watermarking. At each generation step, the vocabulary is randomly divided into a green list and a red list based on a key and pseudo-random function. A watermark bias is added to the logits of green-list tokens, making them more likely to be sampled. Detection works by counting the proportion of green-list tokens in a text sample -- watermarked text will have a statistically higher proportion than non-watermarked text.

The practical utility of watermarking depends entirely on robustness -- whether the watermark signal survives adversarial edits. Previous research has evaluated robustness against token-level perturbations (synonym substitution) and sentence-level perturbations (paraphrasing with another LLM), but character-level perturbations have been understudied despite the fundamental role of tokenization in LLM processing.

Key Findings

▶ Watch: Character-level perturbations and their cascading tokenization effect (4:00)

Character-level attacks consistently outperform token-level attacks across all watermarking schemes and editing rates. At the same editing distance, character-level perturbations influence more tokens and cause more severe watermark signal degradation.

Homoglyph substitution is the most effective single technique, consistently achieving the highest attack success rate (ASR) among character-level perturbations. Replacing a character with a visually identical Unicode homoglyph causes the tokenizer to fail to recognize the word, splitting it into multiple tokens and disrupting the watermark signal.

Cascading tokenization damage: The watermark signal assigned to each token depends on the previous token. When a character-level modification causes one token to be split into multiple tokens, the disruption propagates to subsequent tokens, creating a cascade effect that is more damaging than simply replacing one token with another.

GA-based guided attack with public detector significantly outperforms random perturbation placement. By training a reference detector that approximates the original detector using limited query responses, the attacker can identify optimal perturbation positions for maximum watermark removal.

Data augmentation dramatically improves reference detector fitting: Even a small amount of augmented data causes the reference detector to closely match the original detector's behavior, as demonstrated in scatter plots where points increasingly concentrate on the diagonal line.

Defensive countermeasures are insufficient: Spell checking, OCR, Unicode normalization, and anomalous character deletion only slightly reduce the compound attack's success rate, which remains higher than baseline GA attack performance.

Technical Deep Dive

▶ Watch: Why character-level attacks cause more damage per edit than token-level (6:00)

The research defines two system models reflecting realistic deployment scenarios:

System Model 1 (Private Detector): The watermark detector is accessible only to the model provider or authorized parties. The adversary has black-box access to the victim LLM with limited queries per input. Under this model, the researchers evaluate random editing attacks where token positions are randomly selected and perturbed with different perturbation types.

System Model 2 (Public Detector API): Anyone can submit text and obtain detection results. The adversary can query both the victim LLM and the public detector. This enables a stronger guided attack: the attacker collects detection results on watermarked and non-watermarked text, trains a reference detector that approximates the original, and then uses this surrogate to guide perturbation placement.

The genetic algorithm-based removal attack uses iterative optimization to identify token positions whose modification leads to the most effective watermark removal. The process:

1. Initialize a population of candidate perturbation configurations
2. Evaluate each candidate using the reference detector
3. Select the best-performing candidates
4. Apply crossover and mutation to generate new candidates
5. Repeat until convergence

The researchers also introduce a best-of-one attack (simplified GA without iterative optimization) as a baseline to isolate the contribution of the iterative optimization process.

Five types of character-level perturbations were evaluated: typo insertion, character deletion, character swapping, zero-width character insertion, and homoglyph substitution. The cascading effect is key to understanding their superior effectiveness: in a token-level attack, modifying one token affects the watermark signal of that token and the next token (due to dependency). In a character-level attack, inserting a single special character can split one token into multiple tokens, disrupting watermark signals for all resulting tokens plus propagating to subsequent tokens.

The compound character-level perturbation applies multiple types of character-level modifications at each selected position, making it resistant to any single defensive normalization technique.

Demo / Proof of Concept

▶ Watch: Genetic algorithm-based guided attack using reference detector (8:00)

The talk presented empirical results rather than a live demo. Results across all watermarking schemes showed character-level attacks achieving consistently higher ASR and watermark score dropping rates than token-level attacks at equivalent editing distances. The scatter plot visualization showing reference detector fitting improvement with data augmentation was particularly compelling -- with sufficient augmented data, the reference detector closely approximated the original detector's scoring behavior.

The compound attack results demonstrated resilience against all four tested defenses (spell checking, OCR, Unicode normalization, anomalous character deletion), with average ASR remaining above baseline GA attack levels even after defense application.

Defensive Implications

▶ Watch: Defensive countermeasures fail against compound perturbations (10:30)

This research delivers a sobering message for anyone relying on LLM watermarking as a content provenance mechanism. The finding that simple character-level modifications -- many of which are invisible to human readers -- can systematically defeat watermark detection challenges the viability of current watermarking schemes as a reliable AI content detection mechanism.

The most concerning defensive takeaway is that none of the tested countermeasures adequately address the compound attack. Spell checking catches some perturbations but misses homoglyphs and zero-width characters. Unicode normalization handles some homoglyphs but not all. The compound approach, which mixes multiple perturbation types at each position, is specifically designed to resist any single normalization strategy.

The speaker suggested during Q&A that the best defensive direction is to optimize the tokenization process to be more robust to special characters, minimizing the disruptive cascading effect. This would require fundamental changes to tokenizer design rather than post-hoc detection defenses.

Organizations deploying watermarking should treat it as one signal among many rather than a sole provenance mechanism. Multi-layered detection approaches combining watermarking with statistical classifiers and provenance metadata may provide more robust coverage.

Key Takeaways

• Character-level perturbations (homoglyphs, typos, zero-width characters) are far more effective at removing LLM watermarks than token-level substitution or sentence-level paraphrasing
• The cascading tokenization effect means a single character modification can disrupt watermark signals across multiple tokens
• Homoglyph substitution -- replacing characters with visually identical Unicode alternatives -- is the single most effective perturbation type
• A genetic algorithm-based guided attack using a reference detector trained from public API queries further amplifies attack effectiveness
• Compound perturbations mixing multiple character-level modification types resist all tested defenses including spell checking, OCR, and Unicode normalization
• Current LLM watermarking schemes should not be relied upon as the sole mechanism for AI-generated content detection

About the Speaker(s)

Zhaoxi Zhang is a PhD student at the University of Technology Sydney (UTS). The research was conducted in collaboration with co-authors from UTS, Griffith University, and MIT. The project website and GitHub reading list are available via QR code from the presentation slides.