Towards a theory for securing time synchronization in wireless sensor networks

ABSTRACT

Time synchronization in highly distributed wireless systems like sensor and ad hoc networks is extremely important in order to maintain a consistent notion of time throughout the network and to support the various timing-based applications. But, cheating behavior by the participating nodes in the network can severely jeopardize the accuracy of the associated time synchronization process. Despite recent advances in this direction, a key fundamental question still remains unanswered: Is it theoretically feasible to secure distributed time synchronization protocols, given complete (or global) time and time difference information in the network?

In this paper, we attempt to answer this question with the help of sound mathematical modeling and analysis. We first formulate the problem of distributed time synchronization as a Constraint Satisfaction Problem (CSP) in a graph-based model of the network. Then, we prove that efficiently eliminating cheating behavior in distributed time synchronization protocols is combinatorially hard (NP-hard), i.e., it is highly unlikely that there exists an algorithm that solves, or even approximates, this problem in polynomial (in terms of total number of nodes) time. Due to this negative result for the general case, we focus on studying the problem for a special case of the graph-based model of the network, namely completely connected graphs. We derive an upper bound on the best possible solution quality for this problem, propose two polynomial-time approximation strategies, and present an empirical evaluation of their performance.

References

1. K. Arvind. Probabilistic Clock Synchronization in Distributed Systems. IEEE Transactions on Parallel and Distributed Systems, 5(5):474--487, 1994.
2. V. Bafna, P. Berman, and T. Fujito. A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem. SIAM Journal on Discrete Mathematics, 12(3):289--297, 1999.
3. R. Boppana and M. Halldórsson. Approximating Maximum Independent Sets by Excluding Subgraphs. BIT, 32:180--196, 1992.
4. R. Boppana and M. Halldórsson. Approximating Maximum Independent Sets by Excluding Subgraphs. BIT, 32:180--196, 1992.
5. J. Elson, L. Girod, and D. Estrin. Fine-grained Network Time Synchronization using Reference Broadcasts. ACM SIGOPS Operating Systems Review, 36:147--163, 2002.
6. G. Even, J. Naor, B. Schieber, and M. Sudan. Approximating Minimum Feedback Sets and Multicuts in Directed Graphs. Algorithmica, 20(2):151--174, 1998.
7. F. V. Fomin, S. Gaspers, and A. V. Pyatkin. Finding a Minimum Feedback Vertex Set in Time o(1.7548n). In IWPEC 2006: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation, pages 184--191, 2006.
8. T. Gallai. Maximum-minimum sätze über graphen. Acta Mathematicae, Academiae Scientiarum Hungaricae, 9:395--434, 1958.
9. S. Ganeriwal, S. Capkun, C.-C. Han, and M. B. Srivastava. Secure Time Synchronization Service for Sensor Networks. In WiSe '05: Proceedings of the 4th ACM Workshop on Wireless Security, pages 97--106, 2005.
10. S. Ganeriwal, R. Kumar, and M. B. Srivastava. Timing-sync Protocol for Sensor Networks. In SenSys'03: Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, pages 138--149, 2003.
11. S. Ganeriwal, C. Pöpper, S. Čapkun, and M. B. Srivastava. Secure Time Synchronization in Sensor Networks. ACM Transactions on Information and System Security (TISSEC), 11(4):1--35, 2008.
12. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
13. O. Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge, 2008.
14. J. Hastad. Clique is Hard to Approximate within n^/1--ε. Acta Mathematics, 182:105--142, 2002.
15. M. Jadliwala, Q. Duan, J. Xu, and S. Upadhyaya. On Extracting Consistent Graphs in Wireless Sensor Networks. International Journal of Sensor Networks (IJSNet), 2(3/4):149--162, 2007.
16. R. Karp. Complexity of Computer Computations, chapter Reducibility Among Combinatorial Problems, pages 85--104. Plenum Press, 1972.
17. L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, and V. Gurvich. Generating all Vertices of a Polyhedron is Hard. In SODA '06: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 758--765, 2006.
18. M. D. Lemmon, J. Ganguly, and L. Xia. Model-based Clock Synchronization in Networks with Drifting Clocks. In PRDC '00: Proceedings of the 2000 Pacific Rim International Symposium on Dependable Computing, pages 177--184, 2000.
19. H. Li, Y. Zheng, M. Wen, and K. Chen. A Secure Time Synchronization Protocol for Sensor Network, chapter Emerging Technologies in Knowledge Discovery and Data Mining, pages 515--526. Springer Berlin / Heidelberg, 2007.
20. H. Li, Y. Zheng, M. Wen, and K. Chen. A Secure Time Synchronization Protocol for Sensor Network, chapter Emerging Technologies in Knowledge Discovery and Data Mining, pages 515--526. Springer Berlin / Heidelberg, 2007.
21. M. Maróti, B. Kusy, G. Simon, and Ákos Ĺdeczi. The Flooding Time Synchronization Protocol. In SenSys'04: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, pages 39--49, 2004.
22. D. Mills. Internet time synchronization: The network time protocol. In Global States and Time in Distributed Systems, IEEE Computer Society Press. 1994.
23. S. B. Moon, P. Skelly, and D. Towsley. Estimation and Removal of Clock Skew from Network Delay Measurements. Technical Report UM-CS-1998-043, 1998.
24. P. P. Papadimitratos, M. Poturalski, P. Schaller, P. Lafourcade, D. Basin, S. Capkun, and J.-P. Hubaux. Secure Neighborhood Discovery: A Fundamental Element for Mobile Ad Hoc Networking. IEEE Communications Magazine, 46(2), 2008.
25. S. Ping. Delay Measurement Time Synchronization for Wireless Sensor Networks. Intel Research, IRB-TR-03-013, June 2003.
26. I. Razgon. Exact Computation of Maximum Induced Forest. In SWAT '06: Proceedings of the 10thScandinavian Workshop on Algorithm Theory, pages 160--171, 2006.
27. R. Read and R. Tarjan. Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees. Networks, 5:237--252, 1975.
28. S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach, chapter Constraint Satisfaction Problems, pages 137--160. 2 edition, 2002.
29. M. Sichitiu and C. Veerarittiphan. Simple, Accurate Time Synchronization for Wireless Sensor Networks. In WCNC 2003: Proceedings of the IEEE Wireless Communications and Networking Conference, pages 1266--1273, 2003.
30. H. Song, S. Zhu, and G. Cao. Attack-Resilient Time Synchronization for Wireless Sensor Networks. In MASS 2005: Proceedings of the 2nd IEEE International Conference on Mobile Ad Hoc and Sensor Systems, pages 765--772, 2005.
31. K. Sun, P. Ning, and C. Wang. TinySeRSync: Secure and Resilient Time Synchronization in Wireless Sensor Networks. In CCS '06: Proceedings of the 13th ACM Conference on Computer and Communications Security, pages 264--277, 2006.
32. B. Sundararaman, U. Buy, and A. D. Kshemkalyani. Clock Synchronization in Wireless Sensor Networks: A Survey. Ad-Hoc Networks, 3(3):281--323, 2005.
33. J. van Greunen and J. Rabaey. Lightweight Time Synchronization for Sensor Networks. In WSNA '03: Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications, pages 11--19, 2003.
34. Y. Xianglan, Q. Wangdong, and F. Fei. ASTS: An Agile Secure Time Synchronization Protocol for Wireless Sensor Networks. In WiCom '07: Proceedings of the 3rd International Conference on Wireless Communications, Networking and Mobile Computing, pages 2808--2811, 2007.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Network flows

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows

  • Randomness, geometry and discrete structures