3.1 Dataset

Vulnerable and non-vulnerable codes are needed for the training model to classify source codes into vulnerable or not. Therefore, we used Juliet Test Suite v1.3 for C/C++ ^[10] as dataset. The Juliet Test Suite is a set of test programs with vulnerabilities. It provides both vulnerable code and non-vulnerable code. Thus, both can be obtained in a single dataset. Each test program has a single function involving vulnerability (bad function) and has more than one function similar in behavior to bad function but not vulnerable (good function). Therefore, the dataset was divided into two parts, bad functions and good functions, for labeling easily in the preprocessing step. Moreover, it provides test cases for C/C++ and Java, but only C/C++ cases were used in the experiments.

3.2 Graph Extraction

The static analysis tool is used to extract the program representations. First, it analyzes the source code and generates an abstract syntax tree. Other representations (e.g., control-flow graph) are then constructed from the tree. Using the static analysis tools, seven graphs of six types were extracted (AST, CFG, PDG, CPG, ICFG, and VFG). Each type includes syntax and semantic information. The following are brief descriptions of the graphs.

$\textbf{Abstract Syntax Tree (AST)}$ AST shows the syntactic structure of the program with a tree structure. It leaves necessary parts by excluding the unnecessary parts, such as white space, semicolons, and annotations. The operator is used as the root node, and the operands are used as the leaf node. The shape of AST depends on the compiler.

$\textbf{Control-Flow Graph (CFG)}$ The CFG represents all paths that can be traversed during program execution. It describes the inner flow of the procedure in detail. The graph consists of four components (basic block, directed edge, entry block, and exit block). One basic block can contain more than one line. The entry and exit blocks indicate the start and endpoints of the program.

$\textbf{Program Dependence Graph (PDG)}$ The PDG specifies both the control-dependence and data dependence. The control-dependence denotes which parts of a program can control the other parts ^[11], and the data dependence denotes which parts of the data refer to the same memory locations with other parts. The PDG can obtain a summary of dependence in a program.

$\textbf{Code Property Graph (CPG)}$ CPG is a combination of three existing representations. Its nodes are based on the AST, and its edges have four types: AST, CFG, CDG, DDG. The syntax and semantic information are contained in one graph. Hence, it has recently been used for vulnerability detection research. Only Joern supports CPG. Generating this with other tools might require additional manual efforts.

$\textbf{Inter-procedural Control-Flow Graph (ICFG)}$ While CFG shows the control-flow only in one procedure, the ICFG presents the entire control-flow of a program with multiple procedures. It ties up multiple CFG into a single graph. Simply, each of its nodes is the CFG, and its edges are calling the relationships between procedures.

$\textbf{Value-Flow Graph (VFG)}$ Usually, data-flow analysis uses two types of algorithm to obtain each equivalence: semantic and syntactic. On the other hand, the VFG utilizes syntactic algorithms to obtain semantic equivalence. Hence, it indicates the semantic equivalence of terms ^[12].

In the experiments, three static analysis tools were chosen for graph extraction. The tools were as follows: Table 1 lists which graphs are extracted from which tools.

$\textbf{Clang Static Analyzer [1]}$ Clang Static Analyzer is a part of the Clang compiler. It implements path-sensitive, inter-procedural analysis of C, C++, and Objective-C and provides abstract syntax tree (AST), control-flow graph (CFG), and call graph. In this article, however, only the CFG was used to extract the representation from LLVM IR (intermediate representation)

$\textbf{Joern [13]}$ Joern is a platform for analyzing C and C++. Similar to Clang Static Analyzer, it provides AST, CFG, and program dependence graph (PDG). Uniquely, it produces a new graph representation called the code property graph (CPG), which is a combination of several existing graphs.

$\textbf{SVF [14]}$ SVF is a static tool specialized in inter-procedural pointer analysis of C and C++. It supports the inter-procedural control flow graph (ICFG) and value flow graph (VFG). A representation can be obtained with semantic information but not with syntax information. It also generates graphs with LLVM IR

The performance of each graph on vulnerability detection was measured using graph neural networks. On the other hand, these graphs cannot be used as the input of the GNN directly. Preprocessing is required to utilize graphs as input. This is explained in detail in the next part.

3.3 Preprocessing

The preprocessing phase consists of two steps. One is the vectorization of node features. The node features are necessary to train and generate the output with the GNN. Preprocessing calculates the node embeddings based on the node features, and these embeddings are used to predict the node label. The other one is labeling graphs with 0 (safe) and 1 (vulnerable). In the previous phase, the dataset was divided into two parts: bad and good functions. The granularity of data is function-level. Hence, they were labeled 0 or 1 by the graph, not the node. Therefore, every node in one graph has the same label. Fig. 3 shows how the preprocessing step works.

$\textbf{Step 1: Vectorization of node features.}$ The GNN takes both graphs and node features as input. The node features usually mean statements or conditions composing nodes, which are provided with vectors. The GNN is utilized to compute the embedding of each node. The final embedding of a node is used to predict the label of the graph. Doc2Vec ^[15] was used for vectorization. Doc2Vec is a natural language processing tool that can produce fixed-length low dimensional vectors from node features. Vectors with lengths of 10 were used. One node includes only a few lines of code because the size of the function used in experiments is quite small. This may change depending on the size of the function or programs.

$\textbf{Step 2: Graph labeling.}$ In the experiments, a binary classification was used to indicate if a graph contains a vulnerability. Therefore, all graphs should have labels to specify whether they are vulnerable or not. The dataset was already split into bad and good functions. Following the dataset, they were labeled 0 for good functions and 1 for bad functions. If the prediction is 0, the graph might be safe. Otherwise, the graph might have a vulnerability.

Fig. 3. Preprocessing steps.

3.4 Graph Neural Network Model

Among the various graph neural network models, GraphSAGE ^[7] was chosen to classify the graphs. The model is based on the Graph Convolutional Network (GCN) ^[16]. The GCN uses transductive learning, but it cannot generalize nodes not seen before. To overcome this limitation, GraphSAGE applies inductive learning to produce embeddings for unseen nodes efficiently. It generates embeddings by sampling and aggregating features from the neighbors of a node instead of learning embedding vectors of individual nodes. Fig. 4 shows the process of the model.

Supervised learning was used because all the data have labels for classification. The additional simple test for measuring the performance between supervised and unsupervised learning showed better results in supervised learning. Moreover, mini-batch was applied to compute smoothly, and MEAN is an aggregation function. The dataset was split into three sets: training set for 50%, validation set for 15%, and test set for 35%.

Fig. 4. Left: input graph and sampled nodes, Right: process of aggregating features.

4.1 Evaluation

The experiments under the same conditions to evaluate the performance of each program representations. First, the representations were compared by tool, and then the entire representations. For the comparison between various program representations, the number of True Positive (TP), True Negative (TN), False Positive (FP), and False Negative (FN) were counted. Four metrics were used for the evaluation, accuracy (ACC), precision (P), recall (R), F1-score (F1). Moreover, the total elapsed time was also recorded to check efficiency. Table 2 lists the classification results of the experiments. The results were rounded off to the 2$^{\mathrm{nd}}$ place.

$\textbf{· Accuracy}$

      $\text{Accuracy}=\frac{TP+TN}{\textit{Total number of predictions}}$

$\textbf{· Precision}$

      $\Pr \text{ecision}=\frac{TP}{TP~ +~ FP}$

$\textbf{· Recall}$

      $\mathrm{Re}\text{call}=\frac{TP}{TP~ +~ FN}$

$\textbf{· F1 Score}$

      $\mathrm{F}1\,\,\text{Score}=2*\left(\frac{\textit{Precision} * \textit{Recall}}{\textit{Precision} + \textit{Recall}}\right)$

$\textbf{A. Comparison of representations according to the tool}$

$\textbf{Clang Static Analyzer}$ Using the Clang Static Analyzer, only extract CFG was extracted. The analyzer also provides AST, but its shape is different from the general form because it is usually used for analysis in the tools, not to generate a representation. The performance of the CFG was not very good. In particular, the precision was less than half. This means that there were many FN cases. On the other hand, it takes less time than other methods because its node consists of LLVM IR, which has an abbreviated form.

$\textbf{Joern}$ PDG shows the best performance among the whole metrics, but it took the second most time. The AST, which only contains syntactic information, performs worst, even in precision (only 40%). The performance of CFG and CPG was similar because the CFG performs better than the CPG in precision and F1-score, but the CPG performs well in the other metrics (accuracy and recall). Nevertheless, if the total elapsed time is considered, CPG takes approximately 8.5 times more time.

$\textbf{SVF}$ The VFG presents better performance than the ICFG. The ICFG has huge nodes consisting of the node, node ID, IR, and other detailed information. Therefore, it needs more time to run the model. Even though it contains control-flow information from a procedure and the call relationship between the procedures, the performance is worse than VFG, which has data-flow information obtained syntactically.

$\textbf{B. Comparison of entire representations}$

The PDG showed better performance than other representations, not only between the representations from Joern but also between all representations. The CPG also shows good performance. It took the second most time to compute but produced the second-best result. The lowest performance was ICFG from SVF. Even it takes the longest time to produce results. All metrics were not so good. Three of the metrics indicated less than half. The other four representations indicated similar accuracy between 68~73%. On the other hand, the CFGs, both from the Clang Static Analyzer and Joern, costs less than 1,000 secs. Considering the total elapsed time, the CFGs can be efficient choices. Furthermore, it can be estimated that Joern is a suitable tool for extracting the program representations required for vulnerability detection.

4.2 Discussion

Syntactic and semantic information are required to detect the vulnerabilities. Therefore, it is expected that CPG, which includes both information, would show the highest performance in the evaluation. On the other hand, the PDG showed the best performance, even though it did not contain syntactic information. Moreover, because control-flow (e.g., CFG, ICFG) and data-flow (e.g., VFG) graphs have limited dependence information, their detection performances were lower than those using PDG.

In addition, when a graph has multiple edge types and data is transferred by edges, such information is not fully fitted to the model used, which cannot reflect the information related to edges. To utilize edge information, the model accepting various types of edges, such as gated graph sequence neural network ^[17] is recommended.

The evaluation results can be affected if the vulnerabilities are sliced accurately. In this study, as a whole program containing both vulnerable and non-vulnerable parts was used as an input to the model, unrelated information (e.g., variable declarations) can be considered vulnerable. As a result, the overall detection performance will be increased if a program slicing technique is used to extract vulnerable codebases from a program accurately. Moreover, the size of graphs will be reduced so that the total execution time can be lower than in current experiments.

Because PDG contains both control and data-dependence information, it might be suitable to learn all possible flows of a program. Based on this result, we can conclude that dependence information is most useful when detecting vulnerabilities using flow information.

Table 2. Classification results of the experiments (Training set: 50%, Validation set: 15%, Test set: 35%).