This paper examines the issues involved with responding to complex Internet attacks. Such attacks characteristically occur in stages over extended periods of time and allow specific actions in a particular stage to be interchangeable. The stages can be extremely difficult to correlate because they are separated in time, and these effects can be deliberately obscured to achieve the goals of the attacker. We have chosen an approach to intrusion detection using Hidden Markov Models (HMMs) that explicitly addresses these issues. As part of our research we also developed a methodology for labeling examples that reduced the effort involved from that of labeling thousands of training examples to that of labeling less than two hundred feature values. When compared with two classic machine learning algorithms, decision trees and neural nets, the HMM algorithm provides an approximately five-% performance advantage over the decision tree algorithm, and at least a thirty % advantage over neural nets, at all training levels. The HMM performance advantage over decision trees is shown to increase as the complexity of the attack increases. The HMM performance advantage also increases as the number of training examples decreases. This last result indicates that the HMM algorithm may have additional benefit when examples of a particular attack type are rare.