Computer Science
Computer Science-2021.gz:143298
Computer Science
79d77cf59739fbf09f48b421f84fd5ea65d743c6
VulSPG: Vulnerability detection based on slice property graph representation learning

Vulnerability detection is an important issue in software security. Although various data-driven vulnerability detection methods have been proposed, the task remains challenging since the diversity and complexity of real-world vulnerable code in syntax and semantics make it difficult to extract vulnerable features with regular deep learning models, especially in analyzing a large program. Moreover, the fact that real-world vulnerable codes contain a lot of redundant information unrelated to vulnerabilities will further aggravate the above problem. To mitigate such challenges, we define a novel code representation named Slice Property Graph (SPG), and then propose VulSPG, a new vulnerability detection approach using the improved R-GCN model with triple attention mechanism to identify potential vulnerabilities in SPG. Our approach has at least two advantages over other methods. First, our proposed SPG can reflect the rich semantics and explicit structural information that may be relevance to vulnerabilities, while eliminating as much irrelevant information as possible to reduce the complexity of graph. Second, VulSPG incorporates triple attention mechanism in R-GCNs to achieve more effective learning of vulnerability patterns from SPG. We have extensively evaluated VulSPG on two large-scale datasets with programs from SARD and real-world projects. Experimental results prove the effectiveness and efficiency of VulSPG.


I. INTRODUCTION
Source code-based vulnerability detection is a classic problem, in which considerable efforts have been made in the past decade, such as employing static and dynamic analysis tools to flag potentially dangerous code as candidate vulnerabilities so that it can gain special attention [1], [2]. However, many methods rely on rules manually curated by experts in the security domain, which usually suffer from low coverage (leading to false negatives) and high-cost (due to false positives) [3] [4]. Moreover, these methods are not suitable for tracking existing unknown vulnerabilities on a large scale [5].
Along with the rapid development of artificial intelligence and the increasing accessibility of large scale open-source code repository, many works begin to apply deep learning to vulnerability detection considering that deep neural networks can extract features in an automatic way, instead of being designed by domain experts. For example, Li et al. [6] proposed a systematic framework SySeVR to represent the syntax and semantic information pertinent to vulnerabilities, in which program slicing technique [7] is used to produce smaller code segments (i.e., some possibly discontinuous but semantic and vulnerability-related statements), making it applicable for deep learning networks. Although SySeVR improves the performance of deep learning models in vulnerability detection, it still has two weaknesses: (1) Code segments generated by SySeVR can only cover limited types of vulnerabilities, especially for real-world programs. (2) A sequential neural work (e.g., LSTM or GRU) is used to encode code segments in the form of plain texts, which may lose the information of data and control dependencies among statements in code segments, and therefore cannot effectively learn the nonsequential features of graph-based information.
To preserve the complex structral and sementic information of source code and effectively learn these non-sequential features of graph-based information, Zhou et al. [8] proposed a GGNN-based vulnerability detection model Devign, which first integrates syntax and dependency information of source code into a joint graph representation, and then extracts vulnerability-relevant features from the composite graph with the help of GNNs. However, due to the very small proportion of vulnerable statements in real-world functions, the large amount of information irrelevant with any vulnerability patterns in the composite graph will hinder the accurate learning of the vulnerability patterns.
To mitigate the above problems, we define a novel graphand-slice based code representation named Slice Property Graph (SPG). Compared with other graph-based code representations, the proposed SPG differs in that it aims to not only preserve the rich semantics and explicit structural information that may be relevant to vulnerabilities, but also eliminate irrelevant information as much as possible to reduce the complexity of graphs. To this end, based on the four SyVCs (Syntax-based Vulnerability Candidates) proposed by Li et al. [6], we first add two kinds of new SyVCs to improve the vulnerability coverage of program slicing. Using these six kinds of SyVCs as slicing criterion, we use program slicing technique to extract the slice nodes which might be relevant to vulnerabilities. Then, we take the data dependency, control dependency, and function call dependency between the extracted slice nodes as edges to generate SPG. All these dependency are extracted from the code property graph (i.e. CPG) [9] which combines abstract syntax tree (AST) [10], control flow graph (CFG) [11] and program dependency graph (PDG) [11] into a single data structure. Next, we propose a new vulnerability detection approach, i.e., VulSPG, which combines the improved relational graph convolutional network (R-GCN) [12] model with triple attention mechanism to identify potential vulnerabilities in SPGs. More concretely, the R-GCN can perform representation learning on SPGs with multiple attributes and dependencies, and the triple attention mechanism helps the detection model focus on vulnerability features and suppress unimportant ones via learning attention weight. We evaluated the proposed method on two datasets, and the experimental results demonstrate that VulSPG can identify vulnerabilities more accurately than the baselines.
The main contributions of our work are:   Fig. 1(b) shows the vulnerable code in the FFmpeg project that was fixed in revision 486f0b0, which contains two vulnerabilities: a) Divide By Zero. When the program passes the parameter size to the function ff png zallo(), an error is raised at the statement if(items ≥ UINT MAX / size) if the attacker sets the value of size to 0. b) Uninitialized Memory. The function ff png zallo() calls the av malloc() to request memory without initializing it. Fig. 1(c) shows the patched code for this vulnerable program. From this example, we obtain the following observations: Observation 1. Vulnerabilities in real-world projects usually span multiple functions or files. For example, the Uninitialized-Memory vulnerability in Fig. 1 spans the function ff png zallo() and av malloc(). Therefore, interprocedural analysis is necessary for detecting vulnerabilities across multiple functions or even files, that is, calling relations between functions should be included in code representation to enable it to entirely characterize these vulnerabilities.
Observation 2. There are usually a large number of vulnerability independent statements in vulnerable code. For example, the vulnerable code in Fig. 1 has 70 lines of statements, but only a few of them are logically and semantically to any potential vulnerability. The divide-by-zero vulnerability is only related to the parameter size and the conditional statement if(items≥UINT MAX/size). The uninitialized-memory vulnerability is related to return av malloc(items*size);, ptr = malloc(size);, return ptr;. Taking the vulnerable code shown in Fig. 1 as example, the composite graph proposed by Devign [8] can comprehensively characterize the program by merging AST, CFG, Data flow Graph (DFG) and Natural Code Sequence (NCS) into one graph. It contains 171 nodes and 322 edges, but only several nodes and edges are relevant to the vulnerability.
SySeVR [6] proposed by Li et al. utilizes program slicing technique to generate a set of code statements that are semantically related to the vulnerability called SeVCs (Semantic-based Vulnerability Candidates). In fact, SeVCs is an ordered set of statements which include backward, forward and interprocedural program slice. Fig. 1(d) shows the SeVC generated by SySeVR based on the sensitive function malloc() (a FC-kind SyVC). It provides an entire representation of the uninitialized-memory vulnerability through interprocedural slicing, and reduces a large number of statements that are unrelated to the vulnerability. However, SySeVR leverages token-based sequential representation, which cannot reflect complex structural information and dependencies in the code. The need to model the logic and structure of programs in vulnerability detection tasks has been demonstrated in [8] and [13]. Furthermore, the SeVCs generated by using 4 types of slicing criterions can only cover part of the vulnerable statements in the source code. Taking the SARD dataset provided by Li et al. themselves as an example, about 93.6% of all vulnerable codes in the dataset can be covered by SeVCs, but there are still 890 vulnerable codes that cannot be covered.
To overcome these challenges, we are encouraged to design a more effective code representation, which needs to satisfy several conditions. 1) It should contain the calling relations between functions. 2) It is capable of eliminating redundant information that may not be relevant to the vulnerability as much as possible but can cover more vulnerable code. 3) It is able to characterize the logic and structure of the vulnerable code with a small yet semantically rich graph. To this end, we design SPG, a edge-labeled and directed attributed multigraph, for code representation. The definition and the generation process of SPG can be found in section III and section IV-A.

B. Motivation for Using Graph Neural Network
Current popular approaches convert the various representations of code into a tiled sequence and then use deep learning models (usually CNNs and RNNs) to learn the code representation as natural language sequences [14] [15] [16]. However, SPG as a kind of graph data is irregular, each node in the graph may have a different number of neighboring nodes and the data samples of each node are not independent of each other but are related to other nodes, making it hard for general deep learning algorithms to learn the structural features of the graph. Hence, to obtain a more accurate characterization of the vulnerability code, we select Graph Neural Networks (GNNs) to learn the topology structure and node representation information directly from the SPG. We choose Relational Graph Convolutional Networks (R-GCNs) rather than other graph convolutional networks [17], such as GraphSAGE [18], Gated graph sequence neural networks (GGNN) [19], to learn the characteristics of nodes for two reasons. First, the edges of the SPG are directed, and the directional information of the edges cannot be properly learned by using non-directed GNN models. Second, SPG contains multiple relationships between its nodes, and R-GCN can better exploit these relationships to learn representations of source code.

C. Motivation for Using the Triple Attention Module
Different syntax elements in the source code are of different importance for the detection of vulnerabilities. For example, a statement of type CallExpression related to an API function call may contain more information about the vulnerability. Besides, the code structure contains several other independent dependencies, such as data dependencies, control dependencies and function call dependencies, and the importance of these dependencies varies from one vulnerability to another. For example, data dependencies may be more important than control dependencies in vulnerabilities related to the use of arrays. Therefore, we introduce an attention mechanism to pay more attention to the key vulnerability features so that these features have a greater impact on the classification results. However, there are still some obstacles in applying them to vulnerability detection. First, the attention mechanism should fit both the proposed SPG and the GNN model used in this paper. Second, the attention mechanism needs to be better adapted to the problem of vulnerability detection.

III. OVERVIEW
As shown in Fig. 2, the proposed VulSPG method contains four phases: 1) SPG Generating Phase. To generate the corresponding SPGs of programs, we first traverse the program's AST and identify key points (or called SyVCs [6]) with special syntactic features that are likely to trigger any vulnerability. Then, program slicing technique is applied to find the semantically related nodes (called slice nodes) in PDG to SyVCs. Finally, the slice nodes are connected, through the data-, control-and function call-dependency, to form the SPG structures as shown in Fig. 4. For clarity, the proposed SPGs is defined as follows: Slice Property Graph (SPG): SPG is a novel code representation which merges data dependency graph (DDG), control dependency graph (CDG) and function call dependency graph (FCDG) into a joint graph data structure. Formally, a slice property graph can be denoted as g SP G = (V, E, X, D) where V is a set of slice nodes, E is a set of directed edges, X is the set of property values of nodes, and D is the set of property values of directed edges.
2) Graph Node Embedding Phase. In this phase, we initialize the feature vector for each node in SPG. Firstly, every node of SPG described one code statement is lexied into a sequence of tokens, each of which is then embedding into a continuous distributed vector via the pre-trained word2vec model. Secondly, using these vectors as input, the semanticfeature vectors of the nodes in SPG are obtained by the tokenlevel attention method in the triple attention mechanism. Next, the node type information is embedded into the node-type vector via one-hot encoding, and it is fed into a linear layer by concatenating it with the semantic-feature vector. The output result is the initial vector of SPG nodes.
3) Graph Encoding Phase. In this phase, we first learn the hidden states of the nodes of SPG, DDG, CDG, and FCDG through graph encoding networks, respectively. Then, the hidden states of the nodes can be used for weighted summation to calculate the features of SPG and its subgraphs including DDG, CDG, and FCDG. The weights can be obtained through the node-level attention mechanism. Next, we obtain the feature vector of the subgraph by integrating all subgraphs through a subgraph-level attention mechanism. Finally, the SPG feature vector and the subgraph feature vectors are concatenated and fed into the classifier network to train the model. 4) Vulnerability detection phase. In this phase, we use the model trained in the previous phases to detect whether the input SPG is vulnerable or not.

A. SPG Generating Phase
In this section, we describe the process of generating the SPG which can be divided into three steps.
Step 1. The source code is first parsed by using open-source tool joern 1 to produce a series of code representations (e.g., AST, PDG, CPG), which enable us to analyze the structure of source code and function calls as well as dependencies in the program.
Step 2. We search ASTs for SyVCs as a set of slicing criterions through matching some vulnerability candidate syntax characteristics. The paper uses following six types of SyVCs: API/Library Function Call (FC), Array Usage (AU), Pointer Usage (PU), Arithmetic Expression (AE), Function Parameter (FP) and Function Return statement (FR), where the first four types come from the work of Li et al [6] (please refer their work for details), and the other two types are proposed in this paper to improve the coverage of the vulnerability by the SPG.  We use this example to illustrate how to match FR-kind and FP-kind SyVCs.
• The highlighted node in Figure 3(a) matches the FP-kind syntax characteristic, because it satisfies the following two conditions: 1) its type is "Identifier", and 2) it has a parent node of type "Parameter". • The highlighted node in Figure 3(b) matches the FR-kind syntax characteristic, because it satisfies the following two conditions:1) its type is "Identifier", and 2) it has a parent node of type "Returnstatement".
Step 3. Using the SyVCs obtained in step 2 as the slicing criterion, we traverse the PDG obtained in step 1 to get a set of statements (called slice nodes) related to each slicing criterion. Next, we obtain data-and control-dependencies as well as function calls among slice nodes from CPG. Finally, the union of all dependency sets and functions calls induces the proposed SPG, where nodes are slice nodes and directed edges represent the dependency and call relationships between slice nodes. The detailed process is shown in Algorithm 1, which can be divided into four parts: 1) Generating the CPG and PDGs (Line 1-5 in Algorithm 1): We first generate the CPG g CP G for program P . Then, we generate a PDG g P DG i for each function f i ∈ P . 2) Extracting the set of forward slice nodes (Line 6-14 in Algorithm 1): First, using one SyVC ce j as a slicing criterion, we forward traverse g P DG i of function f i to obtain the set F SN (ce j ) of forward slice nodes. Then, for each node n k in F SN (ce j ), it is considered as caller nodes if it or its child is of type "CallExpression". For the corresponding function f l , we perform forward traverse over the PDG g P DG l to obtain the set IF SN k (ce j ) of interprocedural forward slice nodes. Finally, we merge all the interprocedural forward slice nodes to obtain the set IF SN (ce j ) of interprocedural forward slice nodes.
3) Extracting the set of backward slice nodes (Line 15-23 in Algorithm 1): First, using SyVC ce j as slicing criterion, we backword traverse g P DG i of function f i to obtain the set BSN (ce j ) of backward slice nodes. Next, we query all nodes in g CP G to search a node n z that satisfies one of the following two conditions: 1) n z or its child node is of type "CallExpression" and calls f i ; 2) n z is of type "ReturnStatement" and belongs to the function f l called by f i ; Finally, we backward traverse the PDG of the corresponding function using n z as a starting node to obtain the set IBSN z (ce j ) of interprocedural backward slice nodes and merge all the interprocedural backward slice nodes to obtain the set IBSN (ce j ) of interprocedural backward slice nodes. 4) Generating the SPG (Line 24-33 in Algorithm 1): First, we merge the sets F SN (ce j ) and IF SN (ce j ) obtained from part 2) and the sets BSN (ce j ) and IBSN (ce j ) obtained from part 3) to generate the set SN (ce j ) of slice nodes. Next, we add each control or data dependency edge e q , the source node src(e q ) and the end node end(e q ) of e q in g CP G to SPG g SP G j if src(e q ) ∈ SN (ce q ) and end(e q ) ∈ SN (ce q ). Then, we analyze the calling relationships between functions according to g CP G and add the function call dependency egdes to g SP G j . Specifically, if function f 1 calls function f 2 , we add function call dependency edge with node in f 1 which calls function f 2 as the source node and "FunctionDef" node in f 2 as the end node.
Considering the tradeoff between time cost and performance, only one layer depth of call function is considered in our inter-procedural analysis. Taking the vulnerable code in Fig. 1 as an example, we use the FP-kind SyVC size as a slicing criterion to generate the SPG shown in Fig. 4. The yellow nodes which connected by a data dependency edge in SPG are related to the divide by zero vulnerability, illustrating that the vulnerability is only related to data dependency. The blue nodes are related to the uninitialized memory vulnerability. These four nodes are connected in turn by function call dependency edge, control dependency edge, and data dependency edge, illustrating the necessity of representing the vulnerability by these three types of dependencies together.

B. Graph Node Embedding Phrase
Embedding Nodes of SPG: To encode the semantic and type information of nodes in the SPG, we use the following to generate the initial embedded vectors of the SPG nodes. For the semantic information of the nodes, we first perform lexical analysis for each statement and create a vector of lexical tokens via the pretrained word2vec model. Next, the dependencies between tokens in each statement are captured using a tokenlevel attention mechanism to obtain a semantic feature vector of the SPG node, the detailed procedure of which can be found in Section IV-D. For the type information of nodes, we represent the type of each node as a one-hot vector. Since the semantic feature vector and type feature vector do not belong to the same semantic space, we concatenate the two vectors and feed them to a linear layer to finally obtain the initial embedded vector of the node. The parameters in the linear layer can be trained simultaneously with the vulnerability detection model. Formally, a SPG g SP G (V, E, X, D) is a directed multigraph with labeled edges. For each node v i ∈ V in SPG, there is a corresponding x i ∈ X to represent its feature vector, which is obtained from the semantic feature vector and the type feature vector through a linear layer, i.e.
)+b l . W l and b l are the parameters that can be learned in the linear layer, x se i and x type i are respectively the corresponding semantic feature vector and the type feature vector of node v i . x i is the corresponding initial embedded vector of node v i , the symbol || represents the concatenating operation. For each edge e j ∈ E in SPG, a corresponding Generate the set F SN (ce j ) of forward slice nodes from g P DG i ; 9: for each node n k ∈ F SN (ce j ) do 10: if n k or its child node is of type "CallExpression" & n k contains the function name f l ∈ P called by f i then 11: Generate the set IF SN k (ce j ) of interprocedural forward slice nodes from g P DG l ; 12: end if 13: end for 15: Generate the set BSN (ce j ) of backward slice nodes from g P DG i ; 16: for each node nz ∈ g CP G do 17: if nz or its child node is of type "CallExpression" & nz contains the name of function f i & nz belongs to the function fm ∈ P calling f i then 18: Generate the set IBSNz(ce j ) of interprocedural backward slice nodes from g P DG m ;

19:
else if nz is a node of type "ReturnStatement" & nz belongs to the function f l ∈ P called by f i then 20: Generate the set IBSNz(ce j ) of interprocedural backward slice nodes from g P DG l ; 21: end if 22:

25:
for each edge eq ∈ g CP G do 26: if src(eq) ∈ SN (ceq) & end(eq) ∈ SN (ceq) & eq is data/control dependency edge then 27: Add nodes src(eq), end(eq) and edge eq to g SP G j ; 28: end if 29: end for 30: Add function call dependency edges to g SP G j ; 31: G ← G ∪ g SP G j 32: end for 33: Return G; d j ∈ D denotes its label, where D contains three types: data-, control-, and function call-dependency. Dividing subgraphs of SPG: To better distinguish dependencies in SPG and provide a basis for the attention mechanism based on subgraphs, we divide SPG into three types of subgraphs according to the dependencies in SPG, including Control Dependency Graph (CDG SP G ), a Data Dependency Fig. 4. An example of SPG for the vulnerable code in Fig. 1 Graph (DDG SP G ) and a Function Call Dependency Graph (F CDG SP G ). If the program does not contain a certain dependency that causes the subgraph to be empty, it can be directly treated as a 0-vector of the same dimension.

C. Graph Encoding Network
In this section, we use R-GCN to perform representation learning on SPG and its subgraphs. A graph data structure can be denoted as g G (V, E, X, D), where the superscript G ∈ {SP G, CDG SP G , DDG SP G , F CDG SP G } refers to the type related to the graph g. For each graph, we can use a R-GCN to learn the hidden state of each node in each layer as follows.
where l < L denotes the l-th layer. h has no corresponding dependency. The node initialization state can be seen as the hidden state in the network at layer 0, i.e., h (0) i = x i ∈ R z . At this stage, the weight matrix will also turn to be W After performing the aggregation operation on g G with L layers of R-GCN, we concatenate the hidden states of the nodes in each layer as the final node representation, i.e.,

D. The Triple Attention Mechanism
Token-level Attention mechanism: The token-level attention mechanism is primarily designed to obtain dependency information between tokens within a statement to help generate a more accurate semantic vector representation of each statement node. Specifically, the tokens in each statement node are first embedded into fixed-dimensional vectors via a pretrained word2vec model. Next, we add positional embeddings to the token vectors to encode the position of the tokens with repspect to the sequence. Finally, these vectors are fed into the attention layer to learn the semantic vector representation of each statement node. The reason for using multi-head self-attention rather than typical RNNs (GRU, LSTM, et al.) or CNN is as follows: (1) the self-attention method uses a large number of parallel operations and is computationally faster than most of the other techniques mentioned above.
(2) compared to RNN and CNN, the self-attention method has been shown to be more capable to learn long-range dependencies among tokens [20].
Formally, let the statement node v i contains m tokens and T i = [t i,1 , t i,2 , · · · , t i,m ] T ∈ R m×c be the semantic matrix corresponding to v i , where t i,j ∈ R c denotes the embedding vector of the j-th token in the statement. Note that the positional encodings used in t i,j are calculated in the same way as taken in [20]. Then, the semantic vector x se i corresponding to the node v i can be calculated in (2).
where M utiHead is a multi-head self-attention method that maps a variable-length sequence of code representations to another sequence of equal length, which contains the semantic features of the tokens in the statement. f latten is a function that flattens the resulting semantic sequence into a onedimensional vector for easy computation of node initialization later (Section IV-B).
Node-level Attention mechanism: We establish the nodelevel attention mechanism to obtain the vector representations of SPG and its three subgraphs, as shown in the right part of Fig. 2. For the SPG and its subgraphs, we refer to the attention method in SAGPOOL [21] to calculate the attention score of each node by taking into account both the characteristics of the nodes themselves and the topology of the graph. The calculation equation is as follows: where G ∈ {SP G, CDG SP G , DDG SP G , F CDG SP G } (3) where z G i ∈ R denotes the attention score of the node v i in the graph g G . Θ G d ∈ R (L+1)·z and Θ G 0 ∈ R (L+1)·z are both learnable parameters in the model, Θ G d corresponds to the dependency d while Θ G 0 has no corresponding dependency. The other parameters are the same as those presented in Section IV-C.
To avoid loss of information, instead of using the top-K method to eliminate nodes, we perform the weighted summation operation over all nodes based on self-attention values to ensure that each node in the SPG contributes to the result. Therefore, the feature vector of the graph g G can be calculated in (4). α G i is the attention weight corresponding to node v G i , which is obtained by normalizing the attention scores of all nodes in the graph g G by the softmax function.
is the set of nodes of the graph g G and z G i is the attention score corresponding to node v G i . S G ∈ R (L+1)·z is the feature vector of the graph g G .
Subgraph-level Attention mechanism: After obtaining the vector representations of the SPG, CDG SP G , DDG SP G and F CDG SP G , we propose the subgraph-level attention mechanism to obtain the feature vector of the combined three types of subgraphs. In our approach, the attention of a subgraph of SPG indicates the importance of the subgraph to the SPG, which can be calculated in (5).
Where sub denotes the type related to the subgraph. r sub ∈ R and S T sub ∈ R (L+1)·z represent the attention score and the feature vector of the graph sub respectively. W r ∈ R (L+1)z×(L+1)z is the matrix of weights to be learned. S SP G denotes the feature vector of the g SP G . Then, the attention weights of the subgraphs are obtained by the softmax function. Finally, the subgraph feature vectors are lineraly combined through a weighted sum which is calculated as follows: Where β sub is the attention weight corresponding to the graph sub, S AS is the feature vector of all subgraphs.

E. The Classifier Network
At last, we concatenate the S SU B and the S SP G obtained in Section IV-D, and then feed them directly into the classifier network for vulnerability detection. To achieve end-to-end learning, the classifier network in our approach is a single fully connected layer with softmax outputs. The formula for the classifier network is (7).
Where y ∈ {0, 1} is the class label, and 1 is a vulnerable sample, 0 is a non-vulnerable sample. Both W CN ∈ R 2(L+1)z×2 and b CN ∈ R 2 are the learnable parameters of the classifier network. p(y|g SP G ) is the output of the classifier network. Finally, we use the widely used crossentropy function [22] as a loss function to train the model.
Where T rain is the training datasets,p(y|g SP G ) is the ground truth, i.e.,p(y|g SP G ) = 1 if g SP G contains vulnerabilities andp(y|g SP G ) = 0 otherwise.

V. EVALUATION A. Evaluation Setup
Research Questions: Our evaluation is designed to answer the following research questions. RQ1: How effective is VulSPG when compared with stateof-the-art vulnerability detection methods at slice level? RQ2: How effective is VulSPG when compared with stateof-the-art vulnerability detection methods at function level? RQ3: How effective is SPG in vulnerability detection tasks when compared with other graph-based code representations? RQ4: Is our triple attention mechanism beneficial to vulnerability detection?
Vulnerability dataset: We conduct comparative experiments on two datasets at the slice level and the function level to evaluate the benefits of VulSPG. The first dataset is provided by Li et al. [6] and collected from the National Vulnerability Database (NVD) [23] and the Software Assurance Reference Dataset (SARD) [24]. There are 15,591 programs in this dataset, of which 14,000 are from SARD and contain 13,906 vulnerability programs, and the remaining 1,591 programs from NVD with 874 vulnerability programs. Most of the programs in this dataset are synthetic, which is not suitable for evaluating the performance of the model in practical applications. In addition, this dataset contains interference information (e.g., keyword "Good" and "Bad", etc.), so we peformed a normalization on source code in this dataset and used the same normalization method as in [6] for a fair comparison. The second dataset provided by Zhou et al. [8] contains real-world programs extracted from two C/C++ opensource projects(i.e. FFmpeg and QEMU), including 17,549 programs from QEMU, of which 7,479 are vulnerable, and 9,769 programs from FFmpeg, 4,981 of which are vulnerable. The number of SPGs extracted from these two projects is shown in Table I.
By introducing two new types of SyVCs (i.e. FP-kind and FR-kind), the vulnerability coverage of SPGs on two datasets increased by 3.1% and 10.0%, respectively.
labeling SPG: For SARD programs in the first dataset, if the statement node contains at least one vulnerability in the generated SPG, it is labeled as 1, otherwise it is 0. Unlike the SARD programs, the programs from NVD, FFmpeg and QEMU have no explicit vulnerable lines of code. Therefore, we can only generate labels for SPGs through the diff files, which are divided into three steps. First, for all SPGs generated by non-vulnerable programs, we label them as 0. Second, for deleted lines in the diff file, we treat them as vulnerability codes. That is, if there is a corresponding deleted line in the statement nodes of SPG, the SPG will be labeled as 1. Third, for programs that have no deleted lines in the diff files but are vulnerable, we treat its overall structure as vulnerable, that is, all SPGs generated by these programs are labeled as 1. Finally, we manually review SPGs labeled as vulnerable by security experts to ensure proper labeling.
Baseline methods: We select slice-based approaches (VulDeePecker [25] and SySeVR [6]) and graph-based approaches (Devign [8] and FUNDED [13]) as comparisons to evaluate the effectiveness of the proposed methods. VulDeePecker extracts code segments called code gadgets to represent the programs and then uses BiLSTM to learn the vulnerability patterns. SySeVR generates the code segments named SeVCs by extracting four types of SyVCs and then uses BiGRU to learn the vulnerability patterns. Devign learns vulnerability patterns from the code composite graphs using GGNN with the CONV module for vulnerability detection. FUNDED is similar to Devign, but the proposed representation of the codes is more complex and contains more syntactic and structural information and the improved GGNN is verified to be more suitable for learning multiple relationships of complex graphs. Evaluation Configuration: We implement the proposed GNN-based model with the triple attention mechanism using Pytorch v1.6 [26] and DGL [27]. Our experiments were run on a machine with an Intel Core 2.6 GHz CPU and an NVIDIA 2080Ti GPU. Taking into account the computational efficiency of VulSPG and the results of parameter adjustment during the experiments, we make the following parameter settings. The dimensionality of initial node vector is 64. In the graph encoding phase, we set the dimensionality of hidden states as 64, and the number of hidden state layers as 2. Therefore, the dimensionality of final vector of a SPG is 384. We train our model using the Adam optimizer with a learning rate of 0.001 and 200-epoch patience for early stopping. All baseline approaches are configured with the same settings as reported in their original papers [25] [6] [8] [13].
Evaluation Metrics: We use six widely used metrics to evaluate the performance of VulSPG and other baseline approaches. Accuracy (A). The proportion of all test cases that are classified correctly. Precision (P). The proportion of correctly predicted vulnerability samples to those predicted to be vulnerable. Recall (R). The proportion of correctly predicted vulnerability samples to all vulnerable samples. False-positive rate (FPR). The proportion of false-positive samples among all non-vulnerable samples. False-negative rate (FNR). The proportion of false-negative samples among all vulnerable samples. F1-measure (F1). F1 assesses the overall effect by considering precision and recall.

B. Evaluation Results
Experiments for answering RQ1: To investigate the answer to Q1, we conducted vulnerability detection experiments on the first dataset at the slice level. For comparison, we chose three static vulnerability detection tools: checkmark [28], Flawfinder [29], and RATS [30] and two slice-based methods: VulDeePecker [25] and SySeVR [6]. To reduce the cost and increase the credibility of the experiment, we use the experimental results from the original paper [6]. Following the experimental configurations in [6], we randomly select 80% of the programs in the first dataset as the training set and the rest 20% as the testing set. Specifically, we extracted 639,703 SPGs corresponding to the six kinds of SyVCs from  Table II. First, all slice-based methods perform better than the static vulnerability detection tools. Second, our approach outperforms the other slice-based methods. VulSPG is 4.9% more accurate and the F1-measure is 27.7% higher than VulDeePecker. Compared to SySeVR, VulSPG is still superior in pecision, recall and F1measure, although the accuracy is slightly lower. In summary, VulSPG is more effective than static vulnerability detection tools and state-of-the-art slice-based approaches on slicelevel vulnerability detection tasks.
Note that for RQ2, RQ3, and RQ4, we focus on performing experiments on the second dataset. The main reasons are as follows. First, the second dataset consists of vulnerable codes from real-world projects, while most of the samples in the first dataset are synthetic codes. Second, the second dataset, generated on function-level, is more appropriate for comparing our approach with the state-of-the-art graph-based methods.
Experiments for answering RQ2: This experiment aim to demonstrate the effectiveness of the VulSPG at the functionlevel granularity. Note that SySeVR (4-type) denotes the baseline method based on four types of SyVCs (FC-kind, AUkind, PU-kind, AE-kind) proposed in their original paper, and SySeVR (6-type) indicates the addition of our proposed two SyVCs (FR-kind and FP-kind). Referring to the experimental setup in [8], we randomly divide the samples into two groups at a ratio of 75%:25%. Unlike other graph-based program representations, SPGs are generated by using program slicing technique according to a series of criterions (i.e., SyVCs) extracted from the program. Therefore, the number of SPGs generated in the dataset is much larger than the number of programs. To make a fair comparison with graph-based methods Devign and FUNDED, We use the following methods to detect program vulnerabilities. For each program in the testing dataset, a program is predicted to be vulnerable if at least one of its SPGs is predicted to be vulnerable. A program is predicted to be non-vulnerable if all its SPGs are predicted to be non-vulnerable. Slice-based methods VulDeePecker and SySeVR also use the above approach for vulnerability detection. The experimental results are presented in Table III.
The experimental results indicate that our proposed VulSPG outperforms other state-of-the-art methods on vulnerability detection task at the function-level granularity. In the slicebased approaches, SySeVR performs better than VulDeePecker. The primary reason is that VulDeePecker only de- tects vulnerabilities related to insecure library functions, and thus cannot cover vulnerable programs in the testing dataset that do not contain insecure functions when generating code segments. Similarily, SySeVR (6-type) covers more types of vulnerabilities than SySeVR (4-type) and, thus, has better performance under the same testing dataset. In the graphbased approaches, FUNDED slightly outperforms the Devign in some of the metrics. Although both of them use GGNNs, FUNDED improves upon GGNN to make it more suitable for modeling multiple code relationships extracted from the source code. However, unexpectedly, the graph-based methods (i.e., Devign and FUNDED) perform worse than the slicebased methods (e.g., SySeVR (4-type)). The reason is in two folds: (1) As we detailed in Section II-A, the graph-based representations of the code used by Devign and FUNDED contain a lot of nodes that are not relevant to any vulnerability, which greatly hinders the GGNN to learn effective vulnerable features.
(2) For the FUNDED and Devign methods, the token embedding within a statement is simply averaged or fed into the linear layer to obtain initial node representation, which fails to account for the dependencies between tokens in the statement nodes. In summary, VulSPG is more effective than the state-of-the-art slice-based and graph-based methods on the function-level vulnerability detection task. Experiments for answering RQ3: In this experiment, AST, CFG, PDG, and CPG, are selected as the baselines of program representation. R-GCN and GGNN are selected as the baselines of vulnerability detection model. In the model readout phase, we uniformly use the multilayer perceptron (MLP) for graph-level classification to mitigate the impact of the model on vulnerability detection performance. The detection results are presented in Table IV.
As shown in Table IV, the experimental results for CFG and PDG are slightly better than those for AST. In fact, although AST contains more syntax information than CFG and PDG, it also contains more nodes and edges that are not relevant to vulnerabilities. Simlar to AST, although CPG contains rich information to allow detailed representation of various types of vulnerability patterns, the large amount of redundant information unrelated to vulnerabilities it contains also hinders vulnerability detection, which eventually leads to its failure to obtain better performance of vulnerability detection. The proposed SPG combines slicing technique and graph-based representation to remove a large amount of redundant information while preserving as much structural and semantic information about the vulnerability as possible. Therefore, it achieves the best results in the experiment. The GGNN model does not perform as well as expected, and we found that the GGNN model is prone to over-smoothness in the learning process. GGNN cannot learn the property information of different types of directed edges in SPG like R-GCN, which also explains the performance drop. In summary, our proposed SPG are more effective than other graph-based code representations in vulnerability detection.
Experiments for answering RQ4: To demonstrate the effectiveness of the triple attention mechanism in the Vul-SPG, we use R-GCN but different readout methods to learn vulnerability patterns in SPG. Specifically, We choose MLP and Conv as baselines, where Conv is the readout method of Devign that allows more effective feature extraction. Next, we conduct ablation experiments targeting the triple attention mechanism. We use the full triple attention mechanism as a comparison, removing the token-level, the node-level, and the subgraph-level attention mechanism, respectively. The experimental results are shown in Table V.
The experimental results show that the triple attention mechanism improves the graph classification performance compared with the MLP and Conv models. Indeed, focusing on the structural and semantic features of the code through the attention mechanism is more suitable for vulnerability detection than collecting all node information equally. In the ablation experiment, we find that removing subgraph-level attention mechanism has a greater impact on performance, suggesting that subgraph-level attention mechanism is most important in the triple attention mechanism. The token-level attention mechanism is used in the process of SPG node embedding, and from the experimental results, it plays an equally important role. This indicates that the token-level attention mechanism extracts dependency information between tokens within a statement, thus improving the performance of vulnerability detection. To our surprise, the node-level attention mechanism, while playing a role, is not as important as we expected. The above experimental results demonstrates to some extent that accurate identification of vulnerability patterns requires the ability to consider the combination of semantic, structural, and contextual information about the vulnerability code.
In summary, the triple attention mechanism achieves higher vulnerability detection capability and where tokenlevel, node-level, subgraph-level attention mechanisms are all effective.

C. Discussion and Limitation
Inter-procedural analysis In our experiments, the Devign's dataset is not provided with a complete program and contains only function-level code, thus we did not perform the interprocedural analysis on this dataset. We find that despite the absence of inter-procedural analysis, VulSPG still performs well on Devign's dataset. In addition, using the original same dataset also allows us to make a fairer comparison with Devign. Our future work will consist in verifying the performance of the inter-procedural analysis in real-world projects.
Bias in the experimental results. In the experiments of RQ2, the results of our implementation of Devign differ from those reported in the original paper [8]. This is because in the experiments we used all the programs in the second dataset and did not filter out programs with too many tokens, as in the original paper. Using the FFmpeg project as an example, Devign use 6,716 programs when performing the experiments, while we use all 9,769 programs in the experiments. This leads to more difficult identification of vulnerabilities and worse experimental results. In addition to using different datasets, it is difficult to reproduce the code and optimize the experimental parameters in the same way as the original paper because the original authors did not open the implemented source code.
Limitations. First, the VulSPG currently focuses on detecting vulnerabilities in the source code of C/C++ programs. We plan to extend this method to other languages in future work. Second, although we have added two kinds of SyVCs, there are still some vulnerability codes that are not covered by our generated SPGs. Third, we only consider the most commonly used vulnerability detection method GGNN as the comparison of graph coding. We will compare more types of GNN in our future work.
VI. RELATED WORK Software vulnerability detection relies on program analysis techniques, which include static analysis [31], dynamic analysis [32], and hybrid analysis [33]. Our work builds upon the foundations of static program analysis techniques.
Classic methods: Early static vulnerability detection methods are based on rules developed manually by security experts [34] [3] [4]. However, these methods rely on the knowledge and experience of experts and it is difficult to develop quality rules. Symbolic execution [35] [36] mitigates this by analyzing the control flow of the program, but also suffers from problems such as path explosion and difficulty in resolving constraints.
Machine leaning based methods: Machine learning (ML) based vulnerability detection methods offer alternative solutions for automated and more efficient vulnerability detection. Using manually defined features extracted from source code, such as function/library calls [37], software complexity metrics [38] [39] [40] and developer activity [41], ML-based approaches learn potential or abstract vulnerability patterns by machine learning algorithms. The performance of these machine learning methods strongly depends on the quality of the features extracted from the data (i.e. the discriminative and expressive power of the features) [42].
Deep Learning based methods: DL-based detection methods are able to extract features of vulnerabilities and automatically learn patterns of vulnerable code, which can significantly reduce time and labor costs as they do not require humandefined features [1] [43] [44]. We classify the representative DL-based vulnerability detection methods into slice-based methods (e.g., VulDeePecker [25] and SySeVR [6] ) and graph-based methods (e.g., Devign [8] and FUNDED [13]). Slice-based methods retain only information that may be relevant to the vulnerability, but still treat the code as sequential tokens and often ignore structure of the code. The graph-based methods take into account the structure and logic of the code. However, these code representations also contain too much redundant information unrelated to the vulnerabilities, which interferes with the GNN learning the vulnerability patterns from the vulnerable code.

VII. CONCLUSION
We propose VulSPG, which contains a code representation called SPG for vulnerability detection tasks, and a vulnerability detection method using R-GCN with a triple attention mechanism. We evaluate VulSPG on a large-scale slice-level vulnerability dataset and a function-level real-world dataset, respectively. The experimental results demonstrate that Vul-SPG is superior to state-of-the-art approaches.
ACKNOWLEDGMENT This work was supported by the National Natural Science Foundation of China (Grant Nos.61672191)