Resilient Anomaly Detection in Cyber-Physical Systems By Amin Ghafouri Dissertation Submitted to the Faculty of the Graduate School of Vanderbilt University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY in Computer Science February 28, 2018 Nashville, Tennessee Approved: Xenofon Koutsoukos, Ph.D. Yevgeniy Vorobeychik, Ph.D. Gautam Biswas, Ph.D. Abhishek Dubey, Ph.D. Gabor Karsai, Ph.D. To my parents. ii Acknowledgments IwouldliketothankmyPh.D.advisor,Dr. XenofonKoutsoukosforhishelpandguidance. Iwould also like to thank Dr. Yevgeniy Voroboyechik, Dr. Gautam Biswas, Dr. Abhishek Dubey, and Dr. Gabor Karsai for being members of my thesis committee. In addition, I would like to thank other colleagues at Vanderbilt Univeristy who assisted me duringmystudies. Inparticular,IwouldliketothankAronLaszka,WaseemAbbas,ZhenkaiZhang, Siyuan Dai, Hamzah Abdel-aziz, Bradley Potteiger, Saqib Hasan, Hamid Zare, Hamed Khorasgani, and others at the Institute for Software Integrated Systems. iii Table of Contents Page Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Resilience in Cyber-Physical Systems (CPS) . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Attack Detection in CPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 A Brief Introduction to Anomaly Detection . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Model-Based Attack Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Game Theory for Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4 Machine Learning for Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4.1 Attack Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4.2 Adversarial Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5 Comparison to this Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3 A Game-Theoretic Approach for Selecting Optimal Thresholds for Attack Detection in Dy- namical Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.4.1 Defender’s Loss and Attacker’s Payoff. . . . . . . . . . . . . . . . . . . . . . . . . 27 3.4.2 Best-Response Attack and Optimal Threshold. . . . . . . . . . . . . . . . . . . . 28 iv 3.5 Selection of Optimal Thresholds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.5.1 Fixed Detection Thresholds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.6 Optimal Thresholds in the Presence of Faults and Attacks . . . . . . . . . . . . . . . . 36 3.7 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.7.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.7.1.1 Contamination Attack. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.7.1.2 Damage Function. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.7.2 Detector Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.7.2.1 Estimator. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.7.2.2 Detection Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.7.3 Optimal Thresholds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.7.3.1 Simulation Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.7.3.2 Sensitivity Analysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.7.3.3 Running Time. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.7.4 Random Faults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4 Optimal Detection of Faulty Traffic Sensors Used in Route Planning . . . . . . . . . . . . . 48 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.3 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.3.1 Route Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.3.2 Gaussian Process Regression. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.4 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.4.1 Transportation Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.4.2 Gaussian Process-Based Detector . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.4.2.1 Traffic Prediction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.4.2.2 Detection Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.4.2.3 False-Negative and False-Positive Trade-off . . . . . . . . . . . . . . . . . 53 4.5 Optimal Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.5.1 Optimization Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.5.2 Algorithm for Obtaining Thresholds . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.5.3 Critical Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 v 4.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.6.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.6.1.1 Traffic Data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4.6.1.2 Route Planner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.6.2 Results. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5 Application-Aware Anomaly Detection of Sensor Measurements in Cyber-Physical Systems 62 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 5.2.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.2.2 Anomaly Detection, Recovery, and Resilience . . . . . . . . . . . . . . . . . . . . 65 5.2.3 Example: Real-Time Control of Traffic Signals . . . . . . . . . . . . . . . . . . . 66 5.3 Anomaly Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.3.1 Regression-Based Anomaly Detector . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.3.1.1 Predictor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.3.1.2 Statistical Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.3.2 Detection Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.4 Application-Aware Anomaly Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.4.1 Recovery. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.4.2 Worst-Case Utility Loss Due to Detection Error . . . . . . . . . . . . . . . . . . . 72 5.4.3 Formulation of Application-Aware Detector . . . . . . . . . . . . . . . . . . . . . 74 5.5 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.5.1 Algorithm for Worst-Case Detection Error Loss Problem . . . . . . . . . . . . . . 75 5.5.2 Algorithm for Application-Aware Detection Problem . . . . . . . . . . . . . . . . 76 5.5.3 Algorithm for Application-Aware Detection in a Time Period . . . . . . . . . . . 78 5.6 Special Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.6.1 Single Detector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.6.2 Detectors with Equal Thresholds . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.7 Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6 Adversarial Regression for Stealthy Attacks in Cyber-Physical Systems . . . . . . . . . . . 87 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 vi 6.3 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.3.1 Sensor Attacks in CPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.3.2 Regression-Based Anomaly Detection. . . . . . . . . . . . . . . . . . . . . . . . . 91 6.3.2.1 Predictor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.3.2.2 Statistical Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.4 Adversarial Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.5 Analysis of Adversarial Regression Problem . . . . . . . . . . . . . . . . . . . . . . . . 94 6.5.1 Linear Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.5.2 Neural Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.5.3 Neural Network-Linear Regression Ensemble. . . . . . . . . . . . . . . . . . . . . 98 6.6 Resilient Detector Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 6.7 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.7.1 Tennessee-Eastman Process Control System . . . . . . . . . . . . . . . . . . . . . 101 6.7.2 Regression-Based Anomaly Detector . . . . . . . . . . . . . . . . . . . . . . . . . 101 6.7.3 Adversarial Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.7.4 Resilient Detector. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 7 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 vii List of Tables Table Page 2.1 Differences in Attack Detection Between IT Systems and CPS [97] . . . . . . . . . . . 9 2.2 Detection Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Errors in Anomaly Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 Summary of related work on attack detection in CPS. . . . . . . . . . . . . . . . . . . 12 3.1 List of Symbols. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2 Model Assessment on Test Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.1 Average Optimal Losses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5.1 List of Symbols. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.1 List of Symbols. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 6.2 MSE of Test Data (Original Scale) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 viii List of Figures Figure Page 2.1 Summary of related work on CPS security. . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Anomaly detection architecture. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Detector components. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 Summary of related work on game-theoretical approaches for anomaly detection in CPS. 15 2.5 Anomaly detection methods using machine learning [29]. . . . . . . . . . . . . . . . . 16 3.1 System description. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Hourly water demand during a day [92]. . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3 Trade-off between detection delay and false-positive probability (total chlorine). . . . 42 3.4 Best-responseattackagainsttheoptimaltime-dependentthresholdhasthemagnitude λ=5 and starts at k =116. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 a 3.5 Best-response attack against the optimal fixed threshold has the magnitude λ=4 and starts at k =44. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 a 3.6 The defender’s loss as a function of cost of threshold change. . . . . . . . . . . . . . . 45 3.7 The defender’s loss as a function of cost of false alarms. . . . . . . . . . . . . . . . . . 46 3.8 Running time of Algorithm 2 compared to exhaustive search. . . . . . . . . . . . . . . 47 3.9 The defender’s loss as a function of cost of false alarms for time-dependent thresholds. η∗ istheoptimalthresholdforattacksandη∗ istheoptimalthresholdforcombination A C of faults and attacks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.1 Information flow in our approach. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2 A map of traffic sensors installed in Downtown Los Angeles. . . . . . . . . . . . . . . 58 4.3 Trade-off between the false-positive and false-negative probabilities. . . . . . . . . . . 59 4.4 Reroute occurs due to a conditional undercount fault false negative. (a) Normal. (b) Fault. (Green flag is the source and red flag is the destination.) . . . . . . . . . . . . 60 4.5 Loss as a function of detection threshold. . . . . . . . . . . . . . . . . . . . . . . . . . 61 5.1 System Model. Note that in this case w =m. . . . . . . . . . . . . . . . . . . . . . . 64 5.2 Regression-Based Anomaly Detector . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.3 Architecture of Application-Aware Anomaly Detection. . . . . . . . . . . . . . . . . . 71 ix 5.4 The 3-by-3 grid. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 5.5 Each intersection in the 3-by-3 grid. For illustration, a critical and a redundant sensor are shown in the figure. For each lane, a second redundant sensor is placed with twice as much distance as the distance between the first redundant sensor and the critical sensor. All 8 total redundant sensors are used to predict the value of a sensor. . . . . 82 5.6 Trade-off between true positive and false positive errors for s . . . . . . . . . . . . . 84 EW 5.7 Utility (i.e., pressure-release) during a 2-hour interval. . . . . . . . . . . . . . . . . . . 85 6.1 Regression-Based Anomaly Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6.2 Attack Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 6.3 Ensemble of Neural Network-Linear Regression. . . . . . . . . . . . . . . . . . . . . . 98 6.4 Resilient Detector Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.5 Pressure of the reactor when a sensor attack starts at k = 0.5. After 2 hours the pressure reaches an unsafe state. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.6 MSE of Linear Regression, Neural Network, and Ensemble Model (computed with normalized data). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.7 (a) Adversarial regression for the pressure of the reactor considering different budgets. Surprisingly, linear regression outperforms neural networks. In the figure, δ is max the maximum error that can be added to the measurements of a critical sensor at a timestep. (b)Criticalityanalysisofthefivesafety-criticalsensors. Criticalityisdefined as the maximum of δ during a time interval over distance, where distance is the max difference between operating point and safety limit for a critical sensor. . . . . . . . . 105 6.8 Resilient Detector compared to Baseline. (a) Impact of Attack. (b) Number of False Positives (per day). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 x