Effective Algorithms to Detect Stepping-Stone Intrusion by Removing Outliers of Packet RTTs

In this section, we present an effective algorithm to detect SSI by mining network traffic using an improved version of the k-Means clustering approach. Our network experiment shows that when $k=2$ (i.e., all the RTTs are partitioned into exactly two clusters), our proposed detection algorithm for SSI works effectively, with an effective rate higher than 85.7% in the Internet environment. In this paper, the k-Means clustering approach is only applied when $k=2$ . The k-Means clustering approach is neither needed nor used in our proposed algorithm for other values of $k$ , as it does not work effectively when $k>2$ in the context of the Internet. The input of our proposed detection algorithm for SSI in this section is three datasets that were captured from distinct connection chains with two, three, or four connections. Our proposed detection algorithm can effectively output whether a possible intrusion is underway in the underlying network.

For the general k-Means clustering method, the main idea is to find the appropriate $k$ centers, one for each of the $k$ clusters. The $k$ centers need to be calculated and then updated in a smart way to minimize the final standard derivation calculated based on the updated $k$ centers in the last iteration of the algorithm. Refer to Ref. [ 32 ] regarding the k-Means algorithm and its implementation. A k-Means clustering algorithm is an appropriate option for clustering because of the unique characteristics of TCP packets. Legal applications are well-known for never using three or more intermediate hosts to access a remote server. Therefore, if a target host is accessed via three or more stepping-stones from another host, then it is highly possible that the session is being manipulated by a malicious hacker, and the target system is a potential victim host.

Now, we explain how to use the 2-Means clustering approach to detect SSI effectively. Consider three RTT datasets obtained from connection chains of length two, three, or four in the context of the Internet. We run the 2-Means clustering algorithm on these three RTT datasets. Intuitively, the output generated by the dataset collected from the connection chain of length two would produce the smallest standard derivation. On the basis of this intuition, for these three datasets, we may conclude that the dataset that produced the output with the smallest standard derivation was obtained from the connection chain of length two.

Let $P=\{p_1,p_2,\mathrm{\dots },p_n\}$ be a set of $n$ data points. Assume that $C=\{c_1,c_2,\mathrm{\dots },c_k\}$ is the set of $k$ centers that were found by the k-Means clustering algorithm. We partition P into $k$ disjoint subsets $p_1,p_2,\mathrm{\dots },p_k,$ where the data points in $p_j$ are associated with their nearest center $c_j$ in C for each $1⩽j⩽k$ by associating each point in $P$ with the nearest center in C. For each $1⩽j⩽k$ , let $p_j=\{p_{j_1},p_{j_2},\mathrm{\dots },p_{j_{|p_j|}}\}.$ The standard derivation $\sigma$ of the given dataset $P$ based on k-Means clustering is defined as the square root of its variance as follows:

(2) $$\sigma =\sqrt{\frac{1}{n}\underset{j=1}{\overset{k}{\sum }}\underset{i=1}{\overset{|Y_j|}{\sum }}{\Vert y_{j_i}-c_j\Vert }^2}$$

Let dataset-1, dataset-2, and dataset-3 denote the three RTT datasets obtained from three connection chains of distinct lengths of two, three, or four, respectively. Our proposed algorithm for SSI detection using the 2-Means clustering method can accurately determine which connection chain(s) are sessions possibly manipulated by malicious hackers. This detection algorithm for SSI is described in Algorithm 2.

Next, we explain Algorithm 2, which is used to detect possible SSI. In Step 1, the 2-Means clustering algorithm is called on dataset-1. The procedure is as follows.

Initially, we randomly select two points in the set $P$ as the two centers for the clustering algorithm that executes the steps below:

(1) To generate the two clusters, each point in $P$ is scanned and assigned to the cluster center whose distance from the cluster center is the minimum between both cluster centers;

(2) Calculate the standard derivation ${\sigma }_{\text{curr}}$ using the current partition and cluster centers according to Eq. ( 2 );

(3) For each cluster, recompute the new center, which is the average of the data points in the cluster;

(4) Use the new cluster centers to reproduce the two clusters following the same procedure described in the above Step (1);

(5) Recompute the standard derivation ${\sigma }_{\text{new}}$ using the updated partition and cluster centers according to Eq. ( 2 );

(6) If ${\sigma }_{\text{new}}⩾{\sigma }_{\text{curr}},$ then Exit; otherwise, repeat Step (3).

When the 2-Means clustering algorithm exits, the standard derivation is minimized using the cluster centers and partition obtained in the last round of the clustering algorithm. Thus, at the end of the algorithm execution, the standard derivation can no longer be reduced by changing the centers of each cluster. According to Eq. ( 2 ), the value of ${\sigma }_1$ is the standard derivation obtained using the two clusters obtained in the last iteration of the 2-Means clustering algorithm.

Similarly, the 2-Means clustering algorithm is called on dataset-2 and dataset-3, respectively, at Steps 2 and 3 of the algorithm. Then, the standard derivations ${\sigma }_2$ and ${\sigma }_3$ are in turn calculated.

If ${\sigma }_1$ is the minimum among the three values ${\sigma }_1,{\sigma }_2,$ and ${\sigma }_3,$ then dataset-2 and dataset-3 are sessions possibly manipulated by malicious hackers. Similarly, if ${\sigma }_2$ is the minimum, then dataset-1 and dataset-3 are sessions possibly manipulated by malicious hackers. If ${\sigma }_3$ is the minimum, then dataset-1 and dataset-2 are sessions possibly manipulated by malicious hackers. Therefore, this algorithm can effectively determine which connection chain(s) are sessions possibly manipulated by hackers.

In this section, we present an effective algorithm to detect SSI by mining network traffic using an improved version of the k-Means clustering approach. Our network experiment shows that when $k=2$ (i.e., all the RTTs are partitioned into exactly two clusters), our proposed detection algorithm for SSI works effectively, with an effective rate higher than 85.7% in the Internet environment. In this paper, the k-Means clustering approach is only applied when $k=2$ . The k-Means clustering approach is neither needed nor used in our proposed algorithm for other values of $k$ , as it does not work effectively when $k>2$ in the context of the Internet. The input of our proposed detection algorithm for SSI in this section is three datasets that were captured from distinct connection chains with two, three, or four connections. Our proposed detection algorithm can effectively output whether a possible intrusion is underway in the underlying network.

For the general k-Means clustering method, the main idea is to find the appropriate $k$ centers, one for each of the $k$ clusters. The $k$ centers need to be calculated and then updated in a smart way to minimize the final standard derivation calculated based on the updated $k$ centers in the last iteration of the algorithm. Refer to Ref. [ 32 ] regarding the k-Means algorithm and its implementation. A k-Means clustering algorithm is an appropriate option for clustering because of the unique characteristics of TCP packets. Legal applications are well-known for never using three or more intermediate hosts to access a remote server. Therefore, if a target host is accessed via three or more stepping-stones from another host, then it is highly possible that the session is being manipulated by a malicious hacker, and the target system is a potential victim host.

Now, we explain how to use the 2-Means clustering approach to detect SSI effectively. Consider three RTT datasets obtained from connection chains of length two, three, or four in the context of the Internet. We run the 2-Means clustering algorithm on these three RTT datasets. Intuitively, the output generated by the dataset collected from the connection chain of length two would produce the smallest standard derivation. On the basis of this intuition, for these three datasets, we may conclude that the dataset that produced the output with the smallest standard derivation was obtained from the connection chain of length two.

Let $P=\{p_1,p_2,\mathrm{\dots },p_n\}$ be a set of $n$ data points. Assume that $C=\{c_1,c_2,\mathrm{\dots },c_k\}$ is the set of $k$ centers that were found by the k-Means clustering algorithm. We partition P into $k$ disjoint subsets $p_1,p_2,\mathrm{\dots },p_k,$ where the data points in $p_j$ are associated with their nearest center $c_j$ in C for each $1⩽j⩽k$ by associating each point in $P$ with the nearest center in C. For each $1⩽j⩽k$ , let $p_j=\{p_{j_1},p_{j_2},\mathrm{\dots },p_{j_{|p_j|}}\}.$ The standard derivation $\sigma$ of the given dataset $P$ based on k-Means clustering is defined as the square root of its variance as follows:

(2) $$\sigma =\sqrt{\frac{1}{n}\underset{j=1}{\overset{k}{\sum }}\underset{i=1}{\overset{|Y_j|}{\sum }}{\Vert y_{j_i}-c_j\Vert }^2}$$

Let dataset-1, dataset-2, and dataset-3 denote the three RTT datasets obtained from three connection chains of distinct lengths of two, three, or four, respectively. Our proposed algorithm for SSI detection using the 2-Means clustering method can accurately determine which connection chain(s) are sessions possibly manipulated by malicious hackers. This detection algorithm for SSI is described in Algorithm 2.

Next, we explain Algorithm 2, which is used to detect possible SSI. In Step 1, the 2-Means clustering algorithm is called on dataset-1. The procedure is as follows.

Initially, we randomly select two points in the set $P$ as the two centers for the clustering algorithm that executes the steps below:

(1) To generate the two clusters, each point in $P$ is scanned and assigned to the cluster center whose distance from the cluster center is the minimum between both cluster centers;

(2) Calculate the standard derivation ${\sigma }_{\text{curr}}$ using the current partition and cluster centers according to Eq. ( 2 );

(3) For each cluster, recompute the new center, which is the average of the data points in the cluster;

(4) Use the new cluster centers to reproduce the two clusters following the same procedure described in the above Step (1);

(5) Recompute the standard derivation ${\sigma }_{\text{new}}$ using the updated partition and cluster centers according to Eq. ( 2 );

(6) If ${\sigma }_{\text{new}}⩾{\sigma }_{\text{curr}},$ then Exit; otherwise, repeat Step (3).

When the 2-Means clustering algorithm exits, the standard derivation is minimized using the cluster centers and partition obtained in the last round of the clustering algorithm. Thus, at the end of the algorithm execution, the standard derivation can no longer be reduced by changing the centers of each cluster. According to Eq. ( 2 ), the value of ${\sigma }_1$ is the standard derivation obtained using the two clusters obtained in the last iteration of the 2-Means clustering algorithm.

Similarly, the 2-Means clustering algorithm is called on dataset-2 and dataset-3, respectively, at Steps 2 and 3 of the algorithm. Then, the standard derivations ${\sigma }_2$ and ${\sigma }_3$ are in turn calculated.

If ${\sigma }_1$ is the minimum among the three values ${\sigma }_1,{\sigma }_2,$ and ${\sigma }_3,$ then dataset-2 and dataset-3 are sessions possibly manipulated by malicious hackers. Similarly, if ${\sigma }_2$ is the minimum, then dataset-1 and dataset-3 are sessions possibly manipulated by malicious hackers. If ${\sigma }_3$ is the minimum, then dataset-1 and dataset-2 are sessions possibly manipulated by malicious hackers. Therefore, this algorithm can effectively determine which connection chain(s) are sessions possibly manipulated by hackers.