MaxSAT Evaluation 2019 - Benchmark: Identifying Security-Critical Cyber-Physical Components in Weighted AND/OR Graphs
File(s)Benchmark-MSE19--Barrere-et-al.pdf (193.21 KB)
Accepted version
Author(s)
Barrere Cambrun, Martin
Hankin, Chris
Nicolaou, Nicolas
Eliades, Demetrios G
Parisini, Thomas
Type
Conference Paper
Abstract
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.
Date Issued
2019-11-01
Date Acceptance
2019-07-07
Citation
2019, pp.32-33
Start Page
32
End Page
33
Copyright Statement
© 2019 The Author(s)
Sponsor
Horizon2020
Identifier
https://www.imperial.ac.uk/people/m.barrere
Grant Number
Project ID: 739551
Source
MaxSAT Evaluation 2019 (affiliated with SAT 2019)
Subjects
MaxSAT benchmark
Security metrics
Industrial control systems
Cyber-physical systems
AND-OR graphs
MaxSAT resolution
Publication Status
Published
Start Date
2019-07-07
Finish Date
2019-07-12
Coverage Spatial
Lisbon, Portugal