Substring detection system and method

A method, computer program product, apparatus, and system that detects a substring in an input data string by producing a fingerprint of a portion of the data string and comparing the fingerprint of the portion of the data string to at least one predefined fingerprint. The predefined fingerprint may be a fingerprint of a portion of a predefined pattern of interest. If the fingerprints match, further pattern recognition processing may be performed on the input string.

TECHNICAL FIELD

This disclosure relates to pattern recognition and, more particularly, to substring detection for use in a pattern recognition system and method.

BACKGROUND

In some applications and systems, such as networking systems, it is desirable to recognize the appearance of particular data. For example, network security systems, such as firewalls or intrusion detection systems, may use pattern matching to recognize certain data strings received by the systems. Viruses and/or other types of unwanted data, for example, may be recognized for network protection. Pattern matching may also be used for other purposes, such as network monitoring or biological pattern matching (e.g., particular portions of a deoxyribonucleic acid (DNA) sequence may be of interest for medical research). To detect the appearance of desirable or undesirable data, one or more predefined data patterns may be compared to the data under study. If one or more of the predefined data patterns matches a portion of the data under study, appropriate action may be executed. If a pattern representative of a computer virus is detected, for example, the data that contains the virus may be removed to reduce infection. Existing multiple pattern matching algorithms are complex and may use relatively large memory footprints and a significant amount of time to perform multiple pattern matching on data strings.

Although the following Detailed Description will proceed with reference being made to illustrative embodiments, many alternatives, modifications, and variations thereof will be apparent to those skilled in the art. Accordingly, it is intended that the claimed subject matter be viewed broadly, and be defined only as set forth in the accompanying claims

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Referring toFIG. 1, a system100for transmitting data packets may include an external network112that may include a computer system114and the Internet116. For illustrative purposes a single computer system (i.e., computer system114) is included in external network112, however, two or more computer systems and/or other network devices (e.g., routers, switches, etc.) and networks (e.g., local area networks (LAN), wide area networks (WAN), etc.) may be included in external network12.

In this embodiment, system100may include an internal network118that may include computer systems, network devices, and networks that are separate from external network112. For example, internal network118may represent a network used by an entity such as a business, an educational institution, and the like. Internal network118may include a security device120(e.g., a switch, a router, a computer system, etc.) that provides a level of security (e.g., enforces security policies) to the internal network118. For example, security device120may monitor inbound (and outbound) data for viruses and/or other types of undesirable data. By monitoring inbound data packet traffic, network security device120may reduce the probability of a virus (or other type of undesirable data) from being received at computer system122, computer system124and/or computer system126(or other type of device connected within internal network118).

To enforce security policies, security device120may include a security processor130that may be tasked to monitor the content of inbound data packets. Security processor130may include one input/output (I/O) port132for receiving inbound data packets and another I/O port134for appropriately passing inbound data packets within internal network118(e.g., passing packets to computer system122). Security processor130may be implemented as a single processor or multiple processors. For example, security processor130may include one or more general processors (e.g., a microprocessor) and/or one or more specialized devices (e.g., a co-processor or an application specific integrated circuit (ASIC)). In some embodiments security processor130may be implemented as a monolithic structure (e.g., a single integrated circuit), or, in other embodiments, as a distributed structure. Although the exemplary embodiment shows the security processor130in the security device120, a processor or device capable of the functions described herein may be used in any type of computing device including, but not limited to, desktop computers, laptop computers, mobile phones, handheld devices, and the like.

For illustrative purposes, security device120may receive a series of data packets150. For example, computer system114may initiate sending data packet series150to computer system122via the Internet116. Prior to being delivered to computer system122, security device120may check data packet series150for a certain type of data such as viruses or other types of undesirable data. In some embodiments, security device120may be part of an intrusion detection system such as the open source network intrusion detection system available under the name Snorts.

Security processor130may include a pattern recognizer136for recognizing the data. In some embodiments, pattern recognizer136may be implemented in hardware, in software, or a combination thereof. Further, pattern recognizer136may implement one or more pattern recognition algorithms for checking data packet content of data packet series150. One such pattern recognition algorithm is a multi-pattern matching algorithm known to those of ordinary skill in the art, such as the type used in Snort® intrusion detection systems, for determining if portions of the data packets match multiple patterns of interest. Such pattern recognition algorithms may use a considerable amount of time to check the content of all of the data in a data packet series150. As other data packet series are received by security device120, the amount of time needed for checking packet content may become significant. In aggregate, the delays may cause a transmission bottleneck to appear at security device120that may reduce throughput of the device.

To reduce the time needed to check data packet content (e.g., the contents of data packet series150), security processor130may include a substring detector138. Substring detector138provides a preliminary check on data packet content. To provide this check, substring detector138attempts to detect if one or more predefined substrings may be present in the data packet content. As illustrated below, each predefined substring may be a substring (e.g., a prefix) of one or more predefined patterns of interest. By detecting one or more predefined substrings in the data packet content, substring detector138may identify one or more suspect data packets that may contain a pattern of interest (e.g., a virus or other type of undesirable data). Upon detecting one or more predefined substrings in a suspect data packet, the suspect data packet may be provided to pattern recognizer136to perform further pattern recognition of the data packet contents, for example, using multi-pattern matching. If a substring is not detected, the data packet may be eliminated from further pattern recognition processing and passed on to its destination. Alternatively, a data packet may be placed aside for further pattern recognition processing (e.g., by pattern recognizer136) at a later time. By identifying suspect data packets based upon one or more predefined substrings of predefined patterns of interest, pattern recognizer136may be more efficiently executed for recognizing the patterns of interest in the data packets. Thus, the probability of bottlenecking may be reduced and throughput may be increased.

In this embodiment, the predefined substrings used by substring detector138may be included in a substring library140that may be stored on a storage device142. Storage device142may implement one or more storage techniques (e.g., magnetic, magneto-optical disks, or optical disks, etc.) and be accessible by security device120. By being accessible by security device120, predefined substrings stored in substring library140may be provided to substring detector138. Other data may also be stored on storage device142. For example, data representative of instructions executed by security processor130to perform the operations of substring detector138, pattern recognizer136, and/or I/O ports132,134may be stored in one or more files on storage device142. Along with storing substrings, data representative of the patterns of interest and/or fingerprints of substrings as described below, may also be stored in substring library140.

Referring toFIG. 2, predefined substrings244may be produced from a plurality of patterns of interest242. For illustrative purposes, the patterns of interest242are shown as a list of desired terms and the predefined substrings244are shown as a list of substrings produced from those terms. In this example, each of the substrings244corresponds to a prefix including the first four characters of an entry in the patterns of interest242. However, in other embodiments the substring may include any portion of the pattern of interest and may include more or less characters (e.g., two characters, six characters, etc.). Rather than repeat a substring, predefined substrings244may include one entry for identical substrings. Where both the patterns of interest “intel” and “intelligent” start with the same four character substring (i.e., “inte”), for example, the predefined substrings244may include one entry of “inte”.

In the illustrated embodiment, the patterns of interest242and the substrings244are formed by ASCII characters. However, other types of data may be used to produce substrings for searching the contents of data packets. For example, numerical data (e.g., binary numbers, decimal numbers, hexadecimal numbers, etc.), graphical data, and the like may be used to produce substrings and to search packet content.

In some embodiments, the predefined substrings of the patterns of interest may be processed to produce a plurality of predefined fingerprints246prior to being used for searching packet content. In this embodiment, a fingerprint may be computed for each of the pattern substrings244obtained for the patterns of interest242. In general, fingerprinting is an algorithmic operation that may transform a pattern of one length (W) into a pattern of a shorter length (F), wherein F<W. While the fingerprint of a substring may have a shorter length, the computed fingerprint has a relatively small probability of matching the fingerprint computed for a different substring (known as collision avoidance). Storing smaller sized fingerprints may conserve storage space in comparison to storing the entire substrings. Fingerprinting techniques known to those skilled in the art may be used to compute the predefined fingerprints. One example of a known fingerprinting technique that may be used is fingerprinting by random polynomials. According to this technique, randomly chosen irreducible polynomials may be used to fingerprint bit-strings. Such a technique is described in greater detail in “Fingerprinting by Random Polynomials”, M. Rabin, Technical Report TR-15-81, Harvard University, Department of Computer Science, 1981.

The computed fingerprints246of the substrings244may be stored, for example, in a lookup table. A substring table may be stored in a memory (e.g., volatile, nonvolatile, etc.) such that entries of the table may be accessed by security processor130and compared to the fingerprints computed for the content of one or more data packets. For example, the memory may include random access memory (RAM), read-only memory (ROM), static RAM (SRAM), and/or other type or volatile or nonvolatile memory. Other data structures may also be used to store the predefined fingerprints. Predefined fingerprints may also be stored in a substring library (e.g. substring library140in storage device142shownFIG. 1). Although the illustrated embodiment shows predefined fingerprints246for substrings244associated with one group of patterns of interest242, a substring library may include predefined fingerprints for multiple groups of patterns of interest.

Referring toFIG. 3, one embodiment of substring detection in an input data string is illustrated. In the illustrated embodiment, the input string includes contents of a data packet series350, for example, the packet payload. In particular, data packet1contains a string “intelato” while data packet2contains a string “nceelect” and data packet N contains a string “antintel”. To determine if one or more of the substrings associated with patterns of interest (e.g., substrings244inFIG. 2) match the packet content, substring detector338may compute fingerprints for one or more portions of the input string (e.g., the packet content) and may compare the computed fingerprints to the predefined fingerprints346(e.g., to the entries in a lookup table). In one embodiment, a portion of the input string indicated by bracket352may be read to compute a fingerprint. The number of characters in the portion of the input string, as indicated by bracket352, may match the number of characters included in each predefined substring for a valid comparison of fingerprints. In the illustrated embodiment, for example, the portion of the input string includes four characters in the data packet1(e.g., “inte”), and each of the substrings (e.g., substrings244) used to compute the predefined fingerprints346includes four characters.

In other embodiments, however, the size of the substrings and portions of the input string may include more or less characters (e.g., two characters, six characters, etc.). In other embodiments, a substring detection operation may read portions of different sizes from the input string depending on the size of the predefined substrings. For example, four character string portions may be read from a data packet (and corresponding fingerprints computed) for comparing with predefined fingerprints computed from four character predefined substrings. Six character portions may also be read from a data packet (and corresponding fingerprints computed) for comparing with predefined fingerprints computed from six character predefined substrings.

In one embodiment, data packet1may be examined for substrings and data packets2and N may then be sequentially examined for the substrings. In other embodiments, one or more data packets may be skipped. For example, after examining data packet1, data packet2may be skipped and data packet N may be examined. The contents of data packet2may or may not be examined at a later time. In another embodiment, two or more of the data packets may be examined in parallel. For example, data packets1,2and3may be examined simultaneously to reduce processing time.

The input strings (e.g., data packets) examined may also be of variable length. For example, the data packets may be capable of storing more or less than the eight characters stored in each of data packets1,2and N. In other embodiments, input strings may be provided as a relatively continuous stream of characters and may not be segmented into packets. In still another embodiment, input strings may be included in a stream of fixed or variable length packets.

Substring detector338may compute a fingerprint of the portion of the input string and may compare the computed fingerprint to the predefined fingerprints346. For example, the fingerprint of the portion “inte” may be compared to each of the fingerprints F(“inte”), F(“rate”), F(“elec”), F(“sele”). If a match is detected, data packet1may be provided to pattern recognizer336for executing further pattern recognition on the contents of the packet. In this particular example, a match may be detected since the fingerprint of “inte” is present in the predefined fingerprints F(“inte”), F(“rate”), F(“elec”), F(“sele”). If no match is detected in the substring of the data packet, another portion indicated by bracket354may be accessed, for example, the next four character portion (e.g., “ntel”). The substring detector338may then compute a fingerprint for this next portion of the input string and may compare this next computed fingerprint to the predefined fingerprints346.

This process may be repeated for an entire data string (e.g., data packet1) by sliding across the data string a window of a fixed size (e.g., represented by brackets352,354) corresponding to the size of the predefined substrings (e.g., a four character sliding window is shown). In this embodiment, a window of a fixed size is slid across the data string by one character at a time such that fingerprints are computed for successive fixed-length portions of the input string and compared to the predefined fingerprints. In the exemplary embodiment where the input string is a data packet, the fixed size of the window may correspond to a fixed number of bytes in a packet payload and the window may slide by one byte at a time.

Referring toFIGS. 4-6, a sliding window of a fixed size may also be slid across an input string by more than one character at a time. The fixed size (W) of the window may be greater than the slide (S), where W>S>1. InFIG. 4, for example, a four character sliding window (W=4) is sliding across an input string450(e.g., “bintelat . . . x”) with a slide of two characters (S=2). Bracket452indicates a first position of the window relative to the input string450and bracket454represents a second position of the window relative to the input string450. As mentioned above, a fingerprinting operation may be performed over the window contents as the window slides across the input string. In an exemplary embodiment where the input string450is a packet payload, the fixed window size (W) and the slide (S) may be a number of bytes (e.g., W=4 bytes and S=2 bytes). By sliding the window by more than one character, the substring detection process may be accelerated.

When the window is sliding by more than one character at a time, the predefined fingerprints446may include fingerprints of portions of the substrings in addition to fingerprints of the entire substrings. Comparing the computed fingerprints to fingerprints of portions of the substring prevents patterns from being missed when sliding the window by more than one character.

As shown inFIG. 5, for example, a predefined fingerprint table546may be populated with fingerprints of the substrings (e.g., F(inte)) and fingerprints of augmented portions of the substrings (e.g., F(*int)). Augmented portions of the substrings include a portion of the substring combined with other possible characters that may be used in an input string. In an embodiment where ASCII characters are used, for example, the portion of the substring (e.g., “int”) may be combined with each of the ASCII characters to form augmented portions (e.g., “*int” where * denotes each of the possible 256 ASCII characters). In the illustrated embodiment where the characters are characters in the alphabet, the augmented portions of the substring “inte” may include “aint,” “bint,” “cint,” “dint,” . . . “zint.”

The number of additional characters to be combined with substring portions to form augmented substring portions depends on the slide (S) of the window having the fixed length (W). In particular, the augmented substring portions may include one to S−1 upfront characters combined with the appropriately shortened substring. Where the slide (S) is two (2) characters, therefore, the augmented substring portions include substring portions with only one (1) upfront character (e.g., “*int” where * represents a character). If the slide (S) is three (3) characters, the augmented substring portions may include substring portions with one (1) additional character (e.g., “*int”) and substring portions with two (2) additional characters (e.g., “*#in” where * and # represent any possible character). If the slide (S) is four (4) characters, the augmented substring portions may include substring portions with one (1) additional character (e.g., “*int”), substring portions with two (2) additional characters (e.g., “*#in”), and substring portions with three (3) additional characters (e.g., “*#$i” where *, # and $ represent any possible character). The predefined fingerprint table546may thus be populated by performing a fingerprinting operation over the predefined substrings of each pattern and over the possible augmented portions and storing the results in a lookup table.

During substring detection, computed fingerprints of portions of the input string450corresponding to the sliding window may be compared to each of the predefined fingerprints of substrings and predefined fingerprints of augmented substrings. As shown inFIG. 4, the sliding window indicated by bracket452contains the string portion “bint” and after sliding two characters, the sliding window indicated by bracket454contains the string portion “ntel.” Because the sliding window slides by two characters, the sliding window never contains the string portion “inte.” If the predefined fingerprints446only included the predefined fingerprint F(inte), the substring “inte” would not be detected. The computed fingerprint for the string portion “bint,” however, would match a predefined fingerprint “F(bint)” for the augmented substring portion “bint.” Because “bint” is one of the augmented substring portions (i.e., “*int”) created from the substring “inte,” a match with the predefined fingerprint “F(bint)” is considered a match with the substring “inte.”

In an alternative embodiment, shown inFIG. 6, multiple tables646a,646bof predefined fingerprints may include fingerprints of substrings and fingerprints of shortened portions of substrings. The tables646a,646bmay each store predefined fingerprints of a particular length. The shortened substring portions (e.g., in table646b) may be used to prevent missing substrings instead of using the augmented substring portions shown inFIG. 5. The tables may include tables of substrings and shortened substring portions decreasing in length from the length W of the fixed window to the length W−S+1. In the illustrated embodiment where the sliding window and substrings have a length (W) of four (4) characters and the slide (S) is two (2) characters, table646aincludes substrings of four characters (e.g., length of W) and table646bincludes shortened substring portions of three characters (e.g., W−S+1 characters). If the slide (S) is three (3) characters, another table may include shortened substring portions of two (2) characters. By using multiple tables of smaller sizes, the predefined fingerprints to be stored for use in substring detection may be further compressed and the memory footprint required by the lookup tables may be further reduced.

During substring detection, computed fingerprints of portions of the input string440corresponding to the sliding window may be compared to the tables646aincluding predefined fingerprints of the substrings. Predefined fingerprints of one or more subsets of the sliding window may be computed for comparison to the tables646bincluding fingerprints of shortened substring portions. The subset(s) of the sliding window includes the corresponding portion of the string without the first one to S−1 characters. InFIG. 4, for example, when the window is in the first position indicated by bracket450, a fingerprint for the subset “int” is computed and matched to the predefined fingerprint F(int) in table646bfor the shortened portion “int” of the substring “inte.” Fingerprinting algorithms known to those skilled in the art allow fingerprints of a subset (e.g., F(int)) of a string portion to be computed by subtraction from the fingerprint computed for the string portion (e.g., F(inte)). Thus, the fingerprints for the subset of the sliding window may be computed with operations of relatively low complexity.

Although the illustrated embodiments show a limited number of patterns of interest and predefined substrings of those patterns, substring detection may be used with other numbers of patterns. In one example, a sliding window of W=8 and S=2 may be used to detect about 500 patterns with a fingerprint table size of about 3.32 KB. This example of substring detection may be capable of eliminating over 80% of the input string that would have otherwise been processed using a multi-pattern matching algorithm.

Sliding windows that slide by more than one character at a time may also be used in substring detection without computing fingerprints. The predefined substrings and portions of the predefined substrings may be stored in the lookup tables without computing fingerprints. The portions of the input strings corresponding to the sliding windows may then be compared directly to the predefined substrings and portions of the predefined substrings.

Referring toFIG. 7, flowchart700illustrates one method of composing predefined fingerprints to be used in substring detection. The operations of this method of composing predefined fingerprints may be executed by security processor130, substring detector138, and/or a computer system or other type of instruction executing device. The method of composing predefined fingerprints may include receiving702patterns of interest. As shown inFIG. 2and discussed above, patterns of interest242may include a list of terms of interest. The method of composing predefined fingerprints may also include producing704substrings of the patterns of interest. As shown inFIG. 2and discussed above, substrings244may include a list of substrings derived from the patterns of interest242. The substrings may also include substring portions, such as the augmented substring portions or the shortened substring portions described above.

The method of composing predefined fingerprints may also include computing706fingerprints for each substring and if applicable, the augmented substring portions and/or the shortened substring portions. As mentioned above, fingerprinting techniques known to those skilled in the art, such as fingerprinting by random polynomials, may be implemented for computing the fingerprints. The method of composing predefined fingerprints may further include storing708the predefined fingerprints, for example, in a lookup table. The predefined fingerprints (e.g., lookup tables) may be physically stored on a storage device such as storage device142and/or in a memory (e.g., volatile memory, nonvolatile memory, etc.).

Referring toFIG. 8, a flowchart800illustrates one method of detecting substrings in a data string. The operations of this method may be executed by security processor130, substring detector138, and/or a computer system or other type of instruction executing device. This method of detecting substrings may include producing802a fingerprint of a portion of an input data string. For example, the portion of the input string may include the portion corresponding to the location of the sliding window relative to the data packet content (e.g. the four character portion indicated by bracket352inFIG. 3). The fingerprint of the portion of the input string may be produced by computing the fingerprint for the portion as described above. Producing the fingerprint of the portion of the input string may also include computing a fingerprint of a subset of the sliding window as described above.

The method of detecting substrings may also include comparing804the computed fingerprints with one or more predefined fingerprints. In some embodiments, the predefined fingerprint(s) may include one or more lookup tables of predefined fingerprints. Comparing the fingerprints, a match806may be detected that indicates the substring associated with the predefined fingerprint is included in the portion of the input string associated with the computed fingerprint. If a match is detected, the method of detecting substrings may include initiating808pattern recognition processing on a data string (e.g., the contents of a data packet) that includes the substring. The pattern recognition processing may include processing using a multi-pattern matching algorithm as described above. After initiating pattern recognition processing, the method may be repeated for another input string or may continue to process subsequent portions of the same input string.

If a match is not detected, the method may include determining810if there is another subsequent portion of the input string to be processed. If the method uses a sliding window, for example, the method may determine if the sliding window is able to move (e.g., by one or more characters) to a subsequent location within the input string. If there is a subsequent portion to be processed, the method may then be repeated by producing802a fingerprint of the subsequent portion. As illustrated inFIG. 3, for example, a first portion indicated by bracket352may include four characters (e.g., “int”). After determining if one or more predefined substrings may be present in the first portion, a four character second portion indicated by bracket354that is right shifted by one character (e.g., “ntel”) may be examined. If the input string does not contain any further substrings to be processed, the substring detection processing of the string may be finished812.

One or more of the operations associated with flowchart700and/or flowchart800may be performed by one or more programmable processors (e.g., a microprocessor, an ASIC, etc.) such as security processor130executing a computer program. The execution of one or more computer programs may include operating on input data (e.g., data provided from a memory and/or storage device, etc.) and generating output (e.g., sending data to a computer system, etc.). The operations may also be performed by a processor implemented as special purpose logic circuitry (e.g., an FPGA (field programmable gate array), an ASIC (application-specific integrated circuit), etc.).

Operation execution may also be executed by digital electronic circuitry, or in computer hardware, firmware, software, or in combinations of them. The operations described in flowchart700and/or flowchart800may be implemented as a computer program product, e.g., a computer program tangibly embodied in an information carrier, e.g., in a machine-readable storage device (e.g., RAM, ROM, hard-drive, CD-ROM, etc.) or in a propagated signal. The computer program product may be executed by or control the operation of, data processing apparatus, e.g., a programmable processor, a computer, or multiple computers. A computer program may be written in one or more forms of programming languages, including compiled or interpreted languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program may be deployed to be executed on one computing device (e.g., controller, computer system, etc.) or on multiple computing devices (e.g., multiple controllers) at one site or distributed across multiple sites and interconnected by a communication network.

While the substring detection is described above in the context of network protection, other types of data such as DNA sequences may be searched using substring detection. A substring detection method may also be used in any computing device including, but not limited to, desktop computers, laptop computers, handheld devices, and mobile phones. A substring detection method may also be used in other devices, such as a bio-sequence analyzer, that carry out complex pattern matching.

Referring toFIG. 9, substring detection, consistent with embodiments of the present invention described above, may be implemented in a communications system900. The communications system900may include one or more switch cards910, one or more line cards920, and one or more control cards940. The switch card(s)910may be representative of an Advanced Switching Interconnect (ASI) fabric. The switch card(s)910may include ASI switch components912that control switching of communications between various line cards920of the communication system900. The switch card(s)910may also include other components (not shown), such as a central processing unit (CPU), a memory, and a storage medium, (e.g., a nonvolatile memory device) that stores one or more software components.

The line card(s)920may be coupled to switch card910via a serial interconnect. The line card(s)920may include a local ASI switch component922that is linked to local framer/media access control (MAC)/physical layer (PHY) component(s)924, NPU(s)926, and/or CPU(s)928. The framer/MAC/PHY component(s)924may be used to connect the line card(s)920to other locations via an I/O data link and may also be coupled directly to ASI line card switch component922, for example, via an ASI link. The line card(s)920may also include memory and/or storage components (not shown) coupled to the CPU928. The line card(s)920may further include a security processor930capable of supporting the NPU926by performing substring detection. The security processor930may perform substring detection before further pattern recognition processing performed by security processor930or NPU926. Alternatively or additionally, the switch card(s)910may include a security processor930ato perform the substring detection and/or further pattern recognition.

The control card(s)940may include a CPU942coupled between a memory944and a storage946. The switch card(s)910, line card(s)920and control card(s)940may be implemented in modular systems that employ serial-based interconnect fabrics, such as PCI Express™ components. One example of such modular communication systems includes Advanced Telecommunications Computing Architecture (AdvancedTCA) systems.

Accordingly, an apparatus, consistent with one embodiment, may include an integrated circuit configured to produce a fingerprint of at least one portion of an input data string, to compare the fingerprint of the portion of the data string to at least one predefined fingerprint for a predefined substring, and to initiate pattern recognition processing on the data string if the fingerprints match. The predefined substring includes a portion of a predefined pattern of interest.

A method, consistent with one embodiment, may include receiving at least one portion of an input string of data; producing a fingerprint of the portion of the input string of data; comparing the fingerprint of the portion of the string of data to at least one predefined fingerprint of a predefined substring, wherein the predefined substring includes a portion of at least one predefined string; and if the fingerprints match, initiating pattern recognition on the input string of data.

A system, consistent with a further embodiment, may include a switch fabric configured to route data packets and a plurality of line cards coupled to the switch fabric and configured to receive data packets. At least one of the line cards may include a security processor configured to produce a fingerprint of at least one portion of an input string from at least one of the data packets, to compare the fingerprint of the portion of the data string to at least one predefined fingerprint for a predefined substring, and to initiate pattern recognition processing on the data string if the fingerprints match. The predefined substring includes a portion of a predefined pattern of interest.

Another method consistent with an embodiment of the present invention may include sliding a window of a fixed length across an input string of data to obtain successive portions of the input string of data, wherein the sliding window slides across the input string by more than one character at a time; comparing the portions of the string of data to a plurality of predefined substrings of predefined patterns of interest and to portions of the predefined substrings; and if any one of the portions match, initiating pattern recognition on the input string of data.