A complexity measure for smart contracts
Measuring the complexity of a computer software can predict the expected testing and maintenance costs, as well as the likelihood for bugs.
McCabe’s Cyclomatic complexity is the most popular complexity measure among industrial software analysis tools. It measures the number of different paths in a software code (formally, the number of linearly independent paths). Having path testing in mind, this metric fully predicts the amount of such tests that will be required for a standard program.
For smart contracts, however, testing is only part of the quality assurance process. Having complex interactions with external contracts and storage dictates a manual review process that takes into account all the possible different interactions. Hence, we propose a new complexity measure, namely, the smart contract cyclomatic complexity. This complexity counts the number of different paths that triggers a change in the blockchain state (e.g., write to storage, send ETH, or perform state changing external calls).
In this research, we give a formal definition for the cyclomatic complexity of smart contracts, we implement an open source tool, on top of the woke framework to automatically calculate the complexity of a single smart contract, and we run the tool on MakerDAO’s dss system.
Formal definition
Control flow graph
A control-flow graph (CFG) is a representation, using graph notation, of all paths that might be traversed through a program during its execution.
Below is an example of a solidity function, and the control flow graph that woke generated for it.
function abs(uint a, uint b) public returns(uint) {
uint result;
if(a > b) {
result = a - b;
else {
result = b- a;
}
return result;
} To analyse a full contract, we add an auxiliary root node, with an edge to the entry node of every external and public function. In addition, we also connect the function calls with their respective entry nodes.
Linearly independent paths
The set of all linearly independent paths is the maximal set of program execution paths (w.r.t inclusion) such that in every path there is one edge that does not occur in any of the other paths.
For the purpose of smart contract complexity, we extend this definition, and define the set of linearly independent paths w.r.t blockchain state changes. This is defined as the maximal set of runs such that in every run there is one blockchain state change that does not occur in any of the other paths.
Smart cyclomatic complexity
The smart cyclomatic complexity of a section of source code is the number of linearly independent paths w.r.t blockchain state changes within it.
Implementation
We implemented a printer to the woke static analysis framework. Our code is available here. We thank our friends from the woke telegram group for their great technical support and walkthrough.
Experimental results
We ran our analysis on MakerDAO’s core smart contracts (dss), on each contract separately. The dss consists of 15 smart contracts, and can be found here.
For each contract, we plotted the full control graph. The entry node is labelled in green, and state changing nodes are labelled in red.
We then stripped away all the non state changing nodes that do not contain any branching.
We calculate the cyclomatic complexity for both graphs, and get the classic and smart cyclomatic complexities.
The results are depicted in the table below:
The jug smart contract has the lowest ratio between smart and classic complexity. This is because it contains very little logic other than a complex function for exponent calculation. This function contains a lot of branching statements, however it is a pure function that does not change any state.
Another interesting observation is that the clip and end contracts complexity is significantly higher than the one of the vat, despite having similar classic complexity. And indeed, few bugs were already detected (and patched) in the end contract, and the clip contract is a fix to the old MakerDAO’s liquidation mechanism, which was deprecated due to an economical bug. This is in sharp contrast to the vat contract that is live since the inception of DAI 2.0, and never had any significant issues.
About Risk DAO
Risk DAO is a service DAO focused on providing a new, open-source risk assessment framework, associated audits, and dashboards to stress test, monitor, and manage risk in DeFi lending and borrowing protocols as well as L1 and L2 networks.
You can follow us on Twitter here. You can join our Discord here.
