Abstract:
IP networks carry packets that consist of headers and payloads. Typical traffic analysis systems at layer 3 process packet headers in order to obtain as much information about the traffic as possible. However, performing of deep packet analysis requires the processing of packet payloads as well. Another important requirement of layer 3 processing is the need to process the payloads at wire speeds. A system and method for deep packet inspection at layer 3 involves (a) an approach for packet payload processing; (b) accounting for out of order arrival of packets; (c) an approach for partial match analysis so as to be able to analyze the traffic flows when only partial information is available; and (d) an approach for effective payload processing for attempting to achieve wire speed processing.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to traffic analysis in general, more particularly, analysis of IP packets. Still more particularly, the present invention is related to a system and method for deep packet inspection at layer 3. 
       BACKGROUND OF THE INVENTION 
       [0002]    Traffic analysis involves processing of network traffic at various network elements in a network and IP network traffic analysis is based on the analysis of IP packets. An IP packet consists of a header and a payload: header further comprising of source and destination IP addresses, and source and destination port numbers; payload comprises of application data. Typical IP traffic analysis is performed at two levels: layer 3 level and layer 7 level. Layer 7 level of traffic analysis is at application layer level leading to the availability of application specific information for deeper analysis. Specifically, at this level, the IP packets are used to construct application content allowing for the detailed analysis. On the other hand, the layer 3 analysis is based on the analysis of only packets without the knowledge of the applications involved and this provides limited opportunities for deep packet analysis. 
         [0003]    There are multiple reasons why it is practically required to undertake deep packet analysis at layer 3: Consider an enterprise scenario; within the enterprise network, there is a need for undertaking fine grained bandwidth management and admission control. This is achieved by deep packet inspection. Further, such a deep packet inspection at layer 3 could be a front-end for an intrusion detection system at layer 7. And, finally, the deep packet analysis at layer 3 gives an opportunity for processing at wire speeds. 
       DESCRIPTION OF RELATED ART 
       [0004]    U.S. Pat. No. 5,787,253 to McCreery; Timothy David (Lafayette, Calif.), Zabetian; Mahboud (Walnut Creek, Calif.) for “Apparatus and method of analyzing internet activity” (issued on Jul. 28, 1998 and assigned to The AG Group (Walnut Creek, Calif.)) describes an apparatus for analyzing Internet activity. The packet data is decoded at the internet protocol layer to provide information such as timing and sequencing data regarding the exchange of packets between nodes and the packet data for exchanges between multiple nodes may be recompiled into concatenated raw transaction data which may be coherently stored in a raw transaction data buffer. An application level protocol translator translates the raw transaction data and stores the data in a translated transaction data buffer. The translated data provides high level information regarding the transactions between nodes which is used to monitor or compile statistics regarding network or internetwork activity. 
         [0005]    U.S. Pat. No. 6,591,299 to Riddle; Guy (Los Gatos, Calif.), Packer; Robert L. (Rancho Santa Fe, Calif.), Hill; Mark (Los Altos, Calif.) for “Method for automatically classifying traffic with enhanced hierarchy in a packet communications network” (issued on U.S. Pat. No. 6,591,299 and assigned to Packeteer, Inc. (Cupertino, Calif.)) describes a a method for automatically classifying packet flows for use in allocating bandwidth resources and the like by a rule of assignment of a service level in a packet communication network. The method comprises applying individual instances of traffic classification paradigms to packet network flows based on selectable information obtained from a plurality of layers to define a characteristic class, then mapping the flow to the defined traffic class. 
         [0006]    U.S. Pat. No. 6,789,116 to Sarkissian; Haig A. (San Antonio, Tex.), Dietz; Russell S. (San Jose, Calif.), Koppenhaver; Andrew A. (Littleton, Colo.) for “State processor for pattern matching in a network monitor device” (issued on Sep. 7, 2004 and assigned to Sarkissian; Haig A. (San Antonio, Tex.), Dietz; Russell S. (San Jose, Calif.), Koppenhaver; Andrew A. (Littleton, Colo.)) describes a processor for processing contents of packets passing through a connection point on a computer network. The processor includes a searching apparatus having one or more comparators for searching for a reference string in the contents of a packet, and processes contents of all packets passing through the connection point in real time. 
         [0007]    U.S. Pat. No. 7,017,186 to Day; Christopher W. (Biscayne Park, Fla.) for “Intrusion detection system using self-organizing clusters” (issued on Mar. 21, 2006 and assigned to Steelcloud, Inc. (Herndon, Va.)) describes a system that includes a vector builder that can be configured to generate multi-dimensional vectors from selected features of the pre-defined packet fields and to use a produced a self-organized map of clusters to detect anomalous correlations. 
         [0008]    U.S. Pat. No. 7,143,442 to Scarfe; Richard T (Felixstowe, GB), Kirkham; Edmund A. (Ipswich, GB) for “System and method of detecting events” (issued on Nov. 28, 2006 and assigned to British Telecommunications (London, GB)) describes a system and method of detecting events, and is suitable particularly for detecting uncommon behaviour of network devices by firewall systems. 
         [0009]    U.S. Pat. Application No. 20060212942 dated Sep. 21, 2006 and titled “Semantically-aware network intrusion signature generator” by Barford; Paul Robert; (Madison, Wis.); Giffin; Jonathon Thomas; (Madison, Wis.); Jha; Somesh; (Madison, Wis.); Yegneswaran; Vinod Trivandrum; (Foster City, Calif.) describes an automatic technique for generating signatures for malicious network traffic by performing a cluster analysis of known malicious traffic to create a signature in the form of a state machine. 
         [0010]    U.S. Pat. Application No. 20060239219 dated Oct. 26, 2006 and titled “Application signature based traffic classification” by Haffner; Patrick Guy; (Atlantic Highlands, N.J.) Sen; Subhabrata; (New Providence, N.J.); Spatscheck; Oliver; (Randolph, N.J.); Wang; Dongmei; (Kearny, N.J.) describes a method for identifying traffic to an application including the steps of monitoring communication traffic in a network, identifying data from communication traffic content, and constructing a model for mapping the communication traffic for an application derived from data identified from the communication traffic content. 
         [0011]    “A Finite-State-Machine based string matching system for Intrusion Detection on High-Speed Networks” by Tripp, G. (appeared in the Proceedings of the 14 th EICAR annual conference Saint Julians, Malta, 30 April-3 May 2005) describes a finite state machine approach for string matching within high-speed network intrusion detection systems. 
         [0012]    “Applications of Finite State Machines General Decomposition Method with Optimization” by Pruteanu, C., Galea, D., and Haba, C. (appeared in the Proceedings of 8th International Conference on Development and Application Systems, Suceava, Romania, May 25-27, 2006) describes the General Decomposition Method of finite state machines (FSMs) based approach to divide a single FSM into a network of interacting FSMs by reducing each submachine&#39;s complexity while attempting to minimize the number of the obtained submachines. 
         [0013]    The known systems do not address the various issues related to the deep packet inspection at layer 3 that accounts for application level semantics in the packet analysis. The present invention provides an effective system and method to perform deep packet inspection with the application level semantics described in the form finite state machines at wire speeds. 
       SUMMARY OF THE INVENTION 
       [0014]    The primary objective of the invention is to perform deep packet inspection at layer 3 based on incoming network packets to semantically characterize the packet flows. 
         [0015]    One aspect of the invention is to enable the describing of semantics in the form of a set of finite state machines. 
         [0016]    Another aspect of the invention is to account for a set of key semantic concepts, temporal ordering among the set of key semantic concepts, spatial relationship among the set of key concepts, priorities of the key concepts of the set of key concepts, and mandatory/optional key-concepts. 
         [0017]    Yet another aspect of the invention is to perform the out of order traversal of the set of finite state machines. 
         [0018]    Another aspect of the invention is to automatically convert the set of finite state machines into a set of hierarchical sequence machines. 
         [0019]    Yet another aspect of the invention is to multi-level indexing of the hierarchical sequence machines. 
         [0020]    Another aspect of the invention is to match a packet stream based on multiple hierarchies. 
         [0021]    Yet another aspect of the invention is to support approximate matching when complete information is not available. 
         [0022]    Another aspect of the invention is to label an incoming network flow based on the best matched finite state machine. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0023]      FIG. 1  depicts an overview of Network Architecture of Deep Packet Inspect at Layer 3 (DPIL3) System. 
           [0024]      FIG. 1   a  depicts another Illustrative Network Architecture of DPIL3 System. 
           [0025]      FIG. 2  provides an overview of System Architecture of DPIL3 System. 
           [0026]      FIG. 3  depicts an Illustrative Domain-Specific Template. 
           [0027]      FIG. 3   a  depicts an Illustrative Finite State Machine (FSM). 
           [0028]      FIG. 4  depicts an illustrative Packet Stream Analysis. 
           [0029]      FIG. 5  depicts an illustrative Multi-Level Indexing. 
           [0030]      FIG. 6  provides an approach for matching based on Multiple Hierarchies. 
           [0031]      FIG. 6   a  provides an approach for Flow Labeling based on Matched FSM. 
           [0032]      FIG. 7  provides an approach for matching based on Multi-Level Indexes of Multiple Hierarchies. 
           [0033]      FIG. 7   a  provides an approach for Location based Distance Measure. 
           [0034]      FIG. 7   b  provides an approach for Approximate Matching. 
           [0035]      FIG. 8  provides an approach for Construction of Sequence Machines. 
           [0036]      FIG. 8   a  provides additional steps in the Construction of Sequence Machines. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0037]    Network traffic analysis is performed for a variety of reasons: intrusion detection, viruses and malicious content detection, to address compliance and regulatory requirements, admission control and resource (say, bandwidth) allocation, traffic filtering, and traffic grooming. Some of these requirements demand real-time, wire speed processing while the offline processing is adequate for the other requirements. The more detailed is the processing, the more difficult it is to achieve wire speed processing: in such cases, typically, it pushed to offline processing (even though the real time processing is more beneficial). The tradeoff is between the depth of processing and closeness to wire speed processing. Hence, the challenge is to reach good depth at wire line speeds. One of the ways to achieve this is to process packets at layer 3: This gives an opportunity to process the network traffic as soon as possible. However, packet processing at layer 3 poses its own challenges such as out of order arrival and lack of explicit flow information. 
         [0038]      FIG. 1  depicts an overview of Network Architecture of Deep Packet Inspect at Layer 3 (DPIL3) System. In this enterprise scenario, multiple local area networks that are IP networks ( 100 ,  110 ) are connected to an enterprise-wide IP network ( 120 ) through a network element ( 130 ). The requirement, here, is to perform traffic analysis at the traffic aggregation points in the network and the DPIL3 system ( 140 ) is positioned well to receive all of the traffic through the network element. As depicted, in one of the embodiments, the DPIL3 system is part of the network element and controls the traffic flow as appropriate. In another embodiment, the DPIL3 system performs traffic monitoring functionality and labels flows in real time for other applications to use this information as appropriate. 
         [0039]      FIG. 1   a  depicts another illustrative Network Architecture of DPIL3 System. In this ISP scenario, multiple access networks ( 150 ,  160 ) are connected to the external IP network ( 170 ) through a network element ( 180 ). The DPIL3 system ( 190 ) is part of the network element to monitor and/or control network traffic as appropriate. 
         [0040]      FIG. 2  provides an overview of System Architecture of DPIL3 System. The network traffic is obtained in the form of IP packets ( 200 ) and are segregated based on the implicit flow id associated with the packets ( 205 ). Note that the DPIL3 system ( 210 ) processes individual packets as they arrive and does not require the packets related to a session to be pooled up before processing. An incoming packet is processed based on a set of Finite State Machines (FSMs) ( 215 ). These validated FSMs are processed by Sequence Machine Construction subsystem ( 220 ) to generate a set of sequence machines ( 225 ). The incoming packet is analyzed using a set of multi-level sequence machines by performing appropriate traversals ( 230 ) and accounting for the out of order arrival of packets ( 235 ). In order to be effective and be able to achieve depth of processing at wire speeds, a partial match analysis is performed ( 240 ). Based on the match results, an appropriate characterization of a flow is achieved ( 245 ). Traffic logs ( 250 ) contain the results of the deep packet processing at layer 3. In order to ensure the suitability of FSMs, the FSMs are validated using a stream of packets ( 255 ) based on application-specific analysis ( 260 ) and domain-specific analysis ( 265 ). 
         [0041]      FIG. 3  depicts an illustrative Domain-Specific Template. The template is required to provide information about (a) key-concepts; (b) priorities associated with the key-concepts; (c) mandatory and optional key-concepts; (d) temporal ordering; and (e) spatial information. For example, the key-concept “Current Assets” is associated with the spatial information of (2,0), is of priority 0.8, and is a mandatory key-concept (1). Specifically, any key-concept is associated with the following attributes: (a) Location attribute that is represented as a pair: &lt;X, Y&gt;; (b) Priority attribute that is defined as a value between 0 and 1 with values close to 0 depicting lower priority and values close to 1 depicted higher priority.; and (c) Mandatory-optional attribute this is a binary attribute with the value of 0 indicating that the key-concept is optional and the value of  1  indicating that the key-concept is mandatory. 
         [0042]      FIG. 3   a  depicts an illustrative FSM. Note that the FSM captures all the information associated with each of the key-concepts. 
         [0043]      FIG. 4  depicts an illustrative packet stream analysis. The packet stream analysis is performed at multiple stages: Byte stage analysis ( 400 ), based on a byte stream, helps in efficient identification of tokens leading to the generation of a token stream. A typical byte stage analysis uses a byte hierarchy as depicted in  405 . Note that each path ( 410 ) through the byte hierarchy depicts a byte sequence leading to a token (Tj). The next stage in the packet stream analysis is token stage analysis ( 415 ). This analysis is based on a token stream and helps in the efficient identification of sub-FSM identifiers. A typical token-stage analysis uses a token hierarchy as depicted in  420 . Note that each path ( 425 ) through the token hierarchy depicts a token sequence leading to a sub-FSM identifier (Sj). The sub-FSM identifiers are also alternatively called as meta-tokens. Observe that the tokens part of a token hierarchy are depicted using the notation Tij*, wherever appropriate, indicating zero or more occurrences of the token Tij. This powerful representation helps in depicting FSMs using multiple sequences (such as Byte sequences, Token sequences, one or more Sub-FSM sequences). The next stage in the analysis is a sub-FSM stage and there could be multiple further stages each of which is sub-FSM based and building on the previous analyses. The sub-FSM stage analysis ( 430 ) is based on a sub-FSM stream and uses a sub-FSM hierarchy as depicted in  435 . Note that each path ( 440 ) through the sub-FSM hierarchy depicts a sub-FSM sequence leading to either FSM identifier (F0) or a sub-FSM identifier. Again, observe that the sub-FSM identifiers part of a sub-FSM hierarchy are depicted using the notation Sij*, wherever appropriate, indicating zero or more occurrences of the sub-FSM identifier Sij. This process is continued until all the token/sub-FSM identifiers are resolved leading to the FSM identifiers. Note FSM identifiers are also alternatively called as labels. 
         [0044]      FIG. 5  depicts an illustrative Multi-Level Indexing. An indexing scheme is essential to process the incoming packets at wire speed. The overall objective of the processing is to analyze the packets with respect to a set of FSMs. In turn, these FSMs are converted into a set of hierarchically related sequences (Byte sequences, Token sequences, Sub-FSM (meta-token) sequences, Sub-FSM (meta-token) sequences, . . . ) for reducing the complexity involved in “out of order” traversal of the FSMs. Another opportunity to improve the performance further is to index each of these hierarchical sequences. Consider a hierarchical sequence depicted in  500 . Root NO has six child nodes ( 505 ) and these nodes are arranged in the order of their probability of occurrence leading to efficient sequence matching: the indexing of these child nodes is depicted by Root Index I1( 510 ) (H(I)L(0)—Indexes of Ith hierarchy at level 0). The hierarchical sequences are indexed level by level, and at each level, several indexes are maintained such as Index I10 and Index I11. Another illustration of indexing is of the nodes at level 3 ( 515 ) (H(I)L(3)) is depicted in  520 . 
         [0045]      FIG. 6  provides a detailed overview of packet analysis based on Multiple Hierarchies. Initially, the packet is input to byte stream analysis ( 600 ) and the bytes obtained from the packet are matched with the bytes that are part of the hierarchically related byte sequences using the level-wise indexes ( 605 ). Note that the matching performed here is one of exact matching ( 610 ). The resulting token stream is input to token stream analysis ( 615 ). This analysis is based on the level-wise indexed hierarchically related token sequences ( 620 ). In order to account for out of order arrivals and to achieve effective matching, a partial matching is performed ( 625 ). The output of the partial match analysis is a stream of sub-FSM identifiers, also called as meta-tokens. The next stage in the packet analysis is meta-token stream analysis ( 630 ) and is based on two inputs: token stream and meta-token stream. This analysis makes use of a level-wise indexed meta-token hierarchy (hierarchically related sub-FSM identifiers) ( 635 ) and a partial match is performed to achieve effective matching ( 640 ). The meta-token stream analysis is performed in several stages to finally resolve all meta-tokens to identify matched FSMs. Note that the further stages of meta-token analyses take as input the token stream and the meta-token streams that are generated by the earlier stages of meta-token analyses ( 645 ). Each further stage takes an appropriate level-wise indexed hierarchy K ( 650 ) and performs an appropriate partial match analysis ( 655 ). Observe that any of the token analysis or meta-token analyses stages can potentially lead to the identification of FSMs. 
         [0046]      FIG. 6   a  provides an approach for Flow Labeling based on the Matched FSM. The processing is based on a stream of packets ( 660 ). The packets are grouped according to the implicit session information, say, taking into account source and destination IP addresses, and source and destination port numbers ( 662 ). The packets belonging to a session are processed together. Obtain a packet P of the packet substream of a session ( 664 ). Perform multi-level matching with respect to the byte stream associated with P using the Hierarchy 0 ( 666 ). This generates a token stream and is used to perform multi-level matching using the Hierarchy 1 ( 668 ). Continuing the processing, perform multi-level matching with respect to further meta-token streams using Hierarchies 2 to K ( 670 ). Gather the matched sequences and check whether flow labeling is possible ( 672 ). If so ( 674 ), provide an appropriate characterization of the flow related to the session ( 676 ). Otherwise, continue to process the further available packets ( 678 ). Note that as the FSM labels are based on domain and applications, the flow labels provide information about the nature of the flow supporting high level decisions based on policies. 
         [0047]      FIG. 7  provides an approach for matching based on Multi-Level indexes of Multiple Hierarchies. Obtain a packet and generate the byte stream based on the packet ( 700 ). Based on hierarchy 0 and the corresponding level-wise indexes, generate token stream ( 705 ). At this stage, the current state is as follows (a) set of Tokens (ST); (b) a set of Meta-tokens (SMT); (c) a Set of Partially traversed sequences (SPS); and (d) List of sequences associated with each of the tokens and meta-tokens ( 710 ). Here, ST depicts the tokens that are being explored to match the sequences associated with the hierarchies. In order to account for out of order arrival of packets and the distributed nature of content across multiple packets, each token is matched against at as many places within as many sequences of as many hierarchies. The tokens of a packet would remain in ST until a successful sequence matching is achieved: here, the matching is either exact or approximate. Basically, approximate matching is preferred as FSMs are generic representations. Once a match is achieved, all the tokens that are used in matching with the sequences are removed from ST. Multiple hierarchies also account for multiple sub-FSMs and each of the hierarchies lead to the identification of sub-FSM labels or, alternatively, called meta-tokens. SMT depicts a set of meta-tokens that have been successfully matched until now. These meta-tokens are used during further sequence matching to finally lead to the matched FSMs. SPS depicts the set of partially traversed sequences and as more tokens arrive and more meta-tokens get identified, an attempt is made to match these sequences to successfully match as many of them. In order to efficiently traverse multiple sequences, each token is associated with a list of partially matched sequences so that on completion of a matching of a sequence, it is easy to undo other matches that were also explored to account for out of order arrival of packets and possible incomplete information. Note that each matched token within a partially matched sequence has two location attributes: one based on what is associated with FSMs called as template location; and the second based on the location of the token within a packet called as packet location. 
         [0048]    For each token T, perform the following steps ( 715 ). Obtain the packet location Lp of T ( 720 ). Use the level-wise indexes of each of the hierarchies, and match T based on the location based distance measure ( 725 ). If T matches with one or more new sequences ( 730 ), Check and match meta-tokens based on location-based distance measure with each of these new sequences ( 735 ). If any of the partially matched sequences satisfy the approximate match criterion, add the meta-tokens corresponding to the matched sequences to the set of meta-tokens; compute also the attributes of the meta-token ( 740 ). If any of the meta-tokens correspond to the FSM identifier, output the same ( 745 ). If more matches are possible ( 750 ), proceed to Step  735 . 
         [0049]      FIG. 7   a  describes an approach for location based distance measure. Computing the attributes of a meta-token:
       Let T1, T2, . . . , be the tokens involved in deriving a meta-token MT;   Let the location attribute of T1 be &lt;X1, Y1&gt;, T2 be &lt;X2, Y2&gt;, . . . ; This location attribute is called as template-based location attribute;   Define the location attribute of MT as the set of the location attributes of the involved tokens={&lt;X1, Y1&gt;, &lt;X2, Y2&gt; . . . };   Let the priority attribute of T1 be P1, T2 be P2, . . .   Define the priority attribute of MT as the mean of P1, P2, . . . ;   Let the mandatory-optional attribute of T1 be Q1, T2 be Q2, . . .   Note that Qi is a binary value with 0 meaning optional and 1 meaning mandatory;   Let C1 be the number of Qi&#39;s each with the value of 1;   Let C0 be the number of Qj&#39;s each with the value of 0;   The mandatory-optional attribute of MT is 1 if C1&gt;C0 else 0;         
         [0060]    Computation of location based ordering:
       Location based ordering defines an ordering in general of any two meta-tokens;   Location based ordering (MT1, MT2):
           Template location of MT1={&lt;X11, Y11&gt;, &lt;X12, Y12&gt;, . . . };   Template location of MT2={&lt;X21, Y21&gt;, &lt;X22, Y22&gt;, . . . };   Packet location of MT1={&lt;A11, B11&gt;, &lt;A12, B12&gt;, . . . };   Packet location of MT2={&lt;A21, B21&gt;, &lt;A22, B22&gt;, . . . };   Take any pair P1: &lt;X1i, Y1i&gt; and &lt;X2j, Y2j&gt; and the corresponding pair
               P2: &lt;A1i, B1i&gt; and &lt;A2j, B2j&gt;;   
               the order of P1 and P2 are same   
               
 
         [0070]    Computation of Location based Distance Measure:
       Location based distance measure defines distance measure between (a) a token and a token, (b) a token and a meta-token, or (c) a meta-token and a meta-token;   Location is defined as a pair &lt;X,Y&gt; at token-level;   At meta-token level, it is defined as a set of pairs: {&lt;X1,Y1&gt;, &lt;X2,Y2&gt; . . . &gt;;   Location based Distance (T1, T2)
           Location of T1={&lt;X11, Y11&gt;, &lt;X12, Y12&gt;, . . . }   Location of T2={&lt;X21, Y21&gt;, &lt;X22, Y22&gt;, . . . }   Compute pair-wise distances, say, based on Euclidean measure;
               D11=DISTe (&lt;X11, Y11&gt;, &lt;X21, Y21&gt;)   D12=DISTe (&lt;X11, Y11&gt;, &lt;X22, Y22&gt;)   Dij=DISTe(&lt;X1i, Y1i&gt;, &lt;X2j, Y2j&gt;}   
               
           Define DIST1 as Minimum (D11, D12, . . . , Dij, . . . );       
 
         [0082]      FIG. 7   b  provides an approach approximate matching. 
         [0083]    Matching based on Location based Distance Measure
       Each token/meta-token in a sequence is associated with a set of attributes; Note that the template-based location attribute of a token is &lt;X, Y&gt; while the template-based location attribute of a meta-token is {&lt;X1, Y1&gt;, &lt;X2, Y2&gt;, . . . }   Similarly, each token obtained from a packet is associated with a location attribute &lt;A, B&gt;; This location attribute is called as packet-based location attribute;   Matched portions of a sequence to have a pair of location attributes (template-based and packet-based): {&lt;X1, Y1&gt;, &lt;X2, Y2&gt;, . . . } and {&lt;A1, B1&gt;, &lt;A2, B2&gt;, . . . };   Matching within a sequence:   On matching of a token Tp from a packet P with a token Ts from a sequence S:   Case this is the first match within S:
           Bind the packet-based location attribute &lt;A,B&gt; of Tp with Ts of S;   
           Case this is the second match within S:
           Obtain the template-based location Lt1 of the first match;   Obtain the template-based location Lt2 of the second match;   Obtain the packet-based location Lp1 of the first match;   Obtain the template-based location Lp2 of the second match;   Check to ensure that order of Lp1 and Lp2 is the same as that of Lt1 and Lt2;   Compute Dt as the distance between Lt1 and Lt2;   Compute Dp as the distance between Lp1 and Lp2;   Compute SPF of S as Dp/Dt, where SPF is Sequence Proportionality Factor;   Bind Lp2 with Ts;   
           Case S is a partially matched sequence:
           Obtain a matched token Ts1 that is nearest to Ts based on the location attribute Lt1 of Ts and the location attribute Lt2 of Ts1 (template-based);   Determine the distance Dt based on Lt1 and Lt2;   Obtain the location Lp1 of Tp and Lp2 that is bound with Ts1 (packet-based);   Determine the distance Dp based on Lp1 and Lp2;   Check if |SPF−(Dp/Dt)| is less than a pre-defined threshold;   If so, Tp matches with Ts and bind Lp1 with Ts; Update SPF;   
               
 
         [0108]    Approximate Matching of a sequence: 
         [0109]    Consider a sequence S;
       Let T1, T2, be the tokens/meta-tokens involved in S;   Let P1, P2, be the priorities associated with the tokens/meta-tokens;   Compute Ps as the sum of P1, P2, . . . ;   During matching:   Let M1, M2, . . . be the tokens/meta-tokens that match the tokens/meta-tokens of S;   Compute Pm as the sum of Pi1, Pi2, . . . associated with M1, M2, . . . ;   Declare S is approximately matched if |Ps−Pm1 is within a pre-defined threshold;       
 
         [0117]      FIG. 8  provides an approach for the Construction of Sequence Machines. 
         [0118]    Obtain the set of finite state machines (FSMs) ( 800 ). Obtain the set of tokens based on the analysis of the set of FSMs ( 805 ). Obtain the first byte of each token of the set of tokens ( 810 ). Perform frequency analysis and order the identified bytes in the non-increasing order of their frequency count ( 815 ). Make the identified bytes as child nodes of the root; Create H(0)L(0) Index; and set I to 1 ( 820 ). For each subsequent byte, obtain the list of tokens based on pre-sequences ( 825 ). Perform frequency analyses and order the identified subsequent bytes in the non-decreasing order of their count ( 830 ). Each frequency analysis identifies a set of bytes that is related to a pre-sequence; Make these bytes as the child nodes of the last node of the pre-sequence; Create H(0)L(1) indexes each based on identified set of bytes; and set I to I+1 ( 835 ). If there are more bytes ( 840 ), go to Step  825 . This leads to the creation of Token hierarchy (H0); For each sequence of H(0), traverse down, label the sequence with a Meta-Token, and compute the Meta-Token attributes ( 845 ). Note these meta-tokens are the internally generated distinct identifiers. Modify the set of FSMs to relabel self-loops (MFSMs) ( 850 ). 
         [0119]      FIG. 8   a  provides additional steps in the Construction of Sequence Machines. Obtain the set of modified finite state machines (MFSMs) and set I to 1 ( 860 ). Analyze the set of MFSMs and determine a set of Sub-SFMs such that each of these have no loops (or alternatively called as cycles) within and set J to 0 ( 865 ). If there are more sub-FSMs to be processed ( 870 ), assign meta-token to each of these sub-FSMs and Unravel the loops ( 875 ). Analyze each of the sub-FSMs and obtain a set of meta-tokens wherein each meta-token is a token or meta-token, and forms a part of First Transition/Next Transition; That is, the meta-tokens in the set of meta-tokens match on hop-distance from the start node of the sub-FSMs ( 880 ). Hop distance defines the length of a sub-path from the start node of a sub-FSM to any node in the sub-FSM. Perform frequency analyses and order the meta-tokens in the non-increasing order of their frequency count ( 885 ). Each frequency analysis identifies a set of meta-tokens which is related to a pre-sequence; Make these meta-tokens as the child nodes of the last node of the pre-sequence; Create H(I)L(J) Indexes each based on identified set of meta-tokens; and set J=J+1 ( 890 ). Replace each of the processed sub-FSMs in MFSMs with the associated meta-token or meta-token followed by star as appropriate ( 892 ). If there are more meta-tokens ( 894 ), go to Step  880 . For each sequence of H(I), traverse down, label the sequence with a Meta-Token, compute the Meta-Token attributes, and set I=I+1 ( 896 ). 
         [0120]    Thus, a system and method for deep packet inspection at layer 3 is disclosed. Although the present invention has been described particularly with reference to the figures, it will be apparent to one of the ordinary skill in the art that the present invention may appear in any number of systems that supports deep packet processing. It is further contemplated that many changes and modifications may be made by one of ordinary skill in the art without departing from the spirit and scope of the present invention.