Chiefly Symmetric: Results on the Scalability of Probabilistic Model Checking for Operating-System Code

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Abstract

Reliability in terms of functional properties from the safety-liveness spectrum is an indispensable requirement of low-level operating-system (OS) code. However, with evermore complex and thus less predictable hardware, quantitative and probabilistic guarantees become more and more important. Probabilistic model checking is one technique to automatically obtain these guarantees. First experiences with the automated quantitative analysis of low-level operating-system code confirm the expectation that the naive probabilistic model checking approach rapidly reaches its limits when increasing the numbers of processes. This paper reports on our work-in-progress to tackle the state explosion problem for low-level OS-code caused by the exponential blow-up of the model size when the number of processes grows. We studied the symmetry reduction approach and carried out our experiments with a simple test-and-test-and-set lock case study as a representative example for a wide range of protocols with natural inter-process dependencies and long-run properties. We quickly see a state-space explosion for scenarios where inter-process dependencies are insignificant. However, once inter-process dependencies dominate the picture models with hundred and more processes can be constructed and analysed.

Details

Original languageEnglish
Title of host publicationProceedings Seventh Conference on Systems Software Verification
EditorsFranck Cassez, Ralf Huuck, Gerwin Klein, Bastian Schlich
Pages156-166
Number of pages11
Publication statusPublished - 2012
Peer-reviewedYes

Publication series

SeriesElectronic Proceedings in Theoretical Computer Science, EPTCS
Volume102
ISSN2075-2180

Conference

Title7th Conference on Systems Software Verification
Abbreviated titleSSV 2012
Conference number
Duration28 - 30 November 2012
Degree of recognitionInternational event
Location
CitySydney
CountryAustralia

External IDs

ORCID /0000-0002-5321-9343/work/142236747
ORCID /0000-0003-1724-2586/work/165453609

Keywords

Keywords

  • low-level operating-system (OS) code, probabilistic model checking