Fault Detection in Rule-Based Software Systems

Motivated by packet filtering of firewall systems in Internet applications, we study the fault detection problem in the general rule-based software systems. We discuss algorithms for the detection of conflicts in a given set of rules. We first study a constrained version of the fault detection problem and propose a two-phase algorithm. The first phase is to do the rule normalization. The second phase is to detect conflicting rules. For this constrained version of the fault detection problem, the algorithm takes polynomial time. For the general problem, it is NP-hard.