Graduate Exam Abstract

Vidarshana Bandara

Ph.D. Final

January 21, 2015, 8:30 am - 11:00 am

JNTHR-120 (Johnson Hall)

Extraction, Characterization and Modeling of Network Data Features - A Compressive Sensing and Robust PCA based Approach

Abstract: Designing computer networks resilient to failures, excessive loads, and attacks and then monitoring them are challenged by a range of issues inherent to networks. These limitations include inability to effectively characterize anomalous and baseline behaviors, access restrictions to place probes, and measurement limitations due to load limits. We develop a suite of solutions for extracting network data given the accessibility and load limitations of the networks, and for characterizing interesting behaviors that capture the features useful for designing and monitoring networks. To the network monitoring and data extraction end, we build solutions for (1) retrieving interesting network data such as anomalies, with a limited amount of instrumentation, e.g., at the network periphery, (2) reconstructing a description of the network from a limited number of measurements, with different approaches suitable for computer networks and sensor networks. To the network data characterization end, we develop solutions for (1) extracting interesting features of data, such as anomalies and baselines, and (2) concisely and accurately modeling these features. The contributions of this thesis include: (1) adaptive compressive sensing algorithms for network monitoring, (2) spatiotemporal modeling of network traffic anomalies, (3) modeling and extracting network traffic baselines using Robust PCA, (4) Compressive Sensing (CS) based data recovery for phenomena discovery, (5) Wavelet based plume tracking for sensor networks, (6) Subtle pattern detection algorithm with applications to hardware trojan detection, and (7) TCP/IP filter for extracting features with application to network attack detection. We present multiple algorithms that adaptively perform CS to resolve network tomographic measurements and rapidly localize anomalies. These algorithms are scalable to large networks, operable with probes placed at arbitrary locations, and guide measurements using advanced IP options. The adaptive compressive sensing algorithms demonstrat over 99% detection rates and less than 1% false positive rates in realistic test environments, for networks reaching over 10,000 links. These require a limited number of monitoring probes residing at the edge of the network and are capable of localizing faults with orders of magnitudes fewer measurements than traditional approaches. Thus we overcome the accessibility restrictions in networks and also provide an efficient method to retrieve critical information from networks. Due to the sporadic behavior, modeling spatiotemporal characteristics of network traffic anomalies has been a challenge. The solution we developed models different spatial and temporal properties of anomalies and integrate them into a single model. The final anomaly model captures statistical behaviors of anomalies as they propagate through nodes and subnets. Calibrating the model requires only the local measurements. However it is capable of capturing the global anomaly behaviors. This characterization enables reproducing statistically similar network anomalies. By appending such characterization, traffic generators can now produce realistic behaviors containing realistic anomalies. Based on the anomaly model, a real-time anomaly monitoring system and a real-time parameter learning system are also proposed. The model allows concise and hierarchical characterization of anomaly behaviors of networks, which so far was not possible. Moreover, the model provides vital information for designing robust networks. Our experiments reveal that Robust PCA achieves recovery over much wider ranges of sparsity and rank, than the published sufficient conditions suggest. These findings enable the use of Robust PCA for separating features of network data. We employ Robust PCA and Fourier methods for separating baseline and anomalous components. Further, these methods are made into real- time filters for baseline extraction and modeling. The baseline extraction algorithm is used in anomaly detection and compared against a number of existing methods to establish its fidelity. Extracted baselines are modeled using two types of patterns, one for link level behaviors and another for network level behaviors. Such characterizations are again crucial for network design and provisioning. We derive theoretical recovery bounds of CS for any pairing of sampling and orthogonality measures. This work leads to cost effective phenomena discovery in sensor networks, where every node in the network becomes aware of the overall network state. Phenomena awareness experiments implemented with random walk sampling indicate superior energy savings and comparable accuracy to classical uniform sampling. Random walk measurements provide a practical means of gathering measurements, while uniform sampling is costly to implement. When applied with CS, phenomena awareness provides a practical and efficient approach to build a complete picture. We developed an economical approach for plume tracking using wavelet transforms. It achieves an error of less than 7% with 25% of measurement points. This data reconstruction scheme saves energy and extends longevity of energy starved sensor network by a factor of five in average. A second improved solution is proposed by combining matrix completion and CS. An algorithm for detecting subtle patterns in an array of time-series is also developed. It is capable of extracting interesting but obscure features from data. The subtle pattern extraction algorithm lay the pathway for detecting hardware trojans whose existence makes only a slight impact on the impedance measurements. To extract interesting features from live network data, we develop a TCP/IP feature filter and successfully use it for detecting Neptune, Smurf, IP and port sweep, and Ping of death attacks. These approaches provide different means of extracting network data suitable different applications extending beyond the scope of networks. The proposed solutions are tested on either real-world or realistic data in order to establish performance and accuracy. To obtain real data, we develop tools to extract data from planet-lab infrastructure and other networks. To construct realistic data, we use established data models such as the Gilbert-Elliot model for packet loss and heavy-tailed distributions for delay, calibrated using actual measurements. Further, commonly used synthesis tools such as IGen are used to simulate large scale realistic networks. These test environments help establish the fidelity of the developed solutions. This research provides effective, practical and accurate solutions for network monitoring, data extraction and modeling.

Adviser: Anura P. Jayasumana
Co-Adviser: Ali Pezeshki
Non-ECE Member: Indrajit Ray, Computer Science
Member 3: Jie Rockey Luo, Electrical & Computer Engineering
Addional Members: Louis Scharf

Bandara, V.W., Pezeshki, A., and Jayasumana, A.P., "Spatiotemporal model for Internet traffic anomalies," Networks, IET, vol.3, no.1, pp.41--53, March 2014.
Paffenroth, R., du Toit, P., Nong, R., Scharf, L., Jayasumana, A.P., and Bandara, V., "Space-Time signal processing for distributed pattern detection in sensor networks," Selected Topics in Signal Processing, IEEE Journal of , vol.7, no.1, pp.38--49, Febuary 2013.
Bandara, V., Jayasumana, A.P., Pezeshki, A., Illangasekare, T.H., and K. Barnhardt, "Subsurface plume tracking using sparse wireless sensor networks," Electronic Journal of Structural Engineering (EJSE) - Special Issue: Wireless Sensor Networks and Practical Applications, pp.1--10, December 2010.
Bandara, V.W., Jayasumana, A.P., and Whitner, R., "An adaptive compressive sensing scheme for network tomography based fault localization," Communications (ICC), 2014 IEEE International Conference on, pp.1290--1295, 10-14 June 2014.
Dhanapala, D.C., Bandara, V.W., Pezeshki, A., and Jayasumana, A.P., "Phenomena discovery in WSNs: A compressive sensing based approach," Communications (ICC), 2013 IEEE International Conference on , pp.1851--1856, 9-13 June 2013.
Bandara, V.W., and Jayasumana, A.P., "Extracting baseline patterns in Internet traffic using Robust Principal Components," Local Computer Networks (LCN), 2011 IEEE 36th Conference on, pp.407--415, 4-7 October 2011.
Bandara, V., Pezeshki, A., and Jayasumana, A.P., "Modeling spatial and temporal behavior of Internet traffic anomalies," Local Computer Networks (LCN), 2010 IEEE 35th Conference on , pp.384--391, 10-14 Oct. 2010.
Bandara, V.W. , Scharf, L.L., Paffenroth, R.C., Jayasumana, A.P., and DuToit, P.C. , “Empirical recovery regions of robust PCA,” in preparation.
Bandara, V.W., Dhanapala, D.C., Pezeshki A., and Jayasumana, A.P., “Performance bounds for sparse signal recovery from random samples,” in preparation.
Bandara, V.W., and Jayasumana, A.P., “Adaptive compressive sensing for network fault localization," in preparation.
Nanayakkara, A., and Bandara, V., “Asymptotic behavior of the eigenenergies of anharmonic oscillators V(x)=x2N + bx2,” Canadian Journal of Physics/Revue Canadienne de Physique, pp. 959--968, September 2002.
Nanayakkara, A., and Bandara, V., “Approximate energy expressions for confining polynomial potentials,” Sri Lankan Journal of Physics, vol.3, pp.17--37, 2002.
Bandara, V.W., Vidanapathirana, A.C, and Abeyratne, S.G., "Contouring with DC motors - a practical experience," Industrial and Information Systems, First International Conference on, pp.474--479, 8-11 August 2006.

Program of Study:
ECE 512 - Digital Signal Processing
ECE 514 - Applications of Random Processes
ECE 516 - Information Theory
ECE 658 - Internet Engineering
ECE 752 - Topics in Signal Processing
MATH 510 - Linear Program & Network Flows