Measurement and Classification of Humans and Bots in Internet Chat

Steven Gianvecchio, Mengjun Xie, Zhengyu Wu, Haining WangUSENIX Security 2008 · OpenReview

Abstract

Internet chat services are increasingly targeted by automated bots for spam and phishing. This paper presents a hybrid classification system that distinguishes human users from bots by analyzing behavioral complexity. By combining an entropy-based classifier that measures the predictability of message timing and size with a machine-learning component for content analysis, the system achieves near-perfect detection rates. The approach leverages the inherent statistical "chaos" of human interaction, which is difficult for bots to replicate.

Introduction

The proliferation of bots in chat services poses a significant threat, as they bypass traditional defenses like keyword filters and CAPTCHAs. While a single message might appear human, sustaining human-like statistical patterns over time is a much greater challenge for automated systems. This research identifies a fundamental gap in existing defenses: the lack of systematic investigation into the behavioral differences between humans and bots. The authors argue that human behavior is characterized by a level of complexity and unpredictability that bots struggle to sustain.

Methodology

The researchers propose a dual-component system that leverages both behavioral statistics and message content:

  1. Entropy-Based Classifier: This component measures the entropy rate—a metric of regularity and predictability—of two features: inter-message delay and message size. Humans are naturally unpredictable, resulting in high entropy. Bots, even those using random timers, often exhibit underlying statistical regularities that this classifier can detect.
  2. Machine Learning-Based Classifier: This component uses a Bayesian-based text classifier (specifically CRM114 with Orthogonal Sparse Bigrams) to identify known bot message patterns.
  3. Hybrid Approach: The entropy classifier acts as a "teacher." When it detects a new, unknown bot based on its rigid timing or size patterns, it feeds those messages into the machine-learning component to train it. This allows the system to quickly identify similar bots in the future using only a few messages.

Behavioral Signatures

The study is grounded in a massive real-world dataset collected from Yahoo! Chat, comprising over 340,000 human messages and 87,000 bot messages across 14 different types. Analysis reveals that human inter-message delays follow a "heavy-tailed" distribution (power law), indicating highly variable rhythms.

Human message behavior exhibits high complexity, with inter-message delays (a) following a heavy-tailed distribution and message sizes (b) showing a broad spread.

In contrast, bots exhibit far more regular or clustered patterns. Periodic bots, for instance, show distinct spikes in their probability mass functions (PMF) for message size and timing, reflecting their underlying triggering mechanisms.

Periodic bots exhibit highly clustered message size distributions, reflecting the rigid templates often used by automated scripts.

Performance and Results

The hybrid system proved highly effective across various bot categories:

  • Periodic and Random Bots: The entropy classifier achieved 100% detection based on timing alone.
  • Advanced Bots: Even for "Responder" bots (triggered by human input) and "Replay" bots (which repeat human phrases), the system maintained high accuracy. Message size entropy was particularly effective at catching Responder bots.
  • Efficiency: While the entropy classifier typically requires about 100 messages for high confidence, the machine-learning component can identify known bots in as few as 25 messages.
  • Accuracy: The system was tuned to a target false positive rate of 0.01, ensuring minimal disruption for legitimate human users.

Conclusion

By focusing on the inherent complexity of human behavior, this hybrid approach provides a robust defense against automated threats in chat environments. The use of Corrected Conditional Entropy (CCE) allows for accurate measurements even with short message sequences, making the system practical for real-time application. Future work may apply these techniques to other automated threats, such as web-crawling bots or automated agents in online games.

Summary updated

BibTeX
@inproceedings{gianvecchio2008measurement,
  author = {Steven Gianvecchio and Mengjun Xie and Zhengyu Wu and Haining Wang},
  title = {{Measurement and Classification of Humans and Bots in Internet Chat}},
  booktitle = {USENIX Security},
  year = {2008},
  url = {https://openreview.net/forum?id=3Ujc3JYtkn},
}
Figure