paperbot · PL 论文追踪

全部论文 待读 收藏

P2 State Merging with Quantifiers in Symbolic Execution

符号执行中带量词的状态合并
FSE Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering2023匹配度 3/10 · 该论文研究符号执行中的状态合并与量词约束求解,属于传统程序分析与约束求解方向,未涉及用户当前核心关注的 LLM/Agent 与静态分析交叉、浮点程序分析或贝叶斯程序分析。引用 4 inbox
David Trabish, Noam Rinetzky, Sharon Shoham, Vaibhav Sharma
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出基于量词的状态合并方法,通过动态分组和专用求解过程减少约束编码爆炸。

符号执行中的状态合并会因路径约束编码膨胀而难以应用,尤其是合并时引入大量析取与 if-then-else 表达式。本文提出一种带量词的状态合并方法:先动态检测符号状态路径约束中相似的统一结构,将状态划分到合并组,再用量词高效编码合并后的路径约束与内存。为应对量词约束求解的额外复杂度,作者设计专用求解过程以减少求解时间。实验评估表明,该方法在许多情况下带来显著性能提升。

问题
符号执行中状态合并引入大量析取和 if-then-else,导致约束编码爆炸,限制其适用性。
方法
根据路径约束中相似的统一结构动态划分状态合并组,用量词编码合并后的路径约束与内存,并提出专用求解过程以缓解量词约束求解开销。
评估
通过实验对比评估,显示该方法可显著提升性能。
原文摘要(Abstract)

We address the problem of constraint encoding explosion which hinders the applicability of state merging in symbolic execution. Specifically, our goal is to reduce the number of disjunctions and if-then-else expressions introduced during state merging. The main idea is to dynamically partition the symbolic states into merging groups according to a similar uniform structure detected in their path constraints, which allows to efficiently encode the merged path constraint and memory using quantifiers. To address the added complexity of solving quantified constraints, we propose a specialized solving procedure that reduces the solving time in many cases. Our evaluation shows that our approach can lead to significant performance gains.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@inproceedings{abs-2308-12068,
  title = {State Merging with Quantifiers in Symbolic Execution},
  author = {David Trabish and Noam Rinetzky and Sharon Shoham and Vaibhav Sharma},
  booktitle = {FSE},
  year = {2023},
  doi = {10.1145/3611643.3616287}
}