Abstract: Static program analyses are often formulated as graph-theoretic problems on the control-flow graphs (CFGs) of the underlying program. Treewidth is a structural parameter that formally measures how similar a graph is to a tree, and CFGs form the most well-known real-world family of low-treewidth graphs. In this talk I will present recent algorithmic advances that exploit the low-treewidth property of CFGs for improving the complexity of various static program analyses. In particular, I will cover (i) on-demand interprocedural algebraic analysis, (ii) static library summarization for data-dependence analysis, and (iii) intraprocedural algebraic analysis of concurrent programs. The talk will be mostly theoretical, followed by some preliminary experiments which demonstrate that the theoretical improvements are also realizable in practice.
Bio: Andreas Pavlogiannis is an assistant professor at the Department of Computer Science in Aarhus University, Denmark. His research focuses on algorithmic aspects of programming languages and software verification. He develops algorithms -- based on rigorous foundations such as automata theory, graph theory and combinatorial optimization -- which reason about program correctness and efficiency.
