## 3 Concepts and Methods
### Callgraph Division
Specifically, the weighted sum of the total number of branches contained in the function and the number of uncovered branches was used as this function's weight, as shown in the following formula: \[weight=\left\{ \begin{array}{ll}(\alpha B_{t}+\beta B_{uc})*\frac{B_{uc}}{ \gamma*B_{t}}&if\ function=main\\ \alpha B_{t}+\beta B_{uc}&otherwise\end{array} \right.\] (1) Among them, \(B_{t}\) represents the total number of branches contained in the current function. \(B_{uc}\) represents the number of uncovered branches in this function. \(\alpha\), \(\beta\), and \(\gamma\) are all constants (based on our experience and experiment, we selected a set of values that yield relatively good results: \(\alpha=1\), \(\beta=3\), \(\gamma=3\)). Since the \"main\" function serves as the entry point for every C/C++ program and will be explored by all fuzzing instances, its weight should be appropriately reduced. In addition, when the weight of a certain function is too large, [PERSON] algorithm would be unable to divide it, so the weight needs to be corrected. Specifically, the formula for correcting weights is as follows: \[finalWeight=\left\{ \begin{array}{ll}weight&if\ weight\leq\left\lfloor\frac{W_{t}}{n} \right\rfloor\\ \left\lfloor\frac{W_{t}}{n}\right\rfloor&otherwise\end{array} \right.\] (2) Among them, \(W_{t}\) represents the total weight of all functions that the target program has; the character \(n\) represents the number of subgraphs to be ultimately partitioned. 4. _Callgraph partition._ After obtaining the weight of each function (node) in the callgraph, the classic algorithm for tree partitioning named Lukes' algorithm was used to partition the whole callgraph into a large number of divisions with close internal relationships, as shown in Figure 4e. Further, the pseudocode for the callgraph partitioning algorithm is as follows (Algorithm 1):  
```
Input: Original CallGraph \(G\), Collected Seeds \(S\), Target Binary for Coverage \(T\) Output: CallGraph in Format of Minimum Spanning Tree \(MST\), A List Representing the Result of the Division plist function callgraphPartition(\(G\), \(S\), \(T\))  fileForTrace, fileForCoverage = setupFiles() // run the target with seeds collected in the last phase to obtain new function transfers and the coverage of every function in the target  for seed in \(S\)do  runTarget(\(T\), seed, fileForTrace, fileForCoverage)  endfor // add new functions and new function transfers to callgraph  for line in fileForTrace do  caller, callee, transfer = getInfo(line) ifthe caller/callee is not in \(G\)then  addNode(G, caller/callee)  endif  if the transfer is not in \(G\)then  addEdge(G, transfer)
```  
**Algorithm 1**CallGraph PartitionRemarks on the algorithm of callgraph division are as follows: Firstly, functions (nodes) and function call relationships (edges) that are unavailable from the static analysis were added to the callgraph by using the execution traces of seeds in the global seed corpus (lines 3 to 15). Secondly, the number of basic blocks, branches, and uncovered branches contained in each function was attached to each node in the callgraph (lines 17 to 20). Thirdly, duplicate edges (line 22) and function nodes without any basic blocks or those which cannot be reached from the \"main\" function (line 23) were deleted. Fourthly, the callgraph was transformed into the form of a minimum spanning tree (line 24). Then, the weight of each function node (line 26) was calculated and attached to each function node in the callgraph (line 27). Finally, [PERSON] algorithm was used to partition the callgraph into a massive collection of subgraph divisions (line 29).