Host cardinality is defined as the number of distinct peers that a host communicates with in the network. There have been several algorithms proposed to monitor network traffic and identify high-cardinality hosts at a centralized network operation center (NOC). Due to massive amounts of distributed data and limitations on transforming and processing them at the NOC, it is desirable to design mergable and reversible data structures summarizing traffic measurements in a distributed network monitoring system. A mergable data structure summarizes traffic measurements at each local monitor, and these summaries from different monitors can be merged at the NOC, while preserving the error guarantee without increasing space. A reversible data structure can report interested (high-cardinality) hosts efficiently using compressed information without querying every single host in the network. In this paper, we propose a new data streaming algorithm to identify high-cardinality hosts over the network-wide traffic measurements. Our algorithm introduces a new mergable and reversible data structure for the distributed network monitoring system, which is designed by Noisy Group Testing. We have theoretically analyzed our algorithm and evaluated it against real-world data sets.

Cyber-attacks are happening every day, with a variety of behaviors and objects. For example, email spammers may compromise computers to sign-up millions of email accounts for sending spam emails; during worm spreading, each infected host may try to connect to many hosts to further spread the worm, etc. However, many such large-scale and often distributed cyber-attacks share a common characteristic that the activities involved in them result in changes in the cardinality of attack traffic. Examples include: the cardinality of the accounts signed up by a compromised host often increases in spam email delivery scenarios, and the cardinality of the connections made from a host may increase in worm spreading scenarios. In this paper, we focus on changes in the cardinality of the network/attack traffic that may indicate on-going cyber-attacks. We formulate this problem as cardinality-based change point detection in distributed streams of attack traffic, and develop a nonparametric error-bounded scheme for it. Our scheme supports the capability of merging information collected from multiple monitoring points to detect large-scale attacks. Also, our scheme uses small space as well as constant processing time, which makes it applicable for spaceconstrained network or security systems. We have conducted experiments using both real-world traces and synthetic data. Experimental results and theoretical analysis show that our scheme can detect changes in the cardinality within given time and error bounds. We expect the solutions of this work will be deployed as a building block in network and security monitoring systems to detect large distributed cyber attacks.

There has been a long history of finding a spaceefficient data structure to support approximate membership queries, started from Bloom's work in the 1970's. Given a set A of n items and an additional item x from the same universe U of a size m ≫ n, we want to distinguish whether x ∈ A or not, using small (limited) space. The solutions for the membership query are needed for many network applications, such as cache directory, load-balancing, security, etc. If A is static, there exist optimal algorithms to find a randomized data structure to represent A using only (1+ o(1))n log 1/δ bits, which only allows for a small false positive δ but no false negative. However, existing optimal algorithms are not practical for many Internet applications, e.g., social network services, peer-to-peer systems, network traffic monitoring, etc. They are too spaceand time-expensive due to the frequent changes in the set A, because all items are needed to recompute the optimal data structure for each change using a linear running time. In this paper, we propose a novel data structure to support the approximate membership query in the time-decaying window model. In this model, items are inserted one-by-one over a data stream, and we want to determine whether an item is among the most recent w items for any given window size w ≤ n. Our data structure only requires O(n(log 1/δ+logn)) bits and O(1) running time. We also prove a non-trivial space lower bound, i.e. (n - δm) log(n - δm) bits, which guarantees that our data structure is near-optimal. Our data structure has been evaluated using both synthetic and real data sets.

There have been security problems and network failures that are hard to resolve, for example, botnets, polymorphic worm/virus, DDoS, etc. To address them, we need to monitor the traffic dynamics and have a network-wide view about them, and more importantly, be able to detect attacks and failures in a timely manner. Due to the rapid increase in the traffic volume, it is often infeasible to monitor every individual flow in the backbone network due to space and time constraints. Instead, we are often required to aggregate packets into a small number of flows and develop the detection methods with aggregated flows, namely aggregate queries. Although it enables ISPs to detect network problems in a timely manner, the flow aggregation cannot preserve certain critical information in network traffic, e.g., IP addresses, port numbers, etc. Due to such missing information, it becomes very difficult (or often infeasible) for ISPs to identify the sources of network attacks or the causes of traffic anomalies, which are important to resolve the network problems effectively. In this paper, we propose an efficient data structure, namely the fast sketch, which can both aggregate packets into a small number of flows, and further enable ISPs to identify the anomalous keys (IP addresses, port numbers, etc.), with small space and time. With it, the number of aggregated flows can achieve the lower bound of the heavy-change detection, i.e., Ω(k log(n/k)), where n is the range of flow keys and k is an upper bound of the number of anomalous keys. In addition, our sketch combines both the combinatorial group testing and the quotient technique to identify anomalous keys, which can guarantee a sub-linear running time. We expect our work will improve the practice for real-time traffic monitoring in a high-speed networked system.

Recently, Traffic Activity Graphs (TAGs) have been proposed to understand, analyze, and model network-wide communication patterns. The topological properties of the TAGs have been shown to be very helpful for malware analysis, anomaly detection, and attack attribution. In a TAG, nodes represent hosts in the network and edges are observed flows that indicate certain communication relations or interactions of interest among the hosts. The challenge is how to capture and analyze TAGs which are usually large, sparse and complex and often have overly-large space and computation requirements. In this paper, we present a new sampling-based low-rank approximation method for monitoring TAGs. The resulted solution can reduce the computation complexity for the communication pattern analysis from O(mn) to O(m+n), where m and n denote the number of sources and destinations, respectively. The experimental results with real-world traffic traces show that our method outperform existing solutions in terms of efficiency and the capability of processing and identifying unknown TAGs.

Internet has become an essential part of the daily life for billions of users worldwide, who are using a large variety of network services and applications everyday. However, there have been serious security problems and network failures that are hard to resolve, for example, botnet attacks, polymorphic worm/virus spreading, DDoS, and flash crowds. To address many of these problems, we need to have a network-wide view of the traffic dynamics, and more importantly, be able to detect traffic anomalies in a timely manner. Spatial analysis methods have been proved to be effective in detecting network-wide traffic anomalies that are not detectable at a single monitor. To our knowledge, Principle Component Analysis (PCA) is the best-known spatial detection method for the coordinated low-profile traffic anomalies. However, existing PCA-based solutions have scalability problems in that they require linear running time and space to analyze the traffic measurements within a sliding window, which makes it often infeasible to be deployed for monitoring large-scale high-speed networks. We propose a sketch-based streaming PCA algorithm for the network-wide traffic anomaly detection in a distributed fashion. Our algorithm only requires logarithmic running time and space at both local monitors and Network Operation Centers (NOCs), and can detect both high-profile and coordinated low-profile traffic anomalies with bounded errors.