School of Computer Science (SCS) researchers' groundbreaking work on interleaved Dyck-reachability (InterDyck-reachability) received a Distinguished Paper Award at the Programming Language Design and Implementation (PLDI) conference this month.

The research makes program analysis simpler and more efficient by eliminating ineffective parts of the graph.

“InterDyck reachability is perhaps the most popular abstraction to perform interprocedural program analysis,” said Yuanbo Li, a Ph.D. student in SCS and co-author on the paper.

Many program analysis problems can be viewed as analyzing matching properties in graphs. InterDyck languages can help illuminate those properties. As a balanced-parentheses language, Dyck languages are often used to match one particular program property (such as function calls and returns), but the InterDyck language enables matching multiple balanced-parenthesis properties in program analysis simultaneously. Unfortunately, it's impossible to obtain the exact solution for InterDyck-reachability problems in general.

This research offers a framework to make the existing InterDyck-reachability algorithms more precise and scalable. If a graph edge isn’t contributing, it can be eliminated from the underlying input graph G.

“An edge is removable if and only if it won't affect the precise all-pairs reachability information, but computing the precise solution is undecidable,” Li said. “We are computing an over-approximation of InterDyck reachability. Therefore, we could safely identify a subset of removable edges.”

The researchers’ algorithm simplifies the input graphs and improves exisiting InterDyck reachability algorithms. After applying the simplification algorithm to a taint analysis for Android, all existing InterDyck-reachability algorithms ran much faster and became more precise. In the future, the researchers hope to apply the concept to even more general static analyses.

Li wrote the paper, Fast Graph Simplification for Interleaved Dyck-Reachability, with SCS Assistant Professor Qirun Zhang  and University of Wisconsin, Madison Professor Thomas Reps. They presented it at the 41st PLDI, an Association for Computing Machinery Special Interest Group on Programming Languages (ACM SIGPLAN) conference, held virtually from June 15 to 20.

This was one of three SCS papers at the conference. Zhang and Li presented another paper Debug Information Validation for Optimized Code, co-authored with SCS Ph.D. student Shuo Ding and Apple’s Davide Italiano. Professor Santosh Pande also presented BlankIt Library Debloating: Getting What You Want Instead of Cutting What You Don’t with SCS Ph.D. student co-authors Prithayan Barua, Girish Mururu, and Chris Porter.