# Toward Vulnerability Detection for Ethereum Smart Contracts Using Graph-Matching Network
## 4 Methodology
### Abstract Semantic Graph Generation
#### 4.2.1 ASG from Source Code  
Given the source code in Solidity of a smart contract, it can be parsed into AST by a mature set of compiler tools, e.g., SolidityParser and solc-ast. The top part of Figure 4 illustrates an example AST parsed from the _Simple_ contract in Figure 1.  
It can be observed that AST provides a fine-grained syntactic representation of the source code. However, with the scale of the program increasing, its AST would be extremely complicated. Directly leveraging AST as the basis will largely increase the numbers of nodes and edges in ASG, which can result in intractable problems such as gradient exploding in the follow-up model training phase. In this case, ASG takes a statement-level granularity, which is a single line of code-based elements, as annotated by orange circled numbers in Figure 4, to construct the dedicated graph. Formally, ASG is an abstract semantic graph \(G=(V,E)\), where \(V\) is a set of nodes and \(E\) is a set of edges in the graph. Each node \(v_{i}\in V\) represents a statement of the source code, while an edge \(e_{i,j}\in E\) indicates that there exists either a control dependency (in control flow) or a data dependency (in data flow) from node \(v_{i}\) to \(v_{j}\). Figure 4: Abstract semantic graph generation based on abstract syntax tree and enriched by control flow and data flow. Control flow reflects the orders of statements in the smart contract. Similar to other programming language, Solidity uses keywords such as **if, while, for, continue**, and **break** to control statement orders; rest statements without these keywords are executed consecutively. The control flow can also be extracted from the source code, and thus can be introduced into the ASG accordingly. Note that each node of both ASG and CFG represents the same statement of the contract. Formally, a direct edge \(e_{i,j}=<v_{i},v_{j}>\) indicates that statement \(v_{j}\) is executed after the completion of statement \(v_{i}\). Figure 4 also gives an example control flow for the \(Simple\) contract, where most of control edges are sequential and only one if statement can change the execution order. In a contract that involves complex business logic, its control flow can be more sophisticated. Data flow is another orthogonal representation of the source code, which describes data dependencies between a number of operations. However, data dependencies rely on the execution orders of the statements. Hence, the search of data dependencies has to consider every control path that leads to the endpoint of the data dependency. Formally, a direct edge \(e_{i,j}=<v_{i},v_{j}>\) indicates that data produced by statement \(v_{i}\) are consumed by statement \(v_{j}\). An example data flow for the \(Simple\) contract is also demonstrated in Figure 4. There are two variables, i.e., \(amount\) and \(userBalance\), defined and used in the smart contact. It can be investigated that variable \(userBalance\) in \(v_{3}\) is related to the **if** statement in \(v_{4}\) through variable \(amount\). Such a relationship is quite meaningful for analyzing program behaviors, yet can hardly be obtained from AST or control flow. The overall workflow of ASG generation is depicted by Algorithm 1. The source code of a given smart contract \(S\) is parsed to its \(AST\) (Line 1), which is used to initialize \(ASG\) in statement-level granularity (Line 2). Then, \(AST\) is traversed with awareness of control flow structure and variable definitions (Lines 4-13). Note that control edges can be pointed out with the aid of CFG provided by a Solidity compiler tool (Lines 5-9), while variables defined in the program are recorded in an individual set \(VariableSet\) simultaneously (Lines 10-12). After the control edges are all determined, there will be a set of control paths in the \(ASG\). Thus, data edges are appended to the \(ASG\) by examining every variable along each control path (Lines 14-18). With the completion of all above procedures, the \(ASG\) for the given smart contract is obtained finally.