Network Interdiction Using Adversarial Traffic Flows
Traditional network interdiction refers to the problem of an interdictor trying to reduce the throughput of network users by removing network edges. In this paper, we propose a new paradigm for network interdiction that models scenarios, such as stealth DoS attack, where the interdiction is performe...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020
|
| Online Access: | https://hdl.handle.net/1721.1/126285 |
| _version_ | 1826216263543685120 |
|---|---|
| author | Fu, Xinzhe. Modiano, Eytan H |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Fu, Xinzhe. Modiano, Eytan H |
| author_sort | Fu, Xinzhe. |
| collection | MIT |
| description | Traditional network interdiction refers to the problem of an interdictor trying to reduce the throughput of network users by removing network edges. In this paper, we propose a new paradigm for network interdiction that models scenarios, such as stealth DoS attack, where the interdiction is performed through injecting adversarial traffic flows. Under this paradigm, we first study the deterministic flow interdiction problem, where the interdictor has perfect knowledge of the operation of network users. We show that the problem is highly inapproximable on general networks and is NP-hard even when the network is acyclic. We then propose an algorithm that achieves a logarithmic approximation ratio and quasi-polynomial time complexity for acyclic networks through harnessing the submodularity of the problem. Next, we investigate the robust flow interdiction problem, which adopts the robust optimization framework to capture the case where definitive knowledge of the operation of network users is not available. We design an approximation framework that integrates the aforementioned algorithm, yielding a quasi-polynomial time procedure with poly-logarithmic approximation ratio for the more challenging robust flow interdiction. Finally, we evaluate the performance of the proposed algorithms through simulations, showing that they can be efficiently implemented and yield near-optimal solutions. |
| first_indexed | 2024-09-23T16:44:55Z |
| format | Article |
| id | mit-1721.1/126285 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:44:55Z |
| publishDate | 2020 |
| publisher | IEEE |
| record_format | dspace |
| spelling | mit-1721.1/1262852022-09-29T21:15:29Z Network Interdiction Using Adversarial Traffic Flows Fu, Xinzhe. Modiano, Eytan H Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Traditional network interdiction refers to the problem of an interdictor trying to reduce the throughput of network users by removing network edges. In this paper, we propose a new paradigm for network interdiction that models scenarios, such as stealth DoS attack, where the interdiction is performed through injecting adversarial traffic flows. Under this paradigm, we first study the deterministic flow interdiction problem, where the interdictor has perfect knowledge of the operation of network users. We show that the problem is highly inapproximable on general networks and is NP-hard even when the network is acyclic. We then propose an algorithm that achieves a logarithmic approximation ratio and quasi-polynomial time complexity for acyclic networks through harnessing the submodularity of the problem. Next, we investigate the robust flow interdiction problem, which adopts the robust optimization framework to capture the case where definitive knowledge of the operation of network users is not available. We design an approximation framework that integrates the aforementioned algorithm, yielding a quasi-polynomial time procedure with poly-logarithmic approximation ratio for the more challenging robust flow interdiction. Finally, we evaluate the performance of the proposed algorithms through simulations, showing that they can be efficiently implemented and yield near-optimal solutions. United States. Defense Threat Reduction Agency (Grant HDTRA1-13-1-0021) United States. Defense Threat Reduction Agency (Grant HDTRA1-14-1-0058) National Science Foundation (U.S.) (Grant CNS-1735463) 2020-07-21T18:37:35Z 2020-07-21T18:37:35Z 2019-04 2019-01 2019-10-30T16:51:09Z Article http://purl.org/eprint/type/ConferencePaper 9781728105154 https://hdl.handle.net/1721.1/126285 Fu, Xinzhe and Eytan Modiano. “Network Interdiction Using Adversarial Traffic Flows.” IEEE INFOCOM 2019, Paris, April 29-May 2, 2019, IEEE © 2019 The Author(s) en 10.1109/INFOCOM.2019.8737475 IEEE INFOCOM 2019 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf IEEE MIT web domain |
| spellingShingle | Fu, Xinzhe. Modiano, Eytan H Network Interdiction Using Adversarial Traffic Flows |
| title | Network Interdiction Using Adversarial Traffic Flows |
| title_full | Network Interdiction Using Adversarial Traffic Flows |
| title_fullStr | Network Interdiction Using Adversarial Traffic Flows |
| title_full_unstemmed | Network Interdiction Using Adversarial Traffic Flows |
| title_short | Network Interdiction Using Adversarial Traffic Flows |
| title_sort | network interdiction using adversarial traffic flows |
| url | https://hdl.handle.net/1721.1/126285 |
| work_keys_str_mv | AT fuxinzhe networkinterdictionusingadversarialtrafficflows AT modianoeytanh networkinterdictionusingadversarialtrafficflows |