课题基金 / 基金详情

Program Logics for Compositional Specification and Verification of Distributed Systems

Program Logics for Compositional Specification and Verification of Distributed Systems
分布式系统的组合规范和验证的程序逻辑
批准号:
EP/P009271/1
负责人:
Ilya Sergey
金额:
$12.87万
依托单位:
依托单位国家:
英国
项目类别:
Research Grant
财政年份:
2017
资助国家:
英国
项目状态:
已结题
起止时间:
2017 至 --

项目摘要

项目成果

相似基金

相关文献

中文摘要
翻译
分布式服务在现代生活的许多方面,如医疗保健、在线商务、交通、娱乐和基于云的应用,其重要性和无处不在的重要性怎么强调都不为过。考虑到分布式软件的重要性及其复杂性(源于其并发性质以及容忍重新排序和分组丢失的必要性),目前在工业中被认为至关重要的是具有严格的验证方法来确定其正确性属性,以确保一旦分布式系统启动并运行,它永远不会出错并最终完成其目标。现实世界的应用程序,包括分布式应用程序,不是作为独立的、整体的代码片段来开发的:它们更多地是由多个组件构建的,通过组成在不同模块中实现的程序机制,独立开发,然后链接在一起。因此,这种组合方法的好处是分离关注点,这使得开发过程模块化:为了将分布式协议的实现用作库,人们应该知道它做了什么,而不必费心了解它是如何工作的。遗憾的是,被认为是模块化软件开发中的良好实践的潜力在关于分布式软件的形式推理领域还没有完全实现。现有的用于描述和验证分布式应用的方法主要集中于关于独立协议的系统的推理,其行为使用其执行历史的不变量来描述,然后使用协议的抽象模型来检查。由于缺乏统一的方法来指定和验证分布式协议及其客户端的实现(可能本身就是协议实现),形式推理的纵向组合性出现了缺口:为了证明分布式库的客户端程序的正确性,人们应该依赖于相对于库的模型而不是其实际实现而建立的正确性结果。此外,指定分布式协议的方式可能使用特定的正确性条件,固定其历史不变量,例如线性化、最终或因果一致性,迫使人们为了对协议的客户端进行推理而采用相应的验证方法。这种多样性对水平可组合性提出了挑战,使得对组合了几个协议的非玩具应用程序进行推理变得非常重要。该项目建议开发一种统一的模块化方法,用于在机器检查的框架中正式指定和验证分布式应用程序的实现,同时解决垂直和水平可组合性问题。建议的方法基于Hoare式程序逻辑的思想,用于有效的并发程序及其使用依赖类型的机械化。因此,拟议的方法将在分布式计算领域模块化软件开发的良好做法和关于程序的组合推理思想之间建立联系,以此作为正式核实它们的一种方式,从而最有力地保证它们的正确性。
英文摘要
It is hard to overstate the significance and ubiquity of distributed services in many aspects of the modern life, such as health care, online commerce, transportation, entertainment and cloud-based applications. Given the importance of distributed software and its complexity, stemming from its concurrent nature and the necessity to tolerate reordering and loss of packets, it is nowadays considered vital in industry to have a rigorous verification methodology for establishing its correctness properties, ensuring that, once a distributed system is up and running, it will never go wrong and will eventually complete its goals.Real-world applications, including distributed ones, are not developed as standalone, monolithic pieces of code: they are rather built from multiple components, by composing the program machinery implemented in different modules, developed independently and then linked together. The benefit of such a compositional approach is thus the separation of concerns, which makes the development process modular: in order to use an implementation of a distributed protocol as a library, one should know what it does without bothering to understand how it works.Alas, the potential of what is considered to be a good practice in modular software development, is not yet fully realised in the area of formal reasoning about distributed software. The existing approaches for specification and verification of distributed applications are predominantly focused on reasoning about systems as of standalone protocols, whose behavior is described using invariants of their execution histories, which are then checked using the protocols' abstract models. The absence of a uniform way of specifying and verifying implementations of distributed protocols and their clients (which might be themselves protocol implementations) introduces a gap in vertical compositionality of the formal reasoning: in order to prove correctness of a distributed library's client program, one should rely on the correctness result, established with respect to the library's model rather than its actual implementation. Furthermore, the way a distributed protocol is specified might employ a particular correctness condition, fixing its history invariants, such as linearizability, eventual or causal consistency, forcing one to adopt the corresponding verification methodology for the sake of reasoning about the protocol's clients. This diversity poses challenges with respect to horizontal compositionality, making it non-trivial to reason about non-toy applications that combine several protocols.This project proposes to develop a uniform and modular approach for formally specifying and verifying implementations of distributed applications, in a machine-checked framework, addressing both issues of vertical and horizontal compositionality. The suggested methodology builds on the ideas of Hoare-style program logics for effectful concurrent programs and their mechanisation using dependent types. The proposed approach will thus establish a connecting link between the good practices of modular software development in the area of distributed computing and ideas of compositional reasoning about programs, as a way to formally verify them, therefore, delivering the strongest guarantees of their correctness.
期刊论文(7)
专著(0)
科研奖励(0)
会议论文
Practical Aspects of Declarative Languages - 21th International Symposium, PADL 2019, Lisbon, Portugal, January 14-15, 2019, Proceedings
声明性语言的实用方面 - 第 21 届国际研讨会,PADL 2019,葡萄牙里斯本,2019 年 1 月 14-15 日,会议记录
DOI: 10.1007/978-3-030-05998-9_11
发表时间: 2019
期刊:
影响因子: --
作者: [Andersen K]
通讯作者: Andersen K
DOI: 10.1145/3158116
发表时间: 2017-12
期刊: Proceedings of the ACM on Programming Languages
影响因子: --
作者: [Ilya Sergey;James R. Wilcox;Zachary Tatlock]
通讯作者: Ilya Sergey;James R. Wilcox;Zachary Tatlock
DOI: 10.1145/3276514
发表时间: 2018-10
期刊: Proceedings of the ACM on Programming Languages
影响因子: --
作者: [Sam Blackshear;Nikos Gorogiannis;P. O'Hearn;Ilya Sergey]
通讯作者: Sam Blackshear;Nikos Gorogiannis;P. O'Hearn;Ilya Sergey
DOI: 10.1145/3167086
发表时间: 2018-01
期刊: Proceedings of the 7th ACM SIGPLAN International Conference on Certified Programs and Proofs
影响因子: --
作者: [George Pîrlea;Ilya Sergey]
通讯作者: George Pîrlea;Ilya Sergey
海外基金