HEDGE: Efficient Traffic Classification of Encrypted and Compressed Packets

Fran Casino, Kim-Kwang Raymond Choo, Constantinos Patsakis

In the world of network security, high entropy is usually a sign that something is being hidden. Whether it’s a user protecting their privacy with AES encryption or a system saving bandwidth with GZIP compression, the resulting data packets look like random noise to most monitoring tools. But for a security analyst or a smart firewall, the difference between "encrypted" and "compressed" is massive: one is a secure tunnel, while the other is a potentially reversible data leak.

TL;DR

HEDGE (High Entropy DistinGuishEr) is a novel, real-time traffic classification method that distinguishes between encrypted and compressed packets by analyzing their statistical randomness. By applying a lightweight threshold-based approach to individual packets, HEDGE outperforms state-of-the-art machine learning models while maintaining significantly lower computational overhead.

What Problem Does This Paper Address?

As network traffic explodes due to IoT and mobile devices, monitoring every bit becomes a scalability nightmare. To cope, many systems use sampling. However, current tools struggle to differentiate between high-entropy data streams.

Why does this matter?

  1. Security Auditing: Some IoT devices use compression instead of encryption due to limited CPU power, leaving sensitive data vulnerable to recovery.
  2. Malware Detection: Adversaries often use compression to exfiltrate data, bypassing signature-based detection systems that expect cleartext.
  3. Efficiency: Most existing solutions require access to an entire data stream or "flow" to make a classification. HEDGE aims to do this using only individual, randomly sampled packets.

Methods

The authors propose a method that avoids the "black box" nature and high computational cost of Deep Learning (like CNNs). Instead, HEDGE uses a tree-based threshold system built on classical statistical randomness tests:

  • Chi-Square Test: Used to evaluate if the distribution of bits in a packet deviates from what is expected in a truly random sequence.
  • NIST SP 800-22 Subset: The authors identified three specific tests from the NIST suite—Frequency within Block, Cumulative Sums, and Approximate Entropy—that are particularly effective at spotting the subtle patterns left behind by compression algorithms.
  • Gain Factor ($\gamma$): A tunable parameter that allows administrators to adjust the "strictness" of the detection policy, balancing the trade-off between True Positives (correctly identified compressed files) and False Negatives (missed encrypted files).

Unlike $O(n^2)$ machine learning approaches, HEDGE operates with linear complexity $O(n)$, making it suitable for high-speed, real-time hardware.

Datasets

The researchers developed a new, statistically sound dataset to avoid the biases found in older benchmarks. They pulled raw data from:

  • Images: COCO Dataset and Microsoft Research.
  • Text: Project Gutenberg.
  • Multimedia: ArXiv (PDFs), MP3s (Beethoven), and Video (Cambridge-driving).
  • Binaries: Windows 10 and Ubuntu system files.

They then processed these files using various encryption (AES, Camelia) and compression (ZIP, RAR, BZIP2, GZIP) methods across packet sizes ranging from 1KB to 64KB. The dataset and code are publicly available on GitHub.

Key Insights and Ideas

  • The "Source" Matters for Compression: One of the most interesting findings is that the "randomness" of a compressed file depends heavily on its original type. Compressed text or binary files are much easier to distinguish from encrypted data than compressed images or videos. This is because images and videos already have high entropy; compressing them further leaves them looking almost as random as encrypted data.
  • Packet-Level Granularity: HEDGE doesn't need to see the "handshake" or the start of a session. It can look at a single 1KB fragment in isolation and still make a better-than-average guess.
  • Stability of Encryption: Encrypted data is remarkably consistent in its randomness across all file types and sizes. This stability allows HEDGE to use encryption as a "baseline" for its thresholds.

Key Results

HEDGE consistently outperformed the previous state-of-the-art (Hahn et al., 2018):

  • High Accuracy: At a packet size of 64KB, HEDGE achieved 94.72% accuracy.
  • Small Packet Performance: Even at the challenging 1KB packet size, HEDGE reached 70.6% accuracy, a significant improvement over the 66.9% achieved by previous methods using the same data.
  • Computational Efficiency: Because it uses a threshold system rather than a neural network, it can be easily parallelized and requires no heavy training phase once the initial thresholds are set.

Limitations and Future Work

While HEDGE is a step forward, it faces challenges as packet sizes shrink. Accuracy drops to roughly 68.6% for 1KB packets when considering all file types. The authors also note that very high-entropy original files (like already-compressed JPEGs) remain the "final boss" of traffic classification, as their compressed versions are nearly indistinguishable from encrypted streams.

Future work aims to refine the method for sub-1KB packets and explore whether HEDGE can be extended to identify specific file types (e.g., "this is a compressed PDF") to improve pro-active security measures.

Summary updated

Abstract

As the size and source of network traffic increase, so does the challenge of monitoring and analyzing network traffic. Therefore, sampling algorithms are often used to alleviate these scalability issues. However, the use of high entropy data streams, through the use of either encryption or compression, further compounds the challenge as current state-of-the-art algorithms cannot accurately and efficiently differentiate between encrypted and compressed packets. In this paper, we propose a novel traffic classification method named High Entropy DistinGuishEr (HEDGE) to distinguish between compressed and encrypted traffic. HEDGE is based on the evaluation of the randomness of the data streams and can be applied to individual packets without the need to have access to the entire stream. The findings from the evaluation show that our approach outperforms current state of the art. We also make available our statistically sound dataset, based on known benchmarks, to the wider research community.
BibTeX
@article{casino2019hedge,
  author = {Fran Casino and Kim-Kwang Raymond Choo and Constantinos Patsakis},
  title = {{HEDGE: Efficient Traffic Classification of Encrypted and Compressed Packets}},
  journal = {IEEE Trans. Inf. Forensics Secur.},
  year = {2019},
  url = {https://openreview.net/forum?id=xihTLsqUIwy},
}

Loading related content...

Figure