Detecting faults in chained-inference rules in information distribution systems
Yih-Feng Hwang · 1998
There has previously been considerable work in the quality assessment of critical control systems, such as Command, Control, Communication, and Intelligence (C$\sp3$I) systems used in the battle field, to verify and validate their knowledge bases and to check them for completeness and consistency. The quality of rules in those C$\sp3$I-related systems thus plays a crucial role. During the execution of a C$\sp3$I system, structural faults in a rule set, such as circularity and inconsistency, can decrease the system's performance and even cause more serious failures, such as conducting the same actions in a loop path with a backward-chaining inference engine and performing an undesired/unexpected action in a C$\sp3$I system used in the battle field, respectively. An information distribution system (IDS) is a subsystem within a C$\sp3$I system. Each node in an IDS communicates with others by sending or receiving information. Traditional ways to detect faults in a rule base include comparisons of two rules at once. However, faults could be introduced by rule inferences such that one or more rules will be fired due to another fired rule. The objective of this dissertation is to develop algorithms that will effectively and efficiently detect chained-inference faults in IDS rule sets. The effectiveness of algorithms that detect such faults is a qualitative attribute which increases as the number of faults that are found increases. On the other hand, the efficiency of algorithms that detect such faults is a quantitative attribute which increases as the time to find a number of faults decreases. A new directed graph paradigm called Transition-Directed Graph (TDG), employed to represent IDS rule sets at nodes of the IDS, is presented and used in this dissertation. There are six categories of chained-inference rule faults defined using a TDG presentation. Based on these definitions of faults, algorithms used to detect such faults have been developed and implemented. Each one of the five newly developed algorithms, which uses a generic depth-first search algorithm for detection of a particular category of fault patterns, is effective in detecting one or more faults in that category with an optimal time complexity O(n), where n denotes the number of rules.