# BoostPolyGlot: A Structured IR Generation-Based Fuzz Testing Framework for GCC Compiler Frontend
## 3 Materials and Methods
### Structured Program Characteristics IR Insertion  
When conducting fuzz testing, based on the extracted IR nodes with structured program characteristics, performing insertion operations at the IR level can introduce new IR nodes, explore more potential program behaviors, and further enhance code coverage. For node insertion into IR with structured program characteristics, the following steps are taken: First, analyze the test cases and IR nodes with structured characteristics. Second, traverse the abstract syntax tree of test cases to identify potential insertion nodes based on semantic matching, control flow, and data dependencies. Then, carry out a weighted comprehensive evaluation of the relevant characteristics of multiple insertion nodes to select the final insertion node and execute the insertion operation. The specific procedures are as follows:  
Step 1: Analyze the test case and IR nodes with structured characteristics. Denote the abstract syntax tree of the test case as \(AST_{a}\). Each IR node \(ir_{i}\) represents a grammatical  
Figure 3: The abstract syntax tree of a structured program case after being translated by the master–slave IR translator. structure element, with leaf nodes marked as \(IsLeaf\). The relevant attributes of leaf nodes are as follows: the grammatical structure level \(Level\) indicates the node's depth in the abstract syntax tree, the data type \(Type\) denotes the type involved in the node, and the predecessor node set \(Pre\) and successor node set \(Suc\) are used to determine the leaf node's position in the control flow. Denote the abstract syntax tree composed of IR nodes with structured characteristics as \(AST_{b}\), with the entry node and exit node labeled as \(B_{entry}\) and \(B_{exit}\), respectively. Step 2: Conduct depth-first traversal starting from the root node, recursively visiting each IR node. When traversing to a node \(ir_{i}\) satisfying \(IsLeaf(ir_{i})=\) true, perform the following checks to determine whether it is a suitable candidate insertion point:  
Semantic matching check. Construct the semantic feature vector of the leaf node \(Leaf_{i}\), denoted as \(SemVec_{leaf}=(t_{1},t_{2},\cdots,t_{p})\), where each \(t_{i}\) represents a semantic dimension. The semantic feature vector of the entry node is \(SemVec_{entry}=(s_{1},s_{2},\cdots,s_{p})\). Measure the semantic difference between them using the semantic distance function \(SemDist\), as shown in Equation (2):  
\[SemDist=\sqrt{\sum_{i=1}^{p}(t_{i}-s_{i})^{2}} \tag{2}\]  
If its value is less than the preset semantic threshold \(\theta_{sem}\), it indicates that the leaf node \(Leaf_{i}\) and the entry node \(B_{entry}\) are compatible. Control flow check. For the leaf node \(Leaf_{i}\), calculate the control flow path lengths \(Len_{pre}\) and \(Len_{suc}\) from the root node to each predecessor node \(ir_{pre}\) and successor node \(ir_{suc}\), respectively. Determine the longest control flow path length \(Len_{b}\) of \(AST_{b}\) and the original control flow path length \(Len_{original}\) from \(Pre(ir_{n})\) to \(Suc(ir_{n})\). Define the control flow insertion impact function \(CtrlFlowImpact=|Len_{pre}+Len_{suc}+Len_{b}-Len_{original}|\), which evaluates the impact on the control flow of \(AST_{a}\) based on the structure of \(AST_{b}\) and the changes in the control flow after insertion. If \(CtrlFlowImpact<\theta_{cfl}\), then \(Leaf_{i}\) is a potential insertion point in terms of control flow. Data-dependency check. The data-dependency set of the leaf node \(Leaf_{i}\) is denoted as \(DataDep_{n}=\{d_{1},d_{2},\cdots,d_{q}\}\), and the data-dependency set of IR nodes with structured program characteristics is denoted as \(DataDep_{b}=\{b_{1},b_{2},\cdots,b_{r}\}\). For each data element pair \(\{d_{i},b_{j}\}\), the conflict judgment function \(Conflict(d_{i},b_{j})\) is defined, as shown in Equation (3). If there is a read-write operation conflict between \(d_{i}\) and \(b_{j}\), then \(Conflict(d_{i},b_{j})=1\); otherwise, it is 0.