# US 2003/0200462 A1 · Method and system for establishing normal software system behavior and departures from normal behavior

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2003/0200462 A1
- Document ID: US20030200462A1
- Status: Published application
- Kind: A1
- Application number: 10/462,462
- Filed: 2003-06-16
- Published: 2003-10-23
- Earliest claimed: 1999-05-11
- Assignees: Software Systems International LLC
- Inventors: John C. Munson
- Web page: https://patentgrep.com/patent/US20030200462A1

## CPC

- G06F 11/3698: Environments for analysis, debugging or testing of software
- G06F 11/3612: {by runtime analysis (performance monitoring G06F11/3466)}
- G06F 11/3636: {by tracing the execution of the program}
- G06F 11/3644: {by instrumenting at runtime}
- G06F 21/55: Detecting local intrusion or implementing counter-measures
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Detecting abnormal activity of a software system is based on behavioral information obtained from an instrumented computer program while it executes. As the program executes, it expresses information about the sequence and frequency with which program modules are called. Over time, this sequence and frequency defines the normal behavior of the program, and the information expressed on any given run is compared to this normal behavior. Statistical analysis of the differences between the normal behavior and the current run can be used to detect unauthorized or abusive use of the program. Program modules whose behavior is highly correlated can be grouped into a smaller number of virtual modules. Comparison between current and normal program behavior can then be made on the (smaller number of) virtual modules, thereby reducing the dimensionality of the problem of analyzing the differences between current and normal program behavior.

## Claims

### Claim 1

A method for detecting an anomalous operation of a computer system that executes a plurality of program modules, the method comprising:
(a) monitoring transitions between and among defined points within an internal operating environment on the computer system and producing program execution trace data;
(b) comparing the program execution trace data with data indicative of a nominal operation of the computer system; and
(c) identifying an anomalous operation of the computer system based on the result of the comparison.

### Claim 2 (depends on 1)

A method as recited in claim 1, wherein the data indicative of a nominal operation of the computer system comprises a plurality of values (ra,b) and wherein the comparing act comprises:
determining the difference da,b=ra,b−r′a,b,
wherein ra,b represents the correlation between the ath program module and the bth program module over j eras, and wherein r′a,b represents the correlation between the ath program module and the bth program module over j+1 eras which comprise the first j eras plus one additional era, whereby the operation of the computer system during the one additional era is compared to the operation of the computer system during the first j eras.

### Claim 3 (depends on 2)

A method as recited in claim 2, wherein each program module is associated with one of k different classes, and wherein said difference is considered only for one or more pairs of program modules (a,b) that satisfy the condition that a and b are members of the same class.

### Claim 4 (depends on 3)

A method as recited in claim 3, wherein the comparing act further comprises:
determining the total difference:
19 d t = ∑ i = 1 k ⁢ ∑ ⁢ a , ⁢ b ∈ o i ⁢ | r a , ⁢ b - r a , ⁢ b ′ | , ⁢
wherein oi is the set of program modules belonging to the ith one of said k different classes.

### Claim 5 (depends on 4)

A method as recited in claim 4, wherein the total difference is computed based on corresponding triangles of the matrices represented by ra,b and r′a,b.

### Claim 6 (depends on 5)

A method as recited in claim 5, wherein the total difference is determined by computing:
20 d t = ∑ i = 1 k ⁢ ⁢ ∑ a , ⁢ b ∈ o i , ⁢ a < b ⁢ | l a , ⁢ b - l a , ⁢ b ′ | ,
wherein l and l′ are the lower triangles of the matrices represented by r and r′.

### Claim 7 (depends on 2)

A method as recited in claim 2, wherein ra,b is computed according to the following formulas:
21 r a , b = ∑ i = 1 j ⁢ ⁢ Z a , i ⁢ Z b , i , zi,•=xi,•−{overscore (x)}i/σi, 22 x _ i = 1 j ⁢ ∑ k = 1 j ⁢ x i , k , and σ i = 1 j - 1 ⁢ ∑ k = 1 j ⁢ ( x i , k - x _ i ) ,
wherein xm,n is the number of times that the mth program module executed during the nth era.

### Claim 8 (depends on 2)

A method as recited in claim 2, wherein each era comprises the period during which invocation of any of the program modules has occurred a predetermined number (K) times, such that a new era begins each time that K invocations have taken place since the current era began.

### Claim 9 (depends on 1)

A method as recited in claim 1, wherein each program module implements a predefined functional requirement.

### Claim 10 (depends on 9)

A method as recited in claim 9, wherein each program module includes a mechanism for calling another module, and the method further comprises the use of a statistical methodology to identify a relatively small set of cohesive program modules that represent the dynamic bindings among program modules as they execute.

### Claim 11 (depends on 10)

A method as recited in claim 10, wherein defined points are employed to monitor the activity of an executing program and to indicate an epoch in the execution of the program.

### Claim 12 (depends on 11)

A method as recited in claim 11, further comprising recording, in an execution profile for the program, telemetry from the defined points at each epoch.

### Claim 13 (depends on 12)

A method as recited in claim 12, wherein the execution profile comprises an n element vector (X) comprising at least one entry for each program module.

### Claim 14 (depends on 13)

A method as recited in claim 13, wherein each element, xi, of said vector contains a frequency count for the number of times that the corresponding defined point mi has executed during an era of k epochs, where
23 k = ∑ i = 1 n ⁢ x i .

### Claim 15 (depends on 14)

A method as recited in claim 14, wherein an execution profile is recorded whenever the number of epochs, k, reaches a predefined count, K, at which time the contents of the execution profile vector is set to zero.

### Claim 16 (depends on 15)

A method as recited in claim 15, wherein the recorded activity of the program during its last L=jK epochs is stored in a sequence of j execution profiles, X1, X2 . . . , Xj, where the value xi,j represents the frequency of execution of the ith program module on the jth execution profile.

### Claim 17 (depends on 14)

A method as recited in claim 14, further comprising the step of reducing the size of the execution profiles from n, the number of defined points whose activity is highly correlated, to a smaller set of m virtual defined points whose activity is substantially uncorrelated.

### Claim 18 (depends on 17)

A method as recited in claim 17, wherein the statistical technique of principal components analysis is employed to reduce the dimensionality of the execution profiles.

### Claim 19 (depends on 17)

A method as recited in claim 17, wherein the statistical technique of principal factor analysis is employed to reduce the dimensionality of the execution profiles.

### Claim 20 (depends on 17)

A method as recited in claim 17, wherein an n×j, j>n data matrix D=X1, X2, . . . , Xj is factored into m virtual orthogonal module components, where m is less than n, whereby the dimensionality is reduced from n to m.

### Claim 21 (depends on 20)

A method as recited in claim 20, wherein an eigenvalue λi is associated with each of the m orthogonal components.

### Claim 22 (depends on 21)

A method as recited in claim 21, wherein the eigenvalues satisfy the relation
24 ∑ i = 1 n ⁢ λ i = n .

### Claim 23 (depends on 20)

A method as recited in claim 20, further comprising using a predefined stopping rule in determining a number of components extracted in an orthogonal structure representing an execution profile with reduced dimensionality.

### Claim 24 (depends on 23)

A method as recited in claim 23, wherein the stopping rule is: extract all components whose eigenvalues are greater that a predefined threshold.

### Claim 25 (depends on 23)

A method as recited in claim 23, wherein the stopping rule is: extract those components such that the proportion of variation represented by
25 v = 1 n ⁢ ∑ i = 1 m ⁢ λ i
is at least equal to a predefined value.

### Claim 26 (depends on 20)

A method as recited in claim 20, further comprising constructing a matrix (P), wherein said matrix is an n×m structure whose rows, p•j, contain values showing the degree of relationship of the variation of the ith program module and the jth factor or principal component.

### Claim 27 (depends on 20)

A method as recited in claim 20, further comprising the step of forming a mapping vector (O) for at least one execution profile vector.

### Claim 28 (depends on 27)

A method as recited in claim 27, wherein the mapping vector, O, comprises elements oj whose values are defined as follows:
let
26 q i = max 1 ≤ j ≤ m ⁢ p ij ⁢ ;
let oj=index (qj) represent the column number in which the corresponding value qj occurs.

### Claim 29 (depends on 28)

A method as recited in claim 28, wherein the mapping vector contains data to map probe event frequencies recorded in the execution profile vector onto corresponding virtual module equivalents.

### Claim 30 (depends on 29)

A method as recited in claim 29, wherein a frequency count for each defined point k in an execution profile vector is represented by a value fk, and the mapping vector element ok contains an the index value that k maps into.

### Claim 31 (depends on 20)

A method as recited in claim 20, wherein m orthogonal sources of variation in the data vector D representing the original n defined points is identified.

### Claim 32 (depends on 30)

A method as recited in claim 30, wherein, on each of the original raw execution profiles, the defined point frequency count is represented in the elements, xi,j of the profile vector, Xi.

### Claim 33 (depends on 27)

A method as recited in claim 27, wherein a frequency count for each defined point k in an execution profile vector is represented by a value fk; wherein the mapping vector element ok contains an the index value that k maps into; wherein the mapping vector contains data to map probe event frequencies recorded in the execution profile vector onto corresponding virtual module equivalents; and wherein, after the mapping vector has been established, a virtual profile vector (Yi) is employed to contain the frequency counts for interactions among virtual execution domain sets.

### Claim 34 (depends on 33)

A method as recited in claim 33, wherein the virtual profile vector, Yi, is defined by:
27 y k , • = ∑ i = 1 n ⁢ f ⁡ ( x i , ⁢ • ) ⁢ where , [IndentingNewLine] ⁢ f ⁡ ( x i , • ) = { 0 if ⁢ ⁢ o i ≠ k x i , • otherwise .

### Claim 35

A method for detecting an anomalous operation of a computer system that comprises a plurality of program modules, the method comprising:
(a) monitoring transitions between and among instrumentation points within an operating environment on the computer system, wherein said monitoring is performed by employing signals obtained from instrumented code in the program modules;
(b) providing program instrumentation trace data representative of the transitions between and among program modules within a time frame;
(c) identifying a relatively small set of virtual execution domains whose activity is substantially uncorrelated, and using this information to reduce the amount of trace data needed to detect anomalous activity;
(d) comparing the reduced amount of trace data with predefined data indicative of a nominal operation of the computer system; and
(e) identifying an anomalous operation of the computer system based on the result of the comparison.

### Claim 36 (depends on 35)

A method as recited in claim 35, wherein the data indicative of a nominal operation of the computer system comprises a plurality of values (ra,b) and wherein the comparing act comprises:
determining the difference da,b=ra,b−ra,b,
wherein ra,b represents the correlation between the ath program module and the bth program module over j eras, and wherein r′a,b represents the correlation between the ath program module and the bth program module over j+1 eras which comprise the first j eras plus one additional era, whereby the operation of the computer system during the one additional era is compared to the operation of the computer system during the first j eras.

### Claim 37 (depends on 36)

A method as recited in claim 36, wherein each program module is associated with one of the virtual execution domains, and wherein said difference is considered only for one or more pairs of program modules (a,b) that satisfy the condition that a and b are members of the same class.

### Claim 38 (depends on 37)

A method as recited in claim 37, wherein the comparing act further comprises:
determining the total difference:
28 d t = ∑ i = 1 k ⁢ ∑ a , b ∈ o ⁢ ⁢ i | r a , b - ( r ′ ) a , b | ,
wherein there are k different virtual execution domains, and wherein oi is the set of program modules belonging to the ith one of said k different virtual execution domains.

### Claim 39 (depends on 38)

A method as recited in claim 38, wherein the total difference is computed based on corresponding triangles of the matrices represented by ra,b and r′a,b.

### Claim 40 (depends on 39)

A method as recited in claim 39, wherein the total difference is determined by computing:
29 d t = ∑ i = 1 k ⁢ ∑ a , b ∈ o ⁢ ⁢ i , a < b | l a , b - ( l ′ ) a , b | ,
wherein l and l′ are the lower triangles of the matrices represented by r and r′.

### Claim 41 (depends on 36)

A method as recited in claim 36, wherein ra,b is computed according to the following formulas:
30 r a , b = ∑ i = 1 j ⁢ ⁢ Z a , i ⁢ Z b , i , zi,•=xi,•−{overscore (x)}i/σi, 31 X _ i = 1 j ⁢ ∑ k = 1 j ⁢ X i , k , and σ i = 1 j - 1 ⁢ ∑ k = 1 j ⁢ ( X i , k - X _ i ) ,
wherein xm,n is the number of times that the mth program module executed during the nth era.

### Claim 42 (depends on 36)

A method as recited in claim 36, wherein each era comprises the period during which invocation of any of the program modules has occurred a predetermined number (K) times, such that a new era begins each time that K invocations have taken place since the current era began.

### Claim 43 (depends on 35)

A method as recited in claim 35, wherein said program execution trace data is employed to provide an execution profile including a list of execution paths that have executed in a specified time frame and the frequencies of executions.

### Claim 44

A computer system, comprising:
(a) a plurality of program modules;
(b) monitoring means for monitoring transitions between and among defined points within the program modules, wherein said monitoring is performed by employing signals obtained from instrumented code in the program modules, and for providing trace data representative of the transitions between or among program modules within a time frame;
(c) means for identifying a relatively small set of virtual execution domains whose activity is substantially uncorrelated, and using this information to reduce the amount of trace data needed to detect anomalous activity;
(d) means for comparing the reduced amount of trace data with predefined data indicative of a nominal operation of the computer system; and
(e) means for identifying an anomalous operation of the computer system based on the result of the comparison.

### Claim 45 (depends on 44)

A computer system as recited in claim 44, wherein the data indicative of a nominal operation of the computer system comprises a plurality of values (ra,b) and wherein the means for comparing determines the difference
da,b=ra,b−ra,b,
wherein ra,b represents the correlation between the ath program module and the bth program module over j eras, and wherein r′a,b represents the correlation between the ath program module and the bth program module over j+1 eras which comprise the first j eras plus one additional era, whereby the operation of the computer system during the one additional era is compared to the operation of the computer system during the first j eras.

### Claim 46 (depends on 45)

A computer system as recited in claim 45, wherein each program module is associated with one of the virtual execution domains, and wherein said difference is considered only for one or more pairs of program modules (a,b) that satisfy the condition that a and b are members of the same class.

### Claim 47 (depends on 46)

A computer system as recited in claim 46, wherein the means for comparing determines the total difference:
32 d t = ∑ i = 1 k ⁢ ∑ a , b ∈ o ⁢ ⁢ i ⁢ [LeftBracketingBar] r a , b - r a , b ′ [RightBracketingBar] ,
wherein there are k different virtual execution domains, and wherein oi is the set of program modules belonging to the ith one of said k different virtual execution domains.

### Claim 48 (depends on 47)

A computer system as recited in claim 47, wherein the total difference is computed based on corresponding triangles of the matrices represented by ra,b and r′a,b.

### Claim 49 (depends on 48)

A computer system as recited in claim 48, wherein the total difference is determined by computing:
33 d t = ∑ i = 1 k ⁢ ∑ a , b ∈ o ⁢ ⁢ i , a < b ⁢ [LeftBracketingBar] l a , b - l a , b ′ [RightBracketingBar] ,
wherein l and l′ are the lower triangles of the matrices represented by r and r′.

### Claim 50 (depends on 45)

A method as recited in claim 45, wherein ra,b is computed according to the following formulas:
34 r a , b = ∑ i = 1 j ⁢ z a , i ⁢ z b , i , zi,•=xi,•−{overscore (x)}i/σi, 35 X _ i = 1 j ⁢ ∑ k = 1 j ⁢ X i , k , and σ i = 1 j - 1 ⁢ ∑ k = 1 j ⁢ ( X i , k - X _ i ) ,
wherein xm,n is the number of times that the mth program module executed during the nth era.

### Claim 51 (depends on 45)

A computer system as recited in claim 45, wherein each era comprises the period during which invocation of any of the program modules has occurred a predetermined number (K) times, such that a new era begins each time that K invocations have taken place since the current era began.

### Claim 52 (depends on 44)

A system as recited in claim 44, wherein said trace data is employed to provide an execution profile including a list of execution paths that have executed in a specified time frame and the frequencies of executions.

### Claim 53 (depends on 44)

A system as recited in claim 44, further comprising recording, in a first execution profile for the program, telemetry from the defined points at each epoch.

### Claim 54 (depends on 53)

A system as recited in claim 53, wherein the first execution profile comprises an n element vector (X) comprising at least one entry for each program module, and wherein each element, xi, of said vector contains a frequency count for the number of times that the corresponding defined point mi has executed during an era of k epochs, where
36 k = ∑ i = 1 n ⁢ x i ;
and wherein an execution profile is recorded whenever the number of epochs, k, reaches a predefined count, K, at which time the contents of the execution profile vector is set to zero.

### Claim 55 (depends on 54)

A system as recited in claim 54, wherein the recorded activity of the program during its last L=jK epochs is stored in a sequence of j execution profiles, X1, X2, . . . , Xj, where the value xi,j represents the frequency of execution of the ith program module on the jth execution profile.

### Claim 56 (depends on 55)

A system as recited in claim 55, further comprising the step of reducing the dimensionality of the execution profiles from n, the number of defined points whose activity is highly correlated, to a smaller set of m virtual points whose activity is uncorrelated.

### Claim 57 (depends on 56)

A system as recited in claim 56, wherein an n×j, j>n data matrix D=X1, X2, . . . , Xj is factored into m virtual orthogonal module components, where m is less than n, whereby the dimensionality is reduced from n to m.

### Claim 58

A method for evaluating the behavior of a computer program, the computer program comprising a plurality of program modules, the method comprising:
associating each of the program modules with one of a plurality of virtual modules;
generating first data indicative of the normal behavior of the computer program, the first data comprising, for each pair of program modules (a,b), a value indicative of the correlation between the occurrence of invoking program module a and the occurrence of invoking program module b;
based on an execution of the computer program, generating second data indicative of the behavior of the computer program during said execution, said second data comprising, for each pair of program modules (a,b), a value indicative of the correlation between the occurrence of invoking program module a and the occurrence of invoking program module b;
comparing said first data with said second data by comparing the value in the first data associated with a pair of program modules (m1,m2) with the value in the second data associated with the same pair of program modules (m1,m2), wherein m1 and m2 are associated with the same virtual module; and
determining whether the computer program exhibited normal behavior during said execution based on the result of said comparing act.

### Claim 59 (depends on 58)

A method as recited in claim 58, wherein an execution profile of the computer program has been taken a plurality of times, and wherein a matrix X represents the results of the execution profiles, wherein each of the values of the matrix (xi,j) represents the number of times that the ith program module was invoked during the jth execution profile, and wherein the matrix is factored into a number m of virtual orthogonal components based on an eigenvalue (λi).

### Claim 60 (depends on 59)

A method as recited in claim 59, wherein each of the virtual orthogonal components satisfies the condition:
λi≧t,
wherein t is a threshold value.

### Claim 61 (depends on 59)

A method as recited in claim 59, wherein each of the virtual orthogonal components satisfies the condition:
37 t ≥ 1 n ⁢ ∑ i = 1 n ⁢ λ i ,
wherein n is the number of program modules.

### Claim 62 (depends on 58)

A method as recited in claim 58, wherein said associating act comprises:
determining a degree of correlation between each of the program modules and each of the virtual modules;
associating each of the program modules with the virtual module with which the program module's degree of correlation is the highest.

### Claim 63 (depends on 62)

A method as recited in claim 62, wherein a matrix P is an n×m matrix whose elements are pi,j, each element representing the degree of correlation between the ith program module and the jth virtual module, and wherein the virtual module with which a program module's correlation is the highest is determined by computing:
38 q i = max 1 ≤ j ≤ m ⁢ ⁢ p i , j
wherein m is the number of virtual modules, and wherein n is the number of program modules.

### Claim 64 (depends on 58)

A method as recited in claim 58, wherein said first data comprise a matrix R, whose values are ra,b, each value ra,b representing a degree of correlation between the occurrence of invoking program module a and the occurrence of invoking program module b.

### Claim 65 (depends on 64)

A method as recited in claim 64, further comprising:
partitioning the matrix R into m matricies R1, . . . , Rm, such that each partitioned matrix Ri comprises those elements ra,b of R that satisfy the condition that program module a and program module b are both associated with the ith virtual module.

### Claim 66 (depends on 64)

A method as recited in claim 64, wherein each of the values ra,b is computed according to the following formulas:
39 r a , b = ∑ i = 1 j ⁢ z a , i ⁢ z b , i , zi,•=xi,•−{overscore (x)}i/σi, 40 X _ i = 1 j ⁢ ∑ k = 1 j ⁢ X i , k , and σ i = 1 j - 1 ⁢ ∑ k = 1 j ⁢ ( X i , k - X _ i ) ,
wherein xm,n is the number of times that the mth program module executed during the nth time that execution of the computer program was profiled, and wherein j is the number of times that execution of the computer program was profiled in determining the computer program's normal behavior.

### Claim 67 (depends on 64)

A method as recited in claim 64, wherein the first data indicative of normal behavior of the computer program is generated by profiling the execution of the computer program a predetermined number of times (j), and wherein said second data comprise a matrix R′, each value r′a,b representing a degree of correlation between the occurrence of invoking program module a and the occurrence of invoking program module b based on the original j times that the execution of the computer program was profiled plus one additional execution profile of the computer program.

### Claim 68 (depends on 67)

A method as recited in claim 67, wherein said comparing act comprises computing the value:
da,b=ra,b−r′a,b,
for at least one pair of program modules a and b that satisfy the condition that program module a and program module b are both associated with the same virtual module.

### Claim 69 (depends on 67)

A method as recited in claim 67, wherein said comparing act comprises evaluating the differences between values in corresponding triangles of the matrices R and R′.

### Claim 70 (depends on 69)

A method as recited in claim 69, wherein said comparing act comprises computing the value:
41 d t = ∑ i = 1 k ⁢ ⁢ ∑ a , ⁢ b ∈ oi , ⁢ a < b ⁢ | l a , ⁢ b - l a , ⁢ b ′ | ,
wherein l and l′ are the lower triangles of the matrices R and R′.
