Decipherment for Adversarial Offensive Language Detection

Zhelun Wu, Nishant Kambhatla, Anoop SarkarEMNLP 2018

TL;DR

This paper tackles the challenge of detecting offensive language online, which is often disguised by users to evade filters. The authors propose a novel approach using decipherment techniques, treating disguised messages as encrypted text and aiming to recover the original plaintext for more effective filtering. Their method shows promise in handling various obfuscation techniques, outperforming traditional spelling correction in many scenarios.

What Problem Does This Paper Address?

Online platforms are flooded with offensive language, including hate speech, cyberbullying, and inappropriate content. To combat this, automated filters are commonly employed. However, users intent on bypassing these filters can subtly alter their messages through various obfuscation techniques like misspellings, insertions, deletions, and substitutions (e.g., "leet speak"). These adversarial transformations make it difficult for traditional rule-based or machine learning classifiers to accurately identify offensive content. Existing methods, like simple spelling correction, are often insufficient against these sophisticated disguises. The paper aims to bridge this gap by developing a method that can "decode" these disguised messages, making them recognizable to existing filtering systems.

Methods

The core of the paper's approach is decipherment, framed as recovering an original plaintext message from a disguised ciphertext. They model the disguised messages as if they were encrypted using an invented cipher.

Key techniques include:

  • Modeling Disguises as Ciphers: The authors treat various forms of obfuscation (letter substitution, insertion, deletion) as a form of encryption.
  • NULL Insertion: For handling insertions and deletions, they introduce a method to identify potential positions for inserting "NULL" symbols to aid in segmentation and decipherment. This involves using character-level n-gram models to score potential NULL insertion points.
  • Hidden Markov Model (HMM) Decipherment: They employ an HMM-based decipherment model. In this model, the observed ciphertext characters are the "observations," and the original plaintext characters are the "hidden states." The model learns the substitution probabilities (cipher to plaintext) and uses a language model for the plaintext.
  • Expectation-Maximization (EM) Algorithm: The EM algorithm is used for unsupervised learning of the HMM parameters, specifically the substitution map.
  • Beam Search Decoding: To find the most likely plaintext from the deciphered ciphertext, they utilize an efficient beam search decoding algorithm. This method balances breadth-first search with pruning to reduce the search space.
  • Initialization Strategy: They propose an initialization algorithm for the EM training that leverages previously trained tables to potentially reach better local optima faster.

Datasets

The paper utilizes several datasets for training and evaluation:

  • Wiktionary Dataset: Created from English Wiktionary data, this dataset contains offensive and non-offensive sentences. It was used to train the language model and create a balanced dataset for training an offensive sentence classifier.
  • Europarl Corpus: A parallel corpus of English and German parliamentary proceedings was used to augment the language model, providing a larger source of English text.
  • English Gigaword Corpus: Used to train a word trigram language model for spelling correction.
  • Linux System Dictionary: Used in conjunction with the Gigaword corpus for training the spelling correction error model.
  • Real Chat Messages Dataset: A large dataset of unfiltered chat messages from a provider of filtering services for under-aged users was used to train a letter-based language model. A subset of these messages, flagged as offensive by a rule-based system, was used for testing.

Key Insights and Ideas

  • Adversarial Nature of Online Communication: The paper highlights that offensive language detection is inherently an adversarial problem, where users actively try to circumvent detection systems.
  • Decipherment as a Powerful Tool: Framing message obfuscation as a form of encryption and applying decipherment techniques offers a robust way to recover original intent, even with complex disguises.
  • HMMs Excel at Substitution: The HMM-based decipherment approach demonstrates a strong ability to recover messages encrypted with substitution ciphers (like Caesar and Leet speak), often matching the accuracy of the original, unencrypted text.
  • Limitations of Simple Spelling Correction: Traditional spelling correction methods, while useful for minor errors, struggle significantly with more complex, adversarial transformations that alter word structure beyond simple typos.
  • Language Models are Key: The effectiveness of the decipherment approach is heavily reliant on the quality of the language model used for the plaintext. Domain-specific language models can significantly improve performance.

Key Results

  • Caesar Cipher: For Caesar cipher encrypted text, the HMM decipherment approach achieved classification accuracies of up to 86%, matching the original plaintext accuracy. This indicates a near-perfect recovery of the intended message.
  • Leet Substitution Cipher: For Leet substitution, the HMM decipherment achieved an average classification accuracy of 82% across test sets, significantly outperforming noisy channel spelling correction (average 65%).
  • Real Chat Offensive Words Substitution: In this more realistic scenario, the HMM decipherment achieved accuracies of 77% (random NULL insertion) and 78% (n-gram based NULL insertion), outperforming Aspell (around 75% on average).
  • Real Offensive Chat Messages: The decipherment approach was able to transform about half (51.6%) of corrupted messages into a readable form that an older, rule-based filter could then flag as offensive, demonstrating its potential to accelerate filter development.

Limitations and Future Work

  • Complexity of Ciphers: The authors acknowledge that very complex, unbreakable ciphers might not be decipherable by their system. However, they argue that such ciphers would likely also be unreadable by humans.
  • Edit Distance Limitations: Noisy channel spelling correction has limitations with high edit distance cases, which are common in real chat messages.
  • Domain Specificity: While the HMM approach can learn domain-specific language models, the performance is contingent on having access to relevant training data.
  • Future Work: The authors suggest exploring different language messages for decipherment, as long as corresponding language models can be developed. They also imply that further improvements could be made by handling more complex adversarial transformations.

Summary updated

BibTeX
@inproceedings{wu2018decipherment,
  author = {Zhelun Wu and Nishant Kambhatla and Anoop Sarkar},
  title = {{Decipherment for Adversarial Offensive Language Detection}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2018},
}

Loading related content...

Figure