-Attack trees are often used to analyze a system or detect application programs attacks. To aid in software design, a method to create safe and stable systems should be created. An attack tree has multiple levels and is composed of different nodes, including root nodes, internal nodes, and leaf nodes. These nodes can be separated into parent nodes and child nodes when discussing their relation. Child nodes are defined as conditions that must be satisfied to make their direct parent nodes true. Although an attack tree can express vertical relationships between nodes well, it usually ignores parallel relationships of different branch nodes. Moreover, the relation between parent-child nodes may be inaccurate due to a poorly designed attack tree. To solve these problems, we present a new way to derive an attack tree system in which the initial attack tree is reconstructed into a new attack tree using Interpretive Structural Modeling (abbr. ISM). The proposed method can easily correct the relation between parent-child nodes and identify horizontal relationships. Finally, the proposed method derives a clear attack tree for more precise system's threat analysis and better defensive measures. Index Terms-security, attack tree, model, ISM.
Numerous high-tech products and technologies are invented to improve life, including physical software and cyber-physical systems in the information technology field. Reliance on these types of systems has been increasing. Today these systems store vast amounts of information. However, security of these systems has become important and is being actively researched.
The concept of an attack tree provides a clear way to describe possible attacks and safety threats for a system. We strive to apply the attack tree concept to make a system secure. An attack tree has a structure similar to a tree as it includes different levels of nodes – root nodes and leaf nodes. Root nodes represent attack targets, while leaf nodes denote attack methods.
A root indicates a target goal, and the leaves represent basic attacks with no further refinements in an attack tree. A successful attack would satisfy the roots. That is, if the child nodes are true, then the direct parent nodes are true.
According to the attack tree model, each node can have
different metrics, and finding the minimum value of the sum of the
metrics passing through the path from the tree's bottom to the top
can indicate a system's attack motion [
Generally, an attack tree connects a child node to its parent node. Thus, a child and parent have a vertical relationship. However, some relations exist between horizontal nodes. If the horizontal relationships between nodes are considered, the relation definition of the nodes on the attack tree becomes more complicated. Additionally, the efficiency becomes lower or defenses overlap. If we can redefine the horizontal relationships on an attack tree and re-build the tree, a clearer attack tree with a strict structure could be derived, especially for complicate cases.
Herein we present a new method to rebuild the initial attack
tree by the Interpretive Structural Modeling procedure (abbr.
ISM) [
Section II explains the background of an attack tree and the motivating example. Section III presents the related work on attack trees. Section IV how our method works and implements our method using a running example, and Section V presents discusses our method. Finally, Section VI concludes the paper.
II. BACKGROUND
Before explaining our method, we would like to introduce
the motivating example taken from [
Based on these conditions, we can draw three successful scenarios (Fig. 1b). The first is enter room2 through the window (orange dotted line). The second is to use both key1 and key2; the attacker enters room1 using key1 to open door1. Once in room1, the attacker disables the camera and then uses key2 to enter room2 (green dashed line). The third scenario is the attacker hacks directly into the network (yellow solid line). An attack tree can be used to clearly model these three scenarios.
(a)Floor plan
(b)Attack scenarios
Fig.1. Motivating example [
There are numerous ways to initiate an attack, but most people do not realize this. Even if people are aware of such vulnerabilities, they know little about system security. Due to the increasing complexity of attack motions, it is becoming more difficult to prevent attacks. Defending against an attack based on an engineer’s own personal ability is problematic. “Security” must answer two questions: “Who will attack?” and “How long is security necessary?” Thus, a method to model threats against computer systems must be developed. If the attackers are known, then systems could be protected by presuming their ability and their attack target. By knowing the probability of attacking motions, a defense can be mounted by designing these countermeasures. These situations are why the "attack tree" method is needed.
To analyze the security of an issue, the attack tree model must be selected. In our motivating example, we used three types of nodes: • OR: OR node means an alternative attack. One of the child nodes can be satisfied to attack a parent node. • AND: AND node means a conjunctive attack. All of the child nodes must be satisfied to attack the parent mode. • SAND: SAND node means a sequential attack. All of the child nodes must be satisfied in a specific order to attack the parent node.
Fig. 2 expresses the three scenarios in Fig. 1b as an attack tree. To access the computer data, methods can be separated into physical attacks and network attacks. In the physical attack case, it can be further separated as go through the door or the window. To use the door, the camera should be disabled before entering room2 (node type AND); to enter room2, door1 and door2 should be opened in sequence (node type SAND). The invade computer subtree can be separated to invade from wireless LAN or infection malware. These two nodes can be true if at least one of the leaf nodes is true (node type OR).
Fig.2. Attack tree expressed by scenario
To discuss the relation of nodes, we define the Necessary and Sufficient Relationship between Parent-Child Nodes and the Horizontal Relationship
Child Nodes: The logic relationship between parent-child nodes is very important in an attack tree. Below are two relation definitions between parent-child nodes from the attack tree to clarify the child nodes are conditions that must be satisfied to make the direct parent node true.
a) Child nodes' commands must be a sufficient condition for the commands of parent nodes. For an "OR" node, the statement of the parent node is true when at least one of the child nodes is reached. For an "AND" node, the statement of the parent node is true when all child nodes are reached.
b) A set of child nodes must be the necessary condition for the commands of parent nodes. Based on the premise that the attack tree has integrity when the node type is "OR", the union of child nodes is true if the parent node is true, but when the node type is "AND", the intersection of child nodes is true if the parent node is true.
2) Horizontal relationship: The structure of an attack tree is like a tree. The connections between nodes are usually defined as parent-child relationships (vertical relationships). However, some relations exist between nodes, which are at the same level. Such relations, which are usually ignored in the relationship definition, are horizontal relationships between nodes. To redefine the relations in a tree structure, surplus nodes make it more complicated, reducing the efficiency when setting the defense strategy. Horizontal relations are separated into two types as shown below:
other node on a different branch is true.
b) Similar nodes: The same attack occurs from two leaf nodes.
There are multiple ways to analyze attack trees. B. Schneier
[
When these conditions are combined, Gn, which stands for target node, can be defined. An stands for leaf node (an attack). λ(n) represents the variable cost at point n. λ denotes a variable for Risk, Skill, or other factors. For example, Risk(Aa) can be considered as the risk cost of attack node a.
For a target node Gn, there are Gx, Gy sub-nodes, and the type of node is OR. The relation function is described as: = ,
In Fig. 3a, which shows a very simple attack tree with a target of "reach room2", there are two attacks: "go through the door" or "go through the window". We can use the symbols in Fig. 3b to derive the relation function as:
() = {(), ()} The minimum risk path is chosen between nodes Ab and Ac. When Risk(Ab) is bigger than Risk(Ac), the minimum risk path is Path(Ga, Ac). However, if the parent-child relations are the opposite (Fig. 3c), then the relation function is:
() = {(), ()} Thus, the minimum risk path can be chosen between nodes Aa and Ac. When Risk(Aa) is greater than Risk(Ac), then the minimum risk path is Path(Gb, Aa). We found that this path is not the path of "go through the window", which is actually the minimum risk path of the system. (a) correct attack tree (b) Indicate the nodes (c)parent-child relations opposite
Fig.3. Example of analyze an incorrect attack tree
In Fig. 4a, there are three nodes from the top to bottom: "reach room2"，"go through the door" and "unlock door2", and all of them satisfied the definition of Necessary and Sufficient
to Fig. 4b by symbolization. When we analyze Fig. 4b, we just need to analyze Risk(Ac) for getting Risk(Ga). We put figure 4b's node c on the position of node b's siblings purposely, and adding node d: "get key2", which has the same relations as node c. While analyzing the attack tree on Fig. 4c, we need to analyze these three nodes of risk for each three paths. Although it would get the same result probably from Risk(Ac) and Risk(Ad), it could cost much more time to analyze the variable value of surplus nodes. (a) correct attack tree (b) Indicate the nodes (c)with horizontal relationship Fig.4. Example of analyze attack tree
with missing horizontal relationship
By the method from this thesis, we define Necessary and Sufficient Relationship between Parent-Child Nodes and some ignorable relations between horizontal nodes. When analyzers find out these relations, he would re-judge the relationship between nodes and restructure the attack tree.
Consider the physical attack portion of Fig. 2. To satisfy the node "go through the door", two conditions are necessary: "deactivate camera" and "reach room2". However, the condition "reach the room2 " can be achieved when either "go through the door" or "go through the window" is true. Based on the result, it can be said that the condition in this case is a necessary condition but not a sufficient condition. In other words, there are some obvious logical gaps in the attack tree. Thus, the attack tree should be revised.
Consider the invade the computer part portion in Fig. 2. Here "WEP crack" is a child-node belonging to the node "invade from wireless LAN". However, it can be viewed as child-node belonging to its siblings-node -- "password crack" because the "password crack" would be true if node "WEP crack" is completed. Ignoring the relation of additional contributions, makes the attack tree more complicated by increasing of amount of attack paths, reducing the efficiency of setting the defense strategy. In the "Infection malware" subtree, it can be observed that node "disguised as normal software" and node "drive by download" are the same attack on the system. These kinds of designs are messy and waste defense resources by over-comprehending the values of the attack motions. To address these problems, nodes need to be redefined or combined.
In a real situation, the attack tree would be a huge system with tons of nodes. To prevent the aforementioned problems, the tree’s path needs to have a clear structure to elucidate the relations between nodes. In the next section, we offer a new way to re-build an attack tree with incorrect relations between parentchild nodes and analyze the horizontal relationships of its nodes.
Earlier works introduced the concept of an attack tree. A.
Salter et al. [
Attack trees can be also used in copyright protection of
ecommerce protocols. Higuero M. V. et al. [
We present a method that not only solves problems to repair the incorrect relations between parent-child nodes but also redefines horizontal relationships between nodes on different branches. Our method provides a clear, complete structure of the attack tree through Interpretive Structural Modeling (ISM) procedure.
ISM is a method to confirm complex relations between items
by modeling. For complex issues or systems, the number of
items is huge and the relations between items are complicated.
To express the relations more precisely, we use ISM to present
the relations between items directly and indirectly. By
considering the analyzing issue and system, items are initially defined as
apexes Vi and Vj ( i=1, 2, 3 …；j=1, 2, 3 … ) for ISM. The edge
with an arrow (Vi, Vj) expresses the relations between two items.
A matrix, which is used to express the connection status for
every pair item, is called a Relation Matrix (A) and it provides a
structural self-interaction matrix (SSIM). Afterward, a
reachability matrix (RX) from SSIM is obtained by calculations.
Finally, we can derive a new model from RX by level partitions.
ISM is a very efficient method. Because it is based on different
situations, the number of relations between items can be reduced
by 50–80% [
ISM includes the following steps: 1) Graph the Relation Matrix (A) of the analyzed system 2) Generate the Reachability Matrix (RX) through a transformation of the Relation Matrix 3) Level Partitions 4) Digraph
or expert familiar with the analysis issue must identify the contextual relations among items. Based on these relations, Relation Matrix A = {aij | i, j=1,2,···, n}is created to express all direct binary relationships. The value of n is the number of nodes from the system. All elements are listed in the rows and columns of a table. If two elements have a direct relation, enter 1 on the table grid. Otherwise, enter 0. If the column direction is defined as the predecessor node, then enter 1 on a12 when V1 points to V2 similar to Fig. 5a.
(a)Relation Matrix (A) (b) Power of SSIM is k
Fig.5. Example of A and RX
ability Matrix (RX) is used to express whether the relation between two specific items is direct or indirect. RX can be calculated as:
A + I ≠ + ; ≠ ⋯ ≠ + = = + =>? . 1 = + = . 2 "I" is a Unit Matrix. (A+I) to the power of k is RX when (A+I) to the power of k equals (A+I) to the power of (k+1). A power of SSIM = 1 means that a direct relationship exists between discussed items (the connecting route is 1). A power of SSIM = 2 means that the discussed items are connected with a maximum of 2 routes (passes 1 point). In other words, like in Fig. 5b, when the degree of SSIM is k, the items are connected with at most k routes, and pass through at most (k-1) items.
Step 3: Level Partitions: We can find the reachability sets and antecedent sets from every point (element) for the final reachability matrix. A reachability set is defined as a set composed of itself and points that it can reach. An antecedent set is defined as a set composed of itself and points that can reach it. We can obtain the intersection between these two sets from all elements, and get the different elements' levels. If the reachability set and intersection set of the element are the same, then it would be a top level constructed by ISM. Top level elements can be deleted from the set to find the new top level from new set. This tracing step of the top levels is repeated until all of them are found. The level departure can help build the graph of ISM model.
Step 4: Digraph: The final step is to draw a new model from the new obtained elements. First, we draw elements by level. For example, the top level elements are the root nodes on the attack tree. Thus, they are put on the level first. Then the elements of the second level are located on tree's second level. This is repeated for the third, fourth level, ..., until all elements are added to the attack tree. Next the nodes are connected to the Predecessor node to get the final model while removing the indirect links.
It is necessary to find a relation between elements in the ISM methodology. To reach the goal, the nature of the contextual relationships among the factors must be identified carefully. To analyze the factors, a contextual relationship of "leads to" or "influences" must be chosen. This means that one factor influences another factor. After confirming the relations between parentchild nodes, we can use the ISM method to express an attack tree.
The proposed method includes the following steps (Fig. 6): 1) Indicate the nodes. 2) Re-Judge the relation between nodes and graph the Relation Matrix (A) 3) Generate the Reachability Matrix (RX) through a transformation of the Relation Matrix(A) 4) Level Partitions 5) Digraph
Step 1: Indicate the nodes: In this step, all related nodes are expressed and displayed by symbols. Here Fig. 2 is used as an example. To reduce the computational complexity, the attack tree is separated into two subtrees: Physical Access in Fig. 7a and Invade the Computer in Fig. 8a.
• Subtree Physical Access
Re-Judge the relation between nodes: Analyzer should check the relation between nodes: previously we mentioned that two parent-child relationships, "go through the door" and "reach room2", conflict with the definition Necessary and Sufficient Relationship between Parent-Child Nodes in the physical access attack part. However, if these are separated and considered separately, if "reach room2" is true, then "physical access" must be true. Similarly, if "go through the door" or "go through the window" is true, then "reach room2" is true. To let all of the nodes in this subtree satisfy the Necessary and Sufficient Relationship between Parent-Child Nodes, we should modify the nodes' relations on an attack tree as follows (see Fig. 7b): Delete the connected line between N2 and N5 and add a line from N1 to N5 because the node "physical access" is true if the node "reach room2" is true. Moreover, add the lines N5 to N3 and N5 to N2 because "go through the window" or "go through the door" is a condition, which must be satisfied to make the node "reach room2" true.
(a)Indicate the nodes (b)Revise the relationship (c)Arrange the structure between parent-child nodes
Fig.7. Subtree: Physical Access
After revising the relationship between parent-child nodes, arrange the structure of the attack tree to be less confusing. "Reach room2" and "enter room2" are parent-child relations with the same word meaning. Thus, node8 (enter room2) can be removed. We also change the node type AND to a direct vertical structure. For SAND, the later order points are the sufficient conditions for the former order points. Like the attack tree in Fig. 7c, node7 (unlock door2) is necessary for node2 (go through the door) to be true. Thereby, node4 (deactivate the camera) must be true to let node7 (unlock door2) be true, and demanding node6 (unlock door1) must be true to let node4 (deactivate the camera) be true.
direct relationships after re-judge the relation between nodes of sub-tree physical access.
to Eq. 1 and Eq. 2, the Reachability Matrix can be calculated similar to that in Fig. 8b.
(a)Relation Matrix(A) (b)Reachability Matrix(RX)
Fig.8. A and RX of Physical Access
Matrix for each node, the reachability and antecedent sets are derived. Fig. 9 shows the result using the rule of Level Partitions. The table helps build the ISM model.
Fig.9. Level Partitions of Physical Access
Step 5: Digraph: In Fig. 13a, a new model is drawn from the
• Subtree Invade the Computer
the relations between horizontal nodes: In the attack tree, the horizontal relations, which are ignored in the original attack tree, are separated into Additional contribute and Similar (Fig. 10b). As noted in section II, the attack "WEP crack" can be a condition that makes the node “password crack” attack complete in the subtree "invade the computer". It can also be explained that the “WEP crack” can affect the “password crack” attack. Hence, this relationship is defined as additional contributions. Thus, a new path from "password crack" pointing to "WEP crack" can be added between nodes. Besides, the attack of "deceive to download malware" is a similar motion to the attack of "drive by download". This relation is defined as a similar relationship. Because it is unlikely that they would not affect one another, a path is added between them to express the relation.
(a) Indicate the nodes (b)Define the relationship between
horizontal nodes
Fig.10. Subtree: Invade the Computer
shows the calculation of the Reachability Matrix (RX) from the Relation Matrix.
(a)Relation Matrix(A) (b)Reachability Matrix(RX)
Fig.11. A and RX of Invade the Computer
Step 4: Level Partitions: From the Reachability Matrix (RX), the Level Partitions table is drawn. As shown in Fig. 12, two nodes, node16 (disguised as normal software) and node17 (drive by download), are merged into a new node16 and renamed "drive as a normal software" because they have the same result in the Reachability Set, Antecedent Set, Intersection Set, and
Fig.12. Level Partitions of Invade the Computer
Step 5: Digraph: A new attack tree is drawn from Level Partitions of Invade the Computer (Fig. 13b).
(a) Model of Physical Access (b) Model of Invade the Computer Fig.13. Digraph of the two subtrees
V. DISCUSSION 1) RQ1: We separated this RQ into two aspects. The first is whether the child nodes are sufficient conditions for parent nodes on the attack tree after the ISM revision. When "go through the door" or "go through the window" is true, then the condition "reach room2" must be true. In other words, "go through the door" or "go through the window" refers to "reach room2". It is trivial that the answer for the statement is true. The second is whether the child nodes are necessary conditions for parent nodes in the attack tree after the ISM revision. There are only two ways ("go through the door" or "go through the window") that the statement "reach room2" is true. "Reach room2" must refer to "go through the door" or "go through the window". Combining the two parts provides a conclusion. Based on the complete sets of nodes, the relations between parent nodes and child nodes satisfy necessary and sufficient conditions after revising by ISM method.
However, the complete sets of nodes are affected by other factors such as knowledge limitations of the tree builder or the property of each tree system. Sometimes there is an error due to logical mistakes during the tree restructuring process. To ensure the relations between parent-child nodes are satisfied with necessary and sufficient conditions on the new attack tree, the relations should be rechecked after revising.
2) RQ2: When we analyze an attack tree, we usually use the
probability or cost estimating method to determine the values of
possible attacks. For example, Yan Liu [
3) RQ3: Due to the range of efficiency caused by the difference in the number of nodes and the difference of analysis methods, quantitative analysis is difficult. The more nodes present, the more that nodes can be reduced. Although the ISM matrix becomes more complex and harder to calculate manually due to the increase in nodes, the matrix can be calculated automatically by programming systems. In other words, it is not an extremely laborious task.
Attacks are often used as a model analyzing method in system security analysis due to the complexity of a system. An attack tree may become very large, which leads to two problems: 1) incorrect logic between parent-child nodes and 2) ignored parallel relationships in different branch nodes. The paper presents a definition between parent-child nodes and suggests a method to repair an attack tree with an incorrect relation of parent-child nodes or ignored horizontal relationships.
Our method defines the Necessary and Sufficient Relationship between Parent-Child Nodes: 1) A child node must be the sufficient condition for parent nodes. 2) A set of child nodes must be the necessary condition for commands of parent nodes. Meanwhile, we define two horizontal relationships: additional and similar. While analyzing an attack tree, we hope that analyzers can start by checking the relations between every child node from the subtree for parent-child logical relations and the parallel nodes from different subtrees. Analyzers should re-judge the relations for nodes and restructure the attack tree. Finally, the restructure attack tree should be double checked. Although the revision and verification have some costs, they can verify the accuracy of the attack tree on logical problems, reducing the number of nodes and paths in an attack tree and enhancing the analysis efficiency of the attack tree. Moreover, this method is friendly for beginners as it simplifies the whole system by focusing on the relations between nodes, reducing the burden for users.
Due to the instability in analyzing nodes relations manually, in the future, we would like to find a rapid way to confirm the parent-child nodes' relations. Additionally, we plan to dedicate a program code to the ISM method and make the calculation automatic in order to decrease the restructuring time and further improve the efficiency of the system.