Fast graph simplification for interleaved Dyck-reachability
Fast graph simplification for interleaved Dyck-reachability
复制标题
DOI：
10.1145/3385412.3386021
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Yuanbo Li;Qirun Zhang;T. Reps
中科院分区：
文献类型：
--
作者：
Yuanbo Li;Qirun Zhang;T. Reps
许多程序 - 分析问题可以作为图形性问题提出。交织的戴克语言可达性。交织的戴克语言可达性（Interdyck-Reperability）是一个基本框架，可以在边缘标记的图表上表达各种程序 - 分析问题。 Interdyck语言代表多种匹配的 - 分娩语言（即Dyck语言）的相交。在实践中，程序分析通常利用一种Dyck语言来实现上下文敏感性，而其他Dyck语言则用于建模数据依赖性，例如野外敏感性和指针参考/指示。在理想的情况下，相互访问的框架应同时建模多种戴克语言。不幸的是，精确的相互访问性是不可决定的。任何实用的解决方案都必须过分陈列确切的答案。在文献中，已经提出了许多工作来过分陈列于相互访问的能力。本文提供了提高Interdyck-Reach性能的精度和可伸缩性的新观点：我们旨在简化基础输入图G。我们的关键见解是基于这样的观察，即如果边缘对任何Interdyck-path，Edge不构成贡献，我们可以安全地从G中消除它。我们的技术与相互访问性的配方是正交的，并且可以作为任何任何的预处理步骤过度评价方法，以实现相互访问性。我们已经应用了图形简化算法来预处理基于Android的基于Interdyck-Responsy的污点分析的图形。我们对三种流行的相互影响算法的评估可产生令人鼓舞的结果。特别是，我们的图形简化方法提高了所有三种相互影响算法的可伸缩性和精度，有时是显着的。
Many program-analysis problems can be formulated as graph-reachability problems. Interleaved Dyck language reachability. Interleaved Dyck language reachability (InterDyck-reachability) is a fundamental framework to express a wide variety of program-analysis problems over edge-labeled graphs. The InterDyck language represents an intersection of multiple matched-parenthesis languages (i.e., Dyck languages). In practice, program analyses typically leverage one Dyck language to achieve context-sensitivity, and other Dyck languages to model data dependences, such as field-sensitivity and pointer references/dereferences. In the ideal case, an InterDyck-reachability framework should model multiple Dyck languages simultaneously. Unfortunately, precise InterDyck-reachability is undecidable. Any practical solution must over-approximate the exact answer. In the literature, a lot of work has been proposed to over-approximate the InterDyck-reachability formulation. This paper offers a new perspective on improving both the precision and the scalability of InterDyck-reachability: we aim to simplify the underlying input graph G. Our key insight is based on the observation that if an edge is not contributing to any InterDyck-path, we can safely eliminate it from G. Our technique is orthogonal to the InterDyck-reachability formulation, and can serve as a pre-processing step with any over-approximating approaches for InterDyck-reachability. We have applied our graph simplification algorithm to pre-processing the graphs from a recent InterDyck-reachability-based taint analysis for Android. Our evaluation on three popular InterDyck-reachability algorithms yields promising results. In particular, our graph-simplification method improves both the scalability and precision of all three InterDyck-reachability algorithms, sometimes dramatically.