Symbolic execution in Haskell sped up with configurable embeddings

SymFC: Configurable Semantics for All Paths Symbolic Execution in Haskell via Embeddings

Programming Languages

Summary

Checking programs automatically for bugs or errors can be slow and limited in Haskell because existing tools struggle with many language features and real-world code. The authors created SymFC, which lets symbolic execution be customized using ordinary Haskell functions called embeddings. These embeddings improve speed and flexibility by allowing more kinds of code, including input/output operations, to be analyzed symbolically. SymFC runs inside the Haskell compiler and showed faster performance on real libraries than previous tools.

What this means in practice

  • For functional programming developers: Use SymFC to symbolically verify complex Haskell programs including IO and pointer-related operations more efficiently than past tools allowed.
  • For hardware design teams: Employ SymFC embeddings to verify hardware described in the Clash language within Haskell using symbolic execution.

Authors

Robin Webbers, Wind Wong, Klaus v. Gleissenthall

Abstract

Lightweight methods like QuickCheck have proven to be successful in functional languages and beyond, as they let users specify properties as Boolean functions directly in code. We can replicate some of their benefits for (bounded) proofs via symbolic execution. If we can execute arbitrary functions symbolically, we can specify properties just as easily. Unfortunately, existing symbolic execution tools for Haskell are restricted to a subset of the language that excludes many real-world applications like IO; they also have a hard time scaling to larger programs, making them a poor fit for general purpose lightweight verification. One reason behind these limitations is that existing techniques only offer fixed symbolic semantics for SMT base types. This makes it hard to cover more programming constructs and libraries; it also makes it difficult to fine-tune symbolic representations for better performance. We present SymFC, a new symbolic execution method for Haskell that offers configurable semantics via embeddings. An embedding of a function in SymFC is just another Haskell function that can use arbitrary code, as well as SMT primitives. Embeddings make it easy to support new programming constructs and fine-tune symbolic representations for speed. To integrate embeddings into Haskell's type system, we make use of Haskell's coercions, which let us transparently convert between a Haskell type and the type of its embedding. We realize embeddings in SymFC, an all-paths symbolic execution engine for Haskell, which lets us symbolically represent arbitrary types and values in GHC core. We implement SymFC as a GHC plugin, and evaluate it by checking properties of Haskell's container library, and the iproute library. We build embeddings for IORef, Haskell's Ptr/ForeignPtr interface, and the hardware library Clash, and our evaluation reports a 6.25x speedup on G2's own benchmarks.