TR-09-03: Lightweight Hierarchical Clustering of Network Packets Using (p,n)-grams

Abstract

The complexity of current Internet applications makes understanding network traffic a challenging task. By providing larger-scale aggregates for analysis, unsupervised clustering approaches can greatly aid in the identification of new applications, attacks, and other changes in network usage patterns. In this paper we introduce ADHIC, a new algorithm that clusters similar network traffic together without prior knowledge of protocol structures. Packet similarity is determined through comparisons of (p, n)-grams (substrings within packets at distinguishing offsets). ADHIC is notable in that it 1) assumes no prior knowledge of packet structure, 2) produces a hierarchical decomposition of network traffic, and 3) has the potential to cluster packets at wire speeds. We find that ADHIC appropriately segregates well-known protocols, clusters together traffic of the same protocol running on multiple ports, and segregates traffic from applications, such as p2p, that do not use standard ports. Potential applications for ADHIC include network performance analysis, real-time alerts of flash crowds or worm activity, and dynamic DoS-resistant bandwidth management. We also introduce NetADHICT, our implementation of ADHIC.

TR-09-02.pdf