Analysis techniques for Smart contracts: generation of complete control flow graphs
Alejandro Hernández Cerezo · 2020
Ethereum is the most popular blockchain. It has become really well-known in the last few years because it lets users deploy their smart contracts on top of it. Gas is used to measure the computational effort when executing a transaction and to reward miners. Users set the gas limit when proposing a transaction, and if the miner runs out of gas before performing it, an out-of-gas exception is raised, reverting to the previous state before execution. Thus, inferring gas consumption is really important for not losing resources. Besides, some exploits have been found that have led to major economic losses, due to subtle bugs in the code. An example of it is the famous DAO attack. In order to tackle the efficiency and soundness problems mentioned above, we have to rely on formal methods that guarantee the soundness and accuracy of possible analysis. Research has been done previously in this topic, and it has led to the creation of tolos that analyze different features on Ethereum Virtual Machine(EVM) code. Among them, Gastap is one of the few tools based on static analysis that manages to infer gas upper bounds for transactions. Gastap is one of the most accurate tools in the field, having a great success rate. It generates a Control-Flow-Graph (CFG) as an intermediate representation of the analysis. However, the current algorithm used by Gastap is not precise. Therefore, a considerable number of smart contracts cannot be analyzed. This dissertation proposes a new algorithm for generating a Complete CFG from an EVM smart contract. We will prove that this algorithm is sound, and prove completeness is lost only in certain cases. It greatly improves the performance from the previous version. Experiments corroborate this fact: we have analyzed a total of 10,736 files, generating a CFG from roughly 90%, in contrast with the 80% of the contracts that could be analyzed before. From the 10% remaining, only less than 1% of the contracts still fail due to our analysis. Besides, we achieve a great efficiency: CFG generation time takes less than 0,01% of the total time for the analysis. Another key feature of the proposed algorithm is that it can be easily implemented and adapted to other stack-based programs.