Code generating system for improved pattern matching in a protocol analyzer

• US 6,122,757 A
• Filed: 06/27/1997
• Issued: 09/19/2000
• Est. Priority Date: 06/27/1997
• Status: Expired due to Term

• Current Assignee: Keysight Technologies Singapore (Holdings) Pte. Limited. (Keysight Technologies, Inc.)
• Original Assignee: Agilent Technologies, Inc.
• Inventors: Kelley, Jeffrey V.
• Primary Examiner(s): LE, DIEU MINH T
• Application Number:
  US08/884,143
• Time in Patent Office: 1,180 Days
• Field of Search: 395/183.15, 395/183.17, 395/183.21, 707/6, 706/48, 364/470.06, 714/39, 714/41, 714/45, 714/715, 714/735, 714/738, 714/739
• US Class Current: 714/39
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/18 Protocol analysers
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A machine code generating system for improved pattern matching in a protocol analyzer. The code generating system includes a pattern relationship analysis phase and a pattern matching code generation phase. The pattern relationship analysis phase includes evaluating pairs of test patterns to determine the relationship that exists between each pair such as superset, subset, independent, external, and identical. The pattern matching code generation phase includes generating general pattern matching code in addition to generating specialized comparison code that is specific to the types of relationships that exist among a given set of patterns. The machine code that is generated, organizes the patterns into groups to minimize the number of pattern matching comparisons required to a minimum defined in the average case as the sum of the number of patterns and the maximum number of words per pattern. The machine code generated by the code generating system is ready to execute at the completion of the code generating system operation.

Claims

1. A code generating system for improved pattern matching in a protocol analyzer, said system comprising:

an interface in said protocol analyzer to monitor a plurality of protocol data units on a communication link;

a pattern set in said protocol analyzer;

a pattern relationship analyzer to identify a pattern relationship for each pair of patterns in said pattern set; and

a program code generator to generate executable code unique to said pattern relationship for each of said pair of patterns in said pattern set such that said executable code requires a minimum number of comparisons to determine a match between said pattern set and at least one segment of one of said plurality of protocol data units.

2. A system according to claim 1 wherein said pattern set is a fixed number of at least one pattern originating from at least one source selected from a group comprised of:

at least one pattern from a memory device, at least one pattern input by a user in real time, and at least one plurality of patterns that are commonly selected for pattern matching.

3. A system according to claim 2 including:

a non-volatile memory to save and retrieve user selected ones of said at least one pattern originating from said at least one source.

4. A system according to claim 1 wherein said pattern relationship analyzer includes:

a non-volatile memory to save said pattern relationship for each said pair of patterns in said pattern set.

5. A system according to claim 4 including:

said pattern relationship is of at least one type selected from a group comprised of;

superset, subset, independent, exclusive, and identical; and

said pattern relationship is determined on a word-by-word basis for each said pair of patterns in said pattern set.

6. A system according to claim 1 wherein said minimum number of comparisons includes:

an arithmetic sum of a maximum number of words in any one pattern of said pattern set and a maximum number of patterns in said pattern set.

7. A system according to claim 1 wherein said program code generator is invoked in real-time in response to said pattern relationship analyzer.

8. A system according to claim 1 wherein said program code generator is invoked in real-time in response to a user input command.

9. A code generating system for improved pattern matching in a protocol analyzer, the system comprising:

an interface in the protocol analyzer to monitor a plurality of protocol data units on a communication link;

a pattern set in the protocol analyzer;

a pattern relationship analyzer to identify a pattern relationship for each pair of patterns in the pattern set; and

a program code generator to generate executable code that includes an unrolled recursive call tree having a minimum of external function calls to enhance run-time performance of the executable code, the executable code being unique to the pattern relationship for each pair of patterns in the pattern set such that the executable code requires a minimum number of comparisons to determine a match between the pattern set and at least one segment of one of the plurality of protocol data units, the minimum number of comparisons including an arithmetic sum of a maximum number of words in any one pattern of said pattern set and a maximum number of patterns in said pattern set.

10. A code generating system for improved pattern matching in a protocol analyzer, the system comprising:

an interface in the protocol analyzer to monitor a plurality of protocol data units on a communication link;

a pattern set in the protocol analyzer;

a pattern relationship analyzer to identify a pattern relationship for each pair of patterns in the pattern set; and

a program code generator to generate executable code unique to the pattern relationship for each pair of patterns in the pattern set such that the executable code requires a minimum number of comparisons to determine a match between the pattern set and at least one segment of one of the plurality of protocol data units, the program code generator including;

a pattern matching code generator to identify a pattern P having no subset patterns and generate at least one decision logic block to rule-in and rule-out subsequent pattern comparisons in view of the pattern P; and

a specialization comparison code generator to generate at least one decision logic block for special case ones of the pattern relationship.

11. A method of generating computer executable code for improved pattern matching in a protocol analyzer, said method comprising:

monitoring a plurality of protocol data units on a communication link by way of a protocol analyzer;

generating at least one pattern set for use in said protocol analyzer;

identifying a pattern relationship for each pair of patterns in a selected one of said at least one pattern set; and

generating executable code unique to said pattern relationship for each of said pair of patterns such that said executable code requires a minimum number of comparisons to determine a match between said selected one of said at least one pattern set and at least one segment of one of said plurality of protocol data units.

12. A method according to claim 11 wherein generating at least one pattern set includes:

defining a fixed number of patterns in a given pattern set wherein said fixed number of patterns originates from at least one source selected from a group comprised of;

at least one pattern from a memory device, at least one pattern input by a user in real time, and at least one plurality of patterns that are commonly selected for pattern matching.

13. A method according to claim 12 including:

saving and retrieving user selected ones of said fixed number of patterns in a non-volatile memory.

14. A method according to claim 11 wherein identifying a pattern relationship includes:

saving said pattern relationship for each said pair of patterns in a non-volatile memory.

15. A method according to claim 14 including:

identifying said pattern relationship as at least one type selected from a group comprised of;

superset, subset, independent, exclusive, and identical; and

determining said pattern relationship for each word of each said pair of patterns in said pattern set.

16. A method according to claim 11 wherein generating executable code is invoked in real-time in response to identifying a pattern relationship.

17. A method according to claim 11 wherein generating executable code is invoked in real-time in response to a user input command.

18. A method of generating computer executable code for improved pattern matching in a protocol analyzer, the method comprising:

monitoring a plurality of protocol data units on a communication link by way of a protocol analyzer;

generating a pattern set for use in the protocol analyzer;

identifying a pattern relationship for each pair of patterns in the pattern set; and

generating executable code that includes an unrolled recursive call tree having a minimum of external function calls to enhance run-time performance of the executable code, the executable code being unique to the pattern relationship for each pair of patterns such that the executable code requires a minimum number of comparisons to determine a match between the pattern set and at least one segment of one of the protocol data units, the minimum number of comparisons including an arithmetic sum of a maximum number of words in any one pattern of said pattern set and a maximum number of patterns in said pattern set.

19. A method of generating computer executable code for improved pattern matching in a protocol analyzer, the method comprising:

monitoring a plurality of protocol data units on a communication link by way of a protocol analyzer;

generating a pattern set for use in the protocol analyzer;

identifying a pattern relationship for each pair of patterns in the pattern set; and

generating executable code unique to the pattern relationship for each pair of patterns by executing a pattern matching code process to identify a pattern P having no subset patterns and generate at least one decision logic block to rule-in and rule-out subsequent pattern comparisons in view of said pattern P; and

executing a specialization comparison code generator to generate at least one decision logic block for special case ones of said pattern relationship such that the executable code requires a minimum number of comparisons to determine a match between the pattern set and at least one segment of one of the protocol data units.

20. A method comprising:

monitoring a plurality of protocol data units on a communication link by way of a protocol analyzer;

generating a pattern set for pattern matching use in said protocol analyzer;

identifying a pattern relationship for each pair of patterns in a selected one of said at least one pattern set, wherein said pattern relationship is selected from at least one of a group comprised of;

superset, subset, independent, exclusive, and identical; and

generating executable code unique to said pattern relationship for each of said pair of patterns such that said executable code requires a minimum number of comparisons to determine a match between said selected one of said at least one pattern set and at least one segment of one of said plurality of protocol data units,

wherein said executable code includes creating an unrolled recursive call tree having a minimum of external function calls to enhance run-time performance of said executable code, and

wherein said minimum number of comparisons in said executable code is an arithmetic sum of a maximum number of words in any one pattern of said pattern set and a maximum number of patterns in said pattern set, and

wherein said executable code includes a pattern matching code process to identify a pattern P having no subset patterns and generate at least one decision logic block to rule-in and rule-out subsequent pattern comparisons in view of said pattern P, and a specialization comparison code generator to generate at least one decision logic block for special case ones of said pattern relationship.

21. A computer-readable medium containing computer executable instructions that generate computer executable code for improved pattern matching in a protocol analyzer, the computer executable instructions comprising:

an instruction that monitors a plurality of protocol data units on a communication link by way of a protocol analyzer;

an instruction that generates a pattern set for use in the protocol analyzer;

an instruction that identifies a pattern relationship for each pair of patterns in the pattern set; and

an instruction that generates executable code unique to the pattern relationship for each pair of patterns such that the executable code requires a minimum number of comparisons to determine a match between the pattern set and at least one segment of one of the protocol data units.

22. A computer-readable medium as in claim 21 wherein the instruction that generates the pattern set defines a fixed number of patterns in a given pattern set, the fixed number of patterns originating from at least one source selected from a group comprised of a pattern from a memory device, a pattern input by a user in real time, and a plurality of patterns that are commonly selected for pattern matching.

23. A computer-readable medium as in claim 22 wherein the computer executable instructions comprise an instruction that saves user-selected ones of the fixed number of patterns in a non-volatile memory.

24. A computer-readable medium as in claim 21 wherein the computer executable instructions comprise an instruction that saves the pattern relationship for each pair of patterns in a non-volatile memory.

25. A computer-readable medium as in claim 24 wherein the computer executable instructions comprise an instruction that identifies each pattern relationship as one of the group comprising superset, subset, independent, exclusive, and identical, and determines the pattern relationship for each word of each pair of patterns in the pattern set.

26. A computer-readable medium as in claim 21 wherein the instruction that generates executable code is invoked in real-time in response to the instruction that identifies a pattern relationship.

27. A computer-readable medium as in claim 21 wherein the instruction that generates executable code is invoked in real-time in response to a user input command.

28. A computer-readable medium containing computer executable instructions that generate computer executable code for improved pattern matching in a protocol analyzer, the computer executable instructions comprising:

an instruction that monitors a plurality of protocol data units on a communication link by way of a protocol analyzer;

an instruction that generates a pattern set for use in the protocol analyzer;

an instruction that identifies a pattern relationship for each pair of patterns in the pattern set; and

an instruction that generates executable code that includes an unrolled recursive call tree having a minimum of external function calls to enhance run-time performance of the executable code, the executable code being unique to the pattern relationship for each pair of patterns such that the executable code requires a minimum number of comparisons to determine a match between the pattern set and at least one segment of one of the protocol data units.

29. A computer-readable medium containing computer executable instructions that generate computer executable code for improved pattern matching in a protocol analyzer, the computer executable instructions comprising:

an instruction that monitors a plurality of protocol data units on a communication link by way of a protocol analyzer;

an instruction that generates a pattern set for use in the protocol analyzer;

an instruction that identifies a pattern relationship for each pair of patterns in the pattern set;

an instruction that generates executable code unique to the pattern relationship for each pair of patterns such that the executable code requires a minimum number of comparisons to determine a match between the pattern set and at least one segment of one of the protocol data units;

an instruction that identifies a pattern P having no subset patterns and generates a decision logic block to rule-in and rule-out subsequent pattern comparisons in view of the pattern P; and

an instruction that generates a decision logic block for special case ones of the pattern relationship.