IEEE TRANSACTIONS ON SMART GRID 1 SCPSE: Security

IEEE TRANSACTIONS ON SMART GRID2Inputs Cyber IDS SensorsOffline PreprocessingAccess Policy RulesCyber-Physical State Estimation (online)Attack Graph Template GeneratorCompromised Systems IdentificationPower Flow EquationsPower-System Bad-Data DetectionPower System ModelCyber-PhysicalSituational AwarenessPower System SensorsFig. 1.SCPSE’s high-level architectureand IV. The computational efficiency of SCPSE is discussedin Section V. A prototype implementation and its experimentalresults are presented in Section VI. Sections VII and VIIIreview past related work and conclude the paper.II. SCPSE A RCHITECTURESCPSE data flow. Figure 1 presents a high-level overviewof SCPSE and how its components are interconnected. BeforeSCPSE begins its online operation, it uses the power network’saccess control policies, e.g., firewall rules, and automaticallygenerates an attack graph, called an attack graph template(AGT). The state transitions in an AGT encode all possibleattack paths that an attacker can traverse by sequences ofvulnerability exploitations. Furthermore, SCPSE takes an underlying power system model and calculates a base-case powerflow solution (Figure 1), which reveals how power systemmeasurements should be correlated.During the operational mode, SCPSE monitors the physicalpower and communication networks, detects and analyzesattacks based on the attack graph, and then probabilisticallydetermines the set of computer systems and power systemmeasurements that are likely to have been maliciously compromised. SCPSE then uses that probabilistic information toflag and handle suspicious measurements in order to protectthe power system from the potentially malicious data.In particular, SCPSE uses the past sequence of triggeredIDS alerts to estimate the attack path in the AGT that has beentraversed by the adversary. Because of inherent uncertaintiesin the reported IDS alert notifications, it is not always feasibleto determine the exact attack path traversed. Instead, at eachtime instant, a posterior probability distribution over the AGT’sstate space is calculated according to the false positive andnegative rates of the triggered and non-triggered IDS alerts,respectively. That estimated probabilistic state knowledge reveals the set of privilege domains, i.e., host systems, believedto be compromised in the control network.Potentially modified power measurements are identifiedbased on the given topological information regarding whichpower sensors are managed or processed by the estimated setof compromised hosts. The IDS reports and the correspondingly updated power system state estimator outputs enableSCPSE to provide situational awareness by continuously presenting operators with clear and complete information on thecyber-physical state of the power grid.The combined security state of the power grid is defined inthis work as a binary vector that consists of information relatedto two types of malicious events. First, there are vulnerabilityexploitations, in which the adversary works to obtain specificprivileges in the system. The first set of bits in a state indicateswhether a particular privilege domain, e.g., the root domain onthe historian server, has been compromised. Second, there aremalicious consequences of the attack after a privilege has beenobtained. Specifically, we define consequences as violations ofthe CIA criteria (i.e., confidentiality, integrity, and availability)applied to critical assets in the power grid. For example, theintegrity of a file relay.cfg, which is used to control apower relay, is compromised if the file is maliciously modified,leading to a status change of the underlying relay.The cyber-physical security state encodes the compromisedhost systems and the maliciously modified power measurements. By estimating the cyber-physical state and relaying itto operators, we are capable of responding to attacks. Networkadministrators should develop response strategies for securityattacks that may occur. The strategies may include automatedintrusion response systems. SCPSE neither proposes a newtype of sensor nor presents an automated response mechanism.The main objective of SCPSE is to provide situational awareness of the power grid infrastructures to the operators andthe response systems in charge of taking care of the detectedproblems.III. C YBER S ECURITY-S TATE E STIMATIONAs outlined in Section II, from the power network’s accesscontrol policies, SCPSE generates an AGT and uses it toestimate the compromised set of hosts, given the IDS alerts.The power network’s access control policies are composedof rules about sources (IP/port addresses) that are eitherallowed or not allowed to reach a destination. SCPSE parsesthe rulesets and creates a binary network connectivity matrixthat is a Cartesian product of host systems. The [i, j] entryof the matrix takes on a true value if the traffic from host hito host h j is allowed, and a false value if it is not allowed.The connectivity matrix always includes an Internet noderepresenting a group of hosts outside of the network whereattackers are assumed to initially reside.Attack graph template generation. Generally, every cyberattack path consists of an escalating series of vulnerabilityexploitations by the adversary, who initially has no access tothe system (privilege) but then achieves the privilege requiredto reach his or her attack goals, e.g., modifying a power sensormeasurement. Regardless of the type of the vulnerability, everyvulnerability exploitation (e.g., a malicious buffer overflowagainst the human-machine interface (HMI) server in thepower network) will provide the attacker with control onthe corresponding host computer (e.g., the HMI server inthe previous example). For instance, let us consider a hostsystem H (e.g., an RTU) that is in charge of sending thesensor measurements on one of the power system buses tothe state estimation server. To modify the sensor measurementdata, the attacker needs to get control over H. For example,if the attacker has gotten control over the HMI server (fromthe above example), he or she further needs to exploit a

IEEE TRANSACTIONS ON SMART GRIDvulnerability in the system H so that he or she can modify themeasurements. However, access from the HMI server to thesystem H should be allowed by the network firewall rules (socalled network global access control policies); otherwise, anyattempt by the attacker on the HMI server to access the systemH will be denied automatically by the firewalls. In particular,SCPSE takes into account the global access control policiesthat enumerate all possible attack paths that the attackers cantraverse through the power grid network.We present the attack graph template (AGT), i.e., anextended attack graph, which represents all possible attackpaths (unlike traditional attack graphs [6], which only addresspreviously known paths). To further clarify, an AGT, bydesign, would address a zero-day (previously unknown) bufferoverflow exploitation of a historian server process, while atraditional attack graph would be unaware of it. An AGT is astate-based directed graph, in which a state is defined as the setof compromised privilege domains. Therefore, the initial stateis ( ), in which the attacker does not yet have any privilegesover the power network. Each state transition represents aprivilege escalation that is achieved through a vulnerabilityexploitation. Therefore, any path on the AGT graph representsan attack path in the power network.To generate an AGT, SCPSE pessimistically considers everyhost within the power network to be a single potentiallyvulnerable privilege domain. In particular, SCPSE automatically generates an AGT by traversing the connectivity matrixand concurrently updating the AGT. First, SCPSE creates theAGT’s initial state ( ) and starts the AGT generation with thenetwork’s entry point (Internet) node in the connectivity matrix. Considering the connectivity matrix as a directed graph,SCPSE runs a depth-first search (DFS) on the graph. Whilethe DFS is recursively traversing the graph, it keeps track ofthe current state in the AGT, i.e., the set of privileges alreadygained through the path traversed so far by the DFS. Whenthe DFS meets a graph edge [i, j] that crosses over privilegedomains hi to h j , a state transition in the AGT is created if thecurrent state in the AGT does not include the privilege domainof the host to which the edge leads, i.e., h j . The transition inthe AGT is between the current state and the state that includesexactly the same privilege set as the current state plus the hosth j directed by the graph edge [i, j]. The AGT’s current statein the algorithm is then updated to the latter state, and thealgorithm proceeds until no further updates to the AGT arepossible according to the connectivity matrix. At that point,the offline AGT generation is complete, and by design, theAGT includes all possible attack paths launching from remote(Internet) host systems against the network. Figure 2 shows ahighly simplified power network and its corresponding AGTmodel. Connectivity matrix elements are indicated with dashedarrows among network component pairs.AGT-to-HMM conversion. The AGT is converted to ahidden Markov model (HMM) [7], which will be used laterto determine the attack path traversed by the attacker at eachtime instant, given the past set of triggered IDS alerts.To generate the HMM model, SCPSE enhances the AGTusing the cyber network’s topology to encapsulate knowledgeabout deployed cyber-side IDSes. Specifically, each AGT edge3ØAttack BB: Data HistorianAttack AA: Web serverBAAttack AAttack CC: Relay ControllerAttack BA, BB, CRelayFig. 2.Attack CA, B, CA highly simplified power network and the corresponding AGTis tagged by a (possibly empty) set of IDSes that monitor theedge’s corresponding network link within the power network.SCPSE later uses these tags to map IDS alerts (observations)to their corresponding state transitions to estimate the attackpath traversed by the attacker. In practice, IDSes tend to reportfalse positives and may also miss some incidents, i.e., falsenegatives. To account for the inherent uncertainties in IDS alertnotifications, SCPSE labels the IDS tags on state transitionswith their false positive and negative rates.Cyber security-state estimation. During its online operation, SCPSE makes use of the HMM model and online IDSalerts to probabilistically deduce the attacker’s previous actions(vulnerability exploitations), and hence the set of alreadycompromised host systems. Indeed, IDS alerts provide SCPSEwith the online information about the cyber-side securityincidents and compromises. There are two major types ofIDS solutions that can be used to pinpoint adversarial cyberpenetrations: 1) host-based techniques that run and monitorfor misbehaviors within host systems, such as file integritycheckers and CPU/memory overconsumption monitors; and2) network-based solutions that run on network devices andhence are easier to deploy, and look for attack signaturesand anomalies based on limited available information obtainedfrom the packet headers and payloads, if the traffic is notencrypted. For SCPSE, the specific type of the IDS system isnot relevant, and the only information needed is the intrusiondetection accuracy level; that can be assigned by security admins or historical data analysis techniques [8]. SCPSE makesuse of the HMM to track the attacker’s action sequence as theIDS alerts are sequentially triggered. To do so, SCPSE usesan HMM smoothing algorithm [7] to estimate the network’scurrent security state given the past triggered IDS alerts. In anHMM, unlike a regular Markov model, states are not directlyvisible, but observations (IDS alerts) are visible. The goal isto utilize the past observation sequence and probabilisticallyestimate the traversed state sequence (attack path) consideringthe false positive and negative rates of the monitoring IDSprobes.Formally, SCPSE models each attack scenario as a discretetime hidden Markov process, i.e., event sequence Y (y0 , y1 , · · · , yn 1 ) of arbitrary length. yi (si , oi ), where si is

IEEE TRANSACTIONS ON SMART GRIDan HMM state at the ith step of the attack and is unobserved,and the observation oi is the set of triggered IDS alerts atthat step. The initial state is defined as s0 ( ), as discussedabove.SCPSE’s main responsibility is to compute Pr(st o0:t ),that is, the probability distribution over hidden states at eachtime instant, given the HMM model and the past IDS alertso0:t (o0 , · · · , ot ). In particular, SCPSE makes use of theforward-backward smoothing algorithm [7], which, in the firstpass, calculates the probability of ending up in any particularHMM state given the first k IDS alerts in the sequencePr(sk o0:k ). In the second pass, the algorithm computes aset of backward probabilities that provide the probability ofreceiving the remaining observations given any starting pointk, i.e., Pr(ok 1:t sk ). The two probability distributions canthen be combined to obtain the distribution over states at anyspecific point in time given the entire observation sequence,Pr(st o0:t ) Pr(sk o1:k , ok 1:t ) Pr(ok 1:t sk ) · Pr(sk o1:k )(1)where the last step follows from an application of Bayes’srule and the conditional independence of ok 1:t and o1:k givensk . Having solved the HMM’s smoothing problem for Pr(st o0:t ), SCPSE probabilistically knows about the current cybersecurity state, i.e., the set of compromised host systems. Next,our goal is to use the knowledge of current cyber security stateto accurately estimate the underlying power system state.IV. P OWER S YSTEM S TATE E STIMATIONAs discussed before, the cyber-physical security state of thepower grid is defined for SCPSE as the set of compromisedhost systems and maliciously modified power measurements.In Section III, we introduced an algorithm to probabilisticallydetermine the set of compromised hosts at each time instant.This section explains how SCPSE uses the knowledge aboutcompromised hosts to identify the set of maliciously modifiedpower measurements, the so-called bad data. The bad-datadetection enables SCPSE to estimate the underlying powersystem state correctly.Background. Before presenting the bad-data detection algorithm, we provide a brief review on the power system flowequations and state estimation. In a power grid infrastructure,the underlying power system is represented as a set of nonlinear AC equations that include active and reactive power flows,Pi j V2i [ Gi j ] Vi V j [Gi j cos(θi θ j ) Bi j sin(θi θ j )] (2)Qi j V2i [ Bi j ] Vi V j [Gi j sin(θi θ j ) Bi j cos(θi θ j )](3)where Pi j and Qi j are, respectively, active and reactive powerflows from bus i to bus j. Gi j and Bi j denote the elements inthe i, j position of the real and imaginary components of thesystem admittance matrix Ybus G jB, which contains thenetwork line parameters (I Ybus V) [9].The power system state estimation problem involves estimation of the present conditions in a power system based on snapshots of real-time measurements, i.e., real and reactive power.The estimated quantities include bus voltage magnitudes andangles that constitute the power system state variables. The4estimate is computed using known equations, which relatethe power system measurements to the unknown states thatare to be estimated. The estimates depend on the power flowequations that are derived from the power system topology. Forexample, in equations (2) and (3), the values of Pi j and Qi j aremeasured by the power sensors, and the values of the powersystem state vector (i.e., voltage magnitudes V and phaseangles θ), are estimated using the iterative Newton-Raphsonstate estimation equations [9]. Once the state variables, i.e.,bus voltage phasors, are known, all other quantities, such ascurrents and nonmeasured real and reactive line flows, can becomputed [9].In general, power system state estimation is typically anoverdetermined problem, since there are more measurementsavailable than are needed to solve for the unknown voltagemagnitudes and angles. In other words, the power system stateestimation server can still estimate the power state correctly ifredundant measurements are ignored. However, in a practicalattack-free situation, power measurements may include zeromean Gaussian noise due to natural and accidental faults.Therefore, deployment of redundant power sensors improvesthe accuracy of power system state estimation.In certain cases, it is possible for modified measurementsto cause incorrect power system estimates without beingdetected. These unobservable attacks must satisfy the powerbalance equations.Bad-Data Detection. Many proposed schemes exist forbad-measurement identification [10]. In [2], [11], [12],and [13], it is shown that traditional detection schemes areineffective against coordinated malicious false data injection.Residual-based approaches [9] are the most widely used techniques for handling nonmalicious accidental failures. In summary, those algorithms examine the L2 -norm of the measurement residual z Hx̂ , i.e., the difference between the truemeasurements z and the estimated values of the measurementsHx̂, which are calculated using the power system state estimatex̂ and the system matrix H. The measurements whose L2 -normis greater than a certain threshold τ are marked as bad data.However, unobservable false-data injection attacks [11] provethe inability of residual-based techniques to handle interactingor malicious bad-data modifications [14], as they can changethe estimates without impacting the residual. The failure ofsuch techniques results from their dependence on computationof an initial estimate x̂ using all the measurements, which maybe affected by the bad data.To identify malicious data modifications, we present a newscalable and combinatorial-based bad-data detection (BDD)algorithm. The algorithm makes use of the power measurements as well as the cyber security state estimation result,i.e., the posterior distribution over the HMM’s state spacePr(st o0:t ) (Section III). The main idea is to circumventthe problem of needing to compute the initial power systemestimate x̂ from the full data set by initially throwing outthe set of suspicious measurements. A trivial solution wouldbe to blindly consider each combination of the sensors tobe corrupted, then estimate the power system state for eachcombination without using measurements from those sensors,and finally calculate z Hx̂ to identify the true corrupted

IEEE TRANSACTIONS ON SMART GRIDmeasurements. However, that approach is not generally scalable for use in large-scale power systems, as M sensors yield2M possible combinations. As discussed below, SCPSE usesthe posterior distribution Pr(st o0:t ) to order and limit thenumber of combinations to check.Algorithm 1: Power system BDD algorithm12345678910111213141516Input: P(st o0:t ), z, deadlineOutput: [pwr state, bad data]cybr state, pwr state, bad data;εm 0;List OrderP(st o0:t ) (S);while get time() deadline dos List.pop();c measurement combination(s);[zc , Hc ] Updatec (z, H);if Observable(zc , Hc ) thenx̂ Newton Raphson(zc , Hc );ε z Hx̂ ;if εm ε then[pwr state, bad data] [x̂, c];ε εm ;endendendSCPSE implements Algorithm 1 to detect maliciously badpower measurements. The main inputs (Line 1) are the cybersecurity state estimation result Pr(st o0:t ), the power systemmeasurements, and a timeout threshold for the algorithm.SCPSE initially orders the HMM states in descending orderaccording to the estimated posterior probability P(st o0:t )(Line 3). Then, SCPSE iteratively checks combinations ofmeasurements (Line 4). In particular, the most likely HMMstate s is first picked from the list (Line 5). Using the powergrid topology, SCPSE knows which measurements could ormight have been corrupted, given the set of compromised hostsencoded by s. The set of potentially corrupted measurementsis stored in a binary vector c (Line 6). To clarify, assuming thatthere are a total of m measurements, cm 1 is a binary vectorin which 1s and 0s represent bad and good measurements,respectively. For instance, none of the measurements aremarked as potentially corrupted in the measurement combination c (0, 0, . . . , 0)T .The idea is to throw away the measurements that correspondto the 1 values in c, and proceed with the normal state estimation routine using the remaining measurements. Given thecalculated c, rows of the z and H matrices that correspond tothe 1 values in c are deleted, and the results are saved in zc andHc (Line 7). Using the dimensionally reduced matrices zc andHc , the power system state is then estimated (Line 9). The stateestimate x̂ is used to reconstruct the estimated measurementvector ẑ Hx̂, which is compared to the actual measurementsz (Line 10). During each iteration of the algorithm, the mostdeviating ẑ so far and the related values are stored (Line 12).In essence, each iteration (Line 4) checks a specific set ofpotentially bad measurements to determine whether or not theydiffer significantly from the values they should have, whichare computed based on the remaining (good) measurements.Finally, the procedure returns the best estimates for the powersystem state, and the set of measurements that were identifiedas corrupted (Line 1).5One main point in the algorithm is the observability condition (Line 8), which checks whether it is possible to estimatethe power system state while ignoring a particular subsetof measurements c. Otherwise, if too many measurementsare compromised and must be removed, the system will nolonger be observable, and the algorithm will not be able toproceed with that particular iteration (Line 8). In general,for a power system to be observable, it is necessary for thenumber of available measurements to be equal to or largerthan the number of power system state variables. However,it may be that only parts of the network are observable andsome other parts of the system are not observable, even if thetotal number of good measurements is sufficient. Hence, it isnot only important that there be enough good measurements,but also that they come from well-distributed parts of theunderlying power system. The entire power system is said tobe observable if all state variables can be estimated based onthe given measurements. Further discussion of observabilityanalysis is beyond the scope of this paper. The interestedreader is referred to the literature concerning measurementplacement for observability [10].It is worth stressing that Algorithm 1 provides bad-datadetection mainly for malicious cases and is a supplementto, rather than a replacement for, residual-based approaches,which are suitable for detecting noninteracting and naturalerrors. The proposed algorithm is, in essence, a combinatorialbased solution that makes use of cyber-side IDS reports toimprove its scalability. In the case of natural errors, IDSreports would not provide any useful information, and hencethe proposed algorithm could not always identify corruptedmeasurements within a short amount of time. Consequently,the proposed approach and traditional residual-based techniques should be used together to achieve efficient detectionof measurement corruptions due to both security attacks andaccidental errors.V. C OMPUTATIONAL E FFICIENCYPower systems are large, sparse systems in which each busis connected to at most a few other buses. Thus, power systemsanalysis takes advantage of sparsity in its computations ofnetwork solutions [15], [16]. Likewise, the same sparsity thatpermits the efficient solution of large-scale power networksalso permits efficient solution of the possible communicationsattack paths. SCPSE takes advantage of the network’s topological sparsity and uses an approximation algorithm (discus

IEEE TRANSACTIONS ON SMART GRID 1 SCPSE: Security-Oriented Cyber-Physical State Estimation for Power Grid Critical Infrastructures Saman Zonouz, Katherine M. Rogers, Robin Berthie