A GA-based Solution to an NP-hard Problem of Clustering Security Events

The clustering approach forwarded by Klaus Julisch is considerably effectual in eliminating false positives and finding root causes among huge amount of security events. But the clustering problem was proved to be unfortunately an NP-hard one. In this paper, a GA-based algorithm is forwarded, which is much more effective than the original approximation algorithm by Julisch. The coding scheme and genetic operations including selection, crossover, and mutation are discussed in detail. To validate the quality of the newly-forwarded approach, a tree-version apriori is given, which is quite time-consuming but able to produce absolutely accurate solution used for comparison in a feasible period of time. The results show that the GA-based algorithm is valid and efficient and can find the optimal clusters that are very similar to the absolutely accurate ones