Conflict on a communication channel

ABSTRACT

Imagine that Alice wants to send a message m to Bob, and that Carol wants to prevent this. Assume there is a communication channel between Alice and Bob, but that Carol is capable of blocking this channel. Furthermore, there is a cost of S dollars to send on the channel, L dollars to listen on the channel and J to block the channel. How much will Alice and Bob need to spend in order to guarantee transmission of m?

This problem abstracts many types of conflict in information networks including: jamming attacks in wireless networks and distributed denial-of-service (DDoS) attacks on the Internet, where the costs to Alice, Bob and Carol represent an expenditure of energy or network resources. The problem allows us to quantitatively analyze the economics of information exchange in an adversarial setting and ask: Is communication cheaper than censorship?

We answer this question in the affirmative by showing that it is significantly more costly for Carol to block communication of m than for Alice to communicate it to Bob. Specifically, if S, L and J are fixed constants, and Carol spends a total of B dollars trying to block m, then Alice and Bob must spend only O(B^{φ - 1} + 1)=O(B^.62+1) dollars in expectation to transmit m, where φ = (1 + √5)/2 is the golden ratio. Surprisingly, this result holds even if (1) B is unknown to both Alice and Bob; (2) Carol knows the algorithms of Alice and Bob, but not their random bits; and (3) Carol has total knowledge of past actions of both players.

Finally, we apply our work to two problems: (1) DoS attacks in wireless sensor networks and (2) application-level DDoS attacks in a wired client-server scenario. Our applications show how our results can provide an additional tool in mitigating such attacks.

References

1. E. Addley and J. Halliday. WikiLeaks Supporters Disrupt Visa and MasterCard Sites in 'Operation Payback'. www.guardian.co.uk/world/2010/dec/08/wikileaks-visa-mastercard-operation-pay%back, 2010.
2. D. Alistarh, S. Gilbert, R. Guerraoui, Z. Milosevic, and C. Newport. Securing Your Every Bit: Reliable Broadcast in Byzantine Wireless Networks. In Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 50--59, 2010.
3. B. Awerbuch, A. Richa, and C. Scheideler. A Jamming - Resistant MAC Protocol for Single-Hop Wireless Networks. In Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pages 45--54, 2008.
4. M. Bertier, A.-M. Kermarrec, and G. Tan. Message-Efficient Byzantine Fault-Tolerant Broadcast in a Multi-Hop Wireless Sensor Network. In Proceedings of the International Conference on Distributed Computing Systems (ICDCS), pages 408--417, 2010.
5. V. Bhandari and N. H. Vaidya. On Reliable Broadcast in a Radio Network. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 138--147, 2005.
6. V. Bhandari and N. H. Vaidya. On Reliable Broadcast in a Radio Network: A Simplified Characterization. Technical report, CSL, UIUC, May 2005.
7. V. Bhandari and N. H. Vaidya. Reliable Broadcast in Wireless Networks with Probabilistic Failures. In INFOCOM, pages 715--723, 2007.
8. V. Bhandhari, J. Katz, C.-Y. Koo, and N. Vaidya. Reliable Broadcast in Radio Networks: The Bounded Collision Case. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 258 -- 264, 2006.
9. S. Dolev, S. Gilbert, R. Guerraoui, F. Kuhn, and C. Newport. The Wireless Synchronization Problem. In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (PODC), pages 190--199, 2009.
10. S. Dolev, S. Gilbert, R. Guerraoui, and C. Newport. Gossiping in a Multi-channel Radio Network: An Oblivious Approach to Coping with Malicious Interference. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 208--222, 2007.
11. S. Dolev, S. Gilbert, R. Guerraoui, and C. Newport. Secure communication over radio channels. In Proceedings of the Symposium on Principles of Distributed Computing (PODC), pages 105--114, 2008.
12. T. Eisenbarth, S. Kumar, C. Paar, A. Poschmann, and L. Uhsadel. A Survey of Lightweight-Cryptography Implementations. IEEE Design & Test of Computers, 24:522--533, 2007.
13. J. Franklin, V. Paxson, A. Perrig, and S. Savage. An Inquiry into the Nature and Causes of the Wealth of Internet Miscreants. In 14th ACM Conference on Computer and Communications Security, pages 375--388, 2007.
14. S. Gilbert, R. Guerraoui, D. Kowalski, and C. Newport. Interference-resilient information exchange. In INFOCOM, pages 2249--2257, 2009.
15. S. Gilbert, R. Guerraoui, and C. C. Newport. Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks. In International Conference On Principles Of Distributed Systems (OPODIS), pages 215--229, 2006.
16. W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-Efficient Communication Protocol for Wireless Microsensor Networks. In HICSS, pages 3005--3014, 2000.
17. D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 137--146. ACM, 2003.
18. V. King, C. Phillips, J. Saia, and M. Young. Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 243--252, 2008.
19. C.-Y. Koo. Broadcast in Radio Networks Tolerating Byzantine Adversarial Behavior. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 275--282, 2004.
20. Y. Li, W. Ye, and J. Heidemann. Energy and Latency Control in Low Duty Cycle MAC Protocols. In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), pages 676--682, 2005.
21. M. H. Manshaei, Q. Zhu, T. Alpcan, T. Bcasar, and J.-P. Hubaux. Game Theory Meets Network Security and Privacy. Technical report, Ecole Polytechnique Fédérale de Lausanne (EPFL), September 2010.
22. D. Meier, Y. A. Pignolet, S. Schmid, and R. Wattenhofer. Speed Dating Despite Jammers. In Proceedings of the International Conference on Distributed Computing in Sensor Systems (DCOSS), pages 1--14, 2009.
23. D. Niculescu. Interference Map for 802.11 Networks. In Proceedings of the Internet Measurement Conference (IMC), pages 339--350, 2007.
24. A. Pelc and D. Peleg. Broadcasting with Locally Bounded Byzantine Faults. Information Processing Letters, 93(3):109--115, 2005.
25. A. Pelc and D. Peleg. Feasibility and Complexity of Broadcasting with Random Transmission Failures. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 334--341, 2005.
26. J. Polastre, R. Szewczyk, and D. Culler. Telos: Enabling Ultra-Low Power Wireless Research. In IPSN, 2005.
27. I. Ramachandran and S. Roy. Clear Channel Assessment in Energy-Constrained Wideband Wireless Networks. IEEE Wireless Communications, 14(3):70--78, 2007.
28. A. Richa, C. Scheideler, S. Schmid, and J. Zhang. A Jamming-Resistant MAC Protocol for Multi-Hop Wireless Networks. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 179--193, 2010.
29. V. Sekar and J. V. D. Merwe. LADS: Large-Scale Automated DDoS Detection System. In Proceedings of the USENIX ATC, pages 171--184, 2006.
30. Valerie King and Cynthia Phillips and Jared Saia and Maxwell Young. Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks. Accepted to Algorithmica, 2010.
31. M. Walfish, M. Vutukuru, H. Balakrishnan, D. Karger, and S. Shenker. DDoS Defense by Offense. In Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), pages 303--314, 2006.
32. A. D. Wood and J. A. Stankovic. Denial of Service in Sensor Networks. Computer, 35(10):54--62, 2002.
33. W. Xu, W. Trappe, Y. Zhang, and T. Wood. The Feasibility of Launching and Detecting Jamming Attacks in Wireless Networks. In MobiHoc, pages 46--57, 2005.
34. M. Young and R. Boutaba. Overcoming Adversaries in Sensor Networks: A Survey of Theoretical Models and Algorithmic Approaches for Tolerating Malicious Interference. Accepted to IEEE Communications Surveys & Tutorials, 2011.

Index Terms

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems