Automatic immune system for computers and computer networks

• US 5,440,723 A
• Filed: 01/19/1993
• Issued: 08/08/1995
• Est. Priority Date: 01/19/1993
• Status: Expired due to Term

• Current Assignee: Trend Micro Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Arnold, William C., Chess, David M., Kephart, Jeffrey O., White, Steven R.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Palys, Joseph E.
• Application Number:
  US08/004,872
• Time in Patent Office: 931 Days
• Field of Search: 395/575, 371/16.5, 371/19, 371/11.2, 371/8.2
• US Class Current: 714/2
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: G06F 21/566 Dynamic detection, i.e. detection performed at run-time, e.g. emulation, suspicious activities
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002

Abstract

A method includes the following component steps, or some functional subset of these steps: (A) periodic monitoring of a data processing system (10) for anomalous behavior that may indicate the presence of an undesirable software entity such as a computer virus, worm, or Trojan Horse; (B) automatic scanning for occurrences of known types of undesirable software entities and taking remedial action if they are discovered; (C) deploying decoy programs to capture samples of unknown types of computer viruses; (D) identifying machine code portions of the captured samples which are unlikely to vary from one instance of the virus to another; (E) extracting an identifying signature from the executable code portion and adding the signature to a signature database; (F) informing neighboring data processing systems on a network of an occurrence of the undesirable software entity; and (G) generating a distress signal, if appropriate, so as to call upon an expert to resolve difficult cases. A feature of this invention is the automatic execution of the foregoing steps in response to a detection of an undesired software entity, such as a virus or a worm, within a data processing system. The automatic extraction of the identifying signature, the addition of the signature to a signature data base, and the immediate use of the signature by a scanner provides protection from subsequent infections of the system, and also a network of systems, by the same or an altered form of the undesirable software entity.

Claims

1. A method for providing computational integrity for a digital data processing system, comprising the computer-executed steps of:

detecting, with a data processor, an anomalous behavior of a digital data processing system during program execution, the anomalous behavior being indicative of an undesirable informational state of the digital data processing system that may result from the presence of an undesirable software entity;

scanning, with the data processor, one or more portions of an informational state history of the digital data processing system to detect, if present, at least one known type of undesirable software entity;

in response to the detection of a known type of undesirable software entity, taking remedial action;

else, if a known type of undesirable software entity is not detected by the step of scanning, detecting, with the data processor, a previously unknown type of undesirable software entity;

extracting, with the data processor, an identifying signature from the detected undesirable software entity;

storing the identifying signature so as to enable a future detection of the undesirable software entity as a known type of undesirable software entity; and

taking remedial action;

wherein

the step of extracting includes the data processor executed steps of obtaining at least one sequence of bytes from the detected undesirable software entity, determining likelihoods that the at least one sequence of bytes is also found in program code that may be run on a digital data processing system which is to be protected from the undesirable software entity, and selecting as the extracted identifying signature a plurality of bytes from the at least one sequence that have a high likelihood of reliably identifying a future occurrence of the undesirable software entity.

3. A method as set forth in claim 1 wherein the step of storing stores the identifying signature into a data base of identifying signatures for use during the step of scanning.

4. A method as set forth in claim 1 and, in response to the detection of a known type of undesirable software entity, further including a step of operating a data communications means of the digital data processing system for notifying at least one other digital data processing system of the presence of the undesirable software entity.

5. A method as set forth in claim 1 and, in response to detecting a previously unknown type of undesirable software entity, further including a step of operating a data communications means of the digital data processing system for notifying at least one other digital data processing system of the presence of the undesirable software entity.

6. A method as set forth in claim 5 and further including a step of operating the data communications means of the digital data processing system for providing the at least one other digital data processing system with the identifying signature of the undesirable software entity.

7. A method as set forth in claim 1 wherein the undesirable software entity is a computer virus, wherein the step of detecting includes a step of obtaining at least one instance of a computer virus;

and wherein the step of extracting extracts the identifying signature from the obtained at least one instance of the computer virus.

8. A method as set forth in claim 1 wherein the undesirable software entity is a computer virus, and wherein the step of detecting includes the steps of:

operating at least one decoy program with the digital data processing system; and

comparing the decoy program to a secure copy of the decoy program so as to identify a modification of the decoy program, wherein a modification of the decoy program is indicative of an infection of the decoy program by the computer virus.

22. A method as set forth in claim 1 wherein the steps of taking remedial action each include a step of removing the undesirable software entity.

23. A method as set forth in claim 1 wherein the step of taking remedial action after the step of storing includes a step of scanning one or more portions of the informational state history of the digital data processing system to detect, if present, at least one further instance of the undesirable software entity;

and, in response to detecting at least one further instance of the undesirable software entity, the method includes a step of taking further remedial action.

28. A method as set forth in claim 1 wherein the step of detecting includes a step of deploying at least one decoy program to obtain a sample of the undesirable software entity.

2. A method for providing computational integrity for a digital data processing system, comprising the computer-executed steps of:

detecting, with a data processor, an anomalous behavior of a digital data processing system during program execution, the anomalous behavior being indicative of an undesirable informational state of the digital data processing system that may result from the presence of an undesirable software entity;

scanning, with the data processor, one or more portions of an informational state history of the digital data processing system to detect, if present, at least one known type of undesirable software entity;

in response to the detection of a known type of undesirable software entity, taking remedial action;

else, if a known type of undesirable software entity is not detected by the step of scanning, detecting, with the data processor, a previously unknown type of undesirable software entity;

extracting, with the data processor, an identifying signature from the detected undesirable software entity;

storing the identifying signature so as to enable a future detection of the undesirable software entity as a known type of undesirable software entity; and

taking remedial action;

wherein the step of extracting includes a preliminary step of analyzing the undesirable software entity to identify a portion thereof that remains substantially invariant from a first instance of the undesirable software entity to a second instance of the undesirable software entity, wherein the step of extracting extracts the identifying signature from the identified substantially invariant portion; and

wherein

the step of extracting includes the steps of obtaining a sequence of bytes from the identified substantially invariant portion of the undesirable software entity, decomposing the sequence of bytes into sub-sequences, determining likelihoods that the sub-sequences are also found in program code that may be run on a digital data processing system which is to be protected from the undesirable software entity, and selecting as the extracted identifying signature a plurality of bytes that have a high likelihood of reliably identifying a future occurrence of the undesirable software entity.

9. A method for providing computational integrity for a digital data processing system, comprising the computer-executed steps of:

detecting, with a data processor, an anomalous behavior of a digital data processing system during program execution, the anomalous behavior being indicative of an undesirable informational state of the digital data processing system that may result from the presence of an undesirable software entity;

scanning, with the data processor, one or more portions of an informational state history of the digital data processing system to detect, if present, at least one known type of undesirable software entity;

in response to the detection of a known type of undesirable software entity, taking remedial action;

else, if a known type of undesirable software entity is not detected by the step of scanning, detecting, with the data processor, a previously unknown type of undesirable software entity;

extracting, with the data processor, an identifying signature from the detected undesirable software entity;

storing the identifying signature so as to enable a future detection of the undesirable software entity as a known type of undesirable software entity; and

taking remedial action;

wherein the step of extracting includes the steps of;

obtaining at least one candidate signature of the undesirable software entity from at least one sample of the undesirable software entity, the at least one sample including a sequence of bytes of the undesirable software entity that is likely to remain invariant from a first instance of the undesirable software entity to a second instance of the undesirable software entity;

constructing a list of unique n-grams from the sequence of bytes, each of the unique n-grams being comprised of from one to some maximal number of sequential bytes contained in the sequence of bytes;

for each of the unique n-grams, estimating a probability of an occurrence of a unique n-gram within sequences of bytes obtained from a corpus of computer programs of a type that may be executed by the digital data processing system;

for each candidate signature that is comprised of one or more of the unique n-grams, wherein each candidate signature includes all possible sequences of the unique n-grams in the at least one sample which satisfy a predetermined criterion, estimating a probability of an occurrence of the candidate signature within the sequences of bytes obtained from the corpus of computer programs; and

accepting a candidate signature as a valid signature at least if the estimated probability of the occurrence of the candidate signature is less than a threshold probability, the threshold probability having a value selected to reduce a likelihood of an occurrence of a false positive indication during a subsequent execution of the step of scanning.

10. A method as set forth in claim 9 wherein the step of obtaining includes the initial steps of:

obtaining one or more instances of the undesirable software entity; and

evaluating the one or more instances to identify at least one portion that includes a sequence of bytes that represent machine code instructions of the undesirable software entity that appear in each of the one or more instances.

11. A method as set forth in claim 9 wherein the step of estimating a probability of an occurrence of a unique n-gram includes a step of recording a frequency of occurrence of the n-gram within the sequences of bytes obtained from the corpus of computer programs.

12. A method as set forth in claim 11 wherein for uni-grams (n=1), the estimated probability is given by the recorded frequency divided by a total number of n-grams of length equal to one;

and for n-grams (n≧

2) the estimated probability is given by a weighted average of the recorded frequency and a probability determined by combining together shorter n-grams.

13. A method as set forth in claim 12 wherein two (n-1)-gram probabilities and an (n-2)-gram probability are combined to form an n-gram probability (p) in accordance with the expression:

##EQU6## where B₁ to B_n are sequentially occurring bytes.

14. A method as set forth in claim 9 wherein the step of estimating a probability of an occurrence of a unique n-gram includes a step of looking up the n-gram, or some smaller constituent of the n-gram, within a predetermined table of probabilities that represents occurrences of n-grams within the sequences of bytes obtained from the corpus of computer programs.

15. A method as set forth in claim 9 wherein the step of estimating a probability of an occurrence of the candidate signature includes the step of estimating a probability of an exact match between the candidate signature and the sequences of bytes obtained from the corpus of computer programs.

16. A method as set forth in claim 15 wherein the step of estimating a probability of an exact match includes an initial step of replacing any bytes that may potentially vary, from a first instance of the undesirable software entity to a second instance, with a wildcard symbol that has an exact match with every byte in the sequences of bytes obtained from the corpus of computer programs.

17. A method as set forth in claim 16 wherein the step of estimating a probability of an exact match includes a second initial step of segregating the candidate signature into one or more contiguous blocks of bytes each of which contains no wildcard bytes, and wherein the exact match probability is found by multiplying together probabilities of each of the segregated one or more contiguous blocks of bytes.

18. A method as set forth in claim 9 wherein the step of estimating a probability of an occurrence of the candidate signature includes the step of estimating a probability of a partial match between the candidate signature and the sequences of bytes obtained from the corpus of computer programs.

19. A method as set forth in claim 18 wherein the step of estimating a probability of a partial match includes an initial step of replacing any bytes that may potentially vary, from a first instance of the undesirable software entity to a second instance, with a wildcard symbol that has an exact match with every byte in the sequences of bytes obtained from the corpus of computer programs.

20. A method as set forth in claim 18 wherein the step of estimating a probability of an occurrence of the partial match includes the step of estimating a probability of a fragment of the candidate signature matching the sequences of bytes obtained from the corpus of computer programs.

21. A method as set forth in claim 18 wherein the step of estimating a probability of an occurrence of the partial match includes the step of estimating a probability of all but M bytes of a sequence of bytes obtained from the corpus of computer programs not matching a byte in a corresponding position of the candidate signature.

24. A method as set forth in claim 9 wherein the step of accepting a candidate signature as a valid signature further employs a criterion that an estimated false-positive probability of the candidate signature has a value that is among the lowest of estimated false-positive probability values of all candidate signatures.

25. A method as set forth in claim 9 wherein the step of estimating a probability of an occurrence of the candidate signature includes the steps of:

estimating a first probability of an exact match between the candidate signature and the sequences of bytes obtained from the corpus of computer programs;

estimating a second probability of a fragment of the candidate signature matching the sequences of bytes obtained from the corpus of computer programs; and

estimating a third probability of at most M bytes of a sequence of bytes obtained from the corpus of computer programs not matching a byte in the candidate signature.

26. A method as set forth in claim 25 and further comprising the steps of:

combining the first, second, and third probability estimates to arrive at a final probability estimate; and

comparing the final probability estimate to the threshold probability.

27. A method as set forth in claim 26 and further comprising a step of reporting an identity of the valid signature.

29. A method for providing computational integrity for a network of digital data processing systems, comprising the computer-executed steps of:

detecting, with a data processor, an anomalous behavior of a digital data processing system during program execution, the anomalous behavior being indicative of the presence of an undesirable software entity within the digital data processing system that exhibits the anomalous behavior;

scanning, with the data processor, one or more portions of an informational state history of the digital data processing system to detect, if present, at least one known type of undesirable software entity;

in response to the detection of a known type of undesirable software entity, taking remedial action; and

operating the data processor for notifying at least one other digital data processing system on the network of the presence of the known type of undesirable software entity;

else, if a known type of undesirable software entity is not detected by the step of scanning, locating, with the data processor, a previously unknown type of undesirable software entity;

extracting, with the data processor, an identifying signature from the located previously unknown type of undesirable software entity;

storing the identifying signature so as to enable a future detection of the previously unknown type of undesirable software entity as a known type of undesirable software entity;

using the extracted identifying signature and the data processor to scan one or more portions of an informational state of the data processing system to detect other instances of the previously unknown type of undesirable software entity;

if another instance of the previously unknown type of undesirable software entity is detected using the extracted identifying signature, taking remedial action; and

operating the data processor for notifying at least one other digital data processing system on the network of the presence of the previously unknown type of undesirable software entity.

30. A method as set forth in claim 29 wherein at least the second step of notifying includes a step of providing the at least one other digital data processing system on the network with the identifying signature of the previously unknown type of undesirable software entity.

31. A method as set forth in claim 29 and including a further step of generating a distress signal if the digital data processing system if the step of locating fails to locate a previously unknown type of undesirable software entity.

33. A method as set forth in claim 29 wherein the step of storing stores the identifying signature into a data base of identifying signatures for use during the step of scanning.

34. A method as set forth in claim 29 wherein the undesirable software entity is a previously unknown type of computer virus, and wherein the step of locating includes a step of generating, with a digital data processing system, one or more instances of the unknown type of computer virus to increase a size of a sample population of the unknown type of computer virus;

and wherein the step of extracting extracts the identifying signature from the one or more instances of the unknown type of computer virus.

35. A method as set forth in claim 29 wherein the undesirable software entity is a computer virus, and wherein the step of detecting includes the steps of:

deploying at least one decoy program with the digital data processing system; and

comparing the at least one decoy program to a secure copy of the decoy program so as to identify a modification of the decoy program during the step of deploying, wherein a modification of the decoy program is indicative of an infection of the decoy program by the computer virus.

32. A method for providing computational integrity for a network of digital data processing systems, comprising the computer-executed steps of:

detecting, with a data processor, an anomalous behavior of a digital data processing system during program execution, the anomalous behavior being indicative of the presence of an undesirable software entity within the digital data processing system that exhibits the anomalous behavior;

scanning, with the data processor, one or more portions of an informational state history of the digital data processing system to detect, if present, at least one known type of undesirable software entity;

in response to the detection of a known type of undesirable software entity, taking remedial action; and

operating the data processor for notifying at least one other digital data processing system on the network of the presence of the known type of undesirable software entity;

else, if a known type of undesirable software entity is not detected by the step of scanning, locating, with the data processor, a previously unknown type of undesirable software entity;

extracting, with the data processor, an identifying signature from the located previously unknown type of undesirable software entity;

storing the identifying signature so as to enable a future detection of the previously unknown type of undesirable software entity as a known type of undesirable software entity;

using the extracted identifying signature and the data processor to scan one or more portions of an informational state of the data processing system to detect other instances of the previously unknown type of undesirable software entity;

if another instance of the previously unknown type of undesirable software entity is detected using the extracted identifying signature, taking remedial action; and

operating the data processor for notifying at least one other digital data processing system on the network of the presence of the previously unknown type of undesirable software entity;

wherein the step of extracting includes a preliminary step of analyzing the previously unknown type of undesirable software entity to identify a substantially invariant portion thereof, and wherein the step of extracting extracts the identifying signature from the substantially invariant portion.

36. A method for providing computational integrity for a network of digital data processing systems, comprising the computer-executed steps of:

detecting, with a data processor, an anomalous behavior of a digital data processing system during program execution, the anomalous behavior being indicative of the presence of an undesirable software entity within the digital data processing system that exhibits the anomalous behavior;

scanning, with the data processor, one or more portions of an informational state history of the digital data processing system to detect, if present, at least one known type of undesirable software entity;

in response to the detection of a known type of undesirable software entity, taking remedial action; and

operating the data processor for notifying at least one other digital data processing system on the network of the presence of the known type of undesirable software entity;

else, if a known type of undesirable software entity is not detected by the step of scanning, locating, with the data processor, a previously unknown type of undesirable software entity;

extracting, with the data processor, an identifying signature from the located previously unknown type of undesirable software entity;

storing the identifying signature so as to enable a future detection of the previously unknown type of undesirable software entity as a known type of undesirable software entity;

using the extracted identifying signature and the data processor to scan one or more portions of an informational state of the data processing system to detect other instances of the previously unknown type of undesirable software entity;

if another instance of the previously unknown type of undesirable software entity is detected using the extracted identifying signature, taking remedial action; and

operating the data processor for notifying at least one other digital data processing system on the network of the presence of the previously unknown type of undesirable software entity;

wherein the undesirable software entity is a previously unknown type of computer virus, and wherein the step of extracting includes the steps of;

obtaining at least one sample of the previously unknown type of computer virus, the at least one sample including a sequence of bytes of the computer virus that remains substantially invariant from a first instance of the computer virus to a second instance;

constructing a list of unique n-grams from the sequence of bytes, each of the unique n-grams being comprised of from one to n sequential bytes of the sequence of bytes;

for each of the unique n-grams, estimating a probability of an occurrence of a unique n-gram within sequences of bytes obtained from a corpus of computer programs of a type that may be executed by the digital data processing system;

for a candidate computer virus signature that is comprised of one or more of the unique n-grams, estimating a probability of an occurrence of the candidate computer virus signature within the sequences of bytes obtained from the corpus of computer programs; and

accepting the candidate computer virus signature as a valid computer virus signature at least if the estimated probability of the occurrence of the candidate computer virus signature is less than a threshold probability, the threshold probability having a value selected to reduce a likelihood of an occurrence of a false positive indication during a subsequent execution of the step of scanning.

37. A system providing computational integrity for a digital data processing system, comprising:

means for detecting an anomalous behavior of a digital data processing system during program execution, the anomalous behavior being indicative of the presence of an undesirable software entity that may be detrimental to the computational integrity of the digital data processing system;

means, responsive to the operation of said detecting means, for scanning one or more computer programs executed by the digital data processing system to detect, if present, at least one known type of undesirable software entity;

means, responsive to the detection of a known type of undesirable software entity, for removing a detected known type of undesirable software entity from the digital data processing system;

means, responsive to a failure to detect a known type of undesirable software entity, for locating a previously unknown type undesirable software entity that has associated itself with one or more programs that are executed by the digital data processing system;

means for extracting an identifying signature from the located previously unknown type of undesirable software entity;

means for removing the located previously unknown type of undesirable software entity from the digital data processing system; and

means for storing the identifying signature so as to enable a future detection of the previously unknown type of undesirable software entity as a known type of undesirable software entity.

39. A system as set forth in claim 37 and further including means, responsive to the detection of a known type of undesirable software entity, and further responsive to the extraction of an identifying signature from an unknown type of undesirable software entity, for notifying at least one other digital data processing system of the presence of the known or unknown type of undesirable software entity.

40. A system as set forth in claim 37 wherein the undesirable software entity is a computer virus, and wherein the means for detecting includes:

means for deploying at least one decoy program within the digital data processing system;

means for subsequently comparing the deployed decoy program to a secure copy of the decoy program so as to identify a modification of the decoy program, wherein a modification of the decoy program is indicative of an infection of the decoy program by the computer virus; and

means for obtaining a sample of the computer virus from the deployed decoy program and for providing the sample to said extracting means.

38. A system providing computational integrity for a digital data processing system, comprising:

means for detecting an anomalous behavior of a digital data processing system during program execution, the anomalous behavior being indicative of the presence of an undesirable software entity that may be detrimental to the computational integrity of the digital data processing system;

means, responsive to the operation of said detecting means, for scanning one or more computer programs executed by the digital data processing system to detect, if present, at least one known type of undesirable software entity;

means, responsive to the detection of a known type of undesirable software entity, for removing a detected known type of undesirable software entity from the digital data processing system;

means, responsive to a failure to detect a known type of undesirable software entity, for locating a previously unknown type undesirable software entity that has associated itself with one or more programs that are executed by the digital data processing system;

means for extracting an identifying signature from the located previously unknown type of undesirable software entity;

means for removing the located previously unknown type of undesirable software entity from the digital data processing system; and

means for storing the identifying signature so as to enable a future detection of the previously unknown type of undesirable software entity as a known type of undesirable software entity;

wherein the means for extracting is coupled to means for analyzing the located previously unknown type of undesirable software entity to identify a substantially invariant portion thereof, and wherein the means for extracting extracts the identifying signature from the substantially invariant portion.

41. A method for operating a network comprised of a plurality of data processors so as to provide protection from infection by an undesirable software entity, comprising the computer-executed steps of:

in response to a detection of an anomalous operation of a first one of the data processors of the network, operating the data processor to detect, within the data processor, an unknown type of undesirable software entity;

in response to detecting an unknown type of undesirable software entity, extracting, with the data processor, an identifying signature from the unknown type of undesirable software entity;

storing, within a first memory means that is accessible from the data processor, the identifying signature for subsequent use by the data processor in recognizing a subsequent occurrence of the undesirable software entity;

transmitting the identifying signature from the data processor to at least one other data processor that is connected to the network; and

storing, within a second memory means that is accessible by the at least one other data processor, the identifying signature for subsequent use by the at least one other data processor in recognizing an occurrence of the undesirable software entity.

42. A method as set forth in claim 41 wherein the unknown type of undesirable software entity is a worm.

43. A method as set forth in claim 41 wherein the unknown type of undesirable software entity is a computer virus.

46. A method as set forth in claim 41 and, further in response to the detection of anomalous operation of the first one of the data processors, performing a step of raising an alert state of the data processor so as to periodically monitor the data processor to detect, if present, a known type of undesirable software entity.

44. A method for operating a network comprised of a plurality of data processors so as to provide protection from infection by an undesirable software entity, comprising the computer-executed steps of:

in response to a detection of an anomalous operation of a first one of the data processors of the network, operating the data processor to detect, within the data processor, an unknown type of undesirable software entity;

in response to detecting an unknown type of undesirable software entity, extracting, with the data processor, an identifying signature from the unknown type of undesirable software entity;

storing, within a first memory means that is accessible from the data processor, the identifying signature for subsequent use by the data processor in recognizing a subsequent occurrence of the undesirable software entity;

transmitting the identifying signature from the data processor to at least one other data processor that is connected to the network; and

storing, within a second memory means that is accessible by the at least one other data processor, the identifying signature for subsequent use by the at least one other data processor in recognizing an occurrence of the undesirable software entity;

wherein the step of extracting includes the steps of;

analyzing the unknown type of undesirable software entity to identify at least one portion thereof that remains substantially invariant from a first instance of the unknown type of undesirable software entity to a second instance of the unknown type of undesirable software entity;

segregating the substantially invariant portion from other portions; and

performing the step of extracting on the segregated, substantially invariant portion.

45. A method as set forth in claim 44 wherein the step of analyzing includes the initial steps of:

deploying at least one decoy program to capture a sample of the unknown type of undesirable software entity; and

replicating the captured sample to provide at least one further instance of the unknown type of undesirable software entity.