Method for transformation of regular expressions

• US 20060085389A1
• Filed: 08/26/2005
• Published: 04/20/2006
• Est. Priority Date: 08/26/2004
• Status: Abandoned Application

• Current Assignee: Intel Corporation
• Original Assignee: Sensory Networks, Inc. (Intel Corporation)
• Inventors: Williams, Darren, Gould, Stephen, Tan, Teewoon, Flanagan, Michael, Barrie, Robert Matthew
• Application Number:
  US11/213,622
• Publication Number:
  US 20060085389A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• 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 apparatus for transforming regular expressions into a less resource intensive representation is disclosed. The method and apparatus converts a collection of regular expressions into a multi-level representation in which the memory requirements of the lowest level representation is reduced when compared with a conventional finite state automaton representation. The method and apparatus converts a collection of regular expressions into a collection of segments and a higher level representation in a way that retains the semantics of the original set of regular expressions. This transformation is performed through the use of an intermediate form. The resulting representation and collection admit an implementation which avoids the potentially costly memory requirements of a traditional implementation of the original expressions.

Claims

1. A method for transforming a first regular expression, the method comprising:

converting the first regular expression into a first form;

segmenting the first form into a first collection and a first representation, the first collection comprising two or more segments from the first form, the first representation comprising data representing relationships between the two or more segments in the first collection, the first representation and first collection together defining a first language used to describe the first regular expression;

deriving a second collection of segments from the first collection;

deriving a second representation from the first representation and second collection of segments such that a second language defined by the second representation and the second collection is an approximation of the first language; and

creating a second form comprising the second representation and second collection, the second form representing the transformed first regular expression.

2. The method of claim 1 wherein the first form is a string representation of the first regular expression.

3. The method of claim 1 wherein the first form is a parse tree representation of the first regular expression.

4. The method of claim 1 wherein the first form is a first automaton, the first automaton is a finite state automaton representation of the first regular expression.

5. The method of claim 1 wherein sub-expressions in the first regular expression are tagged with one or more identifiers, and the first and second representations retain the semantics embodied by the tagging of sub-expressions of the first regular expression.

6. The method of claim 2 wherein the segments in the first collection are substrings of the first regular expression.

7. The method of claim 3 wherein the segments in the first collection are sub-trees of the parse tree representation of the first regular expression.

8. The method of claim 4 wherein the segments in the first collection are portions of the first automaton.

9. The method of claim 1 wherein the set of segments in the second collection is a subset of the set of segments in the first collection.

10. The method of claim 1 wherein the adequacy of the approximation is determined by the requirement that the formal language embodied by the second form is a superset of the formal language embodied in the first regular expression.

11. The method of claim 1 wherein the adequacy of the approximation is determined by the requirement that the formal language embodied by the second form is a subset of the formal language embodied in the first regular expression.

12. The method of claim 1 wherein the adequacy of the approximation is determined by the requirement that the formal language embodied by the second form is the same as the formal language embodied in the first regular expression.

13. The method of claim 2 wherein the method of segmenting the first form comprises:

locating one or more key segments in the first form, the one or more key segments being substrings of the first regular expression;

extracting the one or more key segments, the extracted one or more key segments belonging to the set of segments from the first form; and

extracting substrings of the first regular expression that have not been identified as key segments, the extracted substrings belonging to the set of segments from the first form.

14. The method of claim 13 wherein the substrings corresponding to the one or more key segments are found by the literal matching of substrings of the first regular expression against a table of candidate substrings.

15. The method of claim 13 wherein the substrings corresponding to the one or more key segments are found by the matching of substrings of the first regular expression against a table of regular expressions.

16. The method of claim 4 wherein the method of segmenting the first form comprises:

locating one or more key segments in the first form, the one or more key segments are portions of the first automaton;

extracting the one or more key segments, the extracted one or more key segments belonging to the set of segments from the first form; and

extracting portions of the first automaton that have not been identified as key segments, the extracted portions belonging to the set of segments from the first form.

17. The method of claim 16 wherein the portions of the first automaton corresponding to the one or more key segments are found heuristically based on the optimization of one or more cost functions, the cost functions comprising input variables that include properties of the first automaton.

18. The method of claim 1 further comprising a first process of producing new segmentations and representations iteratively until one or more requirements are met, the first process includes the operations of measuring, performing predictive calculations, and carrying out heuristic estimations.

19. The method of claim 18 wherein the first process operates until the combined size of DFAs representing the various segments crosses one or more thresholds.

20. The method of claim 18 wherein the first process operates until the number of states required to represent any of the various segments crosses one or more thresholds.

21. The method of claim 18 wherein the first process operates until the maximum length of any individual segment crosses one or more thresholds.

22. The method of claim 18 wherein the one or more requirements are determined with respect to the resources available on a hardware device.

23. The method of claim 1 wherein the second representation is a finite state automaton.

24. The method of claim 5 wherein the second form is used for matching patterns in a first stream of input data comprising the steps of:

sending a first stream of input data to one or more pattern matching systems, a second form loaded into the one or more pattern matching systems;

receiving pattern matching events from the one or more pattern matching systems, the pattern matching events include information on the tags in the second representation that matched one or more parts of the first input data stream, the tags in the second representation contain information on the corresponding sub-expression tags of the first regular expression; and

verifying that the first regular expression matches one or more parts of the first input data stream by examining the sub-expression tags of the first regular expression and the corresponding tags in the second representation that have been included in the pattern matching events returned by the one or more pattern matching systems.

25. The method of claim 24 further comprising performing one or more actions based on the results obtained from verifying whether the first regular expression matches one or more parts of the first input data.

26. The method of claim 25 wherein the one or more actions include storing and accumulating the match results.

27. The method of claim 25 wherein the one or more actions include ignoring one or more match results.

28. The method of claim 6 wherein the sub-expressions in the resulting second collection are converted to one or more finite automata.

29. The method of claim 28 wherein the one or more finite automata include a collection of deterministic finite automata.

30. The method of claim 28 wherein the one or more finite automata include a single combined deterministic finite automaton.

31. The method of claim 28 wherein the one or more finite automata include a collection of non-deterministic finite automata.

32. The method of claim 28 wherein the one or more finite automata include a single combined non-deterministic finite automaton.

33. An apparatus configured to transform regular expressions, the apparatus comprising:

a module adapted to convert a first regular expression into a first form;

a module adapted to segment the first form into a first collection and a first representation, the first collection comprising two or more segments from the first form, the first representation comprising data representing relationships between the two or more segments in the first collection, the first representation and first collection together defining a first language used to describe the first regular expression;

a module adapted to derive a second collection of segments from the first collection;

a module adapted to derive a second representation from the first representation and second collection of segments such that a second language defined by the second representation and the second collection is an approximation of the first language; and

a module adapted to create a second form comprising the second representation and second collection, the second form representing the transformed first regular expression.

34. The apparatus of claim 33 wherein the first form is a string representation of the first regular expression.

35. The apparatus of claim 34 wherein the module adapted to segment the first form further comprises:

a module adapted to locate one or more key segments in the first form, the one or more key segments being substrings of the first regular expression;

a module adapted to extract the one or more key segments, the extracted one or more key segments belonging to the set of segments from the first form; and

a module adapted to extract substrings of the first regular expression that have not been identified as key segments, the extracted substrings belonging to the set of segments from the first form.

36. The apparatus of claim 33 wherein the first form is a first automaton, the first automaton is a finite state automaton representation of the first regular expression.

37. The apparatus of claim 36 wherein the module adapted to segment the first form further comprises:

a module adapted to locate one or more key segments in the first form, the one or more key segments are portions of the first automaton;

a module adapted to extract the one or more key segments, the extracted one or more key segments belonging to the set of segments from the first form; and

a module adapted to extract portions of the first automaton that have not been identified as key segments, the extracted portions belonging to the set of segments from the first form.

38. The apparatus of claim 33 wherein sub-expressions in the first regular expression are tagged with one or more identifiers, and the first and second representations retain the semantics embodied by the tagging of sub-expressions of the first regular expression.

39. The apparatus of claim 38 wherein the second form is used for matching patterns in a first stream of input data, the apparatus further comprising:

a module adapted to send a first stream of input data to one or more pattern matching systems, a second form loaded into the one or more pattern matching systems;

a module adapted to receive pattern matching events from the one or more pattern matching systems, the pattern matching events include information on the tags in the second representation that matched one or more parts of the first input data stream, the tags in the second representation contain information on the corresponding sub-expression tags of the first regular expression; and

a module adapted to verify that the first regular expression matches one or more parts of the first input data stream by examining the sub-expression tags of the first regular expression and the corresponding tags in the second representation that have been included in the pattern matching events returned by the one or more pattern matching systems.