Minining intrusion detection alarms with an SA-based clustering approach

Intrusion detection systems generally overload their human operators by triggering per day thousands of alarms most of which are false positives. A clustering method able to eliminate most false positives was put forward by Klaus Julisch, who proved that the clustering problem is NP-complete and proposed a low-quality approximation algorithm. In this paper, the simulated annealing technique is applied in the clustering procedure, to produce high-quality solutions. The local optimization strategy, cooling schedule, and evaluation function are discussed in details. A state-of-the-art selection table is proposed, which greatly reduces the evaluation operation. In order to validate the newly proposed algorithm, a kind of exhaustive searching is implemented, which can find global minima for comparison with the cost of long yet feasible execution time. The results show that the SA-based clustering algorithm can produce solutions with the quality very close to that of the best one, whilst the time consumption is within a reasonable range.