Method and apparatus for generating test case for fuzz test

Technical field

The present invention relates to the technical field of software security testing, and in particular to a method and apparatus for generating a test case for a fuzz test.

Background art

Black-box testing is a commonly used security testing method for software, which has achieved widespread use in software security testing on account of its lack of dependence on the program source code of the software under test and the fact that it is always able to detect security loopholes that have been overlooked by test personnel.

Fuzz testing is a black-box test technique which appeared in the 1990s. This technique constructs items of random or semi- random data (called fuzz) to serve as input to the software under test, and monitors the response and/or state of the software under test in order to determine whether there exist security loopholes in the software under test. As a black-box testing tool, fuzz testing is generally used for large-scale software development projects, as it has the following advantages: the testing can be performed at a comparatively low cost, and completely automatically; and fuzz testing can often find relatively serious security loopholes which could be exploited by attackers.

Owing to the rapid development and widespread use of network and communication technologies, security testing of protocol implementation, such as communication protocol and industrial control protocol implementation, is an important issue in the field of software security testing at present. One of the major reasons for security loopholes in protocol implementation is abnormal processing of input data; examples of security issues caused by abnormal processing include buffer overflow attacks, format string attacks and code injection attacks.

Fuzz testing of protocol implementation is generally based on characters. Even if certain input fields of the protocol under test are based on a binary bitstream, this binary bitstream can be converted to a data stream in the form of characters for testing. Therefore a test case inputted to a protocol under test is generally a random or semi-random string. Since this string is significantly different from legitimate content which meets the protocol standard, the protocol under test is unable to parse it correctly, or may discover that it is an illegitimate input, and therefore reject the test case. Thus, the use of such a test case to perform fuzz testing not only results in low test efficiency, but also makes it very difficult to detect deep-level security loopholes inside the protocol under test.

A fuzz testing method is presented in US patent application US20090164975A1. Certain input data of a system under test has undergone encoding in a specific way, e.g. this portion of input data may have undergone Base64 encoding or forward error correction (FEC) encoding. In view of this, this portion of input data may, after being randomized (fuzzed) , be unable to be decoded by the system under test. Even if it can be decoded, the decoded data may lose the original format or be unable to be parsed. Therefore the method in the abovementioned patent application comprises: receiving formatted data for processing by the system under test; determining the method used to encode the formatted data and selecting a portion of the data for fuzzing; on the basis of the encoding method, determining an appropriate decoder to decode the selected data; fuzzing the decoded data; on the basis of the encoding method, determining an appropriate encoder to encode the fuzzed data; and using the encoded fuzzed data to test the system under test. Although this method takes into account the specific way in which certain input data of the system under test is encoded, the fuzzed input data may still be significantly different from normal input data in terms of format, so the problem of rejection by the system under test will similarly be faced.

Content of the invention

In response to the above problem, in order to increase the level of similarity between a test case in fuzz testing and input data of the system under test, the embodiments of the present invention propose a method and apparatus for generating a test case for fuzz testing.

The method for generating a test case for fuzz testing according to the embodiments of the present invention comprises : determining a grammatical structure of an input field of a system under test according to legitimate content of the input field, the grammatical structure of the input field comprising a special character in the field and the position thereof; generating an abnormal case according to a set generation method, and determining a grammatical structure of the abnormal case generated, the grammatical structure of the abnormal case comprising a special character in the abnormal case and the position thereof; comparing the grammatical structure of the abnormal case with the grammatical structure of the input field; if the grammatical structure of the abnormal case has at least one special character in the same position as at least one special character in the grammatical structure of the input field, using the abnormal case as a test case of the system under test. An apparatus for generating a test case for fuzz testing according to the embodiments of the present invention comprises : an input field grammatical structure determination unit, for determining a grammatical structure of an input field of a system under test according to legitimate content of the input field, the grammatical structure of the input field comprising a special character in the field and the position thereof; an abnormal case generation and grammatical structure determination unit, for generating an abnormal case according to a set generation method, and determining a grammatical structure of the abnormal case generated, the grammatical structure of the abnormal case comprising a special character in the abnormal case and the position thereof; a comparison unit, for comparing the grammatical structure of the abnormal case with the grammatical structure of the input field; a filtering unit, for using the abnormal case as a test case of the system under test when the grammatical structure of the abnormal case has at least one special character in the same position as at least one special character in the grammatical structure of the input field.

In the method and apparatus provided by the embodiments of the present invention, at least one special character in the chosen test case has the same position as at least one special character in the legitimate content of the input field, and the special character and position thereof can determine the grammatical structures of the test case and the input field. Thus, there is a certain degree of similarity in terms of format between the chosen test case and the legitimate content of the input field, and there is a greater likelihood of such a test case passing a grammar check of the system under test or being able to be successfully parsed after being inputted to the system under test. Thus instances of rejection of test cases by the system under test can be reduced, to achieve higher efficiency and more comprehensive security testing.

Description of the accompanying drawings

To give those skilled in the art a clearer understanding of the above and other features and advantages of the present invention, illustrative embodiments thereof will be described in detail below with reference to the accompanying drawings, in which :

Fig. 1 is a schematic flow chart of a test case generating method according to the embodiments of the present invention;

Fig. 2 is a schematic diagram of a prefix tree automaton of an input field in an embodiment of the present invention;

Fig. 3 is a schematic diagram of a prefix tree automaton of an input field in another embodiment of the present invention;

Fig. 4 is a schematic diagram of a prefix tree automaton of an abnormal case in an embodiment of the present invention;

Fig. 5 is a schematic diagram of a prefix tree automaton of an abnormal case in another embodiment of the present invention;

Fig. 6 is a schematic diagram of the structure of a test case generating apparatus according to an embodiment of the present invention ;

Fig. 7 is a schematic diagram of the structure of a test case generating device according to an embodiment of the present invention . Particular embodiments

The above characteristics, technical features and advantages of the present invention, together with ways of implementing the same, are illustrated further below in a clear and easily understood way, by explaining preferred embodiments with reference to the accompanying drawings.

The embodiments of the present invention propose a method for generating a test case for fuzz testing. As Fig. 1 shows, the method comprises the following steps:

Step 101: determining a grammatical structure of an input field of a system under test according to legitimate content of the input field, the grammatical structure of the input field comprising a special character in the field and the position thereof .

In the embodiments of the present invention, the system under test may be software written in computer code such as an application program or protocol implementation, but will hereinafter be referred to generally as the system under test.

Legitimate content of an input string of the system under test must conform to a definite grammatical structure, depending on the particular application scenario or protocol standard. The so-called grammatical structure refers to grammar rules which should be satisfied by the legitimate content of the input field; in the embodiments of the present invention, the grammar rules include a special character in the field and the position thereof. Here, the special character may be any symbol for special use other than small letters, capital letters and numerals. The special characters in the legitimate content of the input field will vary with the operating system, protocol standard and/or programming language used by the system under test. For example, in the C/C++ programming language, represents the start of a format string; in the PADIS (Passenger and Airport Data Interchange Standards) protocol, represents a separator for data elements.

Step 102: generating an abnormal case according to a set generation method, and determining a grammatical structure of the abnormal case generated, the grammatical structure of the abnormal case comprising a special character in the abnormal case and the position thereof.

In this step, a set generation method can be used to generate an abnormal case. For instance, most simply, abnormal cases may be generated in a random manner, and the randomly generated abnormal cases can then be filtered by an existing method, to remove similar abnormal cases, so that the test cases can cover the input space of the system under test more comprehensively, in order to increase the efficiency of fuzz testing. Alternatively, a more intelligent method, such as the fuzz testing method in the patent application mentioned above, may be used to generate an abnormal case. In the embodiments of the present invention, no restriction is imposed on the method used to generate an abnormal case.

The grammatical structure of the abnormal case generated is similarly analyzed, to determine a special character in the abnormal case and the position thereof.

Step 103: comparing the grammatical structure of the abnormal case with the grammatical structure of the input field.

Next, the special characters appearing in the abnormal case and input field and the positions thereof are compared.

Step 104: if the grammatical structure of the abnormal case has at least one special character in the same position as at least one special character in the grammatical structure of the input field, using the abnormal case as a test case for the system under test. If comparison shows that the grammatical structure of the abnormal case has one or more special characters in the same position as one or more special characters in the grammatical structure of the input field, the abnormal case is used as a test case for the fuzzy test.

In the above method provided in the embodiments of the present invention, at least one special character in the chosen test case has the same position as at least one special character in the legitimate content of the input field, and the special character and position thereof can determine the grammatical structures of the test case and the input field. Thus, there is a certain degree of similarity in terms of format between the chosen test case and the legitimate content of the input field, and there is a greater likelihood of such a test case passing a grammar check of the system under test or being able to be successfully parsed after being inputted to the system under test. Thus instances of rejection of test cases by the system under test can be reduced, to achieve higher efficiency and more comprehensive security testing.

In another embodiment according to the present invention, priority levels can be set for test cases; the greater the number of special character positions which are the same in the grammatical structure of a test case as in the grammatical structure of the input field, the higher the priority level of the test case. A greater number of special character positions which are the same indicates a higher degree of format similarity between the test case and the legitimate content of the input field, and a lower likelihood of the test case being rejected; therefore the test case can take precedence in being tested .

During specific implementation, a number of threshold ranges can be set to correspond to the priority levels required. For example, threshold ranges of n < A, A ≤ n ≤ B and n > B could be set to correspond to priority levels 1, 2 and 3, respectively, where n represents the number of special character positions which are the same, and A and B are set values. When the number of special character positions which are the same in the grammatical structure of a test case as in the grammatical structure of the input field is less than threshold A, the test case has a priority level of 1, and so on. A test case with a higher priority level will take precedence for use in fuzz testing.

In another embodiment according to the present invention, if the position of at least one special character in the grammatical structure of an abnormal case used as a test case is the same as the position of at least one special character in the grammatical structure of the input field, and the special characters themselves are the same, a higher priority level may be set for the test case. Specifically, a main priority level can for example be set first according to the number of special character positions which are the same in the grammatical structure of a test case as in the grammatical structure of the input field; a secondary priority level can then be further set according to the number of special characters which are the same, under the same main priority level condition. The greater the number of special characters which are the same, the higher the secondary priority level.

In addition, phrases in the input field and values thereof can be determined according to legitimate content of the input field; and phrases in the abnormal case generated and values thereof can be determined. The phrases are separated by special characters; here, the phrases may be small letters, capital letters or numerals, and may also be strings consisting of small letters, capital letters and/or numerals.

If the grammatical structure of an abnormal case generated has at least one special character in the same position as at least one special character in the grammatical structure of the input field, i.e. the abnormal case will be used as a test case, then a further comparison can be made of the values of phrases for which the at least one special character is a prefix/suffix in the test case and the legitimate content of the input field. If the phrases for which the at least one special character is a prefix/suffix have the same value, a higher priority level can be set for the test case, so it can take precedence for use in fuzz testing. Specifically, a main priority level can for example be set first according to the number of special character positions which are the same in the grammatical structure of a test case as in the grammatical structure of the input field; a secondary priority level can then be further set according to the number of phrases with the same value. The greater the number of phrases with the same value, the higher the secondary priority level.

There are generally two types of input field of a system under test: fixed-length input fields and variable-length input fields. The length of a variable-length input field can be characterized by a length field or a specific end symbol, etc. Special characters mostly appear in variable-length input fields; in different input data of a system under test, variable-length input fields may have different lengths and different content. All possible legitimate content of a variable-length input field can be represented by prefix tree automata (PTA) , deterministic finite automata (DFA) or regular expressions .

For example, a PTA is used to represent all possible legitimate content of a variable-length input field, wherein each state (i.e. node) represents a phrase appearing in the legitimate content of the field, and a transfer between states represents a special character separating phrases. Starting at an initial state of the PTA, a state transfer path of the PTA is moved along until a final state is reached, to give an output result of one possible legitimate content of the input field. Suppose that a variable-length input field may have three legitimate inputs, namely "A/B/C", "A/C" and "A/B/D"; then the PTA generated for the input field can be represented as shown in Fig. 2.

The nodes "A", "B", "C" and "D" are the different states of the PTA, representing the phrases which may appear in the legitimate content of the field. The transfers between states represented by the arrows are special characters separating phrases. Starting at the initial state "A" of the PTA, a state transfer path of the PTA is moved along until the final state "D" is reached, to give an output result of one possible legitimate input, "A/B/D". By the same principle, the remaining two possible legitimate inputs "A/B/C" and "A/C" can also be obtained .

Now we shall take a format string input field in the C language as an example, taking three possible kinds of legitimate content of the input field, namely "%s%d", "%.16x" and "%*x", as an example. The special characters which appear in these three possible kinds of legitimate content ", and

"*", and the PTA of the input field obtained by analyzing these kinds of legitimate content can be represented as shown in Fig. 3.

In the figure, an "0" node indicates that the phrase represented by the node is an empty string.

As stated above, an input field of a system under test can generally be represented in the form of characters. Correspondingly, an abnormal case generated may comprise one or more of a super-long string, a format string and a code/script string, corresponding to safety loopholes such as a buffer overflow attack, a format string attack and a code injection attack, respectively. Particular embodiments of the present invention will be explained further below, taking as examples the cases where the abnormal case is a super-long string and a format string.

In the first example, the abnormal case is a super-long string:

With an abnormal case in the super-long string category, an attempt is made to use a string with a length (far exceeding that) permitted by legitimate content to cause a buffer overflow anomaly to occur during processing of input data by the system under test. Suppose that the abnormal cases generated in this embodiment are as follows:

AAA... AAA/EEEE ... EEEE

AAA... AAA/BBB ...BBB/CCC... CCC

AAA... AAA@DDD ... DDD

Here, "AAA...AAA" etc. represents a very long string (much bigger than 1 character) consisting of the capital letter ^λ Α' , etc. Thus the abnormal case PTAs obtained by analyzing these abnormal cases can be represented as shown in Fig. 4.

Suppose that the PTA of the input field in this embodiment is as shown in Fig. 2. Comparison of Fig. 2 with Fig. 4 shows that the abnormal case "AAA... AAA/BBB ... BBB/CCC ... CCC" and the legitimate content "A/B/D" each comprise three phrases, with two adjacent phrases being separated by the special character "/" in each. Thus the abnormal case

"AAA...AAA/BBB...BBB/CCC...CCC" and the legitimate content "A/B/D" have the same grammatical structure, i.e. the special characters appearing therein and the positions thereof are exactly the same; similarly, the abnormal case "AAA...AAA/EEEE ...EEEE" and the legitimate content "A/C" have the same grammatical structure. Since these abnormal cases have exactly the same format as the corresponding legitimate content, there is a greater likelihood of such abnormal cases passing a grammar check of the system under test or being able to be successfully parsed, so instances of rejection by the system under test can be reduced. Thus, these abnormal cases will readily be regarded as normal input data by the system under test. However, super-long strings such as "AAA...AAA" may cause buffer overflow to occur with the input data of the system under test, so if these abnormal cases are used as test cases to perform fuzz testing on the system under test, buffer overflow loopholes in the system under test may be found, and so the effectiveness of fuzz security testing can be increased, as can the efficiency of the testing process.

Since the special characters appearing in the test cases "AAA...AAA/BBB...BBB/CCC...CCC" and "AAA ... AAA/EEEE ... EEEE" are exactly the same as those appearing in the corresponding legitimate content, and are in exactly the same positions, these two test cases can take precedence for use in fuzz testing .

The special characters appearing in the abnormal case "AAA... AAA@DDD... DDD" and in the legitimate input data "A/C" are not the same, being "@" and "/", respectively, but they are in the same positions; in other words, the abnormal case "AAA... AAA@DDD... DDD" and the legitimate content "A/C" have similar grammatical structures. Thus, this abnormal case can also be used in fuzz testing as a test case, but the priority level thereof can be lower than that of the two test cases above, "AAA... AAA/BBB ... BBB/CCC ... CCC" and

"AAA...AAA/EEEE...EEEE".

In the next example, the abnormal case is a format string:

The purpose of an abnormal case in the format string category is to perform security testing on an input field for which no format string has been specified, such as input data of a function such as printf, by means of an abnormal format string. Suppose that the abnormal cases generated in this embodiment are as follows: AAAA

^' "°o- 2o-HU-2o- 2o-iHl ^/'

"%.4096d"

"% * * * *d"

Then the PTAs obtained by analyzing these abnormal cases can be represented as shown in Fig. 5.

Suppose that the PTA of the input field in this embodiment is as shown in Fig. 3. Comparison of Fig. 3 with Fig. 5 shows that the abnormal 4096d" and the legitimate content "%.16x" have the same grammatical structure, i.e. the special characters appearing therein and the positions thereof are exactly the same. However, of the phrases for which the special character is a prefix in these two, 4096 has a far greater value than 16, and this could lead to an anomaly in allocation of memory by a function such as printf. Thus, by using this abnormal case as a test case to perform fuzz testing on the system under test, instances of rejection of test cases by the system under test can be reduced, and format string loopholes in the system under test can be found, making the testing process more effective.

The prefixes ("%s%d", "%*") j_ _n the abnormal test cases "%s%d%s%d" and "%****d" have the same grammatical structures as the legitimate content "%s%d" and "%*x", i.e. special characters appearing therein and the positions thereof are the same, thus the abnormal test cases "%s%d%s%d" and "%****d" can also be used for fuzz testing.

The grammatical structure of the abnormal case "AAAA" shows no similarity to the grammatical structure of any possible legitimate content, so can be discarded and not used for fuzz testing, to save testing time and test resources. Particular embodiments of the method of the present invention have been explained in detail above.

The embodiments of the present invention also propose an apparatus for generating a test case for fuzz testing. As Fig. 6 shows, the apparatus 60 may be realized using software, hardware or a combination of software and hardware, and may specifically comprise: an input field grammatical structure determination unit 601, for determining a grammatical structure of an input field of a system under test according to legitimate content of the input field, the grammatical structure of the input field comprising a special character in the field and the position thereof; an abnormal case generation and grammatical structure determination unit 602, for generating an abnormal case according to a set generation method, and determining a grammatical structure of the abnormal case generated, the grammatical structure of the abnormal case comprising a special character in the abnormal case and the position thereof; a comparision unit 603, for comparing the grammatical structure of the abnormal case with the grammatical structure of the input field; a filtering unit 604, for using the abnormal case as a test case of the system under test when the grammatical structure of the abnormal case has at least one special character in the same position as at least one special character in the grammatical structure of the input field.

In a particular embodiment of the apparatus of the present invention, the filtering unit 604 may be further used for setting a priority level for a test case, wherein the greater the number of special character positions which are the same in the grammatical structure of an abnormal case used as a test case as in the grammatical structure of the input field, the higher the priority level of the test case.

In another embodiment of the apparatus of the present invention, the filtering unit 604 may also be used for setting a higher priority level for a test case when the position of at least one special character in the grammatical structure of the abnormal case used as the test case is the same as the position of at least one special character in the grammatical structure of the input field, and the special characters themselves are the same.

In another embodiment of the apparatus of the present invention, the input field grammatical structure determination unit 601 may also be used for determining phrases in the input field and values thereof according to legitimate content of the input field, the phrases being separated by a special character in the input field.

The abnormal case generation and grammatical structure determination unit 602 may also be used for determining phrases in the abnormal case generated and values thereof, the phrases being separated by a special character in the abnormal case.

The comparison unit 603 may also be used, when the grammatical structure of the abnormal case has at least one special character in the same position as at least one special character in the grammatical structure of the input field, for further comparing the values of phrases for which the at least one special character is a prefix/suffix in the abnormal case and the legitimate content.

The filtering unit 604 may also be used for setting a higher priority level for the test case when the values of the phrases for which the at least one special character is a prefix/suffix are the same. Since particular embodiments of the method of the present invention have been explained in detail above, particular embodiments of the apparatus of the present invention may be understood by referring to the corresponding explanations of the method of the present invention, which will not be repeated here superfluously.

The embodiments of the present invention also provide a device for generating a test case for fuzz testing. As Fig. 7 shows, the device may be realized by a single physical entity, or be part of any physical entity used for fuzz testing.

As Fig. 7 shows, the device for generating a test case for fuzz testing 70 may comprise a memory 701 and a processor 702. The memory 701 may be used for storing executable commands. The memory 702 may be used for performing the following steps according to the executable commands stored in the memory 701: determining a grammatical structure of an input field of a system under test according to legitimate content of the input field, the grammatical structure of the input field comprising a special character in the field and the position thereof; generating an abnormal case according to a set generation method, and determining a grammatical structure of the abnormal case generated, the grammatical structure of the abnormal case comprising a special character in the abnormal case and the position thereof; comparing the grammatical structure of the abnormal case with the grammatical structure of the input field; using the abnormal case as a test case of the system under test when the grammatical structure of the abnormal case has at least one special character in the same position as at least one special character in the grammatical structure of the input field . Furthermore, priority levels may be set for test cases, wherein the greater the number of special character positions which are the same in the grammatical structure of an abnormal case used as a test case as in the grammatical structure of the input field, the higher the priority level of the test case.

If the position of at least one special character in the grammatical structure of an abnormal case used as a test case is the same as the position of at least one special character in the grammatical structure of the input field, and the special characters themselves are the same, then a higher priority level may be set for the test case.

In addition, phrases in the input field and values thereof can also be determined according to legitimate content of the input field, the phrases being separated by a special character in the input field; and phrases in the abnormal case generated and values thereof can be determined, the phrases being separated by a special character in the abnormal case. When the grammatical structure of the abnormal case has at least one special character in the same position as at least one special character in the grammatical structure of the input field, the values of phrases for which the at least one special character is a prefix/suffix in the abnormal case and the legitimate content are compared. When the values of the phrases for which the at least one special character is a prefix/suffix are the same, a higher priority level is set for the test case.

The embodiments of the present invention also provide a machine-readable medium, on which executable commands are stored; when the executable commands are executed, a machine is made to perform the steps performed by the abovementioned processor 702. Specifically, a system or apparatus equipped with a storage medium may be provided, wherein software program code realizing the functions of any one of the above embodiments is stored on the storage medium, and a computer (or CPU or MPU) of the system or apparatus reads and executes the program code stored in the storage medium.

In this case, the program code read from the storage medium is itself capable of realizing the functions of any one of the above embodiments, hence the program code and the medium on which the program code is stored form part of the present invention .

Examples of machine-readable media used to provide program code include floppy disks, hard disks, magneto-optical disks, optical disks (e.g. CD-ROM, CD-R, CD-RW, DVD-ROM, DVD-RAM, DVD- RW, DVD+RW) , magnetic tape, non-volatile memory cards and ROM. Optionally, a communication network may download program code from a server computer.

In addition, it should be clear that not only can part or all of an actual operation be completed by executing program code read out by a computer, but an operating system operating on a computer can also be made to complete part or all of the actual operation by means of commands based on the program code, so as to realize the function of any one of the above embodiments.

In addition, it can be appreciated that program code read out from the storage medium is written into a memory installed in an expansion board inserted in the computer, or written into a memory installed in an expansion unit connected to the computer, and thereafter commands based on the program code make a CPU etc. installed on the expansion board or expansion unit execute part or all of an actual operation, so as to realize the function of any one of the above embodiments.

It must be explained that not all of the steps and modules in the schematic diagrams mentioned above are necessary; certain steps or modules may be omitted depending on actual requirements. The order in which steps are performed is not fixed, but may be adjusted as required. The modular structures described in the above embodiments may be physical structures or logic structures, i.e. certain modules may be realized by the same physical entity, or realized separately by multiple physical entities, or realized jointly by certain components in multiple independent devices.

The present invention has been presented and explained in detail above by way of accompanying drawings and embodiments. However, the present invention is not restricted to these disclosed embodiments; other solutions derived therefrom by those skilled in the art are also within the scope of protection of the present invention. Therefore the scope of protection of the present invention should be defined by the attached claims.