An Application of Pattern Matching in Intrusion Detection

Abstract

This report examines and classifies the characteristics of signatures used in misuse intrusion detection.EfficienL algorithms to matcll paHerns in some of these classes are described.A generalized model for matclling intrusion signatures based on Colored Petri Nets is presented, and some of its properties arc derived.This methodology can be divided into two categories: "anomaly" intrusion detection and "misuse" intrusion detection.The first refers to intrusions that can be detected based on anomalous behavior and use of computer resources.For example, if user Aonly uses the computer from his office between 9 am and 5 pm, an activity on his account late in the night is anomalous and hence, might be an intrusion.A user B might always login outside of working hours through the company terminal server.A late night rlogin session from another host to his account might be considered unusual.This technique of detecting intrusions attempts to quantify the good or acceptable behavior and Hags other irregular behavior as intrusive.In contrast, the second, mislIse intrusion detection, refers to intrusions that follow well defined patterns of attack that exploit weaknesses in system and application software.Such patterns can be precisely written in advance.For example, exploitation of the fingard and sandmail bugs used in the Internet Worm attack [SpaSS] would come under this category.This technique represents knowledge about the bad or unacceptable behavior [Sma92] and seeks to detect it directly, as opposed to anomaly intrusion detection, which seeks to detect the complement of normal behavior.The above mentioned schemes of classifying intrusions was based on its method of detection.Another classification scheme, based on the intrusion types, presented in [Sma88] breaks intrusions into the following six types: Attempted break-in: detected by atypical behavior profiles or violations of security constraints.Masquerade attack: detected by atypical behavior profiles or violations of security constraints.Penetration of the security control system.Leakage: detected by atypical usage of I/O resources.Denial of Service: detected by atypical usage of system resources.Malicious use: detected by atypical behavior profIles, violations of security constraints, or lIse of special privileges. Premise of Intrusion Detection SchemesA main premise of anomaly intrusion detection is that intrusive activity is a subset of anomalolls activity.This might seem reasonable, considering that if an outsider breaks into a computer account, with no notion of the legitimate user's pattern of resource usage, there is a good chance that his behavior will be anomalous.Often, however, intrusive activity can be carried out as a sum of individual activities, none of which, is in itself, anomalous.Ideally, the set of anomalous activity coincides with that of intrusive activity resulting in a lack of false positives.However, intrusive behavior does not always coincide with anomalous behavior.There are four possibilities, each one with a non zero probability: 1. intrusive but not anomalous 2. not intrusive but anomalous 3. nol intrusive and not anomalous 4. intrusive and anomalous For a probabilistic basis of intrusion detection see [LVS9, LV92].Most intrusion detection systems built to date [BKSS, Sma88, LJL+S9, SSI-IWSS, LVS9, LJL+S9] etc. usc Difficulties in Intrusion Detection using Pattern Matching Several regular expression patterns, say Tel,"" Tern can be written as the regular expression (rell ... Ire m ) and matched approximately in O(mn) (page 36], where m is the total length of all the patterns.The oplimizations mentioned in that approach arc also applicable.; this transition is numbered -1 among all the transitions.; indexing is a primitive, polymorphic operation.;global variables are assigned only through temporaries.FILEl and FILE2 ; are variables global to the pattern.; all temporary variables arc named T<number>.; U is also global to the pattern.; Olmer is a built in function that returns the owner of a file.; if T4 matches with U, jump to EXIT. ; built in function giving the filename portion of a full path name.;ifT5 matches "-*" then jump to EXIT. ; built in function to test if a file is a shell script.; if T6 is 0, jump to EXIT. ; built in function giving the permissions of a file.; XGRP is a constant used to determine if a file is group executable ;signals a successful evaluation of the guard.; return from this guard.; XOTH is a constant used to determine if a file is executable by others.46.EXIT: L4: jstate is disabled ; if TS matches "-*" then jump lo EXIT ; this assignment has no effect when the processor is disabled.jinstead of RETURN.If the processor is enabled, ; disable it and continue.A JUMP has no effect otherwise.; instead of RETURN.; instead of RETURN.; compiled away ; this transition is numbered 7 among all the transitions ; compiled away because of value propagation.Same as Ti.; not compiled away because it refers to a pattern variable.; compiled away.same value as T2.; not compiled away ; compiled away.same value as T6.; T6 value propagated to T12.; compiled away.same value as T7.