A clustering-based algorithm for counting mobile devices in presence of MAC address randomization

Mobile devices are constantly sending messages on the network, containing potentially sensible and personal information. In particular, a unique identifier, called the MAC address, is a piece of private information that can be used to track the user’s location and habits. The increasing need to protect users’ privacy has led to the introduction of MAC address randomization, which has rapidly been adopted by most vendors and devices. However, its implementation is not flawless, and many studies have indicated how these limits can be exploited to defeat randomization and possibly obtain the original MAC address. In light of recent mobility and statistical applications, randomization is seen as an obstacle to obtaining truthful data, hence the need for alternative methods to overcome randomization without threatening the users’ privacy. In this thesis, we propose a clustering-based system capable of associating probe requests sent by randomized mac addresses belonging to the same device, hence counting the actual number of devices in the considered scenario. A secondary focus was addressed on testing specific features on which most existing fingerprinting techniques are based, evaluating their efficacy in recent developments. To assure an up-to-date analysis, a specific database was utilized and expanded, also providing a ground truth to evaluate future results. The study presents a comparison between two popular clustering algorithms, K-means and DBSCAN, with an accurately selected set of high entropy features. After a fine-tuning phase of the algorithms’ input parameters, from our performance analysis the K-means and DBSCAN algorithms reach satisfying results, with respective average V-measure scores of 0.69 and 0.79, showing a viable and noteworthy approach to overcome MAC randomization.

I dispositivi mobili inviano costantemente messaggi sulla rete, contenenti informazioni potenzialmente sensibili e personali. L’indirizzo MAC rappresenta un’informazione privata e univoca che può essere utilizzata per tracciare la posizione e le abitudini dell’utente. La crescente necessità di proteggere la privacy degli utenti ha portato all’introduzione della randomizzazione degli indirizzi MAC, che è stata rapidamente adottata dalla maggior parte dei produttori e dei dispositivi. Tuttavia, la sua implementazione non è impeccabile e molti studi hanno indicato come questi limiti possano essere sfruttati per sconfiggere la randomizzazione e possibilmente ottenere l’indirizzo MAC originale. Dal punto di vista dei recenti sviluppi di sistemi basati sulla mobilità (come le smart cities, sistemi di controllo della sicurezza, o pianificazione di reti wireless) la randomizzazione è vista come un ostacolo all’ottenimento di dati veritieri, da cui la necessità di metodi alternativi per superare queste tecniche senza minacciare la privacy degli utenti. In questa tesi proponiamo un sistema basato su tecniche di clustering in grado di associare le Probe Request inviate da indirizzi MAC randomizzati originati da una stessa sorgente stimando, dunque, il numero effettivo di dispositivi nello scenario considerato. Un secondo obiettivo riguarda la sperimentazione di specifiche feature su cui si basano varie tecniche di fingerprinting e de-randomizzazione, di cui è stata valutata l’efficacia all’interno del sistema. Al fine di fornire un’analisi aggiornata è stato utilizzato e ampliato uno specifico database contente una ground truth, tramite la quale è stato possibile ottenere precise misure di efficacia e accuratezza. Lo studio presenta un confronto tra due comuni algoritmi di clustering, K-means e DBSCAN, con un set accuratamente selezionato di feature ad alta entropia. Dopo una fase di messa a punto dei parametri di input degli algoritmi, dall’analisi delle prestazioni, gli algoritmi K-means e DBSCAN raggiungono risultati soddisfacenti ottenendo valori di V-measure che si aggirano attorno allo 0,69 e 0,79, mostrando un approccio valido e degno di nota per superare la randomizzazione MAC.