Anton Risberg Alaküla's PhD defence

Thesis title: Live Exploration and Testing of Source Code Analyzers

Author: Anton Risberg Alaküla, Department of Computer Science, Lund University

Faculty opponent: Associate Professor Matthias Hauswirth, Università della Svizzera italiana (USI), Lugano, Switzerland

Examination Committee:

• Professor Regina Hebig, University of Rostock, Germany
• Professor David Broman, KTH Royal Institute of Technology
• Associate Professor Mircea Lungu, IT University Copenhagen, Denmark
• Deputy: Senior Lecturer Flavius Gruian, Lund University

Session chair: Professor Björn Regnell, Lund University

Supervisors:

• Main supervisor: Professor Görel Hedin, Lund University
• Associate Senior Lecturer Niklas Fors, Lund University

Location: E:1406, E-huset, Klas Anshelms väg 10/Ole Römers väg 3, Lund

Here is a link to the thesis in Research Portal (opens in new window)

Abstract

Source code analysis is central in software development tools, for example in compilers to detect compile-time errors and possible optimizations, in IDEs to provide interactive coding assistance, and in stand-alone analysis tools to detect bugs. Many source code analyses can be composed of a set of smaller, connected analysis steps. For example, the static semantic analysis performed by a compiler typically depends on type analysis, which in turn depends on name analysis. A tool typically only exposes the final step to end users, but during development it is beneficial to be able to explore and test all intermediate steps as well.

In this thesis we explore tools and techniques for simplifying the development of source code analyzers, particularly focusing on exploring and testing intermediate analysis steps. We introduce the concept of property probes to support this goal. Property probes enable efficient and robust interaction with computations associated with nodes in abstract syntax trees (ASTs). This thesis presents the different kinds of probes, and associated algorithms for creating and applying them. We also present benchmarks showing that performance scales well for real-world development tasks.

We have implemented property probes in a tool called CodeProber. CodeProber has been integrated into two university courses on compilers and program analysis as an aid during lab assignments. We performed an in-depth user study on students in one of the courses, and found overall very positive feedback.

Property probes work well with analysis formalisms such as Attribute Grammars (AGs) which associate functionality with nodes in a tree structure. In AGs, attributes are supposed to be specified in a declarative way, free from side effects. However, in practice, side effects may still exist, and this can cause subtle bugs that are hard to debug. In this thesis we present algorithms that can be used to dynamically test for the presence of side effects. We applied these algorithms to a Java compiler and found 13 issues, including nondeterministic code generation.

Finally, in this thesis we present text probes, a language for unit testing source code analysis results. Text probes are structured comments in source files, and they enable tests that are a small fraction of the size of a traditional unit test. They also fit well in an agile test-driven development workflow. We added text probe support to CodeProber, which gives the developer code completion while creating tests, and live feedback on the test results.