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.
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.
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