paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Discovering Likely Program Invariants for Persistent Memory

为持久内存发现疑似程序不变式
ASE Proceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering2024匹配度 3/10 · 该论文属于程序分析与缺陷检测方向,涉及静态依赖分析和动态反事实推理,但与用户核心关注的 PL↔AI/LLM、Agentic 程序、浮点程序分析或贝叶斯程序分析均无直接交叉。其静态分析与工程评估有一定方法参考价值,但主题不在研究画像的核心范围内。引用 2 inbox
Zunchen Huang, Srivatsan Ravi, Chao Wang
crossref: 2026-09-12

AI 速览

一句话:结合静态依赖分析与动态反事实推理,自动推断持久内存程序的持久化对象与顺序性质,并用于缺陷检测。

持久内存(PM)是一种断电后仍能保留数据的快速字节可寻址存储,程序需明确哪些对象应被持久化以及以何种顺序持久化,这类性质(PM 不变式)通常难以人工编写。本文提出自动发现此类不变式的方法:先用静态分析计算 LOAD/STORE 指令之间的依赖关系,并将该信息插桩进可执行程序;再对执行轨迹做动态分析与反事实推理,推断 PM 性质。当依赖关系被精确计算时,推断出的性质是程序在断电与恢复过程中正确行为的必要条件;当依赖关系不精确时,则得到疑似程序不变式。作者在八个持久数据结构以及 Redis、Memcached 两个分布式存储应用上评估,结果显示推断速度快、性质质量优于当前最先进技术,并可将推断出的性质用于 PM 缺陷检测,显著提升已有检测技术的效果。

问题
持久内存程序需要明确指定哪些对象应持久化以及持久化的顺序,这类 PM 性质(不变式)对正确性至关重要,但人工编写困难且易错。
方法
静态分析计算 LOAD/STORE 间的依赖关系并插桩到可执行程序,再基于执行轨迹的动态分析与反事实推理推断 PM 性质。
评估
在八个持久数据结构和 Redis、Memcached 两个分布式存储应用上评估,表明推断快速、性质质量优于最先进技术,并用于 PM 缺陷检测且显著提升其性能。
原文摘要(Abstract)

We propose a method for automatically discovering likely program invariants for persistent memory (PM), which is a type of fast and byte-addressable storage device that can retain data after power loss. The invariants, also called PM properties or PM requirements, specify which objects of the program should be made persistent and in what order. Our method relies on a combination of static and dynamic analysis techniques. Specifically, it relies on static analysis to compute dependence relations between LOAD/STORE instructions and instruments the information into the executable program. Then, it relies on dynamic analysis of the execution traces and counterfactual reasoning to infer PM properties. With precisely computed dependence relations, the inferred properties are necessary conditions for the program to behave correctly through power loss and recovery; with imprecise dependence relations, these are likely program invariants. We have evaluated our method on benchmark programs including eight persistent data structures and two distributed storage applications, Redis and Memcached. The results show that our method can infer PM properties quickly and these properties are of higher quality than those inferred by a state-of-the-art technique. We also demonstrate the usefulness of the inferred properties by leveraging them for PM bug detection, which significantly improves the performance of a state-of-the-art PM bug detection technique.

链接与引用

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

BibTeX
@inproceedings{paperbot8346,
  title = {Discovering Likely Program Invariants for Persistent Memory},
  author = {Zunchen Huang and Srivatsan Ravi and Chao Wang},
  booktitle = {ASE},
  year = {2024},
  doi = {10.1145/3691620.3695544}
}