Abstract: Network intrusion detection based on machine learning suffers from the problems of low detection ratio for unknown intrusion and low detection efficiency due to many complex rules. To solve these problems, a constraint based gene expression programming (GEP) rule extraction algorithm (CGREA) was proposed. The intrusion detection rules were represented based on GEP model,and a constraint grammar was defined to guarantee the rules closeness and adequacy. It restricted the ratio of randomly selecting various symbols in the gene head of GEP rules, and used the elitist strategy to guarantee convergence. The KDI)CUP' 99 DATA Set was used for evaluation the intrusion detection rules auto-extracted by CGREA. A 91%probability of detection was achieved, and three unknown attacks' probabilities of detection were more than 88 %. These results indicate that the intrusion detection rules that extracted by CGREA are effective, simple, and capable of detecting unknown intrusions. Moreover, the efficiency of rule generation and detection is improved.

Key words: Network intrusion detection, GEP (gene expression programming) , Rule extraction, Constraint grammar, Elitist strategy