Efficient Resource Allocation under Adversary Attacks: A Decomposition-Based Approach

Mansoor Davoodi, Setareh MaghsudiarXiv 2025 · DOI · arXiv

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.

Table 1: Summary of notation used in the RAPA framework.

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

Abstract

We address the problem of allocating limited resources in a network under persistent yet statistically unknown adversarial attacks. Each node in the network may be degraded, but not fully disabled, depending on its available defensive resources. The objective is twofold: to minimize total system damage and to reduce cumulative resource allocation and transfer costs over time. We model this challenge as a bi-objective optimization problem and propose a decomposition-based solution that integrates chance-constrained programming with network flow optimization. The framework separates the problem into two interrelated subproblems: determining optimal node-level allocations across time slots, and computing efficient inter-node resource transfers. We theoretically prove the convergence of our method to the optimal solution that would be obtained with full statistical knowledge of the adversary. Extensive simulations demonstrate that our method efficiently learns the adversarial patterns and achieves substantial gains in minimizing both damage and operational costs, comparing three benchmark strategies under various parameter settings.
BibTeX
@misc{davoodi2025efficient,
  author = {Mansoor Davoodi and Setareh Maghsudi},
  title = {{Efficient Resource Allocation under Adversary Attacks: A Decomposition-Based Approach}},
  year = {2025},
  eprint = {2506.23442},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.23442},
}
Figure