CN103441990B - The automatic estimating method of protocol state machine based on state fusion - Google Patents

Abstract

The present invention relates to the field of network technology, and provides an automatic state machine inference method based on state fusion, including the following steps: message format extraction and message classification, session abstraction and initial state machine construction, and state fusion based on output messages . The protocol state machine automatic inference method of the present invention adopts the enhanced prefix tree converter EPTT to describe the session process of the protocol entity, focuses on the output message of the protocol, integrates the same state in the state machine, and conducts test interaction with the protocol entity Verify the feasibility of protocol state fusion, ensure the automation of protocol state machine inference, and improve the accuracy of inference results.

Description

Automatic inference method of protocol state machine based on state fusion

technical field

The invention relates to the field of network technology, in particular to a method for automatically inferring a protocol state machine of a corresponding network protocol based on network messages received and sent by a protocol entity program.

Background technique

Network protocols are the supporting elements for the realization of network communication functions, and are also key research objects in the field of network security. A large number of network security technologies such as intrusion detection, fuzz testing, protocol reuse, and protocol vulnerability analysis are based on detailed protocol specification information.

A large number of private protocols lacking description documents are used in the network, which greatly limits the application range of various network security technologies that rely on information specifications. In order to solve the problem of unknown protocol information, researchers began to use the protocol reverse method to obtain unknown protocol specifications. Protocol reverse refers to the process of extracting specific specification information of network protocols by monitoring and analyzing the network input and output, system behavior and instruction execution process of protocol entities without relying on the protocol description.

The network protocol specification mainly includes two parts: the protocol format and the protocol state machine. The protocol format focuses on the composition and structure of each protocol field in the communication message. The protocol state machine focuses on the number of protocol states in the protocol system and the rules for the protocol system to transition from one protocol state to another protocol state when it receives different inputs.

Traditional protocols are reversed manually, the process is tedious and time-consuming, and the accuracy depends on the technical level and practical experience of the analysts. With the expansion of the network scale and the increase of the types of protocols, the requirements for the accuracy and timeliness of the reverse analysis are getting higher and higher, and the traditional manual reverse analysis of the protocol can no longer meet the needs of practical applications. Automatic protocol reverse can significantly reduce manual analysis and improve the analysis efficiency of private protocols, which has gained more and more attention.

At present, most of the protocol automatic reverse research focuses on the extraction of the protocol format, and the lack of protocol state machine information in the analysis results restricts the practical application of the protocol reverse results. In recent years, with the relative maturity of the protocol format extraction technology, some researchers have begun to try to reverse the protocol state machine. The current protocol state machine inference mainly has the following problems: (1) For the sake of simplicity, the existing state fusion methods (such as the Prospex system) aim at a finite state machine with no output. In this finite state machine, there is only message input, and no message output is considered, ignoring the internal relationship between the input and output messages of the protocol system. The protocol system is a state transition system with output. This simplification makes the state machine obtained by state fusion quite different from the actual protocol system. (2) In order to solve the problem of incomplete sample set, it is often necessary to continuously generate new samples during the inference process of the protocol state machine, and further infer according to whether the new sample belongs to the protocol state machine. Whether a new sample is positive or negative for the protocol state machine depends on manual judgment. On the one hand, it is difficult to ensure the accuracy of the manual judgment processing method. On the other hand, this processing method has a low degree of automation, which restricts the efficiency of reverse analysis.

Contents of the invention

Aiming at the problems existing in the prior art, the present invention aims to provide a method for automatically inferring the protocol state machine based on state fusion, aiming at the problem of inferring the protocol state machine of an unknown protocol, on the basis of the existing packet protocol format inference technology According to the collected message samples, construct an enhanced prefix tree converter EPTT (ExtendedPrefixTreeTransducer) to describe the abstract symbol string composed of the input and output messages involved in the session process of the protocol entity, and determine the feasibility of state fusion through the test interaction with the protocol entity It ensures the automation of state machine inference and improves the accuracy of inference results.

In order to achieve the above object, the technical scheme adopted in the present invention is as follows:

A method for automatically inferring a protocol state machine based on state fusion, comprising the following steps:

(1) Message format extraction and message classification: obtain the specific format information of the input and output messages related to the protocol entity program, and classify the input and output messages according to the message format, and group the message samples with the same structure into is a category, and the category information of the classification is represented by an abstract symbol;

(2) Session abstraction and initial state machine construction: Based on the classification categories represented by abstract symbols, the network communication behavior is abstracted with sessions as units, and the input and output message sequences in the session process are described as abstract input and output symbol strings. Then, according to the session sample set, construct an initial state machine consistent with the set of input and output symbol strings;

(3) State fusion based on the output message: The candidate states are fused according to the similarity, and a test symbol string is generated, and then through an automated test, the protocol entity is compared with the fused state machine after receiving the test symbol string. output response to verify the feasibility of state fusion;

(4) Repeat the above step (3) until there are no states that meet the fusion conditions in the state machine;

The workflow of the aforementioned session abstraction and initial state machine construction phase is as follows: the inference of the state machine is built on the basis of the session sample set, and the input and output messages in the session are represented by abstract symbols corresponding to their categories, so that the input of the complete session The output message sequence is converted into an abstract input and output symbol string; on this basis, according to the session sample set, the initial state machine is constructed in the form of an enhanced prefix tree converter EPTT, and the initial state machine contains all input and output as session samples symbol string;

The workflow of the state fusion stage based on the output message is as follows: on the basis of the initial state machine, two similar states are fused each time according to the degree of similarity, and the selection of similar states is based on the BlueFringe algorithm. The two states with the highest degrees are the candidate states to be fused; whether the fusion of the candidate states is feasible or not will be judged based on the generated test string to determine whether the two candidate states can be fused, wherein: the test string is based on the arrival of the original state machine The string prefixes and string suffixes of the two candidate states are constructed. Through cross splicing, all the string prefixes reaching a certain candidate state are sequentially spliced with all the string suffixes of the other candidate state, and the generated strings form a test String collection, if it is judged that all the output strings are consistent with the fused protocol state machine, it is considered that the state fusion is feasible, otherwise it is judged that the state fusion is not feasible; the test results are added to the session sample set as a new sample and the protocol state machine is extended , and continue to try to fuse other states.

Further, in the aforementioned method, when selecting a candidate state to be fused in the protocol state machine, the BlueFringe algorithm is used as the basis, and the calculation of the similarity is based on the public input string suffix of the protocol state, which reflects that the protocol entity is in two states. In different protocol states, the state transition and output response when receiving the same input message, where: the input string suffix means that the protocol entity starts from a certain protocol state and receives a series of input messages, these input messages The text is expressed as an input string suffix in the state machine; the common input string suffix means that two different states receive the same series of input messages; the calculation of the similarity will consider the length of the common input string suffix of the protocol state , and whether the protocol entity produces the same output when receiving the same input, if two protocol states have the longest length of their common input string suffix, and have the same output for the same input, such two protocol states will Prioritize fusion attempts.

Further, in the aforementioned method, the process of using the test character string set to perform state fusion and feasibility determination includes the following steps: first, according to the test character string and the known message protocol format, generate an input message sequence as a test case; The input message sequence is sent to the protocol entity program to obtain the output message sequence as a response; the output message sequence is abstracted and expressed as an output string sequence; the output string is judged for the protocol state machine after candidate state fusion Whether the output characters in the sequence exist in the output symbol set of the corresponding state of the protocol state machine: if all the output strings are consistent with the fused protocol state machine, then the state fusion is considered feasible, otherwise it is judged that the state fusion is not feasible.

As can be seen from the technical solution of the present invention above, the beneficial effect of the present invention is that the protocol system is regarded as a state transition system with output, focusing on the internal relationship between the input and output messages in the protocol system and implementing fusion of the states in the protocol state machine , by using the enhanced prefix tree converter EPTT (ExtendedPrefixTreeTransducer) to describe the abstract symbol string composed of the input and output messages involved in the session process of the protocol entity, and through the test interaction with the protocol entity to determine the feasibility of state fusion, it will help Ensure that the constructed protocol state machine is highly consistent with the actual protocol system, ensure the automation of state machine inference, and improve the accuracy of inference results; and automatically generate auxiliary judgment input samples for the candidate states to be fused, and then through the automation of the protocol entity program The operation masters the output response of the protocol entity to the input sample, avoids the inefficiency of manual judgment, and improves the accuracy and overall efficiency of the reverse inference of the state machine.

Description of drawings

FIG. 1 is a schematic diagram of the overall implementation flow of the automatic inference method of the present invention.

Fig. 2 is an example of constructing an EPTT state machine based on an abstract string sequence in the present invention.

Fig. 3 is an example of fusion of candidate states in the present invention.

detailed description

In order to better understand the technical content of the present invention, specific embodiments are given and described as follows with reference to the accompanying drawings.

As shown in Figure 1, according to a preferred embodiment of the present invention, the automatic inference method of the protocol state machine based on state fusion includes the following steps:

(1) Message format extraction and message classification: First, a large number of input and output message sequences are collected, and then the existing message format extraction method is used to obtain the specific format information of the input and output messages related to the protocol entity program. Here Basically, according to the message format, the input and output messages are classified respectively, and the message samples with the same structure are classified into one category, and the category information of the classification is represented by abstract symbols;

(2) Conversation abstraction and initial state machine construction: On the basis of message classification, the network communication behavior is abstracted with sessions as units, and the input and output message sequences in the session process are described as abstract input and output symbol strings. Then, according to the session sample set, construct an initial state machine consistent with the set of input and output symbol strings;

(3) State fusion based on the output message: The candidate states are fused according to the similarity, and a test symbol string is generated, and then through an automated test, the protocol entity is compared with the fused state machine after receiving the test symbol string. output response to verify the feasibility of state fusion;

(4) Repeat the above step (3) until there are no more states that meet the fusion conditions in the state machine.

Among them, the workflow of the aforementioned session abstraction and initial state machine construction phase is as follows: the inference of the state machine is built on the basis of the session sample set, and the input and output messages in the session are represented by abstract symbols corresponding to their categories, so that the complete session On this basis, according to the session sample set, the initial state machine is constructed in the form of enhanced prefix tree converter EPTT, and the initial state machine contains all session samples input and output strings;

The workflow of the state fusion stage based on the output message is as follows: on the basis of the initial state machine, two similar states are fused each time according to the degree of similarity, and the selection of similar states is based on the BlueFringe algorithm. The two states with the highest degrees are the candidate states to be fused; whether the fusion of the candidate states is feasible or not will be judged based on the generated test string to determine whether the two candidate states can be fused, wherein: the test string is based on the arrival of the original state machine The string prefixes and string suffixes of the two candidate states are constructed. Through cross splicing, all the string prefixes reaching a certain candidate state are sequentially spliced with all the string suffixes of the other candidate state, and the generated strings form a test String collection, if it is judged that all the output strings are consistent with the fused protocol state machine, it is considered that the state fusion is feasible, otherwise it is judged that the state fusion is not feasible; the test results are added to the session sample set as a new sample and the protocol state machine is extended , and continue to try to fuse other states.

With reference to the overall implementation process shown in Figure 1 and in combination with Figures 2 and 3, the automatic inference method of the protocol state machine in this embodiment includes message format extraction and message classification, session abstraction and initial state machine construction, and based on output message The state of the fusion of three parts, the specific implementation is described below.

(1) Message format extraction and message classification

The embodiment of the present invention firstly collects a large number of input and output message sequences generated by the network communication of the protocol entity program, and uses the message format extraction method of the PI project (Protocol Information Project) to obtain the specific format information of the input and output messages. On this basis, classify the input message and the output message according to the message format, and if several message samples have the same message structure, they will be classified into one category. For each category, use unique Arabic numerals (such as 1, 2, 3) for identification.

(2) Session abstraction and initial state machine construction

On the basis of packet classification, the network communication behavior is abstracted in units of sessions.

A session represents a complete data exchange between communication participants, which can reflect the transition of the protocol state during the communication process. In the field of network protocol research, there are many mature methods for identifying network sessions. Upper-layer applications use services provided by lower-layer protocols. If it is a network application based on the TCP protocol, a session is often started by the three-way handshake of the TCP protocol, and stops when the TCP connection is interrupted; if it is a network application based on the UDP protocol, a session is often distinguished by the communication interval. If the time of stopping communication exceeds a certain period of time, it is inferred that a session has been completed.

In the process of session abstraction, the input and output message categories are used to replace the specific message information, and the string sequence is constructed according to the time sequence of the message.

For example, a session is expressed as a string sequence (<1, 2, 5>, <1, 3, 6>), where <1, 2, 5> represents the input string sequence, and the Arabic numeral 1 in the sequence means that the first input message belongs to the input message category 1, and the number 2 means that the second input message belongs to the input message category 2; <1, 3, 6> indicates the output string sequence, where the number 1 means that the first output message belongs to output message category 1, the number 3 means that the second output message belongs to output message category 3, and so on. The meaning of this session is that when the protocol entity receives a message with a certain category (input message category) as 1, it outputs a message with a certain category (output message category) as 1, and enters a new protocol state at the same time; When in a new protocol state, the protocol entity receives a message with a category (input message category) of 2, outputs a message with a category (output message category) of 3, and enters another protocol state ; In this protocol state, the protocol entity receives a message with a category (input message category) of 5, outputs a message with a category (output message category) of 6, and performs a state transition again.

After the session abstraction of the input and output message samples is converted into a string sequence set, the initial protocol state machine is built. The invention adopts the form of enhanced prefix tree converter EPTT to construct the state machine, which has the advantage of being able to accurately describe the state output information of the protocol entity, and the constructed protocol state machine with output is closer to the actual network protocol situation.

The protocol state machine in the form of EPTT is defined as a 6-tuple (Q _E , I, O, δ _E , λ _E , q _λ ), where Q _E represents the set of states, I represents the set of input symbols, O represents the set of output symbols, and δ _E represents the state transition function, λ _E represents the output function, and q _λ represents the initial protocol state.

When constructing the EPTT protocol state machine, session samples are added to the state machine in turn. FIG. 2 is an example of constructing an EPTT state machine based on an abstract string sequence in the present invention. For a string sequence of a certain session, the input string sequence and the output string sequence are combined for analysis in the form of traversal. For example, for the first conversation sample in Figure 2, the input string sequence <1, 2, 5> and the output string sequence <1, 3, 6> will be combined and analyzed synchronously, reflecting the Correspondence.

During the traversal process, a prefix symbol string will be constructed based on the input string sequence to describe the input characters that have been traversed. The initial state is set to state 0, and the protocol state machine starts to receive input from the initial state. The prefix symbol string is initially set to λ, indicating that the prefix symbol string is currently empty. The characters in the input string sequence are sequentially added to the prefix symbol string. If the state reached by the prefix symbol string does not exist in the original state machine, create a new state and uniquely identify it with Arabic numerals. If the corresponding state transition information does not exist in the original state machine, then expand the state transition function and output function; if the original state machine already contains the corresponding state transition information, it will further judge whether to expand the output information.

For example, for the first session sample in Figure 2, the first input character encountered in the traversal process is 1, forming a prefix symbol string λ1, and a new protocol state needs to be created, and the number 1 identifies this state. At the same time, expand the state transition function (when the protocol entity is in state 0, it receives input character 1 and transfers to state 1), and the output function (when the protocol entity is in state 0, it receives input character 1 and generates output character 1). The second input character encountered in the traversal process is 2, forming a prefix symbol string λ12, creating a new state identified by the number 2, and expanding the state transition function (when the protocol entity is in state 1, the input character 2 is received, transfer to state 2), and the output function (when the protocol entity is in state 1, it receives input character 2 and produces output character 3). For the second session sample in Figure 2, since the state transition involved is the same as that of the first session sample, no new state will be generated. But according to the second conversation sample, the protocol entity in state 1 receives input character 2, which produces output character 4. The output information will be extended to the original protocol state machine, that is, the protocol entity receives input character 2 when it is in state 1, and the output character generated belongs to the output character set {3, 4}.

After traversing all session samples, the initial protocol state machine will be obtained. The construction method of the initial protocol state machine is to directly add all session samples without any distinction and screening. Therefore, the state machine results obtained by construction often contain a large number of redundant states, which need to be simplified by fusing similar states. The obtained protocol state machine has more practical value.

(3) State fusion based on output messages

After the initial state machine is constructed, it will try to perform state fusion on similar states in the state machine according to the degree of similarity. The selection of the similar state in this embodiment is based on the BlueFringe algorithm, but the calculation method of the similarity is improved. Evaluate the similarity of two protocol states, based on the public input string suffix. The input string suffix means that the protocol entity starts from a certain protocol state and receives a series of input messages, and these input messages are represented as the input string suffix in the state machine. The "common" in the public input string suffix emphasizes that two different protocol states receive the same sequence of input packets. The public input string suffix can reflect the state transition and output response of the protocol entity when it receives the same input message when it is in two different protocol states. When calculating the similarity, the length of the public input string suffix of the protocol state will be considered, and whether the protocol entities have the same output results for the same input received. If two protocol states have the longest common input string suffix and have the same output for the same input, such two protocol states will be used as candidate states to try to fuse first.

Whether the two candidate states can be merged requires further determination. Because the protocol state machine is constructed based on training samples, and the training samples are difficult to guarantee comprehensiveness, there may be differences between the inferred protocol state machine and the real protocol state machine. In order to judge whether the fusion of two candidate states is feasible, it is necessary to further generate a test string for testing, and to affirm or deny the fusion of candidate states through the performance of the protocol entity program for the test string, so as to ensure the inferred protocol state machine The results are highly consistent with the real protocol state machine.

Referring to FIG. 3 , the test string is generated based on the state machine before candidate state fusion, mainly based on the string prefix and string suffix of the two candidate states in the state machine. The test strings are generated by cross-splicing, sequentially splicing all string prefixes reaching a certain candidate state with all string suffixes in another candidate state, and the generated strings form a test string set. For example, for the state machine before state fusion in Figure 3, state 1 and state 3 have the highest similarity, and fusion will be attempted first. When constructing the test string, the analysis shows that the set of string prefixes in state 1 is {<1>}, and the set of string prefixes in state 3 is {<1,7>}. Since the string prefix <1,7> contains <1>, during the fusion process, we will focus on the suffix set {<7,2,5,14>} of state 1 and the suffix set of state 3 {<2,5 ,14>}, the generated test string set contains 2 elements {<1,2,5,14>,<1,7,7,2,5,14>}.

In the process of testing with the test character string, firstly, the test character string is instantiated as an input message sequence according to the test character string and the known message protocol format. Send the input message sequence to the protocol entity program, and obtain the output message sequence as a response. Abstract the sequence of output messages and represent it as a sequence of output strings. For the protocol state machine after candidate state fusion, it is judged whether the output characters in the output character string sequence all exist in the output symbol set of the corresponding state of the protocol state machine. If all the output strings are consistent with those in the state machine, it is considered that the state fusion is feasible, otherwise it is judged that the state fusion is not feasible, the test result is added to the sample set as a new sample and the protocol state machine is expanded, and continue to select other in the state machine Candidate states implement fusion.

The state fusion operation will be repeated until there are no fusionable states in the state machine.

It can be known from the above technical solutions of the present invention that the automatic state machine inference method based on state fusion of the present invention, on the basis of the existing message protocol format inference technology, constructs an enhanced prefix tree converter according to the collected message samples, A simplified protocol state machine is obtained by merging the same kind of states in the enhanced prefix tree converter. Adopting this method needs to obtain the protocol entity program, and be able to run the entity program as needed, send a specific message sequence to it, and observe the corresponding message output, as the basis for inferring the protocol state machine.

In summary, the protocol state machine automatic inference method based on state fusion of the present invention regards the protocol system as a state transition system with output, and focuses on the internal relationship between input and output messages in the protocol system. State implementation fusion, through the use of enhanced prefix tree converter EPTT to describe the abstract symbol string composed of input and output messages involved in the session process of the protocol entity, and determine the feasibility of state fusion through test interaction with the protocol entity, which is helpful Ensure that the constructed protocol state machine is highly consistent with the actual protocol system, ensure the automation of state machine inference, and improve the accuracy of inference results; and automatically generate auxiliary judgment input samples for the candidate states to be fused, and then through the automation of the protocol entity program The operation masters the output response of the protocol entity to the input sample, avoids the inefficiency of manual judgment, and improves the accuracy and overall efficiency of the reverse inference of the state machine.

Although the present invention has been disclosed above with preferred embodiments, it is not intended to limit the present invention. Those skilled in the art of the present invention can make various changes and modifications without departing from the spirit and scope of the present invention. Therefore, the scope of protection of the present invention should be defined by the claims.

Claims (3)

1. A method for automatically inferring a protocol state machine based on state fusion, characterized in that, comprising the following steps: (1) Message format extraction and message classification: obtain the specific format information of the input and output messages related to the protocol entity program, and classify the input and output messages according to the message format, and group the message samples with the same structure into is a category, and the category information of the classification is represented by an abstract symbol; (2) Session abstraction and initial state machine construction: Based on the classification categories represented by abstract symbols, the network communication behavior is abstracted with sessions as units, and the input and output message sequences in the session process are described as abstract input and output symbol strings. Then, according to the session sample set, construct an initial state machine consistent with the set of input and output symbol strings; (3) State fusion based on the output message: The candidate states are fused according to the similarity, and a test symbol string is generated, and then through an automated test, the protocol entity is compared with the fused state machine after receiving the test symbol string. output response to verify the feasibility of state fusion; (4) Repeat the above step (3) until there are no states that meet the fusion conditions in the state machine; The workflow of the aforementioned session abstraction and initial state machine construction phase is as follows: the inference of the state machine is built on the basis of the session sample set, and the input and output messages in the session are represented by abstract symbols corresponding to their categories, so that the input of the complete session The output message sequence is converted into an abstract input and output symbol string; on this basis, according to the session sample set, the initial state machine is constructed in the form of an enhanced prefix tree converter EPTT, and the initial state machine contains all input and output as session samples symbol string; The workflow of the state fusion stage based on the output message is as follows: on the basis of the initial state machine, two similar states are fused each time according to the degree of similarity, and the selection of similar states is based on the BlueFringe algorithm. The two states with the highest degrees are the candidate states to be fused; whether the fusion of the candidate states is feasible or not will be judged based on the generated test string to determine whether the two candidate states can be fused, wherein: the test string is based on the arrival of the original state machine The string prefixes and string suffixes of the two candidate states are constructed. Through cross splicing, all the string prefixes reaching a certain candidate state are sequentially spliced with all the string suffixes of the other candidate state, and the generated strings form a test String collection, if it is judged that all the output strings are consistent with the fused protocol state machine, it is considered that the state fusion is feasible, otherwise it is judged that the state fusion is not feasible; the test results are added to the session sample set as a new sample and the protocol state machine is extended , and continue to try to fuse other states. 2. The method according to claim 1, wherein, in the aforementioned method, when selecting a candidate state to be fused in the protocol state machine, based on the BlueFringe algorithm, the calculation of the similarity is based on the public input character string of the protocol state Suffix, the public input string suffix reflects the state transition and output response of the protocol entity when it receives the same input message when it is in two different protocol states, where: the input string suffix means that the protocol entity starts from a certain protocol state , a series of input messages are received, and these input messages are represented as input string suffixes in the state machine; the common input string suffix means that two different states receive the same series of input messages; the similarity The calculation will consider the length of the common input string suffix of the protocol state, and whether the protocol entity produces the same output result when receiving the same input, if two protocol states have the longest length of their common input string suffix, and for the same Inputs have the same output, such two protocol states will preferentially attempt to fuse. 3. The method according to claim 1, characterized in that, in the aforementioned method, the process of utilizing the test character string set to carry out state fusion and feasibility determination comprises the following steps: first according to the test character string and known message protocol Format, generate the input message sequence as a test case; send the input message sequence to the protocol entity program, and obtain the output message sequence as a response; abstract the output message sequence and express it as an output string sequence; The protocol state machine after the fusion of candidate states judges whether the output characters in the output string sequence exist in the output symbol set corresponding to the state of the protocol state machine: if all the output strings are consistent with the fused protocol state machine, the state is considered Fusion is feasible, otherwise it is judged that state fusion is not feasible.