SEMINAR TALKS
LOCATION: CISE BLDG. E555 TIME: THURSDAY, 10:00 am (EST)
Fall '09 |Summer '09 | Archive
Fall '09
October 15, 2009: “WORMEROS: A New Framework for Defending against Wormhole Attacks onWireless Ad Hoc Networks"
Presented by: Incheol Shin.
Abstract
Wormhole attack is a type of replay
attack in wireless networks that has serious consequences and is hard
to defend against. This is because the attacker does not need to modify
packets or compromise wireless nodes. This paper introduces Wormeros, a
new framework to detect wormhole attacks in wireless networks. The
framework contains two phases namely suspicion and confirmation. Our
solution does not require any special hardware (such as GPS) or
expensive mechanisms (such as time synchronization) added to the
wireless nodes. Using analysis and simulation, we show that our
solution is effective in detecting
and defending against wormhole attacks.
October 8, 2009: “Jamming-resistant broadcast communication without shared keys"
Presented by:Ying Xuan.
Abstract
Jamming-resistant broadcast communication is crucial for
safety-critical applications such as emergency alert broadcasts or the
dissemination of navigation signals in adversarial settings. These
applications share the need for guaranteed authenticity and
availability of messages which are broadcasted by base stations to a
large and unknown number of (potentially untrusted) receivers. Common
techniques to counter jamming attacks such as Direct-Sequence
Spread Spectrum (DSSS) and Frequency Hopping are based on secrets that
need to be shared between the sender and the receivers before the start
of the communication. However, relying
broadcast anti-jamming communication on either secret pairwise or group
keys suffers from serious and sometimes even unsolvable scalability and
key-setup problems or from weak jamming-resistance,
respectively. In this work, we therefore propose a solution called
Uncoordinated DSSS (UDSSS) that enables spread-spectrum anti-jamming
broadcast communication without the requirement of shared
secrets. It is applicable to broadcast scenarios in which receivers
hold a certificate of the sender’s public key, but do not share a
secret key with it. UDSSS can handle an unlimited amount of receivers
while being secure against malicious receivers. We analyze the security
and latency of UDSSS and complete our work by an
experimental evaluation on a prototype implementation.
October 1, 2009: “Tracking Dynamic Boundary Fronts Using Range Sensors"
Presented by: Ravi Tiwari.
Abstract
The authors examine the problem of tracking dynamic boundaries occurring in natural phenomena using range sensors. Two main challenges of the boundary tracking problem are energy-efficient boundary estimations from noisy observations and continuous tracking of the boundary. The authors propose a novel approach which uses a regression-based spatial estimation technique to determine discrete points on the boundary and estimates a confidence band around the entire boundary. In addition, a Kalman Filter-based temporal estimation technique is used to selectively refresh the estimated boundary to meet the accuracy requirements. Their algorithm for dynamic boundary tracking (DBTR) combines temporal estimation with an aperiodically updated spatial estimation and provides a low overhead solution to track boundaries without requiring prior knowledge about the dynamics of the boundary. Experimental results demonstrate the effectiveness of our algorithm and estimated confidence bands achieve loss of coverage of less than 2 − 5% for a variety of boundaries with different spatial characteristics.
September 24, 2009: “Large Cliques in a power-law random graph"
Presented by: Dung T. Nguyen.
Abstract
Abstract. We study the size of the
largest clique !(G(n, )) in a random graph G(n, ) on n vertices which
has power-law degree distribution with exponent . We show that for
‘flat’ degree sequences with > 2 whp the largest clique in G(n, ) is
of a constant size, while for the heavy tail distribution, when 0 <
< 2, !(G(n, )) grows as a power of n. Moreover, we show that a
natural simple algorithm whp finds inG(n, ) a large clique of size (1 + o(1))!(G(n, )) in polynomial time.
September 10, 2009: “Distributive Boundary estimation Using Sensor Network"
Presented by: Ravi Tiwari.
Abstract
The authors examined the problem of
determining boundaries occurring in natural phenomena using
sensornetworks. Sensor nodes remotely collect data about various points
on the boundary. From this data, we estimate the boundary along with
the confidence intervals using a regression relationship among sensor
locations and the distances to the boundary. The confidence intervals
are guaranteed to be narrower than a specified maximum width. Our
distributed boundary estimation strategy uses a hierarchical structure
of clusters of sensor nodes and requires 20−50% less messages as
compared to a centralized scheme. The computed intervals show desired
coverage of the true boundary points. Further, motivated by the
practical need to estimate the boundary with a minimum number of
sensors, we develop an adaptive approach for turning sensors on and
off. The number of ON sensors in this scheme is only about 15% more
than what a Practical Oracle needs, to evaluate the boundary and
confidence intervals around it. Our algorithms are also evaluated using
data from real sensors on a testbed.
September 3, 2009: “Constant-Factor Approximation Algorithms for Identifying Dynamic Communities"
Presented by: Nam Nguyen.
Abstract
We propose two approximation algorithms for identifying communities in dynamic social networks. Communities are intuitively characterized as “unusually densely knit” subsets of a social network. This notion becomes more problematic if the social interactions change over time. We show that the algorithms are small constant factors approximation of the optimums, regardless of the input size. They are the first algorithms for inferring communities in dynamic networks with provable approximation guarantees.
August 27, 2009: “What Cannot be Computed Locally?"
Presented by : Thang N. Dinh
Abstract
We give time lower bounds for the distributed approximation of minimum
vertex cover (MVC) and related problems such as minimum dominating set
(MDS). In k communication rounds, MVC and MDS can only be approximated
by factors O(n^(c/k^2)/k) for some c > 1/4 or O(d^(c/d^2)/d) where
d is maximum degree.
In other words the number of rounds required in order to achieve a constant or even only a polylogarith-
mic approximation ratio is at least O(sqrt( log n/ log log n)) and O(sqrt( log d/ log log d)).
Summer '09 |
August 20, 2009: “Detecting Wormhole Attacks in Wireless Networks Using Connectivity Information”
Presented by : Incheol Shin
Abstract
In the talk the paper "Detecting Wormhole Attacks in Wireless Networks Using Connectivity Information" will be presented in which the author proposed a novel algorithm for detecting wormhole attacks in wireless multi-hop networks. The algorithm uses only connectivity information to look for forbidden substructures in the connectivity graph. The proposed approach is completely localized and, unlike many techniques proposed in literature, does not use any special hardware artifact or location information, making the technique universally applicable. The algorithm is independent of wireless communication models. However, knowledge of the model and node distribution helps estimate a parameter used in the algorithm. Further the author presented simulation results for three different communication models and two different node distributions, and show that the algorithm is able to detect wormhole attacks with a 100% detection and 0% false alarm probabilities whenever the network is connected with high probability. Even for very low density networks where chances of disconnection is very high, the detection probability remains very high.
August 13, 2009: “Randomized Rounding for Solving Critical Node Detection Problem”
Presented by : Ying Xuan
Abstract
Critical Vertex/Edge Detection has been shown to be a promising but tough problem due to the difficulties in optimizing the global pairwise connectivity. Fortunately, plenty of advanced mathematical techniques have been proposed to solve this problem, but a majority of them can only provide pseudo-approximation algorithms. To this end, we investigated an Integer Program (IP) formulation of the Critical Node(Vertex) Detection problem and aimed to obtain a true approximation algorithm with O(k\log n) ratio, using a randomized rounding scheme. However, some problems emeried as obstacles to complete the solution. Therefore, I would like to show our basic idea and discuss on the problems to overcome. Hopefully we could come up with helpful ideas to make it through.
Top
August 6, 2009: “Approximating the k-Multicut Problem”
Presented by : Yilin Shen
Abstract
In the talk the paper "Approximating the k-Multicut Problem" is presented in which the author studied the k-multicut problem: Given an edgeweighted undirected graph, a set of l pairs of vertices, and a target k ≤ l, find the minimum cost set of edges whose removal disconnects at least k pairs. This generalizes the well known multicut problem, where k = l. We show that the k-multicut problem on trees can be approximated within a factor of $\frac{8}{3}+\epsilon$, for any fix $\epsilon > 0$, and within $O(log^{2}nloglog n)$ on general graphs, where n is the number of vertices in the graph.For any fixed $\epsilon> 0$, we also obtain a polynomial time algorithm for k-multicut on trees which returns a solution of cost at most $(2 + \epsilon).OPT$, that separates at least $(1−\epsilon)·k$ pairs, where OPT is the cost of the optimal solution separating k pairs. The proposed techniques also give a simple 2-approximation algorithm for the multicut problem on trees using total unimodularity, matching the best known algorithm [8].
July 8, 2009: “Primal Dual Approximation Algorithms for Directed Generalized Steiner Networks”
Presented by : Nam Nguyen
July 1, 2009: “Coverage of Phenomena Cloud Using Wireless Sensor
Network”
Presented by : Ravi Tiwari
Abstract
A phenomenon that expands, shrinks, and changes its location in the contiguous space with the respect to time is called a phenomena cloud.
For instance: forest fire, Mud Flow, Bio-chemical material diffusion, Oil spills. In the presentation I discuss the solution to the phenomena cloud problem formulated as follows: Given a set of sensors forming a Wireless Sensor Network (WSN), represented by a graph G=(V,E). Consider a phenomena cloud occurring within the space covered by the WSN G, the problem is to cover the phenomena cloud minimizing the network resources used and maximizing the sensor network lifetime.
June 24, 2009: “Geometric Embeddings of Metric Spaces”
Presented by : Thang Dinh
Abstract
A geometric network is a graph mapped into the Euclidean plane. It is said to be a geometric spanner if the network distance between any pair of nodes is bounded by a constant times their Euclidean distance. One is interested in spanners with other useful properties such as few edges, small weight, small node degree, or small link diameter. Geometric networks and spanners play an important role in telecommunication, motion planning (robotics), pattern matching, data compression, gene analysis, and sensor networks. Apart from these applications, geometric spanners have had great impact on the construction of approximation algorithms, e.g., for the traveling salesman problem.
June 3, 2009: “Jamming Attack Detection and Countermeasures In
Wireless Sensor Network Using Ant System”
Presented by : Incheol Shin
Abstract
Sensors have varied constraints, which makes the network challenging
for communicating with its peers. In this paper, an extension to the
security of physical layer of a predictive sensor network model using
the ant system is proposed. The Denial of Service (DoS) attack on
sensor networks not only diminishes the network performance but also
affects the reliability of the information making detection of a DoS
threat is more crucial than ecovering from the attack. Hence, in this
paper, a novel approach in detecting the DoS attack is introduced and
analyzed for a variety of scenarios. The DoS attack is dependent on the
vulnerabilities in each layer, with the physical layer being the lowest
layer and the first to be attacked by jammers. In this paper, the
physical layer DoS attack is analyzed and a defense mechanism is
proposed. Classification of the jammer under various attack scenarios
is formulated to predict the genunity of the DoS attacks on the sensor
nodes using receiver operating characteristics (ROC). This novel
approach helps in achieving maximum reliability on DoS claims improving
the Quality of Service (QoS) of WSN.
May 27, 2009: “Euclidean Squared Metric based SDP for graph
partitioning problems” (Contd)
Presented by : Ying Xuan
May 21, 2009: “Euclidean Squared Metric based SDP for graph
partitioning problems”
Presented by : Ying Xuan
Abstract
Euclidean Squared Metric Assignment has been widely adopted and combined with Semi-Definite Programming for various graph partitioning problems, for example minimum bisection, sparsest cut, k-partitioning. Thanks to existing fruitful geometric embedding results(distortion), a underlying $\sqrt{\log n}$ approximation algorithm has been obtained toward this problem family. In this talk, I would like to briefly go through two papers: ARV '04(Geometric Embeddings, Graph Partitioning, and Expander flows) and SODA' 09 (Partitioning graphs into balanced components).
For the first one, I would use its online slides, which include fundamental concepts about the SDP formulation based on l_2^2 assignment and randomized projection rounding. You could refer to it via this website: www.cs.princeton.edu/~arora/talks/geomexpansion.ppt
For the second one, I am writing it and would send all of you the
slides by tomorrow noon, which will include a spreading metric-based
algorithm and corresponding analysis.