Application Level Intrusion Detection using Graph-based Sequence Learning Algorithm

Y. Dong, S. Rajput, and S. Hsu (USA)


Intrusion Detection System, Sequence Learning, AnomalyIntrusion Detection, Unsupervised Method, Graph Model


We present an application level intrusion detection al gorithm - Graph-based Sequence Learning Algorithm (GSLA). It is a non-parametric graph based intrusion detec tion scheme. The GLSA algorithm develops a "normal pro file" first. It then detects the abnormal activity by compar ing the user behavior with the normal profile. The complex ity of the algorithm that is used to build the common normal profile, and to detect the anomaly behaviors for the applica tion level IDS system is O(n). Other unsupervised learning (clustering) methods such as K-mean algorithm and Sup port Vector Machine (SVM) algorithms can also be used in principle. However, it is difficult for them to find an accu rate similarity function and to apply it on time-series data sequence. The proposed GSLA scheme uses a weighted di agraph model. In this model, the weight and anomaly score thresholds are introduced. The anomaly score is given to each session based on the ratio of the number of abnormal links to the session length. The state of each link in the graph is marked as normal, suspend, or abnormal by com paring its weight with the threshold. In addition, a session state is marked as abnormal if the session's anomaly score is beyond the threshold. The procedure of the GSLA al gorithm is described in pseudocode. We demonstrate the potential of this algorithm. We apply it to the log files from a real live homework submission system used by our de partment. Experimental results show the effectiveness of the GSLA algorithm.

Important Links:

Go Back