Linguistic Steganography Using Automatically Generated Paraphrases

Ching-Yun Chang, Stephen ClarkNAACL 2010

TL;DR

This paper introduces a novel method for linguistic steganography by automatically generating paraphrases to embed secret messages within text. They propose a system to check the grammaticality and meaning preservation of these paraphrases using Google n-grams and a CCG parser, aiming to achieve high imperceptibility crucial for steganography.

What Problem Does This Paper Address?

Steganography, the art of hiding information, traditionally focuses on media like images. Linguistic steganography, which hides information within text, faces a significant challenge: even small changes to text, like word substitutions, can easily introduce anomalies that are detectable by observers. This makes it difficult to achieve both high imperceptibility (undetectability) and a meaningful payload (amount of hidden information). Previous methods often struggled with maintaining natural language fluency and meaning. This paper tackles the problem of finding reliable and automatic ways to transform text for steganography without raising suspicion.

Methods

The core of the proposed method lies in using automatically generated paraphrases as a means of linguistic transformation. The authors leverage a paraphrase dictionary, automatically extracted from parallel corpora, to find potential substitutions for phrases within a cover text.

To ensure these paraphrases are suitable for steganography, they developed a two-pronged approach to check their grammaticality and meaning preservation in context:

  1. Google N-gram Method: This approach checks if the context surrounding a paraphrase has been frequently used on the web, as indicated by the Google n-gram corpus. The idea is that if a paraphrased sentence appears often in real-world text, it's likely grammatically correct and contextually appropriate. They define "context window pairs" and use a google-count function to assess their frequency.
  2. Syntactic Filter (CCG Parser): To enhance the accuracy of the n-gram method, they employ a Combinatory Categorial Grammar (CCG) parser. This parser analyzes the syntactic structure of the sentence before and after paraphrasing. The check ensures that words outside the substituted phrase retain the same CCG lexical categories, thus preserving the sentence's grammatical structure.

For embedding, they propose a method that segments the cover text into units. Each unit can embed a single secret bit. If a sentence within a unit is paraphrasable, it can be modified to represent a '1' bit; otherwise, it remains unchanged to represent a '0' bit.

Datasets

  • Penn Treebank (Section 00): Used as the source for cover text sentences for experiments and evaluation.
  • Paraphrase Dictionary: Generated by Chris Callison-Burch, this dictionary contains phrases and their automatically generated paraphrases.
  • Google N-gram Corpus: A large corpus of English text (over 1 trillion word tokens) used to assess the frequency and contextual appropriateness of paraphrases.
  • Human Judgement Corpus: A newly collected corpus of 500 paraphrased sentences, evaluated by human judges for grammaticality and meaning retention. This corpus was split into development (100 instances) and test (400 instances) sets.

Key Insights and Ideas

  • Paraphrases as a Viable Steganographic Tool: The paper demonstrates that automatically generated paraphrases can be a powerful and flexible tool for linguistic steganography, offering a new avenue beyond traditional synonym substitution or syntactic transformations.
  • The Trade-off is Real: A central theme is the inherent trade-off between imperceptibility and payload in steganography. Higher precision (fewer detectable anomalies) often comes at the cost of lower recall (fewer opportunities to hide information).
  • Context is King for Paraphrase Quality: The suitability of a paraphrase is highly dependent on its surrounding context. Simple word-for-word substitution is insufficient; a robust system must consider the broader sentence structure and meaning.
  • N-grams as a Proxy for Grammaticality: The Google n-gram corpus provides a surprisingly effective, albeit imperfect, proxy for judging the grammatical correctness and contextual appropriateness of paraphrases.
  • CCG Parser Adds Grammatical Rigor: The CCG parser acts as a valuable filter, significantly improving the precision of grammaticality checks by ensuring syntactic consistency.

Key Results

  • Google N-gram Method Performance:
    • Achieved high precision (up to 100% for 5-grams) but with a significant drop in recall as n-gram size increased.
  • Accuracy decreased with larger n-grams, but precision was more relevant for steganography.
  • CCG Parser Filter Performance:
    • When used after the Google n-gram method, it generally increased precision with a slight loss in recall.
  • The baseline accuracy for judging grammaticality was 61.5% (majority class).
  • The parser-based method achieved an accuracy of 68.3%, with precision of 67.4% and recall of 93.9%.
  • Human Judgement Agreement:
    • Judges showed higher agreement on grammaticality (42 out of 50 cases) than on meaning retention (34 out of 50 cases). This led the authors to focus evaluation primarily on grammaticality.
  • Payload Capacity: The proposed embedding method can achieve a capacity of 1 bit per sentence, comparable to other linguistic steganography methods.

Limitations and Future Work

  • Meaning Retention Evaluation: The authors acknowledge that their evaluation focused primarily on grammaticality due to unreliable human judgements on meaning retention. Meaning retention is crucial for imperceptibility and requires further investigation.
  • Cover Text Choice: The paper did not discuss the impact of choosing different types of cover texts. For instance, using a newspaper article as cover text might be problematic if the original is readily available for comparison.
  • Language and Transformation Suitability: The paper raises questions about whether certain languages are better suited for linguistic steganography or if some languages are more amenable to specific transformation types.
  • Evaluating Imperceptibility: The authors suggest that evaluating the imperceptibility of the steganography system itself, beyond just grammaticality, is a key area for future work.
  • Dictionary Properties: The proposed embedding method relies on specific properties of the paraphrase dictionary (e.g., paraphrases not appearing as phrases themselves). Further research into dictionary construction and its impact is needed.

Summary updated

BibTeX
@inproceedings{chang2010linguistic,
  author = {Ching-Yun Chang and Stephen Clark},
  title = {{Linguistic Steganography Using Automatically Generated Paraphrases}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
}
Figure