## 3 Concepts and Methods
### Callgraph Division  
Firstly, trim the initial callgraph of the tested program obtained during compilation and convert the trimmed callgraph into a minimum spanning tree. Then, use existing tree partitioning algorithms [35] to divide the converted callgraph into numerous subgraphs. Finally, merge the obtained subgraphs into a specified number of subtasks, where each subtask corresponds to a merged subgraph. The aforementioned task can be divided into two major steps, as detailed below:  
Figure 3: Three main parts of our ensemble fuzzing method: (**a**) callgraph division; (**b**) subgraph association and seed mapping; (**c1–c3**) bitmaps and seeds synchronization and task scheduling. 1. _Callgraph partition_: The tested program is executed sequentially using each seed from the current global seed corpus as the input. Based on the execution traces of the tested program, the functions (nodes) and function call relationships (edges) that are not present in the initial callgraph of the tested program obtained while compiling are added to the callgraph. Subsequently, duplicate edges, nodes without any basic blocks in their corresponding functions, and those nodes that cannot be accessed from the node corresponding to the \"main\" function are removed from the callgraph. Finally, the pruned callgraph is transformed into a minimum spanning tree and divided into a significant quantity of subgraphs with tight internal connectivity using the existing tree partitioning algorithm named Lukes' algorithm [35]. 2. _Subgraph merging_: After generating a significant number of subgraphs from the callgraph, the first step is to merge any subgraphs that do not have functions directly callable by the \"main\" function with the subgraph that can call them. This ensures that every ultimately partitioned subtask can be easily reached from the \"main\" function. Subsequently, the subgraphs are evenly merged into a specified number of subtasks based on the total weight of functions within each subgraph, and these subtasks are marked on the callgraph. 3.1.1. Callgraph Partitioning Callgraph partitioning consists of four specific steps, which are as follows:  
1. _Callgraph updating_. Before dividing the task, it is necessary to update the initial callgraph (as shown in Figure 3(a) as an example) obtained during the compilation of the tested program based on the fuzzing results up to now. Specifically, each seed in the current global seed corpus is used as input sequentially to execute the tested program and obtain the execution trace for each execution. Then, the functions (nodes) and function call relationships (edges) existing in the execution traces but not in the initial callgraph are added to the callgraph. Then, for each function (node) in the callgraph, the number of basic blocks, branches, and uncovered branches are attached to the node based on the execution results. A sample of the updated callgraph is shown in Figure 3(b). 2. _Callgraph simplification_. After updating the callgraph, duplicate edges and nodes containing no basic blocks or those untraversable from the \"main\" function were deleted to trim the callgraph. The simplified callgraph is shown in Figure 3(c). Then, the callgraph was transformed into the form of a minimum spanning tree, as illustrated in Figure 3(d). Figure 4: A sample of callgraph partition. In subgraph (**b**), the purple function node and the edge pointing to it are newly added, while the red function nodes and their associated edges are highlighted to indicate that they will be removed in subgraph (**c**). 3. _Calculation of nodes' weights._ From the perspective of balancing the workload of fuzzing, as shown in Figure 4d, the minimum spanning tree was weighted for each function node to estimate its fuzzing workload. The weight assignment principle is that the more branches a function has, the more complex it is, so the longer time it needs to take for fuzzing; at the same time, functions with more uncovered branches have more exploration potential, so they also require more fuzzing time.