Bi-Layer Shortest-Path Network Interdiction Game for Internet of Things

Jingwen Yan, Kaiming Xiao, Cheng Zhu, Jun Wu, Guoli Yang, Weiming ZhangSensors 2020 · DOI

TL;DR

This paper tackles the critical challenge of securing Internet of Things (IoT) systems by modeling them as a "bi-layer" network (logical and physical). They introduce a novel game where an attacker tries to find the cheapest path on the logical layer, while a defender strategically disrupts the physical layer to increase the attacker's cost. Their proposed algorithms, using Benders decomposition with a "Layer-Mapping" module and "Random-Search," efficiently find optimal defense strategies.

What Problem Does This Paper Address?

Modern IoT systems are complex, integrating functional devices (logical layer) with the underlying communication infrastructure (physical layer). This interconnectedness, while enabling powerful capabilities, also creates significant security vulnerabilities. Malicious actors can exploit these systems, causing disruptions and economic losses. A key challenge is understanding and defending against attacks that span both the logical and physical aspects of these networks. Specifically, this paper addresses the problem of network interdiction in such bi-layer systems. The attacker aims to find the shortest path (minimum cost) on the logical layer, but their actions are supported by the physical network. The defender, with a limited budget, must strategically block critical links in the physical layer to make the attacker's chosen logical path as expensive as possible. This is a generalization of the classic shortest-path network interdiction problem, but with the added complexity of nonlinear objective functions due to the inter-layer dependencies.

Methods

The authors propose a novel formulation for the "Bi-Layer Shortest-Path Network Interdiction Game" (LPNSPI) as a bi-level integer program. To solve this complex problem, they adapt and enhance the Benders decomposition algorithm, a standard technique for solving such optimization problems.

Key methodological contributions include:

  • Benders Decomposition Framework: This approach breaks down the problem into a master problem (for the defender) and a subproblem (for the attacker), iteratively refining solutions.
  • Layer-Mapping Module: This novel module addresses the non-linearity introduced by the bi-layer structure. It efficiently recalculates the status of the physical network based on the defender's strategy, avoiding redundant computations and simplifying the subproblem.
  • Random-Search Method: To accelerate convergence, this module intelligently explores near-optimal paths found by the subproblem. By adding these paths as constraints (SVIs - Supervalid Inequalities) to the master problem, it helps the algorithm converge faster to a good solution, even if not always the absolute global optimum.
  • Supervalid Inequalities (SVIs): These are mathematical constraints added to the master problem to prune the search space and speed up convergence, adapted from single-layer network interdiction problems.

Datasets

The paper evaluates their proposed algorithms on a set of generated layered networks. These networks vary in their logical and physical layer structures, including:

  • Random Networks: Generated with a certain probability of connection.
  • Small-World Networks: Characterized by high clustering and short average path lengths.
  • Scale-Free Networks: Exhibiting a power-law distribution of node degrees.
  • Grid Networks: Standard lattice structures.

Additionally, they tested their methods on a real-world bi-layer IoT network dataset obtained from scanning the internet, comprising approximately 36,409 nodes and 49,084 edges in the physical layer, and 32,490 nodes and 51,340 edges in the logical layer.

Key Insights and Ideas

  • The Interplay of Logical and Physical Layers is Crucial: The paper highlights that simply analyzing the logical or physical layer in isolation is insufficient for understanding and defending against attacks in IoT systems. The interdependencies are key.
  • Non-linearity is a Major Hurdle: The bi-layer structure introduces non-linearities that make standard single-layer interdiction algorithms ineffective. The Layer-Mapping module is a clever way to manage this.
  • Approximation Can Be Efficient: While exact solutions are ideal, the Random-Search method demonstrates that finding "good enough" solutions quickly can be highly beneficial, especially for large-scale networks. The trade-off between solution quality and computation time is well-managed.
  • Benders Decomposition is Adaptable: The paper shows that Benders decomposition, a powerful optimization technique, can be successfully adapted and enhanced to handle the complexities of bi-layer network interdiction.

Key Results

The proposed algorithms, particularly Algorithm 4 (combining Layer-Mapping and Random-Search), demonstrated significant computational efficiency compared to the basic Benders decomposition approach (Algorithm 1).

  • Speedup: Algorithm 3 (with Layer-Mapping) was substantially faster than Algorithm 1, especially for larger physical networks. Algorithm 4 further reduced computation time, particularly for the master problem.
  • Scalability: The algorithms successfully solved instances that were intractable for the basic approach, especially as the interdiction budget (R) increased. Algorithm 3 with Layer-Mapping and Random-Search could handle interdiction budgets up to 12, whereas Algorithm 1 and 3 struggled beyond 8.
  • Accuracy: While Algorithm 4 with a tunable parameter λ (approximation ratio) might yield near-optimal solutions, it achieved high accuracy (e.g., average error rates as low as 0.10% in some cases) and successfully found accurate optimal solutions in comparable scenarios.
  • Interdiction Effectiveness: Figure 4 visually demonstrates that as the interdiction budget (R) increases, the post-interdiction shortest path length (attacker's cost) also increases, confirming the effectiveness of the defender's strategies.

Limitations and Future Work

  • Approximation vs. Optimality: The Random-Search method, while accelerating convergence, introduces the possibility of near-optimal solutions. The paper acknowledges that a larger approximation ratio (λ) can lead to faster convergence but potentially higher error rates.
  • Computational Cost of Random-Search: While effective, the Random-Search module itself can consume considerable time, especially when finding many near-optimal paths.
  • Future Work: The paper suggests exploring more sophisticated methods for generating near-optimal paths and further refining the SVIs for non-optimal subproblem solutions. Investigating other decomposition techniques or metaheuristics could also be promising avenues. The authors also mention the need for further research into the practical implications of these findings for real-world IoT security.

Summary updated

Abstract

Network security is a crucial challenge facing Internet-of-Things (IoT) systems worldwide, which leads to serious safety alarms and great economic loss. This paper studies the problem of malicious interdicting network exploitation of IoT systems that are modeled as a bi-layer logical-physical network. In this problem, a virtual attack takes place at the logical layer (the layer of Things), while the physical layer (the layer of Internet) provides concrete support for the attack. In the interdiction problem, the attacker attempts to access a target node on the logical layer with minimal communication cost, but the defender can strategically interdict some key edges on the physical layer given a certain budget of interdiction resources. This setting generalizes the classic single-layer shortest-path network interdiction problem, but brings in nonlinear objective functions, which are notoriously challenging to optimize. We reformulate the model and apply Benders decomposition process to solve this problem. A layer-mapping module is introduced to improve the decomposition algorithm and a random-search process is proposed to accelerate the convergence. Extensive numerical experiments demonstrate the computational efficiency of our methods.
BibTeX
@inproceedings{yan2020bi,
  author = {Jingwen Yan and Kaiming Xiao and Cheng Zhu and Jun Wu and Guoli Yang and Weiming Zhang},
  title = {{Bi-Layer Shortest-Path Network Interdiction Game for Internet of Things}},
  booktitle = {Sensors},
  year = {2020},
  doi = {10.3390/s20205943},
}
Figure