Hoare-style program logics are a popular and effective technique for software verification. Relational program logics are an instance of this approach that enables reasoning about relationships between the execution of two or more programs. Existing relational program logics have focused on verifying that all runs of a collection of programs do not violate a specified relational behavior. Several important relational properties, including refinement and noninterference, do not fit into this category, as they also mandate the existence of specific desirable executions. This paper presents RHLE, a logic for verifying these sorts of relational $\forall\exists$ properties. Key to our approach is a novel form of function specification that employs a variant of ghost variables to ensure that valid implementations exhibit certain behaviors. We have used a program verifier based on RHLE to verify a diverse set of relational $\forall\exists$ properties drawn from the literature.
翻译:Hoare 式程序逻辑是软件核查的流行和有效技术。 关系程序逻辑是这一方法的一个实例,它有助于推理执行两个或两个以上程序之间的关系。 现有的关系程序逻辑侧重于核实所有程序集的运行并不违反特定的关系行为。 一些重要的关系属性,包括完善和不干涉,并不适合这一类别,因为它们也要求存在具体的可取处决。 本文介绍了RHLE, 一种核实这种关系$forall\clence$特性的逻辑。 我们方法的关键是一种新型功能规范, 使用各种幽灵变量以确保有效的实施能够显示某些行为。 我们使用基于 RHLE 的一套程序验证器来验证从文献中提取的各种关系$\fall\clence$。