Automated Analysis of Weak Memory Models
Loading...
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2018-08-20
Department
Major/Subject
Security and Cloud Computing
Mcode
SCI-ITMO
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
75 + 8
Series
Abstract
Software verification is considered to be a hard computational problem vulnerable to the state explosion problem. Concurrent software verification raises the complexity of the problem to a power determined by all the possible interleavings of states of the system. Moreover, the architecture of a modern shared-memory multi-core processor and optimisations performed by a compiler can cause program behaviour that is unexpected from the point of view of traditional concurrency. The guarantees that an execution environment can provide to a programmer are formalised in its Weak Memory Model (WMM). Over the last decade, weak memory models were defined for multiple hardware architectures and programming languages. This opens new challenges in software verification with respect to a weak memory model. Most existing tools that perform memory model-aware software analysis tools examine behaviours of the program against a single memory model. The first tool that analyses the portability of a concurrent program from one platform to another is Porthos [PFH+17a] released in April 2017. Porthos can verify that the program is portable from the source platform S to the target platform T by checking that the program has no extra states under T. For that, it performs an SMT-based bounded reachability analysis by encoding the constraints of the program and two memory models M_S and M_T into a single SMT-formula. Although the approach has been proven to be efficient, the tool accepts as input the small C-like toy language. Current thesis aims to rework Porthos by extending its input language, so that it is able to process real-world C programs. However, current implementation of Porthos can be considered hardly extensible, which raises the need to redesign its whole architecture in order to increase the robustness, transparency, efficiency and extensibility. The result of the work is PorthosC, a framework for SMT-based memory model-aware analysis.Description
Supervisor
Heljanko, KeijoThesis advisor
Komarov, IgorKeywords
weak memory models, concurrent programming, software verification, portability analysis, bounded reachability analysis, SMT-encoding
