{"636232":{"#nid":"636232","#data":{"type":"news","title":"Researchers Win Distinguished Paper Award at Top Programming Language Conference","body":[{"value":"\u003Cp\u003ESchool of Computer Science (SCS) researchers\u0026#39; groundbreaking work on interleaved Dyck-reachability (InterDyck-reachability) received a Distinguished Paper Award at the \u003Ca href=\u0022https:\/\/conf.researchr.org\/home\/pldi-2020\u0022\u003EProgramming Language Design and Implementation (PLDI)\u003C\/a\u003E conference this month.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe research makes program analysis simpler and more efficient by eliminating ineffective parts of the graph.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;InterDyck reachability is perhaps the most popular abstraction to perform interprocedural\u0026nbsp;program analysis,\u0026rdquo; said \u003Ca href=\u0022https:\/\/www.linkedin.com\/in\/yuanbo-li-2a2801132\u0022\u003E\u003Cstrong\u003EYuanbo Li\u003C\/strong\u003E\u003C\/a\u003E, a Ph.D. student in SCS and co-author on the paper.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EMany 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\u0026#39;s impossible to obtain the exact solution for InterDyck-reachability problems in general.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis research offers a framework to make the existing InterDyck-reachability algorithms more precise and scalable. If a graph edge isn\u0026rsquo;t contributing, it can be eliminated from the underlying input graph G.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;An edge is removable if and only if it won\u0026#39;t affect the precise all-pairs reachability information, but computing the precise solution is undecidable,\u0026rdquo; Li said. \u0026ldquo;We are computing an over-approximation of InterDyck reachability. Therefore, we could safely identify a subset of removable edges.\u0026rdquo;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe researchers\u0026rsquo; 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.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ELi wrote the paper\u003Cem\u003E, \u003C\/em\u003E\u003Ca href=\u0022https:\/\/www.cc.gatech.edu\/~qzhang414\/papers\/pldi20_yuanbo2.pdf\u0022\u003E\u003Cem\u003EFast Graph Simplification for Interleaved Dyck-Reachability\u003C\/em\u003E\u003C\/a\u003E\u003Cstrong\u003E, \u003C\/strong\u003Ewith SCS Assistant Professor \u003Ca href=\u0022https:\/\/www.cc.gatech.edu\/~qzhang414\/\u0022\u003E\u003Cstrong\u003EQirun Zhang \u003C\/strong\u003E\u003C\/a\u003E\u003Cstrong\u003E\u0026nbsp;\u003C\/strong\u003Eand\u003Cstrong\u003E \u003C\/strong\u003EUniversity of Wisconsin, Madison Professor \u003Cstrong\u003EThomas Reps\u003C\/strong\u003E. 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.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis was one of three SCS papers at the conference. Zhang and Li presented another paper \u003Ca href=\u0022https:\/\/www.cc.gatech.edu\/~qzhang414\/papers\/pldi20_yuanbo1.pdf\u0022\u003E\u003Cem\u003EDebug Information Validation for Optimized Code\u003C\/em\u003E\u003C\/a\u003E\u003Cem\u003E,\u003C\/em\u003E\u003Cstrong\u003E \u003C\/strong\u003Eco-authored with SCS Ph.D. student\u003Cstrong\u003E \u003C\/strong\u003E\u003Cstrong\u003EShuo Ding \u003C\/strong\u003Eand Apple\u0026rsquo;s \u003Cstrong\u003EDavide Italiano\u003C\/strong\u003E. Professor \u003Ca href=\u0022https:\/\/sites.google.com\/site\/profsantoshpande\/\u0022\u003E\u003Cstrong\u003ESantosh Pande\u003C\/strong\u003E\u003C\/a\u003E\u003Cstrong\u003E \u003C\/strong\u003Ealso presented \u003Ca href=\u0022https:\/\/dl.acm.org\/doi\/abs\/10.1145\/3385412.3386017\u0022\u003E\u003Cem\u003EBlankIt Library Debloating: Getting What You Want Instead of Cutting What You Don\u0026rsquo;t\u003C\/em\u003E\u003C\/a\u003E with SCS Ph.D. student co-authors \u003Ca href=\u0022https:\/\/prithayan.github.io\/\u0022\u003E\u003Cstrong\u003EPrithayan Barua\u003C\/strong\u003E\u003C\/a\u003E, \u003Ca href=\u0022https:\/\/www.cc.gatech.edu\/grads\/g\/gmururu3\/\u0022\u003E\u003Cstrong\u003EGirish Mururu\u003C\/strong\u003E\u003C\/a\u003E, and \u003Ca href=\u0022https:\/\/www.linkedin.com\/in\/chris-porter-057640113\/\u0022\u003E\u003Cstrong\u003EChris Porter\u003C\/strong\u003E\u003C\/a\u003E.\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"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. "}],"uid":"34541","created_gmt":"2020-06-15 17:07:00","changed_gmt":"2020-06-15 17:49:20","author":"Tess Malone","boilerplate_text":"","field_publication":"","field_article_url":"","dateline":{"date":"2020-06-15T00:00:00-04:00","iso_date":"2020-06-15T00:00:00-04:00","tz":"America\/New_York"},"extras":[],"hg_media":{"636234":{"id":"636234","type":"image","title":"PLDI graph","body":null,"created":"1592241060","gmt_created":"2020-06-15 17:11:00","changed":"1592241060","gmt_changed":"2020-06-15 17:11:00","alt":"Graph simplification","file":{"fid":"242086","name":"graph_simplification.png","image_path":"\/sites\/default\/files\/images\/graph_simplification.png","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/graph_simplification.png","mime":"image\/png","size":40078,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/graph_simplification.png?itok=q_mIoYOH"}}},"media_ids":["636234"],"groups":[{"id":"50875","name":"School of Computer Science"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003ETess Malone, Communications Officer\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/tess.malone@cc.gatech.edu\u0022\u003Etess.malone@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}