MaxSAT Evaluation 2019 -- Benchmark: Identifying Security-Critical Cyber-Physical Components in Weighted AND/OR Graphs
This addresses the challenge of securing cyber-physical systems by offering a benchmark for evaluating methods to identify critical components, though it is incremental as it builds on existing MaxSAT and graph modeling techniques.
The paper tackles the NP-complete problem of identifying security-critical nodes in AND/OR graphs modeling Industrial Control Systems by transforming them into weighted logical formulas for solving via Weighted Partial MaxSAT, providing a benchmark with 80 cases including optimal costs and solutions.
This paper presents a MaxSAT benchmark focused on identifying critical nodes in AND/OR graphs. We use AND/OR graphs to model Industrial Control Systems (ICS) as they are able to semantically grasp intricate logical interdependencies among ICS components. However, identifying critical nodes in AND/OR graphs is an NP-complete problem. We address this problem by efficiently transforming the input AND/OR graph-based model into a weighted logical formula that is then used to build and solve a Weighted Partial MaxSAT problem. The benchmark includes 80 cases with AND/OR graphs of different size and composition as well as the optimal cost and solution for each case.