(l2) Ulllted States Patent
`Agrawal et a].
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 8,108,929 B2
`Jan. 31, 2012
`
`US008108929B2
`
`(54) METHOD AND SYSTEM FOR DETECTING
`INTRUSIVE ANOMALOUS USE OF A
`SOFTWARE SYSTEM USING MULTIPLE
`DETECTION ALGORITHMS
`
`a 3V . . . . . . . . . . ..
`
`gagerer a1~ ~~~~~~~~~~~~~~~~ ~~
`2i:
`2003/0188190 A1* 10/2003 Aaron et a1. ..... ..
`713/201
`2004/0034795 Al *
`2/2004 Anderson et a1. ..
`713/201
`2004/0143756 A1* 7/2004 MunSon et a1.
`713/200
`2005/0229250 A1* 10/2005 Ring etal. . . . . .
`. . . .. 726/23
`2007/0107052 A1 *
`5/2007 Cangml et al' """""""" " 726/22
`(75) Inventors: Subhash C.Agr'aWal, Boxboro, MA
`OTHER PUBLICATIONS
`(US); Scott M. Wimer', Burlington, MA
`Jonathan H‘ Young’ Newton’ MA X. Hoang, J. Hu, and P. Bertok. “A Multi-layer Model for Anomaly
`Intrusion Detection Using Program Sequences of System Calls”,
`Networks’ 2003'
`* cited by examiner
`
`(73) Assignee: Re?ex Systems, LLC, Atlanta, GA (U S)
`
`*
`
`Primary Examiner * Gilberto Barron, Jr.
`Assistant Examiner * Virginia T Ho
`(74) Attorney, Agent, or Firm * David H. Judson
`
`ABSTRACT
`(57)
`A target software system is instrumented to generate behavior
`data representing a current observation or observation aggre
`gate. A method then determines Whether the current observa
`tion or observation aggregate Warrants a second level exami
`nation; preferably, this determination is made by processing
`the current observation or observation aggregate through a
`?rst level detection algorithm that provides a provisional
`indication Of a Possible immsion- If executing the ?rst level
`detection algorithm indicates that the Current Observation or
`observation aggregate Warrants a second level examination,
`the method continues by processing the current observation
`or observation aggregate through at least one second level
`detection algorithms to provide a more de?nite, ?ne grain
`indication of a possible intrusion. Multiple algorithms may be
`executed together Within a single examination level, With the
`-
`-
`-
`.
`.
`lndlvldual results then analyzed to obtaln a composite result
`or output indicative of intrusive or anomalous behavior.
`
`23 Claims, 4 Drawing Sheets
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1844 days.
`
`(21) Appl.No.: 10/967,945
`
`(22) Filed:
`
`Oct. 19, 2004
`
`(65)
`
`Pnor Pubhcatlon Data
`US 2006/0085854 A1
`Apr. 20, 2006
`
`(51) Int. C1.
`(200601)
`G06F 21/00
`(52) us. Cl. ....................................................... .. 726/23
`(58) Field of Classi?cation Search ................... .. 726/23
`See apphcanon ?le for Complete Search hlstory'
`References Cited
`
`(56)
`
`Us PATENT DOCUMENTS
`
`726/23
`6,839,850 B1 *
`1/2005 Campbell et al.
`726/22
`7 069 588 B2 * 60006 Call et al
`726/25
`7,162,741 B2 *
`1/2007 Eskin et a1‘ ‘‘‘ u
`726/23
`7,487,542 B2 *
`2/2009 Boulanger et a1.
`2002/0078381 A1 *
`6/2002 Farley et a1. ................ .. 713/201
`
`KERNEL
`y
`
`FAST ALGORITH MS
`
`F1 : MAXIMUM SENSOR
`FREQUENCY TEST
`F2: MARKOV MODEL
`
`SOPHISTICATED ALGORITHMS
`
`S1 : CORRELATION SHIFT
`ALGORITHMS
`1 ELLIPSOID
`S3 : MULTl-CLUSTER ANALYSIS
`54 I SUPPORT VECTOR MACHINE
`
`USER/COMMAND GROUPS
`
`' ONE FOR ENTIRE SYSTEM
`' USER-DEFINED
`' DATA-DRIVEN
`
`USER
`an
`
`1
`
`SYMC 1008
`
`

`

`US. Patent
`
`Jan. 31, 2012
`
`Sheet 1 of4
`
`US 8,108,929 B2
`
`OPERATING
`SYSTEM
`A
`
`I
`SYSTEM CALL CLICKS :
`INTERCEPTOR
`A
`10/4
`
`106
`/
`CLICK
`AGGREGATOR
`CLICK AGGREGATES
`FOR P
`ESSING
`R00
`
`KERNEL SPACE
`
`[100
`
`FIG. 1
`
`‘I
`
`T
`
`108, IIEHREURNIIICQIEN
`OR DIFFERENT MACHINE) \
`USER SPACE
`I02
`
`CLICK
`TRIAGEI SAVE
`CLICK >
`200/ OR DISCARD?
`
`DI ARD
`SC
`
`KERNEL SPACE
`
`SAVE
`I
`FAST BADNESS
`SCORE>
`THRESHOLD?
`
`202/
`
`V
`PROCESS PARTIAL
`204/ (SUSPICIOUS)
`CLICK BUFFER
`
`SCORE OK >
`
`CLICK
`CONTINUE
`AGGREGATE
`BUFFER FULL? \ 205
`
`:
`
`‘I
`PROCESS FULL
`(NOT SUSPICIOUS) \ 208
`CLICK BUFFER
`
`/
`100
`
`FIG. 2
`
`2
`
`SYMC 1008
`
`

`

`US. Patent
`
`Jan. 31, 2012
`
`Sheet 2 014
`
`US 8,108,929 B2
`
`6
`30 \[
`308
`
`| 310
`I /
`I
`Ei J PERIODICALLY
`'
`:
`
`<THRESHOLD?
`
`YES
`
`NEXT
`ALGORITHM
`7
`
`I
`I
`I
`I
`'
`PROCEED ,
`'
`I
`I
`I
`I
`
`0 0 0000 0000 000 0
`
`311
`
`< L
`THRESHOLD
`
`YES
`
`3/14
`
`312
`
`NO
`
`PROCEED
`
`< U
`THRESHOLD
`
`NO
`
`KERNEL
`302
`——
`
`FAST ALGORITHMS
`
`F :MAXIMUM SENSOR
`I FREQUENCY TEST
`F2: MARKOV MODEL
`
`SOPHISTICATED ALGORITHMS '
`
`S1 ; CORRELATION SHIFT
`ALGORITHMS
`S2 ; ELLIPSOID
`s3 ; MULTI-CLUSTER ANALYSIS
`84 ; SUPPORT vEcTOR MACHINE
`
`USER/COMMAND GROUPS
`
`- ONE FOR ENTIRE SYSTEM
`' USER-DEFINED
`
`' DATA-DRIVEN
`
`USER
`
`304
`
`NEXT
`ALGORITHM
`?
`
`316/ TAKE ACTION
`
`FIG. 3
`
`3
`
`SYMC 1008
`
`

`

`US. Patent
`
`Jan. 31, 2012
`
`Sheet 3 014
`
`US 8,108,929 B2
`
`ALGORITHM
`2
`
`FIG 4 Z‘HLFQTT'WHEE
`
`404
`\
`DEEMED TO BE
`ACCEPTABLE
`
`ACCEPTABLE
`BEHAVIOR
`
`502
`\
`
`504
`\
`
`MARKOV MQDEL
`ALGORITHM ON
`SYSCALL
`SEQUENCE
`LENGTH 40
`
`IVIARKOV MQDEL
`ALGORITHM ON
`SYSCALL
`SEQUENCE
`LENGTH 8
`
`510
`V
`\
`PRQB (LAST
`SENSOR/
`sEQUENCE OF
`PRECEDING 39
`sENsQRs)
`
`512
`V
`\
`PRQB (LAST
`sENsoR/
`sEQUENCE OF
`PRECEDING 8
`sENsQRs)
`
`506
`/
`K-MEANS
`ALGORITHM ON
`RELAT|vE sENsoR
`FREQUENCY; 200
`SENSORS PER
`0BsERvAT|0N
`AGGREGATE
`
`514
`/
`V
`D'STSQ'SEE OF
`OBSERVATION
`AGGREGATE FROM
`THE NEAREST
`CLUSTER
`
`508
`/
`
`EAESEATES;
`ABNORMAL
`TERMINATION
`RATE OVER
`LAST MINUTE
`
`516
`/
`
`V
`PRQB
`(oBsERvED
`RECENT
`SEGMENT
`FAULT RATE)
`
`F1 G. 5
`
`EXCEEDS
`THRESHOLDS
`?
`
`NO
`
`518
`
`INTRUSION/ANOMALY
`
`NONE
`
`4
`
`SYMC 1008
`
`

`

`US. Patent
`
`Jan. 31, 2012
`
`Sheet 4 of4
`
`US 8,108,929 B2
`
`INDIVIDUALALGORITHM
`RESULTS Ri| ,...,Rim
`I
`602 \ RESULT EVALUATION ALGORITHM
`(E.G., BAYESIAN NETWORK)
`I
`AGGREGATE RESULT
`
`‘
`
`J
`
`)
`
`600\’
`
`L
`
`604 A
`
`EXCEEDS
`THRESHOLDS
`?
`
`NO
`
`606
`
`INTRUSION/ANOMALY
`
`FIG. 6
`
`‘I
`NONE
`
`0000000
`
`OBSERVATIONS
`
`7/“
`
`INDIVIDUAL ALGORITHM
`RESULTS Ri|,...,Rim
`
`O O O O O O O ['NQ'EVS'BEASEQERORRIEM ]
`00000 00
`7\06
`
`MEASURED
`OBSERVATIONS \ 708
`
`706/
`
`710 / COMPOSITE OBSERVATION SET FOR NEXT LEVEL
`FIG. 7
`
`5
`
`SYMC 1008
`
`

`

`US 8,108,929 B2
`
`1
`METHOD AND SYSTEM FOR DETECTING
`INTRUSIVE ANOMALOUS USE OF A
`SOFTWARE SYSTEM USING MULTIPLE
`DETECTION ALGORITHMS
`
`BACKGROUND OF THE INVENTION
`
`1. Technical Field
`The present invention generally relates to detecting the use
`of software, and more speci?cally, to the dynamic detection
`of an intrusive anomalous use of computer softWare.
`2. Description of the Related Art
`The literature and media abound With reports of successful
`violations of computer system security by both external
`attackers and internal users. These breaches occur through
`physical attacks, social engineering attacks, and attacks on
`the system. In a system attack, the intruder subverts or
`bypasses the security mechanisms of the system in order to
`gain unauthorized access to the system or to increase current
`access privileges. These attacks are successful When the
`attacker is able to cause the system softWare to execute in a
`manner that is typically inconsistent With the softWare speci
`?cation and thus leads to a breach in security.
`Intrusion detection systems monitor some traces of user
`activity to determine if an intrusion has occurred. The traces
`of activity can be collated from audit trails or logs, netWork
`monitoring or a combination of both. Once the data regarding
`a relevant aspect of the behavior of the system are collected,
`the classi?cation stage starts. Intrusion detection classi?ca
`tion techniques can be broadly catalogued in the tWo main
`groups: misuse intrusion detection, and anomaly intrusion
`detection. The ?rst type of classi?cation technique searches
`for occurrences of knoWn attacks having particular signa
`tures, and the second type searches for a departure from
`normality. Some of the neWest intrusion detection tools incor
`porate both approaches.
`Some recent systems have employed dynamic softWare
`measurement techniques, but they either make a decision
`instantaneously (at every measurement), or they aggregate
`measurements (either by time or by number of observations)
`and perform analyses on aggregates. Techniques that make a
`decision at every measurement point should be very fast,
`because they can potentially be called thousands of times per
`second. This performance constraint severely limits the
`detection accuracy of such techniques. On the other hand,
`techniques that only consider aggregated system behavior can
`have a signi?cant latency betWeen the time of intrusion and
`the time of detection due to the aggregation delay.
`There remains a need for improved techniques.
`
`BRIEF SUMMARY OF THE INVENTION
`
`The present invention shoWs hoW to use a combination of
`analysis techniques (detectors) to improve over the detection
`accuracy of instantaneous detectors Without the latency inher
`ent in simple aggregation-based detection. By cascading
`detectors, fast algorithms are used to Weed out normal behav
`ior very quickly, While more complex algorithms are run
`preferably only When there is a good possibility that some
`thing is Wrong. The complex algorithms may also be run
`periodically to provide additional assurance that no abnormal
`behaviors are occurring or have occurred. Multiple detection
`algorithms may also be combined in parallel to improve the
`precision of detection of very speci?c kinds of behavior or
`anomaliesifor example, a very precise detector for a speci?c
`kind of knoWn assault may be combined With a general detec
`tion algorithm for divergence from previous knoWn behavior.
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`An embodiment of the invention includes a method of
`detecting an intrusion into a target softWare system that has
`been instrumented to generate behavior data representing a
`current observation or observation aggregate. The method
`begins by determining Whether the current observation or
`observation aggregate Warrants a second level examination;
`preferably, this determination is made by processing the cur
`rent observation or observation aggregate through a ?rst level
`detection algorithm that provides a ?rst or “provisional” indi
`cation of a possible intrusion. If a result of executing the ?rst
`level detection algorithm indicates that the current observa
`tion or observation aggregate Warrants a second level exami
`nation, the method continues by processing the current obser
`vation or observation aggregate through at least one or more
`second level detection algorithms to provide a second, more
`de?nite indication of a possible intrusion. The observation
`aggregates used by the ?rst and second level detection algo
`rithms may be the same or different. The ?rst and second level
`detection algorithms may be executed in the same or different
`systems, machines or processors. The target softWare system
`operation may be suspended as the current observation or
`observation aggregate is processed through the one or more
`second level detection algorithms. A given action (e.g., send
`ing an alert, logging the event, activating a countermeasure, or
`the like) may be taken if the result of the second level exami
`nation indicates a possible intrusion.
`In certain circumstances, such as Where a ?rst level deter
`mination can be made With high con?dence that an anomaly
`exists or is executing, it may not be necessary to fully perform
`the second level determination, or to perform the second level
`determination at all.
`The present invention is not limited to using the above
`described multi-level or multi-stage technique just for intru
`sion detection. More generally, the technique may be gener
`aliZed for use in detecting an anomaly in a given behavior of
`the target softWare system. In this context, the invention also
`contemplates the further step of conditionally suspending a
`given operation of the target softWare system that is suspected
`of causing the anomaly While executing the one or more
`second level detection algorithms. The execution of the target
`softWare system may continue despite the possible anomaly
`While the second level examination is performed.
`Preferably, the ?rst level detection algorithm has a compu
`tational-ef?ciency that is greater than a computational-e?i
`ciency of the second level detection algorithm. (This is not a
`limitation, hoWever). In an illustrative embodiment, compu
`tational ef?ciency is measured as a given function of memory
`and processing requirements. Thus, for example, the ?rst
`level detection algorithm may use non-?oating point arith
`metic operations While the second level detection algorithm
`uses ?oating point arithmetic operations. Alternatively, the
`?rst level detection algorithm may use single precision ?oat
`ing point arithmetic operations While the second level detec
`tion algorithm uses double precision ?oating point arithmetic
`operations. Generalizing even further, the ?rst level may
`implement an approximation to a complex algorithm While
`the second level implements the complex algorithm itself.
`In operation, a given ?rst level detection algorithm com
`putes a metric (a value or a set of values) by processing the
`current observation or observation aggregate. This metric
`may then be compared against a given threshold value to
`determine Whether the current observation or observation
`aggregate Warrants the second level examination. In a repre
`sentative (but non-limiting) embodiment, the ?rst level detec
`tion algorithm implements a given mathematical process
`using non-?oating point computations to determine Whether
`the current observation or observation aggregate Warrants the
`
`6
`
`SYMC 1008
`
`

`

`US 8,108,929 B2
`
`3
`second level examination. The given mathematical process
`may be a Markov model process, a frequency threshold pro
`cess, an ellipsoidal model process, or the like.
`As also described, the given second level detection algo
`rithm typically Will have more computational requirements,
`although this is not a strict limitation of the invention. The one
`or more second level detection algorithms preferably are
`selected from a set of mathematical models or algorithms that
`are executed using ?oating-point computations and that
`include: ellipsoidal models, k-means models, decision tree
`models, support vector machine (SVM) models, Markov pro
`cess models, correlation factor models, frequency threshold
`models, ellipsoidal models, and combinations thereof. More
`generally, the ?rst level detection algorithm is a coarse clus
`tering or pattern matching algorithm and the second level
`detection algorithm is a ?ne clustering or pattern matching
`algorithm.
`As is Well-knoWn, a target softWare system may be conve
`niently characteriZed as operating in one of several modes: a
`kernel mode, and a user mode. Typically, a kernel mode refers
`to the situation Where given instructions, program sequences
`or code portions have direct access to all memory, including
`the address spaces of all user-mode processes and applica
`tions, and to hardWare. In contrast, user mode refers to the
`typical softWare system processing mode in Which applica
`tions run. Typically, Where given instructions, program
`sequences or code portions execute in kernel mode, such code
`is run Within a protected memory or space. According to an
`illustrative embodiment of the present invention, the ?rst
`level detection algorithm is executed in the kernel mode and
`at least one second level detection algorithm is executed in the
`user mode.
`According to an illustrative embodiment of the invention,
`the step of processing the current observation or observation
`aggregate through at least one or more second level detection
`algorithms processes the current observation or observation
`aggregate through at least a pair of second level detection
`algorithms Whose outputs are combined according to a given
`function to provide the second, more de?nite indication of the
`possible intrusion. Although not meant to be limiting, the
`given function is selected from a set of functions, for example,
`linear functions, non-linear functions, and logical combina
`tions of linear functions and non-linear functions. The outputs
`may be combined concurrently or otherWise.
`According to a more generaliZed embodiment, a current
`observation or observation aggregate is processed during a
`?rst level examination through a set of one or more fast
`algorithms, e.g., in a cascade manner. If the current observa
`tion or observation aggregate triggers a given threshold for a
`given fast algorithm, a next fast algorithm is tested, and the
`process iterates. If the threshold for each fast algorithm is
`triggered (and the thresholds may vary), a second level
`examination may be initiated. During the second level exami
`nation, the current observation or observation aggregate is
`processed through a set of one or more sophisticated algo
`rithms, e. g., in a cascade manner. If the current observation or
`observation aggregate triggers one or more thresholds for a
`given sophisticated algorithm, a next sophisticated algorithm
`is tested, and the process iterates. If the thresholds (as the case
`may be) for each sophisticated algorithm are triggered (and
`the thresholds may vary), a given action indicative of an
`intrusion or anomaly is taken. Preferably, the ?rst level
`examination occurs in kernel mode While the second level
`examination occurs in user mode.
`The principles of the present invention are not limited to
`multi-level examinations. Multiple algorithms may be
`executed together Within a single examination level, With the
`
`4
`individual results then analyZed to obtain a composite result
`or output indicative of intrusive or anomalous behavior. As a
`representative example, the system may run algorithms in
`parallel to analyZe different types of characteristics embed
`ded in given data, e.g., running a temporal-based algorithm
`(e.g., a Markov model) to examine sequence or temporal
`characteristics, and running frequency-based (e. g., cluster
`analysis algorithms) to analyZe frequency clustering. Of
`course, the system can also run the same algorithm in parallel
`to get similar information by analyZing data for different time
`periods, With the results then analyZed. In addition, the sys
`tem can run algorithms in parallel to explore different types of
`machine, device or program features. Thus, in an illustrative
`embodiment, there may be a examination level in Which a set
`of n algorithms are executed, With each algorithm testing
`against a different characteristic or feature, and their respec
`tive outcomes evaluated together (e. g., against a given thresh
`old) to make a decision. A threshold check may be simple or
`complex. Thus, for example, complex decision machines or
`logic made be used for making a decision, even Within a given
`examination level. Examples of such decision machines
`include Bayesian netWorks or decision tree models to deter
`mine the probability that intrusive or anomalous behavior has
`occurred, cluster analysis algorithms applied to a composite
`vector of observation analysis results, or the like.
`The foregoing has outlined some of the more pertinent
`features of the invention. These features should be construed
`to be merely illustrative. Many other bene?cial results can be
`attained by applying the disclosed invention in a different
`manner or by modifying the invention as Will be described.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`For a more complete understanding of the present inven
`tion and the advantages thereof, reference is noW made to the
`folloWing descriptions taken in conjunction With the accom
`panying draWings, in Which:
`FIG. 1 is a simpli?ed block diagram of a ?rst embodiment
`of the present invention as implemented in a system call
`interception system;
`FIG. 2 is a simpli?ed representation of the click aggregator
`and processing logic components of FIG. 1;
`FIG. 3 is a high level representation of a more generaliZed
`implementation of the present invention, Wherein each pro
`cessing level includes a set of one or more cascaded algo
`rithms;
`FIG. 4 illustrates hoW one can improve detection accuracy
`by executing a pair of algorithms Within a given examination
`level;
`FIG. 5 illustrates a set of algorithms that are executed in
`parallel against given system behavior characteristics or fea
`tures;
`FIG. 6 is a simpli?ed ?owchart of a generaliZed threshold
`check process that may implemented Within a given exami
`nation level; and
`FIG. 7 illustrates hoW an observation aggregate may be
`enhanced With the results from prior analyses of the observa
`tions, alloWing algorithms executed at a next level to bene?t
`from and take into account the results of algorithms executed
`earlier.
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`DETAILED DESCRIPTION OF AN
`ILLUSTRATIVE EMBODIMENT
`
`65
`
`FIG. 1 illustrates one illustrative embodiment of the
`present invention. In this embodiment, an interface betWeen a
`softWare system kernel space 100 anduser space 102 includes
`
`7
`
`SYMC 1008
`
`

`

`US 8,108,929 B2
`
`5
`a system call interceptor 104 and a click or observation aggre
`gator 106 that together determines Whether a current obser
`vation or observation aggregate Warrants a second level
`examination; preferably, this determination is made by pro
`cessing the current observation or observation aggregate
`through a ?rst level detection algorithm that provides a ?rst,
`provisional indication of a possible intrusion. If a result of
`executing the ?rst level detection algorithm indicates that the
`current observation or observation aggregate Warrants a sec
`ond level examination, the aggregator 106 continues by pro
`cessing the current observation or observation aggregate
`through at least one or more second level detection algorithms
`to provide a second, more de?nite ?ne grain indication of a
`possible intrusion. Although the click aggregator 106 is
`shoWn operating in kernel space, more typically the second
`level examination Will takes place in user space. The code
`running in user space can generally support higher computa
`tional requirements as measured in terms of memory and
`processing demands as compared to the code that runs in
`kernel space. The click aggregator provides an output to a
`Watcher application 108, Which runs the second level algo
`rithms and may be running on the same machine or otherWise
`available on a remote machine.
`Although FIG. 1 illustrates the capture of execution behav
`ior at a system call interface, this is not a limitation. The
`execution behavior may be captured at other interfaces, such
`as at a function call, at code branch points, and the like.
`FIG. 2 is a simpli?ed block diagram of the-click aggregator
`and processing logic. In general, a click may be thought of as
`an observation of execution behavior. When a click arrives, a
`test is performed at step 200 to determine Whether it should be
`evaluated. Typically, the mechanism evaluates all clicks, but
`there may be situations (still Within the scope of the invention)
`in Which observations of certain execution behavior may not
`be evaluated, e.g., a very frequent behavior, a behavior that is
`proven alWays to be benign, or a behavior the further process
`ing of Which may potentially create undesirable artifacts. If
`the outcome of the test at step 200 indicates that the click
`should be evaluated, the click is saved, preferably in a ring
`buffer (or similar structure), and evaluated using an algorithm
`that takes into consideration prior execution behaviors (al
`ready present in the ring buffer) to produce a score value.
`Because in this illustrative embodiment the score is to be used
`for detecting “bad behavior” using fast algorithm(s), it is
`sometimes referred to as a “fast badness score.” A test is
`performed at step 202 to determine Whether this fast badness
`score is greater than a given threshold. In the illustrated
`embodiment, the threshold is predetermined in some off-line
`manner, e.g., by testing the algorithm With different loads. If
`the fast badness score is greater than the given threshold, the
`routine branches to step 204 to process the click buffer, Which
`contains suspicious behavior. If, hoWever, the outcome of the
`test at step 202 indicates that the fast badness score is not
`greater than the given threshold, the routine branches to step
`206 Where a test is performed to determine Whether the buffer
`is full. If the buffer is not full, the routine continues. If the
`buffer is full, the routine continues at step 208 to process the
`click buffer to do a periodic check (e. g., using more complex
`algorithms) to ensure that no suspicious behavior has escaped
`detection. The processing of the task Whose execution behav
`ior is being analyZed may be put of hold While the evaluation
`takes place.
`FIG. 3 illustrates a further generaliZation of the invention.
`As illustrated, a current observation or observation aggregate
`300 is processed through a ?rst level examination 302 and,
`optionally, through a second level examination 304. For rep
`resentative purposes, the ?rst level examination 302 occurs in
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`kernel mode, While the second level examination 304 occurs
`in user space. There may be multiple algorithms at a given
`level. The ?rst level examination 302 involves one or more
`fast algorithms P1, With tWo such algorithms being shoWn,
`e.g., F 1, an independent sensor frequency analysis, and F2, a
`fast approximation Markov model. In this examination, the
`current observation or observation aggregate 300 is applied to
`the function Fl. (block 306) With the output then being tested
`against a threshold 308. If the threshold is not met, then the
`routine terminates (as indicated by the “Proceed” statement,
`Which indicates that the application that is generating the data
`should continue execution). If the threshold is met, a test 309
`is performed to determine Whether a next Fl- algorithm should
`be used for further evaluation. If so, the routine cycles back to
`step 306 and the ?rst level examination iterates against the
`next fast algorithm (e.g., F2). Of course, each fast algorithm
`may have a different threshold value or constraint, and each
`may process a different, but related, observation aggregate.
`The particular identity of the fast algorithm and the described
`sequence of these algorithms are merely representative. As
`also seen in FIG. 3, the current observation or observation
`aggregate 300 may also be tested periodically (through the
`one or more fast algorithm(s) Fl) as indicated by the block
`310. If the current observation or observation aggregate
`has triggered the applicable threshold in all of the fast algo
`rithm(s) Fl- (e.g., Fl, then F2, and so forth), the second level
`examination 304 is initiated.
`Generalizing further, the second level examination can be
`triggered if scores from M out of N algorithms in the ?rst level
`examination exceed a given threshold (for the respective
`algorithms).
`The second level examination 304 comprises a set of one or
`more “sophisticated” algorithms 8,, Which in this illustrated
`example includes S1, a correlation shift algorithm, S2, an
`ellipsoid algorithm, S3, a multi-cluster analysis, S4, a support
`vector machine, a sequence analysis algorithm (not shoWn),
`and so forth. As described above, the particular identity and
`sequence of these sophisticated algorithms is merely illustra
`tive. In this embodiment, the observation or observation
`aggregate is evaluated by a given Sl- algorithm (block 312)
`With the output thereof (Which is a value) compared to a loWer
`threshold value L. This is block 314. If the test at block 314
`is not triggered, the second level examination ends, With the
`application continues to “Proceed” as described above. If,
`hoWever, the output of the test at block 314 indicates that a
`loWer threshold has been exceeded, the output (of the given Sl
`algorithm) is compared against an upper threshold value Ui.
`This is block 316. (The particular values of LI. and U1. may vary
`depending on the type of algorithm used, of course). If the
`value generated by executing the S1- algorithm is greater than
`the upper threshold value, then a given action 318 is initiated
`because an intrusion (or anomaly) is indicated.
`If the result of executing the given Sl- algorithm is less than
`the upper threshold value Ui, the routine continues at step 320
`to test Whether any additional sophisticated Sl- algorithm
`remains to be tested. If the result of the test at step 320
`indicates that there is a next sophisticated algorithm, the
`routine iterates and repeats the above-described process.
`When the result of the test at step 320 is negative, the routine
`also branches and takes the given action 318.
`Thus, FIG. 3 illustrates hoW multiple algorithms can be
`used in a cascading fashion (even Within a given examination
`level). In the second level examination, each algorithm also
`uses tests against multiple thresholds, although this is not a
`limitation of the invention either. In the alternative, the mul
`tiple (R or Si) algorithms compute partial scores that together
`
`8
`
`SYMC 1008
`
`

`

`US 8,108,929 B2
`
`7
`may form a multi-element score or a composite aggregate
`score. Of course, a similar function can be implemented in
`kernel space as Well.
`The principles of the present invention are not limited to
`multi-level examinations. Multiple algorithms may be
`executed together Within a single examination level, With the
`individual results then analyZed to obtain a composite result
`or output. This concept is illustrated generally in FIG. 4. In
`this illustration, algorithm 1 is executed and includes an area
`of acceptable behavior data illustrated by reference numeral
`400. Algorithm 2 is executed (concurrently, or otherWise in
`“parallel”inamely, at the same examination level) and
`includes an area of acceptable behavior data illustrated by
`reference numeral 402. Because the algorithms are run in
`parallel (or, more generally, Within the same examination
`level), an area of overlap 404 is then deemed to be acceptable
`behavior for the test, as a Whole, or that area may be more
`narroWly constrained (as reference 406) by some policy or
`other metric. As a representative example, the system may run
`algorithms in parallel to analyZe different types of character
`istics embedded in given data, e.g., running a temporal-based
`algorithm (e.g., a Markov model) to examine sequence or
`temporal characteristics, and running frequency-based (e.g.,
`cluster analysis algorithms) to analyZe frequency clustering.
`Of course, the system can also run the same algorithm in
`parallel to get similar information by analyZing data for dif
`ferent time periods, With the results then analyZed. An
`example of this approach Would be to run a Markov model in
`parallel With different WindoW siZes. In this example, the
`system can then determine Whether the intrusion or anomaly
`has appeared only recently.
`Note that the system can run algorithms in parallel to
`explore different types of machine, device or program fea
`tures. Examples of such characteristics or features include,
`Without limitation, resource utiliZation metrics, number of
`segment faults or abnormal terminations over a certain
`period, actual commands or queries being issued by users,
`parameters for system calls and other function calls, IP
`addresses, and the like. FIG. 5 illustrates a one examination
`level approach Where a set of four (4) algorithms are executed,
`With each algorithm testing against a different characteristic
`or feature and their outcomes are evaluated together to make
`decision about a next step. In this example, a ?rst algorithm
`502 is a Markov model running on system call sequences of a
`?rst given length (e.g., 40), a second algorithm 504 is also a
`Markov model, but one that runs on system call sequences of
`a second given length (e.g., 8). A k-means algorithm 506
`executes on relative sensor frequency (e.g., 200 sensors per
`observation aggregate), and a fourth algorithm 508 examines
`segment faults or abnormal termination rates over a given
`time period (e.g., one minute). The output 510 of the ?rst
`algorithm 502 is an estimate of the probability of occurrence
`of the sequence represented by a value of a last sensor con
`catenated With the values from the sequence of the preceding
`39 sensors. The output 512 of the second algorithm 504 is an
`estimate of the probability of occurrence of the sequence
`represented by a value of a last sensor concatenated With the
`values from the sequence of the preceding 7 sensors. The
`output 514 of the third algorithm 506 is a distance value of a
`last