## 3 Design
### Overview
#### 3.1.1 Step 1: Select Inputs from the Slave Fuzzer Queue for Further Analysis  
In general, the SHF approach first chooses the critical branches and then selects the inputs with those branches to be analyzed by concolic execution. To calculate the critical scores of different branches, we need the information from running each input and analyzing each branch. Thus, the order of choosing inputs is important, because, for the branches chosen by an earlier analyzed input, they will not appear in the later analyzed ones. We take advantage of the input selection method used by QSYM, which is not mentioned in the paper, but in the source code [27]. The difference is that QSYM directly uses this method to select inputs for concolic execution, but we choose inputs in this order just to analyze the critical scores of different branches. We will then give a new execution order of inputs and related target branches by the information we get from further analysis. In the first step, we choose inputs from the slave fuzzer queue in the order considering the following four facts:  
* Inputs with new coverage are favored. If there is a \"+cov\" label in the inputs, it means that this input can introduce new coverage to the fuzzing process. We prioritize these inputs so that we can get more unexplored branches to analyze. * The bigger inputs are favored. Normally, a bigger input means a longer execution path, therefore more new branches to explore. This is different from QSYM because it chooses inputs from the smallest size, for the reason that concolic execution on big inputs takes a very long time. We tested on one input and found out that the execution time increases dramatically as the input gets bigger, which is because there are too many branches to solve. Our approach only analyzes the critical branches instead of all of them, which mitigates this problem greatly. Thus, we can choose the largest sized inputs instead of the smaller sized ones to increase the length of the execution path. * The newer generated inputs are favored. This fact is easy to understand because the newly generated inputs may have more information about the unexplored branches and code. In the AFL fuzzer queue, the newer generated inputs have bigger id numbers, which is easy to track. * The original seed inputs are important. The seed inputs contain the most important information such as the file format. If we only apply the above three methods, then we will miss those original inputs. Thus, we prioritize the inputs with the \"orig\" label in the slave fuzzer queue. At the end of this step, we will have an input list for further analysis, which is denoted as _input_list_ in Algorithm 1. Figure 2: Overview of the Selective Hybrid Fuzzing (SHF) framework based on the AFL synchronization method. 1.2 Step 2: Calculate the Priority Score of Each Input and Related Target Branches by the Two Main Algorithms  
In this step, we analyze each input in the order described in Step 1, calculate the critical score of each branch in one input by the Critical Branch Selection (CBS) algorithm, and select the target branches according to the score of each branch. Then, we give each input a priority score based on the target branches by the Priority Score Calculation (PSC) algorithm and output an input list that has order. The CBS and PSC algorithms are shown in Algorithm 1. This algorithm takes the input list that was calculated in the first step as the input and gives an ordering input list as the output. There are two essential parts of this algorithm, which need further explanation. Firstly, we use three metrics to evaluate how critical a branch is: hit(\(H\)), solvability(\(S\)), and complexity(\(C\)). \(H\) means if one branch is explored or hit. \(S\) means the solvability, i.e., whether this branch can be solved or not. \(C\) means the complexity, i.e., how hard it is to solve this branch. We will explain this part in detail later. Secondly, it matters how the priority score is calculated for each input and how we will select inputs from the ordering input list.