A novel method for detecting anomalous program behavior is presented, which is applicable to host-based intrusion detection systems that monitor system call activities. The method constructs a homogeneous Markov chain model to characterize the normal behavior of a privileged program, and associates the states of the Markov chain with the unique system calls in the training data. At the detection stage, the probabilities that the Markov chain model supports the system call sequences generated by the program are computed. A low probability indicates an anomalous sequence that may result from intrusive activities. Then a decision rule based on the number of anomalous sequences in a locality frame is adopted to classify the program’s behavior. The method gives attention to both computational effciency and detection accuracy, and is especially suitable for on-line detection. It has been applied to practical host-based intrusion detection systems. A novel method for detecting anomalous program behavior is presented, which is applicable to host-based intrusion detection systems that monitor system call activities. The method constructs a homogeneous Markov chain model to characterize the normal behavior of a privileged program, and associates the states of the markov chain with the unique system calls in the training data. At the detection stage, the probabilities that the Markov chain model supports the system call sequences generated by the program are computed. A low probability indicates an anomalous sequence that may result from intrusive activities . The method gives attention to both computational effciency and detection accuracy, and is especially suitable for on-line detection. It has been applied to practical host-based intrusion detection systems.