Achieving 500X Acceleration for Adversarial Robustness Verification of Tree-Based Smart Grid Dynamic Security Assessment

Chao Ren, Chunran Zou, Zehui Xiong, Han Yu, Zhao Yang Dong, Dusit Niyato

Abstract

Ensuring the security of smart grids against malicious data attacks is paramount for modern infrastructure. This paper presents ARVT (Adversarial Robustness Verification for Tree-based models), a high-speed framework designed to provide formal robustness guarantees for ensemble tree models used in Dynamic Security Assessment (DSA). By reformulating the verification of ensemble trees as a graph-theoretic maximum clique problem, the proposed method achieves up to a 564X speedup over traditional verification techniques, enabling near-real-time security monitoring.

Introduction

Dynamic Security Assessment (DSA) is a critical component of modern power systems, predicting stability following faults like short circuits. While tree-based models such as Random Forests and XGBoost offer high accuracy and speed, they are vulnerable to adversarial perturbations—small, intentional changes in sensor data (e.g., bus voltage or power generation) that can lead to misclassification. Verifying the robustness of these non-continuous "step function" models, especially in large ensembles, is computationally intensive (NP-complete), often making traditional tools too slow for real-time grid applications.

Methodology: The ARVT Framework

The authors propose two primary strategies for verification, moving from single trees to complex ensembles:

ARVT-S: Single Tree Verification

ARVT-S calculates the exact distance from an input to the nearest decision boundary. It treats each leaf node as a multi-dimensional "box" (hyper-rectangle). By identifying the minimum perturbation required to move an input point from its current leaf box into a box with a different classification label, the method provides a formal safety radius.

Figure 3: Partitioning of the input space into leaf boxes $B^i$ for a single decision tree.

ARVT-E: Ensemble Tree Verification

To handle ensembles without exponential complexity, ARVT-E maps the verification problem onto a multi-partite graph. Each layer in the graph corresponds to a tree in the ensemble, and nodes represent non-empty leaf boxes. Edges connect nodes if their respective boxes intersect across different trees. Finding a valid adversarial example is then equivalent to solving a Maximum Clique Problem. By leveraging the "bounded boxicity" property of these tree boxes, the search is significantly accelerated.

Figure 6: Mapping ensemble tree verification to a multi-partite graph to solve the Maximum Clique Problem.

Experimental Results

The framework was evaluated using the New England 39-bus system benchmark, a standard in power systems engineering. Key findings include:

  • Massive Acceleration: ARVT-E achieved a 564X speedup for GBDT models and over 500X for XGBoost and AdaBoost compared to baseline linear sum approaches. Verification of a 1,000-tree ensemble took only ~33–58 milliseconds.
  • Robustness vs. Accuracy: Higher accuracy does not equate to higher robustness. Boosting-based ensembles (GBDT, XGBoost) were found to be significantly more robust than Bagging-based models (Random Forest), despite similar accuracy levels. For instance, GBDT had a verification error of only 15.3% at a 0.5 perturbation level, while Random Forest sat at 35.2%.
  • Formal Guarantees: Unlike empirical attacks, ARVT provides a mathematical guarantee that no adversarial example exists within the calculated Robust Index for Tree-based models (RIT).

Conclusion and Future Work

ARVT represents a significant advancement in the formal verification of tree-based models for power systems. By leveraging graph theory, it overcomes the computational barriers of ensemble verification, providing a scalable and efficient tool for securing smart grid DSA. Future work will look to extend this binary classification to multi-class stability assessment and incorporate physical grid constraints into the perturbation models.

Summary updated

Abstract

Dear Editor, This letter presents a novel and efficient adversarial robustness verification method for tree-based smart grid dynamic security assessment (DSA). Based on tree algorithms technique, the data-driven smart grid DSA has received significant research interests in recent years. However, the well-trained tree-based DSA models with high accuracy are always vulnerable caused by some physical noises or attacks, which can misclassify the DSA results. Only with the accuracy index is not enough to represent the performance of the tree-based DSA models. To provide formal robustness guarantee and select the trusted tree-based DSA models, this letter proposes an efficient adversarial robustness verification strategy with a sound robust index to quantify the ability of tree-based DSA models against any adversarial attack. Analysis results verifies the proposed strategy can achieve up to ∼564X speedup.
BibTeX
@article{ren2024achieving,
  author = {Chao Ren and Chunran Zou and Zehui Xiong and Han Yu and Zhao Yang Dong and Dusit Niyato},
  title = {{Achieving 500X Acceleration for Adversarial Robustness Verification of Tree-Based Smart Grid Dynamic Security Assessment}},
  journal = {IEEE CAA J. Autom. Sinica},
  year = {2024},
  doi = {10.1109/jas.2023.124053},
}
Figure