A distributed network-oriented Intrusion Detection System (IDS) is a mechanism which detects misuse accesses to an intra-network by distributed IDSs on the network with decomposed attack scenarios. However, there are only ad hoc algorithms for determining a deployment of distributed IDSs and a partition of the attack scenarios. In this paper, we formally define this problem as the IDS partition deployment problem and design an efficient algorithm for a simplified version of the problem by graph theoretical techniques.

A policy is an execution rule (or constraint) for objects in a system to retain security and integrity of the system. We introduce a simple policy specification language and define its operational semantics. A new NFA construction algorithm that works in linear time is proposed and a model checking method for policy controlled system (PCS) is presented. We conducted verification of a sample PCS for hotel reservation by our automatic verification tool and the experimental results showed the efficiency of the proposed method.