×

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
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×