Method for evolving detectors to detect malign behavior in an artificial immune system

• US 8,065,733 B2
• Filed: 09/18/2006
• Issued: 11/22/2011
• Est. Priority Date: 09/23/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Koelle, Katharina Veronika, Midwinter, Wendy
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): Hailu; Teshome
• Application Number:
  US11/532,855
• Publication Number:
  US 20070168484A1
• Time in Patent Office: 1,891 Days
• Field of Search: 726/23
• US Class Current: 726/23
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: G06F 21/56 Computer malware detection or handling, e.g. anti-virus arrangements
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

A system, apparatus, and method are directed to evolving detectors in an Artificial Immune System for use in detecting unauthorized computing activities. In one embodiment, a population of detectors is generated with a matching value and expectation value of zero. The detectors are then compared to logged fragments of system calls within a computing device to modify the matching value. When the matching value for a given detector is equal to or greater than an expectation value, the detector'"'"'s expectation value may be set to the matching value. The detectors may then evolve and/or generate other detectors using mutation, and/or recombination, or the like. Detectors continue to generate and/or to evolve until a detector'"'"'s matching value reaches a determined value, in which case, the detector may be evaluated to determine if an unauthorized activity is detected. If an unauthorized activity is detected, a detection response may be performed.

Claims

1. A network device for detecting an unauthorized client software activity, comprising:

a transceiver to send and receive data over the network; and

a processor that is operative to perform actions, including;

generating a detector, wherein the detector is a sequence of computer system calls;

determining, for the detector, an initial matching value and an expectation value;

comparing the detector to logged fragments of computer system calls associated with a computing process, and based on the comparison determining a new matching value for the detector;

if the new matching value of the detector is equal to or greater than the detector'"'"'s expectation value, evolving at least one child detector based on at least a copy of the detector and at least one mutation, modifying the detector'"'"'s expectation value, and modifying at least one child detector'"'"'s expectation value and the new matching value based on another comparison to the logged fragments of the computer system calls; and

if the expectation value for the detector or the at least one child detector exceeds a threshold value, evaluating that detector to determine if an unauthorized activity is detected.

2. The network device of claim 1, wherein evolving the at least one child detector further comprises performing at least one of a combination of the detector with another detector to generate the at least one child detector, or mutating the detector to generate the at least one child detector.

3. The network device of claim 1, wherein evaluating that detector to determine if an unauthorized activity is detected further comprises sending that detector to another network device, wherein the evaluation is performed by the other network device.

4. The network device of claim 1, wherein the processor is operative to perform actions, further comprising:

if the new matching value for the detector or the at least one child detector is below the expectation value, determining whether to delete that detector or child detector.

5. The network device of claim 1, wherein evaluating that detector to determine if an unauthorized activity is detected, further comprises, evaluating that detector against a self database to determine if the detector indicates a self or non-self status.

6. The network device of claim 1, wherein evolving at least one child detector based on the detector further comprises generating the at least one child detector, wherein for each child detector associating an initial matching value of zero with the generated child detector, and an initial expectation value based on the expectation value of the detector.

7. The network device of claim 1, wherein determining the new matching value for the detector further comprises, determining the new matching value based on a percentage of the detector that matches a fragment of the computer system calls associated with the computing process.

8. A method for detecting an unauthorized client software activity implemented by a processor executing instructions stored on a computer-readable storage medium, the method comprising:

generating a plurality of detectors, wherein each detector is a different sequence of computer system calls, and wherein each detector is assigned an initial matching value and an expectation value;

comparing each detector to at least one fragment of sequences of computer system calls associated with a computing process, and based on the comparison revising the determining a new matching value for each of the detectors;

if the new matching value for one of the detectors is equal to or greater than that detector'"'"'s expectation value, evolving at least one child detector based in part on at least a copy of that detector and at least one mutation, modifying that detector'"'"'s expectation value, and modifying at least one child detector'"'"'s expectation value and it'"'"'s matching value based on a comparison to the at least one fragment of sequences; and

if the expectation value for a detector in the plurality of detectors or the at least one child detector exceeds a threshold value, evaluating that detector or child detector to determine if an unauthorized activity is detected.

9. The method of claim 8, wherein evolving the at least one child detector further comprises combining that detector with at least another one of the plurality of detectors to generate the at least one child detector.

10. The method of claim 8, wherein evolving the at least one child detector further comprises randomly changing at least one computer system call in that detector'"'"'s sequence of computer system calls to generate the at least one child detector.

11. The method of claim 8, further comprising:

if the new matching value for the detector in the plurality of detectors or the at least one child detector is below the expectation value, determining whether to delete that detector or child detector.

12. The method of claim 8, wherein evolving at least one child detector based in part on that detector further comprises:

determining an initial expectation value for the at least one child detector based in part on the expectation value associated with that detector.

13. A computer-readable storage medium configured to include program instructions for performing the method of claim 8.

14. A system for detecting an unauthorized computing activity, comprising:

a server that is operative to perform actions, including;

generating a plurality of detectors, wherein each detector is a different sequence of computer system calls, and wherein each detector is assigned an initial matching value and an expectation value; and

sending the plurality of detectors over a network;

a client device that is operative to perform actions, including;

receiving the plurality of detectors;

comparing each detector to at least one fragment of sequences of computer system calls associated with the computing activity, and based on the comparison determining a new matching value for each of the detectors;

if the new matching value for one of the detectors is equal to or greater than that detector'"'"'s expectation value, evolving at least one child detector based in part on at least a copy of that detector and at least one mutation, modifying that detector'"'"'s expectation value, and modifying at least one child detector'"'"'s expectation value and it'"'"'s matching value based on a comparison to the at least one fragment of sequences; and

if the expectation value for a detector in the plurality of detectors or the at least one child detector exceeds a threshold value, sending that detector or child detector to the server, wherein that detector or child detector is evaluated to determine if an unauthorized activity is detected on the client device.

15. The system of claim 14, wherein the client device is operative to perform actions, further comprising:

if a matching value for one of the detectors or the at least one child detector is below an expectation value, determining whether to delete that detector or child detector.

16. The system of claim 14, wherein evaluating that detector or child detector, further comprises, evaluating that detector or child detector against a self database to determine if the detector indicates a self or non-self status.

17. The system of claim 14, wherein evolving the at least one child detector further comprises performing at least one of a combination or mutation of that detector.

18. The system of claim 14, wherein the client device is operative to perform actions, further comprising:

if the new matching value for the detector in the plurality of detectors or the at least one child detector is below the expectation value, deleting that detector or child detector.

19. The system of claim 14, wherein generating a plurality of detectors further comprises generating at least one detector in the plurality based on at least one of a random sequence of computer system calls, or generating at least one detector in the plurality based on a known pattern of computer system calls.

20. An apparatus for detecting an unauthorized process activity, comprising:

a memory that stores data and instructions;

a processor that executes instructions that perform actions, including;

generating a detector having an initial matching value and initial expectation value, and wherein the detector is a sequence of computer system calls;

determining a new matching value and an expectation value for the detector based on a characteristic of a client process;

generating another detector based on at least a copy of the detector and at least one mutation and the detector'"'"'s new matching value and the expectation value, wherein another matching value and another expectation value is associated with the other detector; and

performing a hill-climb of the detector'"'"'s and the other detector'"'"'s matching values, until one of the matching values satisfy a threshold value, then means for determining from the detector or the other detector if an unauthorized activity is detected by the client process.