\section{Introduction}
During the last few decades, the use of electronic devices has spread significantly. Companies and individuals are using technology for both personal and work-related reasons. Especially, in the last decade with the use of IoT devices in all aspects of our everyday life a huge amount of personal and sensitive data is stored or processed on computer networks. These kinds of devices are limited in resources and in some cases, the cryptographic algorithms are not applicable. Along with the extended use of electronic devices, the attempts by malicious users to steal this data have increased. As a consequence, the research community has focused on finding ways to protect this data from malicious actors.

One well-known solution for assessing the security of a system is the use of graphical security models. These models represent security scenarios and help security experts identify the system's weaknesses. Their graphical representation constitutes a user-friendly way to analyze the security of the system. In the scope of this paper, we are going to examine only two kinds of these graphical representations - Attack Trees~\cite{schneier1999attack} and Attack Graphs~\cite{Phillips}. For a comprehensive overview of all the available formalisms, we suggest the reader refer to~\cite{KORDY}. Given our focus, we will use the term ``Attack Models'' to refer to the class of graphical security models constituted by both Attack Trees and Attack Graphs.

Currently, security experts manually produce graphical security models. This procedure, especially for such large systems used nowadays, can be tedious, error-prone, and non-exhaustive. Consequently, the need for automatic procedures arose and the research community has focused on addressing this issue. Especially in the last decade, researchers are studying different methods able to automatically produce graphical security models. 

In this work, we present an exhaustive survey on the automatic generation of Attack Models. The main goal of this work is to provide an overview of the field and to identify current challenges and future research opportunities. To our knowledge, it is the first survey paper focusing only on the automatic generation of Attack Models. The survey presents:

\begin{itemize}
    \item A quantitative study of the works included in this survey, with diagrams depicting  important features to provide the reader with a comprehensive overview of the field.
    \item A classification of the surveyed works according to the methodologies they use to automatically generate the graphical models.
    \item A comparative study based on the main characteristics of each work.
    \item An identification of limitations and future directions for the research community, in order to reduce the gap between research developments and practitioners' needs.
\end{itemize}

The paper is structured as follows: Section~\ref{sec:4} presents the related work, Section~\ref{sec:2} presents the main concepts of Attack Models, Section~\ref{sec:cat} presents an overview of the categories used to classify the papers under study, Section~\ref{sec:3} presents the research method used to structure our research, Section~\ref{sec:over} presents the quantitative study and the overview of the categories, Section~\ref{sec:class} presents the classification of the papers, Section~\ref{sec:lim} discusses the challenges and proposes future research directions and Section~\ref{sec:con} concludes the paper.

\section{Related Work}\label{sec:4}

\begin{table*}[!htb]
  \caption{Overview of the papers included in the Related Work}
  \label{tab:rw}
  \centering
\begin{tabular}{||c | c | c | c | c ||} 
 \hline
 Paper & After 2015 & Automatic Generation & Techniques' Classification & Challenges \\ [0.5ex] 
 \hline\hline
 \cite{KORDY} &  &  & \checkmark & \checkmark\\ 
 \hline
 \cite{lallie2020review} & \checkmark &  &  & \checkmark\\
 \hline
 \cite{widel2019beyond} & \checkmark & \checkmark &  & \checkmark\\
 \hline
 Our Work & \checkmark & \checkmark & \checkmark & \checkmark\\[1ex] 
 \hline
\end{tabular}
\end{table*}

In this section, we discuss other surveys focusing on the automatic generation of Attack Models. We chose these works since they are providing surveys on Attack Models, and some of them also consider their automatic generation. We also include a table to summarize the main characteristics of the papers included in the Related Work section. In Table~\ref{tab:rw} four different characteristics are presented. We denote the symbol \checkmark when the referred paper fulfills the corresponding characteristic. The first column includes the references to the paper under examination, the second column ``After 2015'' refers to the papers that have been published after 2015. This is an important characteristic since more than half of the papers included in our survey were published after 2015, the third column ``Automatic Generation'' refers to the papers that study the automatic generation of Attack Models, the fourth column refers to whether the paper presents a classification for the papers included in their survey, based on the techniques used in each paper and the last one if the paper indicates the challenges identified in the field.
The survey papers that we have identified are the following:

Kordy et al.~\cite{KORDY} present a very comprehensive survey of DAG-based graphical models for security. Their work summarizes the state of the art of the existing methodologies, they compare them and classify them based on their formalism. Although this is a very extensive survey, they do not focus on the automated generation of these models. Since it does not cover works published after 2015, their work does not cover several papers on Attack Model generation, that are instead covered in our work.

Lallie et al.~\cite{lallie2020review} examine the effectiveness of the visual representation of Attack Models. They analyze how these structures are representing the cyber-attacks. They conclude that there is no standard method to represent the Attack Models and that the research community should turn their attention to standardizing the representation. Although this paper is a great contribution, it does not examine the issue of the automatic generation of these structures.

Wojciech et al.~\cite{widel2019beyond} provide a survey of the application of formal methods on Attack Trees, their semi-automated or automated generation, and their quantitative analysis. Although they consider automatic generation, their research is not only focused on that. Also, they do not consider the automatic generation of Attack Graphs. Moreover, this paper considered only formal methods approaches and hence does not cover some of the papers we have studied, for example, machine learning approaches.

In our work, we discuss the different methodologies applied by the research community for automating the generation of Attack Models. We only focus on automatic generation and study the weaknesses and future directions in the specific field. To our knowledge, it is the first survey focusing on the automatic generation of Attack Models. We are planning to give to the reader a wide overview of the existing techniques currently used in this field. We are also aiming to provide a structured and comprehensive study for someone who wants to study this topic. Also, we are pointing out the current challenges existing in this field, that have to be addressed. 
Taking everything into consideration, we are providing a wider overview of the automatic generation of Attack Models than the other surveys, since it is the first survey focusing on this particular field. To be more specific, the automatic generation of Attack Trees is only studied in~\cite{widel2019beyond}, where all the papers referring to Attack Graphs are not considered-~\cite{ou2005mulval, Sheyner, sheyner2003tools, Ghazo, ibrahim2019automatic, Swiler, Tippenhauer, Phillips, koo2022attack, bezawada2019agbuilder, Ingols}, we consider all of the above papers. Also, the following papers which generate Attack Tree are not considered-~\cite{Bryans, Kumar, Pinchinat_2, jhawar2018semi, Hong} in~\cite{widel2019beyond}, we on the other hand consider all the papers mentioned above. Overall, our survey covers 15 papers that are not covered in any of the existing surveys.


\section{Background}\label{sec:2}

Before starting our survey we recall here the basic concepts of Attack Models. 

\subsection{Attack Trees}

\begin{figure}[]
\centering
\includegraphics[width=\columnwidth]{attack.pdf}
\caption{Attack Tree from~\cite{Jhawar}}
\label{fig:attack_tree}
\end{figure}

An Attack Tree is a graphical representation of potential attacks on the system's security in the form of a tree. Initially introduced by Schneiner~\cite{schneier1999attack}, this type of representation enables developers to identify the vulnerabilities of the system and facilitates the implementation of countermeasures. They model attack scenarios presented in a hierarchical way with each labeled node corresponding to a sub-goal of the attacker and the \textbf{root} being the main one - the global goal of the attack. The rest of the labeled nodes can be either \textbf{children of a node}, a refinement of the parent's goal into subsidiary goals, or \textbf{leaf nodes}, representing attacks that cannot be further refined in order to be implemented, also called basic actions. 
An Attack Tree is a 3-tuple $(N, \rightarrow, n_0)$, where $N$ is a finite set of nodes, $\rightarrow$ is a finite acyclic relation of type $\rightarrow \subseteq N \times M(N)$ - where $M(N)$ is the multi-set of $N$, and $n_0$ is the root node, such that every node in $N$ is reachable from $n_0$~\cite{mauw2006foundations}.


The basic formal model of Attack Trees incorporates two types of refinements: \texttt{OR} and \texttt{AND}. \texttt{OR} nodes represent disjunction (choice) where the parent node's goal is achieved when at least one of the children's sub-goals is achieved, \texttt{AND} nodes represent conjunction (aggregation) thus requiring for all children's sub-goals to be fulfilled. Several variants of Attack Trees have been proposed. For example, the sequential conjunction refinement \texttt{SAND}, is similar to \texttt{AND} but requires a specific  sequential realization of the children~\cite{widel2019beyond,mauw2006foundations}. One example of an Attack Tree is illustrated in Figure~\ref{fig:attack_tree}. In summary, there are two separate ways for the attacker to accomplish their goal, namely becoming a root: with or without authentication. The two refined authentication options are ssh and rsa, and both must be used because an AND arc is shown. On the other hand, if no authentication is carried out, the user must first be granted access using ftp and then rsh. Following the acquisition of privileges, lobf comes next.
It is readily apparent that the tree notation is very appealing and convenient for a threat analysis process since it can include multiple attacks derived from physical, technical, and even human vulnerabilities~\cite{widel2019beyond}. 

\subsection{Attack Graphs}

\begin{figure}[]
\centering
\includegraphics[width=\columnwidth]{attackgr.pdf}
\caption{Attack Graph from~\cite{cook}
}
\label{fig:attack_gr}
\end{figure}

Attack graphs are graphical representations of all the paths through a system that ends in a condition in which an attacker has successfully achieved their malicious goal. They outline all potential vulnerabilities and all possible attack paths in a given system and they are frequently used to represent complex attacks that have multiple paths and goals~\cite{lallie2020review}.
Attack Graphs play an important role in security, as they directly show the existence of vulnerabilities in the system and how attackers can exploit these vulnerabilities to implement an effective attack~\cite{Zhong}. 

An Attack Graph or AG is a tuple \begin{math}G = (S, \rightarrow, S_0, S_s)\end{math}, where S is a set of states, \begin{math}\rightarrow \subseteq S \times S\end{math} is a transition relation, \begin{math}S_0 \subseteq S\end{math} is a set of initial states, and \begin{math}S_s \subseteq S\end{math} is a set of success states~\cite{Sheyner}. Intuitively, \begin{math}S_s\end{math} denotes the set of states where the intruder has achieved their goals. Unless stated otherwise, we assume that the transition relation \begin{math}\tau\end{math} is total. We define an execution fragment as a finite sequence of states \begin{math}s_0, s_1, ..., s_n\end{math} such that \begin{math}(s_i, s_i+1) \in \tau\end{math} for all \begin{math}0 \leq i \leq n\end{math}. An execution fragment with \begin{math}s_0 \in S_0\end{math} is an execution, and an execution whose final state is in \begin{math}S_s\end{math} is an attack, i.e., the execution corresponds to
a sequence of atomic attacks leading to the intruder’s goal~\cite{Sheyner}. 

One example of an Attack Graph can be seen in Figure~\ref{fig:attack_gr}. The example represents the Attack Graph of a simple network. There is one switch connected to the internet on one side and to a workstation and a printer on the other end. The Attack Graph represents different states of the network and the edges are exploits that an attacker can use~\cite{cook}. In the specific example, the virus can exploit a particular vulnerability in the network in order to transition to State B, where it can exploit another vulnerability to gain root access.


\subsection{Attack Trees vs Attack Graphs}

A graph can be seen as a set of objects connected by a set of edges. A graph can be either directed or undirected. A directed graph has edges that represent a specific direction-one node is set to be the origin and the other one the destination. The edges in an undirected graph do not specify which node is the origin and which is the end-point, they just denote a two-way connection. 

A tree is a special case of a graph, more specifically a Directed-Acyclic Graph (DAG). A tree is represented by three different types of nodes, the root node, which does not have any parents, the internal nodes, which have both a parent and at least one child and the leaf nodes which do not have children. So, the tree represents a hierarchy between the nodes. 

Taking the above into consideration, we can conclude that the basic structure of Attack Trees and Attack Graphs is different. The Attack Graph can represent more than one goal node or in some cases even circles if an attacker is trying the same unsuccessful action multiple times. On the other hand, the Attack Trees only represent one goal node and constitute an acyclic graph by definition. We can also observe the different visual representations in Figures~\ref{fig:attack_tree}~\ref{fig:attack_gr}. 
Furthermore, in Attack Graphs, the event flow is represented top-down, while in the majority of the Attack Trees, this is depicted in a bottom-up way~\cite{lallie2020review}. Moreover,  in the same sense, Attack Trees generally use vertices to represent exploits and not preconditions, while preconditions are assumed to have been met in the transition from one exploit to the next. Attack graphs represent both~\cite{lallie2020review}. Essentially, Attack Models have a graph-based structure. The main differences are: how the event flow is depicted, the representation of full and partial attacks, and the representation of preconditions.


\section{Overview of the Categories}\label{sec:cat}
In this section, we are going to present the different categories we used to classify the papers. Every category is a method we identified in the literature. We also analyze the dimensions we selected to study in every paper.

\subsection{Methods}
One motivation for this work was to contribute to the research community by identifying the tools and methods that have been proposed to automatically produce Attack Models. In view of this, we examined every paper and identified the main underlying technology or method used. During this process, we identified 7 different methods, that form the categories that the papers were classified in this survey. The categories are disjoing; the papers included in the survey fall into only one category each. In particular, the categories are:

\begin{itemize}
    \item \textit{Templates:} The authors are generating the Attack Models using templates, created by common patterns identified. Some of the variables on the templates can be adjusted for each case.
    \item \textit{Transformation Rules:} A representation of the system is already available and some transformation rules are applied in order to obtain an Attack Model.
    \item \textit{Library based:} The Attack Model is generated given a library. A library contains some rules/patterns that must be used identically. The \textit{Templates} can be modified in each case. Also, \textit{Transformation rules} refer to some specific rules for translating from one system to another. In any case, the papers classified in category \textit{Libraries} it is stated by the paper that they use some sort of library. The same applies to \textit{Templates}.
    \item \textit{Artificial Intelligence:} Artificial intelligence techniques and algorithms such as action planning and machine learning are used in order to obtain an Attack Model.
   \item \textit{Logical Formulas:} A paper falls into this category when the system is represented by logical formulas. The Attack Model is derived from processing the logical formulas. 
    \item \textit{Model Checking:} A model checker is used to model the system and a security property is being checked. If the property does not hold, the model checker returns a counterexample that represents a path in the Attack Model. 
     \item \textit{Reachability:} The generated Attack Model is based only on an analysis of the reachability of the nodes of the network. This category includes only network security.
\end{itemize}

While studying the literature, we selected some features worth studying in each paper, in order to identify challenges and future directions in this field. Our primary consideration is to spot the gap between the research on this field and the actual employment of the suggested techniques in real-case scenarios. We are going to examine 7 dimensions in each category:

\begin{itemize}
    \item \textit{Proofs:} If a paper includes formal proofs for the algorithms applied for generating the Attack Models. Proof and semantics are important in order to support a method and identify possible limitations.
    \item \textit{Code:} If a paper includes a reference to the implementation of the proposed solution and if the code is available online. In this case, security experts will be able to use the code to test some cases and expand the method.
    \item \textit{Prerequisites:} The prerequisites one should acquire in order to be able to apply the proposed solution. Some methods require certain information or data the user must possess in order to apply the suggested solution. It is important to know what exactly is required to apply each method. Some prerequisites may be hard to acquire or critical for security.
    \item \textit{Domain:} If a paper proposed a Network Defined, Sociotechnical, or General solution. It is important to know what kind of attacks are considered in every solution, in order to select the best method. Each sub-class of the dimension \textit{Domain} is explained in detail in Subsection~\ref{security}.
    \item \textit{Graph or Tree:} If the proposed solution yields a Tree or a Graph. Some tools support Graphs and other Trees, so it is important to know the number and the quality of tools and methods available for each model.
    \item \textit{Experiments:} If the authors conducted experiments. Experiments are important in order to ensure the employment of the method. We observed that non of the papers have a reproducibility batch.
    \item \textit{Scalability:} If the authors discuss the scalability of their solution. Scalability is a crucial factor for real-life cases.
\end{itemize}

\subsection{Network Security vs General case}\label{security}
There is one of the dimensions that is worth discussing in more detail. The Domain dimension includes two sub-classes representing the attacks depicted by the Attack Models: the network-defined attacks and the general case. 

The first category is network-defined attacks. In this case, the works under study are focused on dealing with network security, meaning that they engage only with network-related attacks. We classify in this category only the papers that explicitly state that their work exclusively focuses on representing network-related attacks.

The second category denoted the general case, where the papers are taking into account both physical and network-related attacks. In many cases, the security of the system is compromised by human errors. Especially in large organizations where many people interact with extensive networks, it is very common for attackers to use social engineering or take advantage of human errors. 

During our research, we also discovered two papers~\cite{David, Gadyatskaya} referring to the term \textit{socio-technical} system. This term refers to a system involving: humans, machines, and interaction with the environment~\cite{BAXTER}. The socio-technical systems have five key characteristics as stated by Baxter et al.~\cite{BAXTER} and form their own category. In terms of attack types covered by the socio-technical systems, we found during our research that they represent both network-related and physical attacks, like social engineering and so we include them in the general case, but we state explicitly that the papers are referring to socio-technical systems.



\section{Research Method}\label{sec:3}

In this section, we are presenting the procedure we followed in order to identify the papers included in the survey. Following, we describe the research questions we are aiming to answer, and the research method applied in order to gather the final pool of papers used.

\subsection{Research Questions}
Our work is aiming to examine and discuss the current literature for the automatic generation of Attack Models. Underlined below are the research questions that motivated us to conduct this survey.
\begin{itemize}
    \item \textbf{RQ1:}What kind of techniques have been proposed for automatically generating Attack Models? 
    \item \textbf{RQ2:}Which of the 7 dimensions are being considered in each paper (proofs, code, prerequisites, domain, graph or tree, experiments, scalability)? 
    \item \textbf{RQ3:}What are the challenges/limitations we identified in the field?
\end{itemize}

\subsection{Research Method}
We decided to conduct our research using the snowballing technique~\cite{Wohlin}. The snowballing technique refers to the procedure of identifying relevant papers from the reference list or the citations of a selected paper. Our final pool includes 20 papers. The steps of the procedure we followed in order to identify our final pool of papers are the following:

\subsubsection{Start Set}
The first step is forming the start set of papers. Firstly we had to identify relevant keywords to form a query to the selected database. The keywords we selected to use are: ``Automatic Generation'', ``Automated Generation'', ``Attack Trees'' and ``Attack Graphs''. We performed our research in DTU Findit \url{https://findit.dtu.dk}, which is an open (guest access) database and includes publications from well-known journals and databases. We used the following query: title:(``Automatic generation'' OR ``Automated generation'') AND title:(``Attack trees'' OR ``Attack graphs''). Our search returns 13 papers, of which 3 were not available online. So based on relevance we formed our start set including five papers
~\cite{Muthumanickam,Zhong,Aksu,Sheyner,Vigo}.

\subsubsection{Iterations}
After finding the start set, we have to decide which papers we are going to include in our final pool. For this purpose, we applied \textit{Backward and Forward Snowballing}. Backward snowballing refers to the examination of the reference list of the papers. In order to identify if a paper will be included we extract some information regarding the title, the author, and the publication venue. Naturally, we should also take into account the context in which the paper is referenced. At this point, if a paper was still in consideration, we read the abstract and other parts of the paper in order to decide if the paper will be included. The forward snowballing is conducted in order to identify papers from the citation list of the paper being examined. Again, for each paper in the citation list, we extracted some basic information, we took into consideration in which context the citation is taking place and for the final decision, we read parts of the paper~\cite{Wohlin}. 



\section{Overview - Quantitative Study}\label{sec:over}
In this section, we are giving an overview of the field through a quantitative study. The reader can find information regarding the quantity of the papers taking into account specific characteristics. The quantitative study allows us to have a better view of the field and the lack of specific information.





\subsection{Publisher and Publication Year}
In this part, we provide statistics regarding the publishers and the publication year of the papers. Our goal is to identify the most popular venues and how the interest of the scientific community regarding the automatic generation of Attack Models altered over the years.  


\begin{figure}[]
\centering
\includegraphics[width=\columnwidth]{publisher_final_2.pdf}
\caption{Percentage of papers published by each publisher}
\label{fig:publishers}
\end{figure}

\begin{figure}[]
\centering
\includegraphics[width=\columnwidth]{years_final_2.pdf}
\caption{Percentage of papers published each year}
\label{fig:years}
\end{figure}




We can observe in Figure~\ref{fig:publishers} that the papers included in this survey have been published by 4 different publishers -IEEE, Springer, ACM, MDPI. The publishers with the most publications in the field are IEEE and Springer.
Also in Figure~\ref{fig:years} we can see the distribution of the papers through the years. The research community turned their interest to the field in 1998 and, at intervals, it has been active since. The interest decreased between 2007 to 2012, but since then the research community seems to be more active in the specific field. For better visualization, the years with zero publications are not presented in the diagram. We can see that the field is really limited, but we strongly believe that the automatic generation of Attack Models is an upcoming topic, and a survey exploring its techniques is missing. 

\subsection{Percentage of papers in each category}
In this work, we classify the papers into 7 different categories. Here we provide information about how many papers are in each category.

\begin{figure}[]
\hspace{-0.9cm}
\includegraphics[width=1.1\columnwidth]{dimen.pdf}
\caption{Number of papers that fall into/examining each dimension out of 20 papers}
\label{fig:stat}
\end{figure}

We can observe in Figure~\ref{fig:cat} that most of the papers fall into the model-checking category. Signifying that the research community preferred to use model-checking techniques for the Automatic Generation of Attack Models.

Later, in the paper, we examine each category separately and provide the reader with proper information, in order to establish a better understanding of each one.

\subsection{Experiments, Proofs, Code, Scalability}

We are also presenting how many papers provide experiments, proofs, code, or the scalability of their solution. In our perspective, these four dimensions (introduced in Section~\ref{sec:3}) studied for each paper are concrete evidence of the quality of the suggested generation algorithm. We also present information about how many papers are referring to the automatic generation of Attack Graphs and how many papers are referring to the automatic generation of Attack Trees. We concluded that almost half of the papers are presenting Attack Graphs and the other half Attack Trees. We can see the results in Figure~\ref{fig:stat}.

\begin{figure}[]
\centering
\includegraphics[width=\columnwidth]{cat_final.pdf}
\caption{Percentage of papers in each category}
\label{fig:cat}
\end{figure}

We can observe in Figure~\ref{fig:stat} that less than half of the papers are presenting experiments or proofs and even less refers to the scalability, in terms of complexity of the Attack Model generation algorithm.

\section{Classification based on the categories}\label{sec:class}

In this section, we present our findings for each category. At the beginning of each category, we present a brief overview of our findings, followed by a detailed presentation of each paper and a discussion of the limitations of each one. We also include tables to graphically represent the key characteristics of every paper, including a column for limitations and the year f publication.
 On Tables~\ref{tab:logic}-~\ref{tab:tr} ten different characteristics have been identified. The first column includes the reference to the paper under examination, and the rest of the columns refer to the different dimensions we identified in Section~\ref{sec:2}. More specifically, the second column ``Domain'' refers to whether the papers include only network-related attacks or general attacks, the third column refers to whether the paper presents Attack Trees or Attack Graphs, the fourth whether the paper presents experiments, the fifth whether the code of the proposed solution is available, the sixth whether the paper presents proofs, the seventh if there is a reference to the scalability in terms of complexity, the ninth if the proposed solution requires any prerequisites, and finally the tenth a limitation. 
 We use text to indicate the Domain (general or network-define attacks), the Attack Model (Tree or Graph), the Prerequisites, and the Limitations.
 We denote the symbol \checkmark when the referred paper fulfills the corresponding characteristic for Experiments, Code, Proof, and Scalability.

\subsection{Logical Formulas}

\begin{table*}[!htb] \scriptsize
  \caption{Overview of the papers included in the category \textit{LOGICAL FORMULAS} }
  \label{tab:logic}
  \centering
\begin{tabular}{||c | c | c | c | c | c | c | c | c||} 
 \hline
 Paper & Domain &  Model & Experiments & Code & Proof & Scalability & Prerequisites & Limitations \\ [0.5ex] 
 \hline\hline
 \cite{Vigo} & General & Tree & &  & \checkmark & \checkmark& \makecell[l]{$\bullet$ System description} & \makecell[l]{$\bullet$ Over approximations for the channels \\ $\bullet$ When a property is acquired it stays for ever}\\ 
 \hline
 \cite{Ou} & Network &  Graph & \checkmark &  & \checkmark & \checkmark&  \makecell[l]{$\bullet$ Network configuration \\ $\bullet$ Machine configuration \\ $\bullet$ Security advisories} & \makecell[l]{$\bullet$ The network must be manually specified by Datalog tuples }\\[1ex] 
 \hline
\end{tabular}
\end{table*}

 All of the papers falling in this category are using logical formulas to represent the system. Afterward, they exploit this structured formation to generate the Attack Models. 


In this category 10\% of the papers are included. We can see that the range of publication years is from 2006 to 2014. All of the papers are referring to the scalability of their solution. We also can see that 1 out of 2 (50\%) papers are generating Attack Trees and 1 out of 2 (50\%) is generating an Attack Graph. Additionally, it is worth pointing out that 1 out of 2 (50\%) papers presenting solutions only related to network security and only 1 out of 2 (50\%) presenting a general approach regarding attacks taken into account. Furthermore, 1 out of 2 (50\%) papers have the code available online, and 1 out of 2 (50\%) papers present experiments. All of the papers are providing formal proof for their solution. Below we are presenting the papers included in this category.

Vigo et al.~\cite{Vigo} propose a static-analysis approach. The authors use the Quality Calculus~\cite{QC} (an extension of the $\pi$-calculus) as a specification language. The processes are translated to proposition formulae, which represent the connection between channel knowledge and program point accessibility. Then, the authors propose a backward chaining search to the formulae from a program point \textit{l} in order to generate an Attack Tree. The main idea is to find the possible ways to access program point \textit{l}. The backward chaining exposes all the paths leading to point \textit{l}, thus unveiling all the information needed to reach that point. The attacker is able to send messages to a channel, for example, the password, but the content cannot be verified. Also, when an attacker achieves to send a message to the channel for the password, it is assumed that the password is known, and this property holds forever. The proposed way defines the system in a formal manner and the threat scenarios are derived automatically from the definition of the system. Moreover, process calculi have been used broadly for defining software systems and organizations in a coherent way. It is worth pointing out that the authors are studying Attack Trees, but their approach can be also applied to produce Attack Graphs. They also discuss the scalability saying that the worst case is exponential, but this case does not occur systematically as in the model checking approaches. The limitation of this approach is that they can only check if something has been received in the channel, but not the content. Finally, there is no reference to the soundness of the result and the generated Attack Trees are mostly used for quantitative analysis.

Ou et al.~\cite{Ou} present a work based on MulVAL~\cite{ou2005mulval}. MulVAL is a system for automatically identifying security vulnerabilities in networks. The central notion of MulVAL is that the configurations can be represented as Datalog tuples and security semantics and most attacks can be represented as Datalog rules. Every rule can be viewed as a logical formula. It evaluates the Datalog rules using XSB, a prolog system. The authors modified the MulVAL system to record the trace of the evaluations and send it to the graph-building algorithm, where the Attack Graph is produced. In every successful query, a function notes the successful deviation to the trace file. The paper also introduces an algorithm to transform the traces into an attack graph. The transformation takes every trace step and transforms it into a part of a graph. This work is focused on network security, meaning that the generated Attack Graph do not include General Attacks. The proposed solution is supported by related formal proofs and experiments, but the code of the proposed solution is not available. Also, the complexity of the algorithm for the generation of the Attack Graph is $O(N^2)$, where $N$ is the number of hosts, assuming that the table look at time is constant. It is worth pointing out that the size of the generated logical graph is polynomial to the size of the network. In order to generate an Attack Graph using the proposed solution the are three prerequisites: network configuration, machine configuration, and security advisories. 

Taking the above into consideration,~\cite{Vigo} can be applied for both Attack Trees and Attack Graphs, while~\cite{ou2005mulval} only generates Attack Graphs. Also,~\cite{Vigo} can mostly be used for quantitative analysis, since the content of the received messages in the designed model cannot be checked. Furthermore, once the attacker acquires information, like the password, it is assumed that it will never change. For example, the ability to change the password is not depicted. Finally, both works have the drawback that the system under investigation must be translated into another format, which is not always viable and time-consuming.

\subsection{Model Checking}

\begin{table*}[!t] \scriptsize
  \caption{Overview of the papers included in the category \textit{MODEL CHECKING}}
  \label{tab:MC}
  \centering
\begin{tabular}{||c | c | c | c | c | c | c | c | c||} 
 \hline
 Paper & Domain & Model & Experiments & Code & Proof & Scalability & Prerequisites & Limitations \\ [0.5ex] 
 \hline\hline
  \cite{Sheyner} & Network & Graph & \checkmark &  & \checkmark & &  \makecell[l]{$\bullet$ The model of the network\\ $\bullet$ A security property} & \makecell[l]{$\bullet$ Exponential to the system's variables}\\
 \hline
 \cite{sheyner2003tools} & Network & Graph & \checkmark &  &  & & \makecell[l]{$\bullet$ The network topology\\ $\bullet$ Configuration data for each host \\ $\bullet$ A set of attack rules \\ $\bullet$ A security property} & \makecell[l]{$\bullet$ Exponential to the system's variables}\\ 
 \hline
   \cite{Pinchinat} &  General& Tree &  & \checkmark  &  & &  \makecell[l]{$\bullet$ Building description \\ $\bullet$ Attacker's strength \\ $\bullet$ Attack objective} & \makecell[l]{$\bullet$ Focused on military buildings}\\
 \hline
\cite{Ghazo} & Network & Graph & \checkmark &   &  & \checkmark &  \makecell[l]{$\bullet$ Formal security model \\ $\bullet$ A security property} & \makecell[l]{$\bullet$ Time-consuming, due to multiple tools interacting}\\
 \hline
 \cite{ibrahim2019automatic} & Network & Graph &  &   & \checkmark &  &  \makecell[l]{$\bullet$ System description\\ $\bullet$ A security property} & \makecell[l]{ $\bullet$ Time-consuming, due to multiple tools interacting }\\[1ex] 
 \hline
\end{tabular}
\end{table*}

All the papers in this category are using Model Checking to automatically generate the Attack Tree/Graph.

In this category 25\% of the total papers are included. We can observe from Table ~\ref{tab:MC} that the chronological range of the publications is from 2002 to 2020. Only 1 out of 5 (20\%) papers discuss the scalability of the solution. Also, only 1 out of 5 (20\%) papers present proofs and provides the code of the proposed solution. Furthermore, 3 out of 5 (60\%) are presenting experiments, but none of them provides the code. Concerning the attacks included, 4 out of 5 (80\%) papers are focused on network security and the rest 1 out of 5 (20\%) are presenting Attack Trees with general attacks. On this note, the papers presenting general attacks are only using Attack Trees as a graphical representation model, and the rest of the papers present Attack Graphs and are focused on network-defined attacks.


Sheyner et al.~\cite{Sheyner} present the network as a finite state machine. They have modified the model checker NuSVM in order to automatically generate the attack graph. First, they form a security property. The model checker takes as input the property and the model M (the network). If the property is satisfied the model checker returns true, otherwise it provides a counterexample. The counterexample depicts a path that the attacker can follow to violate the security property. As future work, they aim to generate attack graphs for a more general class of properties. In this work, the state of the model is depicted as a set of booleans representing the configuration of the network and the attacker's actions as state transitions. As a consequence, the state space created is exponential to the number of the system's variables. This work involves Attack Graphs focused on network-defined attacks. The authors present proofs and experiments but do not present the code and the scalability of their solution. 

Sheyner et al.~\cite{sheyner2003tools} in an earlier work presented a method to generate attack graphs automatically, with the use of model checking~\cite{Sheyner}. The authors choose six network components in order to construct network attack models: a set of hosts, a connectivity relation, a trust relationship among the hosts, an intruder model, a set of individual actions the intruder can exploit to design an attack, and an intrusion detection system. In order to construct the set of actions the intruder can exploit, the authors use real-world vulnerabilities from the Common Vulnerabilities and Exposures (CVE) database. In order to construct the attack graph, the toolkit checks a security property with model checking, in order to ensure that the property is satisfied. An overview of the toolkit is also presented, along with the main components and the user interface. The authors focus on Network Defined attacks. They do not present proofs, the scalability of the solution, or the code. However, they present experiments. The required prerequisites are the network topology, configuration data for each networked host, and a library of attack rules. As a future work, the authors want to specify a library of actions based on a vulnerability database provided by SEI/CERT. This paper outlines a toolkit.


Pinchinat et al.~\cite{Pinchinat} present ATSyRA. ATSyRA is a tool implemented on top of Eclipse to help security experts interact with a user-friendly environment when designing Attack Trees. The main motivation for the implementation of the tool was the security of military buildings. As a first step, the security expert has to define the system: the building description, the attacker’s strength, and their attack objective. The second step is to run the generation of the attack scenarios. This step compiles the input specification into an Attack Graph. As a third step, the security expert specifies a set of high-level actions (HLA). The HLA implies how it can be refined into sub-actions. The final step is to run the Attack Tree synthesis. This step uses the information given in step 3 and the graph produced in step 2, to construct the Attack Tree~\cite{gtt}. The underlying interface for achieving this is a model-checking algorithm.  The paper presents general attacks and creates Attack Trees. The authors also provide the code in the form of a tool \url{https://atsyra2.irisa.fr/}. The scalability, proofs, and experiments are not provided in the paper. We can observe that the solution is not fully automated since the security expert is also taking an active part in the procedure.

Ghazo et al.~\cite{Ghazo} introduce an algorithm for automatic graph construction and visualization that exploits an existing tool of model checking. The description of the system is given as an input using  an Architecture Analysis and Design Language~\cite{sei}. Afterward, JKind~\url{http://loonwerks.com/tools/jkind.html} model checker is employed to check a security property and automatically produce counterexamples that form a path on the produced Attack Graph. Finally, the GraphViz tool was used to combine the paths in an Attack Graph. The present tool can generate a representation of the system, i.e. network level, but also atomic vulnerabilities, post-conditions, and properties regarding  security that can be valuable for our security purposes. The system's input is the description of the system and a security property that one wants to check. Finally, as a limitation, it is pointed out that much time is spent between of the multiple tools involved in the process.

Ibrahim et al.~\cite{ibrahim2019automatic} present a solution including Hybrid Attack Graphs (HAG). Generally, HAGs capture the changes in logical parameters, as defined by the pre and post-conditions, representing the state of the system under attack. They also capture the level of resilience, which is a number indicating the dynamic response of the system under a sequence of attacks. The worst-case scenario is selected to be included in the Attack Graph, based on the level of resilience. 
Automated HAGs can be visualized with a Java-based tool. This procedure requires a formal description of the system's model and the security property (written at Architecture Analysis and Design Language~\cite{sei}), validated by a model checker named JKind~\url{http://loonwerks.com/tools/jkind.html}. 

The first two papers included in this category~\cite{Sheyner, sheyner2003tools} are using the same underlined procedure. The basic limitation of this method is that it is exponential to the variables of the system, so it is not applicable to the large systems employed these days. Furthermore,~\cite{Pinchinat} is mainly focused on military building, so more examples should be employed to test this method in other fields. In~\cite{Ghazo, ibrahim2019automatic}, many tools are involved in the proposed procedures so a lot of time is spent on the interactions between the different components. 





\subsection{Templates}

\begin{table*}[]\scriptsize
  \caption{Overview of the papers included in the category \textit{TEMPLATES}}
  \label{tab:temp}
  \centering
\begin{tabular}{||c | c | c | c | c | c | c | c | c ||} 
 \hline
 Paper & Domain & Model & Experiments & Code & Proof & Scalability & Prerequisites & Limitations \\ [0.5ex] 
 \hline\hline
 \cite{Bryans} & Network & Tree &\checkmark & \checkmark &  & & \makecell[l]{$\bullet$ Description of the network \\ $\bullet$ Set of templates} & \makecell[l]{$\bullet$ Focused on automotive communication}\\ 
 \hline
 \cite{Swiler} & Network & Graph  &  & &  & &  \makecell[l]{$\bullet$ Configuration of the network \\ $\bullet$ Attacker's profile \\ $\bullet$ Attack templates}&  \makecell[l]{$\bullet$ The user has to specify the templates manually}\\
 \hline
  \cite{Tippenhauer} & General & Graph & &  & \checkmark & & \makecell[l]{$\bullet$ Security goal \\ $\bullet$ Workflow of the system \\ $\bullet$ System's description \\ $\bullet$ Attacker model} &  \makecell[l]{$\bullet$ Static templates, that do not adjust to new attacks}\\ 
 \hline
 \cite{Kumar} & Network  & Tree & &  & & &  \makecell[l]{$\bullet$ System description \\ $\bullet$ The Attack Tree template} & \makecell[l]{$\bullet$ Abstract and static Templates}\\
 \hline
 \cite{Phillips} & General &  Graph  &  & &  & & \makecell[l]{$\bullet$ Attacker's profile \\ $\bullet$ A set of templates \\ $\bullet$ Configuration of the system}  &  \makecell[l]{$\bullet$ Limited attack templates}\\[1ex] 
 \hline
\end{tabular}
\end{table*}

\begin{table*}[]\scriptsize
  \caption{Overview of the papers included in the category \textit{LIBRARY-BASED}}
  \label{tab:library}
  \centering
\begin{tabular}{||c | c | c | c | c | c | c | c | c||} 
 \hline
 Paper & Domain & Model & Experiments & Code & Proof & Scalability & Prerequisites & Limitations \\ [0.5ex] 
 \hline\hline
 \cite{Pinchinat_2} & General  & Tree&  & \checkmark  & \checkmark & \checkmark& \makecell[l]{$\bullet$ A library of refinement rules \\ $\bullet$ A trace}  & \makecell[l]{$\bullet$ Have a trace/logs in a specific format \\ $\bullet$ Specify a set of refinement rules}\\
 \hline
 \cite{jhawar2018semi} & General & Tree &   &\checkmark & \checkmark & & \makecell[l]{$\bullet$ An initial version of the tree \\ $\bullet$ A library of annotated attack trees}  & \makecell[l]{$\bullet$ Static library that do not adjust to new attacks}\\[1ex] 
 \hline
\end{tabular}
\end{table*}

In this category belong the papers using templates to generate the Attack Trees/Graphs. 

This category includes 25\% of the total papers. We can see that the year of publication varies from 1998 to 2020. We can observe in Table~\ref{tab:temp} the features of each paper. Also, 3 out of 5 (60\%) papers are limited to network-defined attacks, and the rest of them (40\%) are dealing with general attacks. Furthermore, 2 out of 5 papers are constructing an Attack Tree, while 3 out of 5 are constructing an Attack Graph. Only 1 out of 5 (20\%) of the papers is presenting experiments, the same percentage includes proofs. Additionally, 1 out of 5 (20\%) papers are sharing the code of their solution. It is important to point out that none of the papers are referring to the scalability of their proposed solution.

Bryans et al.~\cite{Bryans} introduce a method to generate Attack Trees automatically from the description of the network and a set of templates. Each template represents an attack step. The templates are using variables that have to be replaced by the components of the system under investigation. The proposed algorithm is recursive, at each step, a leaf of the template trees is investigated and expanded if the leaf contains an unbounded variable. If the name of the child matches the name of the root of one of the templates, it is replaced. When the unbounded variable matches multiple templates an OR node is introduced. The authors are constructing an Attack Tree and the code is available online at \url{https://tinyurl.com/uoptgfb}. They also present the experiments conducted, but they do not discuss the scalability and the proofs. As a future work, they aim to expand the method to support more networks, since right now they are focused on automotive communication networks.

Swiler et al~\cite{Swiler} proposed a method to generate an attack graph, in which each node represents a state of the network. The tool has as an input the configuration of the network, the attacker’s profile, and the attack templates. The attack templates represent steps of known attacks or strategies for moving from one state to another. The tool combines the input information and customizes the generic template attacks according to the attacker profile and the network configuration. Every graph includes some variables that represent the state of the network. When a node in a graph matches the requirements of the template a new edge is added to the network and new nodes are created. This paper is dealing with network-defined attacks. The authors are not providing experiments, proofs, or code, or discussing the scalability of their solution. 

Tippenhauer et al.~\cite{Tippenhauer} are presenting  a Goal-System-Attacker graph. There is a 3-step procedure to generate it. At first, the security goal and the workflow of the system are used to produce the G-graph (Goal-graph), which represents the security goal and the workflow description. The result is used in combination with the system description to generate the GS-graph (Goal-System graph), which is then combined with the attacker model to generate the GSA-graph (Goal-System-Attacker graph). At every step, the graph is updated with further information about the environment. The authors used the framework described above and noticed that there is a series of patterns. These patterns were used to implement some templates. Afterward, they defined local extensions to progressively generate these graphs using the predefined templates. If there is a matching node, the template is integrated into the main graph. The authors are taking into account general attacks and they present proof for their work. They do not give input for the scalability, the code, or any experiments conducted.

Kumar et al.~\cite{Kumar} introduce the use of an Attack Tree template as a feature diagram, i.e. formal and graphical notations, to solve the non-standardization problem of Attack Trees. This problem states that, in general, a standard template for Attack Trees design does not exist. The template considered in this work is structured in layers each refining the previous ones, in order to construct a tree semi-automatically. This Attack Tree template can be seen as an abstraction that can capture crucial scenarios about attacks by refining hierarchical relationship rules. Moreover, the template is constructed by going through the literature on Attack Trees so that common characteristics in their design can be found. Summing up, the authors present a way for identifying  proper meta-categories suitable for Attack Trees by means of feature diagrams, in order to construct the trees in a semi-automated manner.

Phillips et al.~\cite{Phillips} present a system where the graph is generated using the attack profile, the input templates, and the configuration of the system. The procedure starts from the goal node and is built backward. Then, a search of the templates is conducted to find an edge that the head matches the goal node. The paths that do not satisfy the attacker profile are eliminated. The procedure is repeated until we reach an initial state that is not the head of an edge. The authors claim that their approach can model dynamic aspects by overwriting the configuration of the network. As a prerequisite, besides the configuration of the network and the attacker's profile, a database with common attacks is also required. They do not present the code, proofs, or experiments, or discuss the scalability.

Taking the above into account, the method introduced in~\cite{Bryans} is focusing on automotive communication, and the templates produced are adjusted to this specific field. Furthermore, at~\cite{Swiler} the user has to specify the input templates manually which can result in a limited set of templates. The methods from~\cite{Tippenhauer, Kumar} result in static templates that do not catch up with technological and social advancements. Also, the proposed solution at~\cite{Kumar} results in a template of how to design the whole attack tree, which makes it really abstract and some attacks for specific systems might be eliminated. The method at~\cite{Phillips} produces only a limited set of templates. There are some works that require the attacker's profile as input. This addition can eliminate some possible attacks if the user does not cautiously define the profile of the attacker, the worst-case scenario should always take into account.

\subsection{Library Based}


\begin{table*}[]\scriptsize
  \caption{Overview of the papers included in the category \textit{Artificial Intelligence}}
  \label{tab:ml}
  \centering
\begin{tabular}{||c | c | c | c | c | c | c | c | c||} 
 \hline
 Paper & Domain & Model & Experiments & Code & Proof & Scalability & Prerequisites & Limitations \\ [0.5ex] 
 \hline\hline
 \cite{koo2022attack} & Network & Graph & \checkmark & &  & &  \makecell[l]{$\bullet$ Topology information \\ $\bullet$ System information}  & \makecell[l]{$\bullet$ The method is applied to small organisations}\\
 \hline
 \cite{bezawada2019agbuilder} & Network & Graph &  & &  & &   \makecell[l]{$\bullet$ Vulnerability descriptions} &\makecell[l]{$\bullet$ Time-consuming to generate Attack Graph from PPDL }\\[1ex] 
 \hline
\end{tabular}
\end{table*}

\begin{table*}[]\scriptsize
  \caption{Overview of the papers included in the category \textit{REACHABILITY}}
  \label{tab:reach}
  \centering
\begin{tabular}{||c | c | c | c | c | c | c | c  | c||} 
 \hline
 Paper & Domain & Model & Experiments & Code & Proof & Scalability & Prerequisites & Limitations \\ [0.5ex] 
 \hline\hline
 \cite{Ingols} & Network &  Graph & \checkmark  &\  &  & \checkmark&   \makecell[l]{$\bullet$ Map of the Network \\ $\bullet$ Data from Nessus, Sidewinder, Checkpoint  \\ $\bullet$ CVE dictionary \\ $\bullet$ National Vulnerability Database}& \makecell[l]{$\bullet$ Attack paths are monotonic \\ $\bullet$ Not modelling client-side attacks}\\
 \hline
 \cite{Hong} & Network & Tree & \checkmark  & &  & \checkmark& \makecell[l]{$\bullet$ Description of the network}   & \makecell[l]{$\bullet$ The model depicts only  connectivity} \\[1ex] 
 \hline
\end{tabular}
\end{table*}

All the papers included to this category are constructing the Attack Models given a Library.

In this category, the papers included are 10\% of the total papers. We can see that the year of publication range from 2018 to 2020. All of the papers are taking into account general attacks and are constructing Attack Trees. Also, all of the papers are presenting the code and proofs supporting their solution. Finally, 1 out of 2 (50\%) of the papers are referring to scalability.

Pinchinat et al.~\cite{Pinchinat_2} are constructing an Attack Tree. The main goal of this work is to construct the attack tree that explains a trace given a library L (a set of refinement rules). This approach is also good for forensics, but one should have the logs. The Attack Tree is being built according to the refinements provided by the library. The algorithm that handles the procedure is based on the CYK algorithm, which answers whether some input context-free grammar can generate some input world. The code is also available for the readers at \url{http://attacktreesynthesis.irisa.fr/}. The procedure is semi-automatic to avoid unsound results. Also, the Attack Tree consists of AND, OR, and SAND refinements. The authors are also presenting proof for their solution. The mentioned scalability is that the algorithm is polynomial at the size of the trace. The attacks taken into account are general. Finally, the authors are not presenting experiments.

Jhawar et al.~\cite{jhawar2018semi} presented a paper focused on a semi-automatic procedure for creating attack trees. The construction of the Attack Trees can be summed up in four steps: First step: A group of experts defines an initial version of the tree. Second step: Some automatic mechanisms are used to enhance the tree. Third step: The experts curate the new version of the tree. Fourth step: Repeat step two and three. The paper is focusing on implementing the second step. The authors express a predicate-based annotation of the tree, to determine if an attack tree can be attached to another attack tree as a sub-tree. The authors construct a library of annotated attack trees using the National Vulnerability Database~\url{https://nvd.nist.gov/}. After that, they use this library to extend attack trees manually constructed, using the Common Attack Pattern Enumeration and Classification~\url{https://capec.mitre.org/}. As a future work, they want to implement a dynamic library and expand the idea to also include counterexamples. The code is available online at  \url{https://github.com/yramirezc/lib-annotated-attack-trees}. The authors are also providing the reader with proof of their solution. Finally, they do not present experiments or the scalability of their solution.

The method introduced in~\cite{Pinchinat_2} requires the traces of an attack that has already taken place. It might be difficult to acquire such information and also the attack tree is generated after the attack has already happened. This feature makes the method good for forensics. Also, the solution proposed in~\cite{jhawar2018semi} produces a static library that has to be updated over time as society and technology are dynamic systems.

\subsection{Artificial Intelligence}

\begin{table*}[]\scriptsize
  \caption{Overview of the papers included in the category \textit{TRANSFORMATION RULES}}
  \label{tab:tr}
  \centering
\begin{tabular}{||c | c | c | c | c | c | c | c | c||} 
 \hline
 Paper & Domain & Model & Experiments & Code & Proof & Scalability & Prerequisites &  Limitations \\ [0.5ex] 
 \hline\hline
 \cite{Gadyatskaya} & General & Tree & &  &  & & \makecell[l]{$\bullet$ Socio-technical model \\ $\bullet$ The attacker's profile \\ $\bullet$ The asset that the attacker targets} & \makecell[l]{$\bullet$ Limited set of attributes are investigated}\\ 
 \hline
 \cite{Ivanova} & General & Tree &  & &  & & \makecell[l]{$\bullet$ Graphical system model}   & \makecell[l]{$\bullet$ Only for  confidentiality and integrity}\\[1ex] 
 \hline
\end{tabular}
\end{table*}
All the papers assigned in this category are using Artificial Intelligence in order to construct the corresponding Attack Trees/Graphs. 


In this category are included 10\% of the papers included in this survey. The range of publication years varies from 2019 to 2022. We can observe that all the papers are dealing with Network Defined attacks and are constructing the corresponding Attack Graph. Also, none of the papers share the code of their solution. None of the papers in this category are presenting proofs or the scalability of their approach.

Koo et al.~\cite{koo2022attack} introduces a method to support the 
 generation of an attack graph using Deep Learning and Machine Learning. The final model takes as an input the network topology and the system information. 
  Feature extraction is applied to acquire an attack graph generation model by exploiting the input data.  Finally, the authors are using an evaluation metric to evaluate the predicted path. To sum up, the authors present a binary classification problem together with a multi-output learning algorithm, in order to generate an attack graph starting from the information about the system and the network.

Bezawanda et al.~\cite{bezawada2019agbuilder} presented a tool that automatically generates the PDDL (Planner Domain Definition Language) representation of an Attack Graph from descriptions found in the Common Vulnerabilities and Exposures(CVE)~\url{https://cve.mitre.org/} or the National Vulnerability Database (NVD)~\url{https://nvd.nist.gov/}. PPDL is a set of languages able to depict a planning problem~\cite{ghosh2012planner}. The PPDL is composed of two concepts, the PPDL domain, and the PPDL problem. The PPDL domain is some problem descriptions with the corresponding actions and constraints. The PPDL domain includes abstract variables. When these variables take a specific value, an instance of the PDDL domain is created which is called the PDDL problem. The PDDL problem is solved with the help of the PDDL planner, which is trying to find a plan to satisfy the PDDL problem (a sequence of actions one must perform to achieve the end goal). The authors are using natural language processing to produce the PDDL from the textual description. The procedure can be explained in 4 steps. First step: Extract information from the Vulnerability database and form the PDDL domain. Second step: Form the PDDL problems using the PDDL domain and event logs of the system. Third step: An Artificial Intelligence algorithm is generating a PDDL plan for each PDDL problem. Fourth step: The tool updates the content of the PDDL domain with every modification of the input data. Also, the tool offers the transformation of the PDDL to the corresponding Attack Graph for visualization purposes. The authors do not present experiments, code, proofs, or the scalability of their solution.

The authors at~\cite{koo2022attack} present an easy and cheap method for generating Attack Graphs, but they explicitly state that it is applicable to small organizations. This is not the usual case nowadays, since we are surrounded by huge systems and organizations. Furthermore, the proposed solution on~\cite{bezawada2019agbuilder} provides a method that represents an Attack Graph with a Planner Domain Definition Language. The transformation from this form to an Attack Graph is time-consuming. Also, tools available in the literature for analyzing these structures (quantitative and qualitative analysis) do not support the PPDL format.

\subsection{Reachability}
All the papers included in this category are using only the reachability of the nodes in the network in order to construct the corresponding Attack Tree/Graph. 

This category includes 10\%  of the papers. The years of publication range from 2006 to 2013. All of the papers in this category are presenting experiments and show scalability. Also, all of the papers deal with Network defined attacks. Furthermore, 1 out of 2 (50\%) papers is constructing an Attack Tree, and the other one an Attack Graph. None of the papers are providing the reader with their code or formal proofs of their solution.

Ingols et al.~\cite{Ingols} proposed a system based on multiple prerequisite graphs. They argue that this type of graph is better that the full graphs or the predictive graphs due to the lack of dependencies. The system processes the input data (Map of the network) and computes the reachability matrix. The computation of the reachability matrix is equipped with some improvements crucial to saving memory and time. Some sections of the matrix are collapsed into reachability groups. The filtering rules are replaced by Binary decision diagrams, resulting in filtering rules in linear time. The graph is constructed using a breadth-first technique. Multiple prerequisite graphs consist of three different kinds of nodes; state nodes, prerequisite nodes, and vulnerability instance nodes. During the construction, every type of node is added differently to the graph. Also, this work presents a graph simplification for visual presentation. The proposed solution imports data from Nessus \url{http://www.nessus.org}, Sidewinder and Checkpoint firewalls, the CVE dictionary \url{http://cve.mitre.org}, and NVD \url{http://nvd.nist.gov.}.  The generation of the Attack Graph depends on data that can be obtained quickly. The data are evaluated and reported as early as possible. This work assumes that the paths are monotonic, meaning that the attacker will never go back. Also, the authors are not modeling client-side attacks, where an attacker is taking advantage of a server to harm a vulnerable client. The authors refer to the scalability in terms of complexity as almost linear to the size of the network. Also, they present experiments for their solution. Finally, it is also worth mentioning that they do not present the code or proofs for their work.

Hong et al.~\cite{Hong} identify all the paths in the network of the system to construct the full AT, which consists of AND and OR gates. After the construction of the full Attack Tree, there are two proposed methods: 1. Simplified Attack Tree with Full Path Calculations 2. SATwIPC simplified Attack Tree with Incremental Path calculation. The first method requires a logical expression of the attack tree and removes the sequence information from the expression but it groups similar nodes. The second method is maintaining attack path information which is constructed by exploiting network configurations and sequences of vulnerabilities. The authors present Attack Trees that depict attacks concerning only network security. The authors do not present formal proofs or the code of their solution, but they present the scalability and experiments. 

Ingols et al.~\cite{Ingols} assume that the paths are monotonic, meaning that the attacker will never go back. This is not the real case, since some actions may force the attacker to go back into the network. Also, their method does not model client-side attacks, which can cause major issues to a system. Furthermore,~\cite{Hong} proposes a method that represents the Attack Tree as different paths in the network, based only on connectivity. On the contrary,~\cite{Ingols} also exploits extra data to understand the path the attacker has taken. 


\subsection{Transformation Rules}
In this category, the papers that are using transformation rules to obtain the corresponding Attack Tree are included. This category takes into account works where a model of the system is already available and transformation rules are applied to obtain the Attack Model.

This category includes 10\% of the papers included in this survey. Also, the publication year for all the papers is 2016. All of the papers included in this category are taking into account General Attacks and construct the corresponding Attack Tree. Furthermore, none of the papers in this category are presenting experiments, the code, proofs, or scalability of the proposed solution.

Gadyatskaya et al.~\cite{Gadyatskaya} presents an Attack-Defense tree generation for socio-technical models. The socio-technical models capture the organizational infrastructure and human-computer interactions. These models cannot depict all the security aspects, so the need for maintaining a separate Attack (Defense) Tree is essential. The paper deals with defining some transformation rules starting from the socio-technical model in order to obtain a group of attack-defense bundles. These attack-defense bundles can be combined to generate one Attack-defense Tree. This procedure constitutes the first step and the automated procedure. The authors also propose a way to expand the model and place more countermeasures. Basically, the aim of this work is the automation of Attack Tree construction, exploiting socio-technical models.

Ivanova et al.~\cite{Ivanova} are aiming to transform a graphical system model into a graphical attack model. The graphical system model includes locations, actors, processes, and items. The actors and the processes can be decorated with policies and credentials. For every component, the authors introduce some guidelines for transforming the graphical representation to the corresponding Attack Tree. As a future work, the authors would like to extend their model to include attacks aiming to disturb the environment of the system, where the current solution deal with confidentiality and integrity.

Gadyatskaya et al.~\cite{Gadyatskaya} are exploiting socio-technical models for generating Attack-defense Trees, but they limit their investigation in a limited set of attributes. It would be interesting to expand their model with more complex attributes. Furthermore,~\cite{Ivanova} deals only with confidentiality and integrity components, so the model should be enriched with more attributes in order to be applied in real-life cases.

\begin{table*}[ht] \scriptsize
\caption{Limitations for each category}
  \label{tab:lim}
    \centering
    
    \begin{tabular}{| m{2cm} | m{6.7cm} | m{8cm} |}
        \hline
        Category & Limitations  & Future Directions\\
        \hline
        Logical Formulas & 
        \begin{itemize}[leftmargin=*] 
            \item Transform the network to logical formulas.
            \item Fully automated techniques.
        \end{itemize} &
        \begin{itemize}[leftmargin=*]
            \item Introduce semi-automated methods for soundness.
        \end{itemize} \\
        \hline
        Templates &
        \begin{itemize}[leftmargin=*]
            \item Static templates, not adjusted to a specific system.
            \item Templates produced from current literature.
            \item Producing the templates can be tedious and needs expertise.
        \end{itemize} &
        \begin{itemize}[leftmargin=*]
            \item Balance between abstraction and specification.
            \item Automatically updates and produce templates.
        \end{itemize} \\
        \hline
        Library based &
        \begin{itemize}[leftmargin=*] 
            \item Static libraries.
            \item Defining the library can be tedious and requires expertise.
        \end{itemize} &
        \begin{itemize}[leftmargin=*] 
            \item Automatically updates the libraries.
        \end{itemize} \\
        \hline
        Model Checking &
        \begin{itemize}[leftmargin=*] 
            \item State-space explosion, not scalable for large systems.
        \end{itemize} &
        \begin{itemize}[leftmargin=*] 
            \item Experiments with different model checker tools available in the literature.
        \end{itemize} \\
        \hline
        Transformation Rules &
        \begin{itemize}[leftmargin=*] 
            \item Depends only on the input model. 
            \item Static procedure.
        \end{itemize} &
        \begin{itemize}[leftmargin=*] 
            \item Explore transformation of more dynamic input models.
        \end{itemize} \\
        \hline
        Artificial Intelligence &
        \begin{itemize}[leftmargin=*] 
            \item A small set of models have been used.
        \end{itemize} &
        \begin{itemize}[leftmargin=*] 
            \item Experiment with other models.
        \end{itemize} \\
        \hline
        Reachability &
        \begin{itemize}[leftmargin=*] 
            \item Depends only on which node is connected with which.
        \end{itemize} &
         \begin{itemize}[leftmargin=*] 
            \item Use as a component of the automatic generation.
        \end{itemize} \\
        \hline
    \end{tabular}
\end{table*}


\section{Challenges and Future Directions}\label{sec:lim}
After classifying and examining different characteristics of every paper we identified some challenges in the field. In this section, we present some limitations based on each category and the challenges identified that can serve as a future direction for the research community.

\subsection{Limitations}

In this subsection, we discuss the limitations we found in each category. Every method has strengths in Table~\ref{tab:lim} we can see an overview of the limitations for each category and some suggestions for a future direction to deal with these issues. Table~\ref{tab:lim} consists of three columns. The first column includes the categories, the second column the limitations of the corresponding category, and the third column some future directions to improve the limitations mentioned. Following, we discuss our findings in detail.

The papers included in the logical formulas category do not mention the automatic generation of countermeasures for each attack. The models are focusing only on pointing out the attacks (weaknesses) of the system and until now there are no works mentioning the possibility of extending the model to also produce countermeasures. Also, there are fully automated techniques that can result in unsound results or redundant outcomes. An Attack Model is considered to be sound when the decomposition of the main goal results in a set of goals, that their accomplishment yields a partial accomplishment of the main goal. Also, the Attack Model has to be consistent, meaning that the proposed decomposition guarantees the achievement of the main goal, and complete, meaning that the proposed decomposition completely characterizes the main goal~\cite{sound}. If the above statements are not met, the Attack Model is considered unsound. Fully automation is easier and more helpful for security experts but it can be tedious if the results are not sound. Finally, the system has to be defined as logical formulas, which in real-world scenarios might be really difficult for the security experts since they are dealing with very large networks and they might not be familiar with these languages unless the formulas can be extracted automatically.

The templates category provides the community with a more coherent way to specify attacks and avoid unsound results. But the templates can be static and difficult to be adjusted to multiple systems. Also, templates created from the literature in the future can produce outdated results. Finally, in order for the templates to be adjusted to a specific system the security experts have to design these templates, a procedure that might be tedious as designing the Attack Models from scratch on the first try.

Library-based approaches are either constructing a library using well-known databases in order to construct the tree or defining a library of refinement rules in order to automatically construct the Attack Model. The first approach results in a static library that has to be manually updated since the systems are dynamic entities. The second approach requires that the library with the refinement rules is updated when new components are integrated into the system. In both cases, at the first application of the method, one must define the library from scratch according to the system.

Model checking is a really popular method in the field in order to produce Attack Models automatically. Model checking suffers from the state-space explosion and might not be applicable to very large systems, especially when the parameters of the system are being modeled. Also, according to our research, there are no works in this category that can produce countermeasures. 

Transformation rules methods depend only on the input model, thus making the procedure static. If a new component is added to the system the whole procedure must be repeated from scratch.

Until now only a few models of Machine Learning and Deep Learning have been used for the automatic generation of Attack Models. The research community can experiment with other models to find the most suitable one.

Reachability approaches depend only on the reachability of the nodes. This method can exclude different kinds of attacks that rely on more complex information. This is a major limitation since some of the attacks will not be taken into consideration. This method is applicable for networks but should be used as an extra component for the automatic generation of Attack Models.

\subsection{Future Directions}
\begin{itemize}
    \item \textit{Use of $\mathit{SAND}$:} In the automatic generation of Attack Trees only a few papers are including the $\mathit{SAND}$ operator. The $\mathit{SAND}$ operator can represent multiple situations that occur in different kinds of attacks~\cite{Jhawar}. So we believe that it is important to also include this operator in the automatic generation.
    \item \textit{Use of $\mathit{XOR}$:} In our knowledge, there is no reference in the literature to the exclusive choice operator. There are cases in some attacks where an attacker will end up with an exclusive choice. For example to break one out of two doors, due to the equipment available - i.e. one bomb available. In our opinion, it is necessary for the research community to include such an operator on the Attack Trees in general and later on their automatic generation.  With the addition of the $\mathit{XOR}$ operator the security experts or the programs analyzing the potential attacks can exclude some paths or traces.
    \item \textit{Dynamic Solutions:} The systems are being upgraded constantly. New variables or configurations can make an Attack Model useless. The need for more dynamic solutions is crucial. Whenever there are some changes in the system the current version of Attack Models should be updated, helping security experts identify new potential threats. There is one paper in the literature proposing a more dynamic solution~\cite{Phillips}.
    \item \textit{Poor Semantics / Proofs:} The use of semantics and proofs is really important. There are some works that do not use proofs or semantics to support their solution. Neglecting the semantics can lead to poor or unsound results. The use of proofs can help the reader better understand the concepts used and help the researchers expand the field. Semantics can help the community develop the same language concerning the generation of Attack Models. As discussed in Section~\ref{sec:over} 35\% of the papers are presenting formal proof of their findings.
    \item \textit{Forensics:} Another field important to security experts is forensics. Forensics can help security experts identify vulnerabilities that did not previously take into account and secure better their systems. Using forensics one can generate Attack Models to depict what when wrong in a system. This procedure requires the logs or traces of a running system.
    \item \textit{Sound Results:} The automatic generation of Attack Models provide a very good tool for security experts. But it might produce unsound results that are not usable. There are not many works providing proper means to prevent the generation of unsound results. Mostly semi-automated procedures have been proposed to avoid the generation of unsound results~\cite{jhawar2018semi, Pinchinat_2, Kumar}.
    \item \textit{Prerequisites:} All of the papers require some prerequisites in order to generate the Attack Models. In some cases, this might be tedious for the security experts if the prerequisites require their involvement (semi-automated), but a fully automated procedure might produce unsound results. Some prerequisites can be the configuration of the system, which is a very important file that an attacker can exploit to take control of the system. So the prerequisites can themselves be a vulnerability. It is important to find the right balance between the number of prerequisites and producing sound results. It is also important to examine the nature of the prerequisite and how crucial they can be for the security of the system.
    \item \textit{Scalability:} Scalability is one of the main characteristics of a tool. Nowadays we use very large systems to cover our needs. The automatic generation of Attack Trees should be adapted to be able to perform under these circumstances. So, it is important to study the scalability and try to optimize the proposed algorithms.
    \item \textit{Attack Defence Trees:} A few papers are investigating the Automatic generation of Attack Defence Trees~\cite{Gadyatskaya}. After the automatic generation of Attack Models, is it natural to investigate the automatic generation of the corresponding defences/countermeasures.
    \item \textit{Attack Graphs $\leftrightarrow$ Attack Trees} It would be interesting to explore the transformation of Attack Graphs to Attack Trees and vice versa. Pinchinat et al. are exploiting an Attack Graph to produce an Attack Tree~\cite{gtt}. This method can be explored further and tested to produce more concrete results regarding this transformation.
\end{itemize}

\subsection{Attack-Defense Trees}

\begin{figure}[]
\centering
\includegraphics[width=3.5in]{adt.pdf}
\caption{Attack-Defense Tree form ~\cite{adt}}
\label{fig:adt}
\end{figure}

Attack-Defense Trees are an extension of the Attack Trees. They consist of a root node, a set of actions an attacker might take to attack a system, and a set of defense mechanisms the defender can employ. On the Attack-Defense Trees, we have two kinds of nodes the attack nodes and the defend nodes, that both can be refined into sub-goals. Also, every node can have a child of the opposite type called countermeasure. One example of an Attack-Tree can be seen in Figure~\ref{fig:adt}~\cite{adt, kordy2014attack}.

We can observe in Figure~\ref{fig:adt} that the Attack-Defense Tree uses the same operators as the Attack-Tree. The example depicts a bank account attack. The attack can be achieved either from an ATM or online. We can see in the green rectangles the proposed defenses the defender can employ.

In the scope of this paper, we are not going to examine specifically the automatic generation of Attack-Defense Trees. It is an upcoming field and it is included in the future directions proposed at the end of the paper. We strongly believe that the automatic generation of Attack-Defense Trees can be the next step in the automatic generation of Attack-Trees/Graphs.

\section{Conclusion}\label{sec:con}
Graphical representation models are widely used in the security field to depict all possible attacks on a system. Two of the most common graphical representation models are Attack Trees and Attack Graphs. These structures provide a user-friendly representation for the security experts and in parallel, they constitute a useful tool for analyzing the systems under investigation. Designing these kinds of graphical representations by hand can be error-prone and tedious for security experts. Consequently, the research community turned their interest to find ways to automatically generate these structures. In this work, we present the state of the art of the automatic generation of Attack Models. We structured our survey to answer 3 research questions: \textbf{RQ1}, Which techniques are currently used in the field, \textbf{RQ2}, which of the seven dimensions introduced in Section~\ref{sec:cat} are being considered in each paper (experiment, scalability, code, mathematical proofs), \textbf{RQ3}, what kind of limitations we identified in the field. We answered \textbf{RQ1}, by classifying the papers into 7 different categories in Section~\ref{sec:class} and presenting the categories with the percentage of their population in Section~\ref{sec:over}. Following that, we answered \textbf{RQ2} in Section~\ref{sec:over}, giving an overview of how many papers included the corresponding dimensions and in Section~\ref{sec:class} we also present tables that show in detail which paper includes which parameters. Finally, taking everything into consideration we answer \textbf{RQ3} in Section~\ref{sec:lim} and Section~\ref{sec:class}, where we presented some limitations of each paper, of every category and finally general limitations/challenges we identified in the field that also constitute future directions for the research community. 

\section*{Acknowledgment}
This work has been supported by Innovation Fund Denmark and the Digital Research Centre Denmark, through the bridge project ``SIOT – Secure Internet of Things – Risk analysis in design and operation''.

\bibliographystyle{plain}
\balance
