With the growing amount of cyber threats, the need for development of high-assurance cyber systems is becoming increasingly important. The objective of this paper is to address the challenges of modeling and detecting sophisticated network attacks, such as multiple interleaved attacks. We present the interleaving concept and investigate how interleaving multiple attacks can deceive intrusion detection systems. Using one of the important statistical machine learning (ML) techniques, Hidden Markov Models (HMM), we develop two architectures that take into account the stealth nature of the interleaving attacks, and that can detect and track the progress of these attacks. These architectures deploy a database of HMM templates of known attacks and exhibit varying performance and complexity. For performance evaluation, in the presence of multiple multi-stage attack scenarios, various metrics are proposed which include (1) attack risk probability, (2) detection error rate, and (3) the number of correctly detected stages. Extensive simulation experiments are used to demonstrate the efficacy of the proposed architectures.