Analyzing and Evaluating the Robustness of Natural Language Watermarking

He Lu, Xiaolin Gui, Feng Tian, Rei-Feng Wu, Dingyi FangChinese 2012 · DOI

Abstract

This paper establishes a formal theoretical framework for evaluating the robustness of Natural Language Watermarking (NLW) against malicious editing. By proposing a standardized adversary model and classifying NLW techniques into spatial and transform domains, the authors demonstrate that while spatial-domain watermarks are highly vulnerable to "summary attacks" (deleting sentences), transform-domain spread-spectrum methods offer significantly better protection for hidden data. Experimental results validate the theoretical models, highlighting a critical "synchronization trap" in spatial methods and the resilience of statistical feature-based embedding.

Introduction

Natural Language Watermarking involves embedding hidden information into text—such as a digital signature or copyright notice—by making subtle, meaning-preserving changes to the prose. Unlike continuous signals like images or audio, text is discrete and highly sensitive to minor edits. While robustness analysis is mature for multimedia watermarking, it has been largely neglected for NLW. The authors identify a critical gap: the lack of a unified "adversary model" to test how well a text watermark survives malicious editing. Without such a model, researchers cannot objectively compare the durability of different watermarking algorithms.

Methodology

The Adversary Model

The authors define two primary types of attacks based on Kerckhoffs’ principle, assuming the attacker knows the algorithm but not the key:

  1. Substitution Attack: Replacing words or phrases with synonyms using the same NLP tools as the watermarker.
  2. Summary Attack: Using automated summarization software to delete "unimportant" or redundant sentences, a common method to strip information while preserving the text's value.

Classification of NLW Techniques

Algorithms are categorized into two domains:

  • Spatial Domain: Watermarks embedded based on the physical sequence of text units (e.g., T-Lex or syntax-tree-based methods).
  • Transform Domain: Watermarks embedded into statistical features, such as the frequency of specific Part-of-Speech (POS) patterns, which remain independent of the sentences' physical order.

Evaluation and Tooling

The authors developed AutoAttacker, a tool implementing three levels of summary attacks (SAI, SAII, SAIII) using Microsoft Word 2007's summarization features. They utilized corpora such as the Chinese novel Defense of Yan'an (保卫延安) to test transform-domain algorithms, analyzing 145 distinct POS-tagging patterns.

Key Results and Discussion

The Synchronization Trap

A primary insight of the research is the catastrophic failure of spatial-domain watermarks under summary attacks. Because these methods rely on the sequence of sentences, deleting a single sentence causes a "synchronization loss." The extractor subsequently looks for bits in the wrong locations, leading to a Bit Error Rate (BER) of approximately 50% (equivalent to random noise) almost immediately upon attack.

BER of spatial-domain watermarking under summary attacks, illustrating the immediate jump to 50% due to synchronization loss.

Transform Domain Superiority

By embedding data into the frequency of features rather than their position, transform-domain methods are immune to sentence reordering or deletion. While deleting a sentence may weaken the signal, it does not shift the watermark out of alignment. Experimental data shows that transform-domain methods maintain high correlation even after significant sentence deletions.

Correlation (Q) of transform-domain watermarking as a function of attack intensity a, showing sustained signal integrity compared to spatial methods.

Conclusion

The study proves that summary attacks are generally more efficient at destroying watermarks than synonym substitution. While spread-spectrum techniques can mitigate some substitution effects, they cannot resolve the synchronization issues inherent in spatial-domain methods. Future work will focus on developing better metrics to quantify semantic loss during attacks, ensuring that an attack is only considered "successful" if it preserves the readability and meaning of the original text.

Summary updated

BibTeX
@inproceedings{lu2012analyzing,
  author = {He Lu and Xiaolin Gui and Feng Tian and Rei-Feng WU and Dingyi Fang},
  title = {{Analyzing and Evaluating the Robustness of Natural Language Watermarking}},
  booktitle = {Chinese},
  year = {2012},
  doi = {10.3724/sp.j.1016.2012.01971},
}
Figure