With the rapid growth of computer networks, network security has become a crucial issue. The network intruders may use an SSH/Telnet to establish a connection session with the target machine. If directly connecting to the target machine, intruders' IP addresses are visible to the target. A common strategy to hide the intruders' true IP address is known as "stepping-stone intrusion." This strategy launches an intrusion by routing through a sequence of intermediate computers before reaching the target machine. In this dissertation, our goal is to detect stepping-stone intrusions.

One way to detect stepping-stone intrusion is to test if a host is used as part of a stepping-stone connection chain. The first algorithm we present avoids the traffic corruption by using a one-to-one mapping-based approach. The second detection algorithm based on association rule mining is presented in the presence of chaff and timing jitter perturbations. The experimental results and analysis show that these proposed algorithms have high detection rates and are able to resist intruders' evasions.

Finding out if two hosts belong to the same connection chain is another way to contribute to stepping-stone detection. If one suspects an attack originated from a particular host, one may correlate the connections to the target and the suspected host to confirm if they belong to the same chain without knowing much about other intermediate hosts. We propose several algorithms for detecting multi-hop stepping-stone hosts by using dynamic programming based pattern recognition techniques. According to the experimental results, our algorithms can detect stepping-stone attacks with a low time complexity, in the presence of clock skew and chaff.

Most of the detection algorithms above work well when there is a low chaff rate. However, if the chaff rate is high, the detection rate will deteriorate. We present a learning-based detection algorithm to detect chaff anomalies in a traffic stream. By coupling this chaff detection algorithm and the previous correlation-based algorithm, the combined algorithm makes it possible to identify a stepping-stone host in either circumstance.

With the algorithms designed in this dissertation, it is possible to identify intruders even when they use evasion techniques.