Verification of Concurrent Programs on Weak Memory Models
Verification of Concurrent Programs on Weak Memory Models
复制标题
弱内存模型上的并发程序验证
DOI：
10.1007/978-3-319-46750-4_1
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Heike Wehrheim
中科院分区：
文献类型：
--
作者：
Oleg Travkin;Heike Wehrheim
配备弱内存模型的现代多核处理器似乎由于内置优化而对指令进行了重新排序(相对于程序顺序)。对于并发程序，弱内存模型因此产生在顺序一致(SC)内存上不可能的交错执行。因此，并发程序的验证需要考虑正在执行的处理器的内存模型。本文提出了一种将弱存储模型的验证问题简化为SC上的验证问题的方法(并给出了相应的工具Weak2SC)。通过生成一个给定的程序和弱内存模型(这里是TSO或PSO)--一个包含所有重新排序的新程序，从而已经在SC上表现出额外的交织来进行缩减。我们的技术是组合的，在这个意义上，程序生成可以在单个进程上进行，而不需要检查并发程序的状态空间。Weak2SC使用标准C程序作为输入，生成程序描述，可以输入到自动模型检测工具(如SPIN)以及交互验证器(如KIV)中。因此，我们允许广泛的核查选项。我们通过在从并发数据结构到软件事务存储算法的大量示例程序上评估Weak2SC来证明我们的技术的有效性。
Modern multi-core processors equipped with weak memory models seemingly reorder instructions (with respect to program order) due to built-in optimizations. For concurrent programs, weak memory models thereby produce interleaved executions which are impossible on sequentially consistent (SC) memory. Verification of concurrent programs consequently needs to take the memory model of the executing processor into account. This, however, makes most standard software verification tools inapplicable.In this paper, we propose a technique (and present its accompanying toolWeak2SC) forreducingthe verification problem for weak memory models to the verification on SC. The reduction proceeds by generating – out of a given program and weak memory model (here, TSO or PSO) – a new program containing all reorderings, thus already exhibiting the additional interleavings on SC. Our technique iscompositionalin the sense that program generation can be carried out on single processes without ever needing to inspect the state space of the concurrent program. We formally prove compositionality as well as soundness of our technique.Weak2SCtakes standard C programs as input and produces program descriptions which can be fed into automatic model checking tools (like SPIN) as well as into interactive provers (like KIV). Thereby, we allow for a wide range of verification options. We demonstrate the effectiveness of our technique by evaluatingWeak2SCon a number of example programs, ranging from concurrent data structures to software transactional memory algorithms.
登录
查看更多内容
从总存储顺序到顺序一致性：实用的归约定理
DOI：
10.1007/978-3-642-14052-5_28
发表时间：
2010
期刊：
Physical review. E
影响因子：
--
作者：
Ernie Cohen;Norbert Schirmer
通讯作者：
Norbert Schirmer
一种基于自动机的在宽松内存模型上验证程序的符号方法
DOI：
10.1007/978-3-642-16164-3_16
发表时间：
2010
期刊：
bioRxiv
影响因子：
--
作者：
A. Linden;P. Wolper
通讯作者：
P. Wolper
在机械化线性化证明中处理 TSO
DOI：
10.1007/978-3-319-13338-6_11
发表时间：
2014
期刊：
Concurrency and Computation: Practice and Experience
影响因子：
--
作者：
Oleg Travkin;H. Wehrheim
通讯作者：
H. Wehrheim
DOI：
10.1007/978-3-540-70545-1_12
发表时间：
2008-07
期刊：
--
影响因子：
--
作者：
S. Burckhardt;M. Musuvathi
通讯作者：
S. Burckhardt;M. Musuvathi
DOI：
10.1007/s10009-014-0308-3
发表时间：
2015-11-01
影响因子：
1.5
作者：
Ernst, Gidon;Pfaehler, Joerg;Reif, Wolfgang
通讯作者：
Reif, Wolfgang