Abstract: Anomaly detection is the major direction of research in intrusion detection. Presented in this paper is a new method for anomaly detection of program behaviors, which is applicable to host-based intrusion detection systems using system calls as audit data. The method constructs a one-order homogeneous Markov chain to represent the normal behavior profile of a privileged program, and associates the states of the homogeneous Markov chain with the unique system calls in training data. At the detection stage, the occurrence probabilities of the state sequences of the Markov chain are computed, and two different schemes can be used to determine whether the monitored program's behaviors are normal or anomalous while the particularity of program behaviors is taken into account. The method gives attention to both computational efficiency and detection accuracy. It is less computationally expensive than the method based on hidden Markov models introduced by Warrender et al, and is more applicable to on-line detection. Compared with the methods based on system call sequences presented by Hofmeyr and Forrest, the method in this paper can achieve higher detection accuracy. The study empirically demonstrates the promising performance of the method, and it has succeeded in getting application in practical host-based intrusion detection systems.