Researchers Win Distinguished Paper Award at Top Programming Language Conference


Tess Malone, Communications Officer

Sidebar Content
No sidebar content submitted.

Summary Sentence:

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

Full Summary:

No summary paragraph submitted.

  • PLDI graph PLDI graph

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.

Additional Information


School of Computer Science

No categories were selected.
Related Core Research Areas
No core research areas were selected.
Newsroom Topics
No newsroom topics were selected.
No keywords were submitted.
  • Created By: Tess Malone
  • Workflow Status: Published
  • Created On: Jun 15, 2020 - 1:07pm
  • Last Updated: Jun 15, 2020 - 1:49pm