Practical Linguistic Steganography Using Contextual Synonym Substitution and Vertex Colour Coding

Ching-Yun Chang, Stephen ClarkEMNLP 2010

Introduction

Linguistic steganography is the art of concealing secret messages within innocuous-looking text. The primary challenge in this field is balancing payload (the amount of data hidden) with imperceptibility (the ability to evade detection by humans or algorithms). Traditional methods often produce unnatural-sounding sentences or struggle with polysemy—where a single word has multiple meanings—leading to decoding errors.

Presented at EMNLP 2010, Chang and Clark propose a robust framework that leverages massive web-scale data and graph theory to address these hurdles. Their approach ensures that synonym substitutions are contextually appropriate and that bit-assignments remain consistent across different word senses.

Methodology

Contextual Filtering via Google N-Grams

To maintain naturalness, the authors employ the Google Web 1T 5-gram corpus. When a word in a "cover sentence" is a candidate for substitution, the system calculates a "substitution score" based on the frequency of the potential synonym appearing with its immediate neighbors (2-grams through 5-grams) in over a trillion words of web text.

The process of identifying synsets and filtering out contextually inappropriate 'negatives' to maintain sentence naturalness.

If a synonym's score falls below a specific threshold, it is discarded as a "negative." This filtering prevents jarring substitutions, such as replacing "bridge" with "span" in the context of a "suspension bridge," which would otherwise signal the presence of hidden data.

Vertex Colour Coding for Bit Assignment

A significant problem in linguistic steganography is polysemy ambiguity. If a word belongs to multiple synonym sets (synsets), it might represent different bit strings in each. This makes decoding difficult for the receiver without complex word-sense disambiguation.

The authors resolve this by modeling the vocabulary as an undirected graph where vertices represent words and edges connect words sharing a synset. They apply a vertex coloring algorithm (using up to 4 colors), where each color corresponds to a specific bit string (e.g., Color 1 = 00). By ensuring no two adjacent vertices share a color, a word consistently represents the same bit string regardless of its active synset.

Example of a cover sentence transformed into a stego sentence by substituting synonyms to encode a secret bitstring (010).

Evaluation and Results

The system was evaluated using WordNet for synsets and the SemEval-2007 English Lexical Substitution Task as a gold standard for human-like synonym selection. Key findings include:

  • Accuracy: The n-gram filtering method achieved 68% to 74% accuracy across various parts of speech when compared to human annotations.
  • Capacity: The vertex coloring approach allowed the system to utilize 99.6% of WordNet synsets, a massive improvement over previous methods that discarded up to 70% of the database to avoid ambiguity.
  • Payload: At high imperceptibility thresholds, the authors estimate a payload of approximately 1 bit per newspaper sentence.

Discussion and Future Work

The research highlights a fundamental Precision-Recall trade-off: higher n-gram thresholds increase precision (imperceptibility) but decrease recall (payload). By tuning this threshold, users can balance security against data capacity.

While effective for single-word substitutions, the current framework does not yet address multi-word expressions or stylistic consistency. Future work aims to incorporate phrase-level paraphrasing and conduct extensive human "Turing Tests" to further validate the system's imperceptibility in diverse linguistic contexts.

Summary updated

BibTeX
@inproceedings{chang2010practical,
  author = {Ching-Yun Chang and Stephen Clark},
  title = {{Practical Linguistic Steganography Using Contextual Synonym Substitution and Vertex Colour Coding}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2010},
}
Figure