## 3 Design
### Critical Branch Selection
#### 3.2.1 Hit Accuracy  
The first assumption shows that we should always focus on the \"unexplored\" branches, which are destined to introduce new coverage by generating new test cases. In theory, we should choose branches that have never been analyzed before, instead of repeatedly executing the already solved branches from time to time, which will not introduce any new coverage. However, in practice, it is hard to distinguish the \"unexplored\" branches from the already solved ones.  
The problem originates from the coverage analysis, which we have explained in the previous section. For each branch with a particular address, we can not easily decide if this branch is already explored or not. We can see the problem clearly shown in Figure 3. Let us say if we have already solved Branch 3 once, by Input 1 guiding the execution path: (_A_, \(B\), \(D\), _E_), then we will have a new execution coverage: (_A_, \(B\), \(D\), _F_). Then, there is another Input 2 that can guide execution path: (_A_, \(C\), \(D\), _E_). This input can introduce new coverage because a new basic block \(C\) is executed. Now, the problem happens: should we analyze Branch 3 in Input 2? If we believe that Branch 3 has already been solved once and do not analyze this branch any more, then we will lose the execution path (_A_, \(C\), \(D\), _F_), which can be introduced by solving Branch 3 in Input 2. However, if we consider that Branch 3 under this situation is not explored, how can we distinguish it from the previously solved one in Input 1?  
In the Background section, we introduce different ways of calculating coverage. If we want to utilize a more precise calculation of coverage, then we should consider Branch 3 in different execution paths as differently-explored branches. To solve this problem, we propose the \"hit\" metric to measure if one branch is explored or not, which uses a new block-edge coverage tracing algorithm by dynamic binary instrumentation. We define the tuple (_previous branch, target branch_) as a unique branch. For example, in Figure 3, Branch 3 in Input 1 will be denoted as (_Branch 1_, _Branch 3_), while Branch 3 in Input 2 will be denoted as (_Branch 2_, _Branch 3_). Thus, the two different Branch 3s will be distinguished  
Figure 3: The problem of defining whether a branch is explored or not.  
well and both be analyzed by concolic execution. In this way, we can mitigate the imprecise problem of block coverage, which is caused by only considering the branch address as unique.  
We use a dynamic instrumentation tool to run each input and record the execution trace of all branches. When analyzing branches in concolic execution, we define the previous branch as the hash value of the current branch and record the previous branch value in a hash dictionary with the current branch as key and a previous branch value list as the hash value. In the _if_already_hit()_ function shown in Algorithm 1, when analyzing one branch, we will look up in the hash dictionary to see if this branch has a hash value in it. If not, then this branch is \"not hit\", and we will set the \(H\) value of this branch to zero. Otherwise, we will consider this branch as \"hit\" and set the \(H\) value to one.