Promising Multi-Granularity Linguistic Steganography by Jointing Syntactic and Lexical Manipulations

Chengfu Ou, Lingyun Xiang, Yangfan LiuAAAI 2025 · DOI

Abstract

Linguistic steganography hides secret data within natural language text. Existing modification-based methods typically operate within a single linguistic dimension—either syntactic or lexical—limiting their embedding capacity and often compromising semantic integrity. This paper introduces Multi-granularity Modification-based Linguistic Steganography (MMLS), a framework that simultaneously manipulates sentence structure and word choice. By utilizing Distance-Aware Syntactic Bins (DBC) for structural transformation and BERT-based Huffman coding for lexical substitution, MMLS achieves a significant increase in bits-per-word (bpw) while maintaining high semantic similarity and robust security against modern steganalysis.

Introduction

Linguistic steganography is the practice of embedding secret messages into ordinary text to facilitate secure communication. Traditional modification-based linguistic steganography (MLS) methods generally focus on a single "space": they either perform lexical substitution (swapping words for synonyms) or syntactic transformation (rearranging sentence structures).

However, these single-granularity approaches face a "capacity ceiling." Increasing the data load in lexical methods often results in robotic, semantically distorted text, while syntactic methods are constrained by the limited number of valid structural variations for a given sentence. Furthermore, many existing syntactic methods rely on random template assignments, which can lead to "hallucinated" sentences that are easily detected by AI-based steganalysis tools. MMLS addresses these issues by layering syntactic and lexical manipulations to maximize capacity without sacrificing naturalness.

Methodology

The MMLS framework employs a three-stage pipeline to embed information across multiple linguistic granularities.

The MMLS framework architecture, illustrating the Syntactic Transformation, Lexical Substitution, and Consistency Checking units.

1. Syntactic Transformation Unit

To avoid the semantic distortion common in random template selection, MMLS utilizes a Distance-Aware Syntactic Bins (DBC) strategy. Using spectral clustering, the system groups structurally similar syntactic templates into bins. When embedding data, the system selects a template from a bin corresponding to the secret bit sequence. This ensures that the generated paraphrase, produced by a syntax-controlled model (SI-SCP), remains structurally and semantically close to the original cover text.

2. Lexical Substitution Unit

Following structural transformation, the system identifies candidate words for replacement. It leverages a pre-trained BERT model to suggest contextually appropriate synonyms. To embed further data, these synonyms are mapped to binary strings using Huffman coding. An autoregressive encoding approach is used, where BERT considers previously modified words to prevent contextual clashes and maintain sentence coherence.

3. Consistency Checking Unit

In the final phase, the system generates multiple candidate steganographic texts. These candidates are filtered based on their adherence to the target syntactic template and their "semantic distortion" relative to the original text. Only the highest-quality candidate is selected as the final steganogram.

Experimental Setup

The researchers evaluated MMLS using the QQP-Pos dataset (Quora Question Pairs). The paraphrase generator was trained on 140,000 samples, with 3,000 samples reserved for testing. MMLS was compared against several state-of-the-art baselines, including HISS (syntactic-only), SPLS (lexical-only), and PhraseLS (rule-based).

Results and Discussion

Performance comparison of MMLS against various baseline methods across capacity, quality, and security metrics.

Capacity and Quality

As shown in the experimental results, MMLS significantly outperforms single-granularity methods in embedding capacity. It achieved a rate of 0.6305 bits-per-word (bpw), nearly doubling the capacity of baselines like HISS (0.3332 bpw) and LSCD (0.3327 bpw). Remarkably, this increase in capacity did not come at the cost of quality; MMLS maintained a Semantic Similarity (SIM) score approximately 5% higher than competing methods, indicating superior preservation of the original meaning.

Security

The security of MMLS was tested against modern steganalysis tools, such as the TS-RNN detector. MMLS demonstrated lower detection accuracy (Acc) and F1 scores compared to other high-capacity methods. This suggests that the multi-granularity approach produces text that is more difficult for automated systems to distinguish from natural, non-steganographic text.

Conclusion

MMLS represents a significant advancement in linguistic steganography by demonstrating that syntactic and lexical manipulations are complementary rather than mutually exclusive. By jointing these granularities through similarity-based binning and context-aware substitution, the framework achieves record-breaking capacity while enhancing both semantic naturalness and security. Future work will focus on reducing the computational complexity of the multi-model pipeline and exploring more sophisticated syntax-based coding strategies.

Summary updated

BibTeX
@inproceedings{ou2025promising,
  author = {Chengfu Ou and Lingyun Xiang and Yangfan Liu},
  title = {{Promising Multi-Granularity Linguistic Steganography by Jointing Syntactic and Lexical Manipulations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i23.34682},
}
Figure