Mobi-watchdog: you can steal, but you can't run!

Recent years have witnessed widespread use of mobile devices such as cell phones, laptops, and PDAs. In this paper, we propose an architecture called Mobi-Watchdog to detect mobility anomalies of mobile devices in wireless networks that track their locations regularly. Given the past mobility records of a mobile device, Mobi-Watchdog uses clustering techniques to identify the high-level structure of its mobility and then trains a HHMM (hierarchical hidden Markov model). Mobi-Watchdog raises an alert by requesting the device holder to reauthenticate himself when it finds an observed mobility trace significantly deviates from the trained model. The time complexity of the original generalized Baum-Welch algorithm, which is used for HHMM parameter reestimation, scales linearly with T³, where T is the number of locations in an observed sequence. Such a high computational cost can significantly impede deployment of Mobi-Watchdog in large-scale wireless networks in practice. To achieve better scalability, we modify this algorithm to make it scale linearly with T instead. Experimental results with realistic mobility traces demonstrate that Mobi-Watchdog detects mobility anomalies with high probability and reasonably low false alarm rates. We also show that Mobi-Watchdog has very low computational overhead, which makes it a viable candidate for mobility anomaly detection in large wireless networks.