Testing Dafny (experience paper)
Authors:
Open Access
- 18 July 2022
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 556-567
Abstract
Verification toolchains are widely used to prove the correctness of critical software systems. To build confidence in their results, it is important to develop testing frameworks that help detect bugs in these toolchains. Inspired by the success of fuzzing in finding bugs in compilers and SMT solvers, we have built the first fuzzing and differential testing framework for Dafny, a high-level programming language with a Floyd-Hoare-style program verifier and compilers to C#, Java, Go, and Javascript. This paper presents our experience building and using XDsmith, a testing framework that targets the entire Dafny toolchain, from verification to compilation. XDsmith randomly generates annotated programs in a subset of Dafny that is free of loops and heap-mutating operations. The generated programs include preconditions, postconditions, and assertions, and they have a known verification outcome. These programs are used to test the soundness and precision of the Dafny verifier, and to perform differential testing on the four Dafny compilers. Using XDsmith, we uncovered 31 bugs across the Dafny verifier and compilers, each of which has been confirmed by the Dafny developers. Moreover, 8 of these bugs have been fixed in the mainline release of Dafny.Keywords
This publication has 33 references indexed in Scilit:
- Analysing the program analyser2016
- IronFleet2015
- Adaptive Concretization for Parallel Program Synthesis2015
- Testing Static Analyzers with Randomly Generated Programs2012
- The 1st Verified Software Competition: Experience ReportLecture Notes in Computer Science, 2011
- Dafny: An Automatic Program Verifier for Functional Correctness2010
- A Formally Verified Compiler Back-endJournal of Automated Reasoning, 2009
- Survey of compiler testing methodsProgramming and Computer Software, 2005
- Assigning Meanings to Programs1993
- An axiomatic basis for computer programmingCommunications of the ACM, 1969