11institutetext: University of Twente, Enschede, the Netherlands
11email: {t.k.n.dang, m.a.lopuhaa<EMAIL_ADDRESS>
22institutetext: Radboud University, Nijmegen, the Netherlands
22email<EMAIL_ADDRESS>

# Fuzzy Fault Trees Formalized††thanks: 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.

Thi Kim Nhung Dang 11 Milan Lopuhaä-Zwakenberg 11 Mariëlle Stoelinga 1122

###### Abstract

Fault tree analysis is a vital method of assessing safety risks. It helps to
identify potential causes of accidents, assess their likelihood and severity,
and suggest preventive measures. Quantitative analysis of fault trees is often
done via the _dependability_ metrics that compute the system’s failure
behaviour over time.

However, the lack of precise data is a major obstacle to quantitative
analysis, and so to reliability analysis. Fuzzy logic is a popular framework
for dealing with ambiguous values and has applications in many domains. A
number of fuzzy approaches have been proposed to fault tree analysis, but —to
the best of our knowledge— none of them provide rigorous definitions or
algorithms for computing fuzzy unreliability values.

In this paper, we define a rigorous framework for fuzzy unreliability values.
In addition, we provide a bottom-up algorithm to efficiently calculate fuzzy
reliability for a system. The algorithm incorporates the concept of
$\alpha$-cuts method. That is, performing binary algebraic operations on
intervals on horizontally discretised $\alpha$-cut representations of fuzzy
numbers. The method preserves the nonlinearity of fuzzy unreliability.
Finally, we illustrate the results obtained from two case studies.

###### Keywords:

Fault trees reliability analysis fuzzy numbers

##  1 Introduction

_Fault trees._ Fault trees (FTs) are a systematic, graphical tool used to
identify potential sources of failure in a system. By analyzing an FT, a
designer can identify potential failure paths, understand the impact of
failures, and determine the best measures to prevent them. A FT is a directed
acyclic graph (DAG) that consists of basic events (BEs) representing atomic
failure events, intermediate AND/OR gates whose activation depends on that of
their children, and the root representing system failure. The system fails
when the root is activated. We provide a brief overview of FTs in Sec.4

_Quantitative analysis._ Whereas qualitative analysis identifies critical
factors and root causes in a system design, quantitative analysis generates
relevant numerical values. Typical metrics include the system reliability,
availability, mean time to failure, etc. We are focused on _(un)reliability_ ,
a method that calculates system failure probability, where BEs are equipped
with probabilistic information. Unreliability is a critical safety metric to
ensure system safety and availability.

_Uncertain parameters._ Conventional fault tree analysis (FTA) assumes failure
probability is exact or a single estimated value. However, it is infeasible in
practice to estimate a failure rate or probability as we must handle two types
of uncertainty: aleatoric uncertainty that stems from natural fluctuations,
modeled as probability distributions; and epistemic uncertainty that stems
from a lack of knowledge, in our case not knowing exact values for failure
rates. Thus, methods that allow us to deal with uncertain parameter values are
urgently needed.

_Fuzzy theory._ Fuzzy theory is a common framework for handling imprecise
data/uncertainty. Fuzzy logic has been applied in various domains such as
control systems [2], medical imaging, economic risk assessment, decision trees
[3] and machine learning [4]. Fuzzy logic models uncertainty/similarity by a
range of values, and to each of these a possibility value in $[0,1]$ is
assigned by means of a _membership function_. Fundamentals of fuzzy theory are
summarised in Sec.3 and based on our earlier paper [5].

While fuzzy theory has been proposed in many studies to overcome the
limitation of conventional FTA [11, 16, 8, 14], it has been lacking in
mathematical rigor in much of the earlier work. In addition, there are no
efficient algorithms for calculating unreliability with fuzzy parameters.
Performing exact calculations for nonlinear operations is computationally
expensive and difficult to implement in practice. As a consequence, there are
approximations that result in fuzzy numbers of the same type as the operands
[16]. Thus, they do not provide the right-shaped resulting number. Moreover,
if the operands are of two different types, the approximation is not
applicable.

_Contributions._ Our first contribution is a clear, mathematically rigorous
definition of the fuzzy unreliability metric. The definition is valid for
general fuzzy numbers, rather than specific types such as triangular numbers.
The definition follows Zadeh’s extension principle [19], a general approach to
apply functions and arithmetic operations on sets to fuzzy numbers.

We then propose a bottom-up algorithm for calculating fuzzy unreliability
metric for tree-structured FTs. During the calculation procedure, fuzzy
attribution is discretised horizontally and saved as $\alpha$-cut series.
Arithmetic operations are performed on these $\alpha$-cut series representing
fuzzy numbers. Output of the algorithm is an $\alpha$-cut series approximation
of a fuzzy number. This approximate computational technique works for fuzzy
numbers that can be expressed as $\alpha$-cut interval and is applicable when
performing operations on fuzzy numbers of different types.

Summarized our contributions are:

  1. 1.

A rigorous definition of fuzzy unreliability metric;

  2. 2.

A bottom-up algorithm for computing fuzzy unreliability in tree-like FTs based
on $\alpha$-cuts;

  3. 3.

A counter example showing why a straight forward extension of BDD-based
methods for reliability calculations does not work for fuzzy fault trees;

  4. 4.

An implementation of the algorithm and its illustration on two benchmark fault
trees.

##  2 Related work

Fuzzy fault tree analysis has been studied in a wide body of literature and
reviewed in many works[11, 12]. When vagueness arise, uncertain parameters can
be described as fuzzy numbers. Each BEs is then equiped with a fuzzy
number/possibility. Fuzzy set theory was first introduced in fault tree
analysis by Tanaka et al.[16]. The main idea of using fuzzy theory is to
express the ambiguous parameters in triangular, or trapezoidal, or Left-Right
type fuzzy numbers, then calculate the fuzzy probability of the top event
based on Zadeh’s principle as in [16], or using $\alpha$-cut fuzzy operators
as in[8], or applying extended algebraic operations on the L-R type fuzzy
number as in[14].

In general, it is challenging to calculate the fuzzy probability of a top
event. This is because of the multiplication of fuzzy numbers. Nonlinear
programming of the operation is infeasible to implement in practice [17].
Multiplication of trapezoidal or triangular numbers is often done using an
estimation [16] which results in a fuzzy number of the same type as the
operands. An approximate analytical algorithm for calculating fuzzy operations
is L-R representation[6]. Also, there is an approximate numerical approach
[13] that applies the extension principle to the discretised fuzzy numbers
resulting in the discrete extended product. This approach, however, lacks
generality because the extended operation may not result in convex numbers.
Using $\alpha$-cut representation and interval arithmetic, DSW algorithm [17]
provides an efficient way to calculate fuzzy operations. We incorporate this
method into our BU-algorithm.

##  3 Preliminary Theory

Fuzzy set theory was first introduced by L.A. Zadeh [19] in 1965. Since then
it has been used to deal with vague problems. We consider fuzzy elements that
can have a range of possible values. For an element $x$ of a set $X$, the
extent to which $\mathsf{x}$ can be equal to $x$ is expressed by the
_membership degree_ of $x$ in $\mathsf{x}$, which is a value
$\mathsf{x}[x]\in[0,1]$. By that, $\mathsf{x}[x]=1$ denotes full membership,
while $\mathsf{x}[x]=0$ denotes no membership.

For instance, the failure probability of a BE may be given as a real number,
e.g. $x=0.3\in\mathbb{R}$; but often the exact value is not known precisely,
and can be somewhere around $0.3$. This can be represented by a fuzzy number
$\mathsf{x}\colon\mathbb{R}\rightarrow[0,1]$ which is $0$ everywhere except
close to $0.3$, and which has a maximum at $0.3$ (see Fig. 1).

(a)

(b)

(c)

Figure 1:  (a) A non-fuzzy, ‘crisp’ element $x=0.3$, (b) a fuzzy element
$\mathsf{x}$, expressing uncertainty around 0.3, and (c) a trapezoidal fuzzy
number $\mathsf{trap}_{a,b,c,d}$.

###### Definition 1

Let $X$ be a set. A _fuzzy element_ of $X$ is a function $\mathsf{x}\colon
X\rightarrow[0,1]$. The set of all fuzzy elements of $X$ is denoted
$\mathbf{F}(X):=\\{\mathsf{x}\ |\ \mathsf{x}\colon X\rightarrow[0,1]\\}$.

Our definition of fuzzy element is very general. Many works in the literature
restrict the form of the function $\mathsf{x}\colon 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 [7].

###### Example 1

For real numbers $a\leq b\leq c\leq d$, the _trapezoidal fuzzy number_
$\mathsf{trap}_{a,b,c,d}\in\mathbf{F}(\mathbb{R})$ is defined as (see Fig.
1(c)):

$\displaystyle\mathsf{trap}_{a,b,c,d}[x]$
$\displaystyle=\begin{cases}\tfrac{x-a}{b-a},&\textrm{if }a<x\leq b,\\\
1,&\textrm{if }b<x<c,\\\ \tfrac{d-x}{d-c},&\textrm{if }c\leq x<d,\\\
0,&\text{otherwise}.\end{cases}$

Triangular fuzzy numbers are special cases of trapezoidal numbers, with $b=c$.
Thus, $\mathsf{tri}_{a,b,d}=\mathsf{trap}_{a,b,b,d}$. Gaussian fuzzy numbers
are characterized by their mean $m$ and standard deviation $d$:

$\mathsf{gauss}_{m,d}[x]=\exp{(\tfrac{-(x-m)^{2}}{2d^{2}})}$

For convenience, we abbreviate $\mathsf{x}$ via a list of membership values
$x\mapsto\mathsf{x}[x]$, omitting $x$ for which $\mathsf{x}[x]=0$. For
example, $\mathsf{x}=\\{1\mapsto 0.7,2\mapsto 0.5\\}\in\mathbf{F}(\mathbb{Z})$
denotes the fuzzy number with $\mathsf{x}[1]=0.7$, $\mathsf{x}[2]=0.5$ if
$x=2$ and $\mathsf{x}[x]=0$ everywhere else.

##### Zadeh’s extension principle.

They key technique to perform arithmetic operations on fuzzy numbers is based
on Zadeh’s extension principle [7, 19]. To understand this principle, consider
a function $f:X\to Y$. Zadeh’s extention principle lifts $f$ to a function
over fuzzy numbers $\widetilde{f}\colon\mathbf{F}(X)\rightarrow\mathbf{F}(Y)$.
First assume the special case where $f$ is injective and $f(x)=y$. Then we set
$\widetilde{f}(\mathsf{x})[y]=\mathsf{x}[y]$, since the trust we have that for
$f(x)$ to be equal to $y$ is the same the trust we have for $x$ to be $y$. For
$y\in Y$ without an inverse, i.e. with $f^{-1}(y)=\emptyset$, we set
$\widetilde{f}(\mathsf{x})[y]=0$, since $f$ can never be equal to $y$. Now, if
$f$ is not injective, then there can be multiple values $x$ with $f(x)=y$.
Each of these values $x\in f^{-1}(y)$ have been assigned a fuzzy value
$\mathsf{x}$. Zadeh’s extension principle takes the best value from $x\in
f^{-1}(y)$, i.e. for which $\mathsf{x}[x]$ is maximal. For functions of
multiple arguments this works exactly the same.

######  Definition 2 (Zadeh’s Extension Principle)

Let $f$ be a multiargument function $f:X_{1}\times X_{2}\times\dots\times
X_{n}\to Y$. The _Zadeh extension_ of $f$ is the function
$\widetilde{f}\colon\mathbf{F}(X_{1})\times\ldots\times\mathbf{F}(X_{n})\rightarrow\mathbf{F}(Y)$
defined as:

$\widetilde{f}(\mathsf{x}_{1},\ldots,\mathsf{x}_{n})[y]=\begin{cases}\underset{\begin{subarray}{c}(x_{1},x_{2},\dots,x_{n})\in\prod_{i}X_{i}\colon\\\
f(x_{1},x_{2},\dots,x_{n})=y\end{subarray}}{\sup}\min\limits_{i=1,\dots,n}\
\mathsf{x}_{i}[x_{i}],&f^{-1}(y)\neq\emptyset,\\\
0&f^{-1}(y)=\emptyset.\end{cases}$

Addition and subtraction operations performed on specific fuzzy numbers can
have straightforward formulations. E.g., for two trapezoidal fuzzy numbers we
have

$\displaystyle\mathsf{trap}_{a_{1},a_{2},a_{3},a_{4}}\ \widetilde{+}\
\mathsf{trap}_{b_{1},b_{2},b_{3},b_{4}}$
$\displaystyle=\mathsf{trap}_{a_{1}+b_{1},a_{2}+b_{2},a_{3}+b_{3},a_{4}+b_{4}},$
$\displaystyle\mathsf{trap}_{a_{1},a_{2},a_{3},a_{4}}\ \widetilde{-}\
\mathsf{trap}_{b_{1},b_{2},b_{3},b_{4}}$
$\displaystyle=\mathsf{trap}_{a_{1}-b_{4},a_{2}-b_{3},a_{3}-b_{2},a_{4}-b_{1}}.$

The key problem with fuzzy operations is that for many common operations,
Zadeh’s extension principle destroys the shape of their operant. E.g. For
example, due to their non-linearity, the quotient of two trapezoidal fuzzy
numbers is not trapezoidal; the same is true for their product.

Some works approximate operations by a fuzzy number of the same type as the
operations. Such approximations yield outcomes that are easy to visualize, but
are not exact [3].

#####  $\alpha$-cuts

Another way to perform arithmetic operations on fuzzy number is via their
$\alpha$-cuts [3]. An $\alpha$-cut of $\mathsf{x}^{(\alpha)}$ of a fuzzy
number $\mathsf{x}\in\mathbf{F}(X)$ yields all values in $x$ with
$\mathsf{x}[x]\geq\alpha$, i.e. whose trust is at least $\alpha$.

###### Definition 3

Let $\mathsf{x}\in\mathbf{F}(X)$ and $\alpha\in[0,1]$. An $\alpha$-cut or
$\alpha$-level $\mathsf{x}^{(\alpha)}$ of $\mathsf{x}$ equals

$\mathsf{x}^{(\alpha)}=\\{x\in X\ |\ \mathsf{x}[x]\geq\alpha\\}.$ (1)

Figure 2: $\alpha-$cut of trapezoidal fuzzy number $\mathsf{trap}_{a,b,c,d}$.

###### Example 2

The $\alpha$-cuts of trapezoidal and guassian fuzzy number are given by:

$\displaystyle\mathsf{trap}^{(\alpha)}_{a,b,c,d}=[(b-a)\alpha+a,\
d-(d-c)\alpha]$
$\displaystyle\mathsf{gauss}_{m,d}^{(\alpha)}=\bigl{[}m-d\sqrt{-2\ln{\alpha}},\
m+d\sqrt{-2\ln{\alpha}}\ \bigr{]}$

The elements of the set of $\alpha$-cut lie in the red interval shown in Fig.
2

Suppose we have a fuzzy number $\mathsf{x}$ that is (piecewise) continuous and
convex — i.e., for all $x,y\in\mathbb{R}$ and $\lambda\in\mathbb{R}$ we have
$\mathsf{x}[\lambda x+(1-\lambda)y]\geq\min\\{\mathsf{x}[x],\mathsf{x}[y]\\}$.
For such a fuzzy number each $\alpha$-cut $\mathsf{x}^{(\alpha)}$ is a closed
interval $[a^{(\alpha)}_{1},a^{(\alpha)}_{2}]$. Furthermore, $\mathsf{x}$ is
completely determined by this collection of intervals, as $\alpha$ ranges over
$[0,1]$. This means that we have two ways of describing such a fuzzy number:
either by the membership function
$\mathsf{x}\colon\mathbb{R}\rightarrow[0,1]$, or by the two functions
$a_{1},a_{2}\colon[0,1]\rightarrow\mathbb{R}$, that assign to $\alpha$ the
endpoints of the $\alpha$-cut of $\mathsf{x}$. The advantage of the second
viewpoint is that Zadeh extensions become significantly easier to compute: it
turns out that Zadeh extensions of arithmetic operations become interval
operations on the $\alpha$-cuts. These operations are defined as follows.

###### Definition 4

(Interval operations[1, 2]) Let $[a_{1},a_{2}]$ and $[b_{1},b_{2}]$ be two
closed intervals on the real line. The arithmetic operations between intervals
is defined by

  1. 1.

$[a_{1},a_{2}]+[b_{1},b_{2}]=[a_{1}+b_{1},a_{2}+b_{2}]$

  2. 2.

$[a_{1},a_{2}]-[b_{1},b_{2}]=[a_{1}-b_{2},a_{2}-b_{1}]$

  3. 3.

$[a_{1},a_{2}]\cdot[b_{1},b_{2}]=[\min\\{a_{1}b_{1},a_{1}b_{2},a_{2}b_{1},a_{2}b_{2}\\},\max\\{a_{1}b_{1},a_{1}b_{2},a_{2}b_{1},a_{2}b_{2}\\}]$

The following result shows that we can use these interval operations to
calculate Zadeh extensions, by describing the resulting fuzzy number in terms
of its $\alpha$-cuts. Note that many existing fuzzy number types such as
triangular, trapezoidal, Gaussian, satisfy its assumptions.

###### Lemma 1

Let $\mathsf{x},\mathsf{y}$ be two piecewise continuous, convex fuzzy numbers,
and let $\diamond$ be an arithmetic operation in $\\{+,-,\ \cdot\\}$. Then the
$\alpha$-cuts of the fuzzy number $\mathsf{x}\widetilde{\diamond}\mathsf{y}$
are given by

$(\mathsf{x}\ \widetilde{\diamond}\ \mathsf{y})^{(\alpha)}=\\{x\diamond
y|x\in\mathsf{x}^{(\alpha)},\
y\in\mathsf{x}^{(\alpha)}\\}=\mathsf{x}^{(\alpha)}\diamond\mathsf{y}^{(\alpha)},\quad\forall\alpha\in[0,1]$

###### Example 3

Consider two triangular fuzzy numbers $\mathsf{tri}_{1,2,3}$, and
$\mathsf{tri}_{3,4,6}$. We wish to calculate addition, subtraction, and
multiplication of the two fuzzy numbers using their $\alpha$-cuts. We have the
equation describing $\alpha$-cuts of $\mathsf{tri}_{1,2,3}$, and
$\mathsf{tri}_{3,4,6}$, for any $\alpha\in[0,1]$:
$\mathsf{tri}^{(\alpha)}_{1,2,3}=[1+\alpha,3-\alpha]$, and
$\mathsf{tri}^{(\alpha)}_{3,4,6}=[3+\alpha,6-2\alpha]$

  * •

$(\mathsf{tri}_{1,2,3}\ \widetilde{+}\
\mathsf{tri}_{3,4,6})^{(\alpha)}=[4+2\alpha,9-3\alpha]$

  * •

$(\mathsf{tri}_{1,2,3}\ \widetilde{-}\
\mathsf{tri}_{3,4,6})^{(\alpha)}=[3\alpha-5,-2\alpha]$

Because the functions are linear, substituting $\alpha=0$ and $\alpha=1$
provides parameters of the resulting triangular membership functions of the
sum and subtraction: $\mathsf{tri}_{4,6,9}$, and $\mathsf{tri}_{-5,-2,0}$.
Multiplication of fuzzy numbers requires more comments. We need to search for
the minimum and maximum among functions:
$\alpha^{2}+4\alpha+3,-2\alpha^{2}+4\alpha+6,-\alpha^{2}+9,2\alpha^{2}-12\alpha+18$.
Analysing the values of these functions for $\alpha\in[0,1]$, the following
interval is obtained

  * •

$(\mathsf{tri}_{1,2,3}\ \widetilde{\cdot}\
\mathsf{tri}_{3,4,6})^{(\alpha)}=[\alpha^{2}+4\alpha+3,2\alpha^{2}-12\alpha+18]$

The functions are not linear, thus replacing $\alpha$ with 0 and 1 provides
just the values of $x$, for which the membership function takes values 0 and 1
e.g., $(\mathsf{tri}_{1,2,3}\ \widetilde{\cdot}\ \mathsf{tri}_{3,4,6})[3]=0$,
$(\mathsf{tri}_{1,2,3}\ \widetilde{\cdot}\ \mathsf{tri}_{3,4,6})[18]=0$ and
$(\mathsf{tri}_{1,2,3}\ \widetilde{\cdot}\ \mathsf{tri}_{3,4,6})[8]=1$. To
determine the resulting multiplication fuzzy number, we solve two nonlinear
functions: $\alpha^{2}+4\alpha+3=x$, and $2\alpha^{2}-12\alpha+18=x$. The
solution are $\alpha_{1,2}=-2\pm\sqrt{1+x}$ for the first equation, and
$\alpha_{1,2}=\frac{6\pm\sqrt{2x}}{2}$ for the second. In the case of the
first equation, we choose $-2+\sqrt{1+x}$ as the membership function for
$x\in[3,8]$ because it provides values in the range $[0,1]$. For the second
case, the function $\frac{6-\sqrt{2x}}{2}$ provides values in ranges $[0,1]$
for $x\in[8,18]$. Finally the multiplication is described by:

$\displaystyle(\mathsf{tri}_{1,2,3}\ \widetilde{\cdot}\
\mathsf{tri}_{3,4,6})[x]$
$\displaystyle=\begin{cases}-2+\sqrt{1+x},&\textrm{if }3\leq x\leq 8,\\\
\tfrac{6-\sqrt{2x}}{2},&\textrm{if }8<x\leq 18,\\\
0,&\text{otherwise}.\end{cases}$ (2)

##  4 Fault trees

In this section, we briefly review the terminology of (static) fault trees. A
more comprehensive overview can be found, e.g., at [12].

###### Definition 5

_[10]_ A _fault tree_ is a tuple $T=(V,E,t)$, where $(V,E)$ is a rooted
directed acyclic graph, and $t$ is a map $t\colon
V\rightarrow\\{\mathtt{BE},\mathtt{OR},\mathtt{AND}\\}$ such that
$t(v)=\mathtt{BE}$ if and only if $v$ is a leaf for all $v\in V$.

The root of $T$ is denoted $R_{T}$. For a node $v\in V$, we let $ch(v)$ be the
set of all children of $v$. The set of BEs (basic events) is denoted
$\text{BE}_{T}$.

A _safety event_ is a set of BEs that occurs simultaneously. We denote such an
event by its corresponding binary vector
$\vec{f}\in\mathbb{B}^{\text{BE}_{T}}$. The extent to which a safety event
leads to overall system failure is determined by the _structure function_ :
for a node $v\in V$ and a safety event $\vec{f}$, the structure function
$S_{T}(v,\vec{f})$ is a Boolean stating whether $\vec{f}$ propagates through
$v$.

###### Definition 6

Let $T$ be a FT. The _structure function_ $S_{T}\colon
V\times\mathbb{B}^{\text{BE}_{T}}\to\mathbb{B}$ of $T$ is defined, for a node
$v\in V$ and a safety event $\vec{f}\in\mathbb{B}^{\text{BE}_{T}}$, by

$\displaystyle S_{T}(v,\vec{f})=$ $\displaystyle\begin{cases}\bigvee_{w\in
ch(v)}S_{T}(w,\vec{f})&\parbox{55.0pt}{if\leavevmode\nobreak\
$t(v)=\mathtt{OR}$,}\\\ \bigwedge_{w\in
ch(v)}S_{T}(w,\vec{f})&\parbox{55.0pt}{if\leavevmode\nobreak\
$t(v)=\mathtt{AND}$},\\\ f_{v}&\parbox{55.0pt}{if\leavevmode\nobreak\
$t(v)=\mathtt{BE}$.}\end{cases}$ (3)

A safety event $\vec{f}$ that reaches the root $R_{T}$ i.e.
$S_{T}(R_{T},\vec{f})=1$ is called a _cut set_. The set of all cut sets of $T$
is denoted $\mathcal{C}_{T}$.

###  4.1 Fault tree reliability analysis

(a)

(b)

Figure 3: A fault tree for a road trip (a), and its BDD representation (b).
The road trip fails if both phone and car fail; car fails if either engine or
battery fails.

Fault trees are used for quantitative probability analysis as follows: suppose
each BE $v$ is assigned a probability $p(v)$, the unreliability of the system
is the probability that the system as a whole fails. This is the probability
that a random safety event $\vec{F}$ (distributed according to the BE
probabilities) propagates to the root.

###### Definition 7

Let $T=(V,E,t,p)$ be a FT. The _unreliability_ of $T$ is defined as

$\displaystyle U(T)$
$\displaystyle=\sum_{\vec{f}\in\mathcal{C}_{T}}\prod_{v=1}^{n}p(v)^{f_{v}}\cdot\bigl{(}1-p(v)\bigr{)}^{(1-f_{v})}.$
(4)

###### Example 4

Consider the FT from Fig.3(a). Let $p(a)=0.8,p(b)=0.1$, and $p(c)=0.4$, then
$\vec{f}\in\mathbb{B}^{\text{BE}_{T}}$ is written as $f_{a}f_{b}f_{c}$. The
cut set is represented as $\mathcal{C}_{T}=\\{111,\ 110,\ 101\\}$, and thus
the unreliability is

$\displaystyle U(T)$ $\displaystyle=0.8\cdot 0.1\cdot 0.4+0.8\cdot 0.1\cdot
0.6+0.8\cdot 0.9\cdot 0.4=0.368.$

In this definition, the failure probabilities of the BEs are assumed to be
independent. This is a standard assumption; any dependence between the BEs is
meant to be captured by the FT modeling.

####  4.1.1 Bottom-up method

Calculation of (4) directly is difficult (in fact, NP-hard [9]) because
finding the entire set $\mathcal{C}_{T}$ and calculating each element’s
probability is copmutationally infeasible for large FTs. Unreliability can
instead be computed via a bottom-up method, assigning a probability $p_{v}$ to
each node. For a node $v$ with children $v_{1},\ldots,v_{n}$, we have

$\displaystyle p_{v}=$
$\displaystyle\begin{cases}1-\prod_{i=1}^{n}(1-p_{v_{i}})&\parbox{55.0pt}{if\leavevmode\nobreak\
$t(v)=\mathtt{OR}$,}\\\
\prod_{i=1}^{n}p_{v_{i}}&\parbox{55.0pt}{if\leavevmode\nobreak\
$t(v)=\mathtt{AND}$}.\end{cases}$ (5)

Then $U(T)$ is calculated as $p_{R_{T}}$.

###### Example 5

Consider the FT from Fig.3(a). Let $p(a)=0.8,p(b)=0.1$, and $p(c)=0.4$. The
top failure probability derived using probability laws is

$p_{R_{T}}=p_{a}\cdot\bigl{(}1-(1-p_{b})\cdot(1-p_{c})\bigr{)}=0.8\cdot\bigl{(}1-(1-0.1)\cdot(1-0.4)\bigr{)}=0.368.$

The bottom-up algorithm is fast, but only works when $T$ is a tree. The reason
is that the probability laws in (6) only hold when the $p_{v_{i}}$ are
independent probabilities, which will not generally be true if the $v_{i}$
share children. For DAG-structured FTs, a different approach is used.

####  4.1.2 Calculation through BDDs

Another approach to unreliability calculation involves transforming the
structure function of an AT to a binary decision diagram (BDD). BDD are
compact representations of Boolean functions; see Fig. 3(b) for an example. To
evaluate a safety event $\vec{f}$, start from the root of the BDD, and at a
node labeled $v$, take the solid line if $f_{v}=1$, and the dashed line if
$f_{v}=0$. The label of the reached leaf is the value of
$S_{T}(R_{T},\vec{f})$.

Now $U(T)$ is the probability that one ends up in leaf 1, if we assign
probability $p(v)$ to each solid line and $1-p(v)$ to each dashed line from a
BDD node labeled $v$. This can be calculated quickly using a bottom-up
algorithm on the BDD, and this works even when the original FT is DAG-shaped.
A shortcoming of the method is the worst-case-exponential size of the BDD. The
size of BDD is strongly affected by the order of the variable, meanwhile
finding the order that minimizes BDD size is NP-hard.

##  5 Fuzzy unreliability

The concept of failure possibility arises in unreliability analysis when the
failure probabilities are not exactly known. Instead of having a fixed real
value, the failure possibility can be defined by a fuzzy number/ element on
interval $[0,1]$, with any shape of membership function. The failure
possibility of a basic event $i$ denoted as $\mathsf{p}_{i}$. We first give an
example of how this affects unreliability calculation, before giving the
general definition.

###### Example 6

Consider the road trip FT $T$ from Fig.3(a). Its unreliability function
$U_{T}\colon[0,1]^{3}\rightarrow[0,1]$ is given by

$\displaystyle U_{T}(p_{a},p_{b},p_{c})$
$\displaystyle=p_{a}p_{b}p_{c}+p_{a}(1-p_{b})p_{c}+p_{a}p_{b}(1-p_{c})$
$\displaystyle=p_{a}p_{c}+p_{a}p_{b}-p_{a}p_{b}p_{c}.$

Now suppose $T$ has failure possibilities
$\vec{\mathsf{p}}=(\mathsf{p}_{a},\mathsf{p}_{b},\mathsf{p}_{c})$ given by
$\mathsf{p}_{a}=\\{0.5\mapsto 0.7,0.8\mapsto 1\\}$,
$\mathsf{p}_{b}=\\{0.1\mapsto 1\\}$, $\mathsf{p}_{c}=\\{0.4\mapsto 1\\}$; that
is, $b,c$ have crisp probability values, and $a$ either takes probability
$0.5$ or $0.8$ with possibility $0.7$ and $0.1$, respectively. The
unreliability of $T$ is then defined to be
$\widetilde{U}_{T}(\mathsf{p}_{a},\mathsf{p}_{b},\mathsf{p}_{c})$, i.e., the
Zadeh extension of $U_{T}$, applied to $\vec{\mathsf{p}}$. Using Def.2, the
confidence that this fuzzy unreliability value equal to a number $y\in[0,1]$
is equal to

$\widetilde{U}_{T}(\vec{\mathsf{p}})[y]=\sup_{\begin{subarray}{c}p_{a},p_{b},p_{c}\in[0,1]\colon\\\
p_{a}p_{c}+p_{a}p_{b}-p_{a}p_{b}p_{c}=y\end{subarray}}\min\\{\mathsf{p}_{a}[p_{a}],\mathsf{p}_{b}[p_{b}],\mathsf{p}_{c}[p_{c}]\\}$

We notice that $b$ has one single probability value $p_{b}=0.1$ with
$\mathsf{p}_{b}[p_{b}]\neq 0$, and $c$ has only $p_{c}=0.4$ with
$\mathsf{p}_{c}[p_{c}]\neq 0$. Substituting those probabilities and their
confidences to the expression above, then

$\displaystyle\sup_{\begin{subarray}{c}p_{a}:\\\
0.4p_{a}+0.1p_{a}-0.04p_{a}=y\end{subarray}}\min\bigl{(}\mathsf{p}_{a}[p_{a}],1,1\bigr{)}$
$\displaystyle=\begin{cases}1,&\textrm{ if $y=0.368$},\\\ 0.7,&\textrm{ if
$y=0.23$},\\\ 0,&\textrm{ otherwise},\end{cases}$

so $\widetilde{U}_{T}(\vec{\mathsf{p}})=\\{0.23\mapsto 0.7,0.368\mapsto 1\\}$.

###### Definition 8

Let $T$ be a FT.

  1. 1.

A _fuzzy attribution_ is an element $\vec{\mathsf{p}}$ of
$\mathbf{F}([0,1])^{\mathrm{BE}_{T}}$.

  2. 2.

The _fuzzy unreliability value_ of $T$ given $\vec{\mathsf{p}}$ is defined as
$\widetilde{U}_{T}(\vec{\mathsf{p}})$, where
$\widetilde{U}_{T}\colon\mathbf{F}([0,1])^{\mathrm{BAS}_{T}}\rightarrow\mathbf{F}([0,1])$
is the Zadeh extension of the function $U_{T}$ from Definition 7.

More concretely, $\widetilde{U}_{T}(\vec{\mathsf{p}})$ is the fuzzy element of
$[0,1]$ defined, for $y\in[0,1]$, by

$\displaystyle\widetilde{U}_{T}(\vec{\mathsf{p}})[y]$
$\displaystyle=\sup_{\begin{subarray}{c}\vec{p}\in[0,1]^{\mathrm{BE}_{T}}\colon\\\
U_{T}(\vec{p})=y\end{subarray}}\min_{v\in\mathrm{BE}_{T}}\mathsf{p}_{v}[p_{v}].$

##  6 Calculation of fuzzy unreliability

###  6.1 Tree-structured FTs

In general, $\tilde{U}_{T}(\vec{p})$ is difficult to compute. However, when
$T$ is tree-structured, it can be found using a bottom-up algorithm. This
algorithm is inspired by the BU algorithm for crisp FT probabilities. When $T$
is a tree, the children of a node $v$ do not have any descendants in common,
and as such are independent events. This means that their failure
probabilities $\mathsf{p}_{v}$ can be computed via

$\mathsf{p}_{v}=\begin{cases}1-\widetilde{\prod}_{w\in
ch(v)}(1-\mathsf{p}_{w})&\parbox{55.0pt}{if\leavevmode\nobreak\
$t(v)=\mathtt{OR}$,}\\\ \widetilde{\prod}_{w\in
ch(v)}\mathsf{p}_{w}&\parbox{55.0pt}{if\leavevmode\nobreak\
$t(v)=\mathtt{AND}$}.\end{cases}$ (6)

The following result shows the validity of this approach. It is proven
analogously to a similar result for attack trees in [5].

###### Theorem 6.1

Let $T$ be a tree-structured FT, and let
$\vec{\mathsf{p}}\in\mathbb{F}([0,1])^{\text{BE}_{T}}$ be a vector of fuzzy
probabilities. Then $\mathsf{p}_{R_{T}}=\widetilde{U}_{T}(\vec{\mathsf{p}})$.

###### Example 7

We apply the algorithm to Ex. 6. We calculate the $\mathsf{p}_{v}$ as follows:

$\displaystyle\mathsf{p}_{a}$ $\displaystyle=\mathsf{p}_{a}=\\{0.5\mapsto
0.7,0.8\mapsto 1\\},$ $\displaystyle\mathsf{p}_{b}$
$\displaystyle=\mathsf{p}_{b}=\\{0.1\mapsto 1\\},$
$\displaystyle\mathsf{p}_{c}$ $\displaystyle=\mathsf{p}_{c}=\\{0.4\mapsto
1\\},$ $\displaystyle\mathsf{p}_{\texttt{OR}(b,c)}$
$\displaystyle=1-(1-\mathsf{p}_{b})\tilde{\cdot}(1-\mathsf{p}_{c})$
$\displaystyle=1-\\{0.9\mapsto 1\\}\tilde{\cdot}\\{0.6\mapsto
1\\}=\\{0.46\mapsto 1\\},$ $\displaystyle\mathsf{p}_{R_{T}}$
$\displaystyle=\mathsf{p}_{a}\tilde{\cdot}\mathsf{p}_{\texttt{OR}(b,c)}$
$\displaystyle=\\{0.5\mapsto 0.7,0.8\mapsto 1\\}\tilde{\cdot}\\{0.46\mapsto
1\\}=\\{0.23\mapsto 0.7,0.368\mapsto 1\\}.$

Thus we indeed retrieve $\tilde{U}_{T}(T,\vec{\mathsf{p}})=\\{0.23\mapsto
0.7,0.368\mapsto 1\\}$.

###  6.2 Efficient computation via $\alpha$-cuts

While the BU approach calculates $\tilde{U}_{T}(\vec{\mathsf{p}})$ correctly,
it can be difficult to use in practice, due to the fact that the objects
$\mathsf{p}_{v}$ it operates on are functions $[0,1]\rightarrow[0,1]$. Storing
such a function in theory would take an infinite amount of space. On the other
hand, if one were to approximate this by storing $\mathsf{p}_{v}[x]$ for only
finitely many values of $x$, it is not clear how Zadeh-extended operators such
as $\tilde{\cdot}$ are calculated.

To make our algorithm applicable in practice, we choose instead to use
$\alpha$-cuts, as we have seen that this allows for efficient computation.
First, we choose the (finite) set of $A$ of $\alpha$ we are going to use: we
pick the number of cuts $n_{\text{cuts}}$ and take
$A=\left\\{\tfrac{1}{n_{\text{cuts}}},\tfrac{2}{n_{\text{cuts}}},\cdots,1\right\\}$.
Then for each BE $v$, we store $\mathsf{p}_{v}$ as a $n_{\text{cuts}}\times
3$-array whose rows are of the form $(\alpha,a_{1}(\alpha),a_{2}(\alpha))$;
the interpretation is that
$\mathsf{p}_{v}^{(\alpha)}=[a_{1}(\alpha),a_{2}(\alpha)]$. Thus we store each
fuzzy number as a set of $n_{\text{cuts}}$ $\alpha$-cuts. The fuzzy
multiplication $\tilde{\cdot}$ of (6) is now performed level-wise using Lemma
1. Thus at each node we need to make $\mathcal{O}(n_{\text{cuts}})$ crisp
arithmetic operations, for a total time complexity of
$\mathcal{O}(n_{\text{cuts}}\cdot|V|)$.

###  6.3 DAG-structured FTs

When $T$ is not tree-structured but DAG-structured, the BU approach no longer
computes $\tilde{U}_{T}(\vec{\mathsf{p}})$ correctly, because the
probabilities of the children of a node may no longer be independent. In fact,
this is already true for crisp probability values [12], so it is no surprise
that the same holds in the fuzzy setting.

For crisp probabilities the BDD method of Section 4 exists . However, this
also does not work in the fuzzy setting. The reason is that the Zadeh-extended
arithmetic operators $\tilde{+}$ and $\tilde{\cdot}$ no longer satisfy
distributivity, which is crucial in the proof of the BDD method. Thus finding
a general algorithm for DAG FTs is considerably more complicated, and we leave
this as an open problem.

Figure 4: A DAG FT

Figure 5: BDD calculation

###### Example 8

Consider the BDD shown in Fig.5, with variable order $u<v<w$, and
$\mathsf{p}_{u}=\mathsf{p}_{w}=\\{0.5\mapsto 1\\}$ and
$\mathsf{p}_{v}=\\{0\mapsto 1,1\mapsto 1\\}$. We label $v$ as $v_{1}$ and
$v_{2}$ for distinction in the calculation. Let fuzzy attribution as in the
previous example. The fuzzy unreliability of top event is

$\displaystyle\text{BDD}(v)$
$\displaystyle=0.5\cdot\text{BDD}(v_{1})\widetilde{+}0.5\cdot\text{BDD}(v_{2})$
$\displaystyle=0.5\cdot\\{0\mapsto 1,1\mapsto
1\\}\widetilde{+}0.5\cdot\\{0.5\mapsto 1,1\mapsto 1\\}$
$\displaystyle=\\{0\mapsto 1,0.5\mapsto 1\\}\widetilde{+}\\{0.25\mapsto
1,0.5\mapsto 1\\}$ $\displaystyle=\\{0.25\mapsto 1,0.5\mapsto 1,0.75\mapsto
1,1\mapsto 1\\}.$

On the other hand, similar to Ex. 6 one can calculate
$\tilde{U}_{T}(\vec{\mathsf{p}})=\\{0.25\mapsto 1,1\mapsto 1\\}$. This shows
that the BDD method does not work for fuzzy unreliability.

##  7 Experiments

We execute experiments to calculate top event possibility using
$\widetilde{BU}$ algorithm. The algorithm is implemented in Python. As we
perform computation with fuzzy attribution the system unreliability will be a
fuzzy element. We use two benchmark FTs:

  1. 1.

Container Seal Design (CSD)[15] with 6 BEs and 4 ($\mathtt{AND,OR}$) gates.

  2. 2.

Liquid Storage Tank Failure (LSTF)[18] with 35 BEs and 15 ($\mathtt{AND,OR}$)
gates.

We take the crisp probabilities from [15] and [18]. In the case of [15], six
BEs $e_{1},\dots,e_{6}$ have crisp probabilities
$0.1,10^{-5},10^{-3},10^{-3},10^{-3},10^{-3}$, respectively. In case we want
to fuzzify $p_{i}$ into a triangular possibility, we assign
$\mathsf{p}_{i}=\mathsf{tri}_{0.2\cdot p_{i},p_{i},1.8\cdot p_{i}}$. If we
want trapezoidal possibility or Gaussian possibility, we assign
$\mathsf{p}_{i}=\mathsf{trap}_{0.2\cdot p_{i},0.9\cdot p_{i},1.1\cdot
p_{i},1.8\cdot p_{i}}$, or $\mathsf{p}_{i}=\mathsf{gauss}_{p_{i},0.4\cdot
p_{i}}$, respectively.

For the experiments, we have fuzzified all crisp BE probability values
obtained from the two benchmarks. We use triangular possibility, or
trapezoidal possibility, or Gaussian possibility or combination of those
three. When combination of the three types arises, fuzzy possibility type for
each BEs is assigned as in the table in appendix. BEs possibilities will be
horizontally discretised into $n_{cuts}=100$ $\alpha-$cuts series within the
BU algorithm process.

(a) CSD

(b) LSTF

Figure 6: System fuzzy unreliabilities of CSD and LSTF FT models

Figure 6 displays the resulting fuzzy unreliabilities of the systems CSD and
LSTF, respectively. In each subfigure, we plot the crisp unreliability
obtained from crisp BEs values (crisp unreliability), fuzzy unreliability
obtained from fuzzy BEs triangular possibility ($\mathsf{u\\_tri}$),
trapezoidal possibility ($\mathsf{u\\_trap}$), Gaussian possibility
($\mathsf{u\\_gauss}$), and the their combination ($\mathsf{u\\_mix}$). We
observe that the system unreliability is not the same type as the operands BEs
possibilities. This is obvious since calculation of unreliability requires
fuzzy multiplications which is a nonlinear operation. The method overcomes the
complexity of performing exact fuzzy multiplication [16] or using nonlinear
programming [17]. In addition, it provides more precise solution than the
product estimations of fuzzy numbers and the conventional discretisation
approach [13].

##  8 Conclusion and future work

In this paper, we define a mathematical formulation for deriving fuzzy
unreliability values for FTs. The definition is explicit and generic for
general fuzzy attribution. We also introduce an efficient algorithm to
calculate FT fuzzy unreliability metric. The algorithm works for tree-like
structure models with any type of fuzzy attribute that can be expressed as
$\alpha$-cut intervals. Experiments on practical models show that the
algorithm preserves the nonlinear property of the resulting fuzzy number.

In the future, we want to develop an algorithm for fuzzy unreliability
computation on DAG FTs. Another avenue for future research is to create an
algorithm for probabilistic FT analysis in continuous time where each BE is
assigned a continuous probability distribution.

## References

  * [1] Alefeld, G., Mayer, G.: Interval analysis: theory and applications. Journal of Computational and Applied Mathematics 121(1), 421–464 (2000)
  * [2] de Barros, L.C., Bassanezi, R.C., Lodwick, W.A.: The Extension Principle of Zadeh and Fuzzy Numbers, pp. 23–41. Springer, Berlin, Heidelberg (2017)
  * [3] Basiura, B., Duda, J., Gaweł, B., Opiła, J., Pełech-Pilichowski, T., Rębiasz, B., Skalna, I.: Fuzzy Numbers, pp. 1–26. Springer Inter. Publishing, Cham (2015)
  * [4] Couso, I., Borgelt, C., Hullermeier, E., Kruse, R.: Fuzzy sets in data analysis: From statistical foundations to machine learning. IEEE Computational Intelligence Magazine 14(1), 31–44 (2019)
  * [5] Dang, T.K.N., Lopuhaä-Zwakenberg, M., Stoelinga, M.: Fuzzy quantitative attack tree analysis (2024)
  * [6] Dubois, D., Prade, H.: Fuzzy real algebra: Some results. Fuzzy Sets and Systems 2(4), 327–348 (1979)
  * [7] Jezewski, M., Czabanski, R., Leski, J.: Introduction to Fuzzy Sets, pp. 3–22. Springer International Publishing, Cham (2017)
  * [8] Lin, C.T., Wang, M.J.J.: Hybrid fault tree analysis using fuzzy sets. Reliability Engineering & System Safety 58(3), 205–213 (1997)
  * [9] Lopuhaä-Zwakenberg, M.: Fault tree reliability analysis via squarefree polynomials (2023)
  * [10] Lopuhaä-Zwakenberg, M., Budde, C.E., Stoelinga, M.: Efficient and generic algorithms for quantitative attack tree analysis. IEEE Transactions on Dependable and Secure Computing pp. 1–18 (2022)
  * [11] Mahmood, Y.A., Ahmadi, A., Verma, A.K., Srividya, A., Kumar, U.: Fuzzy fault tree analysis: a review of concept and application. International Journal of System Assurance Engineering and Management 4, 19–32 (2013)
  * [12] Ruijters, E., Stoelinga, M.: Fault tree analysis: A survey of the state-of-the-art in modeling, analysis and tools. Computer Science Review 15-16, 29–62 (2015)
  * [13] Schmucker, K.J.: Fuzzy sets, natural language computations, and risk analysis (1983)
  * [14] Singer, D.: A fuzzy set approach to fault tree and reliability analysis. Fuzzy Sets and Systems 34(2), 145–155 (1990)
  * [15] Stamatelatos, M., Vesely, W., Dugan, J., Fragola, J., Minarick, J., Railsback, J.: Fault tree handbook with aerospace applications (2002)
  * [16] Tanaka, H., Fan, L.T., Lai, F.S., Toguchi, K.: Fault-tree analysis by fuzzy probability. IEEE Transactions on Reliability R-32(5), 453–457 (1983)
  * [17] W. M. Dong, H.C.S., Wongt, F.S.: Fuzzy computations in risk and decision analysis. Civil Engineering Systems 2(4), 201–208 (1985)
  * [18] Yazdi, M., Nikfar, F., Nasrabadi, M.: Failure probability analysis by employing fuzzy fault tree analysis. Int. J. Syst. Assur. Eng. Manag. 8, 1177–1193 (02 2017)
  * [19] Zadeh, L.: Fuzzy sets. Information and Control 8(3), 338–353 (1965)