Below are the design milestones and goals that we have achieved in the project so far. We are currently working in the implementation of a distributed intrusion detection system that incorporates our design:

1. Inference on the Bayesian network performed through different choice and placements of detectors. We model the probabilistic relations between attack steps and detectors using the statistical formalism of Bayesian networks. Bayesian networks are particularly appealing in this setting since they enable computationally efficient inference for unobserved nodes (such as attack goals) based on observed nodes (detector alerts.) The important question that Bayesian inference can answer for us is, given a set of detector alerts, what is the likelihood or probability that an attack goal has been achieved. A particularly important advantage is that Bayesian network can be relatively easily created from an attack graph structure which is often assumed to be provided.


2. Greedy and fully polynomial time approximation algorithm developed. We presented a greedy algorithm to determine the choice and placement of detectors in a distributed system, which we called the DETECTOR-PLACEMENT problem. The algorithm takes as input a Bayesian network and a set of detectors. The mapping of our DETECTOR-PLACEMENT problem to the 0-1 Knapsack problem allowed us to utilize the existing algorithms for the popular NP-hard optimization problem. In particular, the Knapsack problem allows approximation to any required degree of the optimal solution by, as previously mentioned, using an algorithm classified as (FPTAS) since the algorithm is polynomial in the size of the instance n and the reciprocal of the error parameter ε. We compared the performance of Greedy and FPTAS algorithms to determine a set of detectors given an attack goal. FPTAS consistently outperformed Greedy, although the latter could be used in scenarios where time constraints exist On-the-fly reconfiguration of sensors (new rules added, rules removed or modified) demonstrated. An execution time comparison between Greedy algorithm and FPTAS, for different values of the error parameter (ε). In our experiments, values of ε equal or larger than 0.01 allow FPTAS to run faster than Greedy.

We imbue our solution with the ability to evolve with changes to the protected system and the kinds of attacks seen in the system. To achieve this, we developed two algorithms: (i) one to update the CPTs in the Bayesian network in an incremental manner, given the alerts received by the reasoning engine from the individual detection sensors; and (ii) an algorithm to update the choice of sensors based on runtime inference. The first algorithm uses a popular and powerful model known as Noisy-OR to represent the conditional probability values and its output is the set of CPTs with the updated values.

In summary we have designed a distributed intrusion detection system (DIADS) that can choose and place sensors in a distributed system. The architecture has been developed with multiple sensors embedded in the protected system and with a centralized inference engine that communicates two-ways with the sensors. Through domain-specific optimizations, we make our reasoning engine fast enough to perform reconfiguration of existing sensors in light of MSA.