More Like this

1. Symbolic types for lenient symbolic execution

   https://doi.org/10.1145/3158128  

   Chang, Stephen; Knauth, Alex; Torlak, Emina (December 2017, Proceedings of the ACM on Programming Languages)

   We present lambda_sym, a typed λ-calculus forlenient symbolic execution, where some language constructs do not recognize symbolic values. Its type system, however, ensures safe behavior of all symbolic values in a program. Our calculus extends a base occurrence typing system with symbolic types and mutable state, making it a suitable model for both functional and imperative symbolically executed languages. Naively allowing mutation in this mixed setting introduces soundness issues, however, so we further addconcreteness polymorphism, which restores soundness without rejecting too many valid programs. To show that our calculus is a useful model for a real language, we implemented Typed Rosette, a typed extension of the solver-aided Rosette language. We evaluate Typed Rosette by porting a large code base, demonstrating that our type system accommodates a wide variety of symbolically executed programs. 

   more » « less
2. Symbolic powers

   Grifo, Eloísa (December 2021, Boletim do CIM)
3. Rational Singularities and Uniform Symbolic Topologies

   Walker, Robert M. (July 2016, Illinois journal of mathematics)
4. Relational Symbolic Execution

   https://doi.org/10.1145/3354166.3354175  

   Farina, Gian Pietro; Chong, Stephen; Gaboardi, Marco (October 2019, Proceedings of the 21st International Symposium on Principles and Practice of Programming Languages, PPDP 2019)
5. Symbolic router execution

   https://doi.org/10.1145/3544216.3544264  

   Zhang, Peng; Wang, Dan; Gember-Jacobson, Aaron (August 2022, Proceedings of the ACM SIGCOMM 2022 Conference)

   Network verification often requires analyzing properties across different spaces (header space, failure space, or their product) under different failure models (deterministic and/or probabilistic). Existing verifiers efficiently cover the header or failure space, but not both, and efficiently reason about deterministic or probabilistic failures, but not both. Consequently, no single verifier can support all analyses that require different space coverage and failure models. This paper introduces Symbolic Router Execution (SRE), a general and scalable verification engine that supports various analyses. SRE symbolically executes the network model to discover what we call packet failure equivalence classes (PFECs), each of which characterises a unique forwarding behavior across the product space of headers and failures. SRE enables various optimizations during the symbolic execution, while remaining agnostic of the failure model, so it scales to the product space in a general way. By using BDDs to encode symbolic headers and failures, various analyses reduce to graph algorithms (e.g., shortest-path) on the BDDs. Our evaluation using real and synthetic topologies show SRE achieves better or comparable performance when checking reachability, mining specifications, etc. compared to state-of-the-art methods. 

   more » « less