A key element in defending computer networks is to recognize the types of cyber attacks based on the observed malicious activities. Obfuscation onto what could have been observed of an attack sequence may lead to mis-interpretation of its effect and intent, leading to ineffective defense or recovery deployments. This work develops probabilistic graphical models to generalize a few obfuscation techniques and to enable analyses of the Expected Classification Accuracy (ECA) as a result of these different obfuscation on various attack models. Determining the ECA is a NP-Hard problem due to the combinatorial number of possibilities. This paper presents several polynomial-time algorithms to find the theoretically bounded approximation of ECA under different attack obfuscation models. Comprehensive simulation shows the impact on ECA due to alteration, insertion and removal of attack action sequence, with increasing observation length, level of obfuscation and model complexity.