Reading List

To make the most out of this course, you should reserve enough time to read papers. One paper is required, and thus directly examinable.

The recommended reading is divided into “Highly Recommended Reading”, which is directly related to the material covered in class, and “Additional Reading”, which will help you gain a deeper knowledge of the topics we cover.

Advice on Studying Papers

Take a look at this short paper on How to Read a Paper. This paper suggests an effective scheme for quickly getting to grips with a paper. You may find this useful when looking at the papers below. However, if you do follow this advice then consider limiting your “third pass”: the paper suggests that this may take 4-5 hours per paper, which is a bit much for this course.

You are strongly encouraged to study these papers collaboratively, with colleagues on the course.

To download some of these papers, you should be connected to the Imperial network.

Required Reading

• Xi Wang, Nickolai Zeldovich, M. Frans Kaashoek, Armando Solar-Lezama: Towards Optimization-Safe Systems: Analyzing the Impact of Undefined Behavior. ACM Symposium on Operating Systems Principles (SOSP 2013).

Coursework-related Papers

You should read the papers under “Topic: Fuzzing” to get inspiration for the first open-ended coursework. In addition, you might want to read the following:

• Michał Zalewski. American Fuzzy Lop README and American Fuzzy Lop “whitepaper”
• Robert Brummayer, Armin Biere: Fuzzing and Delta-Debugging SMT solvers. The International Workshop on Satisfiability Modulo Theories (SMT 2009).

Highly Recommended Reading

Topic: Introduction

• Nancy Leveson: Medical Devices: The Therac-25, Appendix to “Software: System Safety and Computers”, 1995.
• Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, Dawson Engler: A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World. Communications of the ACM, 2010.
  

Topic: Fuzzing

• Barton P. Miller, Louis Fredriksen, Bryan So: An Empirical Study of the Reliability of UNIX Utilities. Communications of the ACM 33:12, 1990.
• Alex Groce, Chaoqiang Zhang, Eric Eide, Yang Chen, John Regehr: Swarm Testing. International Symposium on Software Testing and Analysis (ISSTA 2009).
  

Topic: Compiler Testing & Derived Test Oracles

• Xuejun Yang, Yang Chen, Eric Eide, John Regehr: Finding and Understanding Bugs in C Compilers. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2011).
• Vu Le, Mehrdad Afshari, Zhendong Su: Compiler Validation via Equivalence Modulo Inputs. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2014).
• Zhi Quan Zhou, D. H. Huang, T. H. Tse, Zongyuan Yang, Haitao Huang, T. Y. Chen: Metamorphic Testing and its Applications. International Symposium on Future Software Technology (ISFST 2004).
  

Topic: Undefined Behaviour

• John Regehr: A Guide to Undefined Behaviour in C and C++ Part 1.
• Required reading by Wang et al. (see above)
  

Topic: Compiler Sanitizers

• Konstantin Serebryany, Derek Bruening, Alexander Potapenko, Dmitry Vyukov: AddressSanitizer: A Fast Address Sanity Checker. USENIX Annual Technical Conference (USENIX ATC 2012).
• Evgeniy Stepanov, Konstantin Serebryany: MemorySanitizer: Fast Detector of C Uninitialized Memory Use in C++. IEEE/ACM International Symposium on Code Generation and Optimization (CGO 2015).
  

Topic: Dynamic Symbolic Execution

• Cristian Cadar, Vijay Ganesh, Peter M. Pawlowski, David L. Dill, Dawson R. Engler: EXE: Automatically Generating Inputs of Death. ACM Transactions on Information and System Security, 2008.
• Cristian Cadar, Daniel Dunbar, Dawson R. Engler: KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. USENIX Symposium on Operating Systems Design and Implementation (OSDI 2008).
• Peter Boonstoppel, Cristian Cadar, Dawson R. Engler: RWSet: Attacking Path Explosion in Constrained-Based Test Generation. International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2008).
  

Topic: Data Flow Analysis

• Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman: Chapters 9.2 and 9.3 - Compilers: Principles, Techniques, and Tools (2nd edition).

Topic: Coverage Criteria & Mutation Testing

• Kelly J. Hayhurst, Dan S. Veerhusen, John J. Chilenski, Leanna K. Rierson: Sections 2 and 4 - A Practical Tutorial on Modified Condition/ Decision Coverage. NASA Technical Report, 2001.
• Yue Jia, Mark Harman: An Analysis and Survey of the Development of Mutation Testing . IEEE Transactions on Software Engineering, 2011.
  

Additional Reading

• Topic: Fuzzing. Barton P. Miller, David Koski, Cjin Pheow Lee, Vivekananda Maganty, Ravi Murthy, Ajitkumar Natarajan, Jeff Steidl: Fuzz Revisited: A Re-examination of the Reliability of UNIX Utilities and Services. Technical report.
• Topic: Compiler Testing & Derived Test Oracles. Christopher Lidbury, Andrei Lascu, Nathan Chong, Alastair F. Donaldson: Many-core Compiler Fuzzing. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2015).
• Topic: Compiler Testing & Derived Test Oracles. John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang. Test-Case Reduction for C Compiler Bugs. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2012).
• Topic: Compiler Testing & Derived Test Oracles. Earl T. Barr, Mark Harman, Phil McMinn, Muzammil Shahbaz, Shin Yoo: The Oracle Problem in Software Testing: A Survey. IEEE Transactions on Software Engineering, 2014.
• Topic: Undefined Behaviour. Xi Wang, Haogang Chen, Alvin Cheung, Zhihao Jia, Nickolai Zeldovich, M. Frans Kaashoek: Undefined Behavior: What Happened to My Code?. ACM SIGOPS Asia-Pacific Workshop on Systems (APSys 2012).