Preventing Advanced Persistent Threats in Complex Control Networks

Preventing Advanced Persistent Threats in Complex Control Networks Juan E. Rubio, Cristina Alcaraz and Javier Lopez Department of Computer Science, University of Malaga, Campus de Teatinos s/n, 29071,Malaga, Spain {rubio,alcaraz,jlm}@lcc.uma.es Abstract. An Advanced Persistent Threat (APT) is an emerging attack against Industrial Control and Automation Systems, that is executed over a long period of time and is difficult to detect. In this context, graph theory can be applied to model the interaction among nodes and the complex attacks a↵ecting them, as well as to design recovery techniques that ensure the survivability of the network. Accordingly, we leverage a decision model to study how a set of hierarchically selected nodes can collaborate to detect an APT within the network, concerning the presence of changes in its topology. Moreover, we implement a response service based on redundant links that dynamically uses a secret sharing scheme and applies a flexible routing protocol depending on the severity of the attack. The ultimate goal is twofold: ensuring the reachability between nodes despite the changes and preventing the path followed by messages from being discovered. Keywords: advanced, persistent, threat, attack, detection, response, consensus, opinion, dynamics, secret, sharing, redundant, topology 1 Introduction The interconnection of industrial environments with modern ICT technologies has increased the number of internal and external threats in this context, including those from traditional IT systems (e.g., malware, spyware, and botnets). Among these, the Advanced Persistent Threats (APT) are a new class of sophisticated attacks that are executed by well-resourced adversaries over a long period of time. They usually go undetected because they leverage zero-day vulnerabilities and stealthy and evasive techniques [1]. While APTs originally attacked military organizations, they are now targeting a wide range of industries and governments with multiple purposes: economic (espionage, intellectual property), technical (access to source code), military (revealing information) or political (destabilization of a company). Their goal is to get through the organization’s network and take over the industrial control systems. Stuxnet was the first attack of this kind, reported in 2010, which sabotaged the Iranian Nuclear Program by causing physical damage to the infrastructure and thereby slowed down the overall process. Ever since, the number of reported vulnerabilities concerning Industrial Control Systems has been dramatically increasing, as the research community has become more involved and new attacks have been revealed. Like Stuxnet, all APTs are tailored to the specific victim’s network topology, and they count on a defined succession of steps: firstly, the attacker intrudes on the network by using social engineering (e.g., by means of fraudulent e-mails containing trojans); secondly, they install a backdoor from which the attackers connect to the target network. Then, several exploits and malware are used to compromise as many computers in the victim network as possible, to ultimately modify the productive process or exfiltrate information back to the attacker domain. On the whole, an APT is a meticulously planned attack adapted to the target infrastructure, one whose complexity makes the use of traditional countermeasures (e.g., antivirus, firewalls) insufficient to tackle them. An additional e↵ort is required to mitigate their e↵ects, by involving the organization in security awareness training and introducing novel services in continuous evolution within the company [2]. For this reason, we propose the design of practical mechanisms to firstly detect and then e↵ectively respond to these attacks, applied to a common network representation. We can summarize our contributions as: –Modeling the evolution of an APT within the victim network topology. –Implementation of a multi-agent system for the detection of an APT based on the topological changes su↵ered in selected parts of the network, observed by hierarchically chosen nodes in accordance with controllability criteria. –Use of redundancy edges and random routing protocols to overcome the network deformation provoked by the APT and to avoid compromised systems, ensuring the reachability between nodes and the survivability of the network. The remainder of this paper is organized as follows: Section 2 outlines preliminary concepts about dynamic control networks and describes the threat model used for the APT. In Section 3 the detection of these attacks is addressed by means of a network decision model. Based on this mechanism, response techniques are implemented in Section 4, which are theoretically and experimentally analyzed in Section 5. 2 Preliminaries 2.1 Structural Controllability Considering the cost of the implementation of large control networks from a research point of view, it becomes mandatory to model and simulate the problem through graph theory, taking into account the network topology and the nature of its distribution. Specifically, we focus on topologies of the type power-law y/ x↵[3], since the vast majority of critical control systems follow these structures, which produce small sub-networks similar to current control substations. With the purpose of helping the reader understand the underlying theoretical concepts of our model, topics related to structural controllability and power dominance are described here. The concept of structural controllability was introduced by Lin in 1974 [4], which associates the control to a subset of nodes with the maximum capacity of dominance. Let G=(V,E)beadirected graph that represents the network topology, given by its adjacency matrix, that is, a square binary matrix Mwith dimension |V|where M(i, j)=1whenever(vi,v j)2Eand zero otherwise. Through G(V,E), it is possible to characterize dynamic control networks including loops and weighted edges that represent the interconnection of control devices with remote terminal units (e.g., sensors or actuators). These links contain the maximum capacity to conduct the main traffic between two points, which is defined as the control load capacity (CLC). To represent this traffic, we use the edge betweeness centrality (EBC) [5]. It is an indicator that represents the sum of the fraction of the shortest paths that pass through a given edge, so that edges with the highest centrality participate in a large number of shortest paths. The result is a weighted matrix related to Gw(V,E) whose weights are computed as follows: EBC =X s,t2V (s, t|e) (s, t)(1) where (s, t) denotes the number of shortest (s,t)-paths and (s, t|e)the number of paths passing through the edge e. On the other hand, let the inneighborhood Nin iof a node ibe the set of nodes vjsuch that (vj,v i)2E,while the out-neighborhood Nout iis the set of nodes vjsuch that (vi,v j)2E. Consequently, let the in-degree di inof a node vibe the number of its incoming edges, i.e., din i=|Nin i|, while the out-degree dout iis the sum of its outgoing edges, i.e., di=|Nout i|. Taking these concepts and EBC into account, the Dominating Set (DS) of a graph Gcan be defined as the minimum subset of nodes D✓Vsuch that for each vertex vi62 Dis adjacent to at least one member of D, that is 9vk2 D|(vk,v i)2E. These nodes Dwith highest control capacity will be those with the highest edge betweeness centrality EBC(v) for all their outgoing edges. The creation of this set is explained in Algorithm 1. Related to this concept, the Power Dominating Set (PDS) consists in an extension of the DS by including new driver nodes (denoted by ND), those with the maximum capacity of dominance. The original formulation of this set was given by Haynes et al. in [6], and was later simplified into two fundamental observation rules by Kneis et al. in [7]: OR1 A vertex in NDobserves itself and all its neighbors, complying with DS. OR2 If an observed vertex v of degree d+2is adjacent to d1observed vertices, the remaining un-observed vertex becomes observed as well. This also implies that OR1 ✓OR2 given that the subset of nodes that comply with OR1 becomes part of the set of nodes that complies with OR2. For our purpose in this paper, the dominating nodes play the role of agents that detect topological changes in their surroundings that may be derived from an APT attack, and establish backup links that ensure the continuity of the network. Algorithm 1 DS(G(V,E)) output (DS ={vi,...,v k}where 0i|V|) local: BC(V)representing betweeness centrality of V Choose v 2V with highest BC DS {v}and N(DS) {vi,...,v k}8ijk\(v, vj)2E while V(DS [N(DS)) 6=;do Choose vertex w 2V(DS [N(DS)) with highest BC DS DS [{w} N(DS) N(DS)S{vi,...,v k}where 8ijk\(w, vj)2E end while 2.2 Threat model: Representation of APT Attacks Assuming a successful intrusion inside a network represented by a matrix M, we model an APT with a succession of attacks perpetrated on its topology. Specifically, just as an actual APT works, the attacker firstly selects one node and then makes several lateral movements in order to find new nodes to compromise. Since we want to provide realism in this model and consider a scenario of high criticality, we assume the attacker always seeks those nodes with more controllability, that is, those belonging to the DS and hence the ones with the highest betweeness centrality. In each of the steps in its life cycle, the APT can commit individual attacks on the topology, i.e. changing the edges from the compromised node at a given time instant. This consequently generates a new matrix M’. The types of attacks can be: *Removal of an incoming edge: given the vertex vithat represents the compromised node such that vjexists and M(j, i) = 1, it implies setting M(j, i) = 0. *Removal of an outgoing edge: given the vertex vithat represents the compromised node such that vjexists and M(i, j) = 1, it implies setting M0(i, j) = 0. *Addition of an incoming edge: given the vertex vithat represents the compromised node such that vjexists and M(i, j) = 0, it implies setting M0(i, j) = 1. *Addition of an outgoing edge: given the vertex vithat represents the compromised node such that vjexists and M(i, j) = 0, it implies setting M0(i, j) = 1. In a simple version of the APT, we suppose that the kind of the attack and the first node compromised within the network are chosen randomly. From that moment on, the attack migrates to the adjacent node with highest betweeness centrality, simulating the fact that the attacker can perform a reconnaissance of the network when looking for potential victims that deal with higher loads of control traffic. The resulting attacker behavior is described in Algorithm 2. An example of an APT with three attacks over a defined network topology is depicted in Fig. 1, where driver nodes are marked in black to show how the APT always migrates to vertices with higher controllability. Firstly, node 4 is selected and an outgoing edge is added towards node 2. Then, the attacker moves to node 6 and removes the edge coming from node 3 and then, since node 6 still has dominance, the attack stays there and removes the edge going to 7. Algorithm 2 Advanced persistent threat life cycle output: M0representing the resulting matrix local: M representing G(V, E), numOfAttacks attackedNode random vi2E M0 M for i:=1 to numOfAttacks step 1do attack randomAttack over attackedNode (edge addition or removal) update M0based on attack attackedNode SelectNewAttackedNode(M, attackedNode) if attackedNode == null then attackedNode random vi2E end if end for function SelectNewAttackedNode(M,node) childNodes vertexes vj|M(node, vj)=1 parentNodes vertexes vk|M(vk,node)=1 candidates childNodes [parentNodes maxCentrality := 0 attackedNode null for vertex v in candidates do centrality CalculateBetweenessCentrality(v) if centrality > maxCentrality then attackedNode v end if end for return attackedNode end function Original network 1 6 3 2 7 54 Attack 1 1 6 3 2 7 54 Attack 2 1 6 3 2 7 54 Attack 3 1 6 3 2 7 54 Final network 1 6 3 2 7 54 Figure 1. Example of APT with 3 attacks: 1st: Addition of edge from node 4 to node 2. 2nd: Removal of edge from node 3 to node 6. 3rd: Removal of edge from node 6 to node 7. 3 APT Detection through Opinion Dynamics Now we have modeled the e↵ect of an APT over the network topology, in this section we describe a feasible method to allow the network to locate subtle changes in certain parts, making it easier to accurately deploy response techniques to overcome the e↵ect of one of these threats. We start with the notion introduced before: let us suppose a power law distribution network defined by the directed graph G=(V,E) and represented by the adjacency matrix M. Let us also suppose the presence of nagents deployed over that network (the DS nodes of the graph G), so each node vi2Vis connected to one or more agents. We further assume that the agents can also communicate with each other according to a communication network represented by the directed graph Gc=(V,Ec), where for all (vi,v j)2Ec, we have that (vi,v j)2E. Our goal is to put into practice a distributed cooperative algorithm among these agents to detect precise topology attacks in their neighborhood by exchanging information on changes produced in their observable nodes. In this regard, various decision models can be imported from graph theory, among which we can highlight consensus and opinion dynamics. In the consensus approach, a collection of agents cooperate to reach a common objective by sharing information about their state and other environmental conditions [8]. Such negotiation depends on the network topology, so it can be leveraged to collectively build a global indicator of the entire network health at a given moment. Compared to this algorithm, opinion dynamics proposes a model that admits the fragmentation of patterns, so the aforementioned agents may di↵er in their opinions during the negotiation process [9]. These network partitions will depend on the closeness to the opinion of each node, which is calculated based on the number of topological changes they detect. Therefore, it makes it easier to identify which areas of the network are more a↵ected by the action of the APT and to what extent. Opinion dynamics originally models the influence among individuals in a group or the entire society, where there is a wide spectrum of opinions. Each agent crafts its own opinion taking into consideration the ones from the rest of agents to a certain extent. Eventually, the opinions are distributed into several clusters. For our purpose, it implies fragmenting the network according to the multiple changes that could occur in separate areas, whose individual consensus value raises an indicator of the severity of the attacks over that particular portion of the topology. Let us suppose that xi(t) represents the opinion of a fixed agent iat time t. The vector x(t)=(x1(t),...,x n(t)) represents the opinion profile at time tfor all the agents. Given an agent i, the weight given to the opinion of any other agent j is denoted by aij. For simplicity, we consider aii such that Pn k=1 aik = 1. Therefore, agent ialso takes into account its own opinion during the opinion formation process, which can be described as follows: xi(t+ 1) = ai1x1(t)+ai2x2(t)+... +ainxn(t) In a matrix notation it can be written as: x(t+ 1) = A(t, x(t))x(t) where the matrix A(t, x(t)) = [aij] is the square matrix that collects the weights, which summarize the relationships between the agents’ opinions. These weights can change over time or by opinion, so finally an agent iadjusts its opinion in period t+ 1 by taking a weighted average of the opinion of agent j at time t. When ttends to infinity, the final behavior of the opinion profile may lead to a consensus among all or part of the agents, which can also be visualized graphically. Returning to our domain, we execute this algorithm assuming that xi(0) will be calculated for each agent ias follows: let us suppose that BC(vi)represents the original betweeness centrality for each agent ithat, as explained, works as an indicator of the controllability of that particular node. If BC0(vi)isthe betweeness centrality of the same agent after being victim of a particular attack of those defined in Section 2.2 or another node in its neighborhood, we define the initial opinion xi(0) as xi(0) = |BC0(vi)BC(vi)| BC(vi)(2) Consequently, xi(0) holds the ratio of change in the controllability of an agent iafter an attack, compared to its initial state (due to an increase or decrease of adjacent edges). We assume that when the value was originally zero or the resulting ratio is greater than 1, the result is normalized to the value of 1. Altogether, if we have the vector x(0) concerning the initial opinion of all agents in the DS, we can run the opinion dynamics algorithm to obtain a value of the change ratio of the network after su↵ering an individual attack, making it possible to distinguish between di↵erent clusters of agents with similar opinion. In this case, the closeness among opinions, which is represented by the matrix A with the weights assigned for each agent, has been modeled according to the di↵erence in the degree of change (the individual opinion each agent holds): for two given agents iand j, if the di↵erence is below a determined epsilon value (e.g., 0.3), they increase the weight given to each other; this models the fact that agents that experiment a similar degree of change in their surrounding topology must agree on the presence of an anomaly in their respective area. Figure 2 shows the opinion dynamics algorithm for a network of 30 nodes and 17 agents after su↵ering an APT comprising 10 attacks. The lines represent the evolution in the opinions for each agent, so finally there is multiple consensus between them: in particular, there are only two agents that indicate relatively large changes (more than 0.5 of fluctuation in their betweeness centrality). However, four agents agree on a change of about 0.25 points around their zone of influence, and many of them indicate a fault of approximately 0.1 in the zone governed by these nodes. As can be seen in the figure, a ↵value has been added to the plot, which holds the ratio of agents that find a consensus on the amount of degree experienced. This value, together with the opinion about the changes in the topology, serves as the criticality indicator that regulates how strong the response technique must be to mitigate the e↵ects of the APT. 0 2 4 6 8 10 12 14 16 18 20 Time(Steps) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Opinion Figure 2. Calculus of the opinion dynamics for a set of agents 4 APT Response Once we have obtained a measure of the extent to which the network topology is at risk due to the e↵ect of an APT attack, we are in a position to adopt multiple response techniques. We set the goal of preserving the connectivity for all those nodes in charge of delivering control signals to the rest of nodes of the network. According to the di↵erent change ratios raised by the opinion dynamics algorithms, we can apply di↵erent techniques in separate nodes of the network. Specifically, we suppose a scenario where we wish to ensure that one node i belonging to the DS wants to send control messages to another node jin the network. This is done in the presence of an APT that can remove certain edges that originally enabled both nodes to communicate over a defined path, traversing other points of the topology [10]. At the same time, we want to avoid hopping over compromised nodes that may be victims of the APT and hence intercept these sensitive packets, preserving confidentiality by this means. Moreover, it is desirable that the communication pattern (i.e., the paths described by the messages when being transmitted over the network) is as random as possible, so as to guarantee that the attacker cannot easily determine the topology of the network. As a result, we have a security service that ensures the continuity of the network until the APT has been successfully removed from the system. To sum up, we seek these three objectives when designing a response technique: (a) Ensure the presence of a path between node iand jwhen possible. (b) Define a routing protocol that prevents determining the path. (c) Introduce a mechanism to avoid the interception of messages. To satisfy objective (a), we propose building an edge-redundant network with hidden edges that are added to the original network topology, so these auxiliary links can be leveraged in the event a path between two given nodes is lost after an APT attack. To accomplish this, we create a parallel network from G=(V,E), which we name G0=(V,E0), where E0contains the same edges as Eand includes new ones from the DS nodes to recover the controllability of the network. Specifically, we define and compare three di↵erent strategies: – STG1: addition of redundant edges to all nodes in the network. – STG2: addition of redundant edges only to DS nodes. – STG3: addition of redundant edges only to nodes that are not included in the DS. Our aim is to compare their level of response in terms of message loss and the overhead they experience, as described in Section 5. Algorithm 3 describes the procedure by which redundancy is added depending on the strategy selected: for each vertex, a set of candidates is created that includes the DS and excludes its parents and the node itself. In the case it is empty, we simply select the DS with maximum out-degree as the new parent of the aforementioned vertex, creating a new edge by this means. It is important to note that during the process, it is ensured that the resulting network G0=(V,E0) fulfills OR1 and OR2 conditions, as stated in [11]. On the other hand, to address objectives (b) and (c), we leverage a secret sharing scheme [12]: a secret (i.e., control message) is divided into nshares that are distributed among the sender’s neighborhood nodes and follow independent routes, so that the recipient cannot reconstruct the message until it collects, at least, a defined number kof them, where 1 kn. In the case we have k= 1, it can be considered as the basic level of security, as the message in clear is sent over a determined path over the network. If we have k=n, then the recipient must collect all the shares to reconstruct the original message. At this point, since our aim is to provide a security mechanism that bases its robustness on the criticality of the attack detected, the election of nwill depend on the number of DS agents whose opinion is similar, for which we make use of the ↵ value defined in Section 3. Namely, the maximum number of shares to divide the original message into depends on the ratio of agents that have experienced the same severity in the attacks against their surrounding nodes: the greater the number of DS that experience the same criticality, the greater the number of shares. However, the kvalue can be random (ranging from 1 to n) in order to make the recovery method as stochastic as possible and thereby not leak any information about the topology when analyzing the stream of messages. The resulting methodology, to divide the messages into shares and send them over the network when it has been attacked, and opinion dynamics has been executed, is described in Algorithm 4. It is important to note that the respective shares are arbitrarily sent over the original and redundant links, in order to make the protocol as misleading for the attacker as possible. Figure 3 shows how shares are divided and distributed over the network leveraging a pathfinding algorithm 0 10 20 30 40 50 60 Attacks 0.05 0.1 0.15 0.2 0.25 Global efficiency Graph global efficiency after attacks Original network STG1 STG2 STG3 (a) 100 nodes 0 10 20 30 40 50 60 Attacks 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2 0.22 Global efficiency Graph global efficiency after attacks (b) 200 nodes 0 10 20 30 40 50 60 Attacks 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2 Global efficiency Graph global efficiency after attacks (c) 300 nodes Figure 6. Global efficiency with di↵erent strategies after 50 attacks 6 Conclusions APT attacks must be addressed with innovative techniques that supplement traditional detection and response techniques. As for the former, we have put into practice a dynamic decision mechanism by making use of graph theory and structural controllability concepts and defining a framework of attacks. That allows us to accurately identify topological anomalies in the network with di↵erent degrees of criticality. Accordingly, we have proposed the design of a redundant topology that allows the continuity of the network and also preserves privacy by making the routing process as uncertain as possible for an external attacker. Future work will involve the creation of a richer taxonomy of attacks that not only focus on topological changes, but also on the stealthy compromise of selected nodes within the network. The integration of other distributed decision mechanisms will be also studied, together with restoration and recovery services that ensure a better resilience against APT attacks. Acknowledgements The first author is supported by the Spanish Ministry of Education through the National F.P.U. Program under Grant Agreement No. FPU15/03213. In addition, this work has been partially supported by the the Andalusian Government Research Program through the FISICCO project (P11-TIC-07223) and by the Spanish Ministry of Economy and Competitiveness through the PRECISE project (TIN2014-54427-JIN). References 1. Ping Chen, Lieven Desmet, and Christophe Huygens. A study on advanced persistent threats. In IFIP International Conference on Communications and Multimedia Security, pages 63–72. Springer, 2014. 2. Nikos Virvilis, Dimitris Gritzalis, and Theodoros Apostolopoulos. Trusted computing vs. advanced persistent threats: Can a defender win this game? In Ubiquitous Intelligence and Computing, 2013 IEEE 10th International Conference on and 10th International Conference on Autonomic and Trusted Computing (UIC/ATC), pages 396–403. IEEE, 2013. 3. Giuliano Andrea Pagani and Marco Aiello. The power grid as a complex network: a survey. Physica A: Statistical Mechanics and its Applications, 392(11):2688–2700, 2013. 4. Ching-Tai Lin. Structural controllability. IEEE Transactions on Automatic Control, 19(3):201–208, 1974. 5. Sen Nie, Xuwen Wang, Haifeng Zhang, Qilang Li, and Binghong Wang. Robustness of controllability for networks based on edge-attack. PloS one, 9(2):e89066, 2014. 6. Teresa W Haynes, Sandra M Hedetniemi, Stephen T Hedetniemi, and Michael A Henning. Domination in graphs applied to electric power networks. SIAM Journal on Discrete Mathematics, 15(4):519–529, 2002. 7. Joachim Kneis, Daniel M¨olle, Stefan Richter, and Peter Rossmanith. Parameterized power domination complexity. Information Processing Letters, 98(4):145–149, 2006. 8. Vincent D Blondel, Julien M Hendrickx, Alex Olshevsky, and John N Tsitsiklis. Convergence in multiagent coordination, consensus, and flocking. In Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC’05. 44th IEEE Conference on, pages 2996–3000. IEEE, 2005. 9. Rainer Hegselmann, Ulrich Krause, et al. Opinion dynamics and bounded confidence models, analysis, and simulation. Journal of Artificial Societies and Social Simulation, 5(3), 2002. 10. Cristina Alcaraz and Javier Lopez. Safeguarding structural controllability in cyberphysical control systems. In European Symposium on Research in Computer Security, pages 471–489. Springer, 2016. 11. Cristina Alcaraz and Stephen Wolthusen. Recovery of structural controllability for control systems. In International Conference on Critical Infrastructure Protection, pages 47–63. Springer, 2014. 12. Adi Shamir. How to share a secret. Communications of the ACM, 22(11):612–613, 1979. 13. Edsger W Dijkstra. A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269–271, 1959. 14. Chin Yang Lee. An algorithm for path connections and its applications. IRE transactions on electronic computers, (3):346–365, 1961. 15. Bryan Ek, Caitlin VerSchneider, and Darren A Narayan. Global efficiency of graphs. AKCE International Journal of Graphs and Combinatorics, 12(1):1–13, 2015.