SLING: using dynamic analysis to infer program invariants in separation logic
SLING: using dynamic analysis to infer program invariants in separation logic
复制标题
SLING：使用动态分析来推断分离逻辑中的程序不变量
DOI：
10.1145/3314221.3314634
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Thanhvu Nguyen
中科院分区：
文献类型：
--
作者：
T. Le;Guolong Zheng;Thanhvu Nguyen
我们介绍了一种新的动态分析技术，以在分离逻辑中发现不变型，以用于堆堆积程序。首先，我们使用调试器在样本输入的感兴趣位置获得富的程序执行跟踪。这些迹线由变量的堆和堆叠信息组成，这些变量指向动态分配的数据结构。接下来，我们迭代分析与每个指针变量相关的单独的内存区域，并在分离逻辑中的预定义堆谓词上搜索一个公式以建模这些区域。最后，我们将计算的公式组合为一个不变的，描述了探索的内存区域的形状。我们提出吊索，该工具可以在C程序中的任意位置（例如程序PRE和后的条件和后的条件和循环不变性）中自动生成不变性逻辑中的不变性。现有基准的初步结果表明，吊索可以为操纵各种复杂数据结构的程序有效地产生正确且有用的不变性。
We introduce a new dynamic analysis technique to discover invariants in separation logic for heap-manipulating programs. First, we use a debugger to obtain rich program execution traces at locations of interest on sample inputs. These traces consist of heap and stack information of variables that point to dynamically allocated data structures. Next, we iteratively analyze separate memory regions related to each pointer variable and search for a formula over predefined heap predicates in separation logic to model these regions. Finally, we combine the computed formulae into an invariant that describes the shape of explored memory regions. We present SLING, a tool that implements these ideas to automatically generate invariants in separation logic at arbitrary locations in C programs, e.g., program pre and postconditions and loop invariants. Preliminary results on existing benchmarks show that SLING can efficiently generate correct and useful invariants for programs that manipulate a wide variety of complex data structures.
DOI：
10.1145/2837614.2837621
发表时间：
2016-01
期刊：
Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
影响因子：
--
作者：
J. Brotherston;Nikos Gorogiannis;M. Kanovich;R. Rowe
通讯作者：
J. Brotherston;Nikos Gorogiannis;M. Kanovich;R. Rowe
DOI：
10.1016/j.scico.2010.07.004
发表时间：
2012-08
期刊：
Sci. Comput. Program.
影响因子：
--
作者：
W. Chin;C. David;Huu Hai Nguyen;S. Qin
通讯作者：
W. Chin;C. David;Huu Hai Nguyen;S. Qin
影响因子：
2.5
作者：
Calcagno, Cristiano;Distefano, Dino;Yang, Hongseok
通讯作者：
Yang, Hongseok