Method and system for establishing normal software system behavior and departures from normal behavior

• US 20030200462A1
• Filed: 06/16/2003
• Published: 10/23/2003
• Est. Priority Date: 05/11/1999
• Status: Active Grant

• Current Assignee: StrataCloud, Inc. (Exitlag LLC)
• Original Assignee: Software Systems International, LLC
• Inventors: Munson, John C.
• Granted Patent: US 7,185,367 B2
• Time in Patent Office: Days
• US Class Current: 713/200
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 11/3644 by instrumenting at runtime
• CPC Class Codes: G06F 11/3664 Environments for testing or debugging software
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures

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

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.

2. 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 d_a,b=r_a,b−

r′

_a,b,

wherein r_a,b represents the correlation between the a^th program module and the b^th program module over j eras, and wherein r′

_a,b represents the correlation between the a^th program module and the b^th 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.

3. 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.

4. A method as recited in claim 3, wherein the comparing act further comprises:

determining the total difference;

$d_t=\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\underset{\text{\hspace{1em}<br><br>}<br><br>a,\text{\hspace{1em}<br><br>}<br><br>b\in <br><br>o_i}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}\left|r_{a,\text{\hspace{1em}<br><br>}<br><br>b}-r_{a,\text{\hspace{1em}<br><br>}<br><br>b}^{\mathrm{\prime <br><br>}}\right|,<br><br>\text{\hspace{1em}<br><br>}$

 

wherein o_i is the set of program modules belonging to the i^th one of said k different classes.

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

_a,b.

6. A method as recited in claim 5, wherein the total difference is determined by computing:

7. A method as recited in claim 2, wherein r_a,b is computed according to the following formulas:

$r_{a,b}=\underset{i=1}{\overset{j}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>Z_{a,i}<br><br>Z_{b,i},$z_i,•

=x_i,•

−

{overscore (x)}_i/σ

_i, $\begin{array}{c}{\stackrel{\_}{x}}_i=\frac{1}{j}<br><br>\underset{k=1}{\overset{j}{\sum <br><br>}}<br><br>x_{i,k},\mathrm{and}\\ {\mathrm{\sigma <br><br>}}_i=\frac{1}{j-1}<br><br>\underset{k=1}{\overset{j}{\sum <br><br>}}<br><br>\left(x_{i,k}-{\stackrel{\_}{x}}_i\right),\end{array}$

wherein x_m,n is the number of times that the m^th program module executed during the n^th era.

8. 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.

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

10. 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.

11. 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.

12. 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.

13. 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.

14. A method as recited in claim 13, wherein each element, x_i, of said vector contains a frequency count for the number of times that the corresponding defined point m_i has executed during an era of k epochs, where

15. 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.

16. 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, X₁, X₂ . . . , X_j, where the value x_i,j represents the frequency of execution of the i^th program module on the j^th execution profile.

17. 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.

18. 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.

19. 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.

20. A method as recited in claim 17, wherein an n×

j, j>

n data matrix D=X₁, X₂, . . . , X_j is factored into m virtual orthogonal module components, where m is less than n, whereby the dimensionality is reduced from n to m.

21. A method as recited in claim 20, wherein an eigenvalue λ

_i is associated with each of the m orthogonal components.

22. A method as recited in claim 21, wherein the eigenvalues satisfy the relation

23. 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.

24. A method as recited in claim 23, wherein the stopping rule is:

extract all components whose eigenvalues are greater that a predefined threshold.

25. A method as recited in claim 23, wherein the stopping rule is:

extract those components such that the proportion of variation represented by

26. A method as recited in claim 20, further comprising constructing a matrix (P), wherein said matrix is an n×

m structure whose rows, p<sub>•

j</sub>, contain values showing the degree of relationship of the variation of the i^th program module and the j^th factor or principal component.

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

28. A method as recited in claim 27, wherein the mapping vector, O, comprises elements o_j whose values are defined as follows:

let

$q_i=\begin{array}{c}\max \\ 1\le <br><br>j\le <br><br>m\end{array}<br><br>p_{\mathrm{ij}}<br><br>\text{;<br><br>}$

let o_j=index (q_j) represent the column number in which the corresponding value q_j occurs.

29. 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.

30. 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 f_k, and the mapping vector element o_k contains an the index value that k maps into.

31. 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.

32. 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, x_i,j of the profile vector, X_i.

33. 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 f_k;

wherein the mapping vector element o_k 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 (Y_i) is employed to contain the frequency counts for interactions among virtual execution domain sets.

34. A method as recited in claim 33, wherein the virtual profile vector, Y_i, is defined by:

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.

36. A method as recited in claim 35, wherein the data indicative of a nominal operation of the computer system comprises a plurality of values (r_a,b) and wherein the comparing act comprises:

determining the difference d_a,b=r_a,b−

r_a,b,

wherein r_a,b represents the correlation between the a^th program module and the b^th program module over j eras, and wherein r′

_a,b represents the correlation between the a^th program module and the b^th 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.

37. 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.

38. A method as recited in claim 37, wherein the comparing act further comprises:

determining the total difference;

$d_t=\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\underset{a,b\in <br><br>o<br><br>\text{\hspace{1em}<br><br>}<br><br>i}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}\left|r_{a,b}-{\left(r^{\mathrm{\prime <br><br>}}\right)}_{a,b}\right|,$

 

wherein there are k different virtual execution domains, and wherein o_i is the set of program modules belonging to the i^th one of said k different virtual execution domains.

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

_a,b.

40. A method as recited in claim 39, wherein the total difference is determined by computing:

41. A method as recited in claim 36, wherein r_a,b is computed according to the following formulas:

$r_{a,b}=\underset{i=1}{\overset{j}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>Z_{a,i}<br><br>Z_{b,i},$z_i,•

=x_i,•

−

{overscore (x)}_i/σ

_i, ${\stackrel{\_}{X}}_i=\frac{1}{j}<br><br>\underset{k=1}{\overset{j}{\sum <br><br>}}<br><br>X_{i,k},\mathrm{and}$${\mathrm{\sigma <br><br>}}_i=\frac{1}{j-1}<br><br>\underset{k=1}{\overset{j}{\sum <br><br>}}<br><br>\left(X_{i,k}-{\stackrel{\_}{X}}_i\right),$

wherein x_m,n is the number of times that the m^th program module executed during the n^th era.

42. 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.

43. 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.

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.

45. 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 (r_a,b) and wherein the means for comparing determines the difference

d_a,b=r_a,b−

r_a,b,

wherein r_a,b represents the correlation between the a^th program module and the b^th program module over j eras, and wherein r′

_a,b represents the correlation between the a^th program module and the b^th 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.

46. 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.

47. A computer system as recited in claim 46, wherein the means for comparing determines the total difference:

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

_a,b.

49. A computer system as recited in claim 48, wherein the total difference is determined by computing:

50. A method as recited in claim 45, wherein r_a,b is computed according to the following formulas:

$r_{a,b}=\underset{i=1}{\overset{j}{\sum <br><br>}}<br><br>z_{a,i}<br><br>z_{b,i},$z_i,•

=x_i,•

−

{overscore (x)}_i/σ

_i, ${\stackrel{\_}{X}}_i=\frac{1}{j}<br><br>\underset{k=1}{\overset{j}{\sum <br><br>}}<br><br>X_{i,k},\mathrm{and}$${\mathrm{\sigma <br><br>}}_i=\frac{1}{j-1}<br><br>\underset{k=1}{\overset{j}{\sum <br><br>}}<br><br>\left(X_{i,k}-{\stackrel{\_}{X}}_i\right),$

wherein x_m,n is the number of times that the m^th program module executed during the n^th era.

51. 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.

52. 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.

53. 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.

54. 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, x_i, of said vector contains a frequency count for the number of times that the corresponding defined point m_i has executed during an era of k epochs, where

55. 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, X₁, X₂, . . . , X_j, where the value x_i,j represents the frequency of execution of the i^th program module on the j^th execution profile.

56. 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.

57. A system as recited in claim 56, wherein an n×

j, j>

n data matrix D=X₁, X₂, . . . , X_j is factored into m virtual orthogonal module components, where m is less than n, whereby the dimensionality is reduced from n to m.

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 (m₁,m₂) with the value in the second data associated with the same pair of program modules (m₁,m₂), wherein m₁ and m₂ 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.

59. 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 (x_i,j) represents the number of times that the i^th program module was invoked during the j^th execution profile, and wherein the matrix is factored into a number m of virtual orthogonal components based on an eigenvalue (λ

_i).

60. 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.

61. A method as recited in claim 59, wherein each of the virtual orthogonal components satisfies the condition:

62. 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.

63. A method as recited in claim 62, wherein a matrix P is an n×

m matrix whose elements are p_i,j, each element representing the degree of correlation between the i^th program module and the j^th virtual module, and wherein the virtual module with which a program module'"'"'s correlation is the highest is determined by computing;

64. A method as recited in claim 58, wherein said first data comprise a matrix R, whose values are r_a,b, 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.

65. A method as recited in claim 64, further comprising:

partitioning the matrix R into m matricies R₁, . . . , R_m, such that each partitioned matrix R_i comprises those elements r_a,b of R that satisfy the condition that program module a and program module b are both associated with the i^th virtual module.

66. A method as recited in claim 64, wherein each of the values r_a,b is computed according to the following formulas:

$r_{a,b}=\underset{i=1}{\overset{j}{\sum <br><br>}}<br><br>z_{a,i}<br><br>z_{b,i},$z_i,•

=x_i,•

−

{overscore (x)}_i/σ

_i, ${\stackrel{\_}{X}}_i=\frac{1}{j}<br><br>\underset{k=1}{\overset{j}{\sum <br><br>}}<br><br>X_{i,k},\mathrm{and}$${\mathrm{\sigma <br><br>}}_i=\frac{1}{j-1}<br><br>\underset{k=1}{\overset{j}{\sum <br><br>}}<br><br>\left(X_{i,k}-{\stackrel{\_}{X}}_i\right),$

wherein x_m,n is the number of times that the m^th program module executed during the n^th 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.

67. 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.

68. A method as recited in claim 67, wherein said comparing act comprises computing the value:

d_a,b=r_a,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.

69. 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′

.

70. A method as recited in claim 69, wherein said comparing act comprises computing the value: