# 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 trafﬁc 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 ﬁrst 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 trafﬁc analysis attack for invading sensor data location privacy and essentially re-opens the problem for further examination.

preceded it. With these properties, random walk and its many variations have been used in network routing to ‘randomize’ the trafﬁc 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 ﬁrst 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 trafﬁc analysis attack for invading sensor data location privacy and essentially re-opens the problem for further examination.

MSC Code:

82B41

Keywords: