Time Series Deinterleaving of DNS Traffic

Amir Asiaee T., Hardik Goel, Shalini Ghosh, Vinod Yegneswaran, Arindam Banerjee

Abstract

Stream deinterleaving is an important problem with various applications in the cybersecurity domain. In this paper, we consider the specific problem of deinterleaving DNS data streams using machine-learning techniques, with the objective of automating the extraction of malware domain sequences. We first develop a generative model for user request generation and DNS stream interleaving. Based on these we evaluate various inference strategies for deinterleaving including augmented HMMs and LSTMs on synthetic datasets. Our results demonstrate that state-of-the-art LSTMs outperform more traditional augmented HMMs in this application domain.

Introduction

In modern cybersecurity, tracking the sequence of DNS lookups is vital for identifying "redirection chains"—the series of intermediate domain hops used by malware to obscure its final destination. However, privacy-preserving measures by Internet Service Providers (ISPs) often aggregate traffic and strip user identifiers like IP addresses. This results in an "interleaved" stream of domain requests from multiple users, making it difficult to reconstruct individual browsing episodes. This paper addresses the challenge of "deinterleaving" this traffic to recover original user sequences.

Methodology

The researchers developed a hierarchical framework to model the generation and mixing of DNS traffic.

User Behavior Model

Individual user behavior is modeled as a Hidden Semi-Markov Model (HsMM). In this setup, the hidden state represents the webpage being visited ($w$), while the observations are the specific DNS requests ($r$) triggered by that page. Unlike standard Markov models, the HsMM incorporates a duration parameter ($d$), accounting for the fact that a single webpage visit typically generates multiple DNS requests before the user transitions to a new page.

Evolution of generative models from Markov Chains to HsMM.

Interleaving and Inference

To model the combined traffic of $m$ users, the authors use an Augmented Hidden Markov Model (AHMM). The state space of this model grows exponentially with the number of users and pages, leading to a "curse of dimensionality." Two primary inference strategies were evaluated:

  1. Viterbi Inference: A classic dynamic programming approach for finding the most likely sequence of hidden states in an HMM.
  2. Long Short-Term Memory (LSTM): A recurrent neural network architecture trained to classify which user initiated each request in the interleaved stream, leveraging its ability to learn long-term temporal dependencies.

Experimental Setup

Due to the lack of labeled real-world DNS data, the study utilized synthetic datasets generated via the HsMM framework. Seven distinct scenarios (Cases 1–7) were designed to test the models under varying conditions of complexity.

Visualization of synthetic data scenarios (Cases 1-3) representing different surfing patterns and output distributions.

These cases varied along several dimensions:

  • Surfing Patterns: Whether users visit disjoint sets of pages (Case 1) or share common interests (Case 2/3).
  • Output Distributions: Whether the same page triggers identical or personalized DNS requests for different users.
  • Transition Dynamics: The mechanism determining which user's request enters the queue at any given time.

Results and Discussion

The evaluation revealed a significant performance gap between traditional statistical methods and deep learning.

  • Superiority of LSTMs: In a simplified "toy" scenario, the Viterbi algorithm achieved only 51% accuracy, whereas the LSTM reached 92%. LSTMs proved more robust across all seven synthetic cases, particularly in handling the non-linear temporal relations inherent in "bursty" web browsing.
  • Impact of Output Sparsity: Deinterleaving is most successful when users have "personalized outputs"—even if they visit the same site, the specific background requests they trigger help the models distinguish between them.
  • Computational Efficiency: While the AHMM's state space explodes as users are added, LSTMs scale more gracefully, avoiding the exponential complexity that plagues Viterbi inference in this domain.

Conclusion

This research demonstrates that LSTMs are highly effective at deinterleaving DNS traffic, significantly outperforming traditional HMM-based approaches. While the current study relies on synthetic data, it provides a strong foundation for automating the detection of malicious redirection chains in anonymized traffic. Future work will focus on scaling these models to handle thousands of concurrent users and validating them against real-world, noisy DNS datasets.

Summary updated

Abstract

Stream deinterleaving is an important problem with various applications in the cybersecurity domain. In this paper, we consider the specific problem of deinterleaving DNS data streams using machine-learning techniques, with the objective of automating the extraction of malware domain sequences. We first develop a generative model for user request generation and DNS stream interleaving. Based on these we evaluate various inference strategies for deinterleaving including augmented HMMs and LSTMs on synthetic datasets. Our results demonstrate that state-of-the-art LSTMs outperform more traditional augmented HMMs in this application domain.
BibTeX
@inproceedings{t2018time,
  author = {Amir Asiaee T. and Hardik Goel and Shalini Ghosh and Vinod Yegneswaran and Arindam Banerjee},
  title = {{Time Series Deinterleaving of DNS Traffic}},
  booktitle = {IEEE Symposium on Security and Privacy Workshops},
  year = {2018},
  url = {https://openreview.net/forum?id=akqRfwdysA},
}
Figure