DETECTING PRESENCE OF PRE-SPECIFIED STRINGS IN A MESSAGE
BACKGROUND
[0001] A computing system may comprise programmable devices to store, retrieve, and process data. The computing system may comprise a combination of hardware and software components, which may support various applications such as security applications, billing applications, and other similar applications. The computing system may, also, be a part of a network, which may comprise a group of interconnected computing systems and in such a case the communication system may support various communication protocols.
[0002] The computing system, for example, may receive a message and may detect whether a pre-specified string is present in a message. The computing system may use string search algorithms to detect the presence of a pre-specified string. For example, the computing system may support 'fgrep' utility, which may use Aho-Corasick string search algorithm to detect the presence of a pre-specified string. The string search algorithms may use sequential search techniques, which may consume more time to detect the pre-specified strings in the message.
BRIEF DESCRIPTION OF THE DRAWINGS
[0003] The invention described herein is illustrated by way of example and not by way of
limitation in the accompanying figures. For simplicity and clarity of illustration, elements
illustrated in the figures are not necessarily drawn to scale. For example, the dimensions
of some elements may be exaggerated relative to other elements for clarity. Further,
where considered appropriate, reference labels have been repeated among the figures to
indicate corresponding or analogous elements.
[0004] FIG. 1 illustrates an embodiment of a computing system 100.
[0005] FIG. 2 illustrates an embodiment of the computing system 100 detecting the
presence of pre-specified strings in a message.
[0006] FIG. 3 illustrates an embodiment of a pre-specified string set 310, a state diagram
330, a failure function 360, and an output function 390 generated based on the string set
310.
[0007] FIG. 4 illustrates an embodiment of the computing system 100 generating an
allowed states table.

[0008] FiG. 5 illustrates an embodiment of the allowed states table.
[0009] FIG. 6 illustrates an embodiment of the computing system 100, concurrently,
detecting the presence of pre-specified strings in sub-messages,
DETAILED DESCRIPTION
[0010] The following description describes detecting the presence of pre-specified strings in a message. In the following description, numerous specific details such as logic implementations, resource partitioning, or sharing, or duplication implementations, types and interrelationships of system components, and logic partitioning or integration choices are set forth in order to provide a more thorough understanding of the present invention. It will be appreciated, however, by one skilled in the art that the invention may be practiced without such specific details. In other instances, control structures, gate level circuits, and full software instruction sequences have not been shown in detail in order not to obscure the invention. Those of ordinary skill in the art, with the included descriptions, will be able to implement appropriate functionality without undue experimentation. [0011] References in the specification to "one embodiment", "an embodiment", "an example embodiment", indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to affect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described. [0012] Embodiments of the invention may be implemented in hardware, firmware, software, or any combination thereof. Embodiments of the invention may also be implemented as instructions stored on a machine-readable medium, which may be read and executed by one or more processors. A machine-readable medium may include any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computing device). For example, a machine-readable medium may include read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; electrical, optical, acoustical or other forms of propagated signals (e.g., carrier waves, infrared signals, and digital signals). Further, firmware, software, routines, and instructions may be described herein as performing

certain actions. However, it should be appreciated that such descriptions are merely for convenience and that such actions in fact result from computing devices, processors, controllers, and other devices executing the firmware, software, routines, and instructions. [0013] An embodiment of a computing system 100 is illustrated in Fig. 1. In one embodiment, the computing system 100 may comprise a processor 110, a memory 170, a chipset 180, and I/O devices 190-1 through 190-N. The computing system 100 may, also, represent a network device such as a router, a switch, and similar other devices, which may detect presence of pre-specified strings in a message.
[0014] The I/O devices 190 may comprise various devices such as a key board, mouse, network interface card, display monitors, or similar other devices to enable a user to interact with the processor 110 and the memory 170. In one embodiment, the I/O devices 190 may couple to the chipset 180 via buses that may use, for example, a peripheral component interconnect (PCI) Express, advanced graphics port (AGP), universal serial bus (USB), Serial Advanced Technology Attachment (SATA), and similar other technologies. In one embodiment, a user may use an I/O device 190 to configure the computing system 110. For example, a user may use the key board to provide a pre-specified string set (S), the presence of which may be detected in one or more messages. [0015] The memory 170 may store data that may be written or retrieved by the processor 110 and the I/O devices 190. In one embodiment, the memory 170 may store the pre-specified string set (S), state diagrams, state tables, and similar data values that may be used by the processor 110. In one embodiment, the memory 170 may comprise a dynamic random access memory (DRAM) and a static random access memory (SRAM). In one embodiment, the memory 170 may be coupled to the chipset 180 using a memory bus. [0016] The chipset 180 may couple the processor 110 and the output devices 190 and the memory 170. In one embodiment, the chipset 180 may transfer data units between the processor 110 and the output devices 190 and the memory 170. In one embodiment, the chipset 180 may support memory bus to interface with the memory 170. The chipset 180 may support technologies such as Serial Advanced Technology Attachment (SATA), Integrated Drive Electronics (IDE), Universal Serial Bus (USB), and Low Pin Count (LPC) to interface with the I/O devices 190. The chipset 180 may support front side bus (FSB) to support transactions between the processor 110 and the other devices of the computing system 100.

[0017] The processor 110 may manage various resources and processes within the computing system 100 and may execute software instructions as well. The processor 110 may comprise, for example, one or more microprocessors from the Pentium®, Itanium®, Xeon®, or Duo® family of Intel® microprocessors. The processor 110 may interface with the chipset 180 to send data units to and receive data units from the memory 170 and the I/O devices 190. In one embodiment, the processor 110 may, quickly, detect whether the pre-specified strings are present in a message. In one embodiment, the processor 110 may generate sub-messages from a message and may, concurrently, detect the presence of the pre-specified strings in each sub-message. In one embodiment, the processor 110 may comprise an interface 112, a control unit 113, a state diagram generator 114, programmable processing units (PPU) 115-1 to 115-N, an allowed states generator 116, and a scratch pad 118.
[0018] In one embodiment, the interface 112 may receive a set of pre-specified strings and send the pre-specified strings to the control unit 113. In one embodiment, the interface 112 may receive one or more messages and may pass the messages to the PPUs 115. In one embodiment, the interface 112 may receive a signal from the control unit 113 and may pass the signal to one of the I/O devices 190. In one embodiment, the signal may indicate the identifier of the pre-specified strings that may be present in the message. [0019] In one embodiment, the control unit 113 may provide a 'diagram generate signal' to the state diagram generator 114 after receiving the pre-specified strings set (S) from the interface 112. In one embodiment, the control unit 113 may provide a 'table generate signal' to the allowed states generator 116 after determining that a state diagram is generated by the state diagram generator 114. In one embodiment, the control unit 113 may provide a 'search signal' to the PPUs 115. In one embodiment, the control unit 113 may retrieve, for example, a status signal stored in the scratch pad 118 and may determine whether a pre-specified string is present in the message. The control unit 113 may generate a 'string found' or a 'string not found' signal based on the status signal and may pass the signal to the interface 112.
[0020] In one embodiment, the state diagram generator 114 may generate a state diagram based on the pre-specified strings of the set S. In one embodiment, the state diagram generator 114 may generate a state diagram, for example, as shown in state diagram (SD) 330 of Fig. 3. In one embodiment, the state diagram may comprise a root node and one or more branches originating from the root node. In one embodiment, the branches in the

state diagram may be determined based on the number of pre-specified strings present in the set S. In one embodiment, each branch may comprise one or more nodes coupled by edges and each edge may represent a byte or a character in the pre-specified string. [0021 ] In one embodiment, the allowed states generator 116 may generate an allowed states table in response to receiving the 'table generate signal' from the control unit 113. In one embodiment, the allowed states table may comprise a substring to each node of the state diagram, suffixes to each node, and the allowed states that may be accessed from each node. In one embodiment, the substring to a present node may equal ordered collection of bytes of the edges present between the root node and the present node. In one embodiment, the substring of a first node may equal, for example, (p) of a first edge coupling the root node and the first node. Likewise, a substring of a second node may equal (pf), which is an ordered collection of (p) and (f) of the first edge and a second edge present between root node and the first node and between the first node and the second node.
[0022] In one embodiment, the allowed states generator 116 may generate suffixes to each node in the state diagram. In one embodiment, the suffixes to a present node may equal ordered accumulation of bytes of the edges present between each node positioned prior to the present node and the present node. In one embodiment, if the present node is at Nth position, the suffixes may equal the ordered accumulation of the bytes of the edges present between nodes at position {[(N-l) andN], [(N-2) and N], [(N-3) and N] ...(0 and N)}. [0023] For example, a first node and a second node may be present between the root node and the present node and a first edge may couple the root node and the first node, a second edge may couple the first node and the second node, and a third edge may couple the second node and the present node. The characters, which correspond to the first, the second, and the third edge may equal 'm', T, and 'k', respectively. The suffixes to the present node may equal 'k', 'Ik', and 'mlk'. The byte 'k' may equal a first suffix to the present node, wherein the third edge, corresponding to the byte k, may couple the present node and the second node. Likewise, 'Ik' may equal an accumulation of bytes of the second edge and the third edge, and 'mlk' is the accumulation of bytes of the first, the second, and the third edge.
[0024] In one embodiment, the processor 110 may employ one or more processing units such as the programmable processing units (PPQ) 115-1 to II5-N to detect the presence of pre-specified strings in a message. Each PPU 115-1 to 115-N may, concurrently, search

different portions of a message M to detect the presence of the pre-specified strings. In one embodiment, the PPU 115-1 may generate sub-messages (Ml, M2, ..., Mn) from the message M. In one embodiment, the PPU 115-2, during a first time duration, may start the search operation in response to receiving a search signal from the control unit 113. In one embodiment, the PPU 115-2 may, also, detect, during the first time duration, the presence of the pre-specified strings having their first byte present within the first sub-message Ml. However, a pre-specified string may span over one or more sub-messages such as, for example, M1 and M2. Concurrently, the PPU 115-3 may detect the presence of the pre-specified strings having their first byte present within the second sub-message M2. [0025] In one embodiment, the PPU 115-2 may use the state diagram and the allowed states table to detect the presence of pre-specified strings having a first byte within the first sub-message M1. In one embodiment, the allowed states table may comprise data, which may enable the PPUs 115 to stop the search operation after detecting the pre-specified strings having the first byte within a corresponding sub-message and spanning over the next sub-messages. For example, sub-message Ml may comprise the first byte of a first pre-specified string and M2 may comprise the last byte of the first pre-specified string. [0026] The PPU 115-3 may search a second sub-message M2 while the PPU 115-2 may search the first sub-message Ml. Thus, the PPUs 115-2 and 115-3 may be deemed to be operating in parallel. As a result, the processor 110 may, quickly, detect the presence of pre-specified strings in a message. In one embodiment, the PPUs 115 may set a status signal such as a flag to a first logic level in response to detecting the presence of the pre-specified strings and to a second logic level otherwise. In one embodiment, the status signal may comprise the node identifier based on which the detected pre-specified string may be identified.
[0027] An embodiment of the computing system 100 detecting the presence of the pre-specified strings in the message is illustrated in Fig. 2. In block 210, the control unit 113 may receive a set S comprising strings (SI, S2,..., Sn). In one embodiment, the control unit 113 may send the pre-specified string set S and the 'diagram generate signal' to the state diagram generator 114.
[0028] In block 220, the state diagram generator 114 may generate a state diagram (SD) to represent the pre-specified strings (SI, S2, ..., Sn). In one embodiment, each branch may represent the pre-specified strings and each branch may originate from the root node, which is a common node to all the branches. In one embodiment, each branch may

comprise nodes coupled by edges, which represent a byte each. In one embodiment, the
state diagram generator 114 may generate an output function (OF) and a failure function
(FF) based on the state diagram (SD).
[0029] In block 230, the state table generator 116 may generate a state table (ST), which
may comprise a list of nodes that may be reached from a present node. In one
embodiment, the state table generator 116 may generate the state table in response to
receiving the 'table generate signal'.
[0030] In block 250, the interface 112 may receive a message M and may send the
message M to the PPU 115-1. In block 270, the PPU 115-1 may generate N sub-messages
or segments (M|, M2, ••., Mn) from the message M and each segment (Mi, M2, ..., Mn)
may be marked by a boundary (Bj, 82, ..., Bn), respectively.
[0031 ] In block 290, the PPUs 115-2 to 115-N may, concurrently, detect the pre-specified
strings present in each segment (M|, M2, ..., Mn), respectively.
[0032] An embodiment of a set of pre-specified strings 310, a state diagram 330, a failure
function 360, and an output function 390 is depicted in Fig. 3. In one embodiment, the
user of the computing system 100 such as an administrator may provide the pre-specified
strings set (S) using, for example, a graphical user interface (GUI) displayed on the I/O
unit 190-1 such as a display unit.
[0033] An embodiment of the pre-specified string set 310 is shown comprising rows 311-
315 and each row 311-315 may comprise a string ID field and a pre-specified string field.
The row 311 may comprise SI and 'abcde', which, respectively, represent the string
identifier and the pre-specified string. Likewise, the rows 312-315 may comprise string
identifiers (S2, S3, S4, and S5), which represent the pre-specified strings {abcdku, cdmab,
ktpad, and uvabcz}, respectively. The computing system 100 may detect the presence of
the pre-specified strings {abcde, abcdku, cdmab, ktpad, and uvabcz} in the message M
based on the string search algorithm of Fig. 2.
[0034] An embodiment of the state diagram 330 may comprise one or more branches,
which may represent pre-specified strings in set S. In one embodiment, the state diagram
330 may comprise a root node 300, which may be a common node for the branches. En
one embodiment, the bytes that are position wise identical in two or more pre-specified
strings may be represented by common edges. For example, the state diagram generator
114 may represent first four bytes (abed), which are identical in the strings SI and S2 by
common edges 330-1 to 330-4.

[0035] In one embodiment, the first branch may comprise edges 330-1 to 330-5, which may represent the characters a, b, c, d, and e, respectively. In one embodiment, the edges 330-1 to 330-5 may couple the nodes (330-331), (331-332), (332-333), (333-334), and (334-335), respectively. For example, a node 331 may be coupled to an incoming edge 330-1 and to an outgoing edge 330-2. Likewise, a second branch may represent S2 (=abcdku), which may comprise edges 330-1 to 330-4, 330-6, and 330-7. The edges 330-I to 330-7 may couple the nodes (330-331), (331-332), (332-333), (333-334), (334-336), and (336-337), respectively. The edges 330-1 to 330-4 may represent characters a, b, c, d, which are common to SI and S2, and the edges 330-5 may represent 'e' and edges 330-6 and 330-7 may, respectively, represent bytes 'k' and 'u', which differentiate SI and S2. [0036] The third branch may represent the pre-specified string S3 (=cdmab) and may comprise edges 330-8 to 330-12, which may represent c, d, m, a, and b, respectively. The edges 330-8 to 330-12 may couple the nodes (330-338), (338-339), (339-340), (340-341), and (341 -342), respectively. The fourth branch may represent S4 (=ktpad) and may comprise edges 330-13 to 330-17, which may represent the characters k, t, p, a, and d, respectively. The edges 330-13 to 330-17 may couple the nodes (330-343), (343-344), (344-345), (345-346), and (346-347). The fifth branch may represent S5 (=uvabcz) and may comprise edges 330-18 to 330-23, which represent the characters u, v, a, b, c, and z. The edges 330-18 to 330-23 may couple the nodes (330-348), (348-349), (349-350), (350-351), (351 -352), and (352-353).
[0037] An embodiment of a failure function is depicted in table 360. In one embodiment, the PPU 115-2 may check the failure function of table 360 to determine if a next node, in other branch, is accessible from a present node. The table 360 may comprise rows 361-383 and each row may comprise a present node field and a next node field. In one embodiment, the rows 361-363, 365, 368-371, 373-375, 377-381, and 383 may comprise 331-333, 335, 338-341, 343-345, 347-351, and 353 in the present node field and 300 in the next node field. The above entries of the table 360 indicate that the next node that may be accessible from each of the above present node may equal the root node 300. [0038] However, a next node, other than the root node 300, present in other branches may be accessible from some of the present nodes. In one embodiment, as indicated in row 364, a next node 339 may be reached from the present node 334. For example, a message may comprise "...abcdmab...1, and the PPU 115-2 may move along the nodes 331-334 of the first branch while performing the search operation. The node 334 is reached after

detecting a match for the byte 'd'. In one embodiment, the PPU 115-2 may not reach either 'e' of edge 330-5 or 'k' of edge 330-6 as the next byte in the message equals 'm'. However, 'cdmab' is a pre-specified string and the presence of 'cdmab' may be detected. [0039] The PPU 115-2 may check the failure function 360 to determine whether a next node, other than the root node 300, is available for the present node 334. The PPU 115-2 may reach the next node 339 from the present node 334 and continue the search operation, in the second branch, starting from the next node 339. Similarly, the rows 366, 367, 372, 376, and 382 may comprise the next nodes 343, 348, 332, 331, and 333, which may be reached from the present nodes 336, 337, 342, 346, and 352.
[0040] An embodiment of the output function is depicted in table 390. The table 390 may comprise rows 391-395 and each row may comprise a matching node field and the string present field. The PPU 115-2 may check, as indicated in block 250, the output function 390 after each match is found to determine if the pre-specified string is detected. For example, the row 391 depicts 335 and SI. respectively, in the matching node and the string present field. In one embodiment, the PPU 115-2 may check the output function 390 after detecting a match for 'e' of the edge 330-5. The PPU 115-2 may set the status signal to indicate that the string S1 is present in the message after checking that the node 335 is present in the output function 390. Similarly, rows 392-395 may comprise (337, S2), (342, S3), (347, S4), and (353, S5), which indicate the pre-specified strings S2, S3, S4, and S5 that may be deemed to be detected if the nodes 337, 342, 347, and 353 are reached.
[0041 ] An embodiment of the computing system 100 generating the allowed states table 500 is illustrated in Fig. 4. In block 410, the allowed states generator 116 may generate a list of nodes in the state diagram 330. In one embodiment, the allowed states generator 116 may retrieve the state diagram 330 from the memory 170 after receiving the table generate signal from the control unit 113.
[0042] In block 430, the allowed states table generator 116 may generate a sub-string for each node. In one embodiment, the substring to a present node may equal ordered collection of all the bytes or characters of the edges present between the root node and the present node.
[0043] In block 450, the allowed states table generator 116 may generate suffixes to each node, in one embodiment, the suffixes to a present node may equal ordered accumulation of characters of the edges present between each node prior to the present node and the

present node. In one embodiment, if the present node is at N* position, the suffixes may
equal the ordered accumulation of the characters of the edges present between nodes at
position {[(N-1) and N], [(N-2) and N], [(N-3) and N] ...(0th and N)}.
[0044] In block 470, the allowed states table generator 116 may identify the valid suffixes
of the suffixes generated in block 450. In one embodiment, a suffix may be referred to as
a valid suffix if the edges starting form the root node 300 that represent each character of
the suffix are present.
[0045] For example, the node 332 may comprise suffixes 'b' and 'ab'. However, 'ab' is a
valid suffix as the state diagram 330 depicts an edge 330-1 having a character 'a' coupled
to the root node 300 and 'b' is an invalid suffix as none of the edges coupled to the root
node 300 correspond to the character 'b'.
[0046] In block 490, the allowed states table generator 116 may generate a list of nodes
that may be reached from each valid suffix. For example, the nodes 333, 334, 335, 336,
and 337 may be reached from the node 332, which has a valid suffix 'ab'.
[0047] An embodiment of the allowed states table 500 is illustrated in Fig. 5. The table
500 may comprise rows 551 -573 and each row may comprise - state/node field, sub-string
of the state/node field, suffixes to the state/node field, and allowed states/nodes field. As
described in block 410, the allowed states table generator 116 may generate a list of
states/nodes 331 -353 present in the state diagram 330. For each node, the allowed states
generator 116 may generate a sub-string, suffixes, and allowed states/nodes.
[0048] For example, the row 561 may comprise a node 311, cdma, (a, ma, dma, cdma) and
(332, 333, 334, 335, 336, 337, and 342) in the state/node field, sub-string of the state/node
field, suffixes to the state/node field, and allowed states/nodes field, respectively. The
valid suffixes for the node 311 may equal 'a' and 'cdma' and the states that may be
reached from the nodes 331 corresponding to 'a' and 341 corresponding to 'cdma' may
equal (332, 333, 334, 335, 336, and 337) and 342. Similarly, the allowed states table
generator 116 may generate the entries for the other nodes.
[0049] An embodiment of the computing system 100, concurrently, detecting the presence
of the pre-specified strings in the segments Mi to Mn is illustrated in Fig. 6.
[0050] In block 601, the PPU 115-2 may receive a message M and a sub-message Ml. In
block 605, the PPU 115-2 may assign first bytes of the first edges, for example, to an array
type variable present byte (PB), and first nodes to, for example, an array type variable
present node (PTM) and the first byte of Ml to a variable start byte (SB).

[0051 ] In block 6! 0, the PPU 115-2 may compare each element in the present byte with
the start byte. In one embodiment, the PPU 115-2 may start the search operation in
response to receiving a start signal from the control unit 113.
[0052] In block 615, the PPU 115-2 may check if a match between the present byte and
the start byte is found and control passes to block 620 if a match is not found and to block
630 if a match is found.
[0053] In block 620, the PPU 115-2 may check whether more bytes are present in Ml and
control passes to block 625 if more bytes are present in Ml and the search operation may
end otherwise. As more bytes are present in Ml, control passes to block 625.
[0054] In block 625, the PPU 115-2 may assign a next byte of the message M to the start
byte and control passes to block 610. In block 630, the PPU 115-2 may check whether the
present node is present in the output function 390 and may cause control to reach block
635 if the present node is present in the output function 390 and to block 640 otherwise.
[0055] In block 635, the PPU 115-2 may set the status signal and store the string identifier
associated with the node present in the output function 390. The control unit 113 may
retrieve the status signal and the string identifier and may generate a string found signal
and control may pass to block 670.
[0056] In block 640, the PPU 115-2 may check if the start byte is within the boundary Bl
of Ml and control may pass to block 645 if the start byte is within the boundary Bl and to
block 660 if the start byte is not within the boundary Bl.
[0057] In block 645, the PPU 115-2 may check if the start byte is the last byte of Ml and
control may pass to block 650 if SB is the last byte of Ml and to block 670 otherwise.
[0058] In block 650, the PPU 115-2 may store the allowed states or nodes, of a first
branch of SD, that may be reached from the present node and control may pass to block
660.
[0059] In block 660, the PPU 115-2 may check if the allowed states or nodes are stored
for the present node in the first branch and control passes to block 665 if the allowed states
are present and the search operation may end otherwise.
[0060] In block 665, the PPU 115-2 may assign the next byte of the next edge to the
present byte and next byte in M to the start byte. In block 670, the PPU 115-2 may assign
a next node of the state diagram to the present node, a next byte in the state diagram to the
present byte, and the next byte of M to the start byte.

[0061 ] In block 675, the PPU 115-2 may compare the present byte with the start byte. In
block 680, the PPU 115-2 may check whether a match is found and control passes to block
630 if a match is found and to block 685 otherwise.
[0062] In block 685, the PPU 115-2 may check whether a jump node to the present node is
present in the failure function 360 and control may pass to block 690 if the jump node to
the present node is present and the search may end if the jump node to the first node does
not exist.
[0063] In block 690, the PPU 115-2 may check if the start byte is within the boundary Bl
of the message M1 and control may passes to block 691 if the present byte is within the
boundary Bl and to block 695 if the present byte is not within the boundary Bl.
[0064] In block 691, the PPU 115-2 may check if SB is the last byte of Ml and control
may pass to block 692 if SB is the last byte of Ml and to block 698 if SB is not the last
byte of Ml.
[0065] In block 692, the PPU 115-2 may store the allowed states of the jump node in a
next branch. In block 695, the PPU 115-2 may check if the allowed states for the jump
node in the next branch are present and control may pass to block 698 if the allowed states
are present and string search operation may end otherwise.
[0066] In block 698, the PPU 115-2 may assign jump node to the present node and the
jump byte to the present byte and control may pass to block 675.
[0067] In one embodiment, the PPU 115-2 may receive, in block 601, a message M
(-•'xyzabedmabcdektpadoprqfs') and a sub-message Ml (=xyzabc), which is a portion of
the message M marked by a boundary Bl. The PPU 115-2 may assign, in block 605, first
bytes (a, c, k, and u) of the edges 303-1, 303-8, 303-13, and 303-18 to the present byte, the
first nodes (331, 338, 343, and 348) coupled to the leading end of the first edges to the
present node, and the first byte (x) of Ml to the start byte. In one embodiment, the PPU
115-2 may compare (a, c, k, and u), in block 610, with the start byte 'x' of Ml. In one
embodiment, the control unit 113 may issue search signal to the other PPUs 115-3 to 115-
5, which may, concurrently, start the search operations in other segments M2=dmabcd;
M3=ektpad; and M4=oprqfs.
[0068] In one embodiment, the PPU 115-2 may cause control to pass, in block 615, to
block 620 as the start byte 'x' of M1 is not equal to the present node. In one embodiment,
the PPU 115-2 may assign, in block 620, a next byte 'y' to the start byte. The blocks 610-
625 may be repeated until the byte assigned to the start byte matches with at least one of

the first bytes (a, c, k, or u) or until all the bytes of Ml are compared. In one embodiment, the blocks 610-625 may be repeated until the programmable control unit 115-2 detects a match between the start byte equaling 'a' and the present byte equating 'a'. As a result, control may reach block 630 from block 615.
[0069] The PPU 115-2, in block 630, may cause control to pass to block 640, as the present node 331 is not present in the output function 390. In one embodiment, the start byte, which points to 'a' may be within Bl and control may pass to block 645. The PPU 115-2 may check if 'a' is the last byte of Ml and control may pass to block 670 as 'a' is not the last byte of M1. Before control passes to block 670, the value of present node (PN) may equal 331; the value of present byte (PB) may equal 'a', and the start byte (SB) may equal 'a'. During the first assignment, the PPU 115-2 may assign, in block 670, 332 to PN, 'b' to PB, and 'b' to SB. The PPU 115-2 may compare, in block 675, PB and SB and may cause control to pass to block 680 as PB equals SB. The PPU 115-2 may repeat the blocks 630, 640, 670, 675, and 680 until the SB equals a byte that is not within Bl. For example, during the second assignment, the values of PN, PB, and SB may equal 333, 'c\ and 'c' and during the third assignment, the values of PN, PB, and SB may equal 334, 'd'. and 'd'.
[0070] The PPU 115-2, in block 640, may cause control to pass to block 650 as the SB (=d) is not within B1. The PPU 115-2 may store, in block 650, the allowed states, which correspond to the PN (=334). In one embodiment, the allowed states for 334 may equal (340, 341, 342, 335, 336, and 337). In one embodiment, the PPU 115-2 may continue the search operation beyond Bl if the first byte of a pre-specified string is present within Bl. The PPU 115-2 may check, in block 660, whether the allowed states are present for the PN. As allowed states are present for the PN, the PPU 115-2 may assign, in block 575, next byte (e and k of edges 330-5 and 330-6) to the present byte and the next byte (m) of message M to the start byte. As there is no match between PB and SB, control may pass to block 685.
[0071 ] The PPU 115-2, in block 685, may refer to the failure function 360 to determine if a jump node is available for PN. A jump node 339, in row 364 of table 360, is available for PN (=334) and, as a result, control may pass to block 690. In one embodiment, the availability of jump node (339) indicates that, at least, portions of the pre-specifled strings may be overlapping in the message. In one embodiment, the PPU 115-2 may check, in block 690, whether SB is within Bl and control may pass to block 695 as 'm' is not within

Bl. The PPU 115-2 may, in block 695, check whether allowed states are present for the jump node JN (=339). In one embodiment, the PPU 115-2 may assign a next node (340) of .IN (339) to PN and jump byte 'm' to present byte (PB).
[0072] The PPUI 15-2 may compare, in block 675, PB (=m) and SB (=m) and control may pass to block 630. The PPU 115-2 may continue the search operation by, iteratively, performing the blocks 640, 650, 660, 665, 675, 680, and 630. During the first iteration, the values of PN, PB, and SB may equal 341, 'a', and 'a' and during the second repetition, the values of PN, PB, and SB may equal 342, 'b', and 'b'. During the third iteration, the PPU 115-2 may set the status signal and store the string identifier S3 in the scratch pad 118 as PN (=342) is present in the output function 390. Thus, the presence of the pre-specified string 'cdmab' in the message M may be detected.
[0073] Certain features of the invention have been described with reference to example embodiments. However, the description is not intended to be construed in a limiting sense. Various modifications of the example embodiments, as well as other embodiments of the invention, which are apparent to persons skilled in the art to which the invention pertains are deemed to lie within the spirit and scope of the invention.

What is claimed is:
1. An apparatus comprising
a state diagram generator to generate a state diagram comprising nodes coupled by edges to represent pre-specified strings,
an allowed states generator coupled to the state diagram generator to generate a list of allowed states that may be reached from a present node,
a second programmable processing unit coupled to the allowed states generator to detect the presence of the pre-specified strings in a second segment of the message, and
a first programmable processing unit coupled to the allowed states generator that concurrent to the second programmable processing unit detects the presence of the pre-specified strings in a first segment of a message.
2. The apparatus of claim 1, wherein the first programmable processing unit to
detect the pre-specified strings, wherein each of the pre-specified strings have a first byte
occurring within the first segment.
3. The apparatus of claim 1, wherein the second programmable processing unit is
to detect the pre-specified strings, wherein each of the pre-specified strings have a first
byte occurring within the second segment.
4. The apparatus of claim 2, wherein the first programmable processing unit is to
detect bytes of the pre-specified strings that extend to the second segment if allowed states
for the node that corresponds to a last byte of the first segment are present.
5. The apparatus of claim 1, wherein the list of allowed states comprises nodes
that is accessible from the present node if a suffix that corresponds to the present node is
valid.
6. The apparatus of claim 5, wherein the suffix is valid if the ordered accumulation
of bytes between a root node and the present node is equal to the suffix.
7. A method to detect the presence of pre-specified strings in a message
comprising
generating a state diagram comprising nodes coupled by edges to represent pre-
specified strings,
30 generating a list of allowed states that may be reached from a present node, and
detecting, concurrently, the presence of the pre-specified strings in a first segment and a second segment of a message.

8. The method of claim 7, wherein detecting further comprises searching, in a first
duration, for the presence of bytes of the pre-specified strings, wherein each of the pre-
specified strings have a first byte occurring within the first segment.
9. The method of claim 7, wherein detecting further comprises searching, in the
first duration, for the presence of bytes of the pre-specified strings, wherein each of the
pre-specified strings have a first byte occurring within the second segment.

10. The method of claim 8, wherein the detecting further comprises searching the
bytes of the pre-specified strings that extend to the second segment if allowed states for
the node that corresponds to a last byte of the first segment are present.
11. The method of claim 7, wherein the list of allowed states comprises nodes that
is accessible from the present node if a suffix that corresponds to the present node is valid.
12. The method of claim 11, wherein the suffix is valid if the ordered
accumulation of bytes between a root node and the present node is equal to the suffix.
13. A machine-readable medium comprising a plurality of instructions that in
response to being executed result in a processor
generating a state diagram comprising nodes coupled by edges to represent pre-specified strings,
generating a list of allowed states that may be reached from a present node, and detecting, concurrently, the presence of the pre-specified strings in a first segment and a second segment of a message.
14. The machine-readable medium of claim 13, wherein detecting further
comprises searching, in a first duration, for the presence of bytes of the pre-specified
strings, wherein each of the pre-specified strings have a first byte occurring within the first
segment.
15. The machine-readable medium of claim 13, wherein detecting further
comprises searching, in the first duration, for the presence of bytes of the pre-specified
strings, wherein each of the pre-specified strings have a first byte occurring within the
second segment.
16. The machine-readable medium of claim 14 comprises detecting the bytes of
the pre-specified strings that extend to the second segment if allowed states for the node
that corresponds to a last byte of the first segment are present.

17. The machine-readable medium of claim 13, wherein the list of allowed states
comprises nodes that is accessible from the present node if a suffix that corresponds to the
present node is valid.
18. A device comprising
a input-output device to provide pre-specified strings,
a processor coupled to the input-output device to generate a list of allowed states that may be reached from a present node, to detect the presence of the pre-specified strings in a first segment of a message, and to detect, concurrently, the presence of the pre-specified strings in a second segment of the message, and
wherein the input-out device is to generate a signal to indicate whether the pre-specified string are found in the message.
19. The device of claim 19, wherein the device is a router.
20. The device of claim 19, wherein the device is a client system.