Abstract:
An analysis system for unknown application layer protocols, which could automatically discover unknown applications existing in a network, and then obtain keywords, attribute values, status codes or type codes representing semantic meaning of each field in each type of unknown application as well as message formats, dialogue rules and status transfer relations of application layer protocols by using cluster analysis and optimal partitioning method based on hidden semi-Markov model. Unknown application analysis result could be used for flow management and safety protection of a network. The system has the following advantages: it avoids difficulties arising from manual discovery and analysis of unknown applications, and improves network management efficiency and responding speed against new types of network attacks.

Description:
BACKGROUND OF THE INVENTION 
     This is a continuation-in-part of PCT international application No. PCT/CN2009/074858, filed Nov. 9, 2009. 
     The present invention relates to the technical field of network management and network safety, and specifically relates to an analysis system for unknown application layer protocols. 
     On the Internet, apart from various applications based on common and standard application layer protocols, there are also many other kinds of non-standard protocol applications and new types of network attacks. It is a very difficult task for network managers to separate, analyze, identify and thereby to control unknown applications or attacks from massive collected data. Existing protocol analysis tools and also flow management apparatus based on application identification are only applicable to known and standard protocols but not applicable to unknown and new types of protocols, nor can they discover and analyze new types of attacks. The present invention has the following distinctive advantage: It remedies defects of network management and network safety in the technical field of network management and network safety by providing a kind of technology for automatic discovery, automatic clustering, automatic analysis and automatic identification of unknown application layer protocols. 
     BRIEF SUMMARY OF THE INVENTION 
     In view of the aforesaid disadvantages now present in the prior art, the present invention provides a kind of technology for automatic discovery, automatic clustering, automatic analysis and automatic identification of unknown application layer protocols. This kind of technology avoids the difficulty of processing massive data manually and enhances network management efficiency, so that network management efficiency can keep pace with the emergence of new types of network applications and cope with new types of network attacks. 
     The above objects are attained by the present invention as follows. 
     An automatic analysis method for unknown application layer protocols, comprising an online process for collecting unknown application layer protocols, and an offline process for analyzing the unknown application layer protocols collected; 
     The online process for collecting the unknown application layer protocols comprises: identifying each data stream at main channels, input and output ports or stream convergence points in a network and collecting the unknown application layer protocols; 
     The offline process for analyzing the unknown application layer protocols comprises specifically the following steps: 
     a. performing cluster analysis on data of the unknown application layer protocols; 
     b. searching keywords of the unknown application layer protocols; 
     c. exploring dialogue rules of the unknown application layer protocols; 
     d. analyzing message formats of the unknown application layer protocols; 
     e. estimating status transfer relations of the unknown application layer protocols; and analysis result for the application layer protocols is obtained. 
     The online process of the present invention executes application identification for each stream and records application layer data of unidentifiable streams. The offline process is activated on demand for analysis of unknown application layer protocols, and it is activated either manually or activated automatically when unknown application layer data accumulates up to a prescribed level. 
     Specifically, the process for collecting unknown application layer protocols is to establish automata or regular expressions of known applications in advance and then apply the automata or regular expressions for online identification of applications, and store unidentifiable unknown application layer data into a disk. 
     Further, the offline process for analyzing unknown application layer protocols is detailed as follows: 
     Specifically, the said step a is to extract data stream flow characteristics, character string characteristics and header information characteristics of each layer from collected unknown application layer data, and use these characteristics to form characteristic vectors for cluster analysis, and treat each resulting cluster as an unknown application. 
     Specifically, the said step b is to search protocol keywords and frequent keywords sequences from data of each unknown application by using data searching technology. 
     Specifically, the said step c is to use frequent keywords sequences of the same type of unknown application to establish a prefix tree representing dialogue rules of a respective protocol. Each string of the prefix tree represents a keyword, and each path thereof represents a type of dialogue process. 
     Specifically, the said step d is to treat application layer data of each data packet as a character string, and then perform syntactic analysis on all character strings to establish automata or regular expressions of message formats of the respective unknown application layer protocol. 
     Specifically, the said step e is to treat keywords sequences in each stream as a training cluster to estimate status transfer probability matrix of the respective unknown application layer protocol by using hidden Markov model parameter estimation, and to generate probability distribution of observed values which include keywords, character strings length and encoding format. 
     In order to use the obtained automata or regular expressions for online inspection of the respective application layer protocol, the automata or regular expressions should first be subject to validity verification which comprises specifically testing of a degree which the automata or regular expressions conform with the collected sample streams, and testing of a degree which the automata or the regular expressions reject sample streams of other application layer protocols. 
     In order to achieve normality testing, the collected sample streams could be tested by using automata or regular expressions of obtained unknown application layer protocols, so as to obtain normality distribution of all samples and normality of each sample, or discover abnormal sample streams. 
     The present invention is enabled to perform automatic analysis of unknown application layer protocols by collecting unknown application layer data, performing cluster analysis of the unknown application, searching keywords of unknown application layer protocols, exploring dialogue rules of the unknown application layer protocols, analyzing message formats of the unknown application layer protocols and estimating status transfer relations of the unknown application layer protocols. Therefore, the present invention has the following distinctive advantages: a kind of technology for automatic discovery, automatic clustering, automatic analysis and automatic identification of unknown application layer protocols is provided to avoid difficulty of processing massive data manually and enhance network management efficiency, so that network management efficiency can keep pace with the emergence of new types of network applications and network safety and precautionary measures could cope with new types of network attacks. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic view showing an integral structure of a system of the present invention. 
         FIG. 2  is a schematic view showing message formats and field partitioning in an observation sequence. 
         FIG. 3  shows a hidden semi-Markov model of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention is further described as follows with reference to the accompanying drawings. 
     1. System Configuration 
     As shown in  FIG. 1 , the present invention includes two sub-systems: a) An online sub-system; the online sub-system maintains its operation online and connects at main channels, input and output ports, or stream convergence points of a network; its application identification module uses regular expressions established in advance for application identification of every stream, while those unidentifiable original data packets would be treated as samples of unknown applications and stored in a database by an unknown application layer data collection module; b) An offline sub-system; the offline sub-system is activated when unknown application layer data accumulates up to a prescribed level; its cluster analysis module performs cluster analysis on the collected unknown application layer data; its module which performs reversed engineering on unknown application layer protocols uses an optimal partitioning method based on hidden semi-Markov model to search from a data cluster of every kind of unknown applications for their protocol keywords, message formats, dialogue rules and status transfer probability matrix; and by using results from dialogue rules analysis, Grammar Inference algorithm is then utilized to obtain automata or regular expressions used for application identification, and those automata or regular expressions are then sent back to online application identification system for application identification. 
     2. Application Identification 
     Firstly, establish regular expressions for each known application or obtain automata by using the present invention. Next, use the regular expressions or automata for online identification at beginning stage of each stream. A specific procedure is set out as follows: a) Extract and rearrange application layer data of each stream; b) Perform matching by using each regular expression of a list of regular expressions; c) Successful matching of a regular expression means that the respective stream is identified; d) Otherwise, mark that stream as “unknown”. 
     3. Collect Unknown Application Data 
     Store messages of a stream marked as “unknown” in a database according to sequential order. A two-way message sequence of each unknown stream is an observation sequence. 
     4. Perform Cluster Analysis on Data 
     Perform cluster analysis when there are enough samples in a cluster of collected unknown application observation sequences. First, obtain statistic information of each observation sequence, including: 
     Characteristic information of a stream: port number of a party accepting connection, time of stream continuity, total number of data packets transferred, total ASCII bytes, total binary bytes, statistical characteristics of lengths of the data packets, statistical characteristics of intervals of arrival time of data packets etc, in which, the statistical characteristics include: maximum value, minimum value, average value, medium value, variance, average value of stream beginning stage and average value of stream ending stage. 
     Characteristic information of load: number of ASCII bytes and binary bytes in each message, if the load is enciphered or compressed, frequent sub character trail at the beginning of a message and frequent sub character trail at the end of a message. 
     Preface information of stream: key exchange and security association information of tunnel or IPSec. 
     Use the obtained statistical information to form a characteristic vector: A=(a 1 , a 2 , . . . , a N ), and a i  is the i th  characteristics of that stream. 
     Use characteristic vectors for cluster analysis of a cluster of observation sequences; in other words, treat streams having the closest characteristic vectors as a cluster and to separate as far as possible the characteristic vectors between different clusters. The cluster analysis results in obtaining 1 or more clusters. Treat each cluster as a type of unknown application. 
     5. Model Building 
     Common message formats on the Internet include: a) Binary format: treat several bits (fixed lengths) as a field whereas each field represents an attribute, and a value taken by the bits in the field is a value of the attribute; b) Type-length-value (TLV) format: wherein a fixed byte length T represents type of attribute, a fixed byte length L represents number of bytes of an attribute value that follows, and a variable byte length V represents a value taken by attribute; c) Keyword format: use specific keywords or status codes etc. to represent semantic meanings or commands, while character strings that follow are contents; d) Pointer format: use pointer to point at a beginning position or an ending position of a field. 
     Among the above four message formats, some have fields fixed in length, and some have fields variable in length. Strings in fixed mode appear frequently in a message and therefore could be searched and picked out. Strings in fixed mode are collectively referred as “keywords” in the present invention. 
       FIG. 2  shows a message format C 1 ∥C 2 ∥ . . . ∥C l , wherein C i  represents a field fixed or variable in length and “∥” represents serial conjunction. C i  itself could be further divided into key i ∥data i  format, wherein k i  is first part of the field, data i  is remaining part of the field and could be 0 in length. Accordingly, analysis of message format becomes an optimal partitioning of character strings or bit strings in a message into C 1 , C 2 , . . . , C l , and partitioning of C i  into key i  and data i . 
     Maximum likelihood probability status sequence estimation method of a hidden semi-Markov model (HSMM) is a very suitable method for optimal partitioning, wherein each hidden status represents one or several types of field structure, while time of status continuity represents a length of a respective field. 
     Treat message sequence of an application layer as a character string and refer it as an observation sequence, which is marked as o 1:T =o 1 o 2  . . . o T , wherein T represents length of the observation sequence, and o t  is the t th  character of the observation sequence. Status cluster is defined as S={1, 2, . . . , M}. Status sequence to which the observation sequence o 1:T  corresponds is marked as S 1:T =S 1 S 2  . . . S T  and S t εS. Use S [t:t′]  to represent a status which starts at t and ends at t′. S 1:T  could also be represented by sequence (i 1 ,d 1 ), (i 2 ,d 2 ), . . . , (i n ,d n ), that is, S [1:d     1     ] =i 1 , S [d     1     +1:d     1     +d     2     ]=i   2 , . . . , wherein i m εS is status, d m  is a length of continuation of status i m , and 
                 ∑     m   =   1     n     ⁢     d   m       =   T         
is satisfied. Therefore, optimal field partitioning of the observation sequence is to find a status sequence (i 1 ,d 1 ), (i 2 ,d 2 ), . . . , (i n ,d n ) of a maximum likelihood probability, wherein each status corresponds to a field, and length of continuation of a status is equal to length of a field, and any field or status is restricted within one message and would not extend across two messages. As shown in  FIG. 3 , a character string beginning at its starting position and corresponding to status i m  and length d m  is key m , which is followed by data m . d m  and key m  could be treated as output values or observation values of a given status i m . When necessary, data m  could also be treated as output value (for example, binary or ASCII) of the given status i m .
 
     6. Initial Parameter Setting 
     Since relation between messages and relation between fields in messages represent transfer relation between protocol specification and protocol status, transfer between protocol statues could be understood as a first-order Markov process. In other words, set a ij  as a probability of transfer from status i to status j, and 
                 ∑   j     ⁢     a   ij       =   1         
is satisfied whereas a ii =0. Initial probability of status i is defined as π i . Since protocol status could not be observed, given observation sequence has multiple possible ways of field partitioning. Within one field, different character strings could be selected as key of that field. Therefore, all sub character strings of an observation sequence are possible output values or observation values key of a status. KEY is defined as a cluster of all output values key of a status, and k j (key) defined as probability of key being output values in a given status j, and
 
                 ∑     key   ∈   KEY               ⁢       k   j     ⁡     (   key   )         =   1         
is satisfied.
 
     Lengths of data that follows different key usually have different probability distributions. For example, in protocol specification of Simple Mail Transfer Protocol (SMTP), data of keywords “MAIL” and “RCPT” is a mailing address and generally consists of not more than 30 characters. data following keyword “DATA” is mail text and consists of varying ranges of length distribution from a few hundreds to a few thousands characters. Therefore, length of field, that is, length of continuation of a status, is related not only to status but also to key contained in that field. In a condition under a given status j and its output value being keyεKEY, probability of d being length of continuation of a status is l j,key (d), and 
                 ∑   d     ⁢           ⁢       l             ⁢     j   ,           ⁢   key         ⁢     (   d   )         =   1         
is satisfied, wherein |key|≦d≦D max , with D max  being a maximum length of continuation of a status and |key| being length of key. Besides length of field, encoding format (ASCII, binary, or ASCII and binary) of character string following key could also be considered, in other words, in a condition under a given status j and its output value being keyεKEY, make c j,key (x) as probability of x being encoding format of character string that follows, while c j,key (0)+c j,key (1)+c j,key (2)=1.
 
     Therefore, model parameter of HSMM could be represented as λ={a ij ,π i ,k i (key),l i,key (d)|i,jεS,keyεKEY}. Given a training cluster, forward/backward algorithm of HSMM could be used to complete estimation of model parameter λ. 
     In general, initial values of a ij  and π i  have very little influence on model parameter eventually obtained from training, and equiprobability distribution could be simply obtained. In observation sequence, number of occurrence of short character strings is larger than number of occurrence of long character strings, but long character strings are more likely to be intact keywords. During initialization, make k j (key)=1/|KEY|, wherein |KEY| is number of elements in a KEY cluster and key is any one of the elements in KEY, in other words, obtain equiprobability distribution for all the key. At the same time, set l j,key (d)=ce −τ(d−|key|)  as initial probability distribution of length d≧|key| of each field in a condition when given status j and key, wherein |key| is length of key, d−|key| is length of data that follows the key, τ is a parameter yet to be defined, τ=5 could be resulted according to empirical data, c is a normalization factor resulting in 
     
       
         
           
             
               
                 ∑ 
                 d 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   l 
                   
                     j 
                     , 
                     key 
                   
                 
                 ⁡ 
                 
                   ( 
                   d 
                   ) 
                 
               
             
             = 
             1. 
           
         
       
     
     Suppose the length of key has certain restrictions, KL max  is introduced as the maximum length of key. In general, 10 bytes should be enough for the KL max . When the length of key exceeds KL max , the key would be treated as multiple key′ by a final result. 
     7. Model Parameter Estimation 
     A status ending at t′ is represented by S t′] , and a status starting at t is represented by S [t . S [t:t′  represents a status started at t but not yet ended at t′. S t:t′]  represents a status already started at t and ended at t′. Suppose in a section C m =o t+1:t+d  of an observation sequence, possible range of value of a hidden status output value key is {o t+1:t+kl |1≦kl≦min(d,KL max )}. When given S [t+1:t+d] =j, probability of o t+1:t+d  observed is: 
     
       
         
           
             
               
                 b 
                 
                   j 
                   , 
                   d 
                 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 ( 
                 
                   o 
                   
                     
                       t 
                       + 
                       1 
                     
                     : 
                     
                       t 
                       + 
                       d 
                     
                   
                 
                 ) 
               
             
             = 
             
               
                 ∑ 
                 
                   kl 
                   = 
                   1 
                 
                 
                   min 
                   ⁡ 
                   
                     ( 
                     
                       d 
                       , 
                       
                         KL 
                         max 
                       
                     
                     ) 
                   
                 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   
                     k 
                     j 
                   
                   ⁡ 
                   
                     ( 
                     
                       o 
                       
                         
                           t 
                           + 
                           1 
                         
                         : 
                         
                           t 
                           + 
                           kl 
                         
                       
                     
                     ) 
                   
                 
                 ⁢ 
                 
                   
                     l 
                     
                       j 
                       , 
                       
                         o 
                         
                           
                             t 
                             + 
                             1 
                           
                           : 
                           
                             t 
                             + 
                             kl 
                           
                         
                       
                     
                   
                   ⁡ 
                   
                     ( 
                     d 
                     ) 
                   
                 
               
             
           
         
       
     
     Define forward variable α t (j)=P[S t] =j,o 1:t |λ] wherein its iterative computing formula is: 
                 α   t     ⁡     (   j   )       =     {           π   j           t   =   0                 ∑     i   =   1     M     ⁢           ⁢       ∑     d   =   1       D   t       ⁢           ⁢         α     t   -   d       ⁡     (   i   )       ⁢     a   ij     ⁢       b     j   ,   d       ⁡     (     o       t   -   d   +   1     :   t       )                     1   ≤   t   ≤   T     ,                   
wherein D t  is a maximum length of status j ended with a t th  character. By using the forward variable obtained by iteration, likelihood probability of observation sequence relative to given model λ is computed as:
 
     
       
         
           
             Lkh 
             = 
             
               
                 P 
                 ⁡ 
                 
                   [ 
                   
                     
                       o 
                       
                         1 
                         : 
                         T 
                       
                     
                     | 
                     λ 
                   
                   ] 
                 
               
               = 
               
                 
                   ∑ 
                   
                     j 
                     = 
                     1 
                   
                   M 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     
                       α 
                       T 
                     
                     ⁡ 
                     
                       ( 
                       j 
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
     Define backward variable β t (i)=P[o t+1:T |S t] =i,λ], wherein its iterative computing formula is: 
                 β   t     ⁡     (   i   )       =     {         1         t   =   T                 ∑     j   =   1     M     ⁢           ⁢       ∑     d   =   1       E   t       ⁢           ⁢       a   ij     ⁢       b     j   ,   d       ⁡     (     o       t   +   1     :     t   +   d         )       ⁢       β     t   +   d       ⁡     (   j   )                     1   ≤   t   &lt;   T     ,                   
wherein E t  is a maximum length of continuation of status j having a starting position at a t+1 th  character.
 
     Define intermediate variable: 
                       ξ   t     ⁡     (     i   ,   j     )       =       ⁢     P   ⁡     [         S     t   ]       =   i     ,       S     [     t   +   1         =   j     ,       o     1   :   T       |   λ       ]                     =       ⁢         α   t     ⁡     (   i   )       ⁢       ∑     d   =   1       E   t       ⁢           ⁢       a   ij     ⁢     b     j   ,   d       ⁢       b     j   ,   d       ⁡     (     o       t   +   1     :     t   +   d         )       ⁢       β     t   +   d       ⁡     (   j   )               ,               
wherein i≠j,0≦t≦T−1,
 
                       ψ   t     ⁡     (     j   ,   kl     )       =       ⁢     P   ⁡     [         S     [       t   +   1     :     t   +   kl           =   j     ,       o     1   :   T       |   λ       ]                     =       ⁢       ∑     i   =   1     M     ⁢           ⁢       ∑     d   =   kl       D   t       ⁢           ⁢         α   t     ⁡     (   i   )       ⁢     a   ij     ⁢       k   j     ⁡     (     o       t   +   1     :     t   +   kl         )       ⁢       l     j   ,     o       t   +   1     :     t   -   kl             ⁡     (   d   )       ⁢       β     t   +   d       ⁡     (   j   )               ,               
wherein t≦T−kl,kl≧1,
 
                       ζ   t     ⁡     (     j   ,   key   ,   d     )       =       ⁢     P   ⁡     [         S     [       t   -   d   +   1     :   t     ]       =   j     ,       o       t   -   d   +   1     :     t   -   d   +        key              =   key     ,       o     1   :   T       |   λ       ]                     =       ⁢       ∑     i   =   1     M     ⁢       α     t   -   d       ⁢     (   i   )     ⁢     a   ij     ⁢       k   j     ⁡     (   key   )       ⁢       l     j   ,   key       ⁡     (   d   )       ⁢       β   t     ⁡     (   j   )       ⁢     δ   ⁡     (       o       t   -   d   +   1     :     t   -   d   +        key              -   key     )             ,               
wherein t≧1,D t ≧d≧|key|≧1. δ(o t−d+1:t−d+|key| −key)=1 if o t−d+1:t−d+|key| =key; otherwise, 0 would be resulted.
 
     Use multiple sequence training model. Suppose a training cluster comprises N th  observation sequences, wherein o 1:T     (m)     (m)  is an m th  observation sequence wherein T (m)  is its length. Lkh (m) , ξ t   (m) (i,j), ψ t   (m) (j,kl) and ζ t   (m) (j,key,d) could be computed from o 1:T     (m)     (m) . 
     Model parameter is then estimated by using the following formula: 
     
       
         
           
             
               
                 a 
                 ^ 
               
               ij 
             
             = 
             
               
                 ∑ 
                 
                   m 
                   = 
                   1 
                 
                 N 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   1 
                   
                     Lkh 
                     
                       ( 
                       m 
                       ) 
                     
                   
                 
                 ⁢ 
                 
                   
                     ∑ 
                     
                       t 
                       = 
                       1 
                     
                     
                       
                         T 
                         
                           ( 
                           m 
                           ) 
                         
                       
                       - 
                       1 
                     
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       ξ 
                       t 
                       
                         ( 
                         m 
                         ) 
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         i 
                         , 
                         j 
                       
                       ) 
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 
                   k 
                   ^ 
                 
                 j 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 ( 
                 key 
                 ) 
               
             
             = 
             
               
                 ∑ 
                 
                   m 
                   = 
                   1 
                 
                 N 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   1 
                   
                     Lkh 
                     
                       ( 
                       m 
                       ) 
                     
                   
                 
                 ⁢ 
                 
                   
                     ∑ 
                     
                       t 
                       = 
                       0 
                     
                     
                       
                         T 
                         
                           ( 
                           m 
                           ) 
                         
                       
                       - 
                       
                          
                         key 
                          
                       
                     
                   
                   ⁢ 
                   
                     
                       
                         ψ 
                         t 
                         
                           ( 
                           m 
                           ) 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           j 
                           , 
                           
                              
                             key 
                              
                           
                         
                         ) 
                       
                     
                     · 
                     
                       δ 
                       ⁡ 
                       
                         ( 
                         
                           
                             o 
                             
                               
                                 t 
                                 + 
                                 1 
                               
                               : 
                               
                                 t 
                                 + 
                                 
                                    
                                   key 
                                    
                                 
                               
                             
                             
                               ( 
                               m 
                               ) 
                             
                           
                           - 
                           key 
                         
                         ) 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 
                   l 
                   ^ 
                 
                 
                   j 
                   , 
                   key 
                 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 ( 
                 d 
                 ) 
               
             
             = 
             
               
                 ∑ 
                 
                   m 
                   = 
                   1 
                 
                 N 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   1 
                   
                     Lkh 
                     
                       ( 
                       m 
                       ) 
                     
                   
                 
                 ⁢ 
                 
                   
                     ∑ 
                     
                       t 
                       = 
                       d 
                     
                     
                       T 
                       
                         ( 
                         m 
                         ) 
                       
                     
                   
                   ⁢ 
                   
                     
                       ζ 
                       t 
                       
                         ( 
                         m 
                         ) 
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         j 
                         , 
                         key 
                         , 
                         d 
                       
                       ) 
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 π 
                 ^ 
               
               i 
             
             = 
             
               
                 ∑ 
                 
                   m 
                   = 
                   1 
                 
                 N 
               
               ⁢ 
               
                 
                   ∑ 
                   
                     j 
                     = 
                     1 
                   
                   M 
                 
                 ⁢ 
                 
                   
                     1 
                     
                       Lkh 
                       
                         ( 
                         m 
                         ) 
                       
                     
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       ξ 
                       0 
                       
                         ( 
                         m 
                         ) 
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         i 
                         , 
                         j 
                       
                       ) 
                     
                   
                 
               
             
           
         
       
     
     Finally, perform normalization processing so that a new estimated value {circumflex over (λ)}={â ij ,{circumflex over (π)} i ,{circumflex over (k)} j (key),{circumflex over (l)} j,key (d)} of the model parameter could be obtained. Repeat such estimation process of model parameter and a set of model parameter values could be eventually obtained by convergence. This kind of iterative estimation process has been proved to be a monotonic increase process of likelihood probability and therefore must be a convergent process. According to empirical data, several iterations could already result in very close proximity to convergence value. A maximum of over ten and less than twenty times of iterations could already result in convergence of a fixed point with very high precision. 
     8. Field Partitioning of Maximum Likelihood Probability 
     After model parameter λ is obtained by estimation, start to perform field partitioning of maximum likelihood probability. As mentioned above, any one of observation sequences in a sample cluster has multiple possible ways of field partitioning. Maximum likelihood probability (ML) estimation of a hidden status sequence would be an optimal field partitioning of an observation sequence. Therefore, status sequence of maximum likelihood probability could be estimated by using the following algorithm, and various statuses could then determine various keywords in a protocol: 
     Let G(j,key,d)=k j (key)l j,key (d) and define forward variable: 
                       δ   t     ⁡     (     j   ,   d     )       ≡       ⁢       max     S     1   :     t   -   d           ⁢           ⁢     P   ⁡     [       S     1   :     t   -   d         ,       S     [       t   -   d   +   1     :   t     ]       =   j     ,       o     1   :   t       |   λ       ]                       =       ⁢       max     i   ,     d   ′     ,   kl       ⁢           ⁢         δ     t   -   d       ⁡     (     i   ,     d   ′       )       ⁢     a   ij     ⁢     G   ⁡     (     j   ,     o       t   -   d   +   1     :     t   -   d   +   kl         ,   d     )             ,               
wherein 1≦t≦T, 1≦d≦D t , 1≦d′≦D t−d′  and 1≦kl≦KL max .
 
     Use Ψ(t,j,d) to record a last previous status selected by δ t (j,d) and its time of continuation; at the same time, use Key_ML(t,j,d) to record keywords selected by current status&#39; field partitioning (j,d): 
     
       
         
           
             
               ( 
               
                 
                   i 
                   * 
                 
                 , 
                 
                   d 
                   * 
                 
                 , 
                 
                   kl 
                   * 
                 
               
               ) 
             
             = 
             
               
                 
                   arg 
                   ⁢ 
                   max 
                 
                 
                   i 
                   , 
                   
                     d 
                     ′ 
                   
                   , 
                   kl 
                 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   δ 
                   
                     t 
                     - 
                     d 
                   
                 
                 ⁡ 
                 
                   ( 
                   
                     i 
                     , 
                     
                       d 
                       ′ 
                     
                   
                   ) 
                 
               
               ⁢ 
               
                 a 
                 ij 
               
               ⁢ 
               
                 G 
                 ⁡ 
                 
                   ( 
                   
                     j 
                     , 
                     
                       o 
                       
                         
                           t 
                           - 
                           d 
                           + 
                           1 
                         
                         : 
                         
                           t 
                           - 
                           d 
                           + 
                           kl 
                         
                       
                     
                     , 
                     d 
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               Ψ 
               ⁡ 
               
                 ( 
                 
                   t 
                   , 
                   j 
                   , 
                   d 
                 
                 ) 
               
             
             = 
             
               ( 
               
                 
                   t 
                   - 
                   d 
                 
                 , 
                 
                   i 
                   * 
                 
                 , 
                 
                   d 
                   * 
                 
               
               ) 
             
           
         
       
       
         
           
             
               Key_ML 
               ⁢ 
               
                 ( 
                 
                   t 
                   , 
                   j 
                   , 
                   d 
                 
                 ) 
               
             
             = 
             
               o 
               
                 
                   t 
                   - 
                   d 
                   + 
                   1 
                 
                 : 
                 
                   t 
                   - 
                   d 
                   + 
                   
                     kl 
                     * 
                   
                 
               
             
           
         
       
     
     When forward computation is completed, let t 1 =T, and perform path backtracking in a reversed direction: 
     
       
         
           
             
               ( 
               
                 
                   j 
                   1 
                 
                 , 
                 
                   d 
                   1 
                 
               
               ) 
             
             = 
             
               
                 
                   
                     arg 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     max 
                   
                   ⁢ 
                   
                       
                   
                 
                 
                   i 
                   , 
                   d 
                 
               
               ⁢ 
               
                 
                   δ 
                   T 
                 
                 ⁡ 
                 
                   ( 
                   
                     i 
                     , 
                     d 
                   
                   ) 
                 
               
             
           
         
       
       
         
           
             
               kw 
               1 
             
             = 
             
               Key_ML 
               ⁢ 
               
                 ( 
                 
                   
                     t 
                     1 
                   
                   , 
                   
                     j 
                     1 
                   
                   , 
                   
                     d 
                     1 
                   
                 
                 ) 
               
             
           
         
       
       
         
           
             
               ( 
               
                 
                   t 
                   2 
                 
                 , 
                 
                   j 
                   2 
                 
                 , 
                 
                   d 
                   2 
                 
               
               ) 
             
             = 
             
               Ψ 
               ⁡ 
               
                 ( 
                 
                   
                     t 
                     1 
                   
                   , 
                   
                     j 
                     1 
                   
                   , 
                   
                     d 
                     1 
                   
                 
                 ) 
               
             
           
         
       
       
         
           
             
               kw 
               2 
             
             = 
             
               Key_ML 
               ⁢ 
               
                 ( 
                 
                   
                     t 
                     2 
                   
                   , 
                   
                     j 
                     2 
                   
                   , 
                   
                     d 
                     2 
                   
                 
                 ) 
               
             
           
         
       
       
         
           
             
                 
             
             ⁢ 
             
               
                 … 
                 ⁢ 
                 
                   
 
                 
                 ( 
                 
                   
                     t 
                     n 
                   
                   , 
                   
                     j 
                     n 
                   
                   , 
                   
                     d 
                     n 
                   
                 
                 ) 
               
               = 
               
                 
                   
                     Ψ 
                     ⁡ 
                     
                       ( 
                       
                         
                           t 
                           
                             n 
                             - 
                             1 
                           
                         
                         , 
                         
                           j 
                           
                             n 
                             - 
                             1 
                           
                         
                         , 
                         
                           d 
                           
                             n 
                             - 
                             1 
                           
                         
                       
                       ) 
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     kw 
                     n 
                   
                 
                 = 
                 
                   Key_ML 
                   ⁢ 
                   
                     ( 
                     
                       
                         t 
                         
                           n 
                           - 
                           1 
                         
                       
                       , 
                       
                         j 
                         
                           n 
                           - 
                           1 
                         
                       
                       , 
                       
                         d 
                         
                           n 
                           - 
                           1 
                         
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
     Algorithm ends when it is determined that s 1 =j n . Status sequence [(i 1 ,τ 1 ), . . . , (i n ,τ n )] of maximum likelihood probability and keyword sequence [key 1 , . . . , key n ] included in observation sequence are eventually obtained, wherein i l =j n−l+1 , τ l =d n−l+1 , key l =kw n−l+1  and l=1, . . . , n. 
     9. Obtain Protocol Analysis Result 
     Suppose there are a total number of N th  observation sequences in the training cluster, wherein a status sequence of maximum likelihood probability obtained by an m th  observation sequence o 1:T     (m)     (m)  is [(i 1   (m) ,τ 1   (m) ), . . . , (i n   (m) ,τ n     m     (m) )], keyword sequence included in the observation sequence is [key 1   (m) , . . . , key n     m     (m) ], keyword cluster is 
                 key     (   m   )       =         ⋃     n   m         i   =   1       ⁢     key   i     (   m   )           ,         
message sequence is M (m) =[M 1   (m) , . . . , M l     m     (m) ], wherein each message M j   (m)  includes a keyword sub sequence M j   (m) =[key i     j     (m) , . . . , key i     j+1       −1     (m) ]. Gather all the observation sequences in the total number of N and obtain protocol keyword cluster of a respective protocol being
 
               KEY   =         ⋃   N       m   =   1       ⁢     key     (   m   )           ,         
message format cluster being
 
               F   =         ⋃   N       m   =   1       ⁢         ⋃     l   m         j   =   1       ⁢     M   j     (   m   )             ,         
and dialogue sequence cluster being
 
     
       
         
           
             E 
             = 
             
               
                 
                   ⋃ 
                   N 
                 
                 
                   m 
                   = 
                   1 
                 
               
               ⁢ 
               
                 
                   M 
                   
                     ( 
                     m 
                     ) 
                   
                 
                 . 
               
             
           
         
       
     
     10. Determine Dialogue Rules 
     Establish a prefix tree to represent dialogue rules of a respective protocol by using the dialogue sequence cluster 
             E   =         ⋃   N       m   =   1       ⁢     M     (   m   )               
as obtained, wherein each transfer line of the tree represents a keyword and each path extended from the tree root represents a dialogue sub sequence, in other words, a type of interactive process of a respective application layer protocol dialogue.
 
     Substitute each transfer line of the prefix tree with an automaton corresponding to its respective keyword to form an even larger automaton; simplify the automaton via grammar inference (GI) algorithm by using streams of other application layer protocols as negative examples cluster; the automata or regular expressions eventually obtained are used for online identification of the respective protocol. 
     11. Obtain Status Transfer Relations 
     Status transfer probability matrix of the protocol is determined by the model parameter {circumflex over (λ)}={â ij ,{circumflex over (π)} i ,{circumflex over (k)} j (key),{circumflex over (l)} j,key (d)} as trained and obtained: Remove from â ij  those statuses with very small inward transfer probability and those statuses with a certain outward transfer probability near to 1. The â ij  eventually obtained reflects status transfer relations of an unknown application layer protocol. At the same time, {circumflex over (π)} i  is initial status distribution of the protocol, {circumflex over (k)} j (key) is a probability of occurrence of keyword key when given status j, and {circumflex over (l)} j,key (d) is a probability of having d being length of field when given key and status j.