SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Fri 22 Oct 2021 14:20 - 14:35 at Zurich E - OOPSLA 2020 Papers 5 Chair(s): Yao Li

Building effective symbolic execution engines is challenging in multiple dimensions: an engine must \emph{correctly} model the program semantics, provide \emph{flexibility} in terms of various symbolic execution strategies, and execute these strategies \emph{efficiently}.

This paper proposes a principled approach to building \emph{correct}, \emph{flexible}, and \emph{efficient} symbolic execution engines, directly rooted in the semantics of the underlying language expressed as a high-level definitional interpreter. Starting from this definitional interpreter, we use algebraic effects to model the semantics of symbolic execution, e.g., collecting path conditions as a state effect, and exploring multiple paths as a nondeterminism effect. Different handlers of these effects give rise to different symbolic execution strategies which make execution strategies orthogonal to the symbolic semantics, thus improving flexibility. Furthermore, by annotating the symbolic definitional interpreter with binding-times and specializing it to the input program via the first Futamura projection, we obtain a ``symbolic compiler,'' generating efficient code that is instrumented with the symbolic execution semantics. This staging approach reconciles the interpretation- and instrumentation-based approaches to building symbolic execution engines in a uniform framework.

We illustrate the approach for a simple imperative language step-by-step, and then scale up to a significant subset of LLVM IR. We also show effect handlers for a number of common path selection strategies. We evaluate the performance of our prototype and compare with KLEE, showing that the compiled symbolic execution is an order of magnitude faster than the pure interpretation-based counterpart, as well as being on par with KLEE on single execution path traversal.

Fri 22 Oct

Displayed time zone: Central Time (US & Canada) change

13:50 - 15:10
OOPSLA 2020 Papers 5SIGPLAN Papers at Zurich E
Chair(s): Yao Li University of Pennsylvania
13:50
15m
Talk
Gradual Verification of Recursive Heap Data Structures
SIGPLAN Papers
Jenna Wise Carnegie Mellon University, Johannes Bader Jane Street, Cameron Wong Jane Street, Jonathan Aldrich Carnegie Mellon University, Éric Tanter University of Chile, Joshua Sunshine Carnegie Mellon University
14:05
15m
Talk
Formulog: Datalog for SMT-based Static Analysis
SIGPLAN Papers
Aaron Bembenek Harvard University, Michael Greenberg Stevens Institute of Technology, Stephen Chong Harvard University
14:20
15m
Talk
Compiling Symbolic Execution with Staging and Algebraic Effects
SIGPLAN Papers
Guannan Wei Purdue University, Oliver Bračevac Purdue University, Shangyin Tan Purdue University, Tiark Rompf Purdue University
14:35
15m
Talk
Automated Policy Synthesis for System Call Sandboxing
SIGPLAN Papers
Shankara Pailoor University of Texas at Austin, Xinyu Wang University of Michigan, Hovav Shacham University of Texas at Austin, Isil Dillig University of Texas at Austin
DOI
14:50
20m
Live Q&A
Discussion, Questions and Answers
SIGPLAN Papers