Intrusion detection accelerator Number:7,146,643 from the United States Patent and Trademark Office (PTO) owispatent Signatures of character strings in a document which may indicate a possible intrusion into or attack on a networked computer system or node thereof or other security breach are detected at high speed using a hardware accelerator within the environment of a hardware parser accelerator. An interrupt or exception can thus be issued to a host CPU before a command which may constitute such a security breach, intrusion or attack can be made executable by parsing of a document. The CPU can initiate network control measures to prevent or limit the intrusion.<H accelerator, detection, Intrusion, detec, 7146643.html, Patent, pto, 7146643

Title: Intrusion detection accelerator

Abstract: Signatures of character strings in a document which may indicate a possible intrusion into or attack on a networked computer system or node thereof or other security breach are detected at high speed using a hardware accelerator within the environment of a hardware parser accelerator. An interrupt or exception can thus be issued to a host CPU before a command which may constitute such a security breach, intrusion or attack can be made executable by parsing of a document. The CPU can initiate network control measures to prevent or limit the intrusion.

Patent Number: 7,146,643 Issued on 12/05/2006 to Dapp, et al.

Inventors: Dapp; Michael C. (Endwell, NY), Lett; Eric C. (Endwell, NY)
Assignee: Lockheed Martin Corporation (Bethesda, MD)

Appl. No.: 10/331,879

Filed: December 31, 2002

Current U.S. Class: 726/23 ; 713/164; 713/188; 726/24; 726/25

Current International Class: G06F 11/22 (20060101)

Field of Search: 713/200-201,188,164 714/819 726/23-25

References Cited [Referenced By]

U.S. Patent Documents


4279034	July 1981	Baxter
4527270	July 1985	Sweeton
4556972	December 1985	Chan et al.
4622546	November 1986	Sfarti et al.
4879716	November 1989	McNally et al.
5003531	March 1991	Farinholt et al.
5027342	June 1991	Boulton et al.
5193192	March 1993	Seberger
5214778	May 1993	Glider et al.
5247664	September 1993	Thompson et al.
5280577	January 1994	Trevett et al.
5319776	June 1994	Hile et al.
5379289	January 1995	DeSouza et al.
5414833	May 1995	Hershey et al.
5511213	April 1996	Correa
5513345	April 1996	Sato et al.
5600784	February 1997	Bissett et al.
5606668	February 1997	Shwed
5621889	April 1997	Lermuzeaux et al.
5649215	July 1997	Itoh
5655068	August 1997	Opoczynski
5666479	September 1997	Kashimoto et al.
5684957	November 1997	Kondo et al.
5696486	December 1997	Poliquin et al.
5737526	April 1998	Periasamy et al.
5742771	April 1998	Fontaine
5798706	August 1998	Kraemer et al.
5805801	September 1998	Holloway et al.
5815647	September 1998	Buckland et al.
5832227	November 1998	Anderson et al.
5848410	December 1998	Walls et al.
5850515	December 1998	Lo et al.
5905859	May 1999	Holloway et al.
5919257	July 1999	Trostle
5919258	July 1999	Kayashima et al.
5920698	July 1999	Ben-Michael et al.
5922049	July 1999	Radia et al.
5958015	September 1999	Dascalu
5969632	October 1999	Diamant et al.
5982890	November 1999	Akatsu
5991881	November 1999	Conklin et al.
5995963	November 1999	Nanba et al.
6000045	December 1999	Lewis
6006019	December 1999	Takei
6021510	February 2000	Nachenberg
6083276	July 2000	Davidson et al.
6094731	July 2000	Waldin et al.
6119236	September 2000	Shipley
6151624	November 2000	Teare et al.
6167448	December 2000	Hemphill et al.
6173333	January 2001	Jolitz et al.
6182029	January 2001	Friedman
6233704	May 2001	Scott et al.
6279113	August 2001	Vaidya
6282546	August 2001	Gleichauf et al.
6295276	September 2001	Datta et al.
6301668	October 2001	Gleichauf et al.
6304973	October 2001	Williams
6321338	November 2001	Porras et al.
6363489	March 2002	Comay et al.
6366934	April 2002	Cheng et al.
6370648	April 2002	Diep
6374207	April 2002	Li et al.
6393386	May 2002	Zager et al.
6405318	June 2002	Rowland
6408311	June 2002	Baisley et al.
6418446	July 2002	Lection et al.
6421656	July 2002	Cheng et al.
6446110	September 2002	Lection et al.
6684335	January 2004	Epstein et al.
6697950	February 2004	Ko
6792546	September 2004	Shanklin et al.
6862588	March 2005	Beged-Dov et al.
2001/0056504	December 2001	Kuznetsov
2002/0010715	January 2002	Chinn et al.
2002/0013710	January 2002	Shimakawa
2002/0035619	March 2002	Dougherty et al.
2002/0038320	March 2002	Brook
2002/0059528	May 2002	Dapp
2002/0066035	May 2002	Dapp
2002/0069318	June 2002	Chow et al.
2002/0073091	June 2002	Jain et al.
2002/0073119	June 2002	Richard
2002/0082886	June 2002	Manganaris et al.
2002/0083343	June 2002	Crosbie et al.
2002/0087882	July 2002	Schneier et al.
2002/0091999	July 2002	Guinart
2002/0099710	July 2002	Papierniak
2002/0099715	July 2002	Jahnke et al
2002/0099734	July 2002	Yassin et al.
2002/0103829	August 2002	Manning et al.
2002/0108059	August 2002	Canion et al.
2002/0111963	August 2002	Gebert et al.
2002/0111965	August 2002	Kutter
2002/0112224	August 2002	Cox
2002/0116550	August 2002	Hansen
2002/0116585	August 2002	Scherr
2002/0116644	August 2002	Richard
2002/0120697	August 2002	Generous et al.
2002/0122054	September 2002	Hind et al.
2002/0133484	September 2002	Chau et al.
2002/0143819	October 2002	Han et al.
2002/0152244	October 2002	Dean et al.
2002/0156772	October 2002	Chau et al.
2002/0165872	November 2002	Meltzer et al.
2003/0041302	February 2003	McDonald
2003/0229846	December 2003	Sethi et al.
2004/0025118	February 2004	Renner
2004/0073870	April 2004	Fuh et al.
2004/0083221	April 2004	Dapp et al.
2004/0083387	April 2004	Dapp et al.
2004/0083466	April 2004	Dapp et al.
2004/0172234	September 2004	Dapp et al.
2004/0194016	September 2004	Liggitt
2005/0039124	February 2005	Chu et al.
2005/0177543	August 2005	Chen et al.

Foreign Patent Documents


2307529	Sep., 2001	CA
WO02/11399	Feb., 2002	WO
WO 02/095543	Nov., 2002	WO

Other References

Lunteren et al., "XML Accelerator Engine", 2004. cited by examiner .
Sakharov, "Finite State Machine Specification and Generation in Java", 2000, http://sakharov.net/fsm.html. cited by examiner .
A.B. Kulkarni, S.F. Bush and S.C. Evans "Detecting Distributed Denial-of- Service Attacks Using Kolmogorov Complexes Metrics" dated Dec. 2001. cite- d by other .
S.C. Evans and S.F. Bush "Symbol Compression Ratio for String Compression and Estimation of Kolmogorov Complexity" dated Nov. 2001. cited by other .
M. Neumann; "Encryption Black Box (SiNic)"; ESNET Steering Committee Meeting, Sep. 11-13, 2001. cited by other .
E. Zadok; "Stackable File Systems as a Security Tool"; Technical Report CUCS-036-99 Columbia University Computer Science Department; Dec. 1999; pp. 1-19. cited by other .
Kent, RFC 2401, "Security Architecture for the Internet Protocol," 1998. cited by other .
Fraser et al., "Hardening COTs Software with Generic Software Wrappers"; DARPA Information Survivability Conference and Exposition, 2000, pp. 323-337. cited by other .
Pal et al., "Open Implementation Toolkit for Building Survivable Applications", DARPA Information Survivability Conference and Exposition, 2000, pp. 197-210. cited by other .
Andrivet et al., "A Simple XML Parser", Jul. 1999, C/C++ Users Journal, R&D Publications, Lawrence, KS, US, pp. 22,24,26-28,30,32, XP008015172, ISSN: 1075-2838. cited by other .
Cooper, C., "Using Expat", Sep. 1, 1999, XP002177815. cited by other .
B. Trippe; "XML Hits the Big Time: Major Database Players get into XML"; Find articles.com; Sep. 2002; pp. 1-9. cited by other .
Business Wire, Bellevue, Wash; "DataChannel Releases the Most Advanced XML Parser--XJParser--and Introduces xDev its XML Developers Program"; Find articles.com; Apr. 16, 1999, pp. 1-9. cited by other .
InfoWorld: "Extensible Markup Language (XM). (Technology Information)"; Find articles.com; Jun. 1998; pp. 1-6. cited by other .
T. Yager, "New Standards Orbit (XML) (Technology Information)"; Find articles.com; Jun. 2000; pp. 1-9. cited by other .
Microsoft Corp., "XML: Enabling Next-Generation Web Applications"; Dytech Solutions; Apr. 1998; pp. 1-15. cited by other .
Aho, A.V. et al., "Principles of Compiler Design", Principles of Compiler Design, Reading, Addison-Wesley Publishing Co., US., 1979, pp. 73-125, XP002140006, p. 88, line 4--p. 115, line 7; figures 3.5-3.22. cited by other .
Bauer, F.L., "Compiler Construction--An Advanced Course", 1976, Spring-Verlag, Germany, XP002312623, pp. 42-55; pp. 85-108. cited by othe- r.

Primary Examiner: Louis-Jacques; Jacques
Assistant Examiner: Tran; Tongoc
Attorney, Agent or Firm: Miles & Stockbridge PC Carmichael; James T.

Parent Case Text

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims benefit of priority of U.S. Provisional Patent Application Ser. No. 60/421,773, filed Oct. 29, 2002, the entire contents of which are hereby fully incorporated by reference. Further, this application is related to U.S. patent applications Ser. No. 10/334,086, published as U.S. Patent Application Publication No. 2004/0083466 A1 and U.S. patent application Ser. No. 10/331,315, published as U.S. Patent Application Publication No. 2004/0083221 A1, corresponding to U.S. Provisional Patent applications 60/421,774 and 60/421,775, respectively) which are assigned to the assignee of this invention and also fully incorporated by reference herein.

Claims

The invention claimed is:

1. An intrusion detection system comprising: a character buffer to store a plurality of bytes of a document; a state table addressable in accordance with a byte of the document and a state to access at least one of an interrupt, an exception, or a command to store a token and next state data from said state table, wherein the command to store the token is accessed when a state in the state table is reached that indicates a valid token has been parsed; a register to store said next state data; means for combining contents of said register with a subsequent byte of the document to form a further address into said state table; a token buffer to store a plurality of tokens, wherein said plurality of tokens are available for further processing by a host processor; and a bus to communicate said interrupt or said exception to said host processor, wherein the intrusion detection system simultaneously performs a function of accessing said state table, storing said token, and combining said stored next state data with a second portion of said document in parallel.

2. The intrusion detection system as recited in claim 1, wherein said intrusion detection system is implemented within a parser.

3. The intrusion detection system as recited in claim 2, wherein said state table is implemented in an external memory.

4. The intrusion detection system as recited in claim 3, further including a memory on the same chip as at least one of said register and said means for combining for storing said state table when said state table does not require implementation in said external memory.

5. The intrusion detection system as recited in claim 1, wherein said state table is implemented in memory on the same chip as at least one of said register and said means for combining.

6. The intrusion detection system as recited in claim 1, wherein said state table is accessed at a rate greater than a network packet transmission rate.

7. The intrusion detection system as recited in claim 1, further including means for presenting a pattern matching alert to be presented to said host processor in response to detection of an occurrence of an input sequence which matches a signature of one or more sequences encoded in said state table, to increase response speed.

8. The intrusion detection system as recited in claim 7, wherein an intrusion alert corresponding to said interrupt or said exception is communicated to said host processor to initiate an intrusion prevention action to prevent or limit an intrusion attempt.

9. The intrusion detection system as recited in claim 1, wherein said state table is accessed at a rate substantially equal to a network data packet transmission rate.

10. An intrusion detection method comprising: accessing a state table addressable in accordance with a byte of a document and a current state; retrieving at least one of an interrupt or an exception from said state table, if said interrupt or said exception is available; retrieving a token-storing command from said state table in response to determining that no interrupt or exception is available and that a valid token has been parsed; storing a token in a token buffer in response to said token-storing command; retrieving next state data from said state table; storing said next state data; combining said stored next state data with a subsequent byte of said document to form a further address into said state table; and simultaneously performing the accessing said state table, storing said token, and combining said stored next state data with a second portion of said document in parallel.

11. The intrusion detection method as recited in claim 10, wherein said intrusion detection method is implemented within a parser.

12. The intrusion detection method as recited in claim 11, wherein said state table is implemented in an external memory.

13. The intrusion detection method as recited in claim 10, wherein said state table is accessed at a rate greater than a network packet transmission rate.

14. The intrusion detection method as recited in claim 10, further comprising: presenting a pattern matching alert to be presented to said host processor in response to detection of an occurrence of an input sequence, which matches a signature of one or more sequences encoded in said state table, to increase response speed.

15. The intrusion detection method as recited in claim 14, wherein an intrusion alert corresponding to said interrupt or said exception is communicated to said host processor to initiate an intrusion prevention action to prevent or limit an intrusion attempt.

16. The intrusion detection method as recited in claim 10, wherein said state table is accessed at a rate substantially equal to a network data packet transmission rate.

17. A computer program product for enabling a computer to accelerate the detection of intrusions comprising: software instructions for enabling the computer to perform predetermined operations; and a computer readable medium bearing the software instructions; the predetermined operations including: accessing a state table addressable in accordance with a byte of a document and a previous state; retrieving at least one of an interrupt or an exception from said state table, if said interrupt or said exception is available; retrieving a command to store a token from said state table, if said command is available and said token has been fully parsed, and storing said token in response to said command to store said token; retrieving next state data from said state table; storing said next state data; combining said stored next state data with a subsequent byte of said document to form a further address into said state table; making said token available for subsequent processing for a different purpose after said token has been parsed and stored; and simultaneously performing the accessing said table, storing said token, and combining said stored next state data with a second portion of said document in parallel.

18. The computer program product of claim 17, wherein said different purpose is a contextual analysis to detect an intrusion at a document level.

19. The computer program product of claim 17, wherein said different purpose is an end use of the document.

20. The computer program product as recited in claim 17, wherein said different purpose is unrelated to intrusion detection.

21. An intrusion detection system comprising: means for accessing a state table addressable in accordance with a first portion of a document and a current state; means for retrieving at least one of an interrupt or an exception from said state table, if said interrupt or said exception is available; means for retrieving a command from said state table, if said command is available, and storing a token in response to a command to store a token; means for retrieving next state data from said state table; means for storing said next state data; means for combining said stored next state data with a second portion of said document to form a further address into said state table; means for simultaneously performing the functions of accessing said state table, storing said token, and combining said stored next state data with said second portion of said document in parallel; and means for communicating said interrupt or said exception to a host processor.

22. The intrusion detection system of claim 21, wherein said intrusion detection system is implemented within a parser.

23. The intrusion detection system of claim 21, further including means for presenting a pattern matching alert to be presented to said host processor in response to detection of an occurrence of an input sequence which matches a signature of one or more sequences encoded in said state table to increase response speed.

24. The intrusion detection system of claim 21, wherein an intrusion alert corresponding to said interrupt or exception is communicated to said host processor to initiate an intrusion prevention action to prevent or limit an intrusion attempt.

25. The intrusion detection system of claim 21, wherein said first portion and said second portion represent a character.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention generally relates to parsing of documents such as an XML.TM. document and, more particularly to parsing a document or other logical sequence of network data packets for detecting potential intrusion or an attack on a node of a network.

2. Description of the Prior Art

The field of digital communications between computers and the linking of computers into networks has developed rapidly in recent years, similar, in many ways to the proliferation of personal computers of a few years earlier. This increase in interconnectivity and the possibility of remote processing has greatly increased the effective capability and functionality of individual computers in such networked systems. Nevertheless, the variety of uses of individual computers and systems, preferences of their users and the state of the art when computers are placed into service has resulted in a substantial degree of variety of capabilities and configurations of individual machines and their operating systems, collectively referred to as "platforms" which are generally incompatible with each other to some degree particularly at the level of operating system and programming language.

This incompatibility of platform characteristics and the simultaneous requirement for the capability of communication and remote processing and a sufficient degree of compatibility to support it has resulted in the development of object oriented programming (which accommodates the concept of assembling an application as well as data as a group of more or less generalized modules through a referencing system of entities, attributes and relationships) and a number of programming languages to embody it. Extensible Markup Language.TM. (XML.TM.) is such a language which has come into widespread use and can be transmitted as a document over a network of arbitrary construction and architecture.

In such a language, certain character strings correspond to certain commands or identifications, including special characters and other important data (collectively referred to as control words) which allow data or operations to, in effect, identify themselves so that they may be, thereafter treated as "objects" such that associated data and commands can be translated into the appropriate formats and commands of different applications in different languages in order to engender a degree of compatibility of respective connected platforms sufficient to support the desired processing at a given machine. The detection of these character strings is performed by an operation known as parsing, similar to the more conventional usage of resolving the syntax of an expression, such as a sentence, into its component parts and describing them grammatically.

When parsing an XML.TM. document, a large portion and possibly a majority of the central processor unit (CPU) execution time is spent traversing the document searching for control words, special characters and other important data as defined for the particular XML.TM. standard being processed. This is typically done by software which queries each character and determines if it belongs to the predefined set of strings of interest, for example, a set of character strings comprising the following "<command>", "<data=dataword>", "<endcommand>", etc. If any of the target strings are detected, a token is saved with a pointer to the location in the document for the start of the token and the length of the token. These tokens are accumulated until the entire document has been parsed.

The conventional approach is to implement a table-based finite state machine (FSM) to search for these strings of interest. The state table resides in memory and is designed to search for the specific patterns in the document. The current state is used as the base address into the state table and the ASCII representation of the input character is an index into the table. For example, assume the state machine is in state 0 (zero) and the first input character is ASCII value 02, the absolute address for the state entry would be the sum/concatenation of the base address (state 0) and the index/ASCII character (02). The FSM begins with the CPU fetching the first character of the input document from memory. The CPU then constructs the absolute address in the state table in memory corresponding to the initialized/current state and the input character and then fetches the state data from the state table. Based on the state data that is returned, the CPU updates the current state to the new value, if different (indicating that the character corresponds to the first character of a string of interest) and performs any other action indicated in the state data (e.g. issuing a token or an interrupt if the single character is a special character or if the current character is found, upon a further repetition of the foregoing, to be the last character of a string of interest).

The above process is repeated and the state is changed as successive characters of a string of interest are found. That is, if the initial character is of interest as being the initial character of a string of interest, the state of the FSM can be advanced to a new state (e.g. from initial state 0 to state 1). If the character is not of interest, the state machine would (generally) remain the same by specifying the same state (e.g. state 0) or not commanding a state update) in the state table entry that is returned from the state table address. Possible actions include, but are not limited to, setting interrupts, storing tokens and updating pointers. The process is then repeated with the following character. It should be noted that while a string of interest is being followed and the FSM is in a state other than state 0 (or other state indicating that a string of interest has not yet been found of currently being followed) a character may be found which is not consistent with a current string but is an initial character of another string of interest. In such a case, state table entries would indicate appropriate action to indicate and identify the string fragment or portion previously being followed and to follow the possible new string of interest until the new string is completely identified or found not to be a string of interest. In other words, strings of interest may be nested and the state machine must be able to detect a string of interest within another string of interest, and so on. This may require the CPU to traverse portions of the XML.TM. document numerous times to completely parse the XML.TM. document.

The entire XML.TM. or other language document is parsed character-by-character in the above-described manner. As potential target strings are recognized, the FSM steps through various state character-by-character until a string of interest is fully identified or a character inconsistent with a possible string of interest is encountered (e.g. when the string is completed/fully matched or a character deviates from a target string). In the latter case, no action is generally taken other than returning to the initial state or a state corresponding to the detection of an initial character of another target string. In the former case, the token is stored into memory along with the starting address in the input document and the length of the token. When the parsing is completed, all objects will have been identified and processing in accordance with the local or given platform can be started.

Since the search is generally conducted for multiple strings of interest, the state table can provide multiple transitions from any given state. This approach allows the current character to be analyzed for multiple target strings at the same time while conveniently accommodating nested strings.

It can be seen from the foregoing that the parsing of a document such as an XML.TM. document requires many repetitions and many memory accesses for each repetition. Therefore, processing time on a general purpose CPU is necessarily substantial. A further major complexity of handling the multiple strings lies in the generation of the large state tables and is handled off-line from the real-time packet processing. However, this requires a large number of CPU cycles to fetch the input character data, fetch the state data and update the various pointers and state addresses for each character in the document. Thus, it is relatively common for the parsing of a document such as an XML.TM. document to fully pre-empt other processing on the CPU or platform and to substantially delay the processing requested.

It has been recognized in the art that, through programming, general-purpose hardware can be made to emulate the function of special purpose hardware and that special purpose data processing hardware will often function more rapidly than programmed general purpose hardware even if the structure and program precisely correspond to each other since there is less overhead involved in managing and controlling special purpose hardware. Nevertheless, the hardware resources required for certain processing may be prohibitively large for special purpose hardware, particularly where the processing speed gain may be marginal. Further, special purpose hardware necessarily has functional limitations and providing sufficient flexibility for certain applications such as providing the capability of searching for an arbitrary number of arbitrary combinations of characters may also be prohibitive. Thus, to be feasible, special purpose hardware must provide a large gain in processing speed while providing very substantial hardware economy; requirements which are increasingly difficult to accommodate simultaneously as increasing amounts of functional flexibility or programmability are needed in the processing function required.

In this regard, the issue of system security is also raised by both interconnectability and the amount of processing time required for parsing a document such as an XML.TM. document. On the one hand, any process which requires an extreme amount of processing time at relatively high priority is, in some ways, similar to some characteristics of a denial-of-service (DOS) attack on the system or a node thereof or can be a tool that can be used in such an attack.

DOS attacks frequently present frivolous or malformed requests for service to a system for the purpose of maliciously consuming and eventually overloading available resources. Proper configuration of hardware accelerators can greatly reduce or eliminate the potential to overload available resources. In addition, systems often fail or expose security weaknesses when overloaded. Thus, eliminating overloads is an important security consideration.

Further, it is possible for some processing to begin and some commands to be executed before parsing is completed since the state table must be able to contain CPU commands at basic levels which are difficult or impossible to secure without severe compromise of system performance. In short, the potential for compromise of security would be necessarily reduced by reduction of processing time for processes such as XML.TM. parsing but no technique for significantly reducing the processing time for such parsing has been available.

Many security systems rely on the ability to detect an attempted security breach at a very early stage and a security breach may be difficult or impossible to interrupt quickly or through programmed intervention, once begun. For example, a highly secure system has been proposed and is disclosed in U.S. patent applications Ser. Nos. 09/973,769 and 09/973,776, both assigned to the assignee of the present application. These applications disclose a system having two levels of internodal communications, one at very high speed, by which a node at which a possible attack or intrusion is detected can be compartmentalized and then automatically repaired, if necessary, before reconnection to the network. Acceleration of parsing therefore supports early response to a potential attack and is particularly advantageous in a system such as that disclosed in the system described in the above-incorporated patent applications since an appropriate control of the network can be initiated as an incident of parsing and can thus be initiated at an earlier time if parsing can be significantly accelerated. Proper network control, initiated in a timely fashion in response to a detection alert can effect intrusion prevention in addition to intrusion detection.

SUMMARY OF THE INVENTION

The present invention provides a hardware parser accelerator which provides extreme acceleration of parsing of documents for detection of signatures of a possible intrusion, attack or other security breach in a networked computer system at speeds which accommodate network transmission packet speeds for potentially real-time intrusion detection and prevention actions.

In order to accomplish this and other objects of the invention, an intrusion detection system, possibly implemented within a document parser is provided, comprising a character buffer for a plurality of bytes of a document, a state table addressable in accordance with a byte of a document and a state to access at least one of an interrupt or exception and next state data from the state table, a register for storing next state data, an adder for combining contents of the register with a subsequent byte of a document to form a further address into the state memory, and a bus for communicating the interrupt or exception to a host CPU.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the drawings, in which:

FIG. 1 is a representation of a portion of a state table used in parsing a document,

FIG. 2A is a high level schematic diagram of the parser accelerator in accordance with a concurrently filed related provisional patent application,

FIG. 2B is a high-level schematic diagram of the parser accelerator in accordance with the present invention,

FIG. 2C illustrates an implementation of the inv