Submatch extraction

Patent metadata

Field	Value
Publication number	US-9558299-B2
Application number	US-201213460419-A
Country	US
Kind code	B2
Filing date	Apr 30, 2012
Priority date	Apr 30, 2012
Publication date	Jan 31, 2017
Grant date	Jan 31, 2017

Abstract

A method for submatch extraction may include receiving an input string, receiving a regular expression. The method may further include converting the regular expression with capturing groups into ordered binary decision diagrams (OBDDs) to extract submatches.

First claim

What is claimed is:

1. A method for submatch extraction, the method comprising:
receiving an input string;
receiving a regular expression;
converting, by a processor, the regular expression including a capturing group into an ordered binary decision diagram (OBDD);
processing the input string by the OBDD, one input string character at a time, wherein processing of an individual input string character comprises outputting a tag representing a capturing group that corresponds to the individual input string character;
determining that the regular expression matches the input string; and
in response to a determination that the regular expression matches the input string, extracting a submatch based on the OBDD by processing the tag and the input string in reverse order by the OBDD, one input string character at a time, wherein the submatch corresponds to a substring of the input string, and the substring corresponds to the capturing group.

2. The method of claim 1 , wherein converting the regular expression including the capturing group into the OBDD comprises:
converting the regular expression into a finite automaton with the tag representing the capturing group; and
converting the finite automaton into the OBDD.

3. The method of claim 1 , wherein the OBDD implements a plurality of regular expressions.

4. The method of claim 1 , wherein receiving the input string, receiving the regular expression and converting the regular expression are implemented at a parser.

5. The method of claim 1 , wherein receiving the input string, receiving the regular expression and converting the regular expression are implemented at a security information and event management (SIEM) system.

6. The method of claim 1 , wherein receiving the input string, receiving the regular expression and converting the regular expression are implemented at an intrusion detection system (IDS).

7. The method of claim 1 , further comprising:
converting the regular expression into a finite automaton;
using a Boolean function to represent a transition of the finite automaton; and
extracting the submatch by manipulating the Boolean function using the OBDD.

8. A submatch extraction system comprising:
a memory comprising machine readable instructions to:
receive an input string;
receive a regular expression;
convert the regular expression into a finite automaton;
use a Boolean function to represent a transition of the finite automaton;
convert the regular expression including a capturing group into an ordered binary decision diagram (OBDD), wherein the capturing group corresponds to a substring of the input string, and the substring corresponds to a submatch;

process the input string by the OBDD, one input string character at a time, wherein processing of an individual input string character comprises outputting a tag representing a capturing group that corresponds to the individual input string character;
determine if the regular expression matches the input string; and
in response to a determination that the regular expression matches the input string, extract the submatch based on manipulation of the Boolean function using the OBDD by processing the tag and the input string in reverse order by the OBDD, one input string character at a time; and
a processor to implement the machine readable instructions.

9. The submatch extraction system of claim 8 , wherein the machine readable instructions are to:
convert the regular expression into the finite automaton with the tag representing the capturing group; and
convert the finite automaton into the OBDD.

10. The submatch extraction system of claim 8 , wherein the machine readable instructions are to:
use the OBDD to implement a plurality of regular expressions.

11. A non-transitory computer readable medium having stored thereon machine readable instructions for submatch extraction, the machine readable instructions when executed cause a computer system to:
receive an input string;
receive a regular expression;
convert, by a processor, the regular expression including a capturing group into an ordered binary decision diagram (OBDD);
process the input string by the OBDD, one input string character at a time, wherein processing of an individual input string character comprises outputting a tag representing a capturing group that corresponds to the individual input string character;
determine if the regular expression matches the input string; and
in response to a determination that the regular expression matches the input string, extract the submatch by processing the tag and the input string in reverse order by the OBDD, one input string character at a time.

12. The non-transitory computer readable medium of claim 11 , wherein the machine readable instructions when executed cause the computer system to:
convert the regular expression into a finite automaton with the tag representing the capturing group; and
convert the finite automaton into the OBDD.

13. The non-transitory computer readable medium of claim 11 , wherein the machine readable instructions when executed cause the computer system to:
use the OBDD to implement a plurality of regular expressions.

14. The non-transitory computer readable medium of claim 11 , wherein the machine readable instructions when executed cause the computer system to:
convert the regular expression into a finite automaton;
use a Boolean function to represent a transition of the finite automaton; and
extract the submatch by manipulating the Boolean function using the OBDD.

Assignees

• Yang Liu
• Rao Prasad V
• Manadhata Pratyusa Kumar
• Horne William G
• Haber Stuart
• Hewlett Packard Entpr Dev Lp

Inventors

• Yang Liu
• Rao Prasad V
• Manadhata Pratyusa Kumar
• Horne William G
• Haber Stuart

Classifications

• G06F16/90344 Primary

  by using string matching techniques · CPC title

• G06F17/30985 Primary

  Physics · mapped topic