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, network vantage points such as proxy servers, NAT firewalls, or recursive DNS resolvers often aggregate traffic from numerous users into a single, interleaved stream. For privacy or technical reasons, individual client identifiers like IP addresses are frequently removed. This aggregation poses a significant challenge for security analysts attempting to detect malware "redirection chains"—sequences of domain requests that lead to an exploit. When these sequences are buried within a noisy, interleaved stream, they become nearly invisible. This paper addresses the challenge of stream deinterleaving: accurately assigning each DNS query in a jumbled resolver queue back to its original (anonymous) source sequence.

Methodology

The authors propose a two-part generative model to describe the creation and mixing of DNS traffic.

User Request Model

Individual browsing behavior is modeled as a Hidden Semi-Markov Model (HsMM). In this framework, a user's visit to a webpage is treated as a hidden state, and the resulting DNS queries are the observations. Unlike a standard HMM, the HsMM accounts for the "duration" of a state, reflecting how a single webpage visit can trigger multiple, sequential DNS requests.

Evolution of models from Markov Chain to HsMM.

Interleaving Model

The combined resolver queue is modeled as an Augmented Hidden Markov Model (AHMM). This model factors in the "turn-taking" dynamics between multiple users as they contribute to the shared stream.

The Augmented Hidden Markov Model (AHMM) representing the interleaved resolver queue.

Inference Strategies

Two primary strategies are evaluated for deinterleaving:

  1. Viterbi Inference (AHMM): A traditional statistical approach that seeks the most likely sequence of hidden states. However, this method suffers from "state space explosion," where complexity grows exponentially with the number of users and websites, making it computationally prohibitive for large-scale applications.
  2. Long Short-Term Memory (LSTM) Networks: Deinterleaving is reframed as a multi-class classification problem. The LSTM processes the DNS request sequence and predicts, at each time step, which user was responsible for the query. LSTMs are better suited to capture the complex, non-linear temporal dependencies of "bursty" DNS traffic.

Experimental Evaluation

Due to the lack of labeled real-world DNS data, the researchers utilized synthetic datasets. These included a "Toy Dataset" for baseline testing and seven complex scenarios (Cases 1-7) involving 2 users and 20 pages. These scenarios varied the degree of overlap in surfing patterns and the uniqueness of DNS requests (output matrices).

Key Results

  • Performance: In the toy experiment, the LSTM achieved 92% accuracy, vastly outperforming the Viterbi algorithm, which managed only 51% (barely above the random baseline).
  • Robustness: In "disjoint" scenarios where users visit different sites, the LSTM reached 100% accuracy. Even in the most challenging "shared" scenario (Case 3), where different pages trigger identical DNS requests, the LSTM maintained 63-77% accuracy.
  • Insights: The study found that the uniqueness of DNS requests (output sparsity) is more critical for successful deinterleaving than the specific surfing patterns of users.

Conclusion

Traditional linear models like HMMs struggle with the exponential state space and non-linear dependencies inherent in interleaved DNS traffic. In contrast, LSTMs demonstrate significant promise in reconstructing individual user sequences from aggregated streams. Future work will focus on scaling these models to handle thousands of concurrent users and applying these techniques to extract malware domain groups from real-world, noisy traffic.

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},
}

Loading related content...

Figure