Contact: Björn Lisper
The course module aims to give an overview of static and dynamic program analysis, with some hands-on exercises to give practical experience of the techniques. After having taken the module the student should have an overall understanding how these techniques work, when they are applicable, how they relate to testing, and have knowledge of their respective strengths and weaknesses.
The module has two parts: static analysis, and dynamic analysis. The part on static analysis is examined through a hands-on exercise, where you are supposed to write a short report on your findings, and an assignment with some problems to solve where the solutions are to be sent in. The part on dynamic analysis is examined through a hands-on exercise with a short report.
You will have the opportunity to do the hands-on exercises at the final campus day, June 1st, 2016. We will provide lab computers where the tools to be used are pre-installed, and there will be an instructor available. We recommend that you use this opportunity. If you prefer to do the exercises by yourself, or if you want to start before the campus day, then it is possible to download the tools and install on your own computer (however note that the tool “Valgrind” only runs under linux). Directions for how to download the tools can be found in the instructions for the hands-on exercises.
Lab reports, and solutions to the assignment are to be sent to Björn Lisper.
The lectures for this module can also be found at the Scalable Learning website.
Static analysis
- (Video) Lecture 1: Introduction
- (Video) Lecture 2: Safety, and Relation to Testing
- (Video) Lecture 3: Different Kinds of Static Analysis
- (Video) Lecture 4: Dataflow Analysis
- (Video) Lecture 5: Basics of Value Analysis
- (Video) Lecture 6: An Interval Analysis Example
- (Video) Lecture 7: Tuning Value Analysis
- (Lab assignment) Astrée Hands-on Exercise (revised 2017-04-19)
- Example code: unroll.c
- Example code: insertsort.c
- Astrée home page at ENS (academia, original developers)
- Astrée home page at AbsInt (commercial tool provider)
- (Assignment) Assignment with Static Analysis Problems (revised 2015-11-05)
- Additional Reading
- Emanuelsson, P. and Nilsson, U. A Comparative Study of Industrial Static Analysis Tools. Electronic Notes in Theoretical Computer Science, 217:5-21, 2008. This study compares three commonly used commercial tools for static program analysis. The study is a couple of years old, but still provides interesting information how static analysis tools behave in practice.
- Wögerer, W. A Survey of Static Program Analysis Techniques. Report, Vienna University of Technology, Oct. 2005. This is a tutorial that explains, in some more depth than the lectures, the basics of data flow analysis, value analysis by abstract interpretation, and symbolic execution. (The latter is an interesting technique that we have not covered in the lectures.)
- Daniel Kästner et. al. Astrée: Proving the Absence of Runtime Errors. This paper describes the analysis tool Astrée, and some of its inner workings.
Dynamic analysis
- (Video) Lecture 8: Introduction
- (Video) Lecture 9: Implementing Dynamic Analysis
- (Video) Lecture 10: Valgrind
- (Video) Lecture 11: Memcheck
- (Lab assignment) Valgrind/Memcheck Hands-on Exercise (revised 2016-12-21)
- Additional Reading
- Gosain, A. and Sharma, G. A Survey of Dynamic Program Analysis Techniques and Tools. In Proc. 3rd International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA 2014), Advances in Intelligent Systems and Computing vol. 327, pp. 113-122, 2015. Springer International Publishing. This is a recent survey of techniques and tools for dynamic program analysis.