Applied Science, Faculty of
Electrical and Computer Engineering, Department of
DSpace
UBCV
Kashyap, Aarti
Master of Applied Science - MASc
University of British Columbia
Cyber-Physical Systems (CPS) are deployed in many mission-critical applications such as medical devices (e.g., an Artificial Pancreas System (APS)), autonomous vehicular systems (e.g., self-driving cars, unmanned aerial vehicles) and aircraft control management systems (e.g., Horizontal Collision Avoidance System (HCAS) and Collision Avoidance System-Xu (ACAS-XU)). Ensuring correctness is becoming more difficult as these systems adopt new technology, such as Deep Neural Network (DNN), to control these systems. DNN are black-box algorithms whose inner workings are complex and difficult to discern. As such, understanding their vulnerabilities is also complex and difficult. We identify a new vulnerability in these systems and demonstrate how to synthesize a new category of attacks Ripple False Data Injection Attacks (RFDIA) in them by perturbing specific inputs, by minimal amounts, to stealthily change the DNN’s output. These perturbations propagate as ripples through multiple DNN layers and can lead to corruptions that can be fatal. We demonstrate that it is possible to construct such attacks efficiently by identifying the DNN’s critical inputs. The critical inputs are those that affect the final outputs the most on being perturbed. Understanding this new class of attacks sets the stage for developing methods to mitigate vulnerabilities. Our attack synthesis technique is based on modeling the attack as an optimization problem using Mixed Integer Linear Programming (MILP). We define an abstraction for DNN-based CPS that allows us to automatically: 1) identify the critical inputs, and 2) find the smallest perturbations that produce output changes. We demonstrate our technique on three practical CPS with two mission-critical applications in increasing order of complexity: Medical systems (APS) and aircraft control management systems (HCAS and ACAS-XU). Our key observations for scaling our technique to complex systems such as ACAS-XU were to define: 1) appropriate intervals for their inputs and the outputs, and 2) attack specific objective (cost) functions in the abstraction.
Security Analysis of Deep Neural Network BasedCyber-Physical SystemsbyAarti KashyapB. Technology, College of Engineering Pune, 2018A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of Applied ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Electrical and Computer Engineering)The University of British Columbia(Vancouver)August 2020© Aarti Kashyap, 2020The following individuals certify that they have read, and recommend to the Fac-ulty of Graduate and Postdoctoral Studies for acceptance, the thesis entitled:Security Analysis of Deep Neural Network Based Cyber-Physical Sys-temssubmitted by Aarti Kashyap in partial fulfillment of the requirements for the de-gree of Master of Applied Science in Electrical and Computer Engineering.Examining Committee:Karthik Pattabiraman, Electrical and Computer EngineeringSupervisorMargo Seltzer, Computer ScienceCommittee memberiiAbstractCyber Physical Systems (CPS) are deployed in many mission-critical applicationssuch as medical devices (e.g., an Artifical Pancreas System (APS)), autonomousvehicular systems (e.g., self-driving cars, unmanned aerial vehicles) and aircraftcontrol management systems (e.g., Horizontal Collision Avoidance System (HCAS)and Collision Avoidance System-Xu (ACAS-XU)). Ensuring correctness is becom-ing more difficult as researchers adopt new technology, such as Deep Neural Net-work (DNN)s, to control these systems. DNNs are black box algorithms whoseinner workings are complex and difficult to discern. As such, understanding theirvulnerabilities is also complex and difficult.We identify a new vulnerability in these systems, and demonstrate how to syn-thesize a new category of attacks Ripple False Data Injection Attacks (RFDIA) inthem by perturbing specific inputs, by minimal amounts, to stealthily change theDNN’s output. These perturbations propagate as ripples through multiple DNN lay-ers and can lead to corruptions that can be fatal. We demonstrate that it is possibleto construct such attacks efficiently by identifying the DNN’s critical inputs. Thecritical inputs are those that affect the final outputs the most on being perturbed.Understanding this new class of attacks sets the stage for developing methods tomitigate vulnerabilities.Our attack synthesis technique is based on modeling the attack as an opti-mization problem using Mixed Integer Linear Programming (MILP). We definean abstraction for DNN-based CPS that allows us to automatically: 1) identify thecritical inputs, and 2) find the smallest perturbations that produce output changes.We demonstrate our technique on three practical CPS with two mission-critical ap-plications in increasing order of complexity: Medical systems (APS) and aircraftiiicontrol management systems (HCAS and ACAS-XU). Our key insights for scalingour technique to complex systems such as ACAS-XU were to define: 1) appropri-ate intervals for their inputs and the outputs, and 2) attack specific objective (cost)functions in the abstraction.ivLay SummaryCyber Physical systems (CPS) are systems that perform computations by continu-ous interactions with the physical environment and perform actions in the physicalenvironment based on the computations. CPS are deployed in many mission-criticalapplications such as medical devices, autonomous vehicular systems (e.g., self-driving cars, unmanned aerial vehicles), and aircraft control management systems.This mission-critical aspect of CPS suggests that ensuring their correct functioning,and complying with all safety specifications is of paramount importance. Ensuringcorrectness is becoming more difficult as these systems adopt new technology, suchas Deep Neural Networks (DNN), to control them. DNNs are black box algorithmswhose inner workings are complex and difficult to discern. As such, understandingtheir vulnerabilities is also difficult.This thesis exposes new vulnerabilities by introducing a technique to produceattacks that can alter the behavior of the system in unexpected ways. Understandingthis new class of attacks is the first step towards developing methods to mitigatethese vulnerabilities.vPrefaceI was responsible for shaping the key idea, leading the project, designing the exper-iments, analyzing the results, and writing the work. Prof. Margo Seltzer helped inwriting and editing the drafts and analyzing the results. Mubashir Iqbal contributedwith his prior knowledge and expertise in the area and helped with the experiments.Prof. Karthik Pattabiraman was responsible for overseeing the project, and provid-ing feedback throughout the project’s course.A preliminary version of this work was published in:Aarti Kashyap. 2020. ReLUSyn: Synthesizing stealthy attacks for deep neuralnetwork-based safety-critical cyber-physical systems: student research abstract. InProceedings of the 35th Annual ACM Symposium on Applied Computing (SAC’20). Association for Computing Machinery, New York, NY, USA, 227–229.DOI:https://doi.org/10.1145/3341105.3374221viTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1 Roles description . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Cyber-Physical Systems . . . . . . . . . . . . . . . . . . . . . . 62.3 Conventional Controllers for CPS . . . . . . . . . . . . . . . . . 82.4 DNN Based Controller . . . . . . . . . . . . . . . . . . . . . . . 102.4.1 Understanding DNN complexity . . . . . . . . . . . . . . 112.5 Modeling Mixed-Integer Linear Programming Problems . . . . . 132.6 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . 14vii3 Ripple Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.1 Motivating system: Artificial Pancreas System . . . . . . . . . . . 153.2 Attack Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.2.1 Strawman attacker . . . . . . . . . . . . . . . . . . . . . 173.2.2 Sophisticated Attacker . . . . . . . . . . . . . . . . . . . 173.3 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.3.1 Selecting the automated technique . . . . . . . . . . . . . 183.3.2 Mapping Mixed-Integer Linear Programming Model toDeep Neural Networks . . . . . . . . . . . . . . . . . . . 193.3.3 Modeling cost function . . . . . . . . . . . . . . . . . . . 204 ReLUSyn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.1 ReLUSyn: Overview . . . . . . . . . . . . . . . . . . . . . . . . 214.2 DNN formalism . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.3 MILP Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.4 Building the model . . . . . . . . . . . . . . . . . . . . . . . . . 264.5 Modeling cost functions for attacks . . . . . . . . . . . . . . . . . 284.6 Synthesizing attacks . . . . . . . . . . . . . . . . . . . . . . . . . 305 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315.1 Case study: APS . . . . . . . . . . . . . . . . . . . . . . . . . . 325.1.1 Experimental methodology . . . . . . . . . . . . . . . . . 325.1.2 Result Analysis . . . . . . . . . . . . . . . . . . . . . . . 335.2 Case Study: ACAS-Xu and HCAS . . . . . . . . . . . . . . . . . 345.2.1 Experimental Methodology . . . . . . . . . . . . . . . . 355.2.2 Result Analysis . . . . . . . . . . . . . . . . . . . . . . . 365.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456.1 Verification of CPS . . . . . . . . . . . . . . . . . . . . . . . . . 456.2 False Data Injection Attacks (FDIA) in traditional systems . . . . 466.3 DNN controllers in CPS . . . . . . . . . . . . . . . . . . . . . . 476.4 Deep Neural Network Security . . . . . . . . . . . . . . . . . . . 47viii7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497.1 Designing Robust DNNs . . . . . . . . . . . . . . . . . . . . . . 497.1.1 Effects of normalization and attacks . . . . . . . . . . . . 497.1.2 Effects of DNN size and attacks . . . . . . . . . . . . . . 507.2 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54ixList of TablesTable 5.1 System descriptions . . . . . . . . . . . . . . . . . . . . . . . 31Table 5.2 APS Results: The Attack column consists of the attack modelswhere our goal is to minimize the inputs, Output ranges are theoutput bounds we have set where we want to find the deltas,no. of combinations is the combinations of attacks dependingon the attack model (APS has 74 inputs) which is followed thetotal number of successful and unsuccessful attacks, peak timeto conduct an attack in each set of experiment, memory used. . 38Table 5.3 Critical Inputs - APS - 1 Input perturbed at a time. These arethe safe ranges that we obtain from the specification documentfor a patient. We perturb inputs . . . . . . . . . . . . . . . . . 39Table 5.4 HCAS Results: The different attacks are explained in the At-tack column which depends on the order of the outputs and theranges of the deltas, the number of inputs to be perturbed areselected by the attacker for conducting each attack, the totalnumber of combinations are calculated based on the total num-ber of inputs and the inputs selected to be perturbed, the peaktime is the maximum time it took to test for an attack from thecombinations, X indicates that the experiments timed out. . . . 40Table 5.5 HCAS Results continued . . . . . . . . . . . . . . . . . . . . 41Table 5.6 HCAS Results continued . . . . . . . . . . . . . . . . . . . . 42xTable 5.7 ACAS-Xu Results: The different attacks are explained in theAttack column which depends on the order of the outputs andthe ranges of the deltas, the number of inputs to be perturbedare selected by the attacker for conducting each attack, the totalnumber of combinations are calculated based on the total num-ber of inputs and the inputs selected to be perturbed, the peaktime is the maximum time it took to test for an attack from thecombinations, X indicates that the experiments timed out. . . . 43Table 5.8 Results Summary . . . . . . . . . . . . . . . . . . . . . . . . 44xiList of FiguresFigure 2.1 Architecture of a CPS . . . . . . . . . . . . . . . . . . . . . 6Figure 2.2 Artifical Pancreas System components [1] . . . . . . . . . . . 6Figure 2.3 General structure of a open and closed-loop systems [2] . . . 7Figure 2.4 The block diagram of the position control system of the quad-copter. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8Figure 2.5 Perceptron node [32] . . . . . . . . . . . . . . . . . . . . . . 11Figure 2.6 Illustration of how DNN controllers are replacing conventionalcontrollers. The DNN is trained offline using input-output dataobtained from different trajectories from a conventional con-troller. The DNN is shown to perform better than a conven-tional controller during real-time analysis for decision makingby Sarabakha et al. [3]. . . . . . . . . . . . . . . . . . . . . 12Figure 2.7 DNN structure . . . . . . . . . . . . . . . . . . . . . . . . . 12Figure 3.1 APS DNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15Figure 3.2 Attack model . . . . . . . . . . . . . . . . . . . . . . . . . . 17Figure 4.1 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . 22Figure 4.2 DNN structure . . . . . . . . . . . . . . . . . . . . . . . . . 22Figure 4.3 ReLU can be broken down into two linear units as shown in thefigure for x < 0 and x ≥ 0. This allows us to easily map theDNN equations in MILP models by breaking down the non-linearity inducing function. . . . . . . . . . . . . . . . . . . . 27Figure 4.4 APS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27xiiFigure 5.1 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . 32Figure 5.2 ACAS Xu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35xiiiGlossaryACAS-XU Collision Avoidance System-XuAPS Artifical Pancreas SystemAV Autonomous VehiclesCA Collision AvoidanceCPS Cyber Physical SystemsCGM Continuous Glucose MonitorDNN Deep Neural NetworkFDIA False Data Injection AttacksHCAS Horizontal Collision Avoidance SystemLP Linear ProgramsMILP Mixed Integer Linear ProgrammingNN Neural NetworkRFDIA Ripple False Data Injection AttacksRPI Raspberry PiRELU Rectified Linear UnitSMT Satisfiability Modulo TheoriesxivAcknowledgmentsI would like to thank the following: My advisor, Karthik Pattabiraman, for allowingme to pursue my ideas and explore during my masters which was my original goal.I’ve learned a lot from him.Margo Seltzer for being a constant source of inspiration that helped me pursuemy ideas fearlessly and enjoy research during my masters. Without her, this thesiswould not have been possible.Syed Mubashir Iqbal for collaborating on this work and teaching me a bunch ofstuff; working with Mubashir was one of the most fun experiences of my master’sthesis because of the infinite all-nighters we pulled off to finish the experiments inICICS 348.Mark Greenstreet, Alan Hu, Hassan Halawa and Puneet Mehrotra for patientlylistening to my half-baked ideas in the initial stages of the work that eventuallylead me to find my path.William Bowman for introducing me to the world of abstractions that helpedme understand my work a little better.Members of the computer systems reading group and static analysis readinggroup for interesting discussions that might have directly or indirectly influencedmy thinking.The multiple ’travel granting committees’ from conferences that allowed me totravel all around the world and have many interesting discussions with researcherswhich might have significantly influenced my thinking.Members of Dependable Systems and Systopia (formerly NSS) Lab for multi-ple fun hangouts.The library staff at UBC for always ordering the books I’ve asked for as soonxvas possible.All my friends (y’ all know who you are) for being there; listening to my con-stant bicker about life despite being in different timezones.Tom Lee Music store for letting me use their jam room for hours and hoursevery week since 2018. Surviving the journey without music would be impossible.Akshay Gopalakrishnan for ... everything.My ma and sister for being ok (or may be pretending to be ok) with my newlife plan every other week, thus never holding me back.xviChapter 1IntroductionCyber Physical Systems (CPS) are systems that perform computations by continu-ous interactions with the physical environment, and perform actions in the physi-cal environment based on the computations. They are increasingly being deployedfor applications [4][5][6] such as medical devices (e.g., insulin pumps and roboticsurgery equipment), failures of which could be life threatening, and hence needhigh reliability. The mission-critical aspect of CPS makes them particularly attrac-tive targets for an attacker.There have been multiple attacks demonstrated in the CPS in the past, thoughthe information of most attacks is not publicly available [7]. One of the first re-ported targeted attacks was on a Supervisory Control and Data Acquisition (SCADA)system [8] at the Maroochy Shire Council’s sewage control system in Queens-land, Australia, where an attacker caused more than 750,000 gallons of untreatedsewage water to be released into parks, resulting in clean up damages of morethan $200,000 [9]. There have also been targeted attacks demonstrated on surgicalrobots [10], pacemakers[11], airplanes [12] and cars [13]. Some targeted attacksdemonstrated in these systems also utilized glitches in the software to induce at-tacks without getting detected [14].Traditionally, CPS have used classical control theory-based models [6] [15] [16]to calculate the next output for decision making. Based on classical control-theory,these systems model the physical world via differential equations. For instance,we can model model the movement of a self-driving car using equations that in-1clude parameters (or variables) such as road friction, wind speed and direction, andengine power. Such models have low tolerance for perturbations in the values ofthese parameters, because the equations account for a subset of all possible behav-iors that can happen in reality. This behavior makes CPS vulnerable to attacks thatcan exploit the limitations by injecting a false reading of a variable [17]. Thus, anadversary can cause irreparable harm to such a system by injecting a false readingof a variable; such an attack is called an False Data Injection Attacks (FDIA). In anFDIA, an attacker compromises the measurements from the sensors in a way thatundetected errors are introduced in the outputs [18] that control the object in thereal world.Recently, Deep Neural Network (DNN) based controllers have replaced clas-sical control-theory based controllers [19] [20] [21]. Techniques used to generateinputs to mount an FDIA attack for classical control theory based controllers arenot directly applicable for DNNs, because the state space for DNN based systemsis typically much larger than for classical control theory models. In a conven-tional system, it is relatively easy to identify the function that maps changes ininput values to changes in output values, because the control theory equations arewell defined for different scenarios of output prediction. However, in a DNN, thecomputation proceeds through multiple layers and hence the input-output mappingbecomes opaque, because the DNN model is a function of the training data-set.However, a motivated attacker can figure out how to conduct such attacks ina DNN as we demonstrate in this thesis. If we are to build systems to preventor mitigate such attacks, we must first understand the fundamental nature of theseattacks. This thesis takes a first step towards preventing such attacks by introducingan automated technique to synthesize them.We use our technique to synthesize a new class of attacks for DNN based con-trollers that perturbs specific inputs to produce changes in output. We call these at-tacks Ripple False Data Injection Attacks (RFDIA)s, as they are transmitted throughthe DNN’s layers in the CPS like ripples in large puddles of water. Much like theoutward motion of waves in water when disturbed by dropping a stone, the per-turbations introduced to the inputs of a DNN ripple through the layers until theyreach the output layer. To mount a successful RFDIA attack on a DNN based con-troller, the attacker needs to minimally distort an input such that the effects of its2perturbation reach the final layer, without triggering any alarms.To mount a RFDIA, the attacker needs to identify two things:1. The critical inputs: The inputs (for the attacker) that can be perturbed (ei-ther together or in isolation) to cause a desirable change in the output.2. Perturbations for each critical input: The smallest perturbations that willtrigger the desired change in output.We present an automated technique that finds the critical inputs and the min-imal perturbations to cause a successful RFDIA. We model attack synthesis as anoptimization problem using Mixed Integer Linear Programming (MILP), and buildan automated tool ReLUSyn that identifies the critical inputs and finds the pertur-bations. To the best of our knowledge, we are the first to propose an automatedapproach to systematically identify the critical inputs, and find the minimum per-turbations to conduct a RFDIA for DNN-based controller systems.The main contributions in this work are as follows:1. Define and demonstrate a new class of attacks called RFDIA for DNN basedCPS.2. Model RFDIA synthesis as an optimization problem (specifically as a MILP).3. Demonstrate RFDIA on three DNN based CPS: An Artifical Pancreas Sys-tem (APS) and two air traffic control management systems called CollisionAvoidance System-Xu (ACAS-XU) and Horizontal Collision Avoidance Sys-tem (HCAS).4. Evaluate ReLUSyn ’s performance, and show that it can identify the criticalinputs and perturbations for mounting an RFDIA in a short time period.The main results in this work are as follows:1. We exposed a new set of vulnerabilities in DNN based systems. We find7000, 20, 40 successful RFDIAs for APS, HCAS and ACAS-XU in fewer than1 second, 40 seconds, and 7000 seconds, respectively.32. We design attack specific cost functions to synthesize the attacks for the threesystems.3. We demonstrate the effects of introducing normalization layers in DNN byshowing they make DNNs more robust against RFDIAs.We briefly discuss the relevant background such as CPS, DNN, and MILP inChapter 2, so that we can formally state the problem this thesis addresses. Weprovide a motivating example, and identify the challenges encountered in automat-ing the synthesis of these attacks in Chapter 3. We formalize DNN models andexplain our synthesis approach in Chapter 4, which is followed by the evaluationof our technique on three case studies in Chapter 5. We discuss the related workin Chapter 6. We conclude the thesis with a discussion of how to use our attackgeneration to design robust DNNs suggesting future work in Chapter 7.4Chapter 2BackgroundWe begin this section by describing a CPS attack in terms of three parties involved;this decomposition will lead into our attack model in Chapter 3. Next, we pro-vide a summary of canonical CPS so we can then introduce conventional controllerdesigns and its limitations. We then define DNN based models and describe theopen problems in them. Finally, we conclude the section with a formal problemstatement.2.1 Roles descriptionThere are three parties involved in designing and attacking CPS. These are impor-tant to identify the different pieces of information an attacker needs to gather toattack a system.1. Specification Designer/Domain Expert: The domain expert is responsiblefor developing the system specification. For an APS, the domain expert spec-ifies the safe thresholds for the amount of insulin injected into a patient. Thedomain expert also indicates values that should trigger alarms, e.g., in caseof a high blood glucose reading.2. System Developer: These are the people who build the controller models,e.g., a decision trees, DNN or a conventional controller model to implementthe system.5Figure 2.1: Architecture of a CPSFigure 2.2: Artifical Pancreas System components [1]3. Attacker: The attacker is trying to make the system misbehave by injectingfalse sensor readings in the CPS without triggering safety alarms specified bythe domain expert .2.2 Cyber-Physical SystemsCPS are systems that use sensor readings from the physical world to perform com-putations that produce changes in the physical world. As shown in Figure 2.1, the6Figure 2.3: General structure of a open and closed-loop systems [2]sensors and actuators are the physical parts of the system. The sensors gather datafrom the physical environment and send it to the computational unit. The com-putational unit is a controller, which makes decisions that are sent to the actuator,which in turn physically performs the action. The physical and virtual contexts caneither be humans in the loop or automated mechanisms.In the APS shown in Figure 2.2, the sensor is the Continuous Glucose Monitor(CGM) that is attached to the back of a patient to report blood glucose level. ARaspberry Pi (RPI) is the computational part of the APS, and the insulin pump isthe actuator.There are two types of CPS: open feedback and closed-loop feedback. In openfeedback systems, as shown in Figure 2.3 (top), the human is a part of the loop;he/she keeps track of the decisions being taken by the controller. In closed-loopsystems, there is no human intervention as shown in Figure 2.3 (bottom). In thelatter case, understanding different types of security attacks becomes a necessity,because automation means that once the attacker has found a way to tamper withthe automation mechanism, they can break the system. In the case of stealthy (orsubtle) attacks, as will be described in Chapter 3, closed loop systems are morevulnerable, because existing error-detection mechanisms can be reverse engineeredand then used to attack the systems.7Figure 2.4: The block diagram of the position control system of the quad-copter.2.3 Conventional Controllers for CPSA conventional controller transforms the sensors readings into decisions using setsof differential equations. For instance, a quadcopter contains multiple flight modesin its controller based on the weather conditions such as windy or normal day.These modes are important because during windy weather, the decision makingmodel for stable quadcopter flights will be different from a normal weather flight[22].Based on the inputs or data collected from the sensors, the appropriate modeis selected and the decision is calculated. Every mode consists of a different set ofequations, because every mode represents a different scenario. Figure 2.4 showsa position control system of a quadcopter [22]. The input values use the derivedversion of the equations that are used in decision making.These modes use classical control theory that is represented as a set of equa-tions designed by domain experts. For instance, the model for a medical systemsuch as APS can be designed only if the specifications are known for the medicalsystem. A part of the specification such as the important parameters (insulin, bloodglucose etc. in APS) and their threshold values are provided by domain (in this casemedical) experts. Another important aspect for designing control systems is mod-eling the precise relations between the parameters. This is possible in systems suchas APS, because it is a simpler system compared to self-driving car. However, de-signing the precise mathematical relations for systems such as self-driving cars canbe tedious [23], as we elaborate below.The move from equation-based models to DNNs for modeling CPS behaviorhas been justified by the following observations:81. CPS behavior is controlled using a lot of input data from the many sensorsa system might have. The self-learning nature of DNNs lends itself well tomodel behavior driven by sensor input. This is easier than formulating thecontrol theoretic differential equations, which need domain and mathemati-cal expertise [24].To look at a more concrete example, consider a medical system such as APS,which uses conventional control theory to build models. Forming the modelrequires the programmer to be aware of not only the intended system behav-ior and the mathematical formulation needed to produce the desired result.DNNs, on the other hand, can automatically build models given data. Train-ing DNNs is implicitly dependent on the quality of available training data,and it is a known problem in the field [25]. It does not, however, require thesystem designers to model precise control equations as does control theory.2. There are limitations on the behaviors that can be modeled using the stan-dard control-theoretic approaches. They do not, for instance, work well forbuilding dynamic models [23]. Building such dynamic models is importantin many systems such as in autonomous vehicles, which are essentially com-posed of multiple interacting control systems. Conventional control systemsare not designed to work in an interactive, plug-and-play manner with othercontrol systems, because they are built to model only one behavior. DNNsdo provide this dynamic capability [23]. Due to data driven modeling, it isrelatively easier to build models for autonomous vehicles that have multiplemodels interacting within them. For instance, they contain separate modelsfor image recognition and lane detection that continuously interact with eachother to decide the next best course of action.3. Sarabakha et al. [3] show that using a DNN based controller for a quadcopterleads to better decision making in unspecified cases compared to controltheory models. This is due to the DNN’s ability to adapt to different situationsin contrast to the fixed nature of conventional control theory. Hence, in caseswhen the trajectories or situations cannot be precisely modeled, the DNN islikely to be more effective.92.4 DNN Based ControllerA Neural Network (NN) consists of input, output and hidden layers. The layersare composed of nodes. Every computation occurs within a node of a network.In the simplest case, there is a single neuron that takes all the inputs to produce anoutput, as shown in Figure 2.5. All inputs to the node in Figure 2.5 are summed andpassed through an activation function. The activation function decides, whether aneuron should be activated or not by calculating weighted a sum and further addingbias with it. The purpose of the activation function is to introduce non-linearityinto the output of a neuron. A common activation function is the Rectified LinearUnit (RELU) function. The node determines up to what extent the signal mustprogress to calculate the final output. The final output depends on the network andcan be in binary form or have a precise value associated with it.A DNN consists of multiple hidden layers as shown in Figure 2.7, which isan example of a feed-forward DNN, which is the simplest type of artificial neuralnetwork [26]. The information flows only forward from input through layer tooutputs [27].The classical controller model is being replaced by such DNN based controllersfor CPS as shown in Figure 2.6. The DNN for CPS is trained using the data gatheredfrom conventional control equations. One example is the DNN based controllerdesigned by Dutta et al. [28]. Dutta et al. model a robust DNN using availablepatient data to predict the output for an insulin pump. Their controller design is forproviding a data-driven approach for an artificial pancreas system (APS), which isalso our first system used for evaluation.We evaluate two other systems called Collision Avoidance (CA) systems forunmanned vehicles [29] called HCAS and ACAS-XU: both CA systems are bigger insize (number of nodes and layers) and have a complex architecture in as comparedto APS.DNNs also consist of a feature called normalization in their layers. Normaliza-tion is a common feature engineering method where all the inputs are brought tostandard scale since different set of inputs can be in different ranges. This is im-portant in DNNs for reasons explained by LeCunn et al. [30]. Our two evaluationsystems are aircraft control management systems [31] which include a normaliza-10Figure 2.5: Perceptron node [32]tion layer, which we consider during our MILP formulation in Chapter 4.2.4.1 Understanding DNN complexityTo understand the complexity of DNNs we use two criteria1. Size: The size depends on two aspects, the number of layers in a DNN and thenumber of nodes in each layer. An increase in the hidden layers correspondsto more connections and opacity between the inputs and the outputs. Theincrease in the number of nodes per layer corresponds to more connectionsbetween each layer which ultimately increases the input and output mapping.2. Architecture: The architecture consists of the the design of the networkwhich consists of(a) Connectivity: For a fully-connected network, every node is connectedto every node in the network. There are multiple different ways archi-tectures can be designed.(b) Activation functions: These introduce non-linearity to the layers andhave multiple different characteristics. Some networks also consist oflayers that perform max/average pooling operations.When we refer to DNN complexity in this thesis, we are referring to differences insize and architecture.11Figure 2.6: Illustration of how DNN controllers are replacing conventionalcontrollers. The DNN is trained offline using input-output data obtainedfrom different trajectories from a conventional controller. The DNN isshown to perform better than a conventional controller during real-timeanalysis for decision making by Sarabakha et al. [3].Figure 2.7: DNN controller structure with two hidden layers K=1,2, two in-puts x1 and x2 and one output y. This is an example of a fully connectednetwork.122.5 Modeling Mixed-Integer Linear ProgrammingProblemsWe present a general structure that is required for building a Linear Programs (LP)model, specifically a MILP model. MILP is a LP where some of the variables arerestricted to be integers. We introduce the notion of MILP, because we use theunderlying techniques to model DNNs, and systematically reason about them indifferent scenarios with minimal effort. An LP is characterized by the followingcomponents.1. A LP contains a set of decision variables, which are the unknown quantitiesor decisions that are to be optimized.2. The function that assesses the quality of the solution is called an objectivefunction or the cost function.3. LP’s goal is to minimize or maximize the value of an objective function. Thedecisions that are to be made depends on the requirements and restrictionsof the system modeled as LP.4. A solution that satisfies all constraints is called a feasible solution. Feasi-ble solutions that achieve the best cost function value are called as optimalsolutions.The general form of a LP is shown in Equations 2.1. Values of c denote theobjective coefficient. xi denotes decision variables. bi denotes the constraints. Asthis is a linear model, non-linear terms, for instance, multiplication of z variables,are not allowed.min/maxxcT xsubject to Ax≤ bin∑i=1xi = 1x j, ∀ j ∈ N.(2.1)13We simplify the DNN by modeling it as a MILP, which we will elaborate morein Chapter 5.There are multiple tools that build MILP models such as Cplex [33], and Gurobi[34]. Both are widely used, however, we choose Gurobi for our work because ithas a more intuitive interface and python support.2.6 Problem StatementGiven a trained DNN with fixed parameters our goal is to understand if the RFDIAin classical control theory can also be applied to a DNN. This leads to two sub-problems as follows.P 1. How can we identify the critical inputs i.e inputs that affect the final outputsthe most on being perturbed in a DNN?P 2. What is the smallest perturbation to the critical input(s) that can produceRFDIA?14Chapter 3Ripple Attacks3.1 Motivating system: Artificial Pancreas SystemWe use a DNN based APS, closed-loop model, by Dutta et al. [35] as our motivatingexample for illustrating a RFDIA. The APS model we use in this section is also ourfirst evaluation system; it is also the simplest of the three systems in terms of DNNcomplexity described in 2.4.1. A patient relies on APS to correctly determine thenext dose of insulin to be injected every t minutes.The APS architecture is the same as that discussed in Section 2.4. We examinethe APS controller model from Dutta et al., which has a feed-forward architecturewith 2 hidden layers and 50 neurons each, 74 inputs and 1 output. The DNN forFigure 3.1: APS DNN designed by Dutta et. takes in 74 inputs of insulin andglucose. The next layers form connections between the insulin and theglucose to make predictions.[8]15APS takes 37 glucose and insulin input values (for a total of 74 inputs) discretizedover time and produces the next insulin values as output as shown in Figure 3.1.This implies that the future value is predicted based on the inputs from the previousset of values. The insulin and glucose values are collected from the sensors and theactuators by monitoring the patients behavior for a 30 days.There are two distinct phases in a DNN’s life; training and testing phase. Duringthe training phase, there are three DNNs. The first DNN predicts the dose to admin-ister. The other two DNNs are defense mechanisms to prevent the patient froman insulin overdose. The two DNNs are separate from the main decision makingcontroller. These DNNs are trained based on the latest 30-day patient data, whichis collected by monitoring the patient to understand the standard injections for apatient over time.One DNN learns a lower threshold on injection amount; the other learns an up-per bound on injection amount. Hence, for every time of the day, based on priorpatient characteristics, the minimum and the maximum values are known. How-ever, the system will not detect an adversary who manages to always administerthe maximum allowed dosage through RFDIA. Hence, the attacker needs to iden-tify inputs and perturb them such that the output administers the maximum alloweddosage for every injection, while being lower than the upper threshold to avoid de-tection. We further elaborate this in the next section.3.2 Attack ModelThe attacker’s goal is to manipulate the sensor measurements to corrupt outputwithout triggering alarms as shown in Figure 3.2. The attacker can use networknoise or physical sensor tampering to attack the systems [36].We make the following assumptions in the attack model:1. The attacker knows the precise DNN architecture. This information is easyto find, as the architectures are usually specified in the documentation.2. The weights and bias of the DNN are known as well through read-only accessto the system.3. The attacker can modify only the inputs to the model.16Figure 3.2: Attack model4. The DNN contains ReLU as its activation function.3.2.1 Strawman attackerA simple way to attack the system would be to change all 74 inputs to the DNN.If all the inputs are changed, the final output prediction is going to be wrong. Theproblem in this scenario is that these inputs are collected every five minutes fromthe sensors attached to the patient. This means that the attacker will have to conduct74 FDIAs every five minutes to cause a change in the output. However, this is quitetedious in practice, and hence the attacker needs a better way to attack the system.3.2.2 Sophisticated AttackerA more sophisticated approach to attack the system would be by perturbing a smallnumber of inputs that cause a change in the output. There are two ways to proceed:Attack 1The attacker can randomly choose two inputs and perturb them by large amounts.This will indeed cause a wrong output prediction. However, if the input is perturbedby a large amount, the error detection mechanisms will likely recognize that there17is an anomaly. To prevent this, the attacker can choose to perturb the two inputsby small amounts. However, perturbing any two random inputs by small amountsmight not necessarily lead to a wrong output prediction, as shown in Chapter 5.Attack 2Adding one more layer of sophistication, the attacker can carefully chooses theinputs that can lead to wrong predictions. This will be a more targeted approachfor attacking the system since the input selection will not be random as before.However, not knowing the precise amounts by which the critical inputs should beperturbed can lead to an unsuccessful attack. If the perturbation is too high, it willtrigger the error-detection mechanisms, and if it is too low, it will not affect theoutput as shown in Chapter 5.Attack 3The ideal attack would change a minimal number of inputs by the smallest amountpossible to produce the desired change in output. We demonstrate that it is possibleto generate this kind of attack.3.3 ChallengesThere are three challenges in the design of this technique. (1) choosing a mathe-matical abstraction that works best for our use case, (2) mapping the DNN modelto the abstraction, and (3) designing the DNN for attack synthesis.3.3.1 Selecting the automated techniqueThe first part is choosing an abstraction that allows the attacker to model a DNNand find critical inputs. There are multiple possible approaches such as Satisfiabil-ity Modulo Theories (SMT) solvers, symbolic execution and MILP.We desire a model that is1. General: APS has an architecture that is quite different from that of an aircontrol traffic management system (ACAS-XU and HCAS) as observed fromTable 6.1. This is due to the difference in the application domain and the18DNN architecture design. APS is a medical system that consists of a stan-dard feed-forward network without normalization; ACAS-XU normalizes itsinputs by scaling them to a range of 0-1, which makes it difficult to perturbthe inputs. To accommodate normalization, we need additional details in ourabstraction. Hence, we want an abstraction that supports different architec-tures.2. Scalable: The fully-connected APS DNN consists of 2 hidden layers with50 neurons each which means that there are 2800 (50 ∗ 5 + 50 ∗ 50 + 50 ∗1) connections in total. On the other hand, ACAS-XU consists of 5 hiddenlayers with 50 neurons each, for 10,500 total connections. Hence, we needa technique that is scalabe to complex systems.We show that MILP satisfies these goals, which is why we choose it in our work.3.3.2 Mapping Mixed-Integer Linear Programming Model to DeepNeural NetworksDNN architectures are quite complex making it difficult to extract direct mappingsfrom inputs to outputs. . The complexity arises due to 2 factors.1. The mutliple layers in DNN. A DNN’s mathematical structure contains mul-tiple layers, which is the first layer of complexity. APS has two layers asexplained in Section 3.1 with 8 neurons each.2. The non-linearity of the activation function. The non-linearity introduceddue to the activation functions within the network adds another layer of com-plexity for modeling in MILP. Non-linear terms are not allowed in MILPmodeling [37]We formalize DNN as sets of equations. We use these equations to build MILPmodels by adding constraints on the variables. We tackle the non-linearity of acti-vation functions by defining them as piece-wise linear functions, which we demon-strate for the ReLU activation function. We chose ReLU as it is used in all 3 sys-tems we use for evaluation.193.3.3 Modeling cost functionThe goal of the cost function is to minimize or maximize the linear constraints thatrepresents the DNN architecture and produce an optimization problem. We want tominimize the input perturbations and maximize the output deviations in a DNN asper our attack model. There are two main problems that arise based on our costfunction modeling:1. It is possible that no solution exists. This happens if the MILP model is infea-sible, as defined in Section 2.5, and we need to redefine our cost function.2. If the MILP model is feasible, there is still the possibility that there is nosingle optimal solution. This makes our solution space unbounded and canlead to state space explosions.We demonstrate how we solve both problems in our experimental evaluation inChapter 5. We use interval analysis for this purpose, which we discuss in Chapter4.20Chapter 4ReLUSynReLUSyn is our tool that demonstrates the RFDIA vulnerability in DNN-based CPS,by synthesizing attacks. We explain our approach and algorithms for attack syn-thesis and present ReLUSyn , which implements the algorithms and synthesizesthe models and attacks. We show how fully connected, feed-forward DNNs canbe formulated as MILP models. We use a generic representation and describe themodeling of cost functions that are used to generate RFDIA. We then show howthis allows us to identify critical inputs and find minimal perturbations. Finally,we demonstrate its efficiency in three real systems. We also include a section onhow ReLU (the non-linear activation function) is likely to be modeled internallyby MILP solvers based on Fischetti et al. [38].4.1 ReLUSyn: OverviewFigure 4.1 depicts ReLUSyn .1. ReLUSyn takes as input the DNN for a CPS controller, an optional cost func-tion (which allows users to request particular types of attacks, which will bediscussed in more detail in section 4.5), and a set of bounds indicating howmuch inputs can be varied without raising alarms. The bounds can be oninputs, outputs or both, depending on our attack model.2. ReLUSyn then produces a MILP model for the DNN.21Figure 4.1: The rounded boxes depict the information provided by the usersand the square boxes represent the information that is required by thesolver; MILP model is generated automatically and the cost functionsand bounds are plugged in by the user.Figure 4.2: DNN controller structure with two hidden layers K=1,2, two in-puts x1 and x2 and one output y. This is an example of a fully connectednetwork.3. Any solution that the MILP Solver finds for the model maps to a feasibleattack.4. If there is no such solution, then no attack is possible.4.2 DNN formalismWe follow the formalism based on the general architecture presented in Chapter 2.The DNN controller in Figure 4.2 maps the inputs, x1 and x2 to the output y.We represent the architecture as a function F defined as F : X→Y composed of22multiple layers that map inputs X to output Y. Assume a DNN composed of K +1layers, numbered 0 to K. Layer 0 is the input layer, while layer K is the output.Each layer k ε {0,1, ....,K} consists of nk nodes (neurons). Each neuron has a biasassociated with it. The network is fully connected, hence each neuron from layerk is an input to layer k+ 1. The neurons are labeled starting from 1 to nk in eachlayer of the network. We denote each neuron by NODE(i,k) which corresponds tothe ith node for the layer k.We denote the output vector of layer k as Fk(x). The output for each NODE(i,k)is denoted as Fik(x) where i ε {1, ....,nk}The output for layer 0 is represented as Fk(0). For every layer k ≥ 1 the outputvector is represented in Equation 4.1,Fk(x) = σ(W k−1xk−1 +bk−1) (4.1)where W is the weight vector, b is the bias associated with each layer, x is theinput to the network and σ represents the activation function. DNNs can have var-ious activation functions, each with different modeling capabilities. Two commonones are: Rectified Linear Unit (ReLU) ( f (x) = max (0,x) as shown in Figure 4.3and logistic (or sigmoid) activation function f (x) = 1/(1+ exp(−e)). ReLUSynfocuses on ReLU, since it is one of the most commonly used activation functionsaccording to Krizhevsky et al. [39] and is used in all of our example systems.Thus, the activation function for a layer k and vector x isReLU(x):= ∑nki=1 ei max(0,xi)In this context, we can restate Equation 4.1 as 4.2.Fk(x) = ReLU(W k−1xk−1 +bk−1) (4.2)Since a network consists of multiple layers, the general DNN representation iscomposition function where each Fk represents a DNN layer.F(x) = FK ◦FK−1 ◦FK−2.......◦F1(x),orF(x) = FK(FK−1(FK−2.......(F1(x)))),(4.3)234.3 MILP ModelThe non-linear ReLU activation function cannot be modeled directly by MILPsolvers, so we present an equivalent formulation, which we use to identify criti-cal inputs and find the minimum perturbations as discussed in 2.6. We use theGurobi solver to do so.To create a MILP model, we study the basic scalar equation that describes theDNN architecture where w is the weight, y is the input and b is the bias.x = ReLU(wT y+b) (4.4)We cannot apply the f (x) = max(0,x) operator directly because it is non-linear.As explained in Figure 4.3, the ReLU function is piecewise linear can be broken intwo parts, namely positive and negative parts.In theory f (x) = Max(0,x) can be represented as Equation 4.5, however, MILPdoes not support i f − then constructs because MILP only supports logical con-straints. Hence to model ReLU in MILP we introduce a dummy variable s.i f (x < 0)then(0);else(x);(4.5)Instead, we can rewrite Equation 4.4 given above as follows:wT y+b = x− s,x≥ 0,s≥ 0 (4.6)The addition of variable s in Equation 4.6 translates the ReLU activation func-tion to a linear representation. We make this division so that we can reason aboutthe non-linear activation function separately from the actual equation.Equation 4.6 by itself is problematic as there are infinitely many x,s ≥ 0 thatwould satisfy this equation. For example, if x′,s′ is a possible solution, then so isx′+ 5,s′+ 5 and so on. This is why we need to introduce ac ∈ 0,1 which adds aseparate constraint to the model depending on its value.To implement the piece-wise linear behavior, we define an activation variableac that imposes the logical implications. The choice to use different symbols was24made in the interest of clarity. The equation in this rewritten form is linear, and itdoes model ReLU functionality accurately as x will always be non-negative.ac = 1→ x≤ 0ac = 0→ s≤ 0ac ∈ {0,1}(4.7)If ac = 1, this will add the constraint x≤ 0 to the model. This coupled with x≥0 will mean x will be forced to be 0 and Wy+b =−s≤ 0 (but x which representsthe output to the next layer would be 0).If ac = 0, this will add the constraint s ≤ 0 to the model. This coupled withs≥ 0 will mean s will be forced to be 0 and Wy+b = x≥ 0 (and x which representsthe output to the next layer would be ≥ 0).Adding regularization to ac will mean there is a unique solution for x and s.This regularization will try to clamp ac to 0, which will force s to be 0 and conse-quently x to be greater than or equal to 0. The main takeaway is that it is possibleto model ReLU(x) (or max(0, x)) internally in a MILP solver.Modern MILP solvers can handle these constraints directly.Extending this scalar example to the DNN case leads to a MILP model of theform shown below.We have divided our MILP model in three main parts.Equation 4.8 represents the cost functions that are to be minimized or maxi-mized. These cost functions are different for different applications and depend onour goal; for an attack synthesis application minimization of input deviations is thegoal. The equation 4.8 is a generic representation of cost function modeling. Weexplain our cost function in more detail in 4.5 for RFDIA attack synthesis.min/maxK∑k=0nk∑i=iFjk(x)+K∑k=0nk∑i=iFjk(z) (4.8)Equations 4.9 represents the ReLU modeling for each layer in the network.We showed in Equation 4.7 how we can represent ReLU units as a set of linearconstraints in MILP solvers. To model the constraints, we use the formalism fromEquation 4.6 where we introduce the variable s to accommodate the non-linearity25using linear representations as explained in 4.7. We expand on it and apply it to allthe layers in the modeling.ReLU constraintssubject tonk∑j=0wk−1i j xk−1j +bk−1i = xki − skixki ≥ 0,ski ≥ 0acki ε{0,1}acki = 1→ xki ≤ 0acki = 0→ ski ≤ 0(4.9)Equations 4.10 add lower bounds (lb) and upper bounds (up) in the model fordifferent variables that we will require to add limits to our search space. Thesebounds are for the input and the output layers, all other layers are unbounded andwill be 0 and +∞ respectively.Upper and lower bounds for range analysis are as follows.lb≥ xki ≥ up,lb≥ ski ≥ up(4.10)Our MILP modeling applies the f (x) = max(0,x) operation directly to the out-put of layers because our MILP solver linearizes this internally when solving themodel.4.4 Building the modelAlgorithm 1 represents an algorithm for representing a DNN as a MILP model.This converts the neural network structure into a set of linear equations that can bemapped directly into a back-end MILP solver, in our case, Gurobi.The DNN input for k + 1 is the output of the k layer as shown in Algorithm1. The inputs to the Algorithm 1 is the DNN architecture. The out put is a MILPmodel that can be solved using our backend solver Gurobi.Different applications differ only in the number of layers and nodes in each26Figure 4.3: ReLU can be broken down into two linear units as shown in thefigure for x < 0 and x ≥ 0. This allows us to easily map the DNNequations in MILP models by breaking down the non-linearity inducingfunction.Figure 4.4: APS that takes in two inputs which we consider as the sensorvalues from the human. It predicts the amount of insulin to be injectedat some time based on the sensor inputs.27Algorithm 1: Modeling neural network in MILPInput: weight matrices, bias vectors, num layers, num neuronsOutput: input, layer output, ReLU output,1 Take the weight, bias, number of layers, and the number of neurons perlayer.2 Model,(I) For every layer k (with weight matrix Wk and bias vector bk),out putk =Wk ∗ inputk +bk(II) Apply activation function to every layer’s output,Constraints: ReLU out putk = max(0,out putk) (component-wise)The final layer’s rectified output is the DNN output.layer.x = ReLU(wT y+b) (4.11)4.5 Modeling cost functions for attacksNow that we have formulated the DNN as a MILP model, the next step is to add acost or objective function corresponding to a specific kind of attack. This functionallows the user to specify which inputs should be perturbed to generate the desiredoutput changes.As discussed in Chapter 3 the attacker’s goal is to change the inputs suchthat it leads to an output change without triggering an alarm. More formally, theattacker’s goal is to change the output y to y′, where y′ = y+a for some constant a.However, the catch here is that the inputs perturbations should be sufficientlysmall such to avoid detection.It does not consist of the cost function since the function will be different fordifferent systems, depending on what the attacker wants to minimize and/or max-imize. In our case we are specifically demonstrating RFDIA where the goal is tominimize the inputs deviations and/or maximize the output deviations. This behav-ior can be modeled in the objective function by introducing a new variable calleddelta in the inputs and outputs, which is then minimized and maximized respec-tively.28Hence, the equation 4.1 is represented as 4.12,y = ReLU(W (x+4x)+b) (4.12)(4.13)Algorithm 2 shows how to include the cost functions for RFDIA as a part ofthe MILP model.Algorithm 2: Modeling neural network in MILP with perturbation vari-ables and a cost functionInput: input (x), weight matrices, bias vectors, num layers, num neuronsOutput: input delta (∆x), layer output, ReLU output,1 Take the weight, bias, number of layers and number of neurons per layer.2 Model,(I) For the first layer k = 0 (with weight matrix W0 and bias vector b0),out put0 =W0 ∗ (x+∆x)+bk(II) For every subsequent layer k ≥ 1 (with weight matrix Wk and biasvector bk), out putk =Wk ∗ inputk +bk(III) Applying activation function to every layer’s output,Constraints: ReLU out putk = max(0,out putk) (component-wise)(IV) Applying constraints to the DNN output to force the desireddeviationThe final layer’s rectified output is the DNN output.3 Cost/Attack Functionmin |∆x|An attacker can choose how many inputs can be modified, assigning deltas to0 for those that cannot be modified. This is crucial in CPS where inputs may comefrom different sensors and the attacker may be able to tamper with some, but notall of them.Considering different scenarios, the attacker can minimize the values depend-ing on which inputs they are interested in targeting with an RFDIA. The RFDIA costfunction in Algorithm 2 minimizes the absolute values of the perturbations to bothinputs.294.6 Synthesizing attacksOnce the attacker has a model and the cost function designed, the next step is toidentify the critical inputs, and the desirable perturbations. In the running exampleof APS, there are 74 inputs collected from two sensors every five minutes. The goalof the attacker is to locate the critical inputs such that they can conduct RFDIA. InAPS, the attacker’s goal is to maximize the output, namely the insulin to be injectedinto a patient subject to a constraint, and minimize the change in inputs, namelythe previous glucose and insulin values. To do so, an attacker chooses the inputs tobe perturbed, and the ranges by which they can be perturbed.We explain our experiments and results in the next chapter.30Chapter 5EvaluationTable 5.1 presents the architectures of the three DNNs used in the APS, HCAS, andACAS-XU, in increasing order of complexity. These applications are all missioncritical, and can produce catastrophic outcomes in the presence of a successfulattack. They also come from two rather different domains: medical devices andautonomous vehicles, providing evidence of the generality of ReLUSyn .Table 5.1: System descriptionsAPS HCAS ACAS-XuSize of the networksNumber of inputs 74 5 5Number of hidden layers 2 5 6Neurons/Layer 8 25 50Number of outputs 1 3 5Our overall methodology is described in Figure 5.1. We pass the trained DNNmodels through ReLUSyn , which then identifies the critical inputs and perturba-tions for conducting RFDIA (if they exist). Our tool currently supports TensorFlowDNN formats [40]. We wrote a Python script to synthesize MILP models from DNNsand used it as our Gurobi input.As explained in Chapter 4, our tool ReLUSyn , converts the DNN to MILP formatand provides the critical inputs and the perturbations. We ran our experiments on31Figure 5.1: Our work supports DNNs modeled in tensorflow and pytorch.These files when passed through ReLUSyn produce the critical inputsand perturbations that can be used to conduct ripple false data injectionattacks or determine that no such attack is possible.server with a 2.40 GHz (10 MB L3 cache) Intel Xeon E5-2407 v2 processor with 8cores across 2 NUMA nodes and hyperthreading disabled. The server uses Ubuntu16.04.6 LTS with 32 GB RAM that is uniformly distributed (16 GB each) acrossboth NUMA nodes.5.1 Case study: APSThe APS takes 74 inputs (37 pairs of insulin and glucose values) gathered every 5minutes. It then predicts the next insulin value to be injected, which is 5 minuteslater than the last calculated output by the network. Using ReLUSyn , we cansuccessfully synthesize attacks in less than a minute, making it cost effective foran attacker.5.1.1 Experimental methodologyOur experimental methodology is as follows: we consider a set of accurate inputsand construct perturbation scenarios. A perturbation scenario consists of1. Number of inputs to perturb2. Range by which we can perturb each input.For each perturbation scenario, we evaluate our attack efficacy for a range ofdifferent outcomes. In APS, if a normal output value is x; we consider n differentoutput ranges as shown in Table 5.2 and 5.3, each of which administers too muchinsulin, differing only in how much additional insulin is administered. We thenexhaustively test each unique attack in the perturbation scenario until we obtainthe smallest one. For example as shown in Table 5.2, if the perturbation scenariois ”Attack only a single input, change its value by <= +/−5 and the objective is32input perturbation minimization” then, given 74 inputs, we run 74 tests for each tar-get output range until we find a feasible input. We chose 5 in our evaluation despitethe units of insulin and glucose units being different, because we have constraintsin the model that add the maximum and minimum values of insulin and glucose,which if < 5 and > −5 respectively override 5. In APS, we set the insulin andglucose ranges based on their units, and if 5 is greater or less than their maximumand minimum values respectively, then 5 is overridden by their ranges. We do sobecause there are too many combinations to test to find all possible perturbationsif we check for smaller ranges, or try to find every attack value that can possiblyexist. We iterate over the 74 different inputs, perturbing each by a random amountin the range (x - 5) <= (x + 5) until we find the one with the smallest perturbation.Finally, the inputs that on small perturbations lead to output deviations become ourcritical inputs set as shown in Table 5.3 for one specific case.Table 5.2 shows the results for three perturbation scenarios: changing a singleinput, changing two inputs, and changing all inputs, within a range of +− 5,5.1.2 Result AnalysisResults are shown in Table 5.8 and Table 5.2. We find that for different ranges ofoutputs, the critical inputs vary as shown in Table 5.3.1. We show the critical inputs for the case where one input perturbation isenough to produce a desirable output change. This makes attacking easyfrom an attacker’s perspective because to conduct a successful RFDIA, per-turbing a single input is enough to cause damage instead of changing multi-ple inputs.2. We kept the delta range to be between +−5 which is a very small perturba-tion for the insulin values which ideally lie between 100−200; hence we canobserve that small perturbations are enough to conduct successful RFDIA.3. We show that it takes less than a second for APS to identify the critical inputsand find the minimum perturbations for all the attacks.4. As we can observe in Table 5.2, as the number of perturbed inputs increases,the possible combinations of critical inputs also increases.335.2 Case Study: ACAS-Xu and HCASThe ACAS Xu and HCAS are different from each other in terms of their architec-tures and parameters as shown in Table 5.1. Apart from the difference between theweights, bias and the number of layers, the datasets used to produce the two arealso quite different.The geometry of ACAS-XU is shown in Figure 5.2. The ownship is the un-manned vehicle with the CA system and the intruder’s (another vehicle) goal is tocrash with the ownship. The ACAS-XU is designed to model a large lookup tablethat maps sensor readings to the decisions based on the readings or advisories. Thisis represented as forty-five different DNN models. Each network has the architec-ture described Table 5.1 with 5 inputs, 6 hidden layers and 5 outputs.There are five sensor readings (inputs to the network):1. Distance from ownship to intruder (ρ)2. Angle to the intruder relative to ownship heading direction (ψ)3. Header angle to intruder relative to ownship heading direction (θ )4. Speed of ownship (vown)5. Speed of intruder(vint)The 5 outputs are:1. clear-of-conflict (COC): keep going in the same direction2. weak right: Turn (1.5°/s) to right3. strong right: Turn (3°/s) to right4. weak left: Turn (1.5°/s) to left5. strong left: Turn (3°/s) to leftACAS-XU’s goal is to avoid crashes of the ownship with the intruder; if the twoare getting too close, an action is taken that moves the two apart. The output in theDNN corresponds to the action associated with the minimal score. This means thatbased on the sensor readings, if the output score for strong right is the least of allthe other outputs then the unmanned vehicle should turn 3°/s to its right to avoid acrash.HCAS functions similarly to ACAS-XU apart from the architectural differencesas stated in Table 5.1.We conduct two types of RFDIA: targeted and random. In targeted attacks, the34Figure 5.2: ACAS Xu geometryattacker specifically chooses a particular action to take, and in a random attack, themodel should produce any output that differs from the correct one.5.2.1 Experimental MethodologyWe consider a set of accurate inputs and construct perturbation scenarios. A per-turbation scenario consists of1. The output order2. Inputs perturbedRandom Ordering AttackUnlike APS that had a concrete value as an output, in ACAS-XU and HCAS, theoutput action depends on the scores. In a random attack, if the normal output wasstrong right the attacker’s goal is to change the output to COC. This would leadto a crash since according to the new output decision, there is no intruder in thevicinity, and the unmanned vehicle should keep following its original path. Thiscan be done by adding a constraint that ensures that the score of COC is the leastamong all other outputs. The orderings of other outputs is of no concern to theattacker so long as COC has the least score.35For each perturbation scenario, we evaluate our attack efficacy for differentorderings, which means that if the correct decision based on the scores is 1, thenwe perturb the inputs such that the output changes to 2. For this to happen the scorefor 2 has to be smallest of all other outputs.Attack 1 in Table 5.4 is an example of a random attack where we set one ofthe outputs to be the least of all the outputs. The ordering of rest of outputs doesnot matter because the decision is selected based on the output with the least score.We test it by checking for attacks by perturbing 1, 2 and 3 inputs at a time. Froma practical scenario, a random attack is useful for an attacker because they have tostate four constraints in this case, value(2) < (all other values).Targeted AttackIn a targeted attack, if the original output was strong right, the goal of the attackeris to change the output to strong le f t. The difference from a random attack is thatthe attacker wants the order of all the other inputs also to be in a specific order.This is to avoid potentially getting detected, since if the score for strong le f t is thelowest and the next higher score is for strong right, this can trigger conflicts thatare likely to be detected. Hence, the attacker sets constraints with a specific ordersuch that strong le f t is followed by weak le f t.Multiple different orders are tested for in Table 5.4, 5.5, 5.6 and 5.7 for HCASand ACAS-XU.We conducted two types of targeted attacks:1. Total ordering: In total ordering, there is a specific order decided by theattacker.2. Partial ordering: In partial ordering, the order is set only for the first twooutputs.The attacker can conduct various targeted attacks using the critical inputs asshown in Table 5.4, 5.5, 5.6 and 5.7 for HCAS and ACAS-XU.5.2.2 Result AnalysisSome interesting observations were:361. We found attacks where perturbing a single input was enough to change theoutput decision.2. In a complete ordering targeted attack scenario, we were unable to find asingle successful attack. We believe this was so because the constraints weretoo tight.3. When we tried finding the smallest perturbation, several experiments timedout but finding a perturbation within possible inputs was successful.5.3 Summary1. Overall, we conducted 19,000 attacks for APS out of which 7200 attackswere successful, and took less than 1 second per attack.2. We conducted 30 HCAS random attacks out of which 20 were successful,and the maximum amount of time taken by the attacks was 41 seconds.3. We conducted 7 targeted attacks for HCAS out of which 1 attack was suc-cessful.4. We conducted 140 ACAS-XU random attacks out of which 32 were suc-cessful, and the maximum amount of time taken by the attacks was 7228seconds.5. We conducted 16 targeted attacks for HCAS, out of which 2 attacks weresuccessful.These results are shown in Table 5.8.Thus we can see that synthesizing RFDIA attacks can be easily accomplishedby the attacker in a small amount of time using ReLUSyn . We have also triedout multiple different combinations of attacks keeping multiple attacker scenariosin mind, and show that for systems such as APS, perturbing a single input out ofthe 74 inputs is enough to cause damage in Table 5.2. Similarly for HCAS andACAS-XU, we observe from Table 5.4, 5.5, 5.6 and 5.7 that perturbing a singleinput in certain scenarios is enough to cause output deviation.37Table 5.2: APS Results: The Attack column consists of the attack modelswhere our goal is to minimize the inputs, Output ranges are the outputbounds we have set where we want to find the deltas, no. of combinationsis the combinations of attacks depending on the attack model (APS has 74inputs) which is followed the total number of successful and unsuccessfulattacks, peak time to conduct an attack in each set of experiment, memoryused.AttackOutput ranges(O)No.ofcom-bina-tionsSuc-cess-fulAt-tack(s)Un-suc-cess-fulAt-tack(s)Peaktime(s)Mem-oryused/MBAttack 1: (-5 <= Input <= 5)1 inputchanged at atime; deltaminimiza-tion isprimaryobjective(204 < O < 210)(210 < O < 215)(215 < O < 220)(220 < O < 221)(200 < O < 203)(197 < O < 200)(194 < O < 197)747474747474746020034168147274744058660.0090.0010.0010.0010.0180.0080.00121.818.218.118.222.822.218.5Attack 2: (-5 <= Input <= 5)2 inputschanged at atime; deltaminimiza-tion isprimaryobjective(204 < O < 210)(210 < O < 215)(215 < O < 220)(220 < O < 221)(200 < O < 203)(197 < O < 200)(194 < O < 197)270127012701270127012701270126692202922142137473932248126722699559132719620.0290.01390.0060.0030.06320.04120.041321.818.218.118.222.822.218.5Attack 3: (-5 <= Input <= 5)74 (All)inputschanged at atime; deltaminimiza-tion isprimaryobjective(204 < O < 210)(210 < O < 215)(215 < O < 220)(220 < O < 221)(200 < O < 203)(197 < O < 200)(194 < O < 197)1111111111111100000000.0370.0600.0490.0450.1100.0730.06223.119.120.320.322.522.023.038Table 5.3: Critical Inputs - APS - 1 Input perturbed at a time. These are thesafe ranges that we obtain from the specification document for a patient.We perturb inputsOutput range Critical Inputs(204 <= Out put <= 210) (1-5, 7, 9-13, 34-43,45,70-74)(210 <= Out put <= 215) (41, 43)(215 <= Out put <= 220) X(220 <= Out put <= 221) X(200 <= Out put <= 203) (23, 31, 35, 36, 38-41, 42, 45-51, 53-56, 59-70, 72, 73)(197 <= Out put <=200) (40, 45, 48-51, 56, 61, 63-67, 70, 72, 73)39Table 5.4: HCAS Results: The different attacks are explained in the Attackcolumn which depends on the order of the outputs and the ranges of thedeltas, the number of inputs to be perturbed are selected by the attackerfor conducting each attack, the total number of combinations are calcu-lated based on the total number of inputs and the inputs selected to beperturbed, the peak time is the maximum time it took to test for an attackfrom the combinations, X indicates that the experiments timed out.AttackInputsperturbedNo.ofcom-bina-tionsSuc-cess-fulAt-tack(s)Un-suc-cess-fulAt-tack(s)Peaktime(s)Mem-oryused/MBCriticalinputsRandomAttack 1 - Oneoutput is set to beminimum (otherscan be orderedarbitrarily); deltasare restricted to be5 at the max andare minimized1A - 1 input1B - 2 inputs1C - 3 inputs1212451147105.794.380.970.2108103.50: [(0), (2)],2: [(1)], 4:[(0), (1)]All but 1:[(1,2)]Targeted 1Attack 1 -Complete orderingon outputs; deltasdo not haveuser-specifiedrestriction and arenot minimized1A - 1 input1B - 2 inputs1C - 3 inputs3310003317.9174.41130.673.1114.9152.7NATargeted 2Attack 2 -Complete orderingon outputs; deltasdo not haveuser-specifiedrestriction and arenot minimized2A - 1 input2B - 2 inputs2C - 3 inputs3310003316.7214.62039.271.5123.9290.1NATargeted 3Attack 3 - Partialordering onoutputs; deltas donot haveuser-specifiedrestriction and arenot minimized3A - 1 input3B - 2 inputs3C - 3 inputs3312311003.04.22.769.071.567.4[0], [2]([0,1],[0,2],[1,2])([0,1,2])40Table 5.5: HCAS Results continuedAttackInputsperturbedNo.ofcom-bina-tionsSuc-cess-fulAt-tack(s)Un-suc-cess-fulAt-tack(s)PeaktimeMem-oryusedCriticalinputsTargeted 4Attack 4 - Partialordering onoutputs; deltas donot haveuser-specifiedrestriction and areminimized4A - 1 input4B - 2 inputs4C - 3 inputs33123110010069.483.176([0], [2])([0,1], [0,2],[1,2])([0,1,2])Targeted 5Attack 5 - Partialordering onoutputs; deltas donot haveuser-specifiedrestriction and arenot minimized5A - 1 input5B - 2 inputs5C - 3 inputs3310013304.9229.61.869.7110.458.9XX([0,1,2])Targeted 6Attack 6 - Partialordering onoutputs; deltas donot haveuser-specifiedrestriction and areminimized6A - 1 input6B - 2 inputs6C - 3 inputs331001330XX357.4XX111.1XX([0,1,2])Targeted 7Attack 7 - Partialordering onoutputs; deltas donot haveuser-specifiedrestriction and arenot minimized7A - 1 input7B - 2 inputs7C - 3 inputs3311312003.524.81.967.990.562.0[1]([0,1], [0,2],[1,2])([0,1,2])41Table 5.6: HCAS Results continuedAttackInputsperturbedNo.ofcom-bina-tionsSuc-cess-fulAt-tack(s)Un-suc-cess-fulAt-tack(s)PeaktimeMem-oryusedCriticalinputsTargeted 8Attack 8 - Partialordering onoutputs; deltas donot haveuser-specifiedrestriction and areminimized8A - 1 input8B - 2 inputs8C - 3 inputs3311312003.580.567.968.6104.4103.1[1]([0,1], [0,2],[1,2])([0,1,2])Targeted 9Attack 9 - Partialordering onoutputs; deltas donot haveuser-specifiedrestriction and arenot minimized9A - 1 input9B - 2 inputs9C - 3 inputs3310113206.3139.3314.167.398.4126.6X([1,2])([0,1,2])Targeted 10Attack 10 - Partialordering onoutputs; deltas donot haveuser-specifiedrestriction and areminimized10A - 1input10B - 2inputs10C - 3inputs3310113204.785.0228.871.692.7109.9X([1,2])([0,1,2])42Table 5.7: ACAS-Xu Results: The different attacks are explained in the At-tack column which depends on the order of the outputs and the rangesof the deltas, the number of inputs to be perturbed are selected by theattacker for conducting each attack, the total number of combinations arecalculated based on the total number of inputs and the inputs selectedto be perturbed, the peak time is the maximum time it took to test for anattack from the combinations, X indicates that the experiments timed out.AttackInputsperturbedNo.ofcom-bina-tionsSuc-cess-fulAt-tack(s)Un-suc-cess-fulAt-tack(s)PeaktimeMem-oryusedRandomOne output is set tobe minimum(others can beorderedarbitrarily); deltasare restricted to be5 at the max andare minimized1A - 1 input1B - 2 inputs1C - 3 inputs1D - 4 inputs1E - 5 inputs204040204291282183128122465.84141.16644.917637.911528.4160.7209.1269.1449.5348.2TargetedComplete orderingon outputs; deltasare restricted to be5 at the max andare minimized1A - 1 input1B - 2 inputs1C - 3 inputs1D - 4 inputs1E - 5 inputs5101051000005101051739.43678.17296.624041.94434.7204.8202.6296562.1200.2TargetedPartial ordering onoutputs; deltas arerestricted to be 5 atthe max and areminimized2A - 1 input2B - 2 inputs2C - 3 inputs2D - 4 inputs2E - 5 inputs510105100XX0510XX1975.83816.4XX4766.6223.2197.1XX218.6TargetedAttack 3 - Partialordering onoutputs; deltas areunrestricted3A - 1 input3B - 2 inputs3C - 3 inputs3D - 4 inputs3E - 5 inputs510105101XX159XX01075.062876.6XX8311.2288.21740.5XX1447.443Table 5.8: Results SummaryInputs-pert Total Successful Mean-Time/urbed/Attack Attacks Attacks Attack(s)APS1 518 120 0.00152 18907 7175 0.00274 7 7 0.03HCAS - Random1 12 5 3.872 12 11 32.893 4 4 41.14HCAS - Targeted (Partial Ordering)1 3 1 2.142 3 0 2.913 1 0 2.74ACAS Xu - Random1 20 2 100.112 40 9 548.723 40 12 1452.1764 20 8 5029.585 20 2 7228.966ACAS Xu- Targeted (Partial Ordering)1 5 0 297.22 10 1 23595.585 1 1 8311.2144Chapter 6Related WorkWe have classified related work into four broad categories. The first category dis-cusses the verification techniques that have emerged to verify DNNs. We highlightwhy those techniques cannot directly be used for our application. The second dis-cusses work done in the FDIA community for classic control theory modeled sys-tems, and why our work is required when DNNs replace control theory equations.In the third category, we discuss multiple applications where DNNs have replacedor have been added to the CPS. This provides a glimpse into how the DNNs arebeing utilized in safety-critical applications. Furthermore, this motivates the needfor a technique that can generalize to different settings of DNN based CPS. Finally,in the last category, we discuss adversarial attacks that have gained a lot of atten-tion in the Machine Learning(ML) community and how are they different from ourripple FDI attack .6.1 Verification of CPSFormally verifying DNN based CPS has recently gained a lot of momentum. Re-searchers have proposed automated verification mechanisms that use techniquesinvolving SMT solvers, symbolic execution and MILP [41], [42], [31]. However,the modeling that has been done for those interfaces cannot be directly used forour use case without significant modifications. The goal of these techniques isto conduct an input-output range analysis to establish bounds for the DNN for its45correctness. Our work focuses not on conducting a bound analysis, but on find-ing the inputs for changing the outcome of a CPS under a constrained setting fora FDIA. Also, the approaches focus more on verifying certain properties such asreachability analysis that do not account for ripple FDI attack .Pulina et al.[41] proposed one of the first approaches for verifying DNN safetyproperties using abstraction refinement. They further abstract [42] the nonlinearactivation functions in a linear arithmetic Satisfiability Modulo Theories (SMT)formula but their application and abstraction interface is different from ours. Theythen use a counterexample based approach for abstract refinement. There has beenfurther work by Katz et al.[31] in verifying the networks using SMT solvers wherethey build rules for handling the ReLU activation function. Most of work we havementioned above in this domain utilizes the state-of-the art solvers Z3 and CVC4.However, all the existing techniques focus on proving robustness properties [43]for DNNs that cannot detect or produce FDIA. Xiang at al.[44] focuses on anoutput reachable estimation for NN using simulation-based methods. There havebeen multiple methods proposed to conduct a reachability analysis for DNN usingMILP/SMT approach [45] [46] [31] [47] [42]. Ivanov et al. [48] proposes a verifi-cation framework for verifying DNN based controllers by abstracting the probleminto a hybrid system verification problem.6.2 False Data Injection Attacks (FDIA) in traditionalsystemsAttacking a CPS by exploiting the deep integration of the physical-nature andcyber- nature of the systems has lead to the emergence of FDIAs. There are twomain categories of FDI attacks that have been proposed in the literature: randomFDIA and targeted FDIA. Random FDIA are generated by randomly changing theinputs to cause changes in the state estimation. Targeted FDIAs are the more in-teresting ones from an attackers perspective, because they have to synthesize theexact values of inputs to cause a change in the output without triggering alarms.Our work focuses on synthesizing both random and targeted FDIAs under a spe-cific set of constraints based on the specification documentation that we explain inChapter 2.46In FDI attacks, the attacker’s goal is to compromise the sensor inputs to misleadthe state estimation process [49]. Liu et al. [17] introduced the class of FDIA forelectric power grids to introduce arbitrary errors into certain state variables withoutbeing detected. Giannini et al. [50] generate FDIA under a specific setting, wherethey introduce new information as constraints in the state estimator under the as-sumption that the new information is not available to the attacker. These techniquesgenerate FDIA for systems modeled using control theory in order to cause a wrongstate estimation without getting detected. Our work studies the CPS constructedusing DNNs. We demonstrate if FDIA would work in different constraint settings.Bobba et al. [51] show that by protecting a strategically selected set of sensormeasurements, it is possible to detect the attacks proposed by Liu at al. [17].6.3 DNN controllers in CPSThis line of work focuses on intelligent control using DNN in designing the controlsystems. Fukuda et al. [52] show how NN can be utilized in industrial systems.Cong et al. [53] proposes a recurrent neural network that is used to create a Propor-tional–Integral–Derivative (PID, Kp, Ki and Kd) neural network (PIDNN). This al-lows the network to converge more quickly since PIDNN has one hidden layer with3 neurons that represent Kp, Ki and Kd that are used in traditional PID controllers.Wang et al. [54] proposes a double layer architecture for a non-linear system usingadaptive NN control and Nonlinear Model Predictive Control (NMPC).6.4 Deep Neural Network SecurityAdversarial machine learning emerged when Szegedy et al. [55] showed that theinput-output mappings for DNNs are not continuous and it is possible to perturb theinputs by small amounts such that the classification changes. Since then there hasbeen a lot of work exploring different types of adversarial attacks. Deng et al. [56]analyzes five types of adversarial attacks in autonomous driving models. ConAML[57] explores constrained adversarial attacks for CPS under different settings. Theypropose a best effort algorithm to iteratively generate adversarial examples butdon’t consider the physical notion of systems for their attack model. We, on theother hand, introduce ripple FDI attack that generate ripples based on constraints.47Wang et al. [12] proposes ReLUVal that uses symbolic execution to show that theDNN based systems are free from security vulnerabilities to ensure that in specificintervals, the system is free from attacks; we use MILP that provides us the abilityto model different cost functions for different attacks; symbolic execution does notcontain this.This chapter covers the various techniques that have been used in verification ofDNNs, and explains why none of the existing techniques are suitable for our usecase. We further introduce the various FDIA conducted in classical control theorysystems and their approaches for demonstrating the attacks. We then briefly de-scribe the shift from control theory models to DNN based models for CPS. Finally,we explain the security analysis explored in DNNs.48Chapter 7ConclusionBased on our results, we discuss two approaches that can help researchers and de-velopers design error-free DNNs. We also discuss some limitations of our approach.Finally, we conclude, and discuss potential future work.7.1 Designing Robust DNNsFrom our experience in attacking three different types of DNN based CPS, there aretwo ways to construct or build robust DNN based systems.The two things that help us in building our intuition were:1. Building and running the models on MILP solvers helped us understand thepower in terms of reasoning about DNN based systems for exposing vulner-abilities in form of RFDIA.2. Attacking three practical systems helped us understand how to design robustDNN by adding layers of complexity to DNN, since some architectures aremore resilient than other.7.1.1 Effects of normalization and attacksThe biggest difference between APS and ACAS-XU apart from the DNN size wasthe robustness of the DNN. APS has a fully-connected, feed-forward architecture,where the network takes the inputs and passes them through the hidden layers to49compute the output. ACAS-XU is also a fully-connected DNN; however, it includesnormalization. This means that ReLUSyn has to try out more combinations of inputvariable perturbations to find if an attack exists. Further, small perturbations duringthe FDIA get masked due to the normalization layer; changing an input value from5 to 10 has little to no effect on the DNN if the normalization layer normalizes arange of inputs to a value between 0 and 1. Thus, we have to perturb the inputs byvalues large enough to induce a change in the normalized representation.We also observed that in many cases, despite large enough perturbation, wewere unable to generate RFDIA in HCAS and ACAS-XU as shown in Chapter 5.Intuitively, based on the sizes of APS and ACAS-XU we should have been able togenerate significantly more RFDIA than APS; instead we observe that despite thebigger search space in HCAS and ACAS-XU, we found very few RFDIA as comparedto APS.Therefore, we believe that normalization makes it difficult for the attacker tocompromise the system via RFDIA. It does not eliminate the possibility of conduct-ing RFDIA entirely, but makes the system more secure against them.7.1.2 Effects of DNN size and attacksThe APS was a relatively smaller system compared to ACAS-XU and HCAS. Weobserve that due to much less complex nature of APS, ReLUSyn is able to try outmore combinations, and hence is able to find more attacks. Every attack in APStakes less than a minute for ReLUSyn to generate (if it exists), or to tell us noattacks are possible; HCAS and ACAS-XU, on the other hand can take hours, eitherfor ReLUSyn to tell us that there is no attack, or to find attacks. This restrictsus in terms of exploring all possible combinations and hence selectively choosingthe a subset of all combinations. Hence, comparing between small systems suchas APS, and relatively bigger systems, such as HCAS and ACAS-XU, we observethat the small system size enables us to generate more attacks and cover morecombinations.When we compare HCAS and ACAS-XU we observe a similar behavior; HCAStook less time per attack, and hence we were able to explore more of the space,and find successful instances of attacks. The reason we consider time an important50factor is because if it takes a long time to find an attack, attacks become moreexpensive to find. Hence, our goal is to find a reasonable trade-off between timeand size to generate attacks.Thus, based on our observations we can say that designing bigger systems canhelp make systems more secure given the other aspects of the DNN are similar toour evaluation systems.7.2 LimitationsThere are 2 limitations of ReLUSyn that pave way for future work.1. First, we are assuming that the attacker has read access to the weights andthe bias of a DNN. However, in an ideal scenario it is difficult to obtainread access to the weights and the bias of safety-critical systems such as CAsystems since these are often hidden. Therefore, the attacker might needtools or techniques that allows them to attack the system without havingknowledge about the internals of the network; this is also called as a black-box approach. This would mean that within a short amount of time (say acouple of hours), the attacker is able to attack a black box system and conductRFDIA or other attacks.2. Second, we observed that in complex DNNs of our three systems, there weremany cases when ACAS-XU timed out, and did not return any results. Thetime out occurred because the search space for the appropriate input-outputpair was very huge. However, we believe adding more precise bounds, andlimiting the search space can significantly scale our approach. There is apossibility of designing clever heuristics for domain specific systems suchas removing non required layers, pruning the DNN appropriately, using algo-rithmic approaches to decrease time complexity of MILP solvers.7.3 Future WorkFinally, we believe that there are three extensions that can be done with ReLUSyn .1. First, it can be extended for different application domains to find attacks. Forinstance Autonomous Vehicles (AV) such as self-driving cars have multiple51stacks of DNNs to compute the output, and ReLUSyn can be utilized to findattacks in multiple DNNs. This will require an extension in ReLUSyn toaccommodate multiple DNNs to be analyzed together and be tested for RFDIAor any other attack, unlike in our current work where we analyze one DNN ata time.2. Second, one can model cost functions for an attack model different fromours, and use our insights to generate attacks. This is because the modelingof the DNN and ReLUSyn can be easily reused with different attack specificcost functions. Currently, there are a lot of unexplored vulnerabilities inDNN-based CPS; thus one can use ReLUSyn to model new vulnerabilities.3. Finally, we can ReLUSyn to debug existing DNN. In our work, we proposedReLUSyn to generate attacks for trained DNNs that also tell us if in a particu-lar setting, no attacks exist. However, instead of trying to find attacks in theDNN, we can also use ReLUSyn for debugging; it means that we can conductan input-output pair generation to study if there are some wrong pairs basedon the application that are being generated. This can be seen as trying togenerate the datasets from a trained model that can be used to understand thecorner cases; cases can help the designers or researchers to understand howto modify the training data such that they can improve a DNN performanceby adding or removing from the datasets. In an APS, by using ReLUSyn ,we can generate all combinations of input-output pairs and observe if at theboundary values there exist some wrong predictions.7.4 ConclusionOur goal is to understand if the RFDIA in classical control theory can also be ap-plied to a DNN to expose new vulnerabilities.We demonstrate ReLUSyn , which is based on generating ripple FDI attackusing back-end MILP solvers.We address the two main challenges in synthesizing ripple FDI attack :1. Locating the critical inputs:522. Finding the smallest perturbations for critical inputs to conduct ripple FDIattack .To locate the critical inputs, we model a cost function, add delta variable to theinputs and minimize the delta. This helps the attacker in identifying the minimalset of inputs, by perturbing which by the small amounts, can result in wrong outputpredictions.Based on our experiments, we conclude that:1. The first observation is that it is faster to find attacks on small-sized DNNbased CPS. APS took less than a second for finding an attack, whereas ACASXu took as high as 5 hours, and even timed out for certain constraints.2. We found fewer attacks in ACAS Xu as compared to APS, indicating thatACAS Xu is a more robustly designed network due to the existence of nor-malization that makes it difficult to generate ripples. Hence, it is possibleto design robust DNN while designing the architectures by integrating suchfeatures.3. Finally, we observe that the choice of the cost function and range analysiscan help scale our technique. If there is a minimization function on the inputperturbations, it takes much longer to compute.53Bibliography[1] https://openaps.org/. → pages xii, 6[2] OpenClosedloop. → pages xii, 7[3] A. Sarabakha and E. Kayacan, “Online deep learning for improvedtrajectory tracking of unmanned aerial vehicles using expert knowledge,”2019. → pages xii, 9, 12[4] R. Alur, “Formal verification of hybrid systems,” in Proceedings of the NinthACM International Conference on Embedded Software, EMSOFT ’11, (NewYork, NY, USA), p. 273–278, Association for Computing Machinery, 2011.→ page 1[5] I. Lee and O. Sokolsky, “Medical cyber physical systems,” in Proceedings ofthe 47th Design Automation Conference, DAC ’10, (New York, NY, USA),p. 743–748, Association for Computing Machinery, 2010. → page 1[6] I. Lee, O. Sokolsky, S. Chen, J. Hatcliff, E. Jee, B. Kim, A. King,M. Mullen-Fortino, S. Park, A. Roederer, and K. K. Venkatasubramanian,“Challenges and research directions in medical cyber–physical systems,”Proceedings of the IEEE, vol. 100, pp. 75–90, Jan 2012. → page 1[7] W. C. Uhler, ““a review of: Once again: How the cold war ended and whythe soviet union collapsed”,” The Journal of Slavic Military Studies, vol. 18,no. 3, pp. 505–524, 2005. → page 1[8] S. Zonouz, K. Davis, R. Berthier, R. Bobba, W. Sanders, and T. Overbye,“Scpse: Security-oriented cyber-physical state estimation for power gridcritical infrastructures,” Smart Grid, IEEE Transactions on, vol. 3,pp. 1790–1799, 12 2012. → page 1[9] A. A. Cardenas, T. Roosta, and S. Sastry, “Rethinking security properties,threat models, and the design space in sensor networks: A case study inscada systems,” Ad Hoc Netw., vol. 7, p. 1434–1447, Nov. 2009. → page 154[10] H. Alemzadeh, D. Chen, X. Li, T. Kesavadas, Z. T. Kalbarczyk, and R. K.Iyer, “Targeted attacks on teleoperated surgical robots: Dynamicmodel-based detection and mitigation,” in 2016 46th Annual IEEE/IFIPInternational Conference on Dependable Systems and Networks (DSN),pp. 395–406, June 2016. → page 1[11] D. Halperin, T. S. Heydt-Benjamin, B. Ransford, S. S. Clark, B. Defend,W. Morgan, K. Fu, T. Kohno, and W. H. Maisel, “Pacemakers andimplantable cardiac defibrillators: Software radio attacks and zero-powerdefenses,” in 2008 IEEE Symposium on Security and Privacy (sp 2008),pp. 129–142, May 2008. → page 1[12] S. Wang, K. Pei, J. Whitehouse, J. Yang, and S. Jana, “Formal securityanalysis of neural networks using symbolic intervals,” in 27th USENIXSecurity Symposium (USENIX Security 18), (Baltimore, MD),pp. 1599–1614, USENIX Association, Aug. 2018. → pages 1, 48[13] I. Rouf, R. Miller, H. Mustafa, T. Taylor, S. Oh, W. Xu, M. Gruteser,W. Trappe, and I. Seskar, “Security and privacy vulnerabilities of in-carwireless networks: A tire pressure monitoring system case study,” inProceedings of the 19th USENIX Conference on Security, USENIXSecurity’10, (USA), p. 21, USENIX Association, 2010. → page 1[14] K. Chung, X. Li, P. Tang, Z. Zhu, Z. T. Kalbarczyk, R. K. Iyer, andT. Kesavadas, “Smart malware that uses leaked control data of roboticapplications: The case of raven-ii surgical robots,” in 22nd InternationalSymposium on Research in Attacks, Intrusions and Defenses (RAID 2019),(Chaoyang District, Beijing), pp. 337–351, USENIX Association, Sept.2019. → page 1[15] G. K. Fourlas, K. J. Kyriakopoulos, and C. D. Vournas, “Hybrid systemsmodeling for power systems,” IEEE Circuits and Systems Magazine, vol. 4,pp. 16–23, Third 2004. → page 1[16] B. Kim, A. Ayoub, O. Sokolsky, I. Lee, P. Jones, Y. Zhang, and R. Jetley,“Safety-assured development of the gpca infusion pump software,” inProceedings of the Ninth ACM International Conference on EmbeddedSoftware, EMSOFT ’11, (New York, NY, USA), p. 155–164, Association forComputing Machinery, 2011. → page 1[17] Y. Liu, P. Ning, and M. K. Reiter, “False data injection attacks against stateestimation in electric power grids,” ACM Trans. Inf. Syst. Secur., vol. 14,June 2011. → pages 2, 4755[18] G. Liang, J. Zhao, F. Luo, S. R. Weller, and Z. Y. Dong, “A review of falsedata injection attacks against modern power systems,” IEEE Transactions onSmart Grid, vol. 8, pp. 1630–1638, July 2017. → page 2[19] W. Xiang, P. Musau, A. A. Wild, D. M. Lopez, N. Hamilton, X. Yang,J. Rosenfeld, and T. T. Johnson, “Verification for machine learning,autonomy, and neural networks survey,” arXiv:1810.01989, 2018. → page 2[20] J. Kocic, N. Jovicic, and V. Drndarevic, “An end-to-end deep neural networkfor autonomous driving designed for embedded automotive platforms,”Sensors (Basel, Switzerland), vol. 19, p. 2064, May 2019. 31058820[pmid].→ page 2[21] M. G. Bechtel, E. McEllhiney, M. Kim, and H. Yun, “Deeppicar: A low-costdeep neural network-based autonomous car,” 2017. → page 2[22] A. Joukhadar, M. Alchehabi, and A. Jejeh, Advanced UAVs NonlinearControl Systems and Applications. 06 2019. → page 8[23] F. Pereira, “Control design for autonomous vehicles: A dynamicoptimization perspective,” European Journal of Control - EUR J CONTROL,vol. 7, pp. 178–202, 12 2001. → pages 8, 9[24] M. Aamir, “On replacing pid controller with ann controller for dc motorposition control,” International Journal of Research Studies in Computing,vol. 2, Apr 2013. → page 9[25] H. Jabbar and R. Z. Khan, “Methods to avoid over-fitting and under-fitting insupervised machine learning (comparative study),” Computer Science,Communication and Instrumentation Devices, 2015. → page 9[26] J. Schmidhuber, “Deep learning in neural networks: An overview,” CoRR,vol. abs/1404.7828, 2014. → page 10[27] A. Zell, “Simulation neuronaler netze [simulation of neural networks] (ingerman) (1st ed.),” Addison-Wesley. p. 73., 1994. → page 10[28] S. Dutta, T. Kushner, and S. Sankaranarayanan, “Robust data-driven controlof artificial pancreas systems using neural networks,” in ComputationalMethods in Systems Biology, vol. tbd of Lecture Notes In Computer Science,p. tbd, Springer-Verlag, 2018. → page 10[29] G. Manfredi and Y. Jestin, “An introduction to acas xu and the challengesahead,” in 2016 IEEE/AIAA 35th Digital Avionics Systems Conference(DASC), pp. 1–9, Sep. 2016. → page 1056[30] Y. LeCun, L. Bottou, G. B. Orr, and K.-R. Mu¨ller, “Efficient backprop,” inNeural Networks: Tricks of the Trade, This Book is an Outgrowth of a 1996NIPS Workshop, (Berlin, Heidelberg), p. 9–50, Springer-Verlag, 1998. →page 10[31] G. Katz, C. Barrett, D. L. Dill, K. Julian, and M. J. Kochenderfer, “Reluplex:An efficient smt solver for verifying deep neural networks,” in ComputerAided Verification (R. Majumdar and V. Kuncˇak, eds.), (Cham), pp. 97–117,Springer International Publishing, 2017. → pages 10, 45, 46[32] N. network. → pages xii, 11[33] CPLEX, “Ibm cplex optimizer,” 2019. → page 14[34] L. Gurobi Optimization, “Gurobi optimizer reference manual,” 2019. →page 14[35] S. Dutta, T. Kushner, and S. Sankaranarayanan, “Robust data-driven controlof artificial pancreas systems using neural networks,” in ComputationalMethods in Systems Biology (M. Cˇesˇka and D. Sˇafra´nek, eds.), (Cham),pp. 183–202, Springer International Publishing, 2018. → page 15[36] Y. Cao, C. Xiao, B. Cyr, Y. Zhou, W. Park, S. Rampazzi, Q. A. Chen, K. Fu,and Z. M. Mao, “Adversarial sensor attack on lidar-based perception inautonomous driving,” in Proceedings of the 2019 ACM SIGSAC Conferenceon Computer and Communications Security, CCS ’19, (New York, NY,USA), p. 2267–2281, Association for Computing Machinery, 2019. → page16[37] Gurobi, “Gurobi,” 2019. → page 19[38] M. Fischetti and J. Jo, “Deep neural networks as 0-1 mixed integer linearprograms: A feasibility study,” 2017. → page 21[39] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification withdeep convolutional neural networks,” Commun. ACM, vol. 60, p. 84–90,May 2017. → page 23[40] TensorFlow. → page 31[41] L. Pulina and A. Tacchella, “An abstraction-refinement approach toverification of artificial neural networks,” in Proceedings of the 22ndInternational Conference on Computer Aided Verification, CAV’10, (Berlin,Heidelberg), p. 243–257, Springer-Verlag, 2010. → pages 45, 4657[42] L. Pulina and A. Tacchella, “Challenging smt solvers to verify neuralnetworks,” AI COMMUNICATIONS, vol. 25, pp. 117–135, 01 2012. →pages 45, 46[43] O. Bastani, Y. Ioannou, L. Lampropoulos, D. Vytiniotis, A. Nori, andA. Criminisi, “Measuring neural net robustness with constraints,” inAdvances in Neural Information Processing Systems 29 (D. D. Lee,M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, eds.),pp. 2613–2621, Curran Associates, Inc., 2016. → page 46[44] W. Xiang, H.-D. Tran, and T. T. Johnson, “Output reachable set estimationand verification for multi-layer neural networks,” 2017. → page 46[45] S. Dutta, X. Chen, S. Jha, S. Sankaranarayanan, and A. Tiwari, “Sherlock - atool for verification of neural network feedback systems: Demo abstract,” inProceedings of the 22nd ACM International Conference on Hybrid Systems:Computation and Control, HSCC ’19, (New York, NY, USA), p. 262–263,Association for Computing Machinery, 2019. → page 46[46] R. Ehlers, “Formal verification of piece-wise linear feed-forward neuralnetworks,” 2017. → page 46[47] A. Lomuscio and L. Maganti, “An approach to reachability analysis forfeed-forward relu neural networks,” 2017. → page 46[48] R. Ivanov, J. Weimer, R. Alur, G. J. Pappas, and I. Lee, “Verisig: verifyingsafety properties of hybrid systems with neural network controllers,” 2018.→ page 46[49] Q. Yang, J. Yang, W. Yu, D. An, N. Zhang, and W. Zhao, “On falsedata-injection attacks against power system state estimation: Modeling andcountermeasures,” IEEE Transactions on Parallel and Distributed Systems,vol. 25, pp. 717–729, 3 2014. → page 47[50] Z. Zhang, R. Deng, Member, IEEE, D. Yau, S. Member, P. Cheng, J. Chen,and Fellow, “Analysis of moving target defense against false data injectionattacks on power grid,” 12 2019. → page 47[51] R. B. Bobba, K. M. Rogers, Q. Wang, H. Khurana, K. Nahrstedt, and T. J.Overbye, “Detecting false data injection attacks on dc state estimation,”2010. → page 4758[52] T. Fukuda and T. Shibata, “Theory and applications of neural networks forindustrial control systems,” IEEE Transactions on Industrial Electronics,vol. 39, pp. 472–489, Dec 1992. → page 47[53] S. Cong and Y. Liang, “Pid-like neural network nonlinear adaptive controlfor uncertain multivariable motion control systems,” Industrial Electronics,IEEE Transactions on, vol. 56, pp. 3872 – 3879, 11 2009. → page 47[54] T. Wang, H. Gao, and J. Qiu, “A combined adaptive neural network andnonlinear model predictive control for multirate networked industrialprocess control,” IEEE Transactions on Neural Networks and LearningSystems, vol. 27, pp. 416–425, 2016. → page 47[55] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. J. Goodfellow,and R. Fergus, “Intriguing properties of neural networks,” CoRR,vol. abs/1312.6199, 2013. → page 47[56] Y. Deng, X. Zheng, T. Zhang, C. Chen, G. Lou, and M. Kim, “An analysis ofadversarial attacks and defenses on autonomous driving models,” 2020. →page 47[57] J. Li, J. Y. Lee, Y. Yang, J. S. Sun, and K. Tomsovic, “Conaml: Constrainedadversarial machine learning for cyber-physical systems,” 2020. → page 4759
Thesis/Dissertation
eng
Electrical and Computer Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Security analysis of deep neural network-based cyber-physical systems
Text