Property-Based Testing of Abstract Machines: an Experience Report

Authors: Francesco Komauli and Alberto Momigliano

Paper Information

Title:Property-Based Testing of Abstract Machines: an Experience Report
Authors:Francesco Komauli and Alberto Momigliano
Proceedings:LFMTP Regular papers
Editors: Giselle Reis and Frédéric Blanqui
Keywords:mechanized meta-theory, property-based testing, typed assembly languages, exhaustive and randomized data generation

ABSTRACT. Contrary to Dijkstra's diktat, testing, and more in general, validation, has found an increasing niche in formal verification, prior or even in alternative to theorem proving. Validation, and in particular, property-based testing (PBT) is quite effective in mechanized meta-theory of programming languages, where theorems have shallow but tedious proofs that may go wrong for fairly banal mistakes in specifications. In this report, we abandon the comfort of high-level object languages and address the validation of abstract machines and typed assembly languages. We concentrate on Appel and Leroy's List-machine benchmark (JAR, 2012), which we tackle both with alphaCheck, the simple model-checker on top of the nominal logic programming alphaProlog and the PBT library FSCheck for F#. This allows us to compare the relative merits of exhaustive-based PBT in a logic programming style versus the more usual randomized functional setting. We uncover one major bug in the published version of the paper, plus several typos and ambiguities thereof. This is particularly striking, as the paper is accompanied by two full formalizations, in Coq and Twelf. Finally, we do a bit of mutation testing on the given model, to asses further the trade-off between exhaustive and randomized data generation. Spoiler alert: the former performs better.

Talk:Jul 07 12:20 (Session 26H: Verification and Testing)