A resource-competitive jamming defense
Tóm tắt
Consider a scenario where Alice wishes to send a message m to Bob in a time-slotted wireless network. However, there exists an adversary, Carol, who aims to prevent the transmission of m by jamming the communication channel. There is a per-slot cost of 1 to send, receive or jam m on the channel, and we are interested in how much Alice and Bob need to spend relative to Carol in order to guarantee communication. Our approach is to design an algorithm in the framework of resource-competitive analysis where the cost incurred by correct network devices (i.e., Alice and Bob) is parameterized by the cost incurred by faulty devices (i.e., Carol). We present an algorithm that guarantees the successful transmission of m and has the following property: if Carol incurs a cost of
$$T$$
to jam, then both Alice and Bob have a cost of
$$O(T^{\varphi - 1} + 1)=O(T^{.62}+1)$$
in expectation, where
$$\varphi = (1+ \sqrt{5})/2$$
is the golden ratio. In other words, it possible for Alice and Bob to communicate while incurring asymptotically less cost than Carol. We generalize to the case where Alice wishes to send m to n receivers, and we achieve a similar result. Our findings hold even if (1)
$$T$$
is unknown to either party; (2) Carol knows the algorithms of both parties, but not their random bits; (3) Carol can jam using knowledge of past actions of both parties; and (4) Carol can jam reactively, so long as there is sufficient network traffic in addition to m.
Tài liệu tham khảo
Abraham, I., Alvisi, L., Halpern, J.Y.: Distributed computing meets game theory: combining insights from two fields. SIGACT News 42(2), 69–76 (2011)
Aiyer, A.S., Alvisi, L., Clement, A., Dahlin, M., Martin, J.-P., Porth, C.: BAR fault tolerance for cooperative services. In: Proceedings of the 20th ACM Symposium on Operating Systems Principles, pp. 45–58 (2005)
Alistarh, D., Gilbert, S., Guerraoui, R., Milosevic, Z., Newport, C.: Securing your every bit: reliable broadcast in byzantine wireless networks. In: Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 50–59 (2010)
Anantharamu, L., Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Medium access control for adversarial channels with jamming. In: Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 89–100 (2011)
Aschenbruck, N., Gerhards-Padilla, E., Martini, P.: Simulative evaluation of adaptive jamming detection in wireless multi-hop networks. In: Proceedings of the 30th International Conference on Distributed Computing Systems Workshops, pp. 213–220 (2010)
Ashraf, F., Hu, Y.-C., Kravets, R.: Demo: bankrupting the jammer. In: Proceedings of the 9th International Conference on Mobile Systems, Applications, and Services (MobiSys) (2011)
Awerbuch, B., Richa, A., Scheideler, C.: A jamming-resistant MAC protocol for single-hop wireless networks. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pp. 45–54 (2008)
Bardwell, J.: Converting Signal Strength Percentage to dBm Values (2002)
Bayraktaroglu, E., King, C., Liu, X., Noubir, G., Rajaraman, R., Thapa, B.: On the performance of IEEE 802.11 under jamming. In: Proceedings of the International Conference on Computer Communications (INFOCOM), pp. 1265–1273 (2008)
Bender, M.A., Fineman, J.T., Gilbert, S., Young, M.: How to scale exponential backoff: constant throughput, polylog access attempts, and robustness. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 636–654 (2016)
Bender, M.A., Fineman, J.T., Movahedi, M., Saia, J., Dani, V., Gilbert, S., Pettie, S., Young, M.: Resource-competitive algorithms. SIGACT News 46(3), 57–71 (2015)
Bertier, M., Kermarrec, A.-M., Tan, G.: Brief announcement: reliable broadcast tolerating byzantine faults in a message-bounded radio network. In: Proceedings of the 22nd International Symposium on Distributed Computing (DISC), pp. 516–517 (2008)
Bertier, M., Kermarrec, A.-M., Tan, G.: Message-efficient byzantine fault-tolerant broadcast in a multi-hop wireless sensor network. In: Proceedings of the International Conference on Distributed Computing Systems (ICDCS), pp. 408–417 (2010)
Bhandari, V., Vaidya, N.H.: On reliable broadcast in a radio network. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 138–147 (2005)
Bhandari, V., Vaidya, N.H.: On reliable broadcast in a radio network: a simplified characterization. Technical Report. CSL, UIUC (2005)
Bhandari, V., Vaidya, N.H.: Reliable broadcast in wireless networks with probabilistic failures. In: Proceedings of the International Conference on Computer Communications (INFOCOM), pp. 715–723 (2007)
Bhandhari, V., Katz, J., Koo, C.-Y., Vaidya, N.: Reliable broadcast in radio networks: the bounded collision case. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 258–264 (2006)
Castro, M., Druschel, P., Ganesh, A., Rowstron, A., Wallach, D.S.: Secure routing for structured peer-to-peer overlay networks. In: 5th Usenix Symposium on Operating Systems Design and Implementation (OSDI), pp. 299–314 (2002)
Clement, A., Napper, J., Li, H., Martin, J.-P., Alvisi, L., Dahlin, M.: Theory of BAR games. In: Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing, pp. 358–359 (2007)
Crossbow: MICAz Wireless Measurement System. http://www.openautomation.net/uploadsproductos/micaz_datasheet.pdf
David Goldman CNN: FCC to Marriott: Never Try to Block Wi-Fi Again (2015). http://money.cnn.com/2015/01/27/technology/fcc-wifi-hotel/
Dani, V.: Resource-competitive error correction. In: Proceedings of the 10th ACM International Workshop on Foundations of Mobile Computing, pp. 53–58 (2014)
Dani, V., Hayes, T., Movahedi, M., Saia, J., Young, M.: Interactive communication with unknown noise rate. Inf. Comput. (2017) (In press)
Dani, V., Movahedi, M., Saia, J., Young, M.: Interactive communication with unknown noise rate. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 575–587 (2015)
Deng, J., Varshney, P.K., Haas, Z.J.: A New Backoff Algorithm for the IEEE 802.11 Distributed Coordination Function. http://surface.syr.edu/eecs/85/
Dolev, S., Gilbert, S., Guerraoui, R., Kuhn, F., Newport, C.: The wireless synchronization problem. In: Proceedings of the 28th ACM symposium on Principles of distributed computing, Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 190–199 (2009)
Dolev, S., Gilbert, S., Guerraoui, R., Newport, C.: 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), pp. 208–222 (2007)
Dolev, S., Gilbert, S., Guerraoui, R., Newport, C.: Secure communication over radio channels. In: Proceedings of the Symposium on Principles of Distributed Computing (PODC), pp. 105–114 (2008)
Douceur, J.: The sybil attack. In: Proceedings of the Second International Peer-to-Peer Symposium (IPTPS), pp. 251–260 (2002)
Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, pp. 139–147 (1993)
Emek, Y., Wattenhofer, R.: Frequency hopping against a powerful adversary. In: Proceedings of the 27th International Symposium Distributed Computing (DISC), pp. 329–343 (2013)
Federal Communications Commission (FCC): Jammer Enforcement (2017). https://www.fcc.gov/general/jammer-enforcement
Ganeriwal, S., Pöpper, C., C̆apkun, S., Srivastava, M.B.: Secure time synchronization in sensor networks. ACM Trans. Inf. Syst. Secur. 11, 23 (2008)
Gilbert, S., Guerraoui, R., Kowalski, D., Newport, C.: Interference-resilient information exchange. In: Proceedings of the International Conference on Computer Communications (INFOCOM), pp. 2249–2257 (2009)
Gilbert, S., Guerraoui, R., Newport, C.C.: Of malicious motes and suspicious sensors: on the efficiency of malicious interference in wireless networks. In: International Conference On Principles Of Distributed Systems (OPODIS), pp. 215–229 (2006)
Gilbert, S., King, V., Pettie, S., Porat, E., Saia, J., Young, M.: (Near) optimal resource-competitive broadcast with jamming. In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’14, pp. 257–266 (2014)
Gilbert, Seth, King, Valerie, Saia, Jared, Young, Maxwell: Resource-Competitive Analysis: A New Perspective on Attack-Resistant Distributed Computing. In: Proceedings of the \(8^{th}\) ACM International Workshop on Foundations of Mobile Computing, (2012)
Gilbert, S., Kowalski, D.R.: Trusted computing for fault-prone wireless networks. In: Proceedings of the 24th International Symposium, Distributed Computing (DISC), pp. 359–373 (2010)
Gilbert, S., Newport, C., Zheng, C.: Who are you? Secure identities in ad hoc networks. In: Proceedings of the 28th International Symposium on Distributed Computing (DISC), pp. 227–242 (2014)
Gilbert, S., Young, M.: Making evildoers pay: resource-competitive broadcast in sensor networks. In: Proceedings of the 31th Symposium on Principles of Distributed Computing (PODC), pp. 145–154 (2012)
Gilbert, S., Zheng, C.: SybilCast: broadcast on the open airwaves. In: Proceedings of the 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 130–139 (2013)
Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H.: Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS), pp. 3005–3014 (2000)
Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 617–643 (2000)
Karlof, C., Sastry, N., Wagner, D.: TinySec: a link layer security architecture for wireless sensor networks. In: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys), pp. 162–175 (2004)
King, V., Phillips, C., Saia, J., Young, M.: Sleeping on the job: energy-efficient and robust broadcast for radio networks. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 243–252 (2008)
King, V., Phillips, C.A., Saia, J., Young, M.: Sleeping on the job: energy-efficient and robust broadcast for radio networks. Algorithmica 61(3), 518–554 (2011)
King, V., Saia, J., Young, M.: Conflict on a communication channel. In: Proceedings of the 30th Symposium on Principles of Distributed Computing (PODC), pp. 277–286 (2011)
Koo, C.-Y.: Broadcast in radio networks tolerating byzantine adversarial behavior. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 275–282 (2004)
Law, Y.W., Doumen, J., Hartel, P.: Survey and Benchmark of Block Ciphers for Wireless Sensor Networks. ACM Trans. Sens. Netw. 2(1), 65–93 (2006)
Li, F., Mittal, P., Caesar, M., Borisov, N.: SybilControl: practical sybil defense with computational puzzles. In: Proceedings of the Seventh ACM Workshop on Scalable Trusted Computing, STC ’12, pp. 67–78 (2012)
Li, H.C., Clement, A., Wong, E.L., Napper, J., Roy, I., Alvisi, L., Dahlin, M.: BAR gossip. In: Proceedings of the Seventh Symposium on Operating Systems Design and Implementation, pp. 191–204 (2006)
Li, Y., Ye, W., Heidemann, J.: Energy and latency control in low duty cycle MAC protocols. In: Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), pp. 676–682 (2005)
Lichtman, M., Reed, J.H., Clancy, T.C., Norton, M.: Vulnerability of LTE to hostile interference. In: IEEE Global Conference on Signal and Information Processing, pp. 285–288 (2013)
Lin, G., Noubir, G.: On link layer denial of service in data wireless LANs. Wirel. Commun. Mob. Comput. 5(3), 273–284 (2005)
Liu, D., Ning, P.: Multi-level \(\mu \)TESLA: broadcast authentication for distributed sensor networks. ACM Trans. Embed. Comput. Syst. 3, 800–836 (2004)
Liu, X., Noubir, G., Sundaram, R., Tan, S.: SPREAD: foiling smart jammers using multi-layer agility. In: Proceedings of the International Conference on Computer Communications (INFOCOM), pp. 2536–2540 (2007)
Liu, X., Yang, X., Xia, Y.: NetFence: preventing internet denial of service from inside out. In: Proceedings of the ACM SIGCOMM 2010 Conference, pp. 255–266 (2010)
Manshaei, M.H., Zhu, Q., Tansu, A., Bacşar, T., Hubaux, J.-P.: Game theory meets network security and privacy. ACM Comput. Surv. 45(3), 25:1–25:39 (2013)
Meier, D., Pignolet, Y.A., Schmid, S., Wattenhofer, R.: Speed dating despite jammers. In: Proceedings of the International Conference on Distributed Computing in Sensor Systems (DCOSS), pp. 1–14 (2009)
Merkle, R.C.: Secure communications over insecure channels. Commun. ACM 21(4), 294–299 (1978)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Navda, V., Bohra, A., Ganguly, S., Rubenstein, D.: Using channel hopping to increase 802.11 resilience to jamming attacks. In: Proceedings of the International Conference on Computer Communications (INFOCOM), pp. 2526–2530 (2007)
Niculescu, D.: Interference map for 802.11 networks. In: Internet Measurement Conference (IMC), pp. 339–350 (2007)
Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
Ogierman, A., Richa, A., Scheideler, C., Schmid, S., Zhang, J.: Competitive MAC under adversarial SINR. In: Proceedings of the International Conference on Computer Communications (INFOCOM), pp. 2751–2759 (2014)
Parno, B., Wendlandt, D., Shi, E., Perrig, A., Maggs, B., Hu, Y.-C.: Portcullis: protecting connection setup from denial-of-capability attacks. In: Proceedings of the ACM SIGCOMM 2007 Conference, pp. 289–300 (2007)
Pelc, A., Peleg, D.: Feasibility and complexity of broadcasting with random transmission failures. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 334–341 (2005)
Phillips, C.A., Stein, C., Torng, E., Wein, J.: Optimal time-critical scheduling via resource augmentation. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pp. 140–149 (1997)
Polastre, J., Szewczyk, R., Culler, D.: Telos: enabling ultra-low power wireless research. In: IPSN (2005)
Ramachandran, I., Das, A.K., Roy, S.: Analysis of the contention access period of IEEE 802.15.4 MAC. ACM Trans. Sens. Netw. 3(1), 4 (2007)
Ramachandran, I., Roy, S.: Clear channel assessment in energy-constrained wideband wireless networks. IEEE Wirel. Commun. 14(3), 70–78 (2007)
Richa, A., Scheideler, C., Schmid, S., Zhang, J.: A jamming-resistant mac protocol for multi-hop wireless networks. In: Proceedings of the International Symposium on Distributed Computing (DISC), pp. 179–193 (2010)
Richa, A., Scheideler, C., Schmid, S., Zhang, J.: Competitive and fair medium access despite reactive jamming. In: Proceedings of the 31st International Conference on Distributed Computing Systems (ICDCS), pp. 507–516 (2011)
Richa, A., Scheideler, C., Schmid, S., Zhang, J.: Competitive and fair throughput for co-existing networks under adversarial interference. In: Proceedings of the 31st ACM Symposium on Principles of Distributed Computing (PODC), pp. 291–300 (2012)
Robinson, S.: The price of anarchy. SIAM News 37(5), 1–4 (2004)
Sleator, D., Tarjan, R.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985)
Srinivasan, K., Levis, P.: RSSI is under appreciated. In: EmNets (2006)
Steve Schmadeke Chicago Tribune: Man accused of jamming calls on red line ‘disturbed by people talking around him’ (2016). http://www.chicagotribune.com/news/local/breaking/ct-cell-phone-jamming-red-line-20160309-story.html
Tegeler, F., Fu, X.: SybilConf: computational puzzles for confining sybil attacks. In: Proceedings of the IEEE Conference on Computer Communications Workshops (INFOCOM), pp. 1–2 (2010)
Vaikuntanathan, V.: Brief announcement: broadcast in radio networks in the presence of byzantine adversaries. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) (2005)
Vilaça, X., Denysyuk, O., Rodrigues, L.: Asynchrony and collusion in the n-party BAR transfer problem. In: Proceedings of the 19th International Conference on Structural Information and Communication Complexity (SIROCCO), pp. 183–194 (2012)
Walfish, M., Vutukuru, M., Balakrishnan, H., Karger, D., Shenker, S.: DDoS Defense by Offense. In: Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), pp. 303–314 (2006)
Walters, J.P., Liang, Z., Shi, W., Chaudhary, V.: Security in Distributed, Grid, Mobile, and Pervasive Computing. Chapter 16: Wireless Sensor Network Security: A Survey. Auerbach Publications, Boca Raton (2007)
Watro, R., Kong, D., Cuti, S., Gariner, C., Lynn, C., Kruus, P.: TinyPK: securing sensor networks with public key technology . In: Proceedings of the 2nd ACM Workshop on Security of Ad Hoc and Sensor Networks (SASN), pp. 59–64 (2004)
Wilhelm, M., Martinovic, I., Schmitt, J.B., Lenders, V.: Short paper: reactive jamming in wireless networks: how realistic is the threat? In: Proceedings of the Fourth ACM Conference on Wireless Network Security, pp. 47–52. WiSec (2011)
Wood, A.D., Stankovic, J.A.: Denial of service in sensor networks. Computer 35(10), 54–62 (2002)
Xu, W., Ma, K., Trappe, W., Zhang, Y.: Jamming sensor networks: attack and defense strategies. IEEE Netw. 20(3), 41–47 (2006)
Xu, W., Trappe, W., Zhang, Y., Wood, T.: The feasibility of launching and detecting jamming attacks in wireless networks. In: Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 46–57 (2005)
Ye, W., Heidemann, J., Estrin, D.: An energy-efficient MAC protocol for wireless sensor networks. In: Proceedings of the International Conference on Computer Communications (INFOCOM), pp. 1567–1576 (2002)
Young, M., Boutaba, R.: Overcoming adversaries in sensor networks: a survey of theoretical models and algorithmic approaches for tolerating malicious interference. IEEE Commun. Surv. Tutor. 13(4), 617–641 (2011)