Static Worst-Case Resource Analysis for Substrate Pallets

We present saft, the first attempt of a static analyzer that extracts the asymptotic function complexity for the Polkadot/Substrate ecosystem, where the burden of accounting for computation resource consumption is put on the developer. saft is a tool meant to be used in a complementary way with pre-existing development tools to improve the Substrate-based blockchain security. saft combines two techniques to analyze the MIR generated from the compilation of the blockchain subsystems, the pallets: (i ) abstract interpretation for the over-approximation of the concrete semantics and extraction of complexity asymptotics and (ii ) symbolic execution to track the length of dynamically sized vectors, increasing the precision of (i ). The developers can then compare saft output with their resource consumption computation. Our experimental evaluation showed that the tool scales well with arbitrary pallets, given some manual specifications.