A proof system for lock-free concurrency

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Software has become widespread, being used and relied upon on nearly every domain. Furthermore, as this globalization of software took place and multi-core architectures became the norm, several programs are now expected to run on a given device at the same time in a timely fashion. Attending this need, concurrent and distributed systems are a well known way of dealing with performance and scalability of computation. Although several such systems exist in the devices and services we depend on, it is frequent for those systems to be exploited or go wrong. Because most complex programs are built in modules and lack a formal specification of what they do, it is hard to prevent the emerging system from failing or being exploited. Therefore, one of the most sought after results by software industry is a way of reasoning about programs that prevents undesired behavior. Formal methods contribute to a rigorous specification, analysis, and verification of programs, having proven to be quite effective in this regard. Program logics,in particular, are able to verify validity of user-specified formulas and are the solution we propose to tackle this issue. Regarding concurrent programs, locks are a mechanism that make reasoning easier by serializing access to shared resources, taming concurrency. Since lock-free programs offer a better way of taking advantage of concurrency, we are especially interested in them. In this context, the LL/SC pair of primitives have proven to be more expressive than their widely used CAS counterpart. The goal of our work is then to develop a proof system capable of proving correctness of lock-free programs based on LL/SC primitives. In this dissertation we present a new program logic, based on those of concurrent separation logic and RGSep, which establishes a solid theoretical basis for reasoning about such programs.