Quantifying Source Location Privacy Routing Performance via Divergence and Information Loss

Matthew Bradbury and Arshad Jhumka. Quantifying Source Location Privacy Routing Performance via Divergence and Information Loss. IEEE Transactions on Information Forensics and Security, 17:3890–3905, 2022. doi:10.1109/TIFS.2022.3217385.

[ bibtex] [ file] [ project]

There has been much work investigating Source Location Privacy (SLP), including the analysis of techniques. However, one area in which there is a lack of analysis is against adversaries in the network. These adversaries can be cheaply equipped with a laptop, directional antenna and a cheap software defined radio to effectively locate the sources of valuable assets. In this work we investigated how to quantify the amount of information a non-SLP-aware routing matrix reveals to an adversary compared to a SLP-aware routing matrix via a measure of divergence. Using this measure an algorithm was developed to transform a non-SLP-aware routing matrix into an SLP-aware routing matrix.

Protectionless Routing Protocol is transformed by Algorithm 2 into a Protectionless Routing Matrix, which is tranformed by Algorithms 3 and 4 to an SLP Routing Matrix, which needs to be manually tranformed into an SLP Routing Protocol.
Methodology developed in the paper. Transform the protectionless routing protocol into protectionless routing matrix and the protectionless routing matrix into a SLP routing matrix. However, the transformation of the SLP routing matrix back into an SLP routing protocol needs to be performed manually.

This technique allowed for the transformation of the below protectionless routing matrix into the SLP-aware routing matrix. Assuming the adversary starts at the sink (node number 5) and wants to reach the source (node number 1), the SLP-aware routing matrix is considered to provide SLP as the attacker does not capture the source within the safety period. The safety period is calculated as the capture time under protectionless routing (in this case 2), multiplied by a safety factor (also set to be 2), giving a safety period of 4.

A protectionless routing protocol demonstrated on a 3 by 3 grid. The source is at the top left and the sink in the centre. Messages take the shortest path from source to sink.
Protectionless Routing Matrix
Attacker movement in response to the protectionless routing protocol shown on a 3 by 3 grid. The attacker takes the shortest path from sink to source.
Attacker movement for Protectionless Routing Matrix [Capture time=2]
An SLP routing protocol demonstrated on a 3 by 3 grid. The source is at the top left and the sink in the centre. Messages take a long path from source to sink by following nodes around the edge of the network before being delivered at the sink.
SLP-aware Routing Matrix
Attacker movement in response to the SLP routing protocol shown on a 3 by 3 grid. The attacker takes the long path around the edge of the network from sink to source caused by the SLP routing protocol.
Attacker movement for SLP-aware Routing Matrix [Capture time=6]

Using the measures of entropy and divergence we can see that while there is no uncertainty in the route taken in the SLP-aware routing matrix, the divergence when the adversary starts at the sink (node 5) is maximal for six steps. This is longer than the safety period.

Legend showing the line style for the 9 potential starting locations.
Entropy of the protectionless routing matrix showing that when the adversary starts at the sink or nodes far from the source, then there is uncertainty for the first few steps before the entropy drops to 0.
Entropy of Protectionless Routing Matrix
Entropy of the protectionless routing matrix showing that there is no entropy for all adversary start locations.
Entropy of SLP-aware Routing Matrix
Divergence between the protectionless and SLP routing matrices. When the adversary starts at the sink the routing protocols diverge for 6 steps, which is the longest period of time the matrices diverge for any start locations.
Divergence between the two

Importance

The most effective way to evaluate the performance of any Source Location privacy technique is to deploy it on hardware in real environments. However, the testbed facilities that exist do not always reflect real environments. Further, there are advantages to analysing abstract algorithms in order to gauge theoretical performance as it is much cheaper to do so. This paper filled a gap in the literature by introducing a technique to analyse performance of algorithms against an adversary with local visibility.

Perspectives

Analysing the performance of adversaries with a presence in the network is challenging, this is because their visibility changes over time as they move through the network. This is in contrast to an adversary with global visibility, whose visibility never changes. Due to this complexity assumptions need to be made about both the routing algorithms and the adversary, which has necessitated using time homogenous Markov chains, there is interesting scope for future work on the application of time inhomogenous modelling to broaden the applicability of this work to more techniques and adversaries.

Extends

This paper extends a previous shorter paper:
Matthew Bradbury and Arshad Jhumka. Understanding Source Location Privacy Protocols in Sensor Networks via Perturbation of Time Series. In IEEE INFOCOM, 1611–1619. May 2017. doi:10.1109/INFOCOM.2017.8057122.