In order to discover the available access points, a WiFi-enabled device periodically broadcasts probe requests. Traditionally, the probes encapsulate their globally unique physical addresses. By chronologically ordering the probes according to the addresses, the behavior of the user carrying the device can be analyzed over time. To offer better privacy protection, recent operating systems have been using randomized (virtual) MAC addresses in the probes, with addresses altered at unpredictable interval ranging from seconds to minutes. This fragments the path of the user into short segments, hence breaking the path continuity and defeating analytics over longer term. In this thesis, we study how to join the segments into path by concatenating and sequencing the probes of a device...[ Read more ]

In order to discover the available access points, a WiFi-enabled device periodically broadcasts probe requests. Traditionally, the probes encapsulate their globally unique physical addresses. By chronologically ordering the probes according to the addresses, the behavior of the user carrying the device can be analyzed over time. To offer better privacy protection, recent operating systems have been using randomized (virtual) MAC addresses in the probes, with addresses altered at unpredictable interval ranging from seconds to minutes. This fragments the path of the user into short segments, hence breaking the path continuity and defeating analytics over longer term. In this thesis, we study how to join the segments into path by concatenating and sequencing the probes of a device emitting virtual addresses. For generality, we do not consider the probe locations, and the number of devices is unknown.

We propose FIESEQ to construct device path. FIESEQ is based on keen observations of the Information Elements (IE) and sequence number (SEQ) in probe requests. We first identify the IE fields to be used as fingerprints to group the probes likely from the same device. Because a group may contain multiple devices, we further use the gap and growth rate of the sequence numbers in probes to path each device. Besides F-measure, we propose a novel metric called Degree of Concatenation (DOC) to evaluate the level of fragmentation of the constructed paths from a single device. Using several real-world datasets, we demonstrate that FIESEQ outperforms state-of-the-art techniques, and is effective in pathing devices with randomized virtual MAC addresses with high accuracy.