# TMVDPatch: A Trusted Multi-View Decision System for Security Patch Identification
## 4 Design and Implementation
### Code Parsing  
As described in Section 3, currently in the field of security patch identification, there are two main methods for learning code differences: parsing the source code to build an AST syntax tree and parsing the difference as ordinary text. However, we find the generated AST abstract syntax tree is too large in the experiments of C source code. At the same time, security patches are closely related to data dependencies and control dependencies. It is difficult to directly learn the changes of the data dependencies and control dependencies via the path of the child nodes of the AST abstract syntax tree. Currently, using control dependency graph and data dependency graph to represent semantics are widely used in program analysis. However, how to apply it to the field of source code patch analysis remains to be further studied. Inspired by it, we build the data dependency graph and control dependency graph by parsing the source code, so as to capture more information. To build the data dependency graph and control dependency graph of a function, the following concepts need to be introduced. **Definition 1**. : _Control Flow Graph (CFG) : Consider a function, the CFG of the function is a graph \(G=(V,E)\), where \(V=\{n_{1},n_{2},...,n_{i}\}\) is a set of nodes with each node representing a statement or control predicate, and \(E=\{e_{1},e_{2},...,e_{i}\}\) is a set of direct edges with each edge representing the possible flow of control between a pair of nodes._  
**Definition 2**. : _Control Dependency: Consider a function, the CFG of the function is a graph \(G=(V,E)\), and two nodes \(n_{i},n_{j}\) in \(V\) where \(i\
eq\) ae and \(n_{j}\) is the latter node. If all paths from \(n_{i}\) to the end node in the CFG pass through \(n_{j}\), then it is said that \(n_{j}\) post-dominate \(n_{i}\). If there exist a path from \(n_{i}\) to \(n_{j}\) in the CFG, and satisfy \(n_{j}\) post-dominate all nodes on this path except \(n_{i}\) and \(n_{j}\), and \(n_{j}\) does not post-dominate \(n_{i}\). Then it is said that \(n_{j}\) is control-dependent on \(n_{i}\)._  
**Definition 3**. : _Data Dependency: Consider a function, the CFG of the function is a graph \(G=(V,E)\), and two nodes \(n_{i},n_{j}\) in \(V\) where \(i\
eq\ae\) and \(n_{j}\) is the latter node. If there exist a path from \(n_{i}\) to \(n_{j}\) in the CFG, and a value computed at \(n_{i}\) is used at \(n_{j}\), then it is said that \(n_{j}\) is data-dependent on \(n_{i}\)._  
In order to clearly illustrate, this paper takes the quicksort program as an example to generate CDG, the details are attached in the Appendix A. In contrast to other tools, the CDG and DDG generated by [PERSON] [43] are not in the unit of statement nodes, but in more fine-grained units of nodes similar to AST nodes. As shown in Appendix A, the 18 th line of the source code (\(``if(destra>jj)quick\_sort(a,jj,destra)\);\") is parsed into two nodes: \((<operator>.greaterThan,destra>jj)\) and \((quick\_sort,quick\_sort(a,jj,destra))\). This fine-grained node representation is more effective for subsequent semantic extraction, as it captures more details. Additionally, the CDG generated by Joern is composed of multiple subgraphs. In this paper, a virtual node (ENTRX, ENTRY) is constructed as the starting node, and all subgraphs are merged to obtain a new CDG. It should be noted that when we use Joern to parse the code, we found that some functions had recognition problems, and some samples could not show patch differences in the generated CDG and DDG ([[https://github.com/joernio/joern/issues/1420](https://github.com/joernio/joern/issues/1420)]([https://github.com/joernio/joern/issues/1420](https://github.com/joernio/joern/issues/1420)) (accessed on 1 May 2022)). After verification, the problem is due to the existence of \(ifdef\) macro definitions in the source code. Although tools can print a comma-separated list of all preprocessor \(ifdef\) and \(if\) statements.