On monitoring and diagnosing classes of discrete event systems.

Abstract

This thesis addresses three detection and diagnosis problems for systems with event-driven dynamics. First, the diagnosis of intermittent faults in discrete event dynamic systems is considered. A modeling methodology for discrete event systems with intermittent faults is proposed. New notions of diagnosability that provide information about the status of intermittent faults at different levels of detail are introduced. Necessary and sufficient conditions for a system to be diagnosable under each notion are specified and proven. These conditions are based upon the known technique of diagnosers, with appropriate enhancements to capture the dynamic nature of faults in the system model. Secondly, this thesis studies the diagnosis of unobservable faults in large and complex discrete event systems modeled by parallel composition of automata. A modular approach is developed to mitigate the computational difficulties in diagnosing such systems. The notion of modular diagnosability is introduced and conditions that are necessary and sufficient to ensure it are identified. For verification purposes, a new algorithm that incrementally exploits the modular structure of the system to save on computational effort is designed. The correctness of the algorithm is proven. Online diagnosis of modularly diagnosable systems is achieved using only local diagnosers. Finally, this thesis addresses the longstanding and difficult problem of detecting and classifying spatially distributed network anomalies from multiple monitoring sites on the Internet. An event-driven hierarchical framework, based on multi-criteria decision making methodologies, is developed to detect anomalous behavior in large and distributed networks. The associated tool, which implements this framework, generates temporally and spatially-correlated risk indices for each anomaly with respect to certain types of network attacks (e.g., Worm and Denial-of-Service). The main goal of this approach is to help security experts to make fast decisions when anomalies occur in large numbers and with different intensities, which is often the case in the Internet.