System security approaches using sub-expression automata

• US 20050278781A1
• Filed: 06/14/2004
• Published: 12/15/2005
• Est. Priority Date: 06/14/2004
• Status: Active Grant

• Current Assignee: Lionic Corp.
• Original Assignee: Lionic Corp.
• Inventors: Zhao, Shi-Ming, Chien, Shih-Wei
• Granted Patent: US 7,685,637 B2
• Time in Patent Office: Days
• 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, comprising:

splitting a regular expression that corresponds to a plurality of patterns into a plurality of sub-expressions;

maintaining dependency relationships among a plurality of finite automata that correspond to said sub-expressions with initial state information and final state information of each of said finite automata;

putting a plurality of data units through said finite automata in a sequence that is based on said dependency relationships, said initial state information, and said final state information;

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; and

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

2. The method as recited in claim 1, further comprising 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.

3. The method as recited in claim 1, further comprising blocking said set of said suspected data units from reaching their destinations.

4. The method as recited in claim 1, further comprising making 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:

arranging said plurality of said data units in a sequence according to said sequencing information contained in said packets prior to putting said data units through said finite automaton.

7. The method as recited in claim 1, further comprising obtaining said patterns from an external entity.

8. The method as recited in claim 1, further comprising:

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.

9. A computer-readable medium containing one or more sequences of instructions for ensuring 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 plurality of sub-expressions;

maintain dependency relationships among a plurality of finite automata that correspond to said sub-expressions with initial state information and final state information of each of said finite automata;

put a plurality of data units through said finite automata in a sequence that is based on said dependency relationships, said initial state information, and said final state information;

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; and

perform an action based on the result of said identifying of said set of said 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 putting said data units through said finite automaton.

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, comprising:

splitting a regular expression that corresponds to a plurality of patterns into a plurality of sub-expressions;

maintaining dependency relationships among a plurality of finite automata that correspond to said sub-expressions;

putting a plurality of data units through said finite automata in a sequence that is based on said dependency relationships;

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 by merging results from said finite automata; and

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

18. The method as recited in claim 17, further comprising 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.

19. The method as recited in claim 17, further comprising:

identifying an overlapping portion between two identified sub-expressions out of said sub-expressions;

inserting additional states and state transitions that correspond to said overlapping portions between said finite automata of said identified sub-expressions; and

including said additional states and said state transitions in said sequence.

20. The method as recited in claim 19, further comprising blocking said set of said suspected data units from reaching their destinations.

21. The method as recited in claim 19, further comprising making said result known.

22. The method as recited in claim 17, further comprising:

arranging said plurality of said data units in a sequence according to sequencing information contained in said data units prior to putting said data units through said finite automaton.

23. The method as recited in claim 17, further comprising:

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.

24. A system, comprising:

means for splitting a regular expression that corresponds to a plurality of patterns into a plurality of sub-expressions;

means for maintaining dependency relationships among a plurality of finite automata that correspond to said sub-expressions;

means for putting a plurality of data units through said finite automata in a sequence that is based on said dependency relationships;

means for 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 by merging results from said finite automata; and

means for performing an action based on the result of said identifying of said set of said suspected data units.

25. The system as recited in claim 24, further comprising 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.

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

means for identifying an overlapping portion between two identified sub-expressions out of said sub-expressions;

means for inserting additional states and state transitions that correspond to said overlapping portions between said finite automata of said identified sub-expressions; and

means for including said additional states and said state transitions in said sequence.

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

means for arranging said plurality of said data units in a sequence according to sequencing information contained in said data units prior to putting said data units through said finite automaton.

28. The system as recited in claim 24, further comprising:

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.

29. A system, comprising:

means for splitting a regular expression that corresponds to a plurality of patterns into a plurality of sub-expressions;

means for maintaining dependency relationships among a plurality of finite automata that correspond to said sub-expressions with initial state information and final state information of each of said finite automata;

means for putting a plurality of data units through said finite automata in a sequence that is based on said dependency relationships, said initial state information, and said final state information;

means for 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; and

means for performing an action based on the result of said identifying of said set of said suspected data units.

30. The system as recited in claim 29, further comprising 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.

31. The system as recited in claim 29, further comprising:

means for arranging said plurality of said data units in a sequence according to said sequencing information contained in said packets prior to putting said data units through said finite automaton.

32. The system as recited in claim 29, further comprising:

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.

33. A system, 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 plurality of sub-expressions;

maintain dependency relationships among a plurality of finite automata that correspond to said sub-expressions;

put said plurality of said data units through said finite automata in a sequence that is based on said dependency relationships;

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 by merging results from said finite automata; and

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

34. The system as recited in claim 33, 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.

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

identifies an overlapping portion between two identified sub-expressions out of said sub-expressions;

inserts additional states and state transitions that correspond to said overlapping portions between said finite automata of said identified sub-expressions; and

includes said additional states and said state transitions in said sequence.

36. The system as recited in claim 33, 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 putting said data units through said finite automaton.

37. The system as recited in claim 33, 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.

38. A system, 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 plurality of sub-expressions;

maintain dependency relationships among a plurality of finite automata that correspond to said sub-expressions with initial state information and final state information of each of said finite automata;

put a plurality of data units through said finite automata in a sequence that is based on said dependency relationships, said initial state information, and said final state information;

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; and

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

39. The system as recited in claim 38, 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.

40. The system as recited in claim 38, wherein said processor:

arranges said plurality of said data units in a sequence according to said sequencing information contained in said packets prior to putting said data units through said finite automaton.

41. The system as recited in claim 38, 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.

42. A system, comprising:

a processor,

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

splits a regular expression that corresponds to a plurality of patterns into a plurality of sub-expressions;

maintains dependency relationships among a plurality of finite automata that correspond to said sub-expressions;

puts a plurality of data units that said system receives through said finite automata in a sequence that is based on said dependency relationships;

identifies 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 by merging results from said finite automata; and

performs an action based on the result of said identifying of said set of said suspected data units.

43. The system as recited in claim 42, 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.

44. The system as recited in claim 42, wherein said co-processor unit further:

identifies an overlapping portion between two identified sub-expressions out of said sub-expressions;

inserts additional states and state transitions that correspond to said overlapping portions between said finite automata of said identified sub-expressions; and

includes said additional states and said state transitions in said sequence.

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

arranges said plurality of said data units in a sequence according to sequencing information contained in said data units prior to putting said data units through said finite automaton.

46. The system as recited in claim 42, 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.

47. A system, comprising:

a processor,

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

splits a regular expression that corresponds to a plurality of patterns into a plurality of sub-expressions;

maintains dependency relationships among a plurality of finite automata that correspond to said sub-expressions with initial state information and final state information of each of said finite automata;

puts a plurality of data units that said system receives through said finite automata in a sequence that is based on said dependency relationships, said initial state information, and said final state information;

identifies 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; and

performs an action based on the result of said identifying of said set of said suspected data units.

48. The system as recited in claim 47, 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.

49. The system as recited in claim 47, wherein said co-processor unit:

arranges said plurality of said data units in a sequence according to said sequencing information contained in said packets prior to putting said data units through said finite automaton.

50. The system as recited in claim 47, 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.