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

ABSTRACT

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.

REFERENCES

• 1: S. V. Dongen. Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht, May 2000.
• 2: A. J. Enright, S. V. Dongen, and C. A. Ouzounis. An efficient algorthm for large-scale detection of protein families. Nucleic Acids Research, 30(7), 2002.
• 3: F. Erbas, K. Kyamakya, J. Steuer, and K. Jobmann. On the user profiles and the prediction of user movements in wireless networks. In Proceedings of IEEE PIMRC, 2002.
• 4: Shai Fine , Yoram Singer , Naftali Tishby, The Hierarchical Hidden Markov Model: Analysis and Applications, Machine Learning, v.32 n.1, p.41-62, July 1998 [doi>10.1023/A:1007469218079]
• 5: M. C. Gonzalez, C. A. Hidalgo, and A.-L. Barabasi. Understanding individual human mobility patterns. Nature, 2008.
• 6: Amit Jardosh , Elizabeth M. Belding-Royer , Kevin C. Almeroth , Subhash Suri, Towards realistic mobility models for mobile ad hoc networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939008]
• 7: J. Kim. Realistic mobility modeling and simulation for mobile wireless network in urban environments. Master's thesis, University of Deleware, 2005.
• 8: Lin Liao and Dieter F. Kautz. Extracting places and activities from gps traces using hierarchical conditional random fields. Artificial Intelligence, 2007.
• 9: http://www.washingtonpost.com/wp-dyn/content/article/2005/07/24/AR2005072%401135.html.
• 10: K. Murphy and M. Paskin. Linear time inference in hierarchical HMMs. In Advances in Neural Information Processing Systems 13. MIT Press, Cambridge, MA, 2002.
• 11: Mirco Musolesi , Stephen Hailes , Cecilia Mascolo, An ad hoc mobility model founded on social network theory, Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 04-06, 2004, Venice, Italy [doi>10.1145/1023663.1023669]
• 12: L. R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proc. of the IEEE, February 1989.
• 13: Reality mining project. http://reality.media.mit.edu/.
• 14: S. Schonfelder. Some notes on space, location and travel behavior. In Swiss Transport Research Conference, Monte Verita, Ascona, 2001.
• 15: John Scourias , Thomas Kunz, An activity-based mobility model and location management simulation framework, Proceedings of the 2nd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.61-68, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313237.313250]
• 16: B. Sun, Y. Xiao, and R. Wang. Detection of fraudulent usage in wireless networks. IEEE Trans. on Vehicular Technology, 56(6), 2007.
• 17: B. Sun, F. Yu, K. Wu, Y. Xiao, and V. C. M. Leung. Enhancing security using mobility-based anomaly detection in cellular mobile networks. IEEE Trans. on Vehicular Technology, 55(3), 2006.
• 18: http://cbs5.com/consumer/wireless.runaround.2.451677.html.
• 19: Hua-Ping Zhang , Hong-Kui Yu , De-Yi Xiong , Qun Liu, HHMM-based Chinese lexical analyzer ICTCLAS, Proceedings of the second SIGHAN workshop on Chinese language processing, p.184-187, July 11-12, 2003, Sapporo, Japan [doi>10.3115/1119250.1119280]
• 20: Jingyuan Zhang, Location management in cellular networks, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Performance, Security

Keywords:
anomaly detection, hhmm, mobility, wireless networks