Cyber criminals often use a sequence of intermediate "stepping-stone" hosts to attack a target machine in order to maintain anonymity. This type of attack of using a connection chain is called stepping-stone attack. Most existing algorithms to detect such attack is to use timing-based correlation on the connections. However, these timing-based approaches are vulnerable if the intruders add chaff packets to evade the detection. The stepping-stone detection rate decreases as the chaff rate increases. We developed a novel anomaly detection algorithm to detect the presence of chaff in a connection by monitoring the packet inter-arrival times. Our study shows the probability distribution of the inter-arrival time of a chaffed connection differs from that of one without chaff. Our experiments show the detection rate as a function of the chaff rate under a variety of complex circumstances. The new algorithm complements the existing correlation-based stepping-stone detection algorithms in providing a more robust solution to stepping-stone detection.