Attack trees are important for security, as they help to identify weaknesses and vulnerabilities in a system. Quantitative attack tree analysis supports a number security metrics, which formulate important KPIs such as the shortest, most likely and cheapest attacks.
A key bottleneck in quantitative analysis is that the values are usually not known exactly, due to insufficient data and/or lack of knowledge. Fuzzy logic is a prominent framework to handle such uncertain values, with applications in numerous domains. While several studies proposed fuzzy approaches to attack tree analysis, none of them provided a firm definition of fuzzy metric values or generic algorithms for computation of fuzzy metrics.
In this work, we define a generic formulation for fuzzy metric values that applies to most quantitative metrics. The resulting metric value is a fuzzy number obtained by following Zadeh’s extension principle, obtained when we equip the basis attack steps, i.e., the leaves of the attack trees, with fuzzy numbers. In addition, we prove a modular decomposition theorem that yields a bottom-up algorithm to efficiently calculate the top fuzzy metric value.
1 Introduction
Attack trees. Attack trees (ATs) [32] are a popular tool for modeling and analyzing security risks. They provide a structural way to identify vulnerabilities in a system, by decomposing the attacker’s goal into subgoals, down to basic attack steps that a malicious actor can take to reach said objective. An attack tree consists of basic attack steps (BASs) representing atomic adversary actions, and intermediate AND/OR-gates whose activation depends on the activation of their children. The attacker’s goal is to activate the root (top node), see Fig. 1 for an example. ATs can be trees or directed acyclic graphs (DAGs). ATs have been supported by commercial tools [1‐3] and equipped with semantics [18, 25].
Fig. 1.
The AT model visualises the attack steps by which an attacker can illegally take money from a bank. The attacker needs to enter the bank by breaking in or sneaking in, and also needs to open a vault. Sneaking in, breaking in, and opening a vault cost 30, 5 and 60 minutes, respectively. Hence, the quantitative metric minimal cost for the attacks is \(\min (30+60,5+60)=65\).
×
Quantitative analysis. Beyond qualitative analysis, ATs are also used to calculate important security metrics of the system, e.g., the minimal cost (in money, time or resources) the attacker needs to spend for a successful attack, or the probability of a successful attack. Such metrics are obtained by assigning an attribute value to each BAS, such as the cost needed to perform that BAS, and using this as input to calculate the security metric. When the AT is treeshaped, the metric is quickly calculated using a bottom-up algorithm, propagating values from the BASs to the top. For DAG-shaped ATs this problem is NP-complete, but good heuristics exist [22]. These algorithms are formulated in the generic algebraic structure of semirings, allowing them to be employed to a vast range of security metrics including cost, time, skill, damage, etc.
Anzeige
Uncertain parameters. The methods described above assume that all BAS parameters are known exactly. However, this is problematic in practice: statistics on attacker capabilities may be hard to obtain, and because of the fast-changing nature of the field historical data are only of limited use. Obtaining accurate and realistic parameter values is a key bottleneck in quantitative security analysis. In its absence, there is a great need for methods that allow us to deal with uncertain and approximately known parameter values.
Fuzzy theory. Fuzzy theory is a prominent framework in which parameter uncertainty and its effect on a calculation’s outcome can be expressed mathematically. It has been successfully used in many applications, including machine learning [7], reliability engineering [6], and computational linguistics [24]. Rather than exact (‘crisp’) values, e.g., \(x = 3\), each parameter is assigned a range of values, and to each of these a possibility value in [0, 1] is assigned by means of a membership function. Often, only functions of a specific form are considered, leading to the definition of triangular, trapezoidal, etc. fuzzy numbers [13].
While fuzzy theory has been applied to AT analysis before [11, 17, 19, 35, 36], much of the earlier work lacks mathematical rigor, and none of these apply fuzzy theory to quantitative analysis. As a result, there are no algorithms for calculating AT metrics with fuzzy parameters. In fact, to our knowledge the fuzzy counterpart of quantitative AT analysis has not been defined yet. A key technical hurdle is that the operations typically used in AT analysis do not preserve popular fuzzy number types: for instance, the OR-gate corresponds to the operation min for the minimal cost metric, and applying min to two triangular fuzzy numbers does not yield a triangular fuzzy number.
Contributions. Our first contribution is a clear, mathematically rigorous definition of fuzzy AT metrics. Because these are defined for general fuzzy numbers, rather than specific subtypes such as triangular fuzzy numbers, we sidestep the problem that these subtypes are not preserved under AT metric operations; instead, our definition works for the generic semiring framework defined in [22]. We show that our definition naturally follows from Zadeh’s extension principle [38], a general approach for extending functions to fuzzy numbers.
Anzeige
Having defined fuzzy AT metrics, we furthermore develop a linear-time, bottom-up algorithm for calculating them for tree-shaped ATs. We show the validity of this algorithm by showing that fuzzy AT metrics are susceptible to modular analysis: when an AT has a module, i.e., a minimally connected subcomponent, a fuzzy metric can be computed by first calculating the metric for the module and then for its complement. When an AT has many modules, this substantially speeds up computation. When an AT is tree-shaped, every node is a module, proving the validity of the algorithm.
Our algorithm generalizes the bottom-up algorithm for crisp AT metrics from [22]. Unfortunately, the algorithm for DAG-shaped metrics from that paper does not transfer to the fuzzy setting. The key reason is that fuzzy numbers do not form a semiring, as we show in this paper. Fuzzy metrics for DAG-shaped ATs require a radically new approach, and we leave this for future work.
Summarized our contributions are:
1. A rigorous, general definition of fuzzy AT metrics;
2. A bottom-up algorithm for computing fuzzy metrics in tree-structured ATs;
3. A proof of modular decomposition for fuzzy AT metrics.
The full version of this paper (including the appendix) is available on Zenodo[9].
2 Related work
Below, we provide a literature review for computation of metrics with fuzzy numbers applied to attack trees and the related formalism of fault trees.
Attack tree analysis with fuzzy numbers. An intuitionistic fuzzy set was used to represent the uncertainty and hesitancy present in data [17], or an attack-defense model was proposed [11, 35], or using a fuzzy analytic hierarchy process to establish a successful probability model of cyber attack [19, 36]. However, there have been several studies on the approach of involving fuzzy attribution in fault tree analysis (FTA) summarized [14, 15, 23, 31, 37] for many years.
Fault tree analysis. Fault trees can be considered as the safety variant of attack trees: whereas attack trees indicate how malicious attacks propagate through a system and lead to damage, fault trees indicate how unintended failures propagate and lead to system level failures. Therefore, leaves of a fault tree model component failures and are called basic events (BEs). Due to their similarities, many approaches to fuzzy fault tree analysis can also be applied to attack trees. Comprehensive literature surveys on fault trees with fuzzy numbers can be found in [14, 23, 31, 37].
Fault tree analysis with fuzzy probabilities. Fuzzy set theory was firstly used in fault tree analysis by Tanaka et al. [34] to address the problem of uncertain BEs failure. In the paper, Zadeh’s extension principle was used to estimate the possibility of system failure. The failure possibility of the basic events and top event were represented as trapezoidal fuzzy numbers.
Singer [33] considered the distribution of BEs as fuzzy numbers. The membership function is continuous and is approximated by left and right functions called L-R type fuzzy numbers [10]. Here, L-R type fuzzy numbers are defined by a triplet (m, a, b), where m, a, b are positive real numbers. The author extended algebraic operations on the triplet of L-R type fuzzy numbers and calculated the possibility distribution of the system.
Kim et al. [16] evaluated the possibility of system failure. Similar to [33], L-R type fuzzy numbers are used as the possibilities of BEs. The value m of the triplet (m, a, b) is evaluated by four-expert valuations in the form of triangular fuzzy numbers (TFNs). Each value m is determined to calculate the optimistic and pessimistic possibilities of a system accident. Finally, two cases of possibilities - the pessimistic possibility of system failure with major TFN and the optimistic one with minor TFN - were determined.
Lin et al. [21] estimated failure possibility of ambiguous events. For this purpose, the linguistic variables describing the evaluation data are expressed in triangular or trapezoidal fuzzy numbers denoting failure possibilities. The fuzzy possibility of a top event is calculated using the \(\alpha \)-cut fuzzy operators.
Peng et al. [27] presented an approach to fault diagnosis of communication control systems. All probability values of the fault tree were converted to uniform triangle fuzzy numbers. The fuzzy probability of the top event was then calculated using Zadeh’s principle. A fault tree (FT) consisting of only OR-gates was shown as an analytical example to determine the confidence interval of probability of top event and achieve fuzzy reasoning diagnosis result.
Fault tree reliability analysis with interval arithmetic. Purba et al.[28] developed a fuzzy probability based fault tree analysis to propagate and quantify epistemic uncertainty raised in basic events. BE reliability characteristics are described in fuzzy probabilities. From the BE fuzzy probabilities, the matrix of fuzzy probabilities of the minimal cut sets is generated and then the top event fuzzy probability is quantified using the Fuzzy multiplication rule in engineering applications.
Purba et al. [29] proposed a fuzzy probability and \(\alpha \)-cut based-FTA approach. Each fuzzy probability distribution of BEs is represented uniquely by an \(\alpha \)-cut. The top event \(\alpha \)-cut is quantified into the best estimate \(\alpha \)-cut, the lower bound \(\alpha \)-cut, and the upper bound \(\alpha \)-cut follow fuzzy arithmetic operations on \(\alpha \)-cuts of BEs. The approach was verified by evaluating the reliability of a complex engineering system and the results are compared to the reliability of the same system quantified by conventional FTA.
Fuzzy FTA by conversion of fuzzy number of BEs to crisp probability of BEs. Hu et al. [12] developed an FFTA methodology for analyzing above-ground walled storage system failures. Expert elicitation and fuzzy logic was used to manipulate the ambiguities and vagueness in the linguistic variables of BEs. Fuzzy probability BE was defuzzified to a crisp number. The resultant crisp probability of BEs were used as inputs to generate crisp probability of the top event.
At the time of this writing, fuzzy analysis has not been studied for ATs. The literature has introduced fuzzy analysis of FTs, but it only addresses certain types of fuzzy numbers (trapezoidal, triangular, etc.). This paper thus provides a general mathematical framework for fuzzy analysis of ATs.
3 Fundamentals of fuzzy theory
Fuzzy set theory was introduced by L.A. Zadeh [38] to deal with problems in which vagueness is present. Instead of considering elements x of a set X with a fixed value, we consider fuzzy elements \(\textsf{x}\) which can have a range of possible values; the extent to which \(\textsf{x}\) can be equal to x is expressed by the membership degree of x in \(\textsf{x}\), which is a value \(\textsf{x}[x] \in [0,1]\). The value \(\textsf{x}[x]\) is the confidence one has that \(\textsf{x}\) has value x. Here \(\textsf{x}[x] = 1\) denotes full membership, while \(\textsf{x}[x] = 0\) denotes no membership.
For instance, the time needed to perform an attack may be given as a real number, e.g. \(x = 3 \in \mathbb {R}\); but often the exact time needed is not known precisely, and can be somewhere around 3. This can be represented by a fuzzy number \(\textsf{x}:\mathbb {R} \rightarrow 1\) which is 0 everywhere except close to 3, and which has a maximum at 3 (see Fig. 2).
Fig. 2.
A non-fuzzy, ‘crisp’ element x (a) and a fuzzy element \(\textsf{x}\) (b).
×
Definition 1
Let X be a set. A fuzzy element of X is a function \(\textsf{x}:X \rightarrow [0,1]\). The set of all fuzzy elements of X is denoted \(\textbf{F}(X) := \{ \textsf{x} \ | \ \textsf{x} :X \rightarrow [0,1] \}\).
In the literature, fuzzy elements are usually called fuzzy sets [38], on the basis that the membership function \(\textsf{x}:X \rightarrow [0,1]\) generalizes the indicator function \(1_S:X \rightarrow \{0,1\}\) of a set \(S \subseteq X\); thus a fuzzy set can be thought of as a set of which elements can have partial membership. Instead, we use the term fuzzy element to stress that in this paper, fuzzy elements are used to express the uncertainty of individual values, as in Fig. 2b, rather than the uncertainty of set membership. A fuzzy element \(\textsf{x}\) behaves similarly to a probability density function in that the uncertainty of an element of X is expressed by a function on X.
Our definition of fuzzy element is very general. Many works in the literature restrict the form of the function \(\textsf{x}:X \rightarrow [0,1]\) to make computation more convenient, especially for \(X = \mathbb {R}\), i.e., for so-called fuzzy numbers. Thus there exist triangular, trapezoidal, Gaussian, etc. fuzzy numbers [8, 13].
Example 1
Consider real numbers \(a \le b \le c \le d\). The trapezoidal fuzzy number\(\textsf{trap}_{a,b,c,d} \in \textbf{F}(\mathbb {R})\) is defined as (see Fig. 3):
$$\begin{aligned} \textsf{trap}_{a,b,c,d}[x] &= {\left\{ \begin{array}{ll} \tfrac{x-a}{b-a}, &{} \text {if } a < x \le b,\\ 1, &{} \text {if } b<x<c,\\ \tfrac{d-x}{d-c}, &{} \text {if } c \le x < d,\\ 0, &{} \text {otherwise}. \end{array}\right. } \end{aligned}$$
(1)
The trapezoidal fuzzy number \(\textsf{trap}_{a,b,c,d}\) has the maximal membership degree of 1, i.e., \(\textsf{trap}_{a,b,c,d}[x]=1\) for all \(x\in [b,c]\). At the same time, a and d are the lower and upper bounds of its support, respectively. In case \(b=c\), we have a triangular fuzzy number\(\textsf{tri}_{a,b,d}\).
Fig. 3.
The trapezoidal fuzzy number \(\textsf{trap}_{a,b,c,d}\).
×
For notational convenience we occasionally abbreviate \(\textsf{x}\) via a list of membership values \(x \mapsto \textsf{x}[x]\), omitting x for which \(\textsf{x}[x] = 0\). For example, \(\textsf{x} = \{1 \mapsto 0.7,2 \mapsto 0.5\} \in \textbf{F}(\mathbb {Z})\) is defined by
Arithmetic operations on fuzzy elements are performed following Zadeh’s extension principle [4, 13, 38‐41]. This principle provides a framework to apply functions and arithmetic operations on sets to their fuzzy elements. Before giving the full definition, we motivate it by an example.
Example 2
Consider \(\textsf{x},\textsf{y} \in \textbf{F}(\mathbb {N})\) given by
We wish to calculate the addition of \(\textsf{x}\) and \(\textsf{y}\), which we write as \(\textsf{x}\widetilde{+}\textsf{y}\). This is also an element of \(\textbf{F}(\mathbb {N})\) and so we must specify the confidence \((\textsf{x}\widetilde{+}\textsf{y})[z]\) that the sum values to z, for all \(z \in \mathbb {N}\). Consider \(z = 8\); the sum values to 8 only in one of these two cases:
\(\textsf{x}\) values to 2 and \(\textsf{y}\) values to 6;
\(\textsf{x}\) values to 3 and \(\textsf{y}\) values to 5.
Our confidence that \(\textsf{x}\) values to 2 is \(\textsf{x}[2] = 0.4\), and our confidence that \(\textsf{y}\) values to 6 is \(\textsf{y}[6] = 0.6\). Our confidence that both of these are true, i.e., that the first case holds, is then \(\min \{0.4,0.6\} = 0.4\). Similarly, our confidence that the second case holds is \(\min \{1,1\} = 1\). Our confidence \((\textsf{x}\widetilde{+}\textsf{y})[8]\) that the sum values to 8 is then the confidence that either of the two cases above holds; this is expressed by the maximum, so
Similarly one can calculate \((\textsf{x}\widetilde{+}\textsf{y})[z]\) for other values of z, by taking all possible outcomes of the sum and calculating their confidence. This yields
The idea behind Example 2 can be applied to general multivariate functions. The only change that needs to be made is that in general, there may be infinitely many pairs (x, y) such that \(f(x,y) = z\); therefore one needs to take the supremum over all \(\min \{\textsf{x}[x],\textsf{y}[y]\}\) rather than the maximum.
Definition 2 (Zadeh’s Extension Principle)
[Zadeh’s Extension Principle] Let f be a multiargument function \(f:X_1\times X_2\times \dots \times X_n \rightarrow Y\). The Zadeh extension of f is the function \(\tilde{f}:\textbf{F}(X_1) \times \ldots \times \textbf{F}(X_n) \rightarrow \textbf{F}(Y)\) defined as:
Based on the extension principle, different arithmetic operations on fuzzy numbers have been defined [4, 5, 20, 27, 34]. As a result of Definition 2, addition and subtraction operations on fuzzy numbers typically have straightforward formulations. E.g., for two trapezoidal fuzzy numbers we have
Multiplication and division, however, are nonlinear operations that produce fuzzy numbers of different types than the operands; for example, the quotient of two trapezoidal fuzzy numbers is itself not trapezoidal. For convenience and to simplify the computation, the resulting fuzzy number can be approximated by a fuzzy number of the same type. The computation and visualisation of these estimations can be found in [5].
In section 5, we will apply the general fuzzy element framework to formulate fuzzy attack tree metrics. Unfortunately, the operators considered in AT analysis, such as \(\min \), do not preserve triangular, trapezoidal, etc. fuzzy numbers. We therefore need to work with fuzzy numbers and Zadeh extensions in full generality as defined above.
4 Attack trees
In this section, we provide a brief overview of ATs as presented in [22]. Attack trees are hierarchical graphical models that illustrate the attack process. The trees are usually drawn inverted, with the root node located at the top of the tree and branches descending from the root to the lowest levels of the tree – the leaves. The root node represents the attacker’s overall objective. The leaves in ATs are called Basic Attack Steps (BASs) representing the attacker’s activities. Nodes between the leaves and the root node depict transitional states or attacker sub-goals. These intermediate steps are equipped with logical gates that indicate whether an intermediate step succeeds, e.g. the AND-gate succeeds if all input children succeed, the OR-gate is successful if at least one child does succeed.
Definition 3
[22] An attack tree is a tuple \(T=(N,E,t)\), where (N, E) is a rooted directed acyclic graph, and t is a map \(t:N \rightarrow \{\texttt{BAS},\texttt{OR},\texttt{AND} \}\) such that \(t(v) = \texttt{BAS} \) if and only if v is a leaf for all \(v \in N\).
The root of T is denoted \(R_T\), and the set of children of a node v is denoted \(ch(v) = \{w \in N \mid (v,w) \in E\}\). The set of basic attack steps is denoted \(\textrm{BAS}_T = \{v \in N \mid t(v) = \texttt{BAS} \}\).
4.1 Semantics for attack trees
The semantics of an AT are defined by its successful attacks, i.e., attacks that activate the top node. Formally, an attack is a subset \(A \subseteq \textrm{BAS}_T\). For example, in Fig. 1, \(\{p,r\}\) is an attack, corresponding to stealing money by breaking in and then opening the vault. An attack’s success is most conveniently expressed by the structure function, which is defined recursively as follows:
Definition 4
[22] Let T be an AT. The structure function\(f_T:N \times 2^{\textrm{BAS}_T}\rightarrow \{0,1\}\) of T is defined, for a node \(v \in N\) and an attack \(A \subseteq \textrm{BAS}_T\), by
(2)
An attack A is said to reach a node v if \(f_T(v,A) = \mathtt {{1}}\), i.e. it makes v succeed. If no proper subset of A reaches v, then A is a minimal attack on v. The set of minimal attacks on \(R_T\) is denoted
. For example, the AT from Fig. 1, has three successful attacks: \(\{r,q\}\), \(\{r,p\}\), and \(\{r,q,p\}\). The first two are minimal, so we have:
.
Discussion regarding attacks and semantics for ATs are presented in [22]. Note that adding BASes to an attack will not make it less successful; hence the successful attacks are determined by
. This leads to the following definition of the semantics.
Definition 5
The semantics of an ATT is its suite of minimal attacks
.
4.2 Security metrics for attack trees
Quantitative AT analysis may concern various attributes, such as cost, time, damage, etc. To handle all these attributes in a generic way, analysis algorithms work over a so-called attribute domain\((V,\triangledown ,\vartriangle )\). Here V is the value domain for the attribute, e.g., \(\mathbb {R}_{\ge 0}\) for costs, and [0, 1] for probability. Furthermore, \(\triangledown \) and \(\vartriangle \) are binary operators on V, where \(\triangledown \) denotes the way values are propagated over an \(\texttt{OR} \)-gate: If \(T = \texttt{OR} (a,b)\) and a, b are BASs assigned metric values \(x_a,x_b\), then \(x_a \triangledown x_b\) is the security value of T. Similarly \(\vartriangle \) is the operator corresponding to the \(\texttt{AND} \)-gate. For technical reasons we assume \(\triangledown \) and \(\vartriangle \) satisfy some algebraic properties, which is encoded in the definition of a semiring.
Definition 6
[22] A semiring is a tuple \((V,\triangledown ,\vartriangle )\) where V is a set, \(\triangledown \) and \(\vartriangle \) are commutative associative binary operators on V, and \(\vartriangle \) distributed over \(\triangledown \) (i.e. \(x \vartriangle (y \triangledown z) = (x \vartriangle y) \triangledown (x \vartriangle z)\)).
To assign a metric value to an AT T, one chooses a semiring V in which the metric takes value, as well as a BAS value \(x_a \in V\) for each BAS a; this is encoded as a vector \(\vec {x} \in V^{\textrm{BAS}_T}\). The calculation of T proceeds in two steps: first, we assign values to an attack \(A = \{a_1,\ldots ,a_n\}\). Since all BASs have to be executed, we set \(m_A(\vec {x}) = \bigtriangleup _{i=1}^n x_{a_i}\). This corresponds to the cost/damage/probability/etc. of the attack A, given the BAS values \(\vec {x}\). Next, we calculate the metric value of T as a whole. To do this, we consider the set of all minimal attacks
. Since for the top node to be reached one only needs one minimal attack, the metric value for T is calculated via \(m_T(\vec {x}) = \bigtriangledown _{i=1}^m m_{A_i}(\vec {x})\).
Example 3
We consider the minimal cost metric that assigns to an AT the minimal cost the attacker needs to spend to successfully reach the top node. This corresponds to the semiring \((\mathbb {N},\min ,+)\). Indeed, the cost needed to activate the top node in \(\texttt{OR} (a,b)\) is the minimum of the costs \(x_a\) and \(x_b\), as only one of the two children needs to be activated; hence \(\triangledown = \min \). Similarly, an \(\texttt{AND} \)-gate needs to activate all children, so their costs need to be added and \(\vartriangle = +\). Then given a vector \(\vec {x} \in \mathbb {R}_{\ge 0}^{\textrm{BAS}_T}\) assigning a cost value \(x_a \in \mathbb {R}_{\ge 0}\) to each BAS a, the metric value of T is defined as
. Here \(\sum _{a \in A} x_a\) is the total cost of performing an attack A, so the metric value corresponds to the cost of the cheapest minimal attack. Consider the AT \(T=\textrm{AND}\big (r,\textrm{OR}(q,p)\big )\) in Fig. 1. Recall that
, and consider an attribution \(\vec {x}\) given by \(x_r = 60, x_q = 30, x_p = 5\). Then the metric can be calculated as follows.
Formalizing the discussion and example above leads to the following definition.
Definition 7
[22] Let T be an AT and let \((V,\triangledown ,\vartriangle )\) be a semiring.
1.
An attribution of T in V is an element \(\vec {x}\) of \(V^{\textrm{BAS}_T}\).
2.
Given an attribution \(\vec {x}\), the metric value of T given V and \(\vec {x}\) is defined as
(3)
As is implicit from the notation, we consider a metric to be a function \(m_T:V^{\textrm{BAS}_T}\rightarrow V\) that takes as input the vector \(\vec {x}\) of BAS attribute value (e.g. BAS costs), and outputs the AT’s security value (e.g. minimal cost needed to successfully attack the AT). This viewpoint is useful when extending AT metrics to the fuzzy setting in the next section.
5 Fuzzy metrics for attack trees
To define fuzzy AT metrics — as stated, to the best of our knowledge no such definition exist yet — we equip each BAS with a fuzzy element of V, i.e., an element of \(\textbf{F}(V)\). Thus, a fuzzy attribution is an element \(\vec {\textsf{x}}\) of \(\textbf{F}(V)^{\textrm{BAS}_T}\), assigning a fuzzy element \(\textsf{x}_a\) to each BAS a. For crisp metrics, the AT’s metric value is obtained by applying a function \(m_T\) to the crisp attribution vector \(\vec {x}\), as outlined in Definition 7. Analogously, we obtain the fuzzy metric value by applying \(\tilde{m}_T\) to \(\vec {\textsf{x}}\), where \(\tilde{m}_T\) is the Zadeh extension of \(m_T\).
Example 4
Consider the AT \(T = \textrm{AND}(r, \textrm{OR}(q,p)) \) from Fig. 1; recall that
. We consider the minimal time metric, corresponding to the semiring \((\mathbb {R}_{\ge 0},\min , +)\). For this semiring, consider the fuzzy attribution \(\vec {\textsf{x}} = (\textsf{x}_r, \textsf{x}_q, \textsf{x}_p)\) given by \(\textsf{x}_r = \{50 \mapsto 1, 60 \mapsto 1\}, \textsf{x}_q = \{0\mapsto 1\}\), and \(\textsf{x}_p = \{5 \mapsto 1\}\), respectively; that is, q and p have crisp time values, and r either takes time 50 or 60, with equal possibility.
Since the minimal attacks are \(\{r,q\}\) and \(\{r,p\}\), the function \(m_T:V^3 \rightarrow V\) is given by \(m_T(x_r,x_q,x_p) = \min (x_r+x_q,x_r+x_p)\) for all \(x_r,x_q,x_p \in V\). Then the fuzzy metric value is equal to \(\tilde{m}_T(\textsf{x}_r,\textsf{x}_q,\textsf{x}_p)\). Using the definition of Zadeh extension from Definition 2, the confidence that this fuzzy metric value is equal to a \(y \in \mathbb {R}_{\ge 0}\) is equal to
Since \(\textsf{x}_q[x_q] \ne 0\) only for \(x_q = 0\), where \(\textsf{x}_q[x_q] = 1\), we only need to consider \(x_q = 0\), and, for the same reason, we only need to consider \(x_p = 5\). Thus the expression above is equal to
so \(\widetilde{m}_T(\vec {\textsf{x}}) = \{50 \mapsto 1, 60 \mapsto 1\}\).
Formally fuzzy AT metrics are then defined as follows.
Definition 8
Let T be an AT and let \((V,\triangledown ,\vartriangle )\) be a semiring.
1.
A fuzzy attribution is an element \(\vec {\textsf{x}}\) of \(\textbf{F}(V)^{\textrm{BAS}_T}\).
2.
Given a fuzzy attribution \(\vec {\textsf{x}}\), the fuzzy metric value of T given V and \(\vec {\textsf{x}}\) is defined as \(\widetilde{m}_T(\vec {\textsf{x}})\), where \(\widetilde{m}_T:\textbf{F}(V)^{\textrm{BAS}_T} \rightarrow \textbf{F}(V)\) is the Zadeh extension of the function \(m_T\) from Definition 7.
More concretely, \(\widetilde{m}_T(\vec {\textsf{x}})\) is the fuzzy element of V defined, for \(y \in V\), by
×
Our choice of using Zadeh’s extension to extend crisp AT metrics to fuzzy AT metrics is justified by the fact that Zadeh extension treats the input fuzzy numbers \(\textsf{x}_1,\ldots ,\textsf{x}_n\) as independent, i.e., it assumes that there is no nontrivial joint fuzzy distribution on the product space \(\prod _i X_i\) of which the \(\textsf{x}_i\) are the marginal distributions [30]. This is a standard assumption on BASes (See [26] for a similar viewpoint on fault trees) which we follow. In theory, one could extend the definition to allow non-independent BASes with more complicated joint fuzzy distributions. However, the prevailing viewpoint is that such relations should be explicitly modeled into the AT itself. For example, if the non-independence is due to a common cause affecting the joint distribution of multiple BAS attribute values, then this common cause should be explicitly modeled into the AT framework by replacing the BAS by sub-ATs with shared nodes [26]. We will follow this philosophy and use the Zadeh extension as the natural way to define fuzzy AT metrics.
An alternative way of defining fuzzy AT metrics would be to replace the crisp operators \(\triangledown , \vartriangle \) in (3) with their fuzzy counterparts \(\widetilde{\triangledown }, \widetilde{\vartriangle }\). However, this does not coincide with our definition, as the following result shows:
Theorem 1
In general,
(5)
This result is shown by the following example.
Example 5
We continue Example 4, where \(\widetilde{m}_T(\textsf{x}_p,\textsf{x}_q,\textsf{x}_r) = \{50 \mapsto 1, 60 \mapsto 1\}\). On the other hand,
×
One could calculate this fuzzy number in a manner analogous to Example 4, but here we show another method that is often more convenient. For a fuzzy number \(\textsf{x} \in \textbf{F}(\mathbb {R}_{\ge 0})\), define \(\textsf{x}^{(1)} = \{x \in \mathbb {R}_{\ge 0} \mid \textsf{x}[x] = 1\}\); this is the level 1 \(\alpha -\)cut of \(\textsf{x}\) [13]. Then from Definition 2 one can deduce that for \(\textsf{x},\textsf{y} \in \textbf{F}(\mathbb {R}_{\ge 0})\) and \(f:\mathbb {R}_{\ge 0}^2 \rightarrow \mathbb {R}_{\ge 0}\) one has
$$ (\tilde{f}(\textsf{x},\textsf{y}))^{(1)} = \{f(x,y) \mid x \in \textsf{x}^{(1)}, y \in \textsf{y}^{(1)}\}. $$
For brevity we abbreviate the right hand side of this equation to \(f(\textsf{x}^{(1)},\textsf{y}^{(1)})\). It follows that
Hence
if and only if \(x \in \{50,55,60\}\). Since this fuzzy number only takes possibility values 0 and 1, it follows that
The ‘extra’ possibility \(55 \mapsto 1\) on the LHS comes from comparing the attack \(\{r,q\}\) with cost \(60+0\) to the attack \(\{r,p\}\) with cost \(50+5\). In other words, in this comparison r is considered to have costs 50 and 60 simultaneously. By contrast, in the calculation of \(\tilde{m}_T(\vec {\textsf{x}})\) the cost \(x_r\) can only have one value at a time.
×
Equation (5) shows that a priori, there are two ways one can define fuzzy AT metrics. We choose to use the definition of \(\widetilde{m}_T(\vec {\textsf{x}})\) via Zadeh’s extension as in Definition 8 for two reasons: first, this accurately captures the independence of the BASes as outlined below Definition 8. Second, we show in Theorem 3 that this definition satisfies modular decomposition, a fundamental property of AT metrics. The RHS of (5) does not satisfy modular decomposition, giving another argument why Definition 8 is the preferred definition (see Remark 2 below).
Fig. 4.
Two triangular fuzzy numbers and their minimum, as a Zadeh extension of the function \(\min \).
×
Example 6
Consider the AT \(T = \textrm{OR}(a,b)\) with the min cost metric, represented by the semiring \((\mathbb {R}_{\ge 0},\min ,+)\). As fuzzy attributions consider \(\textsf{x}_a = \textsf{tri}_{0,1,4}\) and \(\textsf{x}_b = \textsf{tri}_{1,2,3}\). Then one can show (see Fig. 4) that \(\widetilde{m}_T(\vec {\textsf{x}}) = \widetilde{\min }(\textsf{x}_a,\textsf{x}_b)\) is given by
In particular \(\widetilde{\min }(\textsf{x}_a,\textsf{x}_b)\) is not a triangular fuzzy number. Hence triangular fuzzy numbers are not preserved by the operations inherent to AT analysis. The same holds for other popular subtypes of fuzzy numbers such as rectangular numbers; for this reason, we define fuzzy quantitative AT analysis for general fuzzy numbers in Definition 8. Finding subtypes of fuzzy numbers that are preserved by AT analysis operations forms an interesting avenue for future research.
Remark 1
Besides AT metrics as defined in this paper, in [22] quantitative analysis for so-called dynamic ATs (DATs) is also defined. DATs include a new gate type SAND (“sequential AND”) used when attack steps have to be performed in sequential order; the normal AND-gate allows its children to be performed in parallel. This changes both semantics and quantitative analysis: an attack is now a partially ordered set \((A,\prec )\) rather than just a set A of BASes, to denote the relative timing behaviour of the attack steps; and for quantitative analysis a third binary operation \(\triangleright \) is introduced to correspond to SAND-gates, and the metric is defined in terms of these operators.
The results of this paper straightforwardly carry over to the DAT setting. That is, fuzzy DAT metrics are defined as the Zadeh extension of crisp DAT metrics akin to Definition 8. Furthermore, this definition satisfies modular decomposition, which follows from the modular decomposition of crisp DAT metrics analogous to Theorem 3. As a result, a bottom-up algorithm analogous to Alg. 1 calculates fuzzy DAT metrics for treelike DATs.
6 Metric computation for ATs
To calculate the fuzzy AT metric \(\tilde{m}_T(\textsf{x})\) directly from Definition 8, one first needs to calculate the function \(m_T\), which in return requires one to find
. In general, this set is of exponential size, making calculation cumbersome for large ATs. Therefore, dedicated algorithms for quantitative AT analysis are needed. For crisp AT metrics these are described in [22]. In this section, we define a bottom-up algorithm for calculating fuzzy AT metrics for tree-shaped ATs, and we show that its validity follows from the fact that fuzzy AT metrics satisfy modular decomposition. We also show that the BDD-based approach for metric calculation for DAG-shaped ATs from [22] does not extend to the fuzzy case, and that a radically new approach is needed.
6.1 Bottom-up algorithm
The bottom-up algorithm presented in Algorithm 1 is adapted from the bottom-up algorithm for crisp AT metrics first presented in [25]. It takes as input an AT T, a node v of T, a semiring \(D = (V,\triangledown ,\vartriangle )\), and a fuzzy attribution \(\vec {\textsf{x}}\), and outputs a fuzzy value \(\widetilde{\texttt{BU}}(T,v,D,\vec {\textsf{x}}) \in \textbf{F}(V)\) assigned to v; this value corresponds to the metric value associated to reaching v. If \(t(v) = \texttt{BAS} \), this is simply \(\textsf{x}_v\). If \(t(v) = \texttt{OR} \), then \(\widetilde{\texttt{BU}}(T,v,D,\vec {\textsf{x}})\) is obtained by applying \(\widetilde{\triangledown }\) to the values associated to the children of v; for \(t(v) = \texttt{AND} \) we instead use \(\widetilde{\vartriangle }\). The AT’s fuzzy metric value is then given by \(\widetilde{\texttt{BU}}(T,R_T,D,\vec {\textsf{x}})\).
×
Theorem 2
Let T be a static AT with tree structure, \(D = (V,\triangledown ,\vartriangle )\) a semiring, and \(\vec {\textsf{x}}\) a fuzzy attribution with values in V. Then \(\widetilde{m}_T(\vec {\textsf{x}}) = \widetilde{\texttt{BU}}(T, R_T , D,\vec {\textsf{x}})\).
Example 7
We apply the algorithm to Example 4. Then the algorithm calculates the metric as follows
The algorithm is efficient as we can see that it is linear in |E|, making it vastly more efficient than first calculating \(m_T\) and then Zadeh-extending it. The algorithm is generic as it is applicable to popular quantitative metrics in ATs such as cost, damage, skill, probability, etc. [22]. We should note, however, that the linearity of the time complexity assumes that the fuzzy operations \(\widetilde{\triangledown }\) and \(\widetilde{\vartriangle }\) take constant time.
While the algorithm applies only to tree-structured ATs, this covers a large portion of the ATs found in the literature [25]. As such, the algorithm can be used in many applications.
As we show in the appendix of [9], the proof of Theorem 2 depends on a fundamental property of AT metrics called modular decomposition. In the next section, we will explain this and show that fuzzy metrics satisfy this property.
6.2 Modular decomposition
Modular decomposition is a fundamental property of AT metrics as it facilitates the recursive solution of many problems, which typically improves performance.
For a node v in an AT T, let \(T_v\) be the AT consisting of all descendants of v, i.e., the nodes w for which there exists a path \(v \rightarrow w\). This is a rooted DAG with root v. A module is a node v for which \(T_v\) is only minimally connected to the rest of T:
Definition 9
Let \(v \in N \setminus \textrm{BAS}\). We call node v a module if v is the only node in \(T_v\) with connections to \(T\setminus T_v\).
For instance, in Fig. 1, the modules are “enter the bank” and “get money”. Finding the modules of an AT aids in calculating metrics as follows. Given a module v, one can split up T into two parts: the sub-AT \(T_v\) with root v, and the ‘quotient’ \(T^v\) obtained by replacing the entire sub-AT v with a single new node, which we will still call v (see Fig. 5). Then one can calculate the metric for \(T_v\) to find \(\widetilde{m}_{T_v}(\vec {\textsf{x}})\), and use this as a BAS attribute value for v in \(T^v\). One then calculates the metric value for \(T^v\) with this new BAS value. In [22, Thm. 9.2] it is shown that for crisp metrics this results in the same metric value for T as when one considers the entirety of T at once. As a result, we can split up metric calculations via a divide-and-conquer approach once one has identified the modules. The following theorem shows that this also holds for fuzzy AT metrics.
Theorem 3
Let \((V, \triangledown , \vartriangle )\) be a semiring. Let v be a module in an AT T, \(\vec {\textsf{x}} \in \textbf{F}(V)^{\textrm{BAS}_T}\) be a fuzzy attribution for T. Let \(\vec {\textsf{x}}_v \in \textbf{F}(V)^{\textrm{BAS}_{T_v}}\) be the fuzzy attribution for \(T_v\) obtained from restricting \(\textsf{x}\), i.e., \((\vec {\textsf{x}}_v)_w = \textsf{x}_w\) for all \(w \in \textrm{BAS}_{T_v}\). Let \(T^v\) be the AT obtained by replacing \(T_v\) in T by a single BAS still called v. Let \(\vec {\textsf{x}}^v \in \textbf{F}(V)^{\textrm{BAS}_{T^v}}\) be a fuzzy attribution for \(T^v\) given by
Then \(\widetilde{m}_{T}(\vec {\textsf{x}}) = \widetilde{m}_{T^v}(\vec {\textsf{x}}^v)\).
Fig. 5.
Calculation of \(\widetilde{m}_T(\vec {\textsf{x}})\) can be done by computing \(\widetilde{m}_{T^v}(\vec {\textsf{x}}^v)\), where \(v' \in \text {BAS}_{T^v}\) is assigned with fuzzy attribute \(\widetilde{m}_{T_v}(\vec {\textsf{x}}_v)\).
×
The theorem is the extension of Theorem 9.2 of [22]. The proof of Theorem 3 is shown in the appendix of [9]. In a treelike AT, every node is a module, and applying modular decomposition then yields Theorem 2.
Remark 2
In the same way that Theorem 3 can be used to prove Theorem 2, it can also be used to show that the alternative definition of fuzzy AT metrics in the RHS of (5) does not satisfy modular decomposition. Namely, if the alternative definition would satisfy modular decomposition, Alg. 1 would also calculate the alternative definition for treelike ATs. However, since this does not conform to our Definition 8 even for treelike ATs (see Theorem 1), we conclude that the alternative definition does not satisfy modular decomposition.
6.3 Computations for DAG ATs
Directed acyclic graph (DAG) ATs refer to ATs in which a node has more than one parent [22]. Fig. 6a visualizes an AT with DAG structure. Unfortunately, Alg. 1, does not correctly compute the (fuzzy) metric value of DAG-shaped ATs. The reason for this is that the algorithm does not detect whether a node’s child is shared with another node or not, which leads to double counting of a child’s metric value.
Example 8
Let \(\textsf{x}_u=\{1 \mapsto 1\}, \textsf{x}_v=\{0 \mapsto 1, 3 \mapsto 1\}, \textsf{x}_w=\{1 \mapsto 1\},\) and \( D=\{\mathbb {N}, \min , + \}\). The min cost computation for the DAG AT shown in Fig. 6a using algorithm 1 gives \(\widetilde{\texttt{BU}}(T, R_T , \textsf{x}, D) = \widetilde{\min } (\textsf{x}_u, \textsf{x}_v) \ \widetilde{+} \ \widetilde{\min } (\textsf{x}_v, \textsf{x}_w) = \{0\mapsto 1, 1 \mapsto 1\} \ \widetilde{+} \ \{0\mapsto 1, 1 \mapsto 1\} = \{0 \mapsto 1, 1 \mapsto 1, 2 \mapsto 1 \}\), whereas \(\widetilde{m}_T(\textsf{x}_u, \textsf{x}_v, \textsf{x}_w) = \{0 \mapsto 1, 2 \mapsto 1\}\).
Fig. 6.
A DAG AT (a), and its BDD (b).
×
For crisp metrics, this was solved by the BDD-based approach introduced in [22]. Boolean functions are compactly represented by a binary decision diagram(BDD), a type of directed acyclic graph. One can apply this to the structure function of an AT as in Fig. 6b: as one can see, each nonleaf is labeled with a BAS and has two outgoing edges, while the leafs are labeled \(\texttt{0}\) and \(\texttt{1}\). For a given attack A, the BDD evaluates \(f_T(R_T,A)\) as follows: at a node with label v, follow the dashed line if \(v \notin A\), and the nondashed line if \(v \in A\). The leaf in which one ends up holds the value of \(f_T(R_T,A)\). Every Boolean function can be represented as a BDD, and although the corresponding BDD is worst-case of exponential size, BDDs are usually quite compact.
The BDD can also be used to calculate (crisp) AT metrics. We showcase this for the minimal cost metric, but it can be applied to other metrics, so long as the corresponding semiring is absorbing (see [22]). Minimal cost is calculated as follows: for each BAS v, the cost \(x_v\) is attached to the nondashed edges originating from BDD nodes with label v, while each dashed edge gets label 0 (see Fig. 6b). Then the attack with minimal cost corresponds to the shortest path from \(R_T\) to \(\texttt{1}\) in the BDD; since the BDD is acyclic this computation is linear in the size of the BDD. In total, this means that this is worst-case exponential in the size of the AT, but in practice the calculation is quite fast.
Unfortunately, this approach no longer works for fuzzy AT metrics. The reason is that this approach assumes that the metric arises from a semiring, in particular, that distributivity holds. As the following example shows, if \((V,\triangledown ,\vartriangle )\) is a semiring, then \((\textbf{F}(V),\widetilde{\triangledown },\widetilde{\vartriangle })\) is no longer a semiring, because distributivity no longer holds. It is therefore no surprise that the BDD method no longer works either.
Example 9
Let \((V,\triangledown ,\vartriangle ) = (\mathbb {R}_{\ge 0}, \min ,+)\), and consider the fuzzy elements \(\textsf{x} = \{0 \mapsto 1, 2 \mapsto 1\}\) and \(\textsf{y} = \textsf{z} = \{0 \mapsto 1\}\). Then using the methods from Example 5, we find that
Hence \((\textbf{F}(\mathbb {R}_{\ge 0}),\widetilde{\min },\widetilde{+})\) is not distributive, and in particular not a semiring.
The reason that distributivity fails for fuzzy numbers is that, as we discussed in Section 5, a Zadeh-extended operator like \(\widetilde{+}\) acts as though its two arguments are independent. However, in an expression like \(\widetilde{\min }(\textsf{x}\widetilde{+}\textsf{y},\textsf{x}\widetilde{+}\textsf{z})\) the arguments \(\textsf{x}\widetilde{+}\textsf{y}\) and \(\textsf{x}\widetilde{+}\textsf{z}\) are typically not independent. This ensures that distributivity is not retained under Zadeh extension.
Since the BDD method used for crisp AT metrics does not work, a new method is needed for calculating fuzzy metrics for DAG-like ATs. This is beyond the scope of this paper. One possible way to approach this problem is to find a way to keep track of the ‘double counting’ that occurs when applying \(\widetilde{\texttt{BU}}\) to DAG-like ATs, and eliminate it at the end of the algorithm. Such an approach would require a radically new, strategy, and we therefore leave it to future work.
7 Conclusion and future work
In this paper we define a mathematical formulation for deriving AT fuzzy metrics values. In our knowledge, fuzzy theory has been applied in FTs for imprecise data, but fuzzy quantitative metrics remain somewhat implicitly defined. The definition we provide is explicit and generic for commonly used quantitative metrics. Moreover, this definition can be used to better capture uncertainty in quantitative metrics values. In addition, this paper introduces an efficient algorithm to calculate AT metrics with fuzzy attribution. The proposed algorithm is linear in |E|, as opposed to the definition of fuzzy metrics which requires calculation of crisp metrics followed by fuzzy operators. The algorithm works for tree-like structure models that satisfy modular decomposition.
In the future, we want to develop an algorithm for fuzzy metrics computation on DAG ATs. For that aim, the algorithm should address the non-semiring property of fuzzy operators and the DAG structure on ATs. Another avenue for future research is the development of subtypes of fuzzy numbers that are preserved by (Zadeh-extended) arithmetic operations inherent to AT analysis, such as \(\min \) and \(\max \). Upon formally defining such subtypes, these can then be used to implement quantitative analysis algorithms efficiently.
Acknowledgement
This research has been partially funded by ERC Consolidator grant 864075 CAESAR and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101008233.
Disclosure of Interests
The authors have no competing interests to declare that are relevant to the content of this article.
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
. For example, the AT from Fig. 1, has three successful attacks: \(\{r,q\}\), \(\{r,p\}\), and \(\{r,q,p\}\). The first two are minimal, so we have:
.
. This leads to the following definition of the semantics.
.
. Since for the top node to be reached one only needs one minimal attack, the metric value for T is calculated via \(m_T(\vec {x}) = \bigtriangledown _{i=1}^m m_{A_i}(\vec {x})\).
. Here \(\sum _{a \in A} x_a\) is the total cost of performing an attack A, so the metric value corresponds to the cost of the cheapest minimal attack. Consider the AT \(T=\textrm{AND}\big (r,\textrm{OR}(q,p)\big )\) in Fig. 1. Recall that
, and consider an attribution \(\vec {x}\) given by \(x_r = 60, x_q = 30, x_p = 5\). Then the metric can be calculated as follows.
. We consider the minimal time metric, corresponding to the semiring \((\mathbb {R}_{\ge 0},\min , +)\). For this semiring, consider the fuzzy attribution \(\vec {\textsf{x}} = (\textsf{x}_r, \textsf{x}_q, \textsf{x}_p)\) given by \(\textsf{x}_r = \{50 \mapsto 1, 60 \mapsto 1\}, \textsf{x}_q = \{0\mapsto 1\}\), and \(\textsf{x}_p = \{5 \mapsto 1\}\), respectively; that is, q and p have crisp time values, and r either takes time 50 or 60, with equal possibility.
if and only if \(x \in \{50,55,60\}\). Since this fuzzy number only takes possibility values 0 and 1, it follows that 
. In general, this set is of exponential size, making calculation cumbersome for large ATs. Therefore, dedicated algorithms for quantitative AT analysis are needed. For crisp AT metrics these are described in [22]. In this section, we define a bottom-up algorithm for calculating fuzzy AT metrics for tree-shaped ATs, and we show that its validity follows from the fact that fuzzy AT metrics satisfy modular decomposition. We also show that the BDD-based approach for metric calculation for DAG-shaped ATs from [22] does not extend to the fuzzy case, and that a radically new approach is needed.