Statistics on Data Streams with Applications on Mining High-Impact Computer Network Events

• Activity Number: 547
• Type: Contributed
• Date/Time: Wednesday, August 12, 2015 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Shrijita Bhattacharya* and Stilian Stoev and George Michailidis and Michael Kallitsis
• Companies: University of Michigan and University of Michigan and University of Florida and Merit Network, Inc.

Abstract

Monitoring traffic for finding nefarious activity in modern day networks involves rapid analysis of large volumes of data. Such types of data, referred to as data streams can only be accessed sequentially under relatively stringent time and space constraints. This poses novel challenges to the types of statistics that can be used in this setting. Here we address the canonical problem of the detection and estimation of the number of high activity entities, also called heavy hitters in a data stream. The problem is motivated by the detection of anomalies such as the onset of denial of service attacks in networks. We use small space data structures and pseudo-random hash functions for compressing the data stream. A statistical model which elucidates network flow characteristics is presented. We develop statistics that can be efficiently computed on fast data streams and allow one to track the number of heavy users in real time. We provide estimates on the accuracy of these estimators and identify their optimal regime with respect to tuning parameters. We use data visualization techniques to study the global structure and dynamics of network flows in real time.