Conformance Testing of Formal Semantics using Grammar-based Fuzzing
In our work “A Denotational Semantics of Solidity in Isabelle/HOL” [1] we presented a formal semantics for Solidity, the most common language for implementing smart contracts. Such a formal semantics one of the corner stones of developing a formal verification approach that, mathematically, can prove the absence of certain types of bugs (e.g., such as the Parity Wallet bug that made USD 280mil worth of Ether inaccessible).
But, of course, any verification can only be as good as the underlying semantics. So, how do we ensure that our formal semantics actually captures the behavior of Solidity faithfully? This is the question we answer in our latest paper [2] that will be presented at the International Conference on Tests and Proofs.
In our approach, we use grammar-based fuzzing, a technique that generates example programs from a formal grammar. Our goal is to ensure that our post-hoc developed formal semantics of Solidity complies to the real world system, i.e., our formalization should behave identical to the implementation. For ensuring this, we generate a test oracle from our formal specification, which allows us to check that executing a test case (generated by the grammar-based fuzzer) executed on the formal semantics yields the same result as executed on the Ethereum blockchain. Our main contributions are:
- An approach extending a parse grammar for Solidity to ensure that a generic grammar-based fuzzer generates type correct Solidity programs, instead of generating syntactically correct, but often ill-typed, programs.
- An approach for automatically deriving a test-oracle from a formal specification in Isabelle/HOL that allows to efficiently decide if a test case passes or fails and that allows to measure the test coverage in terms of statements and expressions of the target language usually based on an implicit test specification that informally can be described as “no crashes occur”.
- A framework for testing the compliance of a formal semantics of Solidity in Isabelle/HOL to their execution on the Ethereum blockchain
Update: The formalization is now also available in the Archive of Formal Proofs [3].