System security approaches using sub-expression automata

• US 7,685,637 B2
• Filed: 06/14/2004
• Issued: 03/23/2010
• Est. Priority Date: 06/14/2004
• Status: Active Grant

• Current Assignee: Lionic Corp.
• Original Assignee: Lionic Corp.
• Inventors: Chien, Shih-Wei, Zhao, Shi-Ming
• Primary Examiner(s): Moazzami; Nasser G
• Assistant Examiner(s): Louie; Oscar A
• Application Number:
  US10/868,665
• Publication Number:
  US 20050278781A1
• Time in Patent Office: 2,108 Days
• Field of Search: 726 2- 4, 726/16, 726/17, 726/21, 726/22, 726/26, 726/27, 380/59
• US Class Current: 726/22
• CPC Class Codes: G06F 21/563 by source code analysis
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

A method and system for ensuring system security is disclosed. The method and system split a regular expression that corresponds to a number of patterns into sub-expressions. The dependency relationships among the finite automata that correspond to the sub-expressions are maintained. Then, as data units are put through these finite automata in a sequence that is based on the dependency relationships, suspected data units are identified. The suspected data units are the ones containing content that collectively matches one or more of the aforementioned patterns. Identification of the suspected data units is based on the merged results of the finite automata. Depending on the result of identifying the suspected data units, different actions are performed.

Claims

1. A method of inspecting a plurality of data units received by a computing device, comprising:

configuring a processing unit of said computing device to

convert a plurality of patterns into a regular expression;

split said regular expression into a first sub-expression and a second sub-expression;

formulate a first deterministic finite automaton (DFA) from said first sub-expression with a first initial state and a first final state;

formulate a second DFA from said second sub-expression with a second initial state and a second final state;

construct a dependency relationship between said first DFA and said second DFA;

identify a first suspected data unit and a second suspected data unit out of said plurality of said data units, wherein a first content of said first suspected data unit and a second content of said second suspected data unit collectively match any of said plurality of said patterns represented by said first DFA and said second DFA that are arranged in a sequence based on said dependency relationship; and

perform an action based on a result of said identifying a first suspected data unit and a second suspected data unit.

2. The method as recited in claim 1, further comprising configuring said processing unit to temporarily retain said first suspected data unit after said first content of said first suspected data unit matches a code segment of a first pattern out of said plurality of said patterns until said first content of said first suspected data unit and said second content of said second suspected data unit collectively match said first pattern.

3. The method as recited in claim 1, further comprising configuring said processing unit to block said first suspected data unit, said second suspected data unit, or said first suspected data unit and said second suspected data unit from reaching their destinations.

4. The method as recited in claim 1, further comprising configuring said processing unit to make said result known.

5. The method as recited in claim 1, wherein said data units are packets with sequencing information.

6. The method as recited in claim 5, further comprising configuring said processing unit to arrange said plurality of said data units in a sequence according to said sequencing information prior to identifying said first suspected data unit and said second suspected data unit out of said plurality of said data units.

7. The method as recited in claim 1, further comprising configuring said processing unit to obtain said patterns from an external entity.

8. The method as recited in claim 1, further comprising configuring said processing unit to retain a comparison result after said first content of said first suspected data unit matches a code segment of a first pattern out of said plurality of said patterns.

9. A computer-readable medium containing one or more sequences of instructions configured to ensure system security, which instructions, when executed by one or more processors, cause the one or more processors to:

split a regular expression that corresponds to a plurality of patterns into a first sub-expression and a second plurality of sub-expression;

formulate a first deterministic finite automaton (DFA) from said first sub-expression with a first initial state and a first final state;

formulate a second DFA from said second sub-expression with a second initial state and a second final state;

construct a dependency relationship between said first DFA and said second DFA;

insert a state in between said first DFA and said second DFA upon identifying an overlapped portion between said first DFA and said second DFA;

formulate a third DFA by merging said first DFA, said second DFA, and optionally said state;

identify a set of suspected data units out of said plurality of said data units, wherein the content of said set of said suspected data units collectively matches any of said plurality of said patterns represented by said third DFA; and

perform an action based on a result of said identifying of a set of suspected data units.

10. The computer-readable medium as recited in claim 9, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to retain said suspected data units in temporary storage while comparing the content of each of said suspected data units to any part of said patterns.

11. The computer-readable medium as recited in claim 9, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to block said set of said suspected data units from reaching their destinations.

12. The computer-readable medium as recited in claim 9, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to make said result known.

13. The computer-readable medium as recited in claim 9, wherein said data units are packets with sequencing information.

14. The computer-readable medium as recited in claim 13, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to arrange said plurality of said packets in a sequence according to said sequencing information contained in said data units prior to identifying said set of suspected data units out of said plurality of said data units.

15. The computer-readable medium as recited in claim 9, wherein said patterns are obtained from an external entity.

16. The computer-readable medium as recited in claim 9, further comprising instructions which, when executed by the one or more processors, cause the one or more processors to retain a comparison result after the content of a first data unit matches a code segment of a first pattern out of said plurality of said patterns.

17. A method of ensuring system security of a computing device, comprising:

configuring a processing unit of said computing device to

split a regular expression that corresponds to a plurality of patterns into a first sub-expression and a second sub-expression;

formulate a first deterministic finite automaton (DFA) from said first sub-expression with a first initial state and a first final state;

formulate a second DFA from said second sub-expression with a second initial state-and a second final state;

construct a dependency relationship between said first DFA and said second DFA;

insert a state in between said first DFA and said second DFA upon identifying an overlapped portion between said first DFA and said second DFA;

formulate a third DFA by merging said first DFA, said second DFA, and optionally said state;

identify a set of suspected data units out of said plurality of said data units, wherein the content of said set of said suspected data units collectively matches any of said plurality of said patterns represented by said third DFA; and

perform an action based on a result of said identifying of a set of suspected data units.

18. The method as recited in claim 17, further comprising configuring said processing unit to temporarily retain a first data unit out of said suspected data units after the content of said first data unit matches a code segment of a first pattern out of said plurality of said patterns until the content of said set of said suspected data units collectively matches said first pattern.

19. The method as recited in claim 17, further comprising configuring said processing unit to block said set of said suspected data units from reaching their destinations.

20. The method as recited in claim 17, further comprising making said result known.

21. The method as recited in claim 17, further comprising configuring said processing unit to arrange said plurality of said data units in a sequence according to sequencing information contained in said data units prior to identifying said set of suspected data units out of said plurality of said data units.

22. The method as recited in claim 17, further comprising configuring said processing unit to retain a comparison result after the content of a first data unit matches a code segment of a first pattern out of said plurality of said patterns.

23. A system configured to ensure system security, comprising:

a processing means for

splitting a regular expression that corresponds to a plurality of patterns into a first sub-expression and a second sub-expression;

formulating a first deterministic finite automaton (DFA) from said first sub-expression with a first initial state and a first final state;

formulating a second DFA from said second sub-expression with a second initial state and a second final state;

constructing a dependency relationship between said first DFA and said second DFA;

inserting a state in between said first DFA and said second DFA upon identifying an overlapped portion between said first DFA and said second DFA;

formulating a third DFA by merging said first DFA, said second DFA, and optionally said state;

identifying a set of suspected data units out of said plurality of said data units, wherein the content of said set of said suspected data units collectively matches any of said plurality of said patterns represented by said third DFA; and

performing an action based on a result of said identifying of a set of suspected data units.

24. The system as recited in claim 23, further comprising a storage means for temporarily retaining a first data unit out of said suspected data units after the content of said first data unit matches a code segment of a first pattern out of said plurality of said patterns until the content of said set of said suspected data units collectively matches said first pattern.

25. The system as recited in claim 23, wherein said processing means is further configured for:

arranging said plurality of said data units in a sequence according to sequencing information contained in said data units prior to identifying said set of suspected data units out of said plurality of said data units.

26. The system as recited in claim 23, further comprising:

a storage means for retaining a comparison result after the content of a first data unit matches a code segment of a first pattern out of said plurality of said patterns.

27. A system configured to detect and prevent intrusion, comprising:

a processing means for

splitting a regular expression that corresponds to a plurality of patterns into a first sub-expression and a second sub-expression;

formulating a first deterministic finite automaton (DFA) from said first sub-expression with a first initial state and a first final state;

formulating a second DFA from said second sub-expression with a second initial state and a second final state;

constructing a dependency relationship between said first DFA and said second DFA;

identifying a first suspected data unit and a second suspected data unit out of said plurality of said data units, wherein a first content of said first suspected data unit and a second content of said second suspected data unit collectively match any of said plurality of said patterns represented by said first DFA and said second DFA that are arranged in a sequence based on said dependency relationship; and

performing an action based on a result of said identifying a first suspected data unit and a second suspected data unit.

28. The system as recited in claim 27, further comprising a storage means for temporarily retaining said first suspected data unit after said first content of said first suspected data unit matches a code segment of a first pattern out of said plurality of said patterns until said first content of said first suspected data unit and said second content of said second suspected data unit collectively match said first pattern.

29. The system as recited in claim 27, wherein said processing means is further configured for:

arranging said plurality of said data units in a sequence according to sequencing information contained in said plurality of said data units prior to identifying said first suspected data unit and said second suspected data unit out of said plurality of said data units.

30. The system as recited in claim 27, further comprising:

a storage means for retaining a comparison result after said first content of said first suspected data unit matches a code segment of a first pattern out of said plurality of said patterns.

31. A system configured to ensure system security, comprising:

a processor,

a bus, coupled to said processor,

a communication interface, coupled to said bus, wherein said communication interface receives a plurality of data units,

a main memory, coupled to the bus, wherein said memory includes instructions when executed by said processor, causes said processor to;

split a regular expression that corresponds to a plurality of patterns into a first sub-expression and a second sub-expression;

formulate a first deterministic finite automaton (DFA) from said first sub-expression with a first initial state and a first final state;

formulate a second DFA from said second sub-expression with a second initial state and a second final state;

construct a dependency relationship between said first DFA and said second DFA;

insert a state in between said first DFA and said second DFA upon identifying an overlapped portion between said first DFA and said second DFA;

formulate a third DFA by merging said first DFA, said second DFA, and optionally said state;

identify a set of suspected data units out of said plurality of said data units, wherein the content of said set of said suspected data units collectively matches any of said plurality of said patterns represented by said third DFA; and

perform an action based on a result of said identifying of a set of suspected data units.

32. The system as recited in claim 31, wherein a temporary storage temporarily retains a first data unit out of said suspected data units after the content of said first data unit matches a code segment of a first pattern out of said plurality of said patterns until the content of said set of said suspected data units collectively matches said first pattern.

33. The system as recited in claim 31, wherein said processor further:

arranges said plurality of said data units in a sequence according to sequencing information contained in said data units prior to identifying said set of suspected data units out of said plurality of said data units.

34. The system as recited in claim 31, wherein a temporary storage retains a comparison result after the content of a first data unit matches a code segment of a first pattern out of said plurality of said patterns.

35. A system configured to detect and prevent intrusion, comprising:

a processor,

a bus, coupled to said processor,

a communication interface, coupled to said bus, wherein said communication interface receives a plurality of data units,

a main memory, coupled to the bus, wherein said memory includes instructions that when executed by said processor, cause said processor to;

split a regular expression that corresponds to a plurality of patterns into a first sub-expression and a second sub-expression;

formulate a first deterministic finite automaton (DFA) from said first sub-expression with a first initial state and a first final state;

formulate a second DFA from said second sub-expression with a second initial state and a second final state;

construct a dependency relationship between said first DFA and said second DFA;

identify a first suspected data unit and a second suspected data unit out of said plurality of said data units, wherein a first content of said first suspected data unit and a second content of said second suspected data unit collectively match any of said plurality of said patterns represented by said first DFA and said second DFA that are arranged in a sequence based on said dependency relationship; and

perform an action based on a result of said identifying a first suspected data unit and a second suspected data unit.

36. The system as recited in claim 35, wherein a temporary storage retains said first suspected data unit after said first content of said first suspected data unit matches a code segment of a first pattern out of said plurality of said patterns until said first content of said first suspected data unit and said second content of said second suspected data unit collectively match said first pattern.

37. The system as recited in claim 35, wherein said processor:

arranges said plurality of said data units in a sequence according to sequencing information contained in said plurality of said data units prior to identifying said first suspected data unit and said second suspected data unit out of said plurality of said data units.

38. The system as recited in claim 35, wherein a temporary storage retains a comparison result after said first content of said first suspected data unit matches a code segment of a first pattern out of said plurality of said patterns.

39. A system, comprising:

a processor, and

a co-processor unit, electrically coupled to said processor, wherein said co-processor unit is configured to;

split a regular expression that corresponds to a plurality of patterns into a first sub-expression and a second sub-expression;

formulate a first deterministic finite automaton (DFA) from said first sub-expression with a first initial state and a first final state;

formulate a second DFA from said second sub-expression with a second initial state and a second final state;

construct a dependency relationship between said first DFA and said second DFA;

insert a state in between said first DFA and said second DFA upon identifying an overlapped portion between said first DFA and said second DFA;

formulate a third DFA by merging said first DFA, said second DFA, and optionally said state;

identify a set of suspected data units out of said plurality of said data units, wherein the content of said set of said suspected data units collectively matches any of said plurality of said patterns represented by said DFA; and

perform an action based on a result of said identifying of a set of suspected data units.

40. The system as recited in claim 39, wherein a temporary storage retains a first data unit out of said suspected data units after the content of said first data unit matches a code segment of a first pattern out of said plurality of said patterns until the content of said set of said suspected data units collectively matches said first pattern.

41. The system as recited in claim 39, wherein said co-processor unit farther:

arranges said plurality of said data units in a sequence according to sequencing information contained in said data units prior to identifying said set of suspected data units out of said plurality of said data units.

42. The system as recited in claim 39, wherein a temporary storage retains a comparison result after the content of a first data unit matches a code segment of a first pattern out of said plurality of said patterns.

43. A system, comprising:

a processor, and

a co-processor unit, electrically coupled to said processor, wherein said co-processor unit is configured to;

split a regular expression that corresponds to a plurality of patterns into a first sub-expression and a second sub-expression;

formulate a first deterministic finite automaton (DFA) from said first sub-expression with a first initial state and a first final state;

formulate a second DFA from said second sub-expression with a second initial state and a second final state;

construct a dependency relationship between said first DFA and said second DFA;

identify a first suspected data unit and a second suspected data unit out of said plurality of said data units, wherein a first content of said first suspected data unit and a second content of said second suspected data unit collectively match any of said plurality of said patterns represented by said first DFA and said second DFA that are arranged in a sequence based on said dependency relationship; and

perform an action based on a result of said identifying a first suspected data unit and a second suspected data unit.

44. The system as recited in claim 43, wherein a temporary storage retains said first suspected data unit after said first content of said first suspected data unit matches a code segment of a first pattern out of said plurality of said patterns until said first content of said first suspected data unit and said second content of said second suspected data unit collectively match said first pattern.

45. The system as recited in claim 43, wherein said co-processor unit:

arranges said plurality of said data units in a sequence according to sequencing information contained in said plurality of said data units prior to identifying said first suspected data unit and said second suspected data unit out of said plurality of said data units.

46. The system as recited in claim 43, wherein a temporary storage retains a comparison result after said first content of said first suspected data unit matches a code segment of a first pattern out of said plurality of said patterns.