Traditional network anomaly detection involves developing models that rely on packet inspection. However, increasing network speeds and use of encrypted protocols make per-packet inspection unsuited for today's networks. One method of overcoming this obstacle is aggregating packet header information and performing flow based analysis. Many existing approaches are special purpose limited to detecting specific behavior. Also, data reduction inherent in identifying anomalous flows hinders alert correlation. In this paper, we propose and develop a dynamic anomaly detection approach for augmented network flows. We sketch network state during flow creation enabling general purpose threat detection. We describe an efficient flow augmentation approach based on the count-min sketch that provides per-flow, per-node, and per-network level statistics parallel to flow record generation. We design and develop a support vector machine based adaptive anomaly detection and correlation mechanism, which is capable of aggregating alerts without a-priori alert classification and evolving models online. We further develop a lightweight evolving alert aggregation method and combine it with a confidence forwarding mechanism identifying a small percentage predictions for additional processing. We show effectiveness of our methods on both enterprise and backbone traces. Experimental results demonstrate its ability to maintain high accuracy without the need for offline training.
Self-stabilizing systems tolerate transient faults by always returning to a legitimate system state within a finite time. This work considers the design of self-stabilizing distributed algorithms from the perspective of game theory. The basic idea is to achieve an intended system goal through private goals of processes. However, this notion is complicated by several features of self-stabilizing systems such as arbitrary initial system states and non-deterministic process execution sequences. We propose two game-theoretic designs for identifying a maximal independent set (MIS) among all processes in a distributed system. The proposed games eventually converge to a quiescent yet legitimate game state regardless of initial game configuration and game play sequence. We convert the game designs into distributed self-stabilizing algorithms expressed in guarded commands. The surprising result is that the derived algorithm is the first self-stabilizing MIS algorithm with a guaranteed performance ratio of ( + 2) / 3. Simulation results indicate that, for various representative types of network topologies, the algorithm outperforms existing methods in terms of MIS size and convergence rate.
SASO 2014: Selected, Revised, and Extended Best Papers
Underwater wireless sensor networks (UWSNs) have been developed for a set of underwater applications, including resource exploration, pollution monitoring, tactical surveillance, and so on. The complexity and diversity of underwater environments differentiate them significantly from terrestrial environments. Thus, the coverage requirements (coverage degrees) at different regions are possibly different as well. However, few efforts have so far been made on the topology control of UWSNs for the diverse coverage requirements. This paper proposes two algorithms for the diverse coverage problem: Traversal Algorithm for Diverse Coverage (TADC) adjusts the sensing radii of nodes successively, and at every round only one node alters its radius; Radius Increment Algorithm for Diverse Coverage (RIADC) sets the sensing radii of nodes incrementally, and at every round multiple nodes may increase their sensing radii simultaneously. Mathematical analysis shows both TADC and RIADC try best to achieve diverse coverage, but they have advantages in message complexity or optimal radius, respectively. Hence, these algorithms are suitable for different scenarios. Algorithm performance is also analyzed through simulation experiments that indicate TADC and RIADC realize diverse coverage while optimizing energy consumption as much as possible.
In this paper, we propose formation control of non-holonomic mobile robots avoiding obstacles in a distributed manner for cluttered environment. The introduction of virtual robot re-structures the formation control problem into a tracking control problem between virtual reference robot and follower robots. A novel obstacle avoidance approach is proposed based upon the scaling of whole (partial) formation corresponding to centralized (distributed) framework. For the distributed environment having limited communication, our approach utilized Proportional-Integral (PI) average consensus estimators, whereby information from each robot diffuses through the communication network. The theoretical contribution is to determine the time constant involved in the diffusion process which can affect overall systems' performance. The asymptotic convergence of follower robots to the position and orientation of the reference robot is ensured using the Lyapunov function. The new technique is tested with complete, limited and no information availability. Several simulation results are provided that demonstrate the formation control and obstacle avoidance for multi-robots using the proposed scheme.