Classifying DNS Heavy User Traffic by Using Hierarchical Aggregate Entropy

We introduce the notion of hierarchical aggregate entropy and apply it to identify DNS client hosts that wastefully consume server resources. Entropy of DNS query traffic can capture client query patterns, e.g., the concentration of queries to a specific domain or dispersion to a large domain name space. However, entropy cannot capture the spatial structure of the traffic. That is, even if queries disperse to various domains but concentrate in the same upper domain, entropy among domain names provides no information on the upper domain structure, which is an important characteristic of DNS clients. On the other hand, entropies of aggregated upper domains do not have detailed information on individual domains. To overcome this difficulty, we introduce the notion of hierarchical aggregate entropy, where queries are recursively aggregated into upper domains along the DNS domain tree, and calculate their entropies. Thus, this method enables us to analyze the spatial characteristics of DNS traffic in a multi-resolution manner. We calculated the hierarchical aggregate entropies for actual DNS heavy-hitters and observed that the entropies of normal heavy-hitters were concentrated in a specific range. On the basis of this observation, we adopt the support vector machine method to identify the range and to classify DNS heavy-hitters as anomalous or normal. It is shown that with hierarchical aggregate entropy, classification error was halved compared to non-hierarchical entropies. In addition, we analyzed time series variation of the component ratio of heavy-hitters and found a sudden increase of normal heavy-hitters between Mar. and Oct. 2009. We confirmed that one of the major reasons for the increase was the implementation of DNS prefetch in a popular Web browser.