Parameterized Algorithms for Graph-based Program Analyses

PhD Qualifying Examination


Title: "Parameterized Algorithms for Graph-based Program Analyses"

by

Mr. Kerim KOCHEKOV


Abstract:

Parameterized complexity is a way of dealing with hard algorithmic problems. It
primarily analyzes NP-hard problem instances along with extra parameters on the
input. Suggesting an algorithm that builds complexity based on defined extra
parameters enables us to solve problems in polynomial time. This work focuses
on graph problems to facilitate program analysis. It is widely recognized that
programs can be represented with control-flow and call graphs (CFGs and CGs),
allowing us to exploit the structural sparsity properties for obtaining faster
algorithms. In addition to the main concept, we will provide descriptions of
various structural graph parameters and techniques, such as dynamic
programming, that are utilized in designing fixed-parameter tractable
algorithms. These techniques have been applied to classical sample problems in
this work like Vertex Cover and Graph Coloring to enhance clarity.

The treewidth and treedepth are arguably the most commonly used graph
parameters. Throughout this work, we have used them as well to achieve
remarkable speedup for interprocedural and intraprocedural Algebraic Program
Analysis (APA) on real-world programs, based on the well-known claim that CFG
of structured goto-free programs has a bounded treewidth. The APA framework
models a wide variety of static analysis tasks, including dataflow analysis,
recurrence analysis, predicate abstraction, and invariant generation. It first
computes a regular expression ? that captures all program paths of interest in
a closed-form solution and then interprets it based on program semantics. This
regular expression ? is then interpreted over the algebra to obtain the desired
result. The main objective of this work is to achieve faster runtimes for
on-demand APA compared to repeated application of classical APA. In an
on-demand setting for APA, the program is given as input and can be
preprocessed. The analysis needs to answer a large number of online queries,
each providing a pair (s, t) of program lines representing the start and end
point of the query, respectively. The goal is to avoid the significant cost of
running a fresh APA instance for each query. Our algorithm uses an elegant
combination of tree decompositions and centroid decompositions, which was
previously unknown and helps avoid the treewidth blowup present in prior
treewidth-based static analyses in the literature.


Date:                   Friday, 8 December 2023

Time:                   3:30pm - 5:30pm

Venue:                  Room 3494
                        lifts 25/26

Committee Members:      Dr. Amir Goharshady (Supervisor)
                        Prof. Cunsheng Ding (Chairperson)
                        Prof. Mordecai Golin
                        Prof. Pedro Sander


**** ALL are Welcome ****