Computer network intrusion detection

• US 6,370,648 B1
• Filed: 12/08/1998
• Issued: 04/09/2002
• Est. Priority Date: 12/08/1998
• Status: Expired due to Term

• Current Assignee: Visa International Service Association (Visa, Inc.)
• Original Assignee: Visa International Service Association (Visa, Inc.)
• Inventors: Diep, Thanh A.
• Primary Examiner(s): Wright, Norman M.
• Application Number:
  US09/208,617
• Time in Patent Office: 1,218 Days
• Field of Search: 713/201, 713/200, 706/13, 706/14
• US Class Current: 726/22
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

Detecting harmful or illegal intrusions into a computer network or into restricted portions of a computer network uses statistical analysis to match user commands and program names with a template sequence. Discrete correlation matching and permutation matching are used to match sequences. The result of the match is input to a feature builder and then a modeler to produce a score. The score indicates possible intrusion. A sequence of user commands and program names and a template sequence of known harmful commands and program names from a set of such templates are retrieved. A closeness factor indicative of the similarity between the user command sequence and a template sequence is derived from comparing the two sequences. The user command sequence is compared to each template sequence in the set of templates thereby creating multiple closeness or similarity measurements. These measurements are examined to determine which sequence template is most similar to the user command sequence. A frequency feature associated with the user command sequence and the most similar template sequence is calculated. It is determined whether the user command sequence is a potential intrusion into restricted portions of the computer network by examining output from a modeler using the frequency feature as one input.

Claims

1. A method of detecting an intrusion in a computer network, the method comprising:

(a) retrieving a user input sequence;

(b) retrieving a sequence template from a plurality of sequence templates;

(c) comparing the user input sequence and the sequence template to derive a closeness factor indicating a degree of similarity between the user input sequence and the sequence template;

(d) calculating a frequency feature associated with the user input sequence and a most similar sequence template; and

(e) determining whether the user input sequence is a potential intrusion by examining output from a modeler using the frequency feature as one input to the modeler.

2. A method as recited in claim 1 further comprising:

retrieving the most similar sequence template;

determining a first frequency of how often the user input sequence occurs in a first command stream created by a particular network user from a plurality of network users;

determining a second frequency of how often the most similar sequence template occurs in a second command stream created by the plurality of network users; and

calculating the frequency feature using the first frequency and the second frequency.

3. A method as recited in claim 2 further comprising calculating the second frequency using a smoothing coefficient and a previous second frequency.

4. A method as recited in claim 1 wherein retrieving a user input sequence further comprises:

logging, in a chronological manner, commands and program names entered in the computer network thereby creating a command log;

arranging the command log according to individual users on the computer network; and

identifying the user input sequence from the command log using a predetermined time period.

5. A method as recited in claim 1 wherein retrieving a sequence template from a plurality of sequence templates further comprises:

logging chronologically commands and program names entered in the computer network thereby creating a command log;

identifying a command sequence from the command log determined to be suspicious; and

creating the sequence template from the command sequence.

6. A method as recited in claim 1 further comprising:

repeating steps (b) through (c) for each sequence template in the plurality of sequence templates thereby deriving a plurality of closeness factors; and

determining the most similar sequence template by examining each closeness factor from the plurality of closeness factors.

7. A method as recited in claim 1 wherein comparing the user input sequence and the sequence template to derive a closeness factor further comprises utilizing permutation matching to compare the user input sequence and one sequence template from the plurality of sequence templates.

8. A method as recited in claim 1 wherein comparing the user input sequence and the sequence template to derive a closeness factor further comprises utilizing discrete correlation matching to compare the user input sequence template and one sequence template from the plurality of sequence templates.

9. A method of determining similarity between a user sequence and a sequence template in a computer network intrusion detection system using correlation matching, the method comprising:

(a) retrieving the user sequence including a plurality of user commands;

(b) retrieving a template sequence including a plurality of template commands;

(c) transforming one of the user sequence and the template sequence such that the user sequence and the template sequence are of substantially the same length;

(d) performing a series of comparisons between the user sequence and the template sequence producing matches;

(e) deriving a similarity factor from the number of matches between the plurality of user commands and the plurality of template commands; and

(f) associating the similarity factor with said template sequence as an indication of likelihood of intrusion, whereby the complexity of the computer network intrusion system is low.

10. A method as recited in claim 9 wherein transforming one of the user sequence and the template sequence further comprises:

determining which of the user sequence and the template sequence is a shorter sequence; and

inserting one or more reserved characters at the end of the shorter sequence.

11. A method as recited in claim 9 wherein deriving a similarity factor from the number of matches further comprises shifting one of the plurality of user command elements and the plurality of template command elements by one or more elements before performing each comparison of the series of comparisons between the user sequence and the template sequence.

12. A method of determining similarity between a user sequence and a template sequence in a computer network intrusion system using permutation matching, the method comprising:

retrieving the user sequence including a plurality of user commands;

retrieving a template sequence including a plurality of stored commands;

creating a user subset and a template subset, the user subset including user commands found in the template sequence and the template subset including stored commands found in the user sequence; and

determining a number of alterations needed to reorder one of the user subset and the template subset to have the same order as one of the user subset and the template subset that was not reordered wherein the number of alterations is indicative of similarity between the user sequence and the template sequence, the similarity indicating a likelihood of intrusion, whereby the complexity of the computer network intrusion is low.

13. A method as recited in claim 12 further comprising inverting adjacent user commands of the user subset until the order of the user commands is the same as the order of the stored commands of template subset.

14. A method as recited in claim 12 further comprising inverting adjacent stored commands of the template subset until the order of the stored commands is the same as the order of the user commands of the user subset.

15. A method as recited in claim 12 further comprising normalizing the number of alterations by dividing the number of alterations by a worst-case number of alterations wherein the worst-case number of alterations is the number of alterations needed to reorder one of the user subset and the template subset to have the same order as one of the user subset and the template subset that was not reordered when the user commands in the user subset and the stored commands in the template subset are in opposite order.

16. A system for detecting an intrusion in a computer network, the system comprising:

an input sequence extractor for retrieving a user input sequence;

a sequence template extractor for retrieving a sequence template from a plurality of sequence templates;

a match component for comparing the user input sequence and the sequence template to derive a closeness factor indicating a degree of similarity between the user input sequence and the sequence template;

a features builder for calculating a frequency feature associated with the user input sequence and a most similar sequence template; and

a modeler using the frequency feature as one input to the modeler whereby it can be determined whether the user input sequence is a potential intrusion by examining output from the modeler.

17. A system as recited in claim 16 wherein the user input extractor further comprises:

a command log containing, in a chronological manner, commands and program names entered in the computer network and arranged according to individual users on the computer network; and

a sequence identifier for identifying the user input sequence from the command log using a predetermined time period.

18. A system as recited in claim 16 wherein the sequence template extractor further comprises:

a command log containing, in a chronological manner, commands and program names entered in the computer network;

a command sequence identifier for identifying a command sequence from the command log determined to be suspicious; and

a sequence template extractor for creating the sequence template from the command sequence.

19. A system as recited in claim 16 wherein the match component for comparing the user input sequence and the sequence template further comprises a permutation matching component for comparing the user input sequence and one sequence template from the plurality of sequence templates.

20. A system as recited in claim 16 wherein the match component for comparing the user input sequence and the sequence template further comprises a correlation matching component to compare the user input sequence template and one sequence template from the plurality of sequence templates.

21. A computer-readable medium containing programmed instructions arranged to detect an intrusion in a computer network, the computer-readable medium including programmed instructions for:

(a) retrieving a user input sequence;

(b) retrieving a sequence template from a plurality of sequence templates;

(c) comparing the user input sequence and the sequence template to derive a closeness factor indicating a degree of similarity between the user input sequence and the sequence template;

(d) calculating a frequency feature associated with the user input sequence and a most similar sequence template; and

(e) determining whether the user input sequence is a potential intrusion by examining output from a modeler using the frequency feature as one input to the modeler.

22. A computer-readable medium as recited in claim 21 further comprising programmed instructions for:

retrieving the most similar sequence template;

determining a first frequency of how often the user input sequence occurs in a first command stream created by a particular network user from a plurality of network users;

determining a second frequency of how often the most similar sequence template occurs in a second command stream created by the plurality of network users; and

calculating the frequency feature using the first frequency and the second frequency.

23. A computer-readable medium as recited in claim 22 further comprising programmed instructions for calculating the second frequency using a smoothing coefficient and a previous second frequency.

24. A computer-readable medium as recited in claim 21 wherein the programmed instructions for retrieving a user input sequence further comprises programmed instructions for:

logging, in a chronological manner, commands and program names entered in the computer network to create a command log;

arranging the command log according to individual users on the computer network; and

identifying the user input sequence from the command log using a predetermined time period.

25. A computer-readable medium as recited in claim 21 wherein the programmed instructions for retrieving a sequence template from a plurality of sequence templates further comprises programmed instructions for:

logging chronologically commands and program names entered in the computer network thereby creating a command log;

identifying a command sequence from the command log determined to be suspicious; and

creating the sequence template from the command sequence.

26. A computer-readable medium as recited in claim 21 further comprising programmed instructions for:

repeating steps (b) through (c) for each sequence template in the plurality of sequence templates to derive a plurality of closeness factors; and

determining the most similar sequence template by examining each closeness factor from the plurality of closeness factors.

27. A computer-readable medium as recited in claim 21 wherein the programmed instructions for comparing the user input sequence and the sequence template to derive a closeness factor further comprises programmed instructions for utilizing permutation matching to compare the user input sequence and one sequence template from the plurality of sequence templates.

28. A computer-readable medium as recited in claim 21 wherein programmed instructions for comparing the user input sequence and the sequence template to derive a closeness factor further comprises programmed instructions for utilizing discrete correlation matching to compare the user input sequence template and one sequence template from the plurality of sequence templates.

29. A computer-readable medium containing programmed instructions arranged to determine similarity between a user sequence and a sequence template in a computer network intrusion detection system using correlation matching, the computer-readable medium including programmed instructions for:

(a) retrieving the user sequence including a plurality of user commands;

(b) retrieving a template sequence including a plurality of template commands;

(c) transforming one of the user sequence and the template sequence such that the user sequence and the template sequence are of substantially the same length;

(d) performing a series of comparisons between the user sequence and the template sequence producing matches;

(e) deriving a similarity factor from the number of matches between the plurality of user commands and the plurality of template commands; and

(f) associating the similarity factor with said template sequence as an indication of likelihood of intrusion, whereby the complexity of the computer network intrusion system is low.

30. A computer-readable medium containing programmed instructions arranged to determine similarity between a user sequence and a template sequence in a computer network intrusion system using permutation matching, the computer-readable medium including programmed instructions for:

retrieving the user sequence including a plurality of user commands;

retrieving a template sequence including a plurality of stored commands;

creating a user subset and a template subset, the user subset including user commands found in the template sequence and the template subset including stored commands found in the user sequence; and

determining a number of alterations needed to reorder one of the user subset and the template subset to have the same order as one of the user subset and the template subset that was not reordered wherein the number of alterations is indicative of similarity between the user sequence and the template sequence, the similarity indicating a likelihood of intrusion, whereby the complexity of the computer network intrusion is low.