# RAPT: A Robust Attack Path Tracing Algorithm to Mitigate SYN-Flood DDoS Cyberattacks
## 3 The Proposed Robust Attack Path Tracing Algorithm
### RAPT Algorithm Design
#### 3.3.1 At the Edge Router \(R_{i}\)  
In this subsection, a detailed discussion is provided on how the RAPT algorithm (see Algorithm 1) works on the edge router. Table 2 provides the notation used throughout the algorithm. In the RAPT algorithm, the edge routers periodically monitor two parameters, namely, (i) The relative change in frequency (\(\Delta f_{t}\)); and (ii) the cumulative mean of frequency (\(\mu f_{t}\)). Then, the edge router \(R_{i}\) performs the following steps:  
1. At the end of the current \(t\) period, the edge router compares \(\Delta f_{t}\) and \(\mu f_{t}\) (see Equations (1) and (2) below) against two thresholds \(\alpha\) and \(\beta\), respectively. If both are exceeding these two thresholds, this might indicate that the SYN traffic is malicious and a potential attack might be active. Therefore, the router must create a trace packet called _TracePack_, which will pass through all the routers between the victim and the attacker/daemon including edge and core routers. The enroute routers record their IP addresses on the payload of TracePack, which is used by the victim to extract the entire attack path: \[\Delta f_{t}=\frac{f_{t}-f_{t-1}}{f_{t-1}}\] (1) \[\mu f_{t}=\frac{f_{t-1}+\mu f_{t-1}}{n+1}\] (2)
2. Pick one of the SYN packets randomly named _RandPack_ from the incoming SYN traffic destined to the potential victim; 1. If the packet is a fragment, its identifier will be the value stored in the identification field of the IP header; 2. Otherwise, the unused identification field (set to 0) will be used such that the router generates a pseudo random number as a function of time to be used as an identifier for the packet and write it to the identification field; 3. \(R_{i}\) generates a trace packet called TracePack with the following information: 1. Source address being \(R_{i}\)s IP address; 2. Destination address is RandPack's destination address (victim's IP address); 3. Append to the payload of TracePack the source address of RandPack, identifier of RandPack, and \(R_{i}\)s IP address. The reason behind appending RandPack's ID field is because the next-hop router needs to recognize RandPack from other flowing packets. This is ensured by forwarding TracePack ahead of RandPack, which allows \(R_{j}\) to capture RandPack; 4. \(R_{i}\) sends TracePack to the next-hop \(R_{j}\) using hop-by-hop TCP connections [38] to guarantee the delivery of TracePack; 5. Upon receiving the acknowledgement of TracePack's arrival to \(R_{j}\), then \(R_{i}\) sends RandPack to the next-hop \(R_{j}\) similarly using hop-by-hop TCP connections.  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Meaning** \\ \hline \(\mathbb{Z}\) & HotSet of IP addresses to be monitored against SYN-Flood attacks. \\ \(f_{t}\) & Frequency of received SYN packets during period \(t\). \\ \(f_{t-1}\) & Frequency of received SYN packets during previous period \(t-1\). \\ \(\Delta f_{t}\) & Relative change in Frequency of SYN packets. \\ \(\mu f_{t}\) & Cumulative mean of Frequency in SYN packets. \\ \(R_{i}\) & Current router (edge or core). \\ \(R_{j}\) & Next-hop router towards the victim. \\ \(n\) & Number of observed periods. \\ \(\alpha\) & Threshold acceptable for \(\Delta f_{t}\). \\ \(\beta\) & Threshold acceptable for \(\mu f_{t}\). \\ \hline \hline \end{tabular}
\end{table}
Table 2: Notation used in the RAPT algorithm.