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:

  1. 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.
  2. 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”.
  3. 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].


D. Marmsoler and A. D. Brucker, A denotational semantics of Solidity in Isabelle/HOL,” in Software engineering and formal methods (SEFM), R. Calinescu and C. Pasareanu, Eds. Heidelberg: Springer-Verlag, 2021.
D. Marmsoler and A. D. Brucker, Conformance testing of formal semantics using grammar-based fuzzing,” in TAP 2022: Tests and proofs, L. Kovacs and K. Meinke, Eds. Heidelberg: Springer-Verlag, 2022.
D. Marmsoler and A. D. Brucker, Isabelle/solidity: A deep embedding of solidity in isabelle/HOL,” Archive of Formal Proofs, Jul. 2022,

Welcome to the blog of the Software Assurance & Security Research Team at the University of Exeter. We blog regularly news, tips & tricks, as well as fun facts about software assurance, reliability, security, testing, verification, hacking, and logic.

You can also follow us on Twitter: @logicalhacking.




academia ai android apidesign appsec bitcoin blockchain bpmn browser browserextensions browsersecurity bug certification chrome composition cordova dast devops devsecops dom dsbd efsm epsrc event extensions fixeffort floss formaldocument formalmethods funding hol-ocl hol-testgen humanfactor hybridapps iast industry internetofthings iot isabelle/hol isabelledof isadof latex logic maintance malicous mbst mobile mobile apps modelinference modeling monads monitoring msc ocl ontology opensource owasp patches pet phd phdlife phishing policy protocols publishing reliability research safelinks safety sap sast sdlc secdevops secureprogramming security securityengineering securitytesting semantics servicecomposition skills smartcontract smartthings softwareeinginering softwaresecurity softwaresupplychain solidity staff&positions statemachine studentproject tcb test&proof testing tips&tricks tools transport tuos uk uoe upgrade usability verification vulnerabilities vulnerableapplication webinar websecurity


blog whole site