Incremental validation of policy-based systems

Policy-based systems are gaining popularity as a way to manage applications with dynamic behaviour. These systems have policies specifying the desired behaviour, entered into the system by either end-users or system administrators. In order to assure that the policies don't violate any stipulated properties of the system or conflict with one another, the policies must be validated. This validation process can take a very large amount of time as the system's policy base grows. This thesis suggests an incremental validation method, whereby a system which has been determined to be consistent can be validated when a new rule is added to the system. "Trigger chaining" is a concept introduced in this thesis that examines which policies are triggered by the firing of a particular policy. This concept leads to new kinds of conflicts. An algorithm is suggested for incremental detection of such conflicts and is shown to operate in linear time, as opposed to complete revalidation which has quadratic complexity. Trigger chaining also leads to the detection of cyclic conflicts which are briefly discussed. Decision tables are suggested as a suitable format for the internal representation of policies. This format provides a method of checking a policy set for completeness and could help in checking for conflicts. Also decision tables are shown to be a natural format for storing policies. It is also known how to convert decision tables into executable rules, making the transition from decision table-based policies to rule engine policies a simple on