Walter Scott, Jr. College of Engineering

Graduate Exam Abstract

Vidarshana Bandara
Ph.D. Final
Jan 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
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
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
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