Using Harmonic Measures to Reveal Source Locations Under Random Walks

Tuesday, October 29, 2013 - 10:15am - 11:05am
Keller 3-180
Jie Gao (State University of New York, Stony Brook (SUNY))
Random walk on a graph is a Markov chain and thus is ‘memoryless’ as the next node to visit depends only on the current node and not on the sequence of events that
preceded it. With these properties, random walk and its many variations have been used in network routing to ‘randomize’ the traffic pattern and hide the location of the data sources. In this paper we examine a myth in common understanding of the memoryless property of a random walk applied for protecting source location privacy in a wireless sensor network. In particular, if one monitors only the network boundary and records the first boundary node hit by a random walk, this
distribution can be related to the location of the source node. For the scenario of a single data source, a very simple algorithm by integrating along the network boundary would reveal the location of the source. We also develop a generic algorithm to reconstruct the source locations for various sources that have simple descriptions (e.g., k source locations, sources on a line segment, sources in a disk). This represents a new type of traffic analysis attack for invading sensor data location privacy and essentially re-opens the problem for further examination.
MSC Code: