Abstract
Modern distributed systems, such as cloud infrastructures and power grids, are under constant threat from adversarial attacks. Protecting these systems requires allocating limited resources under statistical uncertainty regarding the adversary's behavior. This paper introduces a novel decomposition-based framework for the Resource Allocation in the Presence of Adversaries (RAPA) problem. By decoupling the challenge into a chance-constrained allocation phase and a network-flow transfer phase, the proposed system learns attack patterns over time. Experimental results demonstrate that this approach converges to the performance of models with full prior knowledge while maintaining computational efficiency and minimizing operational costs.
Introduction
Defending distributed networks involves a fundamental challenge: how to distribute a limited resource budget (e.g., bandwidth, security patches, or backup power) across various nodes to minimize damage from attacks. Most existing research assumes that the defender knows the statistical properties of the adversary, such as the mean and variance of attack intensities. In practice, however, an adversary’s behavior is often a "black box."
Furthermore, redistributing resources between nodes is not instantaneous or free; it incurs significant operational costs. The RAPA problem seeks to balance two competing objectives: minimizing system damage and minimizing the cost of moving resources, all while operating under statistical uncertainty.
Problem Formulation and Methodology
The authors propose a bi-objective stochastic optimization framework solved via a two-phase decomposition approach. The notation used throughout the model is summarized in the table below.
Phase I: Chance-Constrained Allocation
Instead of predicting specific attacks, the system solves a quadratic program to ensure that system damage remains below a threshold with a specified confidence level (e.g., 95%). Using a Cantelli-type bound, the authors transform probabilistic uncertainty into a deterministic mathematical problem that can be solved efficiently using standard solvers like Gurobi.
Phase II: Minimum-Cost Network Flow
Once the optimal target resource levels ($r_i^t$) for each node are determined, the system calculates the most cost-effective way to move resources from their current locations to these targets. This is modeled as a classic linear programming network flow problem, where $x_{ij}^t$ represents the resource transferred from node $i$ to node $j$.
Iterative Learning
The model is dynamic. After each time slot, the system observes actual attack indicators ($\tilde{y}_i^t$) and updates its internal estimates of the unknown attack probabilities ($p_i$). This allows the "Un-mean" (unknown mean) algorithm to improve its defense strategy over time, eventually matching the performance of the "Kn-mean" (known mean) benchmark.
Experimental Evaluation
The framework was tested using synthetic simulations to capture the dynamic nature of adversarial interactions.
- Network Configurations: Simulations covered networks ranging from 25 to 200 nodes over 20 to 80 time slots.
- Attack Modeling: Attacks were generated using Bernoulli distributions with randomized probabilities.
- Benchmarks: The "Un-mean" method was compared against "Kn-mean" (perfect statistical knowledge), a "Greedy" heuristic (allocation based on importance and frequency), and an "Oracle" (perfect foresight of individual attacks).
Key Insights and Results
Convergence and Performance
A primary finding is the theoretical and empirical proof that the "Un-mean" system converges to the optimal solution as it gathers more data. The gap in damage between the learning algorithm and the model with perfect statistical knowledge dropped toward zero over time. The proposed method significantly outperformed the Greedy heuristic, which often failed to protect critical nodes.
The Risk-Cost Trade-off
The introduction of a tunable risk parameter, $\alpha$, allows operators to navigate the Pareto front between damage and transfer costs. A risk-averse setting spends more on resource transfers to ensure lower damage, while a risk-seeking setting accepts higher potential damage to reduce operational overhead.
Computational Efficiency
By decomposing the problem into two distinct phases, the authors maintain polynomial complexity. Large-scale instances with 200 nodes were solved in under 30 seconds on standard hardware, demonstrating the framework's suitability for real-time applications.
Conclusion and Future Work
This research provides a robust framework for network defense under uncertainty. While the current model assumes a stationary adversary and centralized control, it lays the groundwork for more complex scenarios. Future work will explore distributed decision-making and strategic adversaries that actively adapt their attack patterns in response to the defender's resource allocation.
Summary updated