FAST AND SCALABLE PROCESS FOR REGULAR EXPRESSION SEARCH

• US 20080034427A1
• Filed: 07/30/2007
• Published: 02/07/2008
• Est. Priority Date: 08/02/2006
• Status: Abandoned Application

• Current Assignee: NEC Laboratories America Inc (NEC Corporation)
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Becchi, Michela, Cadambi, Srihari, Chakradhar, Srimat T.
• Application Number:
  US11/830,487
• Publication Number:
  US 20080034427A1
• Time in Patent Office: Days
• US Class Current: 726/22
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

A method includes reducing a deterministic finite automata DFA representative of an expression to provide a smaller DFA, and subjecting information that matches the smaller DFA to non-deterministic finite automata NFA representative of the expression for reducing memory required for pattern matching of the information.

Claims

1. A method comprising the steps of:

reducing a deterministic finite automata DFA representative of an expression to provide a smaller DFA, and

subjecting information that matches said smaller DFA to non-deterministic finite automata NFA representative of said expression for reducing memory required for pattern matching of said information.

2. The method of claim 1, wherein said smaller DFA can produce both false positives and false negatives.

3. The method of claim 2, wherein said false positives and false negatives are resolved using said NFA.

4. The method of claim 1, wherein said smaller DFA can produce false positives and no false negatives.

5. The method of claim 4, wherein said reducing said DFA comprises building a reduced said DFA according to:

(i) where d is a transition function of said DFA,

(ii) d(S,c) indicate the state to which S transitions to upon receiving input character c,

(iii) finding two sates A and B such that, for all possible strings w, d(A,w) is an accepting state if d(B,w) is an accepting state, and

(iv) once finding A and B, moving B'"'"'s incoming and outgoing transitions to A and then deleting B.

6. The method of claim 4, wherein said information is packet information and matching of said packet information to both said smaller DFA and said NFA is indicative of a malicious packet.

7. The method of claim 1, wherein said reducing of said DFA comprises sate merging where at least two non-equivalent states in said DFA are merged into a single state using transition labels.

8. The method of claim 7, wherein said state merging is a non-lossy transformation of the original DFA producing neither false positives nor false negatives.

9. The method of claim 7, wherein said sate merging of said DFA is realized in at least one of software and hardware for reducing memory requirements.

10. The method of claim 9, wherein said hardware comprises a look up table for implementing state-to-next-sate mapping of said DFA.

11. A method comprising the steps of:

removing states from a discriminate finite automata DFA for deriving a smaller said DFA that can produce false positives and no false negatives,

building a non-discriminate finite automata NFA, and

subjecting packet information that matches said DFA to a check by said NFA for pattern matching that combines processing rate of said DFA with memory requirements of said NFA.

12. The method of claim 11, wherein said step of removing said states comprises building a reduced said DFA according to an outline where:

(i) d is a transition function of said DFA,

(ii) d(S,c) indicate the state to which S transitions to upon receiving input character c,

(iii) finding two sates A and B such that, for all possible strings w, d(A,w) is an accepting state if d(B,w) is an accepting state,

(iv) once finding A and B, moving B'"'"'s incoming and outgoing transitions to A and then deleting B.

13. The method of claim 11, wherein matching of said packet information to both said smaller DFA and said NFA is indicative of a malicious packet.

14. A method comprising the steps of:

subjecting network information to pattern matching combining reduced deterministic finite automata DFA producing false positives and no negatives followed by non-deterministic finite automata NFA for detecting network information that is malicious.