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.

We consider a new type of distinct element counting problem in dynamic data streams, where (1) insertions and deletions of an element can appear not only in the same data stream but also in two or more different streams, (2) a deletion of a distinct element cancels out all the previous insertions of this element, and (3) a distinct element can be re-inserted after it has been deleted. Our goal is to count the number of distinct elements that were inserted but have not been deleted in a continuous data stream. We also solve this new type of distinct element counting problem in a distributed setting. This problem is motivated by several network monitoring and attack detection applications where network traffic can be modelled as single or distributed dynamic streams and the number of distinct elements in the data streams, such as unsuccessful TCP connection setup requests, is calculated to be used as an indicator to detect certain network events such as service outage and DDoS attacks. Although there are known tight bounds for distinct element counting in insertion-only data streams, no good bounds are known for it in dynamic data streams, neither for this new type of problem. None of the existing solutions for distinct element counting can solve our problem. In this paper, we will present the first solution to this problem, using a space-bounded data structure with a computation-efficient probabilistic data streaming algorithm to estimate the number of distinct elements in single or distributed dynamic data streams. We have done both theoretical analysis and experimental evaluations, using synthetic and real data traces, of our algorithm to show its effectiveness.

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.

Frauds and attacks for online banking are increasing quickly. The major platform for current online banking, personal computer, has become untrusted especially under malware attacks. In this study, we design a smart card-based solution called secure online banking companion (SOBC) to address this problem. Portability and cost are also highly considered in the design. We have implemented a prototype of the solution on a Java Card simulator, which shows the solution can be implemented easily using current smart card technologies.