% path impl

This module has the goal to solve the hard challenge to find, in a complex graph structure, all the filtering points crossed by each pattern traffic that has a match with one or more security rules.

\subsection{Graph traversal}

In computer science, graph traversal, also known as graph search, refers to the process of visiting (checking and/or updating) each vertex in a graph~\cite{graph-traversal}.\newline

The graph model is represented as a connected graph $G = (V,E)$ with directional edges, the algorithm starts from a specific vertex and it explores all the the incident outgoing edges and vertices at the end of them. If the node is not found, the previous steps are repeated starting from a different vertex until all the nodes are visited.\newline

This process has a significant computational cost expressed as $O(V(E+V))$, which could be reduced to $O(E+V)$ if the \textit{Kosaraju's Strongly Connected Component Algorithm} is used.

\subsection{Depth-first search}

The \textit{Depth-first search} (DFS) is a traversing algorithm for graph and tree data structures. The process starts from the root vertex, which is chosen randomly in case of a graph, and for all the branches it explores as far as possible along the chosen one until backtracking.

The pseudo-code example of a recursive implementation is reported below.

\hfill

\begin{algorithm}[H]
	\SetAlgoLined
			
	\KwIn{G \Comment{the graph}} 
	\KwIn{v \Comment{a vertex of the graph}} 
	$\;$\\
	\Begin{
		
		label $v$ as ``discovered''
		
		\If{v is the goal}{
			return $v$;
		}
	
		\Comment{exploring this branch}\\
			
		\ForAll{ directed edges from v to w that are in G.adjacentEdges(v)}{
			$\;$\\
			\If{w is the goal}{
				return $w$;
			}
			$\;$\\
			\If{vertex w is not labeled as discovered}{
				recursively call DFS(G, w)
			}
		}
	}
	\caption{Depth-first search - DFS(G, v)}
	
\end{algorithm}
\clearpage

\subsection{Breadth-first search}

The Breadth-first search (BFS) is the other searching algorithm for the tree ad graph data\break structures. Its approach is the opposite of the previous one, because, instead of exploring\break completely a branch before backtracking, it explores all the neighbour nodes at the current depth and then passes to the following level of depth.

The pseudo-code example of a recursive implementation is reported below:

\begin{algorithm}[H]
	\SetAlgoLined
	
	\KwIn{G \Comment{the graph}} 
	\KwIn{v \Comment{a vertex of the graph}} 
	$\;$\\
	\Begin{
		
		define $Q$ as a queue \\
		label $v$ as ``discovered'' \\
		$\;$\\
		
		$Q.enqueue(v)$ 
		
		$\;$\\
		
		\If{v is the goal}{
			return $v$;
		}
		
		\Comment{exploring this depth level}\\
		
		\ForAll{ q in the Q queue}{
			
			$w \gets Q.dequeue()$
			
			$\;$\\
			
			\If{w is the goal}{
				return $w$;
			}
			
			\Comment{adding the following level vertex to the queue}\\
			
			\ForAll{ directed edges from w to k that are in G.adjacentEdges(w)}{
				
				\If{vertex w is not labeled as discovered}{
					
					label $k$ as discovered
					
					$k.parent \gets w$
					$Q.enqueue(k)$
				
				}
			}
		}
	}
	\caption{Breadth-first search - BFS(G, v)}
	
\end{algorithm}

\subsection{Pruning approach}

The analysis of the previous algorithms leads to prefer the \textit{Depth-first search} as the one to be implemented. This chosen is done because of the intrinsic data structure that is going to represent the cloud deployment.

In the networking world the tree structure is preferred over a graph representation to avoid loop cycle and black holes and, as is explained in Section~\ref{sec:path_model}, the physical topology on which this thesis work is based is structured as a tree.
Moreover not all the vertexes of the tree could be the goal of the traversal process, because only leafs are a potential target for the traffic and for this reason also for the algorithm. The DFS is in most of the cases faster than the BFS algorithm because, the last one explores the potential vertex only at the end of process, instead of the former algorithm.

Neverless the DFS is the best choice in this environment, the computational cost still remain $O(E+V)$ and it is too much time expensive. 
The decision taken is to follow the \textit{pruning} approach for the algorithm to have a faster searching process and to reduce the size of decision trees by removing some sections of the data structure.
\clearpage

The pruning allows the algorithm to avoid the exploration of complete branches of the tree, this means that the step of backtracking is not more contemplated in the algorithm, but it starts to examine a section if there is the target node on that branch.
The optimization of the searching time has a side effect, because each vertex has to store additional informations, in particular it has to provide what nodes are its children and what are reachable from the parent node. In this way each node is able to know the right direction to take to get the goal vertex.

The process to create a traffic path is divided into several steps:

\begin{itemize}
	\item 
	to find the starting points: the process starts from the \textit{root} element and search all the nodes where a specific traffic pattern could be generated;
	
	\item
	to find the ending points: the process, as the previous step, starts from the \textit{root} element, and it explores with the pruning DFS algorithm the tree structure to retrieve all the nodes where the packets could be intended;
	
	\item
	to find the filtering points: starting from one of the nodes, which could generate the traffic, the process begins looking for how to reach any end points. If the current node is a potential destination node the path process ends, returning as the only filtering point the node where the procedure starts.
	Otherwise the algorithm searches between the children nodes and the parent destinations, any nodes that could match with this type of traffic.
\end{itemize}

The number of leafs in a cloud environment could be huge, and a linear search $O(n)$ to find a match for each vertex is too time consuming. For this reason the \textit{condition clause} notation is introduced to have a constant $O(1)$ matching.
It is used to refer, in security context, to the rule fields forming the clause that match the packet.

Here it has a new utilization, because each node has two condition clause, except the leafs vertex and the root element that they just have one, which are used to check in a unique operation the children nodes and the parent's one.

In this way each intermediate node has a \textit{child} condition clause, which is the union of the children condition clauses, and another one called \textit{father} condition clause that has all the condition clauses coming from the parent node.

Finally the algorithm behaves in two ways based on the $a \in \mathcal{A}$ action performed by the current rule and the $d \in \mathcal{A}$ default action enforced.

\begin{itemize}
	\item 
	deny action: in case the rule action is equivalent to a \textit{deny} action, this filtering rule has to be enforced at least in one place from the node that generates the traffic and the one that receives the packets. The path finder process (Algorithm~\ref{alg:pruning1}) starts from the first nodes and it continues until the ending point, unless it found a fork in the path. This means the traffic could takes different paths from this point forward, here the process stops and return all the point found, include this last one;
	
	\item
	allow action: if the rule action is \textit{allow} action, the behave of the Algorithm~\ref{alg:pruning2} is quite different. It acts like the previous one until it reaches a fork in the path, here recursively explores all the branches of the fork found as far as it reaches all the nodes that matches. The reason is to maintain reachability between nodes that the other way could not be achieved.
\end{itemize}
\clearpage

\resizebox{0.97\textwidth}{!}{
\begin{algorithm}[H]
	\SetAlgoLined
	
	\KwIn{G \Comment{the graph}} 
	\KwIn{v \Comment{a vertex of the graph}} 
	\KwIn{start \Comment{condition clause that identify the starting point}}
	\KwIn{end \Comment{condition clause that identify the ending point}}
	
	\Begin{
		define $L$ as the list of node that matches the ``end'' condition clauses 
		
		\If{v.matchConditionClause(end)}{
			return $v$; \Comment{v is a leaf node}
		}
		$\;$\\
		$L.addAll(v.childrenNodesMatching(end));$
		
		\If{L.size() $>$ 1}{
			return $v$; \Comment{a fork is found - process stop}
		}
		
		\If{L.size() $=$ 1}{
			return v, PS(G, L.get(0), start, end); \Comment{recursively call PS()}
		}
		$\;$\\
		$L.addAll(v.fatherNodesMatching(end));$
		
		\If{L.size() $>$ 1}{
			return $v$; \Comment{a fork is found - process stop}
		}
		
		\If{L.size() $=$ 1}{
			return v, PS(G, L.get(0), start, end); \Comment{recursively call PS()}
		}
		
	}
	\caption{Pruning search - deny action PS(G, v, start, end)}
	\label{alg:pruning1}
\end{algorithm}
}

\resizebox{0.97\textwidth}{!}{
\begin{algorithm}[H]
	\SetAlgoLined
	
	\KwIn{G \Comment{the graph}} 
	\KwIn{v \Comment{a vertex of the graph}} 
	\KwIn{start \Comment{condition clause that identify the starting point}}
	\KwIn{end \Comment{condition clause that identify the ending point}}
	
	\Begin{
		define $L$ as the list of node that matches the ``end'' condition clauses 
		define $R$ as the list of node to return 
		
		\If{v.matchConditionClause(end)}{
			return $v$; \Comment{v is a leaf node}
		}
		$\;$\\
		$L.addAll(v.childrenNodesMatching(end));$
		
		\If{L.size() $>$ 0}{
		
			\ForAll{ w in the L list}{
				$R.addAll(PS(G, w, start, end))$
			}
			
			$R.add(v);$
			
			return $R$;
		}
		
		$\;$\\
		$L.addAll(v.fatherNodesMatching(end));$
		
		\If{L.size() $>$ 0}{
			
			\ForAll{ w in the L list}{
				$R.addAll(PS(G, w, start, end))$
			}
			
			$R.add(v);$
			
			return $R$;
		}
		
	}
	\caption{Pruning search - allow action PS(G, v, start, end)}
	\label{alg:pruning2}
\end{algorithm}
}

\subsection{Topology Graph - XSD schema}

The physical topology is represented as graph, in particular as previous specified, it is a tree structure. The XSD schema is used to define the structure of each element that takes part in this representation and to delineate constraints.

The XML file allows to specify the type of \code{VIM = \{OPENSTACK, KUBERNETES\}} which is running on the machines, the metric type to be optimized \code{performanceType = \{LATENCY, BANDWIDTH, CPU_CONSUMPTION\}} then a list of nodes.

\begin{figure}[H]
	\HRule
\begin{lstlisting}[numbers=left,stepnumber=1, style=XML]
<xsd:element name="Deployment">
	<xsd:complexType>
		<xsd:sequence>
			<xsd:element name="Host" type="HostElement" minOccurs="1" maxOccurs="unbounded"/>
		</xsd:sequence>
		
		<xsd:attribute name="VIM" type="VIMElement" use="required"/>
		<xsd:attribute name="PerformanceType" type="PerformanceTypeElement" default="LATENCY"/>
	</xsd:complexType>
</xsd:element>
	
\end{lstlisting}
	\HRule
	%\caption{z3 used as library in a Java project.
		%\label{fig:z3-code}}
\end{figure}

Each graph element is called ``Deployment'' and it is composed by a set of \textit{node} elements, each one represents a physical machines in the cluster.
Each \textit{node} is characterized by:

\begin{itemize}
	\item 
	\textit{IP}: it is the IP address of the server;
	\item
	\textit{SecurityUserName}: it is the the username of the network admin manager;
	\item
	\textit{NetworkNode}: it is a boolean variable in which the \textit{true} value means that this node is responsible for the networking, otherwise it is only a compute node;
	\item
	\textit{coefficient, offset, maxNumRules}: they are parameters for the optimization model;
	\item
	\textit{switch list}: it is a list of virtual switches.
	
\end{itemize}

\begin{figure}[H]
	\HRule
\begin{lstlisting}[numbers=left,stepnumber=1, style=XML]
<xsd:complexType name="HostElement">
	<xsd:sequence>
		<xsd:element name="vSwitch" type="vSwitchElement" minOccurs="1" maxOccurs="unbounded"/>
	</xsd:sequence>
	
	<xsd:attribute name="SecurityUserName" type="xsd:string" use="required"/>
	<xsd:attribute name="IP" type="IPElement" use="required"/>
	<xsd:attribute name="NetworkNode" type="xsd:boolean" use="required"/>
	<xsd:attribute name="coefficient" type="xsd:decimal"/>
	<xsd:attribute name="offset" type="xsd:decimal"/>
	<xsd:attribute name="maxNumRules" type="xsd:integer"/>
</xsd:complexType>

\end{lstlisting}
	\HRule
	%\caption{z3 used as library in a Java project.
	%\label{fig:z3-code}}
\end{figure}
\clearpage

Each \textit{vSwitchElement} it is a node of the graph that is characterized by the same elements of the node \textit{HostElement}, but it contains a list of different node types, \textit{vRouterElement} and \textit{NodeElement}, furthermore it has a type that could be chosen from the enumeration \code{vSWTypeElement = \{OVS, LINUXBRIDGE\}}.

The former is a virtual router that could be instantiated only in a ``NetworkNode'', it is characterized by:
\begin{itemize}
	\item 
	\textit{Label}: it is the identifier of the router, which must be unique;
	\item
	\textit{interface list}: a list of interfaces, each one with an IP address.
\end{itemize}

\begin{figure}[H]
	\HRule
\begin{lstlisting}[numbers=left,stepnumber=1, style=XML]
<xsd:complexType name="vRouterElement">
	<xsd:sequence>
		<xsd:element name="Interface" type="InterfaceElement" minOccurs="1" maxOccurs="unbounded"/>
	</xsd:sequence>
	<xsd:attribute name="Label" type="xsd:string" use="required"/>
</xsd:complexType>

\end{lstlisting}
	\HRule
	%\caption{z3 used as library in a Java project.
	%\label{fig:z3-code}}
\end{figure}

The latter is called ``NodeElement'', which is the basic element of the topology, it is\break characterized by its type \code{NodeTypeElement = \{VM, POD\}} and it represents the unit where the services will be deployed on.

Each \textit{NodeElement} is characterized by:

\begin{itemize}
	\item
	\textit{NodeType}: it represents the type of the service node;
	\item 
	\textit{IP}: it is the IP address of the server;
	\item
	\textit{SecurityUserName}: it is the the username of the network admin manager;
	\item
	\textit{coefficient, offset, maxNumRules}: they are parameters for the optimization model;
	
\end{itemize}

\begin{figure}[H]
	\HRule
	\begin{lstlisting}[numbers=left,stepnumber=1, style=XML]
<xsd:complexType name="NodeElement">
	<xsd:attribute name="NodeType" type="NodeTypeElement" use="required"/>
	<xsd:attribute name="SecurityUserName" type="xsd:string" use="required"/>
	<xsd:attribute name="IP" type="IPElement" use="required"/>
	<xsd:attribute name="coefficient" type="xsd:decimal"/>
	<xsd:attribute name="offset" type="xsd:decimal"/>
	<xsd:attribute name="maxNumRules" type="xsd:integer"/>
</xsd:complexType>
	\end{lstlisting}
	\HRule
	%\caption{z3 used as library in a Java project.
	%\label{fig:z3-code}}
\end{figure}
\clearpage

A complete example of an XML file representing a physical topology is provided in the Listing \ref{list:xml_physical} and the picture (Figure \ref{fig:xml_physical}) shows the graphical representation.

\hfill
\begin{figure}[ht]
	\HRule
	\begin{lstlisting}[numbers=left,stepnumber=1, style=XML]
<Deployment xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:noNamespaceSchemaLocation="xml_physical_network.xsd" VIM="OPENSTACK">

	<Host NetworkNode="true" IP="192.168.0.102" coefficient="6.87" offset="275" SecurityUserName="admin">
		
		<vSwitch External="false" Label="SW1" vSWType="OVS" coefficient="0.5" offset="100">
			
			<Node NodeType="VM" IP="10.0.0.56" SecurityUserName="admin1" coefficient="7" offset="300"/>
			<Node NodeType="VM" IP="20.0.0.38" SecurityUserName="admin2"/>
			
			<Router Label="R1">
				<Interface Name="eth0" IP="10.0.0.1"/>
				<Interface Name="eth0" IP="20.0.0.1"/>
			</Router>
			
			<Router Label="R2">
				<Interface Name="eth0" IP="30.0.0.1"/>
				<Interface Name="eth0" IP="40.0.0.1"/>
			
			</Router>
		</vSwitch>
		
		<vSwitch External="true" Label="SW-EXT" vSWType="LINUXBRIDGE" maxNumRules="3000"></vSwitch>
	</Host>
	
	<Host NetworkNode="false" IP="192.168.0.103" SecurityUserName="admin">
		
		<vSwitch External="false" Label="SW2" vSWType="OVS">
			
			<Node NodeType="VM" IP="30.0.0.100" SecurityUserName="admin3"/>
			<Node NodeType="VM" IP="40.0.0.3" SecurityUserName="admin4"/>
		
		</vSwitch>
	</Host>

</Deployment>
	\end{lstlisting}
	\HRule
	\caption{XML file describing a physical topology.
	\label{list:xml_physical}}
\end{figure}
\clearpage 

\begin{figure}[H]
	\centerline{\includegraphics[width=1\textwidth]
		{physical_topology.png}}
	\caption{Graphical representation of the physical topology described in XML file.
		\label{fig:xml_physical}}
\end{figure}