`
`
`
`Manuscript version: Author’s Accepted Manuscript
`The version presented in WRAP is the author’s accepted manuscript and may differ from the
`published version or Version of Record.
`
`Persistent WRAP URL:
`http://wrap.warwick.ac.uk/131160
`
`How to cite:
`Please refer to published version for the most recent bibliographic citation information.
`If a published version is known of, the repository item page linked to above, will contain
`details on accessing it.
`
`Copyright and reuse:
`The Warwick Research Archive Portal (WRAP) makes this work by researchers of the
`University of Warwick available open access under the following conditions.
`
` ©
`
` 2019 Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-
`NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/.
`
`
`
`
`
`Publisher’s statement:
`Please refer to the repository item page, publisher’s statement section, for further
`information.
`
`For more information, please contact the WRAP Team at: wrap@warwick.ac.uk.
`
`
`
`
`
`
`
`warwick.ac.uk/lib-publications
`
`
`
`WIZ - EXHIBIT 1011
`Wiz, Inc. v. Orca Security Ltd.
`
`

`

`Elsevier Computer Science 00 (2019) 1–46
`
`Computer
`Science
`Reviews
`
`A Review of Attack Graph and Attack Tree Visual Syntax in Cyber Security
`
`Harjinder Singh Lalliea, Kurt Debattistab, Jay Balc
`aCyber Security Centre, WMG, University of Warwick, Coventry, UK, HL@warwick.ac.uk
`bWMG, University of Warwick, Coventry, UK, K.Debattista@warwick.ac.uk
`cWMG, University of Warwick, Coventry, UK, jay.bal@warwick.ac.uk
`
`Abstract
`Perceiving and understanding cyber-attacks can be a difficult task, and more effective techniques are needed to aid cyber-attack perception. Attack
`modelling techniques (AMTs) - such as attack graphs, attack trees and fault trees, are a popular method of mathematically and visually representing
`the sequence of events that lead to a successful cyber-attack. These methods are useful visual aids that can aid cyber-attack perception.
`This survey paper describes the fundamental theory of cyber-attack before describing how important elements of a cyber-attack are represented
`in attack graphs and attack trees. The key focus of the paper is to present empirical research aimed at analysing more than 180 attack graphs and
`attack trees to identify how attack graphs and attack trees present cyber-attacks in terms of their visual syntax.
`There is little empirical or comparative research which evaluates the effectiveness of these methods. Furthermore, despite their popularity,
`there is no standardised attack graph visual syntax configuration, and more than seventy self-nominated attack graph and twenty attack tree
`configurations have been described in the literature - each of which presents attributes such as preconditions and exploits in a different way. The
`survey demonstrates that there is no standard method of representing attack graphs or attack trees and that more research is needed to standardise
`the representation.
`
`Keywords: Attack graph, attack tree, visual syntax, cyber-attack
`
`1. Introduction
`
`Cyber security pervades many aspects of social, political
`and business life and has huge implications for the online and
`personal safety of individuals and families. In 2017, the average
`cost of a data breach was reported globally as $3.86 million
`[163]. Although many data breaches result in the compromise
`of personal data, a number of well publicised attacks against
`vehicular [392], medical [106], and industrial control systems
`[112] have demonstrated that cyber security breaches can have
`serious impacts on personal safety.
`Quite often mitigation strategies focus on protecting sys-
`tems from perpetrators intent on causing deliberate damage to
`a system and/or data, however, many cyber security failures oc-
`cur simply as a result of user behaviour - often because of un-
`intentional errors brought about by a failure to fully understand
`security mechanisms [75].
`User error and behaviour is an important factor in a cyber-
`attack [23, 92]. Perhaps one of the most important mechanisms
`in improving user behaviour is to make it easier to perceive
`cyber security and make it more ‘usable’. Research into cy-
`ber security usability aims to design systems which help to
`
`1
`
`understand how users perceive and understand cyber security
`[343, 309, 293] by taking “into account the perceptions, char-
`acteristics, needs, abilities and behaviors of users” [77].
`Cyber-attack perception is an important research problem
`[295, 211, 381] which demands better techniques and methods
`to aid the perception and assessment of cyber-attacks. Quite
`often, observers find the analysis and understanding of com-
`plex patterns difficult to visualise [187, 368]. Well-designed
`diagrams and graphical systems can aid this process [263, 180].
`This paper describes how attack graphs and attack trees rep-
`resent cyber-attacks in terms of their visual syntax. The paper
`demonstrates that although there are numerous benefits to pre-
`senting cyber-attacks as attack graphs or attack trees, there are
`inconsistencies regarding the way cyber-attacks are represented
`in attack graphs and attack trees and in doing so, outlines the
`need to standardise their visual syntax. This is the first paper to
`present such a detailed critical analysis of the visual syntax of
`attack modelling techniques.
`Collectively these shortcomings outline the need for further
`research and they also define some of the parameters that com-
`parative evaluations should consider. The research presented in
`
`

`

`/ Elsevier Computer Science 00 (2019) 1–46
`
`2
`
`Figure 1. Two attack models. A fault tree (left) and an attack graph (right)
`
`Lallie et al. [216, 217] aims to address these shortcomings and
`propose an attack graph visual syntax which is cognitively ef-
`fective and also preferred by practitioners - thereby increasing
`the likelihood of adoption.
`The rest of this paper is structured as follows. Section 2 be-
`gins by describing the concept of AMTs and the use of visual
`syntax to represent cyber-attacks. Section 3 proceeds to de-
`scribe the underlying theory of cyber-attacks. This section de-
`scribes the relationship between the primary cyber-attack con-
`structs which are: precondition, exploit and precondition logic,
`and also explains the secondary constructs which are variants
`of primary constructs. Collectively, the primary and secondary
`constructs correspond to the concepts that AMTs should repre-
`sent.
`Section 4 outlines some of the graph theory relating to at-
`tack graphs and attack trees and then Section 5 introduces im-
`portant visual syntax theoretical concepts. Section 6 provides a
`detailed analysis of the presentation of attack graphs and attack
`trees.
`
`2. Attack Modelling Techniques (AMTs)
`
`Attack modelling techniques (AMT) are used to model and
`visualise the sequence and/or combination of events that enable
`a successful cyber-attack on a computer or network. AMTs
`can be broadly divided into three categories: methods that are
`
`Figure 2. Attack modelling techniques
`
`2
`
`based on the use case framework, methods that present a cyber-
`attack from a temporal perspective, and graph based methods.
`These methods are highlighted in Figure 2. Of the methods
`outlined in Figure 2, attack graphs and attack trees are the most
`popular method of representing cyber-attacks - at least as far as
`the academic literature is concerned. These two methods form
`the basis of the present research.
`AMTs enable observers to evaluate the salient information
`in a diagram [190, 156, 99, 368] and help remove the intel-
`lectual burden from security experts - who have to evaluate
`cyber-attack scenarios and evaluate potential mitigations [329].
`Consequently, security problems can be presented in a man-
`ner that enables a decision maker - whether an expert or non-
`expert, to more quickly grasp the problem [156], better per-
`ceive risk landscapes [154], and easily perceive complex con-
`cepts [350].
`In such circumstances, AMTs provide effective
`tools and workspaces [115], they make this process clearer and
`simpler and thereby facilitate easier discussion and debate [99],
`and can aid the perception of cyber-attacks with little reference
`to logical models [118].
`An example of two AMTs - a fault tree and attack graph,
`is provided in Figure 1. The example in Figure 1 demon-
`strates how a perpetrator is able to conduct a series of exploits
`(sshd bof) on a sequence of host computing devices (denoted
`in brackets), and by doing so, acquire user privileges (user)
`on each one. The example also shows one of the preconditions
`(sshd) that are necessary for the attack to be successful. This
`example demonstrates how a sequence of exploits can be visu-
`alised to aid cyber-attack perception.
`The cyber security domain suffers from two specific prob-
`lems relevant to the present paper: inconsistency in the onto-
`logical terms, vocabulary, and definitions used to describe the
`domain [146], and a problem of unclear and meaningless se-
`mantics [157].
`Multiple terms are used to mean the same thing. For exam-
`ple, exploits are also referred to as actions or attacks, the perpe-
`trators are also referred to as attackers, malefactors, actors and
`adversaries, the preconditions to an exploit are also referred
`
`user(2)
`
`user(1)
`
`sshd(1,2)
`
`user(3)
`
`sshd(3,2)
`
`sshd_bof(1,2)
`
`sshd_bof(3,2)
`
`sshd_bof(1,2)
`
`sshd_bof(3,2)
`
`sshd(1,2)
`
`user(1)
`
`sshd(3,2)
`
`user(3)
`
`user(2)
`
`Attack modelling techniques
`
`Use case methods
`
`Temporal methods
`
`Graph based methods
`
`Misuse cases
`
`Riskit
`
`Cyber kill chain
`
`Diamond model
`
`Misuse case maps
`
`Security use cases
`
`Misuse sequence
`diagrams
`
`CORAS
`
`Attack graph
`
`Attack tree
`
`Fault tree
`
`Event tree
`
`Decision tree
`
`Petri net
`
`

`

`/ Elsevier Computer Science 00 (2019) 1–46
`
`3
`
`Table 1. Terms used to describe the fundamental cyber-attack constructs
`Term
`Term used & supporting references
`
`Precondition
`
`Postcondition
`
`Perpetrator
`
`Prerequisite: [278, 280, 281, 169, 243, 415, 233]; Precondition:
`[371, 78, 16, 175, 45, 71, 160, 174, 125, 164]; Prerequisite and
`precondition: [326, 363, 228, 125, 406]; Predicate; [176, 280, 302,
`377, 6, 136, 146]; Requires: [279, 79, 15]
`Postcondition: [78, 175, 71, 174, 209]; Effect: [229]; Provides:
`[279, 79, 15]; Consequence: [278, 280, 403, 228, 270]; Impact:
`[118, 7, 11, 15, 4, 5];
`Perpetrator: [86, 323, 389]; Attacker: [169, 243, 181, 294, 30, 137];
`Adversary: [45, 319, 234, 222]; Malefactor: [209, 139, 358]; Actor:
`[80, 146, 204, 364]; Hacker: [326, 130, 86, 56, 89, 374, 39, 227, 95,
`110, 155, 52, 167, 185, 249, 219, 222, 73, 143, 164, 407, 22, 50,
`207, 246, 42, 148, 204, 109, 189, 221]; Crook: [363] [364] [242];
`Mis-actor: [363]2; Assailant: [32, 117, 338, 145, 109]; Misuser:
`[363, 47, 250, 185, 120, 184]; Bad guy: [88, 194, 252, 398, 145,
`191]
`
`1 Wu et al. use the terms attacker, adversary, malefactor and perpetrator interchange-
`ably in the same paper [418].
`2 Sindre and Opdahl use the terms crook and mis-actor in the same paper to refer to
`a perpetrator. The term mis-actor is used specifically as an ‘inverted actor’ in other
`words the opposite to actor which is the term generically used in use cases to refer to
`the user of a service or function [363].
`
`to as requires, predicates or prerequisites, and the postcondi-
`tions of the exploit are also referred to as provides or effects.
`Further examples are provided in Table 1. This problem of in-
`consistency extends to multiple areas in cyber security, and is
`particularly acute for attack graphs and attack trees.
`This paper uses the terms exploits, preconditions and perpe-
`trators. While the use of precondition and exploit may appear
`straightforward, the selection of the term perpetrator requires
`more justification. Terms such as attacker, adversary, crook,
`bad guy, assailant and hacker suggest that the source of a cyber-
`attack is acting deliberately, when in fact the exploit might be
`effected inadvertently. Terms such as mis-user and mis-actor
`are very uncommon and unlikely to resonate easily with read-
`ers. The term perpetrator doesn’t suggest either a deliberated
`or inadvertent motive. The use of this term does not remove
`anything in terms of the descriptive power of the term.
`Attack models are constructed using a combination of two-
`dimensional shapes - such as squares, rectangles, ellipses; one-
`dimensional shapes - such as lines; and textual syntax to repre-
`sent cyber-attack constructs. This is referred to as a visual syn-
`tax [266], visual rhetoric [351] or visual grammar [212]. The
`visual syntax of modelling systems such as fault trees [166] and
`Petri nets [311] - both also used occasionally to model cyber-
`attacks, is standardised - resulting in a common understanding
`of the framework. This is not the case for attack graphs and
`attack trees.
`Attack graphs and attack trees suffer from a distinct lack of
`standards, prescriptive methodologies and common approaches
`in terms of their visual syntax [87, 253]. Authors use self-
`nominated and untested visual syntax to model the attack - re-
`ferred to by Alexander [9] as the unselfconscious design ap-
`proach [9].
`There are more than seventy five attack graph visual syntax
`configurations and more than twenty attack tree configurations -
`as demonstrated in Table 22 and Table 24 which describe the vi-
`sual syntax of more than 180 attack graph and attack tree visual
`syntaxes. The visual syntax in these examples differ in terms
`
`of the shapes used to represent constructs such as preconditions
`and exploits. The availability of numerous opposing propos-
`als can give rise to confusion for researchers and practitioners
`in deciding which to use and is evidence of an “immature re-
`search field” resulting in a “fragmentation of research efforts”
`[265].
`
`3. Cyber-Attacks
`
`A number of recent high-profile attacks have exemplified
`the need to better understand cyber-attacks. These include the
`Stuxnet virus [249, 112, 55] the Jeep Cherokee hack [392], the
`heartbleed attack [42, 62, 100], the Sony hack [44, 109, 340,
`397] and the Ukrainian power grid attack [221, 320].
`The fundamental components of all these cyber-attacks
`were the same and comprised of elements such as exploits, vul-
`nerabilities, and postconditions.
`The terms described in this paper are summarised in Table
`2 and the rest of this section describes these terms in further
`detail.
`
`3.1. Vulnerability, Precondition and Postcondition
`3.1.1. Vulnerability
`A vulnerability is an exploitable weakness in the design,
`implementation or management of a system [362]. A vulnera-
`bility comprises of a combination of one or more system states
`referred to as preconditions.
`
`3.1.2. Precondition
`Preconditions are a set of system properties that must ex-
`ist for an exploit to be successful. An initial precondition is a
`system property which exists inherently in a system and which
`did not arise as a consequence of exploitation [16]. Addressing
`these could make all further steps in an attack null and void.
`There are at least three types of precondition:
`
`1. Statuses/services. The target holds or advertises par-
`ticular versions of operating systems, systems soft-
`ware/applications, services [313, 12], or is in a particular
`hardware/software state.
`
`Term
`
`Vulnerability
`
`Precondition
`Initial
`precondition
`Perpetrator
`capability
`Postcondition
`Goal
`Exploit
`
`Non-intrusive
`event
`
`Table 2. Cyber-attack terms
`Explanation
`
`An exploitable unplanned system weakness which exists because of
`the existence of one or more preconditions
`A system state that is necessary for an exploit to be successful
`The first precondition in a cyber-attack
`
`The tools, knowledge and/or access/privilege levels that a perpetra-
`tor needs to be able to run an exploit
`The conditions/states created by a successful exploit
`The ultimate target of a cyber-attack
`A set of steps - executed as code or manual steps, which take advan-
`tage of one or more vulnerabilities in a target system and provide
`specific capabilities to the perpetrator
`An event which aids and supports a cyber-attack but does not alter
`the state of the target system
`
`3
`
`

`

`/ Elsevier Computer Science 00 (2019) 1–46
`
`4
`
`2. Reachability. The target is reachable.
`3. Perpetrator capability. The perpetrator has particular ca-
`pabilities such as the ability to run a process on a tar-
`get, access to tools, or privilege levels [179] and/or is in
`possession of the tools to conduct an attack and has the
`necessary skill level [313].
`
`Of the precondition types discussed above, statuses/services
`are commonly represented in AMTs such as attack graphs and
`attack trees, however, reachability and perpetrator capability
`are less commonly represented [313, 146, 27].
`Perpetrator capability is an important element in the analy-
`sis of an attack and it can be important for a security analyst to
`understand exploits that require greater perpetrator capability
`versus those that require less [380]. As an example of perpe-
`trator capability, consider the example of the rcp (remote call
`procedure) exploit given by [16]. The rcp exploit requires the
`following capabilities:
`• The rcp service must be available to the perpetrator.
`• The target host must trust the source host.
`• The perpetrator must have local shell access.
`
`3.1.3. Postcondition
`The successful perpetration of an exploit results in one or
`more postconditions. Although the result of an exploit is tech-
`nically referred to as a postcondition, these can also form the
`preconditions of further exploits, therefore, most researchers re-
`fer to postconditions simply as precondition with the term goal
`being used to identify the final postcondition.
`
`3.2. Precondition Logic
`For an exploit to be successful, one or more preconditions
`must be satisfied. The combination of preconditions can be rep-
`resented using precondition logic. So, given two preconditions:
`pr1 and pr2, if both the preconditions have to be satisfied, this
`can be represented as a conjunction of the form: pr1 ∧ pr2 -
`where the symbol ∧ represents conjunction. Conversely, if any
`one of the two must be satisfied, then this can be represented
`as a disjunction of the form: pr1 ∨ pr2 - where the symbol ∨
`represents disjunction.
`The shape or symbol used to represent precondition logic
`in an AMT is referred to as the precondition operator. In the
`examples given above, the precondition operators are ∧ and ∨.
`Although the representation of precondition logic is criti-
`cal in helping to identify cyber-attack mitigations and counter-
`measures, very few attack graphs represent precondition logic
`[383, 366, 11, 227, 227, 54, 122].
`To illustrate the benefit of presenting precondition logic,
`consider the attack graph representation in Figure 3 [26].
`In
`this example, sshd(3,1) and user(3) are two preconditions.
`In the formal expressions presented by Barik and Mazumdar,
`sshd(3,1) means that the sshd (secure shell daemon/service)
`is running on host 1 and is accessible by host 3, and user(3)
`means that the perpetrator has user access privileges on host 3
`which is the host from which the exploit will be launched.
`
`This attack graph does not represent the precondition logic
`necessary for each exploit, consequently, the attack graph could
`be interpreted in a number of ways. For example, for a success-
`ful sshd buffer overflow attack (sshd bof(3,1)), one of
`the following two preconditions might apply:
`1. sshd(3,1) ∧ user(3)
`2. sshd(3,1) ∨ user(3)
`As it happens, both preconditions (sshd(3,1) ∧ user(3))
`must be satisfied for the exploit to be successful.
`The representation of precondition logic in attack graphs
`is highlighted in Table 22, and the data shows that there are
`numerous attack graphs which do not represent precondition
`logic.
`
`3.3. Exploits
`An exploit is a set of steps - executed as code or manual
`steps, which take advantage of one or more vulnerabilities in a
`target system and provide specific capabilities to the perpetrator
`[146].
`Exploits can be defined as a formal expression in the form:
`
`exploit(vulnerability, postcondition, source,
`target)
`
`where:
`• vulnerability is the vulnerability being exploited. As
`outlined earlier, the vulnerability can be broken down
`into a number of preconditions, all or a combination of
`which must exist for the vulnerability to be exploited.
`• postcondition is the outcome of the exploit.
`• source is the source host i.e., the host that commits the
`exploit.
`• target is the target of the exploit.
`
`Examples of the formal expression of exploits include:
`
`Figure 3. An example attack graph (adapted from [27])
`
`4
`
`

`

`/ Elsevier Computer Science 00 (2019) 1–46
`• ftp rhosts(ftp, trustedhost,i,j): where i ex-
`ploits an ftp vulnerability in j, and uploads a list of
`trusted hosts to host j.
`• sshd bof(sshd, root,i,j): where i exploits a buffer
`overflow vulnerability in the ssh (secure shell) service of
`j. This provides i with root access to j.
`• local bof(bofv, root,i,j): where i exploits a
`buffer overflow vulnerability (bofv) in j. This provides
`i with root access to j.
`
`It is noteworthy that the formal expression presented above
`is proposed by the authors, and although numerous proposals
`have been put forward in the literature [91, 361, 169, 220], there
`are no standards or agreements in terms of the formal expres-
`sions used to define exploits and vulnerabilities.
`
`3.3.1. Non-intrusive Events
`Non-intrusive events - also referred to as secondary exploits
`[209] and suspicious events [80], are system discovery oper-
`ations used by perpetrators to discover target system proper-
`ties and vulnerabilities [80, 294]. Unlike exploits - which alter
`system properties, non-intrusive events do not alter the system
`properties - unless there is a programmed/manual reaction to
`the event such as system port blocking, or the creation of new
`intrusion detection system rules.
`Examples of non-intrusive events include rpcinfo - which
`reveals port and service data on the target machine, and probes
`and scans such as nmap, netcat, amap, XProbe, P0f and
`X-Scan - which return a system response but do not alter the
`system state.
`Intrusion detection systems (IDSs) detect and alert both in-
`trusive (exploits) and non-intrusive events. Table 3 shows that
`some events - such as the RPC sadmind UDP PING and the
`RPC portmap sadmind request UDP, are both intrusive and
`non-intrusive.
`In other words, RPC sadmind UDP PING re-
`veals some information about the host - this is non-intrusive,
`and RPC portmap sadmind request UDP provides system
`access to the host - which is intrusive. Similarly, an IP address
`spoof results in a non-intrusive outcome.
`
`RPC sadmind UDP
`PING
`
`RPC portmap sadmind
`request UDP
`
`Disclosure of host data
`
`Table 3. IDS signatures, preconditions & postconditions [15]
`Signature (Exploit)
`Precondition
`Postcondition
`running
`Disclosure of host data
`Disclosure of
`service; system access
`(non-intrusive)
`Disclosure of port num-
`ber; disclosure of run-
`ning service;
`system
`access;
`remote access
`(non-intrusive)
`remote
`System access;
`access;
`admin access
`(intrusive)
`
`RPC sadmind UDP
`NETMGT PROC SERVICE
`CLIENT DOMAIN
`overflow attempt
`
`RPC sadmind
`query with root
`credentials attempt
`UDP
`
`Disclosure of host; dis-
`closure of port num-
`ber; disclosure of run-
`ning service
`Disclosure of host; dis-
`closure of port num-
`ber; disclosure of run-
`ning service; system ac-
`cess; remote access
`
`Remote access; admin
`access (intrusive)
`
`5
`
`5
`
`This paper refers to intrusive and non-intrusive events sim-
`ply as exploits.
`Exploits, preconditions and precondition logic are referred
`to in this research as primary constructs because they are
`the fundamental cyber-attack constructs. Initial preconditions,
`goals, postconditions and perpetrator capability are referred to
`as secondary constructs because they are variants of primary
`constructs.
`
`3.4. Cyber-attack
`Having outlined the basic cyber-attack constructs, the dis-
`cussion can now proceed to defining the term itself. A cyber-
`attack comprises of a set of one or more exploits which are
`applied as sequences or in parallel against a target system or
`systems and which expose vulnerabilities in, and alter the state
`of the targeted system(s) [15].
`Once the vulnerability is exploited, a number of postcondi-
`tions are created - each of which could be a precondition for
`further exploits [146]. The ultimate purpose/aim of an attack is
`referred to as a goal in an attack tree [346] and attack graph,
`and an undesirable condition in a fault tree [25].
`It is useful to note that observers are interested in different
`views of a cyber-attack. This is referred to by Moody [266] as
`the principle of cognitive fit (discussed in Section 5). Analysts
`are interested in a low level view technical of a cyber-attack and
`particularly in the preconditions and exploits that contributed to
`the attack. Occasionally, they have to communicate the cyber-
`attack to non-experts. Non-experts such as stakeholders, ex-
`ecutives and decision makers are interested in a high-level -
`often non-technical view of the cyber-attack which hides the
`constituent elements of the attack. However, occasionally it is
`useful for them to see the cyber-attack from the analyst’s view-
`point [352].
`
`3.5. Attack Paths
`Quite often, there are alternative sequences of exploits - any
`one of which can result in a successful attack. These are re-
`ferred to as attack paths and are represented in all AMTs. An
`example of this is provided in the attack graph highlighted in
`Figure 6 which comprises of two attack paths which can be de-
`scribed as:
`1. sshd(3,1) ∧ user(3) → sshd bof(3,1);
`user(1) ∧ sshd(1,2) → sshd bof(1,2) →
`user(2) (highlighted in a red/dotted line).
`2. user(3) ∧ sshd(3,2) → sshd bof(3,2) →
`user(2) (highlighted in a green/dashed line).
`
`Techniques such as attack path analysis aid the investiga-
`tion of exploit paths in an attack graph by outlining known and
`predicted attack event sequences. Such an analysis helps to
`identify the resources in the path that could be affected, as well
`as the vulnerabilities that lie along those paths. Examples of the
`use of attack path analysis combined with weighted edges in
`aiding the attack prediction include the Bayesian based attack
`graph proposed by Frigault and Wang [125]. The attack graph
`in this example enables an analyst to calculate the probability
`
`

`

`/ Elsevier Computer Science 00 (2019) 1–46
`
`6
`
`Prediction strategy
`
`Event predic-
`tion
`
`Miscellaneous
`
`Determining
`optimal
`device config-
`uration
`
`Measuring event
`likelihood
`
`Analysing multi-Step
`attacks
`Attack path
`analysis
`Strengthening security
`weaknesses
`Prioritising vulnera-
`bility removal
`IDS alert
`correlation
`Identifying critical de-
`vices
`Determining optimal
`device placement
`Optimal device con-
`figuration
`Predicting the impact
`of configuration set-
`tings
`
`Table 4. Application of attack graphs in system hardening
`Method & citations
`Markov decision process to calculate the probability of attack success [176], hyper-alert correlation graph and the attack strategy
`graph [280, 279], compromised confidence index [122], adjacency matrix clustering [285], alert correlation matrix [433], association
`rule mining [228], rankFutureScenarios [7], probability based attack prediction [243, 233], absorbing Markov chain for performing
`exploitability analysis and a Markov reward model for aiding likelihood of compromise, [2], forecasting attack graph [133], pwnPr3d
`[178], Other contributions include: [130, 86, 280, 319, 228, 273, 243, 233, 37, 129]
`Alert clustering, alert merging and intent recognition [80], alert correlation framework [278], causal correlation [281], clustered
`adjacency matrices [285], divide and conquer framework [220], divisive hierarchical clustering algorithm [272], exploit dependency
`graph [73], other contributions include: [91, 228, 273, 238, 349, 14, 64, 173, 329]
`Attack chaining [91], calculating the difficulty of perpetrating an attack [227], association rule mining [228], other contributions
`include: [380], [273], [164],
`[86, 176, 359, 27] exploitation graphs [227], topological vulnerability analysis [287]
`
`Skill level analysis [380], Minimum Critical Set of Attacks (MCSA) [176], predictive graph [169, 229], network hardening graph [403],
`[225], a game-theoretic approach [275]
`Hyper-alert correlation graph [280], ADEPTS [122], association rule mining algorithm [228], topological vulnerability analysis (TVA)
`[173], Other contributions include: [384, 175, 278, 319, 361, 169, 7, 15, 133]
`AssetRank algorithm [344], Other contributions include: [144, 2, 316]
`
`Topological vulnerability analysis [287], success measurement model [13]
`
`Graph based network vulnerability analysis [313], clustered adjacency matrices [285], ranked attack graph using PageRank [256],
`dependency attack graphs [344], optimal IDS placement [21, 287], NetSPA [169], attack response graph [241]
`Reverse graph traversal for identifying critical preconditions and vulnerabilities [403], ranked attack graph [256], adjacency matrix
`clustering method and reachability analysis [285], predictive graph [169, 229, 287], divisive hierarchical clustering algorithm [272]
`
`of a successful attack path. Each node in the graph represents a
`potential vulnerability and the preconditions and postconditions
`associated with the vulnerability. A probability is assigned to
`each node to represent the likelihood of that vulnerability being
`exposed. Further examples are provided in Table 4.
`Figure 6 highlights another of the differences in the visual
`representation of attack graphs and attack trees - that of the
`event flow. The figure shows that the flow of events is repre-
`sented top-down. In other words, an observer starts reading at
`the top and follows the sequence of events downwards. How-
`ever in Figure 1 (left), the event flow is represented bottom-up.
`The data described in Table 22 and Table 24, shows that 102
`of the 118 attack graph configurations surveyed (86.4%) pre-
`sented events as top-down, and 59 of the 61 attack trees sur-
`veyed (96.7%) presented these as bottom-up.
`Figure 6 introduces another key difference between the vi-
`sual representation of attack graphs and attack trees. Although
`this attack graph represents a single attack goal (user 2) with
`two paths leading to it, attack graphs are frequently used to rep-
`resent complex attacks which have multiple paths and goals.
`Aguessy notes that attack trees are limited in that they only rep-
`resent a single attack, whereas an attack graph can represent
`multiple attacks [4].
`Aguessy is referring to what are known as full attack graphs
`and partial attack graphs. A full attack graph outlines all po-
`tential vulnerabilities and all possible attack paths in a given
`network [16, 174, 301, 65, 118]. A partial attack graph -
`also referred to as a minimal attack graph [136], outlines
`the pattern of interactions between nodes for a given attack
`[313, 326, 175, 359, 65]. The ability to represent a full attack
`graph is important in scenarios such as the Stuxnet and Jeep
`Cherokee attacks and also in analysing network problems.
`Generally, attack trees represent singular attacks, and the
`
`attack forest - a collection of attack trees [347, 204], was an
`attempt to address this problem.
`
`4. Representing Attack Graphs and Attack Trees
`
`Having outlined the broad principles relating to cyber-
`attacks, it is useful to highlight how cyber-attacks are repre-
`sented in a visual form using AMTs. Numerous AMTs have
`been proposed in the academic literature. These can be broadly
`divided into three categories: use case, temporal and graph
`based methods. A number of these methods are highlighted
`in Figure 2 and in Table 5. This section describes two graph
`based AMTs - attack graphs and attack trees.
`Attack graphs, attack trees and their variants - which in-
`clude: OCTAVE, event trees and decision trees, are graph based
`representations of a cyber-attack. Of these, attack graphs and
`attack trees are the most popular in the research literature.
`The research shows a clear divide between papers that focus
`on attack graphs and those that focus on attack trees. In other
`words, authors either write about attack graphs or attack trees -
`
`Table 5. Attack modelling techniques - miscellaneous methods
`Method
`Citations
`Use case based
`Misuse cases [363, 10, 364, 251, 412, 298, 387, 184]; misuse
`AMTs
`case maps [188, 185]; security use cases [116]; CORAS [322,
`95, 370, 84, 33]
`Temporal meth-
`Diamond model [58, 210]; cyber kill chain [161, 148, 258,
`ods
`141]; Riskit [200, 202, 124]
`Miscellaneous
`Event tree [182]; OCTAVE [8]; the bowtie method [74, 393,
`graph/tree based
`38, 224, 389]; influence diagrams [357, 3, 160, 341, 107];
`AMTs1
`extended influence diagram [215, 367]
`1 As the title suggests, these are general miscellaneous attack graph/tree based AMTs.
`Attack graph based examples are given in Table 22, and attack tree based examples are
`provided in Table 24.
`
`6
`
`

`

`/ Elsevier Co