.png){kind=icon}
返回
Fast Client-Driven CFL-Reachability via Regularization-Based Graph Simplification
.png){kind=icon}
PRE
AI
DOI：10.1145/3763065.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
上下文无关语言（CFL）可达性是一种重要的分析框架，被广泛应用于各类程序分析中，尽管其计算复杂度因三次方或接近三次方的时间复杂度而带来挑战，这往往导致客户端应用程序性能显著下降。值得注意的是，在实际场景中，客户端通常仅需针对特定的源-汇点对获取可达性信息，这为定向优化提供了机会。我们提出了MOYE，一种基于正则化的图简化技术，旨在通过剪除非贡献边（即不参与任何指定CFL可达路径的边）来提升客户端驱动的CFL可达性分析的效率。MOYE采用正则近似来确保所有指定节点对的精确可达性结果，并且其操作与图中边的数量呈线性关系。这种轻量级的高效性使MOYE成为一项有价值的预处理步骤，能够大幅减少CFL可达性分析的计算时间和内存需求，超越了一种近期领先的图简化方法。我们的评估基于两个主流的CFL可达性客户端应用程序，结果表明MOYE能够显著提升性能并降低资源消耗。
Keyword:
CFL-Reachability
Graph Simplification
期刊
P
IF:
2.8
论文数:
308
被引数:
4.7K
机构
引用论文
.png){kind=icon}
分享收藏
分享收藏分享收藏
查看更多内容