Symbolic Execution and Quantitative Reasoning Applications to Software Safety and Security

This book reviews recent advances in symbolic execution and its probabilistic variant and discusses how they can be used to ensure the safety and security of software systems. Symbolic execution is a systematic program analysis technique which explores multiple program behaviors all at once by collecting and solving symbolic constraints collected from the branching conditions in the program. The obtained solutions can be used as test inputs that execute feasible program paths. Symbolic execution has found many applications in various domains, such as security, smartphone applications, operating systems, databases, and more recently deep neural networks, uncovering subtle errors and unknown vulnerabilities. We review here the technique has also been extended to reason about algorithmic complexity and resource consumption.

Furthermore, symbolic execution has been recently extended with probabilistic reasoning, allowing one to reason about quantitative properties of software systems. The approach computes the conditions to reach target program events of interest and uses model counting to quantify the fraction of the input domain satisfying these conditions thus computing the probability of event occurrence. This probabilistic information can be used for example to compute the reliability of an aircraft controller under different wind conditions (modeled probabilistically) or to quantify the leakage of sensitive data in a software system, using information theory metrics such as Shannon entropy.

This book is intended for students and software engineers who are interested in advanced techniques for testing and verifying software systems.

Acknowledgments.- Introduction.- Symbolic Execution: The Basics.- Symbolic Complexity Analysis.- Probabilistic Reasoning.- Side-Channel Analysis.- Conclusion and Directions for the Future.- Bibliography.- Author's Biography.

Corina S. Pasareanu is an ACM distinguished scientist, working at NASA Ames Research Center. She is affiliated with Carnegie Mellon University’s CyLab and holds a courtesy appointment in Electrical and Computer Engineering. At Ames, she is developing and extending Symbolic PathFinder, a symbolic execution tool for Java bytecode. Her research interests include model checking and automated testing, compositional verification, model-based development, probabilistic software analysis, software engineering for machine learning, autonomy, and security. She is the recipient of several awards, including ASE Most Influential Paper Award (2018), ESEC/FSE Test of Time Award (2018), ISSTA Retrospective Impact Paper Award (2018), ACM Impact Paper Award (2010), and ICSE2010 Most Influential Paper Award (2010). She has been serving as Program or General Chair for several conferences including: FM 2021, ICST 2020, ISSTA2020, ESEC/FSE 2018, CAV 2015, ISSTA 2014, ASE 2011, and NFM 2009.She is currently an associate editor for the IEEE TSE Journal.