Name
Title | ||
|---|---|---|
Finding Cardinality Heavy-Hitters In Mussive Traffic Data And Its Application To Anomaly Detection |
Abstract | ||
|---|---|---|
We propose an algorithm for finding heavy hitters in terms of cardinality (the number of distinct items in a set) in massive traffic data using a small amount of memory. Examples of such cardinality heavy-hitters are hosts that send large numbers of flows, or hosts that communicate with large numbers of other hosts. Finding these hosts is crucial to the provision of good communication quality because they significantly affect the communications of other hosts via either malicious activities such as worm scans, spam distribution, or botnet control or normal activities such as being a member of a flash crowd or performing peer-to-peer (P2P) communication. To precisely determine the cardinality of a host we need tables of previously seen items for each host (e.g., flow tables for every host) and this may infeasible for a high-speed environment with a massive amount of traffic. In this paper, we use a cardinality estimation algorithm that does not require these tables but needs only a little information called the cardinality summary. This is made possible by relaxing the goal from exact counting to estimation of cardinality. In addition, we propose an algorithm that does not need to maintain the cardinality summary for each host, but only for partitioned addresses of a host. As a result, the required number of tables can be significantly decreased. We evaluated our algorithm using actual backbone traffic data to find the heavy-hitters in the number of flows and estimate the number of these flows. We found that while the accuracy degraded when estimating for hosts with few flows, the algorithm could accurately find the top-100 hosts in terms of the number of flows using a limited-sized memory. In addition, we found that the number of tables required to achieve a pre-defined accuracy increased logarithmically with respect to the total number of hosts, which indicates that our method is applicable for large traffic data for a very large number of hosts. We also introduce an application of our algorithm to anomaly detection. With actual traffic data, our method could successfully detect a sudden network scan. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1093/ietcom/e91-b.5.1331 | IEICE TRANSACTIONS ON COMMUNICATIONS |
Keywords | Field | DocType |
cardinality, anomaly detection, data stream | Communication quality,Data mining,Anomaly detection,Peer-to-peer,Computer science,Data stream,Botnet,Cardinality,Computer network,Large numbers,Shared resource | Journal |
Volume | Issue | ISSN |
E91B | 5 | 0916-8516 |
Citations | PageRank | References |
1 | 0.39 | 11 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Keisuke Ishibashi | 1 | 121 | 20.26 |
| Tatsuya Mori | 2 | 153 | 17.64 |
| Ryoichi Kawahara | 3 | 219 | 33.33 |
| Yutaka Hirokawa | 4 | 6 | 1.95 |
| Atsushi Kobayashi | 5 | 8 | 3.40 |
| Kimihiro Yamamoto | 6 | 7 | 2.65 |
| Hitoaki Sakamoto | 7 | 6 | 1.27 |
| Shoichiro Asano | 8 | 31 | 7.96 |