Automated diagnosis has always been a challenging task to AI. When model-based diagnosis is adopted, a model of the system is required in order to generate a set of diagnoses based on a collection of observations, where a diagnosis is a set of faulty components or, more generally, a set of faults ascribed to components. An active system (AS) is an asynchronous, distributed discrete-event system, whose model consists of a topology (how components are connected to one another), and a communicating automaton for each component (the mode in which a component reacts to events). A problem afflicting all model-based approaches to diagnosis is a possibly large number of diagnoses explaining the observations, which may jeopardize the task of a diagnostician in charge of monitoring the system, owing to the cognitive overload raised by an overwhelming number of faulty scenarios to examine. This is exacerbated in critical application domains, where, under uncertain conditions, an artificial agent is supposed to perform recovery actions in real-time, even in the order of milliseconds, to possibly restore the system. To make diagnosis of ASs viable in critical, real-time application domains, a Smart Diagnosis Engine is presented, which is grounded on two heuristics: (1) if a diagnosis δ is a superset of a diagnosis δ ' , then δ is ignored (minimality); (2) if the cardinality (number of faults) of a diagnosis δ is lower than the cardinality of a diagnosis δ ' , then δ is generated before δ ' (sorting). Consequently, the diagnosis output consists in a sequence of minimal diagnoses that are generated in ascending order by cardinality. As indicated by the experimental results, the overall improvement is twofold: most likely diagnoses are generated upfront, thereby supporting real-time recovery actions; also, the abductive search in the behavior space of the AS is reduced considerably, owing to the pruning of the trajectories that will not generate minimal diagnoses, thereby resulting in an impressive reduction in both memory allocation and processing time.

Model-based diagnosis has always been conceived as set-oriented, meaning that a candidate is a set of faults, or faulty components, that explains a collection of observations. This perspective applies equally to both static and dynamical systems. Diagnosis of discrete-event systems (DESs) is no exception: a candidate is traditionally a set of faults, or faulty events, occurring in a trajectory of the DES that conforms with a given sequence of observations. As such, a candidate does not embed any temporal relationship among faults, nor does it account for multiple occurrences of the same fault. To improve diagnostic explanation and support decision making, a sequence-oriented perspective to diagnosis of DESs is presented, where a candidate is a sequence of faults occurring in a trajectory of the DES, called a fault sequence. Since a fault sequence is possibly unbounded, as the same fault may occur an unlimited number of times in the trajectory, the set of (output) candidates may be unbounded also, which contrasts with set-oriented diagnosis, where the set of candidates is bounded by the powerset of the domain of faults. Still, a possibly unbounded set of fault sequences is shown to be a regular language, which can be defined by a regular expression over the domain of faults, a property that makes sequence-oriented diagnosis feasible in practice. The task of monitoring-based diagnosis is considered, where a new candidate set is generated at the occurrence of each observation. The approach is based on three different techniques: .1/ blind diagnosis, with no compiled knowledge, .2/ greedy diagnosis, with total knowledge compilation, and .3/ lazy diagnosis, with partial knowledge compilation. By knowledge we mean a data structure slightly similar to a classical DES diagnoser, which can be generated (compiled) either entirely offline (greedy diagnosis) or incrementally online (lazy diagnosis). Experimental evidence suggests that, among these techniques, only lazy diagnosis may be viable in non-trivial application domains.

Abstract A finite automaton can be either deterministic (DFA) or nondeterministic (NFA). An automaton‐based task is in general more efficient when performed with a DFA rather than an NFA. For any NFA there is an equivalent DFA that can be generated by the classical Subset Construction algorithm. When, however, a large NFA may be transformed into an equivalent DFA by a series of actions operating directly on the NFA, Subset Construction may be unnecessarily expensive in computation, as a (possibly large) deterministic portion of the NFA is regenerated as is, a waste of processing. This is why a conservative algorithm for NFA determinization is proposed, called Quick Subset Construction, which progressively transforms an NFA into an equivalent DFA instead of generating the DFA from scratch, thereby avoiding unnecessary processing. Quick Subset Construction is proven, both formally and empirically, to be equivalent to Subset Construction, inasmuch it generates exactly the same DFA. Experimental results indicate that, the smaller the number of repair actions performed on the NFA, as compared to the size of the equivalent DFA, the faster Quick Subset Construction over Subset Construction.

The majority of websites incorporate JavaScript for client-side execution in a supposedly protected environment. Unfortunately, JavaScript has also proven to be a critical attack vector for both independent and state-sponsored groups of hackers. On the one hand, defenders need to analyze scripts to ensure that no threat is delivered and to respond to potential security incidents. On the other, attackers aim to obfuscate the source code in order to disorient the defenders or even to make code analysis practically impossible. Since code obfuscation may also be adopted by companies for legitimate intellectual-property protection, a dilemma remains on whether a script is harmless or malignant, if not criminal. To help analysts deal with such a dilemma, a methodology is proposed, called JACOB, which is based on five steps, namely: (1) source code parsing, (2) control flow graph recovery, (3) region identification, (4) code structuring, and (5) partial evaluation. These steps implement a sort of decompilation for control flow fattened code, which is progressively transformed into something that is close to the original JavaScript source, thereby making eventual code analysis possible. Most relevantly, JACOB has been successfully applied to uncover unwanted user tracking and fingerprinting in e-commerce websites operated by a well-known Chinese company.

Discrete-event knowledge (DEK) consists in a variety of automaton-based data structures which are generated by knowledge-based and engineering systems, including intelligent diagnosis systems. Model-based diagnosis methods for discrete-event systems (DESs) are typically supported by large automata that allow for the efficient generation of the candidate diagnoses when the DES is being operated. However, the generation of the DEK may involve a determinization step, where a nondeterministic finite automaton (NFA) is transformed into an equivalent deterministic finite automaton (DFA) by means of the classical Subset Construction algorithm. When this determinization is performed online and the NFA is large, the diagnosis engine may slow down to such an extent that the entire diagnosis task is jeopardized. This is why a novel determinization algorithm is proposed, called Quick Subset Construction, which, instead of generating from scratch the equivalent DFA, removes the nondeterminism by operating directly on the NFA. This way, the larger the NFA and the smaller the portion of nondeterminism involved, the faster Quick Subset Construction will be over Subset Construction. Massive experimentation on large automata has confirmed this result empirically.

An active system (AS) is a discrete-event system (DES) with asynchronous behavior, which is represented by a network of components that are modeled as communicating automata. When being operated, an AS performs a trajectory within its behavior space, while generating a sequence of observations, namely a temporal observation. The model of the AS and a temporal observation are the two key ingredients of the diagnosis task, which aims to find out possible faulty behavior via abductive reasoning. Among other knowledge, such reasoning requires knowing what is observable and what is not. This essential distinction constitutes the observability of the AS. In the literature, the observability of a DES boils down to qualifying each state transition either as observable or unobservable, which contrasts with the way humans observe reality, typically by mapping a collection of observations to a single, abstract perception. Moreover, the occurrence of single state transitions is not necessarily what we can observe or what we want to observe for diagnosis purposes. This paper presents an extended notion of observability, where each observation is associated with a behavioral scenario rather than a single state transition, where a scenario is defined as a regular language on state transitions. To speed up the online diagnosis engine, specific diagnosis-oriented knowledge is compiled offline. Eventually, the diagnosis technique based on abstract observability is extended to cope with temporal uncertainty.

Model-based diagnosis of discrete-event systems (DESs) generates a set of candidates upon the reception of a temporal observation. In the literature, a candidate is a set of faults produced by a trajectory of the DES that is consistent with the temporal observation. As such, a candidate does not convey any temporal relationship between faults, nor does it account for multiple occurrences of the same fault. To overcome the limitations of this set-oriented approach to diagnosis of DESs, the novel notions of temporal fault and temporal diagnosis are proposed, along with two diagnosis techniques. A temporal fault is the (possibly unbounded) sequence of faults produced by a trajectory. A temporal diagnosis is a (possibly infinite) set of temporal faults. Hence, in this new temporal-oriented approach to diagnosis of DESs, a candidate is a temporal fault. The fact that a temporal diagnosis turns out to be a regular language is key to coping with the infinity of candidates, which can be represented by a regular expression. The diagnosis task can be performed either by restricting the DES space to the trajectories that are consistent with the temporal observation, or by exploiting a temporal diagnoser which allows for fast online diagnosis. The claim of this paper is that the extra temporal information embedded in candidates may be essential in taking critical decisions based on the diagnosis results.

Since its appearance in AI, model-based diagnosis is intrinsically set-oriented. Given a sequence of observations, the diagnosis task generates a set of diagnoses, or candidates, each candidate complying with the observations. What all the approaches in the literature have in common is that a candidate is invariably a set of faulty elements (components, events, or otherwise). In this paper, we consider a posteriori diagnosis of discrete-event systems (DESs), which are described by networks of components that are modeled as communicating automata. The diagnosis problem consists in generating the candidates involved in the trajectories of the DES that conform with a given temporal observation. Oddly, in the literature on diagnosis of DESs, a candidate is still a set of faulty events, despite the temporal dimension of trajectories. In our view, when dealing with critical domains, such as power networks or nuclear plants, set-oriented diagnosis may be less than optimal in explaining the supposedly abnormal behavior of the DES, owing to the lack of any temporal information relevant to faults, along with the inability to discriminate between single and multiple occurrences of the same fault. Embedding temporal information in candidates may be essential for critical-decision making. This is why a temporal-oriented approach is proposed for diagnosis of DESs, where candidates are sequences of faults. This novel perspective comes with the burden of unbounded candidates and infinite collections of candidates, though. To cope with, a notation based on regular expressions on faults is adopted. The diagnosis task is supported by a temporal diagnoser, a flexible data structure that can grow over time based on new observations and domain-dependent scenarios.

Model-based diagnosis is typically set-oriented. In static systems, such as combinational circuits, a candidate (or diagnosis) is a set of faulty components that explains a set of observations. In discrete-event systems (DESs), a candidate is a set of faulty events occurring in a sequence of state changes that conforms with a sequence of observations. Invariably, a candidate is a set. This set-oriented perspective makes diagnosis of DESs narrow in explainability, owing to the lack of any temporal knowledge relevant to the faults within a candidate, along with the inability to discriminate between single and multiple occurrences of the same fault. Embedding temporal knowledge in a candidate, such as the relative temporal ordering of faults and the multiplicity of the same fault, may be essential for critical decision making. To favor explainability, the notions of temporal fault, explanation, and explainer are introduced in diagnosis of DESs. The explanation engine reacts to a given sequence of observations by generating and refining in real-time a sequence of regular expressions, where the language of each expression is a set of temporal faults. Moreover, to avoid total knowledge compilation, the explainer can be generated incrementally either offline, based on meaningful behavioral scenarios, or online, when being operated in solving specific diagnosis problems.

An abduction-based diagnosis technique for a class of discrete-event systems (DESs), called deep DESs (DDESs), is presented. A DDES has a tree structure, where each node is a network of communicating automata, called an active unit (AU). The interaction of components within an AU gives rise to emergent events. An emergent event occurs when specific components collectively perform a sequence of transitions matching a given regular language. Any event emerging in an AU triggers the transition of a component in its parent AU. We say that the DDES has a deep behavior, in the sense that the behavior of an AU is governed not only by the events exchanged by the components within the AU but also by the events emerging from child AUs. Deep behavior characterizes not only living beings, including humans, but also artifacts, such as robots that operate in contexts at varying abstraction levels. Surprisingly, experimental results indicate that the hierarchical complexity of the system translates into a decreased computational complexity of the diagnosis task. Hence, the diagnosis technique is shown to be (formally) correct as well as (empirically) efficient.

Summary A mutating finite automaton (MFA) is a nondeterministic finite automaton (NFA) that changes its morphology over discrete time by a sequence of mutations. This results in a sequence of NFAs, the initial NFA, and one mutated NFA for each mutation. Some application domains, including model‐based diagnosis of discrete‐event systems in artificial intelligence and model‐based testing in software engineering, require temporal determinization of MFAs. Determinizing an MFA temporally means generating a deterministic finite automaton (DFA) that is equivalent to the mutated NFA as soon as a mutation occurs. Since, in computation time, the classical Subset Construction determinization algorithm may be less than optimal when applied to MFAs, a conservative algorithm is proposed, called Subset Restructuring, which, instead of constructing the new DFA from scratch based on the mutated NFA, generates the new DFA by updating the previous DFA based on the mutation occurred. Subset Restructuring is sound and complete, thereby yielding the same DFA generated by Subset Construction. Results from massive experimentation indicate the viability of Subset Restructuring, especially so when large MFAs change by small mutations.

A mutating finite automaton (MFA) is a nondeterministic finite automaton (NFA) which changes its morphology over discrete time by a sequence of mutations, one mutation at each time instant. A mutation involves the insertion and/or removal of a set of states and/or transitions. This results in a sequence of NFAs, one mutated NFA for each mutation. Some application domains, including model-based diagnosis and monitoring of active systems in artificial intelligence and model-based testing in software engineering, require online determinization of MFAs. Determinizing an MFA online means generating a deterministic finite automaton (DFA) as soon as a mutation occurs, which is equivalent to the mutated NFA. Since the classical Subset Construction determinization algorithm may be inadequate for MFAs, a conservative algorithm is proposed, called Subset Restructuring, that generates the new DFA by restructuring the previous DFA based on the mutation occurred, instead of building it from scratch. Experimental results indicate the effectiveness of the approach, especially so when large MFAs change in time by small mutations.

An active system (AS) is a network of communicating automata. A complex active system (CAS) is a hierarchy of communicating active systems. By inspiration of biological systems, organized in a hierarchy of subsystems, the interaction between automata in an AS gives rise to an emergent behavior at a superior AS, which is unpredictable from a knowledge of the behavior of the communicating automata only. Real systems can be conveniently modeled as CAS's, in order to be monitored and diagnosed by automated techniques. A diagnosis method for CAS's is presented, with viability being a major requirement: despite the complexity of the system, diagnosis shall be performed efficiently. This is supported by lazy techniques, which allow for the sound and complete solution of the diagnosis problem.

Subset Construction (SC) is the classical algorithm for the determinization of a nondeterministic finite automaton (NFA) into an equivalent deterministic one (DFA). Although SC works fine in most application domains, it may be inappropriate when the NFA expands over time and determinization is required after each expansion, such as in diagnosis of active systems in artificial intelligence, or in model-based testing in software engineering. For such an expanding automaton, the IDEA algorithm (Incremental Determinization of Expanding Automata) may be more suitable. Given an NFA N⁠, an equivalent DFA D⁠, and an expansion ΔN of N⁠, the determinization of N′=N∪ΔN into D′ is performed based not only on N′ but also on ΔN and D⁠. Rather than starting from scratch the generation of the DFA D′ equivalent to N′⁠, IDEA applies the set of actions which are sufficient for transforming D into D′⁠. This way, a possibly large part of the determinization process is avoided. Experiments show that the degree of convenience in determinizing expanding automata using IDEA rather than SC largely depends on the nature of the expanding automaton in the actual application domain.

The determinization of a nondeterministic finite automaton (FA) is the process of generating a deterministic FA (DFA) equivalent to (sharing the same regular language of) . The minimization of is the process of generating the minimal DFA equivalent to . Classical algorithms for determinization and minimization are available in the literature for several decades. However, they operate monolithically, assuming that the FA to be either determinized or minimized is given once and for all. By contrast, we consider determinization and minimization in a dynamic context, where augments over time: after each augmentation, determinization and minimization of into is required. Using classical monolithic algorithms to solve this problem is bound to poor performance. An algorithm for incremental determinization and minimization of acyclic finite automata, called IDMA, is proposed. Despite being conceived within the narrow domain of model-based diagnosis and monitoring of active systems, the algorithm is general-purpose in nature. Experimental evidence indicates that IDMA is far more efficient than classical algorithms in solving incremental determinization and minimization problems. Copyright © 2015 John Wiley & Sons, Ltd.

A gap still exists between complex discrete-event systems (DESs) and the effectiveness of the state-of-the-art diagnosis techniques, where faults are defined at component levels and diagnoses incorporate the occurrences of component faults. All these approaches to diagnosis are context-free, in as much diagnosis is anchored to components, irrespective of the context in which they are embedded. By contrast, since complex DESs are naturally organized in hierarchies of contexts, different diagnosis rules are to be defined for different contexts. Diagnosis rules are specified based on associations between context-sensitive faults and regular expressions, called semantic patterns. Since the alphabets of such regular expressions are stratified, so that the semantic patterns of a context are defined based on the interface symbols of its subcontexts only, separation of concerns is achieved, and the expressive power of diagnosis is enhanced. This new approach to diagnosis is bound to seemingly contradictory but nonetheless possible scenarios: a DES can be normal despite the faulty behavior of a number of its components; also, it can be faulty despite the normal behavior of all its components.

The determinization of a nondeterministic finite automaton (NFA) N is the process of generating a deterministic finite automaton (DFA) D equivalent to (sharing the same regular language of) N. The minimization of D is the process of generating the minimal DFA M equivalent to D. Classical algorithms for determinization and minimization are available in the literature for several decades. However, they operate monolithically, assuming that the finite automaton to be either determinized or minimized is given once and for all. By contrast, we consider determinization and minimization in a dynamic context, where N expands over time: after each expansion, determinization and minimization of N into M is required. Using classical monolithic algorithms to solve this problem is bound to poor performances. An algorithm for incremental determinization and minimization of acyclic finite automata, called IDMA, is proposed. Despite being conceived within the narrow domain of model-based diagnosis and monitoring of active systems, the algorithm is general-purpose in nature. Experimental evidence indicates that IDMA is far more efficient than classical algorithms in solving incremental determinization and minimization problems.

A novel class of discrete-event systems, called higher-order DESs (HDESs) is introduced, along with a relevant diagnosis technique. The behavior of a HDES is stratified, resulting in a hierarchy of cohabiting sub-DESs, each one living its own life. The communication between subsystems at different levels of abstraction relies on complex events, occurring when specific patterns of transitions are matched. Separation of concerns is achieved and the expressive power of diagnosis, which is scalable and context-sensitive, is enhanced.

Since the seminal work of Sampath et al. in 1996, despite the subsequent flourishing of techniques on diagnosis of discrete-event systems (DESs), the basic notions of fault and diagnosis have been remaining conceptually unchanged. Faults are defined at component level and diagnoses incorporate the occurrences of component faults within system evolutions: diagnosis is context-free. As this approach may be unsatisfactory for a complex DES, whose topology is organized in a hierarchy of abstractions, we propose to define different diagnosis rules for different subsystems in the hierarchy. Relevant fault patterns are specified as regular expressions on patterns of lower-level subsystems. Separation of concerns is achieved and the expressive power of diagnosis is enhanced: each subsystem has its proper set of diagnosis rules, which may or may not depend on the rules of other subsystems. Diagnosis is no longer anchored to components: it becomes context-sensitive. The approach yields seemingly contradictory but nonetheless possible scenarios: a subsystem can be normal despite the faulty behavior of a number of its components (positive paradox); also, it can be faulty despite the normal behavior of all its components (negative paradox).

In monitoring-based diagnosis of active systems, the observation is fragmented over time: at the occurrence of each fragment, the internal representation of the observation received so far is updated, new monitoring states are estimated, and a new set of candidate diagnoses is output. When the observation is temporally uncertain, a problem arises about the dependability of the monitoring output: Two consecutive sets of diagnoses, relevant to two consecutive observation fragments, may be unrelated to one another, and, even worse, they may be unrelated to the actual diagnosis. To cope with this problem, the notion of monotonic monitoring is introduced, which is supported by specific constraints on the fragmentation of the uncertain temporal observation, leading to the notion of stratification. Stratified observations support monotonic monitoring of active systems.

In similarity-based diagnosis of discrete-event systems the knowledge generated for solving a previous diagnostic problem can be reused to solve a new one, provided the two problems are similar. Problem-similarity requires that the temporal observation relevant to the new problem be subsumed by the temporal observation relevant to the old one. A temporal observation encompasses the (uncertain) events observed over a time interval and their (uncertain) reciprocal temporal order. Such an observation has been produced by one out of several distinct certain sequences of observable events, with each of such sequences being a sentence of the regular language of the observation. An observation subsumes another if its regular language contains the regular language of the other. However, checking observation-subsumption by following its formal definition is time consuming. In order to speed up the process, an alternative technique is proposed, which is based on the notion of coverage and exploits a number of necessary conditions, as well as a sufficient condition, for subsumption to hold. Such conditions can be directly checked on the properties of the given observations, without any need to appeal to the language theory. Experimental evidence confirms the efficiency of subsumption-checking via coverage.

In discrete-event system monitoring, a set of candidate diagnoses is output at the reception of each observation fragment. However, when the observation is uncertain, this result may be not dependable: the sets of diagnoses, relevant to consecutive observation fragments, may be unrelated to one another, and, even worse, they may be unrelated to the actual diagnosis. To cope with this problem, the notion of monotonic monitoring is introduced, which is supported by specific constraints on the fragmentation of the uncertain observation, leading to the notion of stratification.

Abstract Automated diagnosis of communicating‐automaton networks (CANs) is a complex task, which is typically faced by model‐based reasoning, where the behavior of the network is reconstructed based on its observation. This task may take advantage of knowledge‐compilation techniques, where a large amount of reasoning is anticipated off‐line (when the diagnostic process is not active), by simulating the behavior of the network and by constructing suitable data structures embedding diagnostic information. This (general‐purpose) compiled knowledge is exploited on‐line (when the diagnostic process becomes active), so as to generate the solution to the problem. Additional reusable (special‐purpose) compiled knowledge is generated on‐line when solving new problems. A software environment for the diagnosis of CANs has been developed in the C programming language with the support of the PostgreSQL relational database management system, under the Linux operating system. It supports the modeling and preprocessing of CANs as well as the solution of diagnostic problems, including on‐line knowledge compilation. The environment has been tested through a variety of experiments. Results are encouraging and provide a valuable feedback for further work. Copyright © 2006 John Wiley & Sons, Ltd.

Discrete-event modeling can be applied to a large variety of physical systems, in order to support different tasks, including fault detection, monitoring, and diagnosis. The paper focuses on the model-based diagnosis of a class of distributed discrete-event systems, called active systems. An active system, which is designed to react to possibly harmful external events, is modeled as a network of communicating automata, where each automaton describes the behavior of a system component. Unlike other approaches based on the synchronous composition of automata and on the off-line creation of the model of the entire system, the proposed diagnostic technique deals with asynchronous events and does not need any global diagnoser to be built. Instead, the current approach features a problem-decomposition/solution-composition nature whose core is the online progressive reconstruction of the behavior of the active system, guided by the available observations. This incremental technique makes effective the diagnosis of large-scale active systems, for which the one-shot generation of the global model is almost invariably impossible in practice. The diagnostic method encompasses three steps: (1) reconstruction planning; (2) behavior reconstruction; and (3) diagnosis generation. Step 1 draws a hierarchical decomposition of the behavior reconstruction problem. Reconstruction is made in Step 2, where an intensional representation of all the dynamic behaviors which are consistent with the available system observation is produced. Diagnosis is eventually generated in Step 3, based on the faulty evolutions incorporated within the reconstructed behaviors. The modular approach is formally defined, with special emphasis on Steps 2 and 3, and applied to the power transmission network domain.

This paper addresses the important issue of identifying the requirements for advanced human-system interface (HSI) in the context of a disciplined requirements engineering process. This is essential if we are to have effective, well-designed HSIs as part of large software development projects. A complete methodology, called AMMETH (a mixed methodology), that can substantially help carry out the requirements analysis of HSIs in a disciplined and effective way, is proposed. The methodology integrates several proven analysis techniques within a structured framework, where they can be exploited effectively, on their own, and orchestrated as a whole. It includes seven steps, namely: 1) analyzing the context, 2) stating interaction goals, 3) eliciting user needs and expectations, 4) identifying and rating interaction features, 5) defining interaction patterns, 6) collecting usability feedback, and 7) defining requirements. The methodology has been applied successfully to the design of a real advanced HSI toward a complex process supervision and diagnostic system of an electric power plant.