2 ) H o w to d e te c t a sh a d o win g a n o m a ly : The nonexistence
of anomaly in general implies the nonexistence of any category
of anomalies. On the other hand, the existence of anomaly
in general implies that specific anomalies may exist. For
example, let us show how to detect (i.e. verify the existence
of) a shadowing anomaly. As defined in [18], a rule can be
shadowed by one or a set of preceding rules that match all
the packets which also match the shadowed rule, while they
perform a different action. In this case, all the packets that
one rule intends to deny (accept) can be accepted (denied) by
previous rule(s); thus, the shadowed rule will never be taken
effect. It is important to discover shadowed rules and alert the
administrator to correct this error by reordering or removing
these rules [2]. Based on this definition and using Prop. 1, we
deduce the following proposition to detect the specific anomaly
of shadowing using our automaton B:
P ro p o si t i o n 4 : In a security policy defined by n filtering
rules R1, · · · , Rn, rule Rj is shadowed by rule Ri if and only
if the following three conditions hold:
• Ri has priority on Rj , i.e. i < j;
• Action of Ri is different from action of Rj (ai = aj);
• For every reachable final state r of the automaton B:
if r contains qjm, then r contains qim.
For example, there is no shadowing anomaly in the security
policy used in Section V, because there is no pair of rules
(Ri, Rj ) that respects the three conditions of prop. 4 in the
automaton of Figure 3.