Parameterized Graph Algorithms and Their Role in Static Program Analysis

PhD Thesis Proposal Defence


Title: "Parameterized Graph Algorithms and Their Role in Static Program 
Analysis"

by

Miss Giovanna KOBUS CONRADO


Abstract:

Static analyses refer program analysis done prior to program execution, 
with goals such as speeding up the program, minimizing memory usage, or 
detecting potential errors and vulnerabilities. Although static analysis 
are usually expected to be efficient, many related problems are NP-hard 
or even undecidable. Here, we use parameterization graph algorithms to 
navigate these challenges.

Parameterized complexity analyzes problems and instances along multiple 
parameters on the input or output, allowing for more efficient solutions 
when an instance has lower inherent difficulty. This thesis will focus 
on multiple studies that show parameterization can be used as a 
versatile tool to speed up static analysis.

We will firstly present a couple of studies that exemplify how to design 
algorithms parameterized by structural graph parameters. These serve as 
an introduction to the topic of parameterized complexity. We will then 
present methods that rely on parameterized algorithms to solve static 
program analysis problems. These include speeding up register allocation 
by presenting a bound on the pathwidth of control-flow graphs, using 
graph parameters to process on-demand algebraic program analysis 
queries, and using a parameterized generalization of context-free 
grammars to identify context and field-sensitive data-flow.

In each case, we develop new algorithms for these static analysis 
problems and experimentally demonstrate their efficiency compared to 
previous methods.


Date:                   Wednesday, 27 November 2024

Time:                   4:00pm - 6:00pm

Venue:                  Room 5501
                        Lifts 25/26

Committee Members:      Dr. Amir Goharshady (Supervisor)
                        Prof. Pedro Sander (Supervisor)
                        Dr. Sunil Arya (Chairperson)
                        Prof. Charles Zhang