Fixed vs.variable-length patterns for detectingsuspicious process behaviorAndreas Wespi∗,Herv´e Debar,Marc Dacier and Mehdi NassehiIBM Research Division,Zurich Research Laboratory,S¨a umerstrasse4,CH-8803R¨u schlikon,Switzerland{anw,dac,mmn}@herve.debar@May11,2004AbstractThis paper addresses the problem of creating patterns to model the normal behavior of UNIX processes.The pattern model can be used for intrusion-detection purposes.First,we present methods to generate input data sets that enable us to observe thenormal behavior of a process in a secure environment.Second,we propose varioustechniques to derive eitherfixed-length or variable-length patterns from the input datasets.We show the advantages and drawbacks of each technique,based on the resultsof the experiments we have run on our testbed.1IntroductionIn[6]Forrest et al.introduced a change-detection algorithm which is based on the way natural immune systems distinguish“self”from“nonself”.In[5]they reported preliminary results aimed at establishing such a definition of self for Unix processes.This technique mod-els the way an application or service running on a machine normally behaves by registering the sequences of system calls invoked.An intrusion is assumed to exercise abnormal paths in the executable code,and is detected when new sequences are observed(see also[3,4,7,8]).Like every behavior-based technique,an intrusion-detection system needs to be trained to learn what the“normal”behavior of a process is.This is usually done by recording the activity of the process running in a real environment during a given period.This procedure has several drawbacks:∗Corresponding author.1•It has the potential to produce false alarms if not all possible normal behaviors have been exercised during the recording period,for example when users execute“new”,i.e.previously unseen,commands;•It has the potential to produce no alarm when an attack is performed if the application was hacked during the recording period and the attack pattern was learned by the system;•The observed behavior is a function of the environment in which it is running and thus prevents the distribution of an“initialized”intrusion-detection system that could be immediately plugged in and activated.Another approach consists of artificially creating input data sets that exercise all normal modes of operation of the process.For example,Forrest et al.[5]use a set of112messages to study the behavior of the sendmail daemon.This method eliminates the risk of obtaining false positives but not that of obtaining false negatives.Furthermore,it is an extremely complex and time-consuming task to come up with a good input data set.We make use of the functionality verification test(FVT)suites provided by application developers to observe all the specified behaviors of an application[1].Not only are we able to eliminate the risk of obtaining false positives with this approach,we also dramatically reduce the risk of obtaining false negatives because,by design,our input data set exercises all the normal(in the sense of having been tested by the designer of the application)modes of operation of the application under study.We present the results of experiments we have been running with this technique.Besides the use of the FVT suites,our work differs from that of Forrest et al.in three main ways:•The algorithm used to createfixed-length patterns is slightly different and results in shorter tables of patterns.•We consider in addition the opportunity of using variable-length patterns[14]and various ways of doing this.•The decision to raise an alarm is based on a new paradigm that is simpler than the Hamming distance described in[5],thus allowing possible real-time countermeasure.The structure of the paper is as follows.Section2presents the principles of the intrusion detection method we are working with.It explains how patterns are generated and used to cover sequences.Section3shows how we create the reference information by either recording and replaying user sessions or by using the FVT suites.Section4presents the experimental results obtained when applying afixed-length pattern-generation algorithm. Section5does the same for a variable-length pattern-generation algorithm.These two sections also highlight advantages and disadvantages of each technique.Section6concludes the paper by offering a comparison of the results as well as ideas for future work.22Principles of the approachIn our approach,UNIX processes are described by the sequences of audit events 1[15]that they generate,from start (fork )to finish (exit ).Their normal behavior is modeled by a table of patterns which are sub-sequences extracted from these sequences.The detection process relies on the assumption that when an attack exploits vulnerabilities in the code,new (i.e.not included in the model)sub-sequences of audit events will appear.Figure 1describes the complete chain used to configure the detecting tool.AECFG -> alarmFILE_closeFILE_closeFILE_openS_PASSWORD_READTCPIP_connect ABCD -> matched Figure 1:Intrusion-detection system.2.1Off-line treatmentThe upper part of Fig.1represents how the model of normal behavior is created off-line.Audit events are recorded from the ftp daemon,which has been triggered by an experiment process,and translated as letters for easier handling.Such a letter in our system actually represents the combination of the audit event and the name of the process generating it,both 1Note that Forrest et al.[5,6]use sequences of system calls instead of audit events.Obtaining system calls constitutes a more intrusive technique than the one we present here.3pieces of information being provided by the Unix C2audit trail.This recording runs through afiltering and reduction process whose purpose is explained below.When the experiment has been completed,the entire audit information is used to generate the table of patterns that constitute our model of the normal behavior of the system.The purpose of thefiltering/reduction/aggregation box is threefold(explained in more detail in the remainder of the section):filtering to eliminate irrelevant events(processes that are not related to the services we monitor)and to sort the remaining ones by process number;reduction to remove duplicate sequences due to processes generating exactly the same stream of audit events from start(fork)tofinish(exit)2;andaggregation to remove consecutive occurrences of the same system calls.Sorting prevents the introduction of arbitrary context switches into the audit stream by the operating system.Processes are sorted so that the intrusion-detection process is applied to each process individually.The events inside the process remain in the order in which they have been written to the audit trail.The reduction keeps only unique process images for model extraction.We use test suites to record the normal behavior of the ftp daemon.These test suites carry many repetitive actions and therefore result in many instances of the same process image(see[1]for a complete explanation of this issue).We remove these duplicates because they are not used by the current algorithm extracting the patterns from the reference audit data.The aggregation comes from the observation that strings of N consecutive audit events (N>20)are quite frequent for certain events,with N exhibiting small variations.A good example is the“ftp login”session,where the ftp daemon closes severalfile handles inherited from inetd.The number of these closes changes for no apparent reason.Therefore,we have simplified the audit trail to obtain a model that contains fewer and shorter patterns,and have observed no differences in experiments that do or do not use the aggregation.There is no claim that the reduced(simplified)audit trail and the original one are equivalent;the new one possibly has less semantic content.This is an experimental choice,and we would remove the aggregation part if the true/false alarm performance of the intrusion-detection system were not satisfactory.This aggregation phase would also be omitted if the intrusion-detection technique requires redundancy,e.g.neural networks.The most obvious aggregation consists of replacing identical consecutive audit events with an extra“virtual”audit event.However,doing so enriches the vocabulary(the number of registered audit events)and possibly the number of patterns,which we want to keep small.Our solution simply aggregates these identical consecutive audit events.Therefore, any audit event represents“one or more”such events(i.e.,A=A+in regular expression formalism)at the output of the aggregation box.The pattern-extraction procedure is discussed in detail in Sections4and5.2This is not used in the on-line version because of the memory cost and algorithmic complexity of keeping all known process images.42.2Real-time detectionThe lower part of Fig.1shows the real-time intrusion-detection process.Audit events are again generated by the ftp daemon,and go through the same sorting and reduction mecha-nism in real time.Then,we apply a pattern-matching algorithm (Section 2.3)to cover the sequences on the fly.When no known pattern appropriately matches the current stream of audit events,a decision has to be taken whether to raise an alarm (see Section 2.4).2.3Pattern-matching algorithmThe pattern-matching algorithm is quite critical for the performance of the intrusion-detection system.We wish to maximize both its speed and detection capabilities.Therefore,we require that patterns match exactly,i.e.,that they cannot be matched as regular expres-sions using wildcards.We use a two-step algorithm:the first step looks for an exact match,and the second step looks for the best partial match possible.These two steps are illustrated with the examples presented in Figs.2and 3.String:ABCABCDXYZGHI ABCDXYZGHI XYZGHI GHI ABC validated: 3 consecutive patterns yield exact matchABCD XYZD ABC Remainder of string:ABCD ABCD XYZD ABC GHI ABC ValidatedABC Selectable ABCDABCGHIXYZHF TableXYZDABCD XYZD ABC GHI XYZ Remainder of string:Remainder of string:Figure 2:Exact pattern-matching sequence.The first step of the algorithm is illustrated in Fig.2.A pattern that matches the beginning of the string is selected from the pattern table.If no pattern matches the beginning of the string,then the first event is counted as uncovered and removed.The algorithm is subsequently applied to the remainder of the string.Once a selectable pattern has been found,the algorithm will recursively look for other patterns that exactly cover the continuation of the string up to a given depth D or to the end of the string,which ever comes first (D =3in Fig.2).This means that,for a selectable pattern to be chosen,we must find D other patterns that also completely match the events following that pattern in the sequence.If such a sequence of D patterns does not exist,step 2of the algorithm is used.The rationale behind this is that we want to know whether the selected pattern has a positive influence on the coverage of the audit events that are in its vicinity.When such a D -pattern sequence has been found,the algorithm removes the head pattern from the sequence and continues with the remainder of the string.5String:ABCABCDKMWHF ABCDKMWHF ABC ABCD ABCD XYZD ABC length 6length 7Remainder of string:K Shifted MW Shifted Shifted SELECTEDUncovered sequence KMWABCDXYZDABCGHIXYZHF TableFigure 3:Approximate pattern-matching sequence.If we cannot find three other patterns that match the sequence after the selected pattern,we deselect it and try the next selectable pattern in the table.The fact that there were selectable patterns –but none that fulfill the depth requirement –triggers the second phase of the algorithm.The second step of the algorithm deals with failure cases and is illustrated in Fig.3.The algorithm looks for the sequence of N patterns that covers the largest number of audit events.This sequence is removed from the string and the algorithm goes back to its first part,looking again for a selectable pattern,and shortening the string as long as one is not found.2.4Intrusion detectionFor each string,the algorithm extracts both the number of groups of audit events that were not covered and the length of each of these groups.The decision whether to raise an alarm is based on the length of the uncovered sequences.It is worth noting that this is different from the measures used for the same purpose by Forrest et al.,namely the amount and the percentage of uncovered events in a string [5].There are three reasons for this:•Processes can generate a large number of events.An attack can be hidden in the midst of a set of normal ing the percentage of uncovered characters would fail to detect the attack in this case.•Small processes could be falsely flagged as anomalous because of a few uncovered events if we use the percentage of uncovered characters.•Long processes could be falsely flagged as anomalous because of many isolated uncov-ered events if we use the amount of uncovered characters.6During our experiments we observed that the trace of the attacks was represented by a number of consecutive uncovered characters.This is consistent with thefindings of Kosore-sow and Hofmeyr[8],who note that mismatches due to intrusions occur in fairly distinct bursts in the sequences of system calls that they monitored.This means that an attack cannot be carried out in fewer than T consecutive characters.Our experiments led us to choose the value7for T.In other words,each group of more than six consecutive uncovered events is considered anomalous and isflagged as an attack.This amounts to defining an intrusion as any event that generates a sequence of at least T consecutive events not covered by the algorithm defined above.To validate the concepts presented here,we have developed an intrusion-detection testbed [2].It is used to compare various strategies to build the pattern table used in the detector. Before reporting the results of the experiments performed on the testbed,we address the problem of generating the input data sequences for the intrusion-detection system.We focus on the ftp service,which is widely used,is known to contain many vulnerabilities(either due to softwareflaws or configuration errors),and provides rich possibilities for user interaction. 3Generating the reference dataThe most commonly practiced method for training behavior-based intrusion-detection sys-tems is to record the activity of the users on a normal workday.This recording is used as the reference information from which the process model is extracted during the training phase. In Section3.1we present an improvement of this method.On our testbed we can reproduce the reference information and record it under varying external conditions.Our recording procedure ensures that the reference information is attack-free.Section3.2describes various methods to systematically generate all possible user activities.We concentrate on a method that uses the functionality verification test(FVT)suite to exercise all subcommands of a given process.3.1Experimental reference data generationThefirst approach we present to create the reference data is to simulate user sessions.We wish to do the recording in a closed environment to ensure that no attacks against the ftp server take place.We achieve this goal by asking several participants in our laboratory to record ftp sessions against an internal ftp server supporting users and anonymous connec-tions.The ftp server is then reconfigured inside a closed network to prevent interactions with the outside world.Once this recording process is complete,we automatically transform the recordings into simple expect[9]scripts,which recreate the interactive er-related information such as username,password,and target ftp server is variable to allow the parallelization of the scripts.Additional scripts are added to the database to perform specific actions,such as using tar and compress to transferfiles,that were not in the original configuration of the recordings.7This need comes from the attack simulator.As some attacks involve the use of tar and compression programs to create setuid shells,our normal user activity also has to invoke these commands.We performed a number of experiments to record the reference behavior from which the model is extracted.These experiments involve(1)varying the load on the server(number of simultaneous connections),(2)changing the network interface(Ethernet or Token-Ring), and(3)selecting different subsets of scripts.We separate our user scripts into four groups:all the scripts that we have in the database; the scripts involving normal user behavior;the scripts involving anonymous user behavior; and the scripts involving normal user behavior but without those that have been added to include the usage of tar and compress(via the site exec command).The experimentation results are presented in Table1.Thefirst column describes the experiment,the second gives the total number of scripts run,the third the total number of audit events generated,the fourth the total number of processes created(output of the filtering),thefifth the number of unique processes generated(output of the reduction),and columns six to eight the number of unique processes generated with aggregation levels of3,2, and1,respectively.An aggregation level of N,N=1,2,3,means that N or more identical audit events are aggregated to exactly N such events(e.g.,AAA=AAA+for N=3).Table1:Collection of user data.No.audit events and reduction Experiment description of in the and aggregationscripts ref.set321All scripts on Ethernet interface5511152143070707069All scripts on Token-Ring interface5510506443070707069All scripts simultaneously on both11020135786070707069 Simulation of light load200494126160470707069 Simulation of heavy load6001082548458370707069All scripts500849095393172727271 Normal user scripts500299048400825252524 Anonymous user scripts5001038129376449494949 Normal user scripts w/o“site exec”5001118403417840404040 Table1shows that the number of processes generated is in direct proportion to the number of scripts run.When we look for unique processes,we alwaysfind the same number of different processes(70).Aggregation does not reduce this number significantly.This is radically different from observations(in the LINUX environment)made using the strace command which monitors at the system call level.There,we observed variances in the number of different processes generated from experiment to experiment,mainly because of operating system context switches and signals.This shows that even a low-level information8source such as the C2audit trail gives some abstraction to the data,such as eliminating context switches,signals,and interrupts.3.2Systematic reference data generationEmploying user-“controlled”manipulations to generate the reference behavior of the service is not optimal.One requirement is that in addition to being attack-free and reproducible, the reference behavior must contain all the possible legitimate commands supported by the ftp service,and that these commands must be received by the ftp server from the network interface.A second requirement is that these commands are either generated by an ftp client or directly“manufactured”,for example,by a packet-spoofing tool.3.2.1Software engineering and source-code analysisThefirst possibility to generate the reference data is to extract the complete call graph[10] of the code considered.This process is very costly,and is only possible by acquiring source code for the service investigated.Given the increasing complexity of programs and the fact that many system calls would actually happen inside the libraries for which source-code may not be available,we have eliminated this course of action because it is too cumbersome. Moreover,this technique does notfit our client-side requirement.3.2.2Macroscopic simulation as afinite-state automatonThis second approach is based on afinite-state automaton that implements all possible actions that can be performed by a user.Generating normal behavior simply means running the automaton.However,only a very limited subset of these commands is actually known to users and used by them.Therefore,it would make sense to enrich the automaton with transition probabilities.This approach is very difficult to implement for three main reasons:•The values of the transition probabilities are difficult to determine,and specific to the experimental environment.•This approach is only suitable when the set of commands is limited.It can simulate an ftp client but not a normal user shell session.•Even in simple cases such as ftp clients,implementation problems can arise.Indeed, ftp clients on different platforms sometimes have a different syntax,and the commands they generate make the ftp server react in different ways.These difficulties encountered in modeling ftp activity also apply to other services.There-fore,this approach was dropped from the current implementation of the workbench.93.2.3Approximating user behavior with test suitesA simpler approach consists of using the test suites provided by the operating-system de-velopment laboratories.In our case,we obtained access to the test suite used by the AIX development team.This test suite,called functionality verification tests(FVT),tests the compliance of the implementation of the TCP/IP services with their specification from the functional point of view,i.e.it tests the server functionality using the client in the case of ftp.The FVTs exercise all possible commands a user can send to an ftp server.These FVTs do not offer a realistic view of what users usually do,but at least they show how the system should behave when responding to normal requests.Actually,these test cases implement very simple scripts to test one command at a time.In that sense,they can be considered as traveling a subgraph of the user sessions where the length of the path would not exceed one or two commands between login and logout.This approach is also interesting to evaluate the false-alarm rate of knowledge-based intrusion-detection systems.Because the FVT will make the network daemons generate all sorts of events that do not(or very infrequently)occur in real-life systems,these events can be confused with attack scenarios.In this case,every alarm generated by a knowledge-based intrusion-detection system is a false alarm.If the intrusion-detection system has rules governing the normal behavior of the network service,running such a test suite allows us to check the completeness of the normal behavior model and also to interpret alarms generated by the intrusion-detection system as false alarms.However,the capability to fully train a behavior-based intrusion-detection system on this kind of data is still an open issue,as the profiles may contain behavior rarely exercised by the users.3.3Experimentations with the FVTThis section shows how to use the FVT data to record different reference information sets, from which process models are then generated.Recording the FVT sessions was done by simply running all available tests.Table2 presents the same results as Table1does,but for the FVT data collection.Three separate runs of the FVT were made to compare the resulting reference information.Data collec-tion took place on an isolated network,with as little interference as possible from other applications.Thefirst observation drawn from Table2is that77unique process images for487tests is very small.In fact,many of these tests are redundant,i.e.they transfer exactly the samefile in different modes(e.g.ascii,ebcdic,struct,record).The basic sequence(login, set parameters,transfer,logout)is repeated several times,but the parameter changes affect only the network level,and not the system.Therefore,we do not observe changes in the audit trail.The second observation is that,contrary to the user-simulation case,aggregation reduces the number of different processes in a significant way.Even with these very similar processes, the recording of audit events is sometimes still not completely identical.In particular,the10Table2:Collection of FVT data.Experiment description:Number of No.of processes afterfilteringNo.audit events and reductionSequential run of of in the and aggregationall available FVT tests scripts ref.set321Run14878779340177736557Run24878781340173686258Run34878912840171676156login sequence depends on the number of openfile handles handed to the ftpd daemon by the inetd daemon.We extract the model of behavior from these process images,which we regard as our reference information.4Generatingfixed-length patterns4.1Pattern generationFixed-length patterns are the most immediate approach to generate the table of patterns. We have evolved four ways of obtaining these patterns.For each of them,we use a parameter L,the length of the patterns.Technique1is an exhaustive generation of all possible patterns by sliding a window of size L across the sequence,thus recording each unique L-event sequence.This technique is easy to implement,but it has obvious drawbacks.First,a large number of patterns in the reference table will not be used by the matching algorithm on the reference data set. Moreover,the covering algorithm generates boundary mismatches when the length of the process image is not a multiple of L,because it uses a juxtaposing window instead of a sliding one(which would not make sense in this context).It is worth noting that this is the technique used to run the experiments described in[4,5,8].To solve thefirst problem,technique2is introduced,which shifts the string by L events, thus creating juxtaposed patterns instead of overlapping ones.In other words,the events in positions1to L constitute thefirst pattern,events in the positions L+1to2L constitute the second one,and so on...The table we obtain is thus much shorter than the table generated by technique1,which makes the pattern-matching algorithm faster.Technique2drops the remainder of the sequence of events when its length is not a multiple of L,therefore the second problem mentioned remains.To solve it,we have introduced techniques3and4.They are similar to technique2but keep the events remaining at the end of the string as a stand-alone pattern or concatenated to the last generated pattern,respectively.Techniques3and4both result in100%coverage of the test sets.As they are the ones that were most promising during the experiments,we11focus on them for the remainder of this paper.Note that some of the patterns are smaller or larger than the specified size,and these can only match at the end of the process execution, as they necessarily contain the end-of-process event.4.2Experimental resultsWe have used three test sets in our experiments.Thefirst test is solely based on the FVT. The second test set includes additional information on tools that are used by ftp users,but are not in the testing of the ftp daemon per se.The third data set is based on the recording of several hundred real user sessions.The experimental results are presented for the second test set.The reference table generated from thefirst set does not contain patterns for commands like tar,which are used by normal ing the third set breaks the rulefixed in the introduction of the paper(no user recording for training),thus this set has only been used to evaluate the false negative rates obtained with our approach.The output of the intrusion-detection system is shown in Fig.4.Each line reports the analysis for one process related to the ftp service.|Number of|Number of|Percentage|Number of|Average|Number of|Length of|audit|uncovered|of covered|patterns|size of|groups of|each group|events|events|events|needed|pattern|uncovered|||||||events|||||||||569|4|99.30|188| 3.01|4|1111|97|0|100.00|32| 3.03|0||928|3|99.68|308| 3.00|3|111|735|3|99.59|244| 3.00|3|111|6|0|100.00|2| 3.00|0||878|8|99.09|290| 3.00|8|11111111|839|4|99.52|278| 3.00|4|1111|8|6|25.00|1| 2.00|1|6|963|2|99.79|320| 3.00|1|2|168|2|98.81|55| 3.02|2|11|476|1|99.79|158| 3.01|1|1|366|3|99.18|121| 3.00|3|111Figure4:Output of the intrusion-detection system.Table3shows the results of the experiments to monitor our ftp server under various conditions using the intrusion-detection system loaded with several reference tables.The first column identifies the experiment.The second column lists the number of audit events in the experiment.The third column indicates the two parameters corresponding to the reference table used in the intrusion-detection system,t denotes the generation technique(3 or4)and s the size of the patterns(2,3and4).The fourth column lists the overall number of uncovered characters.Thefifth column lists the number of patterns used for the coverage. The sixth column lists the average size of patterns3,and the seventh column indicates the number of false alarms triggered by the intrusion-detection system.As described in Section 2.4,alarms are raised if there are more than6uncovered events in a row.3This value is truncated to two places after the decimal point.12。
