## 2 Background
### Hybrid Fuzzing  
Hybrid fuzzing was firstly introduced in 2007 [15] and then brought to the public as a hot topic by [PERSON] [9] in 2016. Both works used the demand launch strategy, which starts the fuzzing in the beginning, then when the fuzzing process gets stuck, concolic execution is triggered to analyze the selected inputs and negate branches to get new test cases, which can introduce new coverage. There are two disadvantages in this demand launch strategy, as described in DigFuzz [11]. Firstly, it is hard to define the state of \"stuck\". In the experiments of DigFuzz, for most of the testing programs, concolic execution is never triggered in the predefined test time because the fuzzer never becomes \"stuck\". Secondly, because of the bad efficiency of concolic execution, it takes too long to analyze even only one input, which makes the overall performance worse than pure fuzzing in some cases. MDPC [19] proposes a new strategy called optimal switch, which uses the optimal decision on which branches to solve by concolic execution. More specifically, the MDPC algorithm calculates the complexity for every branch in terms of solving, then decides which branches will be solved by concolic execution and which branches will be solved by fuzzing. The problem of this work is that the optimal decision costs too much overhead since the analysis is performed on every branch. However, this work is still important because it firstly introduced the concept of branch scheduling to hybrid fuzzing. DigFuzz [11] uses the same strategy as MDPC, which also calculates branch complexity, but with a smarter algorithm called MCP3. By considering fuzzing as a process of random sampling, this algorithm builds an execution tree with probabilities between different branches. For each branch on the execution tree, there is a probability to get the result of this branch by fuzzing. Thus, the probability of one path will be the product of all branches along this path. DigFuzz uses coverage statistics from AFL to build this execution tree for the whole program execution paths and schedule branches for fuzzing and concolic execution based on the probabilities calculated from the tree. For concolic execution, it will find the inputs that contain target branches and perform concolic execution on those inputs. There are a few problems that DigFuzz fails to solve. Firstly, it is still an optimized version of the demand launch strategy, which means concolic execution is not triggered as much as possible, at least not enough compared with the synchronization method. Secondly, it chooses the hardest-to-solve branches without considering unexplored coverage. Even though the selected branches are solved by concolic execution, there is a big chance that they may not contribute to the coverage or finding vulnerabilities. Thirdly, it fails to consider the solvability of the target branch, i.e., it fails to know if each branch has a solvable valid descendant path. Our work is based on a more scalable and efficient synchronization strategy, which utilizes the power of multi-core CPUs. QSYM [10] is the state-of-the-art hybrid fuzzing work that provides an efficient concolic execution engine. Benefiting from the fast concolic execution engine, QSYM uses synchronization mode to collaborate with the AFL fuzzer by generating new test cases all the time in parallel with fuzzing. Even though this strategy can analyze much more inputs and branches than demand launch and optimal switch, input and branch scheduling is still very important. As we explained in the previous section, only a small amount of the candidate inputs will be analyzed in a 12 h hybrid fuzzing process. QSYM uses a naive approach to select inputs, by four metrics: (a) smaller inputs are favored; (b) the newer generated inputs are favored; (c) the inputs with new coverage are favored; (d) the original inputs are important. There is no coverage guidance on this input selection strategy, nor any branch selection method.