Extra Seminar Computer Science

Title:

New Algorithms for Static Program Analysis

ABSTRACT

Modern-day software is increasingly complex and software engineering is commonly accepted as a challenging, error-prone task. Consequently, software bugs are prevalent, incurring detrimental financial costs and often risking human lives. Static analyses are lightweight approximations to program behavior and largely constitute the first effective step to automated bug detection in the software development process.

In this talk, I will introduce the Algebraic Path Problem on Recursive Graphs (APP) and its close variant of Dyck Reachability (DR). These problems serve as algorithmic formulations of static analyses on various domains, such as dataflow/alias/data-dependence analysis and program slicing. I will present recent algorithmic advances on APP and DR that lead to theoretical complexity improvements and provide a significant scalability boost in practice. In addition, the new techniques are more effective in dealing with incremental updates of codebases, and are thus better suited to today's software development lifecycle. Finally, I will present quantitative extensions to APP that can assist with code optimization at compilation time.