US 5,440,723 A · Automatic immune system for computers and computer networks

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.

Claims46

Dependent claims

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.

7 more elements

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.

8 more elements

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.

12 more elements

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.

9 more elements

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.

10 more elements

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.

16 more elements

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.

5 more elements

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.

8 more elements

Dependencies are inferred from the claim text.

Automatic immune system for computers and computer networks

Life of this patent

Automatic immune system for computers and computer networks

Life of this patent

Abstract

Claims46