Branch coverage guided symbolic execution for hybrid fuzz testing of software binaries

• US 10,635,576 B2
• Filed: 06/18/2018
• Issued: 04/28/2020
• Est. Priority Date: 06/18/2018
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Phan, Quoc-Sang, Murthy, Praveen
• Primary Examiner(s): Lee, Adam
• Application Number:
  US16/010,722
• Publication Number:
  US 20190384697A1
• Time in Patent Office: 680 Days
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 11/3676 for coverage analysis
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites

Abstract

According to some examples, computer-implemented methods for branch coverage guided symbolic execution for hybrid fuzzing are described. An example computer-implemented method may include receiving a seed input of a binary program under analysis (BPUA) that is discovered during testing by a greybox fuzzer. The method may also include concretely executing the seed input in the BPUA, and collecting a trace resulting from the concrete execution of the seed input. The method may further include determining whether the concrete execution of the seed input discovers a new branch. The method may include, responsive to a determination that the concrete execution of the seed input discovers a new branch, updating a bitmap to indicate that the new branch is discovered, wherein the bitmap is utilized by the greybox fuzzer to maintain a record of discovered branches in BPUA, and providing the seed input to the greybox fuzzer.

Claims

1. A computer-implemented method for branch coverage guided symbolic execution for hybrid fuzzing, the method comprising:

receiving, at a symbolic execution engine, a seed input of a binary program under analysis (BPUA) that is discovered during testing of the BPUA by a greybox fuzzer;

concretely executing, at the symbolic execution engine, the BPUA using the seed input;

collecting a trace resulting from the concrete execution by the symbolic execution engine of the BPUA using the seed input;

determining a number of new branches discovered by the concrete execution of the BPUA using the seed input by comparing branches executed in the trace to a bitmap indicative of discovered branches previously discovered during prior executions of the BPUA by the greybox fuzzer and the symbolic execution engine; and

responsive to a determination that the concrete execution of the BPUA using the seed input discovers at least one new branch;

updating the bitmap to indicate that the new branch is discovered, wherein the bitmap is utilized by the greybox fuzzer and the symbolic execution engine during the testing of the BPUA to maintain a record of discovered branches in the BPUA;

assigning a priority to the seed input based on the number of new branches discovered;

providing the seed input to a priority queue;

after obtaining the seed input from the priority queue according to the assigned priority, symbolically executing the BPUA along the trace using a symbol of the seed input;

collecting one or more constraints satisfied along the trace symbolically executed through the BPUA, wherein at least one of the one or more constraints is used to transform the seed input; and

providing the transformed seed input to the greybox fuzzer.

2. The method of claim 1, further comprising, responsive to a determination that the concrete execution of the BPUA using the seed input discovers at least one new branch:

negating a constraint of the one or more satisfied constraints;

determining whether the negated constraint is satisfiable;

responsive to a determination that the negated constraint is satisfiable;

generating a model that solves the negated constraint;

generating a new input using the model; and

providing the new input to the greybox fuzzer for execution.

3. The method of claim 2, wherein providing the new input to the greybox fuzzer comprises:

assigning a fuzzing priority to the new input; and

providing the new input to a fuzzing priority queue such that the new input is retrieved according to the assigned fuzzing priority.

4. The method of claim 1, further comprising, responsive to a determination that the concrete execution of the BPUA using the seed input does not discover a new branch, discarding the seed input.

5. The method of claim 1, wherein the seed input is an arbitrary input.

6. A computer program product including one or more non-transitory machine-readable mediums encoded with instruction that when executed by one or more processors cause a process to be carried out for branch coverage guided symbolic execution for hybrid fuzzing, the process comprising:

receiving, by a symbolic execution engine, a seed input of a binary program under analysis (BPUA) that is discovered during testing of the BPUA by a greybox fuzzer;

concretely executing, by the symbolic execution engine, the BPUA using the seed input;

collecting, by the symbolic execution engine, a trace resulting from the concrete execution of the BPUA using the seed input;

determining, by the symbolic execution engine, a number of new branches discovered by the concrete execution of the BPUA using the seed input by comparing branches executed in the trace to a bitmap indicative of discovered branches previously discovered during prior executions of the BPUA by the greybox fuzzer and the symbolic execution engine; and

responsive to a determination that the concrete execution of the BPUA using the seed input discovers at least one new branch;

updating, by the symbolic execution engine, the bitmap to indicate that the new branch is discovered, wherein the bitmap is utilized by the greybox fuzzer and the symbolic execution engine during the testing of the BPUA to maintain a record of discovered branches in BPUA;

assigning a priority to the seed input based on the number of new branches discovered;

providing the seed input to a priority queue;

after obtaining the seed input from the priority queue according to the assigned priority, symbolically executing the BPUA along the trace using a symbol of the seed input;

collecting one or more constraints satisfied along the trace symbolically executed through the BPUA, wherein at least one of the one or more constraints is used to transform the seed input;

placing the transformed seed input in a fuzzing queue; and

providing the transformed seed input to the greybox fuzzer.

7. The computer program product of claim 6, the process further comprising, responsive to a determination that the concrete execution of the BPUA using the seed input discovers at least one new branch:

negating, by the symbolic execution engine, a constraint of the one or more constraints satisfied by the seed input;

determining, by the symbolic execution engine, whether the negated constraint is satisfiable;

responsive to a determination that the negated constraint is satisfiable;

generating, by the symbolic execution engine, a model that solves the negated constraint;

generating, by the symbolic execution engine, a new input using the model; and

providing the new input to the greybox fuzzer for execution.

8. The computer program product of claim 6, wherein the fuzzing queue is a fuzzing priority queue, wherein placing the transformed seed input in the fuzzing priority queue comprises assigning a fuzzing priority to the transformed seed input, and wherein the transformed seed input is retrieved according to the assigned fuzzing priority.

9. The computer program product of claim 6, the process further comprising, responsive to a determination that the concrete execution of the BPUA using the seed input does not discover a new branch, discarding the seed input.

10. A system to perform branch coverage guided symbolic execution for hybrid fuzzing, the system comprising:

one or more non-transitory machine-readable mediums configured to store instructions; and

one or more processors configured to execute the instructions stored on the one or more non-transitory machine-readable mediums, wherein execution of the instructions causes the one or more processors to;

receive a seed input of a binary program under analysis (BPUA) that is discovered during testing of the BPUA by a greybox fuzzer;

concretely execute the BPUA using the seed input;

collect a trace resulting from the concrete execution of the BPUA using the seed input;

determine a number of new branches discovered by the concrete execution of the BPUA using the seed input by comparing branches executed in the trace to a bitmap indicative of discovered branches previously discovered during prior executions of the BPUA by the greybox fuzzer; and

responsive to a determination that the concrete execution of the BPUA using the seed input discovers at least one new branch;

update a bitmap to indicate that the new branch is discovered, wherein the bitmap is utilized by the greybox fuzzer during the testing of the BPUA to maintain a record of discovered branches in BPUA;

assign a priority to the seed input based on the number of new branches discovered;

provide the seed input to a priority queue;

after obtaining the seed input from the priority queue according to the assigned priority, symbolically execute the BPUA along the trace using a symbol of the seed input;

collect one or more constraints satisfied along the trace symbolically executed through the BPUA, wherein at least one of the one or more constraints is used to transform the seed input;

place the transformed seed input in a fuzzing queue; and

provide the transformed seed input to the greybox fuzzer.

11. The system of claim 10, wherein execution of the instructions causes the one or more processors to, responsive to a determination that the concrete execution of the BPUA using the seed input discovers at least one new branch:

negate a constraint of the one or more constraints satisfied by the seed input;

determine whether the negated constraint is satisfiable;

responsive to a determination that the negated constraint is satisfiable;

generate a model that solves the negated constraint;

generate a new input using the model; and

providing the new input to the greybox fuzzer for execution.

12. The system of claim 11, wherein the fuzzing queue is a fuzzing priority queue, wherein placing the transformed input seed in the fuzzing priority queue comprises assigning a fuzzing priority to the transformed seed input, and wherein the transformed seed input is retrieved according to the assigned fuzzing priority.

13. The system of claim 10, wherein execution of the instructions causes the one or more processors to, responsive to a determination that the concrete execution of the BPUA using the seed input does not discover a new branch, discard the seed input.