Model Checking Software: 16th International SPIN Workshop, Grenoble, France, June 26-28, 2009, Proceedings (Lecture Notes in Computer Science Theoretical Computer Science and General Issues)

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Alfred Kobsa University of California, Irvine, CA, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany

5578

Corina S. P˘as˘areanu (Ed.)

Model Checking Software 16th International SPIN Workshop Grenoble, France, June 26-28, 2009 Proceedings

13

Volume Editor Corina S. P˘as˘areanu NASA Ames Research Center, Space Science Division Mail Stop 269-2, Moffett Field, CA 94035, USA E-mail: [email protected]

Library of Congress Control Number: 2009928779 CR Subject Classification (1998): F.3, D.2.4, D.3.1, D.2 LNCS Sublibrary: SL 1 – Theoretical Computer Science and General Issues ISSN ISBN-10 ISBN-13

0302-9743 3-642-02651-6 Springer Berlin Heidelberg New York 978-3-642-02651-5 Springer Berlin Heidelberg New York

This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. springer.com © Springer-Verlag Berlin Heidelberg 2009 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper SPIN: 12703296 06/3180 543210

Preface

This volume contains the proceedings of the 16th International SPIN Workshop on Model Checking of Software (SPIN 2009), that was held at the Grenoble World Trade Center, in Grenoble, France, June 26–28, 2009. The workshop was co-located with the 21st International Conference on Computer-Aided Verification (CAV 2009). The SPIN workshop is a forum for practitioners and researchers interested in the model checking-based analysis of software systems. The focus of the workshop is on theoretical advances and empirical evaluations related to state-space and path exploration techniques, as implemented in the SPIN model checker and other software verification tools. The workshop aims to encourage interactions and exchanges of ideas with all related areas in software engineering. SPIN 2009 was the 16th event in the workshop series, which started in 1995. This year, we received 41 submissions (34 technical papers and 7 tool papers) out of which 18 papers were accepted (15 technical papers and 3 tool papers). Each submission was reviewed by three Program Committee members. In addition to the refereed papers, the workshop featured four invited talks given by Patrice Godefroid, from Microsoft Research, USA, on “Software Model Checking Improving Security of a Billion Computers,” Marta Kwiatkowska, from Oxford University, UK, “On Quantitative Software Verification,” Joseph Sifakis (recipient of the Turing Award 2007), from VERIMAG, France, on “The Quest for Correctness - Beyond a posteriori Verification,” and Willem Visser, from the University of Stellenbosch, South Africa, on “Who Really Cares if the Program Crashes?” We would like to thank the authors of submitted papers, the invited speakers, the Program Committee members, the external reviewers, and the Steering Committee, for their help in composing a strong program. Special thanks go to Stefan Leue for his guidance throughout the SPIN 2009 organization, to Saddek Bensalem for the SPIN 2009 local organization, and to last year’s organizers, Klaus Havelund and Rupak Majumdar, for their advice and help with advertising the event. We also thank Springer for agreeing to publish these proceedings as a volume of Lecture Notes in Computer Science. The EasyChair system was used for the submission and reviewing of the papers and also for the preparation of the proceedings. April 2009

Corina S. P˘ as˘areanu

Organization

Program Chair Corina S. P˘ as˘areanu

Program Committee Christel Baier Dragan Bo˘sna˘cki Patricia Bouyer Lubos Brim Marsha Chechik Matthew Dwyer Stefan Edelkamp Jaco Geldenhuys Susanne Graf Klaus Havelund Gerard Holzmann Radu Iosif Michael Jones Sarfraz Khurshid Orna Kupferman Stefan Leue Rupak Majumdar Madan Musuvathi Koushik Sen Scott Stoller Farn Wang Pierre Wolper

University Bonn, Germany Eindhoven University, The Netherlands ´ ENS de Cachan, France Masaryk U, Czech Republic University of Toronto, Canada University of Nebraska, USA T.U. Dortmund, Germany University of Stellenbosch, South Africa VERIMAG, France JPL, USA JPL, USA VERIMAG, France Brigham Young U, USA University of Texas, Austin, USA Hebrew University, Israel University of Konstanz, Germany University of California, Los Angeles, USA Microsoft Research, USA University of California, Berkeley, USA Stony Brook University, USA National Taiwan University, Taiwan University of Liege, Belgium

Steering Committee Dragan Bo˘sna˘cki Stefan Edelkamp Susanne Graf Klaus Havelund Stefan Leue (Chair) Rupak Majumdar Pierre Wolper,

Eindhoven University, The Netherlands T.U. Dortmund, Germany VERIMAG, France JPL, USA University of Konstanz, Germany University of California, Los Angeles, USA University of Liege, Belgium

VIII

Organization

Local Organization Saddek Bensalem (CAV 2009 Local Organization, VERIMAG/UJF, France)

External Reviewers Husain Aljazzar Adam Antonik Bahareh Badban Jiri Barnat Tobias Blechmann Jacob Burnim Franck Cassez Ivana Cerna Joel Galenson Pallavi Joshi Sudeep Juvekar Shadi Abdul Khalek Peter Kissmann Joachim Klein Filip Konecny Laura Kovacs

Matthias Kuntz Roman Manevich Nicolas Markey Eric Mercer Chang-Seo Park Polyvios Pratikakis Neha Rungta Roopsha Samanta Christoph Scheben Jiri Simacek Jocilyn Simmonds Christos Stergiou Damian Sulewski Faraz Torchizi Wei Wei Tim Willemse

Table of Contents

Invited Contributions Software Model Checking Improving Security of a Billion Computers . . . Patrice Godefroid

1

On Quantitative Software Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Marta Kwiatkowska

2

The Quest for Correctness-Beyond a Posteriori Verification . . . . . . . . . . . Joseph Sifakis

4

Who Really Cares If the Program Crashes? . . . . . . . . . . . . . . . . . . . . . . . . . Willem Visser

5

Regular Papers Tool Presentation: Teaching Concurrency and Model Checking . . . . . . . . . Mordechai (Moti) Ben-Ari

6

Fast, All-Purpose State Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Peter C. Dillinger and Panagiotis (Pete) Manolios

12

Efficient Probabilistic Model Checking on General Purpose Graphics Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dragan Boˇsnaˇcki, Stefan Edelkamp, and Damian Sulewski Improving Non-Progress Cycle Checks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . David Farag´ o and Peter H. Schmitt Reduction of Verification Conditions for Concurrent System Using Mutually Atomic Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Malay K. Ganai and Sudipta Kundu Probabilistic Reachability for Parametric Markov Models . . . . . . . . . . . . . Ernst Moritz Hahn, Holger Hermanns, and Lijun Zhang

32 50

68 88

Extrapolation-Based Path Invariants for Abstraction Refinement of Fifo Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Alexander Heußner, Tristan Le Gall, and Gr´egoire Sutre

107

A Decision Procedure for Detecting Atomicity Violations for Communicating Processes with Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nicholas Kidd, Peter Lammich, Tayssir Touili, and Thomas Reps

125

X

Table of Contents

Eclipse Plug-In for Spin and st2msc Tools-Tool Presentation . . . . . . . . . . . Tim Kovˇse, Boˇstjan Vlaoviˇc, Aleksander Vreˇze, and Zmago Brezoˇcnik

143

Symbolic Analysis via Semantic Reinterpretation . . . . . . . . . . . . . . . . . . . . Junghee Lim, Akash Lal, and Thomas Reps

148

EMMA: Explicit Model Checking Manager (Tool Presentation) . . . . . . . . Radek Pel´ anek and V´ aclav Roseck´y

169

Efficient Testing of Concurrent Programs with Abstraction-Guided Symbolic Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Neha Rungta, Eric G. Mercer, and Willem Visser

174

Subsumer-First: Steering Symbolic Reachability Analysis . . . . . . . . . . . . . . Andrey Rybalchenko and Rishabh Singh

192

Identifying Modeling Errors in Signatures by Model Checking . . . . . . . . . Sebastian Schmerl, Michael Vogel, and Hartmut K¨ onig

205

Towards Verifying Correctness of Wireless Sensor Network Applications Using Insense and Spin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Oliver Sharma, Jonathan Lewis, Alice Miller, Al Dearle, Dharini Balasubramaniam, Ron Morrison, and Joe Sventek Verification of GALS Systems by Combining Synchronous Languages and Process Calculi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hubert Garavel and Damien Thivolle Experience with Model Checking Linearizability . . . . . . . . . . . . . . . . . . . . . Martin Vechev, Eran Yahav, and Greta Yorsh

223

241 261

Automatic Discovery of Transition Symmetry in Multithreaded Programs Using Dynamic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yu Yang, Xiaofang Chen, Ganesh Gopalakrishnan, and Chao Wang

279

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

297

Software Model Checking Improving Security of a Billion Computers Patrice Godefroid Microsoft Research [email protected]

Abstract. I will present a form of software model checking that has improved the security of a billion computers (and has saved Microsoft millions of dollars). This form of software model checking is dubbed whitebox fuzz testing, and builds upon recent advances in systematic dynamic test generation (also known as DART) and constraint solving. Starting with a well-formed input, whitebox fuzzing symbolically executes the sequential program under test dynamically, and gathers constraints on inputs from conditional statements encountered along the execution. The collected constraints are negated systematically one-byone and solved with a constraint solver, yielding new inputs that exercise different execution paths in the program. This process is repeated using novel state-space exploration techniques that attempt to sweep through all (in practice, many) feasible execution paths of the program while checking simultaneously many properties. This approach thus combines program analysis, testing, model checking and automated theorem proving (constraint solving). Whitebox fuzzing has been implemented in the tool SAGE, which is optimized for long symbolic executions at the x86 binary level. Over the past 18 months, SAGE has been running on hundreds of machines and has discovered many new expensive security-critical bugs in large shipped Windows applications, including image processors, media players and file decoders, that are deployed on more than a billion computers worldwide. SAGE is so effective in finding bugs missed by other techniques like static analysis or blackbox random fuzzing that it is now used daily in various Microsoft groups. This is joint work with Michael Levin (Microsoft CSE) and other contributors.

C.S. P˘ as˘ areanu (Ed.): SPIN 2009, LNCS 5578, p. 1, 2009. c Springer-Verlag Berlin Heidelberg 2009


On Quantitative Software Verification Marta Kwiatkowska Oxford University Computing Laboratory, Parks Road, Oxford, OX1 3QD

Software verification has made great progress in recent years, resulting in several tools capable of working directly from source code, for example, SLAM and Astree. Typical properties that can be verified are expressed as Boolean assertions or temporal logic properties, and include whether the program eventually terminates, or the executions never violate a safety property. The underlying techniques crucially rely on the ability to extract from programs, using compiler tools and predicate abstraction, finite-state abstract models, which are then iteratively refined to either demonstrate the violation of a safety property (e.g. a buffer overflow) or guarantee the absence of such faults. An established method to achieve this automatically executes an abstraction-refinement loop guided by counterexample traces [1]. The vast majority of software verification research to date has concentrated on methods for analysing qualitative properties of system models. Many programs, however, contain randomisation, real-time delays and resource information. Examples include anonymity protocols and random back-off schemes in e.g. Zigbee and Bluetooth. Quantitative verification [2] is a technique for establishing quantitative properties of a system model, such as the probability of battery power dropping below minimum, the expected time for message delivery and the expected number of messages lost before protocol termination. Models are typically variants of Markov chains, annotated with reward structures that describe resources and their usage during execution. Properties are expressed in temporal logic extended with probabilistic and reward operators. Tools such as the probabilistic model checker PRISM are widely used to analyse system models in several application domains, including security and network protocols. However, at present the models are formulated in the modelling notations specific to the model checker. The key difficulty in transferring quantitative verification techniques to real software lies in the need to generalise the abstraction-refinement loop to the quantitative setting. Progress has been recently achieved using the idea of strongest evidence for counterexamples [3] and stochastic game abstractions [4]. In this lecture, we present a quantitative software verification method for ANSI-C programs extended with random assignment. The goal is to focus on system software that exhibits probabilistic behaviour, for example through communication failures or randomisation, and quantitative properties of software such as “the maximum probability of file-transfer failure” or “the maximum expected number of function calls during program execution”. We use a framework based on SAT-based predicate abstraction, in which probabilistic programs are represented as Markov decision processes, and their abstractions as stochastic C.S. P˘ as˘ areanu (Ed.): SPIN 2009, LNCS 5578, pp. 2–3, 2009. c Springer-Verlag Berlin Heidelberg 2009


On Quantitative Software Verification

3

two-player games [5]. The abstraction-refinement loop proceeds in a quantitative fashion, yielding lower and upper bounds on the probability/expectation values for the computed abstractions. The bounds provide a quantitative measure of the precision of the abstraction, and are used to guide the refinement process, which proceeds automatically, iteratively refining the abstraction until the interval between the bounds is sufficiently small. In contrast to conventional approaches, our quantitative abstraction-refinement method does not produce counterexample traces. The above techniques have been implemented using components from GOTO-CC, SATABS and PRISM and successfully used to verify actual networking software. The lecture will give an overview of current research directions in quantitative software verification, concentrating on the potential of the method and outlining future challenges. Acknowledgements. Supported in part by EPSRC grants EP/D07956X, EP/ D076625 and EP/F001096, and FP7 project CONNECT-IP.

References 1. Clarke, E., Grumberg, O., Jha, S., Lu, Y., Veith, H.: Counterexample-guided abstraction refinement. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 154–169. Springer, Heidelberg (2000) 2. Kwiatkowska, M.: Quantitative verification: Models, techniques and tools. In: Proc. 6th ESEC/FSE, pp. 449–458. ACM Press, New York (2007) 3. Hermanns, H., Wachter, B., Zhang, L.: Probabilistic CEGAR. In: Gupta, A., Malik, S. (eds.) CAV 2008. LNCS, vol. 5123, pp. 162–175. Springer, Heidelberg (2008) 4. Kwiatkowska, M., Norman, G., Parker, D.: Game-based abstraction for Markov decision processes. In: Proc. QEST 2006. IEEE, Los Alamitos (2006) 5. Kattenbelt, M., Kwiatkowska, M., Norman, G., Parker, D.: Abstraction refinement for probabilistic software. In: Jones, N., Muller-Olm, M. (eds.) VMCAI 2009. LNCS, vol. 5403, pp. 182–197. Springer, Heidelberg (2009)

The Quest for Correctness-Beyond a Posteriori Verification Joseph Sifakis Verimag Laboratory

Abstract. In this presentation, I discuss the main achievements in the area of formal verification, in particular regarding their impact thus far on the development of Computer Science as a discipline and on future research directions. The presentation starts with a short overview of formal verification techniques and their main characteristics, followed by an analysis of their current status with respect to: 1) requirements specification; 2) faithfulness of modeling; 3) scalability of verification methods. Compositional modeling and verification is the main challenge to tackling complexity. System verification should be tightly integrated into the design process, making use of knowledge about the system’s structure and its properties. I identify two complementary research directions for overcoming some of the current difficulties in compositional techniques: 1) Moving away from low-level automata-based composition to component-based composition, by developing frameworks encompassing heterogeneous components; 2) Using such frameworks to study compositionality techniques for particular architectures and/or specific properties. I illustrate these ideas through the BIP (Behavior, Interaction, Priority) component framework which encompasses high-level composition of heterogeneous components. BIP supports a design methodology for building systems in a threedimensional design space by using property-preserving transformations. This allows efficient compositional verification techniques for proving invariants, and deadlock-freedom in particular.

C.S. P˘ as˘ areanu (Ed.): SPIN 2009, LNCS 5578, p. 4, 2009. c Springer-Verlag Berlin Heidelberg 2009


Who Really Cares If the Program Crashes? Willem Visser Computer Science Division Department of Mathematical Sciences University of Stellenbosch South Africa

Abstract. After spending eight years at NASA doing research in model checking and testing, I decided it would be a nice change of scene to see how software is being developed in a fast-paced technology start-up (SEVEN Networks). Of course I was secretly hoping to solve all their testing problems with the cool research techniques from the verification and testing community. At NASA software is written once, for the most part run once, and if it fails there are serious (even life-threatening) consequences. Clearly this is a fruitful hunting ground for advanced verification and testing technology. At SEVEN, on the other hand, code is maintained and adapted for years and the same programs execute thousands of times a second on various platforms. Failures are plentiful, but they only become important once they start to impact service level agreements with the paying customers; i.e. when they start to have a negative impact on the bottomline. Failures are not necessarily crashes either, it is much more likely to be a performance bottle-neck that eventually causes a system-wide failure. What does the verification and testing community have to offer in this arena, bearing in mind there are very few ”NASA”s and very many ”SEVEN”s in the world? This talk is about what I learned in the past two years at SEVEN and how it is influencing my current research. In particular I will explain why I ran a model checker on SEVEN code just once, used a static analysis tool only once as well, the reasons why model based testing is no longer used at SEVEN, why I am no longer certain deadlocks are so important (but races are), why SQL is a useful debugging aid and why performance analysis is important. I will also highlight some of the more interesting errors I encountered at SEVEN and why our current tools cannot find most of these.

C.S. P˘ as˘ areanu (Ed.): SPIN 2009, LNCS 5578, p. 5, 2009. c Springer-Verlag Berlin Heidelberg 2009


Tool Presentation: Teaching Concurrency and Model Checking Mordechai (Moti) Ben-Ari Department of Science Teaching Weizmann Institute of Science Rehovot 76100 Israel [email protected] http://stwww.weizmann.ac.il/g-cs/benari/

Abstract. This paper describes software tools for teaching concurrency and model checking. jSpin is an development environment for Spin that formats and filters the output of a simulation according to the user’s specification. SpinSpider uses debugging output from Spin to generate a diagram of the state space of a Promela model; the diagram can be incrementally displayed using iDot. VN supports teaching nondeterministic finite automata. The Erigone model checker is a partial reimplementation of Spin designed to be easy to use, well structured and well documented. It produces a full trace of the execution of the model checker in a format that is both readable and amenable to postprocessing.

1

Introduction

Concurrency is a notoriously difficult subject to learn because the indeterminate behavior of programs poses challenges for students used to debugging programs by trial and error. They must learn new concepts of specification and correctness, as well as formal methods such as state transition diagrams and temporal logic. Nevertheless, efforts are being made to teach this fundamental topic to beginning undergraduates and even to high school students, hopefully, before a sequential mindset takes hold [1,2]. We have found that students at this level are fully capable of understanding basic concepts of concurrency such as race condition, atomicity, interleaving, mutual exclusion, deadlock and starvation. Special tools are needed to teach concurrency, because the student must be able to examine and construct scenarios in full detail, and this is not possible without fine-grained control of the interleaving. The traditional educational tool is a concurrency simulator for (a subset of) a language like Pascal or C augmented with processes, semaphores and monitors [3,4]. Concurrency is now being taught in Java because of its near-universal use in teaching introductory programming. I believe that this is far from optimal for several reasons: concurrency is inextricably bound with objects, there is no fine-grained control of the interpreter, the language-defined monitor-like construct is too high-level and not well designed, and the java.util.concurrent library is too complex. C.S. P˘ as˘ areanu (Ed.): SPIN 2009, LNCS 5578, pp. 6–11, 2009. c Springer-Verlag Berlin Heidelberg 2009


Tool Presentation: Teaching Concurrency and Model Checking

7

Several years ago, I became convinced that the Spin model checker is appropriate for teaching concurrency even to beginning students: (a) The simplicity of the Promela language does not obscure the basic concepts; (b) There is direct support for fundamental constructs like shared variables, semaphores (using atomic) and channels; (c) The execution can be displayed in full detail and the interleaving of individual statements controlled. For teaching at introductory levels, I feel that Spin is better tool than Java PathFinder [5], because Promela is much simpler than Java, and Spin is a simpler tool to use. GOAL [6] can be used for studying concurrency through infinite automata, but these students have yet to study even finite automata. Learning Spin led me to write a new edition of my concurrency textbook [7] and an introductory textbook on Spin [8]. During this period, I developed software tools for teaching: jSpin, a development environment; SpinSpider, which automatically generates the state space diagram of a Promela program that can be viewed incrementally with iDot; VN, a tool to support learning nondeterministic finite automata (NDFA). The Erigone model checker is a partial reimplementation of Spin designed to simplify modeling checking when teaching concurrency and to facilitate learning model checking itself.1

2

jSpin: A Development Environment for Spin

The downside of using Spin for teaching is that it requires a C compiler which can be difficult for beginning students to install. Furthermore, Spin is a commandline tool with a daunting list of arguments, while the XSpin interface is oriented at professional users and requires Tcl/Tk which students do not use. jSpin is a simple GUI that allows the student to edit Promela programs and to execute Spin in its various modes with a single mouse click or keypress. jSpin formats the output of a simulation (random, interactive or guided) as a scenario in a tabular representation. You can specify that certain variables and statements will be excluded from the table, so that less important information like incrementing indices does not clutter the display. An example of the output of jSpin is shown below. It is for a program that repeatedly increments a global variable concurrently in two processes by loading its value into local variables and then storing the new value. Surprisingly, there is a scenario in which the final value of the global variable can be two! The final part of a trail is shown below; the barrier variable finished and the loop indices have been excluded, as have the statements that increment the indices. Process 0 P 0 P 1 Q 1 Q 0 P 1

Statement 9 temp = n 10 n = (temp+1) 22 n = (temp+1) 25 finished = (fi 13 finished = (fi

P(0):temp 8 9 9 9 9

Q(1):temp 1 1 1 1 1

n 9 9 10 2 2

Screenshots of the tools can be found on the website given in Section 8.

8

M. Ben-Ari

2 Finis 29 finished==2 9 1 spin: text of failed assertion: assert((n>2))

2

Each line shows the statement that is to be executed and the current values of all the variables; the result of executing the statement is reflected in the following line. Spin only displays the values of variables that have changed, while this tabular format facilitates understanding executability and execution of expressions and statements that can involve several variables.

3

SpinSpider: Visualizing the State Space

SpinSpider uses data available from Spin to generate a graphical representation of the complete state space of a Promela program; it is written out in the dot language and laid out by the dot tool of Graphviz [9]. The trail of a counterexample can be displayed as a separate graph or it can be emphasized in the graph of the state space. SpinSpider is integrated into the jSpin environment, although it can be run as a standalone application. iDot displays the graphics files generated by SpinSpider interactively and incrementally.

4

VN: Visualization of Nondeterminism

Nondeterminism is a related, but important, concept that is difficult for students to understand [10]. In particular, it is difficult to understand the definition of acceptance by an NDFA. VN visually demonstrates nondeterminism by leveraging simulation and verification in Spin together with the graph layout capabilities of dot. Its input is an XML representation of an NDFA generated interactively by JFLAP [11]. For any NDFA and input string, a Promela program is generated with embedded printf statements that create a file describing the path in the NDFA taken by an execution. VN runs the program in random simulation mode to show that arbitrary scenarios will be generated for each execution. In interactive simulation mode, the user resolves the nondeterminism like an oracle. Verification is used to show the existence of an accepting computation.

5

The Erigone Model Checker

My experience—both teaching concurrency and developing the tools described above—led me to develop the Erigone model checker, a simplified reimplementation of Spin. The rationale and design principles were as follows: Installation and execution. The installation of a C compiler is a potential source of error for inexperienced students, so Erigone is designed as a single executable file. The size of the state vector is static, but this is not a problem for the small programs taught in a course. The constants defining the size of the state vector are declared with limited scope so that a future version could—like Spin—generate a program-specific verifier with minimize recompilation.

Tool Presentation: Teaching Concurrency and Model Checking

9

Tracing. The implementation of the above tools was difficult because there is no uniform and well documented output from Spin. Erigone uses a single format—named association—that is both easy to read (albeit verbose) and easy to postprocess. Here are a few lines of the output of a step of a simulation of the “Second Attempt” to solve the critical section problem [7, Section 3.6]: next state=,p=3,q=8,wantp=1,wantq=0,critical=0, all transitions=2, process=p,source=3,target=4,...,statement={critical++},..., process=q,source=8,target=2,...,statement={!wantp},..., executable transitions=1, process=p,source=3,target=4,...,statement={critical++},..., chosen transition=, process=p,source=3,target=4,...,statement={critical++},..., next state=,p=4,q=8,wantp=1,wantq=0,critical=1,

Four data options are displayed here: all the transitions from a state, the executable transitions in that state, the chosen transition and the states of the simulation. Fifteen arguments independently specify which data will be output: (a) the symbol table and transitions that result from the compilation; (b) for an LTL to BA translation, the nodes of the tableau and the transitions of the BA; (c) for a simulation, the options shown above; (d) for a verification, the sets of all and executable transitions, and the operations on the stacks and on the hash table; (e) runtime information. The display of the first step of a verification is (with elisions): push state=0,P=1,Q=1,R=1,n=0,finish=0,P.temp=0,Q.temp=0, all transitions=3, ... executable transitions=2, process=P,source=1,target=2,...,line=5,statement={temp=n}, process=Q,source=1,target=2,...,line=12,statement={temp=n}, push transition=0,process=1,transition=0,...,visited=false,last=true, push transition=1,process=0,transition=0,...,visited=false,last=false, top state=0,P=1,Q=1,R=1,n=0,finish=0,P.temp=0,Q.temp=0, top transition=1,process=0,transition=0,...,visited=false,last=false, inserted=true,P=2,Q=1,R=1,n=0,finish=0,P.temp=0,Q.temp=0,

Postprocessing. A postprocessor Trace was written; it implements a filtering algorithm like the one in jSpin that formats a scenario as a table, excluding variables and statements as specified by the user. Because of the uniform output of Erigone, it could be implemented in a few hours. Well structured and well documented. Learning model checking is difficult because there is no intermediate description between the high-level pseudocode in research papers and books, and the low-level C code of Spin. This also has implications for research into model checking, because graduate students who would like to modify Spin’s algorithms have to learn the C code. During the development of Erigone, continuous effort was invested in refactoring and documentation to ensure the readability and maintainability of the software.

10

6

M. Ben-Ari

The Implementation of Erigone

Erigone is a single program consisting of several subsystems: (1) a top-down compiler that translates Promela into transitions with byte code for the statements and expressions; (2) a model checker that implements the algorithms as described in [12], except that an explicit stack for pending transitions from the states is used instead of recursion; (3) a translator of LTL to BA using the algorithm in [13]. The compiler and the LTL-to-BA translator can be run independently of the model checker. Erigone is implemented in Ada 2005. This language was chosen because of its superb facilities for structuring programs and its support for reliable software. An additional advantage of Ada is that the source code can be read as easily as pseudocode. A researcher who wishes to modify Erigone will have to learn Ada, but I believe that that is not a difficult task and that the reliability aspects of the language will repay the effort many times over.

7

Current Status of Erigone and Future Plans

Erigone implements enough of Promela to study the basic concepts and algorithms found in textbooks like [7], in particular, the safety and liveness of Dijkstra’s “four attempts” and Dekker’s algorithm. Weak fairness is implemented and weak semaphores can be defined using atomic. Correctness specifications are given using assert and LTL formulas. Arrays can be used for solving nondeterministic algorithms [14], [8, Chapter 11] and for simulating NDFAs. Channels will be implemented in the near future. Versions of jSpin and VN for Erigone are under development. Future plans include: (a) Develop a regression test suite; (b) Develop interactive visualizations (unlike SpinSpider which uses postprocessing); (c) Visualize the LTL to BA translation, perhaps by integrating Erigone with GOAL[6]; (d) Measure the performance and improve the efficiency to the extent that it can be done without sacrificing clarity; (e) Implement more efficient algorithms for LTL to BA translation, fairness and state compression, but as optional additions rather than as replacements for the existing algorithms, so that students can begin by learning the simpler algorithms; (f) Use the excellent concurrency constructs in Ada to implement a parallel model checker [15].

8

Availability of the Tools

All these tools are freely available under the GNU General Public License and can be downloaded from Google Code; see the links at: http://stwww.weizmann.ac.il/g-cs/benari/home/software.html The GNAT compiler from AdaCore was used; it is freely available under the GNU GPL for Windows and Linux, the primary platforms used by students. jSpin is implemented in Java, as are SpinSpider, iDot and VN.

Tool Presentation: Teaching Concurrency and Model Checking

11

Acknowledgements Mikko Vinni of the University of Joensuu developed iDot, and Trishank Karthik Kuppusamy of New York University wrote the Promela compiler under the supervision of Edmond Schonberg. Michal Armoni helped design VN. I am deeply indebted to Gerard Holzmann for his unflagging assistance throughout the development of these tools. I would also like to thank the many victims of my emails asking for help with the model-checking algorithms.

References 1. Arnow, D., Bishop, J., Hailperin, M., Lund, C., Stein, L.A.: Concurrency the first year: Experience reports. ACM SIGCSE Bulletin 32(1), 407–408 (2000) 2. Ben-David Kolikant, Y.: Understanding Concurrency: The Process and the Product. PhD thesis, Weizmann Institute of Science (2003) 3. Ben-Ari, M.: Principles of Concurrent Programming. Prentice-Hall International, Hemel Hempstead (1982) 4. Bynum, B., Camp, T.: After you, Alfonse: A mutual exclusion toolkit. ACM SIGCSE Bulletin 28(1), 170–174 (1996) 5. Visser, W., Havelund, K., Brat, G., Park, S., Lerda, F.: Model checking programs. Automated Software Engineering 10(2), 203–232 (2003) 6. Tsay, Y.K., Chen, Y.F., Tsai, M.H., Wu, K.N., Chan, W.C., Luo, C.J., Chang, J.S.: Tool support for learning B¨ uchi automata and linear temporal logic. Formal Aspects of Computing 21(3), 259–275 (2009) 7. Ben-Ari, M.: Principles of Concurrent and Distributed Programming, 2nd edn. Addison-Wesley, Harlow (2006) 8. Ben-Ari, M.: Principles of the Spin Model Checker. Springer, London (2008) 9. Gansner, E.R., North, S.C.: An open graph visualization system and its applications to software engineering. Software Practice & Experience 30(11), 1203–1233 (2000) 10. Armoni, M., Ben-Ari, M.: The concept of nondeterminism: Its development and implications for education. Science & Education (2009) (in press), http://dx.doi.org/10.1007/s11191-008-9147-5 11. Rodger, S.H., Finley, T.W.: JFLAP: An Interactive Formal Languages and Automata Package. Jones & Bartlett, Sudbury (2006) 12. Holzmann, G.J.: The Spin Model Checker: Primer and Reference Manual. AddisonWesley, Boston (2004) 13. Gerth, R., Peled, D., Vardi, M.Y., Wolper, P.: Simple on-the-fly automatic verification of linear temporal logic. In: Fifteenth IFIP WG6.1 International Symposium on Protocol Specification, Testing and Verification XV, pp. 3–18 (1996) 14. Floyd, R.W.: Nondeterministic algorithms. Journal of the ACM 14(4), 636–644 (1967) 15. Holzmann, G.J., Joshi, R., Groce, A.: Tackling large verification problems with the Swarm tool. In: Havelund, K., Majumdar, R., Palsberg, J. (eds.) SPIN 2008. LNCS, vol. 5156, pp. 134–143. Springer, Heidelberg (2008)

Fast, All-Purpose State Storage Peter C. Dillinger and Panagiotis (Pete) Manolios College of Computer and Information Science, Northeastern University 360 Huntington Ave., Boston MA 02115, USA {pcd,pete}@ccs.neu.edu

Abstract. Existing techniques for approximate storage of visited states in a model checker are too special-purpose and too DRAM-intensive. Bitstate hashing, based on Bloom filters, is good for exploring most of very large state spaces, and hash compaction is good for high-assurance verification of more tractable problems. We describe a scheme that is good at both, because it adapts at run time to the number of states visited. It does this within a fixed memory space and with remarkable speed and accuracy. In many cases, it is faster than existing techniques, because it only ever requires one random access to main memory per operation; existing techniques require several to have good accuracy. Adapting to accommodate more states happens in place using streaming access to memory; traditional rehashing would require extra space, random memory accesses, and hash computation. The structure can also incorporate search stack matching for partial-order reductions, saving the need for extra resources dedicated to an additional structure. Our scheme is wellsuited for a future in which random accesses to memory are more of a limiting factor than the size of memory.

1

Introduction

An efficient explicit-state model checker such as Spin can easily fill main memory with visited states in minutes if storing them exactly [1]. This is a hindrance to automatically proving properties of large asynchronous programs by explicit state enumeration. In most cases, a level of uncertainty in the completeness of the verification is acceptable, either because of other uncertainties in the process or because one is simply looking for errors. Over-approximating the set of visited states can allow orders of magnitude more states to be explored quickly using the same amount of memory. Bitstate hashing [2], which uses Bloom filters [1,3,4], is the pinnacle of exploring as many states as possible when available memory per state is very small—say, less than 8 bits per state. The configuration that tends to cover the largest proportion of the state space in those conditions (setting three bits per state) covers even more when there is more memory per state, but it does not utilize the extra memory well. Using different configurations of the same or a different structure makes better use of the extra memory and comes much closer to full coverage of the state space—or achieves it. At around 36 bits per state, C.S. P˘ as˘ areanu (Ed.): SPIN 2009, LNCS 5578, pp. 12–31, 2009. c Springer-Verlag Berlin Heidelberg 2009


Fast, All-Purpose State Storage

13

hash compaction has a good probability of full coverage [5], while the standard bitstate configuration omits states even with 300 bits per state. The difficulty in making better use of more memory is that special knowledge is needed for known schemes to offer a likely advantage. In particular, one needs to know approximately how many states will be visited in order to tune the data structures to be at their best. In previous work, we described how to use a first run with the standard bistate approach to inform how best to configure subsequent runs on the same or a related model [4]. This can help one to achieve a desired level of certainty more quickly. We also implemented and described automatic tool support for this methodology [6]. The shortcoming of this methodology is that the initial bitstate run can omit many more states than theoretically necessary, if there are tens of bits of memory per state. Ideally, no guidance would be required for a model checker to come close to the best possible accuracy for available memory in all cases. Such a structure would be good at both demonstrating absence of errors in smaller state spaces and achieving high coverage of larger state spaces. If it were competitively fast, such a structure would be close to the best choice conceivable when the state space size is unknown. This paper describes a scheme that is closer to this ideal than any known. The underlying structure is a compact hash table by John G. Cleary [7], which we make even more compact by eliminating redundancy in metadata. Our most important contribution, however, is a fast, in-place algorithm for increasing the number of cells by reducing the size of each cell. The same structure can similarly be converted in place to a Bloom filter similar to the standard bitstate configuration. These algorithms allow the structure to adapt to the number of states encountered at run time, well-utilizing the fixed memory in every case. Do not mistake this scheme for an application of well-known, classical hash table technology. First of all, the Cleary structure represents sets using near minimum space [8], unlike any classical structure, such as that used by the original “hashcompact” scheme [9]. The essence of this compactness is that part of the data of each element is encoded in its position within the structure, and it does this without any pointers. Second, our algorithm for increasing the number of cells is superior to classical rehashing algorithms. Our adaptation algorithm requires no hash function computation, no random memory accesses, and O(1) auxiliary memory. Our scheme is also competitively fast, especially when multiple processor cores are contending for main memory. Because it relies on bidirectional linear probing, only one random access to main memory is needed per operation. Main memory size is decreasingly a limiting factor in verification, and our scheme is usually faster than the standard bitstate approach until memory is scarce enough to shrink cells for the first time. Even then, each adaptation operation to shrink the cells only adds less than two percent to the accumulated running time. Execution time can also be trimmed by integrating into the structure the matching of states on the search stack or search queue, used for partial-order reductions [10,11]. This entails dedicating a bit of each cell to indicating whether

14

P.C. Dillinger and P. (Pete) Manolios

that element is on the stack. In many cases, such integration reduces the memory required for such matching and improves its accuracy as well. In Section 2 we overview Cleary’s compact hash tables and describe a noticeable improvement. Section 3 describes our fast adaptation algorithms. Section 4 describes how to incorporate search stack/queue matching to support partialorder reduction. Section 5 tests the performance of our scheme. In Section 6, we conclude and describe avenues for future work.

2

Cleary Tables

John G. Cleary describes an exact representation for sets in which only part of the descriptor of an element and a constant amount of metadata needs to be stored in each cell [7]. The rest of the descriptor of each element is given by its preferred location in the structure; the metadata link elements in their actual location with their preferred location. We describe one version of Cleary’s structure and describe how redundancy in the metadata enables one of three metadata bits to be eliminated. A Cleary table is a single array of cells. For now, assume that the number of cells is 2a , where a is the number of address bits. If each element to be added is b bits long, then the first a are used to determine the home address (preferred location) and the remaining b − a are the entry value stored in the cell. With three metadata bits, each cell is therefore b−a+3 bits. At this point, we notice some limitations to the Cleary structure. First, each element added has to be of the same fixed size, b bits. It might also be clear that operations could easily degrade to linear search unless the elements are uniformly distributed. This can be rectified by using a randomization function (1:1 hash), but in this paper, we will use the Cleary table exclusively to store hashes, which are already uniformly distributed. We are using an exact structure to implement an inexact one, a fine and well-understood approach [8,12]. 2.1

Representation

We can’t expect each element added to be stored in the cell at its home address; this is where bi-directional linear probing and the metadata come in. Entries with the same home address will be placed in immediate succession in the array, forming chains. The change metadata bit marks that the entry in that cell is the beginning of a chain. The mapped bit at an address marks that there is a chain somewhere in the table with entries with that home address. The occupied bit simply indicates whether an entry is stored in that cell. The nth change bit that is set to 1 begins the chain of entries whose home address is where the nth mapped bit that is set to 1 is located. To ensure that every occupied entry belongs to a chain with a home address, a Cleary table maintains the following invariant:

Fast, All-Purpose State Storage

15

Invariant 1. In a Cleary table, the number of mapped bits set is the same as the number of change bits set. Furthermore, the first occupied cell (if there is one) has its change bit set. The chains do not have to be near their homes for the representation to work, but the order of the chains corresponds to the order of the set mapped bits. Conceptually, the occupied and change bits relate to what is in the cell and the mapped bit relates to the home address whose preferred location is that cell. One could implement a variant in which the number of cells and home locations is different, but we shall keep them the same. 2.2

Random Access

For the structure to be fast, chains should be near their preferred location, but it is not always possible for each chain to overlap with its preferred location. Nevertheless, this next invariant makes fast access the likely case when a portion of cells are left unoccupied: Invariant 2. In a Cleary table, all cells from where an element is stored through its preferred location (based on its home address) must be occupied. This basically says that chains of elements must not be interrupted by empty cells, and that there must not be any empty cells between a chain and its preferred location. Consequently, when we go to add an element, if its preferred location is free/unoccupied, we store it in that cell and set its change bit and mapped bit. We know by Invariant 2 that if the preferred location of an element is unoccupied, then no elements with that home address have been added. Consequently, the mapped bit is not set and there is no chain associated with that home address. (See the first two additions in Figure 1.) If we’re trying to add an element whose preferred location is already occupied, we must find the chain for that home address–or where it must go–in order to complete the operation. Recall that the element stored in the corresponding preferred location may or may not be in the chain for the corresponding home address. To match up chains with home addresses—to match up change bits with mapped bits—we need a “synchronization point.” Without Invariant 2 the only synchronization points were the beginning and end of the array of cells. With Invariant 2, however, unoccupied cells are synchronization points. Thus, to find the nearest synchronization point, we perform a bidirectional search for an unoccupied cell from the preferred location. From an unoccupied, unmapped cell, we can backtrack, matching up set mapped bits with set change bits, until we reach the chain corresponding to the home address we are interested in—or the point where the new chain must be inserted to maintain the proper matching. If we are adding, we have already found a nearby empty cell and simply shift all entries (and their occupied and change bits) toward and into the empty cell, opening up a space in the correct chain—or where the new chain must be added. The remaining details of adding

16

P.C. Dillinger and P. (Pete) Manolios

Index (dec) Index (bin) Mapped Change Occupied Data entry

0 000

1 001

2 010

3 011

4 100

5 101

6 110

7 111

001

010

011

100

101

110

111

101

110

111

Add "1001110" Index (bin) Mapped Change Occupied Data entry

000

1110

Add "0001010" Add "1011100" Add "1110110" Index (bin) 000 Mapped Change Occupied Data entry 1010

001

010

011

100

1110 1100

0110

Add "0001011" Add "1000011" Index (bin) 000 001 Mapped Change Occupied Data entry 1010 1011

010

011

100

101

0011 1110 1100

110

111

0110

Add "0111101" Add "1000101" Index (bin) 000 001 010 011 100 101 110 111 Mapped Change Occupied Data entry 1010 1011 1101 0011 0101 1110 1100 0110 Fig. 1. This diagram depicts adding eight elements to a Cleary table with eight cells. In this example, the elements are seven bits long, the home addresses are three bits long, and the cell data entries are, therefore, four bits long. Each cell is shown with three metadata bits (mapped, change, and occupied). The lines connecting various metadata bits depict how the metadata bits put the entries into chains associated with home addresses.

Fast, All-Purpose State Storage

17

are a trivial matter of keeping the change and mapped bits straight. See Figure 1 for examples, but Cleary’s paper can be consulted for full algorithms [7]. Because each add or query operation requires finding an empty cell and the structure uses linear probing, the average search length can grow very large if the structure is allowed to grow too full. Others have analyzed this problem in detail [13], but in practice, more than 90% occupancy is likely to be too slow. We default to allowing no more than 85% occupancy. Note, however, that the searching involves linear access to memory, which is typically much less costly than random access. For large structures, random accesses are likely to miss processor cache, active DRAM pages, and even TLB cache. 2.3

Eliminating occupied Bits

The last invariant was originally intended to speed up lookups, but we show how it can be used to eliminate the occupied bits: Invariant 3. In a Cleary table, all entries in a chain are put in low-to-high unsigned numerical order. This makes adding slightly more complicated, but probably does not affect much the time per visited list operation, in which all negative queries become adds. With Invariant 3, the occupied bits are redundant because if we fill all unoccupied entries with all zeros and make sure their change bit is unset, then entries with all zeros are occupied iff their change bit is set. This is because entries with all zeros will always be first in their chain, so they will always have their change bit set. Eliminating this bit allows another entry bit to be added in the same amount of memory, which will cut expected omissions in half. This optimization does seem to preclude the encoding of multisets by repeating entries, because only one zero entry per chain is allowed under the optimized encoding. It seems this is not a problem for visited lists, but will complicate the combination of adaptation and stack matching. 2.4

Analysis

As briefly mentioned, we will use this structure to store exactly inexact hashes of the visited states. This makes the probabilistic behavior relatively easy to analyze. If the hashes are b bits long with a bits used for the home address, the structure has 2a cells of b − a + 2 bits each. Let n be the number of cells occupied, which is also the number of states recognized as new. The probability of the next new state appearing to have already been visited is f = n/2b . The expected number of new states falsely considered visited until the next one correctly recognized as new is f /(1 − f ). (For example, when f = 0.5, we expect 0.5/(1 − 0.5) = 1 new state falsely considered visited per new state correctly recognized as new.) Thus, the expected hash omissions for a Cleary table after recognizing n states as new is b  n−1 
n/2b 2b n/2 f n b oˆCT (n, b) = ≈ n df = −n − 2 ln 1 − (1) 1 − n/2b n 0 1−f 2b i=0

18

P.C. Dillinger and P. (Pete) Manolios

Note that floating-point arithmetic, which is not good at representing numbers very close to 1, is likely to give inaccurate results for the last formula. Here are simpler bounds, which are also approximations when n  2b : n(n − 1) n − 1 n/2b n−1 n/2b n(n − 1) = · ≤ o ˆ (n, b) ≤ · = b+1 CT 2b+1 2 1 2 1 − n/2b 2 − 2n

(2)

For example, consider storing states as b = 58-bit hashes in 228 cells. There are then a = 28 address bits and 58 − 28 + 2 = 32 bits per cell. That is correct: a Cleary table can store any 228 58-bit values using only 32 bits for each one. If we visit n = 2 × 108 states, we expect 0.06939 hash omissions (all approximations agree, given precise enough arithmetic). Consequently, the probability of any omissions is less than 7%. The structure is approximately 75% full, which means the structure is using roughly 43 bits per visited state. Non-powers of 2. The problem of creating a Cleary table of hash values with a number of cells (and home addresses) that is not a power of two can be reduced to the problem of generating hash values over a non-power-of-two range. Take how many cells (home addresses) are desired, multiply by 2b−a (the number of possible entry values), and that should be the number of possible hash values. In that case, stripping off the address bits—the highest order bits of the hash value—results in addresses in the proper range.

3

Fast Adaptation

Here we describe how to adapt a Cleary table of hash values to accommodate more values in the same space, by forgetting parts of the stored hash values. The basis for the algorithms is a useful “closer-first” traversal of the table entries. In this paper, we use this in doubling the number of cells, by cutting the size of each in half, and in converting the table into certain Bloom filters. Both of these can be done in place making only local modifications throughout the structure (no random accesses). 3.1

Twice as Many, Half the Size

Consider the difference between a Cleary table with cells of size 2j = b − a + 2 bits and one with cells of half that size, 2j−1 = b − a + 2 bits. If they are the same size overall, then the second has twice as many addresses—one more address bit: a = a + 1. If the elements added to these are prefixes of the same set of hash values, they will have similar structure. Each home address in the first corresponds to two home addresses in the second, so each mapped home address in the first will have one or both of the corresponding home addresses in the second mapped. In fact, the left-most (highest) bit of an entry in the first determines which of the two corresponding home addresses it has in the second. Thus, the entries in the second have one less bit on the left, which is now part of the home address, and 2j−1 − 1 fewer on the right. Only the 2j−1 − 1 bit on

Fast, All-Purpose State Storage

19

the right are truly missing in the second structure; that is half of the 2j − 2 bits per entry in the first structure. For example, if j = 5 and a = 20, the first structure has 25 = 32 bits per cell, 32−2 = 30 bits per stored entry, and each element is 30+20 = 50 bits. The second structure has 16 bits per cell, 16 − 2 = 14 per stored entry, 20 + 1 = 21 address bits, and 14 + 21 = 35 bits per element. The second effectively represents 30/2 = 15 fewer bits per element. Both structures are 32×220 bits or 4 megabytes overall. Converting from the first to the second requires careful attention to two things: (1) making sure the new mapped and change bits are updated properly, as each one set in the old structure could entail setting one or two in the new, and (2) making sure to shift elements toward their preferred location, displacing any empty cells in between. These correspond to preserving Invariant 1 and Invariant 2 respectively. Preserving Invariant 3 is just a matter of keeping elements in the same order. In fact, if a chain becomes two in the new structure, Invariant 3 guarantees that all elements in the new first chain are already before elements of the new second chain, because elements with the highest-order bit 0 come before those with highest-order bit 1! A naive approach that converts the data entries in order from “left” to “right” or “right” to “left” fails. As we iterate through the chains, we need to update the new mapped bits according to the presence of new chains, and those mapped bits might be off to either side of the chains. The problem is that half of the new mapped bits are where old data entries are/were, and we cannot update mapped bits on the side where we have not processed. We could queue up those new mapped bits and update them when we get there, but the queue size is technically only bounded by the length of the whole structure. A preferable solution should only process data entries whose new mapped bit lies either in the cell being processed or in cells that have already been processed. We can solve this problem with a traversal that processes entries in an order in which all entries between an entry and its preferred location are processed before that entry is processed. 3.2

Closer-First Traversal

It turns out that virtually any in-place, fast adaptation we want to do on a Cleary table can be done by elaborating a traversal that processes the entries between any given entry and its preferred location before processing that entry. This traversal can be done in linear time and constant space. All accesses to the table are either linear/streaming or expected to be cached from a recent linear access. The following theorem forms the basis for our traversal algorithm: Theorem 1. In a Cleary table, the maximal sequences of adjacent, occupied cells can be divided uniquely into subsequences all with the following structure: – Zero or more “right-leaning” entries each with its preferred location higher than its actual location, followed by – One “pivot” entry at its preferred location, followed by

20

P.C. Dillinger and P. (Pete) Manolios

– Zero or more “left-leaning” entries each with its preferred location lower than its actual location. Proof Idea. Proof is by induction on the number of pivots in a maximal sequence, using these lemmas: – An entry in the first cell of the structure is not left-leaning, and an entry in the last cell is not right-leaning. (This would violate Invariant 1 or how change bits are implicitly connected to mapped bits.) – An entry adjacent to an unoccupied cell cannot be leaning in the direction of the unoccupied cell. (This would violate Invariant 2.) – A left-leaning entry cannot immediately follow a right-leaning entry. (Such entries would be in different chains and violate how change bits are implicitly connected to mapped bits.)   This theorem solves the bootstrapping problem of where to start. We start from each pivot and work our way outward. To minimize the traversing necessary to process entries in an acceptable order, we adopt this order within each subsequence: process the pivot, process the right-leaning entries in reverse (right-toleft) order, and then process the left-leaning entries in (left-to-right) order. Index (bin) 000 001 010 011 100 101 110 111 Mapped Change Occupied Data entry 1010 1011 1101 0011 0101 1110 1100 0110 Theorem 1 Categorization

P

Traversal order

1

P 2

5

4

3

P 6

7

8

Fig. 2. This diagram takes the final Cleary table from Figure 1, shows how the entries are categorized according to Theorem 1, and lists the order of processing by the closerfirst traversal

A natural implementation of the overall traversal, which finds subsequences “on the fly,” goes like this: (1) Remember starting location. (2) Scan to a pivot and remember its location. (3) Process the pivot and then all entries back through the starting location (reverse order). (4) Process entries after the pivot until one that is not left-leaning and go back to (1). To determine the direction of each entry’s home, home addresses for the current and saved locations are tracked and updated as they are updated. Proper tracking eliminates the need for searching for synchronization points. All accesses are adjacent to the previous except between steps (3) and (4). Since the pivot was processed recently, it will still be cached with high probability. A corollary of Theorem 1 is that processing entries in this order guarantees that processing the (old or new) home location of an entry will never come after the processing of that entry.

Fast, All-Purpose State Storage

3.3

21

Building on the Traversal

The closer-first traversal allows us to compact cells to half their size and update mapped and change bits accordingly without overwriting unprocessed cells. (That handles Invariant 1.) Storing entries near their preferred location (Invariant 2) can also be handled in the same elaborated traversal. We store the pivot entry in the new cell that is its preferred location. For processing the right-leaning entries, we keep track of the “next” new location, which is the one just before (left of) the new cell we most recently put an entry into. Each right-leaning entry will be placed at the minimum (left-most) of that “next” location and the entry’s preferred location. We do the symmetric thing for left-leaning entries. This procedure guarantees Invariant 2 because it places each entry either at its preferred location, or adjacent to an entry (which is adjacent to an entry . . . ) which is at that preferred location. 3.4

Our Design

Cell sizes should be powers of two to allow for repeated cutting in half. Our current design starts with 64 bits per cell. If there are, say, 228 cells (2 GB), states are stored as 62 + 28 = 90 bit hash values. The probability of any omissions is theoretically one in billions. Jenkins’ hash functions are fast and behave according to expectation [14]. Thus, the only tangible benefit of allowing larger values is psychological, and it might require more hash computation. Recall that the structure becomes unacceptably slow beyond 90% occupancy. Thus, when an occupancy threshold is reached (default 85%), we convert from 64 to 32, from 32 to 16, and from 16 to 8. We do not go from 8 to 4. Consider what a Cleary table with 4 bits per cell would be like. Two bits are metadata and two bits are left for the entry. Each cell contains only one of four possible entries. But each cell is four bits long. This means we could represent sets of values with the same number of bits using the same amount of memory just by using them as bit indexes into a bit vector, and that would allow us to add any number of such values. That would be the same as a k = 1 Bloom filter. You could also think of it as a Cleary table with just mapped bits; entries are 0 bits, so no need for change bits. In other words, a Cleary table with 4 bits per cell is no more accurate than a k = 1 Bloom filter, cannot accommodate as many elements, and might be noticeably slower. Thus, we choose to convert from an 8-bit-per-cell Cleary table into a Bloom filter. We actually convert into a special k = 2 Bloom filter, but let us first examine how to convert an 8-bit-per-cell Cleary table into a single-bit (k = 1) Bloom filter. 3.5

Adapting to Bloom Filter

Adapting a Cleary table using 8 bits per cell into a single-bit (k = 1) Bloom filter is incredibly easy using the traversal. To turn an old entry into a Bloom filter index, we concatenate the byte address bits with the highest three data bits, from

22

P.C. Dillinger and P. (Pete) Manolios

the six stored with each old entry. This means that setting the Bloom filter bit for each old entry will set one of the eight bits at that entry’s preferred location. In other words, only bytes that had their mapped bits set will have bits set in the resulting Bloom filter. Using the same “closer-first” traversal guarantees that entries are not overwritten before being processed. Unfortunately, single-bit Bloom filters omit states so rapidly that they often starve the search before they have a high proportion of their bits set. Holzmann finds that setting three bits per state (k = 3) is likely to strike the right balance between not saturating the Bloom filter and not prematurely starving the search. Unfortunately, we cannot convert a Cleary table using 8 bits per cell into any structure we want. First of all, it needs to have locality in the conversion process, so that we can do the conversion in place. Second, it can only use as many hash value bits as are available in the 8-bit-per-cell Cleary table. We believe the best choice is a special k = 2 Bloom filter that has locality. It is well-known that forcing Bloom filter indices to be close to one another significantly harms accuracy, but we do not have much choice. The first index uses three of the six old entry bits to determine which bit to set. That leaves only three more bits to determine the second index, which can certainly depend on the first index. Running some simulations has indicated that it does not really matter how those three bits are used to determine the second index from the first; all that matters is that all three are used and that the second index is always different from the first. We have decided that the easiest scheme to implement uses those three bits as a bit index into the next byte. Thus, the same address bits that determined the home addresses for the 8-bit Cleary table determine the byte for the first Bloom filter index. The first three entry bits determine the index within that byte, and the next three determine the index within the next byte. Altering the conversion/adaptation algorithm to generate this structure is not too tricky. Recognizing that we cannot order our traversal to avoid the second indices overwriting unprocessed entries, we must keep track of the new byte value that should follow the right-most processed entry and not write it until the entry has been processed. That is the basic idea, anyway. Our implementation caches up to three bytes yet to be written: one left over from the previous subsequence, one to come after the pivot, and one more to work with while iterating down the “leaning” sides. We can analyze the expected accuracy of this scheme by building on results from previous work [4]. This is a k = 2 fingerprinting Bloom filter whose fingerprint size is 3 bits more than one index (log2 s = 3 + log2 m; s = 8m; s is the number of possible fingerprints and m is the number of bits of memory for the Bloom filter). Previous work tells us that a simple over-approximation of the expected hash omissions from a fingerprinting Bloom filter is the sum of the expected hash omissions due to fingerprinting, which we can compute using Equation 1 or 2 (b = 3 + log2 m), and the expected hash omissions due to the

Fast, All-Purpose State Storage

underlying Bloom filter, which is roughly Thus, our rough estimate is oˆBF ≈

n−1 i=0

23

(1−e−2i/m )2 ≈ n(1−e−2n/m )2 /2.

2 n(n − 1) n + 1 − e−2n/m 2(8m − n) 2

(3)

That formula and Equations 1 and 2 give the expected omissions assuming we had been using the given configuration since the beginning of the search. That is easily corrected by subtracting the expected hash omissions for getting to the starting conditions of each new configuration—had that configuration been used from the beginning. For each Cleary table configuration, we subtract the expected hash omissions for the starting number of occupied cells from the expected hash omissions for the ending number of occupied cells. Note that collapses can make the next starting number smaller than the previous ending number. We cannot easily be so exact with the Bloom filter, so we can just use the previous ending number as the starting number.

4

Search Stack Matching

Partial-order reductions play a central role in making contemporary explicitstate verifiers effective [15], by reducing the size of the state space that needs to be searched for errors. In many cases, the reduction is dramatic, such as making previously intractable problems tractable. A typical implementation requires runtime support in the form of a “cycle proviso,” which needs to know whether a state is on the DFS stack [10] or BFS queue [11] (depending on whether depth-first or breadth-first search is being used). We will refer to this as checking whether the state is active. Combining with visited list. A visited list based on cells, such as the Cleary table, can include a bit with each cell that indicates whether the state stored in that cell is active. This can be a compact option since no other random-access structure with this data is required. However, the relative size of the stack or queue can be small enough that the vast majority of active bits would be zero and a separate structure would be more compact. Speed should favor the unified structure, because separate lookup is not required to check whether a state is active. Marking the state as active can also “piggy-back” on the initial look-up by saving the cell location where the new entry was just placed. Accuracy is also a strong point of the unified structure. Specifically, stack/queue matching is 100% accurate whenever the visited list is accurate. Using a separate structure that is independently inaccurate could lead to imprecise reductions and error omission even if the visited list causes no omissions. Complications. Despite the fact that multiple states can map to the same value at the same address in a Cleary table (or other “hash compaction” scheme), there is not traditionally a need to account for multiple stack entries per stored

24

P.C. Dillinger and P. (Pete) Manolios

value, because only one such state would ever be recognized as new and, therefore, only one can ever be active. But our adaptive Cleary tables can have more than one state on the stack that each map to the same table entry. When shrinking cells, some pairs of entries will no longer be distinguishable and are collapsed into one. (One of each such pair would have been a hash omission if the new cell size had been used from the beginning!) If both states are on the stack, however, we prefer to be able to say that there is more than one state on the stack matching a certain entry. Cleary’s table representation allows duplicate entries, so in these rare cases, perhaps we could duplicate the entry for each matching state on the stack. However, our optimization that allowed only two metadata bits per state assumed that an entry of all zeros would be at the beginning of a chain, and if we allow more than one entry of all zeros in a chain, this is no longer the case. However, the only case in which we want to have duplicate entries is when each of those entries needs to have its active bit set. As long as the active bit is set, therefore, it would be possible to distinguish the entry from an unoccupied cell. When the state gets removed from the stack/queue, however, we would need to do something other than clearing the active bit and turning the duplicate all-zeros entry into an unoccupied cell (which could violate Invariant 2). Since deletion from a Cleary table is possible, we just delete the duplicate entry when its active bit is cleared. Our implementation deletes all such duplicates, not just all-zero entries, to (1) make room for more additions and (2) maintain the invariant that no state that is active has a matching entry in the Cleary table without its active bit set. A final complication comes when the structure becomes a Bloom filter, which is not based on cells. For a single-bit Bloom filter, we could have an active bit for each bit, but that would be a waste of space considering what a small proportion of visited states are typically on the stack. There is also the problem that a Cleary table with 8 bits per cell and an active bit in each cell only has five entry data bits per cell. Ideally, we want a two-bit Bloom filter that uses all five bits and takes up more space than the accompanying active information. Here’s a design: use two bits per byte as a counter of the number of active states whose home is/was this byte. As in a counting Bloom filter [16], the counter can overflow and underflow, introducing the possibility of false negatives—in addition to the false positives due to sharing of counters. In the context of a search that is already rather lossy, these are not big issues. Six bits of each byte remain for the Bloom filter of visited states. If we set two bits per state, one in the home and one in the following byte, that is 36 possibilities for states whose home is this byte. The 5 bits of data left allow us to cover 32 of those 36 possibilities. Mapping those 5-bit values to pairs of indices 0..5 is efficient with a small look-up table. This makes it easy to spread indices somewhat evenly over that range, but all six bit indices cannot have the exact same weight/likelihood.

5

Validation

We have implemented the schemes described in a modified version of Spin 5.1.7 and use that for all of the experimental results. It can be downloaded from [17].

Fast, All-Purpose State Storage

25

Our implementation also outputs the expected hash omission numbers based on formulas given. Timing results were taken on a 64-bit Mac Pro with two 2.8 GHz quad-core Intel Xeon processors and 8GB of main memory. 5.1

Accuracy

In this section we demonstrate the accuracy advantages of our adaptive Cleary+ Bloom structure as compared to the standard k = 3 bitstate approach and validate the predictive value of our formulas. Setup. The main accuracy test of Figure 3 has an artificial aspect to it, and we explain that here. A typical protocol is subject to what we call the transitive omission problem [4]. States omitted from a lossy search can be put in two categories: hash omissions, those states that were falsely considered not new by the visited list, and transitive omissions, those states that were never reached because other omissions made them unreachable. Clearly, if there are zero hash omissions, there are zero transitive omissions. But when there are hash omissions, we do not reliably know how many transitive omissions resulted. In well-behaved protocols, there tends to be a linear relationship, such as two transitive omissions per hash omission. Despite the transitive omission problem—or perhaps because of it—minimizing expected hash omissions is key to maximizing the accuracy of a search. This approach also optimizes two other metrics: the probability of any omissions and expected coverage. Note that when much smaller than 1, the expected hash omissions approximate the probability of any omissions. However, the probability of any omissions is not good at comparing searches that are expected to be lossy, and coverage is hard to predict in absolute terms in the presence of transitive omissions. Thus, we focus on minimizing hash omissions. To measure hash omissions and compare those results against our mathematical predictions, we generated a synthetic example that is highly connected and, therefore, should have almost no transitive omissions. The model consists of a number starting at zero, to which we non-deterministically add 1 through 10 until a maximum is reached. Choosing that maximum allows us to manipulate the size of the state space, as we have done to get the results in Figure 3. Adaptive vs. Bitstate. A quick examination of Figure 3 confirms that when memory is not highly constrained (left side), our visited list scheme (“Adaptive”) is more accurate than (below) the standard bitstate approach (“Bitstate”). (For now, only consider the results using a chaining hash table for stack matching, “ChainTable.”) For example, at around 200 000 states, our scheme has less than a 1 in 10 000 chance of any omissions while the bitstate scheme expects to have omitted about 10 states. When memory is highly constrained (right side), the two yield similar accuracy. If we look at the “Adaptive, ChainTable” accuracies in more detail, we can see where the adaptations occur. When the expected omissions are near 10−14 , it is still using 64 bits per cell. When the expected omissions jump to 10−5 , it has changed over to 32 bits per cell. Near one omission, it is using 16 bits per

26

P.C. Dillinger and P. (Pete) Manolios

Average omissions (log scale)

100000

1

1e-05 Adaptive, ChainTable, Observed Adaptive, ChainTable, Predicted Adaptive, Integrated, Predicted Adaptive, CountingBF, Predicted Bitstate, ChainTable, Observed Bitstate, ChainTable, Predicted Bitstate, CountingBF, Predicted

1e-10

1e-15 100000

1e+06 State space size (log scale)

Fig. 3. This graph compares the predicted and observed accuracy of searches using our adaptive scheme and the standard k = 3 bitstate scheme, using different DFS stack-matching schemes. The model is described in Section 5.1; it exhibits virtually no transitive omissions and allows the state space size to be manipulated. About 1MB total is available for visited and active state matching (see Section 5.1). Observation data points represent the average of 10-50 trials. Not enough trials were performed to observe any omissions from searches expecting full coverage with high probability. To avoid clutter, observations for many configurations are omitted but are analogously close to prediction. Predicted values are based on equations given in this paper.

cell. When it moves to 8 bits per cell, its accuracy is similar to the standard k = 3 bitstate approach. The structure converts to the special k = 2 Bloom filter around 106 states. The mathematical prediction overestimates a little at first because of the roughness of the approximation for fingerprinting Bloom filters, but it gets closer later. No observations show up for the 64 and 32 bits per cell cases because no omissions were encountered in the tens of trials run for each state space size. At least a million trials would have been required to get good results for 32 bits per cell. Figure 3 generalizes very easily and simply. These results are for 1 megabyte. To get the results for c megabytes, simply multiply the X- and Y-axis values by c. It is that simple. In other words, the proportion of states that are expected to be hash omissions under these schemes depends only on the ratio between states and memory, not on their magnitude. Unlike many classical structures, these schemes scale perfectly. Also, the Jenkins hash functions [14] used by Spin are good enough that, for all non-cryptographic purposes, the relationships among reachable state descriptors in a model are irrelevant. The Jenkins hashes are effectively random.

Fast, All-Purpose State Storage

27

Stack Matching. The “ChainTable” results of Figure 3 assume that a chaining hash table is used to match active states and that its memory size is negligible compared to the memory size of the visited list (see memory usage in Figure 4). This is the case for problems whose maximum depth is orders of magnitude smaller than the state space size. Because this approach is faster and usually more compact than what is currently available in Spin(version 5.1.7)—but an application of classical techniques—we consider it state-of-the-art for this case. (More information is on the Web [17].) The “CountingBF” results assume that a counting Bloom filter [16] that occupies half of available memory is used. This is the allocation usually used by Spin’s CNTRSTACK method, and we consider it state-of-the-art for unbounded active lists that are dynamically swapped out to disk, as in Spin’s SC (“stack cycling”) feature. Note that a counting Bloom filter cannot overflow a fixed memory space as a chaining hash table can. The important difference for Figure 3 is that only half as much memory is available to the visited list for the “CountingBF” results as for the “ChainTable” results—to accommodate the large counting Bloom filter. Thus, the counting Bloom filter approach is clearly detrimental to accuracy if the search stack is small enough to keep in a small area of memory (Figure 3). The (k = 2) counting Bloom filter is also relatively slow, because it always requires two random lookups into a large memory space; thus it is DRAM-intensive (see Figure 4). But if the search stack is large enough to warrant swapping out, the counting Bloom filter is likely to be a better choice (not graphed, but see memory usage in Figure 5). Using our adaptive Cleary+Bloom structure allows a third option: integrating active state matching with visited state matching (“Integrated”), which is always preferable to the counting Bloom filter. Making room for the counting Bloom filter as a separate structure requires cutting the bits per entry by about half. Making room for one active bit in each cell only takes away one entry bit. The result is a doubling in the expected omissions, which is tiny compared to the impact of cutting cell sizes in half (“Adaptive, Integrated” vs. “Adaptive, CountingBF” in Figure 3). 5.2

Speed

Figure 4 confirms that the Cleary table is very fast when the structure is big and never gets beyond about half full. Plugging in a 64-bit Cleary table in place of k = 3 bitstate increases speed by about 2.8% when running by itself. Using the Cleary table also for search stack matching increases that to 5.5%, unless using the counting Bloom filter with standard bitstate, which is 13.5% slower than the integrated Cleary structure. The Cleary table with integrated matching of active states is the least affected by running in parallel with other model checker instances. Running six instances simultaneously slows each by about 9%, but running six instances of Spin’s bitstate implementation slows them by about 20%. This can easily be explained by the fact that the Cleary table with integrated stack matching only needs one random access to main memory to check/add a new state and/or check/add it

New states per second per process

28

P.C. Dillinger and P. (Pete) Manolios

700000 600000 500000 400000 300000 200000

Cleary, Integrated MEM=1089MB Cleary, ChainTable MEM=1105MB Bitstate, ChainTable MEM=1105MB Bitstate, CountingBF MEM=1083MB

100000 0 1

2

3

4

5

6

Number of processes running in parallel

Fig. 4. This plots the verification speed, in average time per state per process, of various visited and stack matching methods for one to six instances running in parallel on a multicore system. In this test, Cleary tables never became full enough to trigger adaptation algorithms. The model is PFTP with LOSS=1,DUPS=1,QSZ=5. Statevector is 168 bytes. Visited state storage is 1024MB, except for CountingBF, which is given 512MB each for the visited set and the counting Bloom filter stack. Depth limit of 1.5 million was beyond the maximum and required a relatively small amount of additional storage. 67.8M states results in about 127 bits per state.

to the search stack. The k = 3 bitstate method with the counting Bloom filter stack requires five random accesses. Figure 5 shows how the user can optimize more for speed or more for accuracy by setting the maximum occupancy before adaptation. The omissions (not graphed) decrease with higher maximum occupancy, most dramatically between 60% and 65% (in this case) because 60% and lower ended with a smaller cell size. The omissions for 60% were about twenty times higher than for 65%, a much larger difference than between 50% and 60% or 70% and 90%. Adaption itself does not cause omissions, but after adaption, the significantly higher rate of omission causes the number of omissions to jump, as in Figure 3. Typically, lower maximum occupancy means faster, but 60% was actually slower than 65% because the 60% doubled the number of cells right before it finished. It should be possible to avoid such scenarios with heuristics that predict how close to completion the process is and allowing higher occupancy if near completion. Nevertheless, even after doubling its number of cells several times, our adaptive storage scheme is faster than standard bitstate in some cases. Another experiment (not graphed) exhibits how little time is needed for adaptation. We ran a 370 million state instance of PFTP(1,1,7) using 320 megabyte instances of our adaptive structure, causing adaptation all the way down to a k = 2 Bloom filter. Adaptation operations required 1.3-2.0% of the running time so far, with the total time spent on adaptation never exceeding 3.3% of the running time so far. This includes maximum allowed occupancies of 75% and 90%,

Fast, All-Purpose State Storage

29

New states per second (overall)

700000 650000 600000 550000 500000 450000 400000

Adaptive, Integrated(SC) MEM=548MB Adaptive, ChainTable MEM=675MB Bitstate, ChainTable MEM=675MB Bitstate, CountingBF(SC) MEM=545MB

350000 50 60 70 80 90 Maximum allowed % occupancy before each adaptation

100

Fig. 5. This plots the verification speed, in average time per state, of our adaptive Cleary tables, allowed to fill to various occupancies before each doubling of the number of cells. The straight lines show k = 3 bitstate performance with the specified stack matching scheme. Visited set is given 512MB, except for CountingBF(SC), which splits that equally between visited and active state matching. “Stack cycling” (SC) was used when supported to reduce memory requirements. Otherwise, depth limit of 3 million was needed to avoid truncation. The model is PFTP with LOSS=1,DUPS=1,QSZ=6. State-vector is 192 bytes. 170M states results in about 25 bits per state. All Cleary tables converted from 64 to 32 and 32 to 16 bits per cell. Those limiting to less than 65% occupancy also converted from 16 to 8 and had at least an order of magnitude more omissions. These results are for a single process running alone; results with four processes are slightly steeper and also cross the bottom line at around 90%.

with and without integrated active state matching, and 1 to 4 processes running simultaneously. Despite all the adaptations, “Adaptive, Integrated(SC)” was 718% faster and explored more states than “Bitstate, CountingBF(SC)” on the same problem given the same amount of memory. (Non-power of 2 memory size and significant time spent as a localized k = 2 Bloom filter conferred advantages to our adaptive structure not seen in previous results.) In other experiments not shown, we have noticed that the Cleary structure gains speed relative to competing approaches as memory dedicated to the structure grows very large. We suspect that this relates to higher latency per main memory access because of more TLB cache misses in accessing huge structures. If one compares the approaches using relatively small amounts of memory, findings are likely to be skewed against the Cleary table. The biggest sensitivity to the particular model used is in how long it takes to compute successors and their hashes, which is closely tied to the state vector size. More computation there will tend to hide any differences in time required by different state storage techniques. Less will tend to inflate differences. There is little way for a different model to result in different speed rankings. The PFTP

30

P.C. Dillinger and P. (Pete) Manolios

model used here for timings has a state vector size (about 200 bytes) that is on the low end of what might be encountered in large problems, such as those listed in Tables V and VI of [18].

6

Conclusion and Future Work

We have described a novel scheme for state storage that we believe has a future in explicit-state model checkers such as Spin. It has the flexibility to provide highassurance verification when memory is not highly constrained and good coverage when memory is highly constrained. In that sense, it is an “all-purpose” structure that requires no tuning to make good use of available memory. In many cases, our scheme is noticeably faster than Spin’s standard bitstate scheme. We believe this is due to its favorable access pattern to main memory: only one random look-up per operation. For example, when multiple processor cores are contending for main memory, our scheme is consistently faster. When supporting unbounded search stack/queue sizes, our scheme is consistently faster. Otherwise, the standard bitstate scheme is only a little faster once the number of states reaches about 1/100th the number of memory bits. At that point, bitstate has already omitted states while our scheme can visit twice that many with no omissions. Cleary’s compact hash tables and our fast, in-place adaptation algorithm offer speed, accuracy, compactness, and dynamic flexibility that previous schemes fall well short of in at least one category. We plan to extend this technique further. It should be possible to start a search storing full states and then adapt quickly in place to storing just hash values. This would provide the psychological benefit of exact storage for as long as possible. It should also be possible to make an intermediate adaptation step in between splitting cells in half. This is much trickier, but would make even better use of available memory. In fact, we hope to demonstrate how the scheme is “never far from optimal.”

References 1. Holzmann, G.J.: The Spin Model Checker: Primer and Reference Manual. AddisonWesley, Boston (2003) 2. Holzmann, G.J.: An analysis of bitstate hashing. In: Proc. 15th Int. Conf. on Protocol Specification, Testing, and Verification, INWG/IFIP, Warsaw, Poland, pp. 301–314. Chapman & Hall, Boca Raton (1995) 3. Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13(7), 422–426 (1970) 4. Dillinger, P.C., Manolios, P.: Bloom filters in probabilistic verification. In: Hu, A.J., Martin, A.K. (eds.) FMCAD 2004. LNCS, vol. 3312, pp. 367–381. Springer, Heidelberg (2004) 5. Stern, U., Dill, D.L.: A new scheme for memory-efficient probabilistic verification. In: IFIP TC6/WG6.1 Joint Int’l. Conference on Formal Description Techniques for Distributed Systems and Communication Protocols, and Protocol Specification, Testing, and Verification, pp. 333–348 (1996)

Fast, All-Purpose State Storage

31

6. Dillinger, P.C., Manolios, P.: Enhanced probabilistic verification with 3Spin and 3Murphi. In: Godefroid, P. (ed.) SPIN 2005. LNCS, vol. 3639, pp. 272–276. Springer, Heidelberg (2005) 7. Cleary, J.G.: Compact hash tables using bidirectional linear probing. IEEE Trans. Computers 33(9), 828–834 (1984) 8. Pagh, A., Pagh, R., Rao, S.S.: An optimal bloom filter replacement. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 823–829. SIAM, Philadelphia (2005) 9. Wolper, P., Leroy, D.: Reliable hashing without collision detection. In: 5th International Conference on Computer Aided Verification, pp. 59–70 (1993) 10. Holzmann, G.J., Peled, D.: Partial order reduction of the state space. In: First SPIN Workshop, Montr`eal, Quebec (1995) 11. Bosnacki, D., Holzmann, G.J.: Improving spin’s partial-order reduction for breadth-first search. In: Godefroid, P. (ed.) SPIN 2005. LNCS, vol. 3639, pp. 91– 105. Springer, Heidelberg (2005) 12. Carter, L., Floyd, R., Gill, J., Markowsky, G., Wegman, M.: Exact and approximate membership testers. In: Proceedings of the 10th ACM Symposium on Theory of Computing (STOC), pp. 59–65. ACM, New York (1978) 13. Pagh, A., Pagh, R., Ruzic, M.: Linear probing with constant independence. In: Proceedings of the 39th ACM Symposium on Theory of Computing (STOC), New York, NY, USA, pp. 318–327. ACM, New York (2007) 14. Jenkins, B.: http://burtleburtle.net/bob/hash/index.html (2007) 15. Clarke, E.M., Grumberg, O., Peled, D.: Model Checking. MIT Press, Cambridge (1999) 16. Fan, L., Cao, P., Almeida, J., Broder, A.Z.: Summary cache: a scalable wide-area Web cache sharing protocol. IEEE/ACM Transactions on Networking 8(3), 281– 293 (2000) 17. Dillinger, P.C., Manolios, P.: 3Spin home page, http://3spin.peterd.org/ 18. Holzmann, G.J., Bosnacki, D.: The design of a multicore extension of the spin model checker. IEEE Trans. Softw. Eng. 33(10), 659–674 (2007)

Efficient Probabilistic Model Checking on General Purpose Graphics Processors Dragan Boˇsnaˇcki1, Stefan Edelkamp2 , and Damian Sulewski3 1

Eindhoven University of Technology, The Netherlands 2 TZI, Universit¨ at Bremen, Germany 3 Technische Universit¨ at Dortmund, Germany

Abstract. We present algorithms for parallel probabilistic model checking on general purpose graphic processing units (GPGPUs). For this purpose we exploit the fact that some of the basic algorithms for probabilistic model checking rely on matrix vector multiplication. Since this kind of linear algebraic operations are implemented very efficiently on GPGPUs, the new parallel algorithms can achieve considerable runtime improvements compared to their counterparts on standard architectures. We implemented our parallel algorithms on top of the probabilistic model checker PRISM. The prototype implementation was evaluated on several case studies in which we observed significant speedup over the standard CPU implementation of the tool.

1

Introduction

Probabilistic Model Checking. Traditional model checking deals with the notion of absolute correctness or failure of a given property. On the other hand, probabilistic1 model checking is motivated by the fact that probabilities are often an unavoidable ingredient of the systems we analyze. Therefore, the satisfaction of properties is quantified with some probability. This makes probabilistic model checking a powerful framework for modeling various systems ranging from randomized algorithms via performance analysis to biological networks. From an algorithmic point of view, probabilistic model checking overlaps with the conventional one, since it too requires computing reachability of the underlying transition systems. Still, there are also important differences because numerical methods are used to compute the transition probabilities. It is those numerical components that we are targeting in this paper and show how they can be sped up by employing the power of the new graphic processors technology. 1

In the literature probabilistic and stochastic model checking often are used interchangeably. Usually a more clear distinction is made by relating the adjectives probabilistic and stochastic to the underlying model: discrete- and continuous-time Markov chain, respectively. For the sake of simplicity in this paper our focus is on discrete-time Markov chains, so we opted for consistently using the qualification “probabilistic”. Nevertheless, as we also emphasize in the paper, the concepts and algorithms that we present here can be applied as well to continuous-time Markov chains.

C.S. P˘ as˘ areanu (Ed.): SPIN 2009, LNCS 5578, pp. 32–49, 2009. c Springer-Verlag Berlin Heidelberg 2009


Efficient Probabilistic Model Checking on GPGP

33

Parallel Model Checking. According to [31] less than two years ago a clear majority of the 500 most powerful computers in the world (www.top500.org) were characterized as clusters of computers/processors that work in parallel. Unfortunately, this has not had a major impact on the popularity of parallel computing both in industry and academia. With the emergence of the new parallel hardware technologies, like multi-core processors and general purpose graphics processing units, this situation is changing drastically. This “parallelism for the masses” certainly offers great opportunities for model checking. Yet, ironically enough, model checking, that was mainly introduced for the verification of highly parallel systems, in the past has mostly relied on sequential algorithms. Parallel model checking algorithms have been designed before (e.g., [33,30,8]) and with few exceptions [27,26] all of them targeted clusters of CPUs. However, this did not have any major impact in practice - besides some recent case studies on a big cluster (DAS-3)[4] none of the widely used model checking tools has a cluster version that preserves its full range of capabilities. In the last several years the things started to change. In [24,25] the concept of multi-core model checking was introduced, followed by [5]. In the context of large-scale verification, different disk-based algorithms for solving the model checking problem have been published [16,9,7]. In [16], the authors avoid nested depth-first search for accepting cycle detection by reducing the liveness to a safety problem. This I/O-efficient solution was further improved by running directed search and exploiting parallelism. Another disk-based algorithm for LTL model checking [7] avoids the increase in space, but does not operate on-the-fly. The algorithm given in [9] is both on-the-fly and linear in the space requirements wrt. the size of the state space, but its worst-case time complexity is large. Other advances in large-scale LTL model checking exploit Flash media [18,19]. GPGPU Programming. In the recent years (general purpose) graphics processor units ((GP)GPUs) have become powerful massively parallel systems and they have outgrown their initial application niches in accelerating computer graphics. This has been facilitated by the introduction of new application programming interfaces (APIs) for general computation on GPUs, like CUDA form NVIDIA, Stream SDK from AMD, and Open CL. Applications that exploit GPUs in different domains, like fluid dynamics, protein folding prediction in bioinformatics, Fast Fourier Transforms, and many others, have been developed in the last several years [32]. In model checking, however, GPUs have not had any impact. To the best of our knowledge the only attempt to use model checking on GPUs was by the authors of this paper [15]. They improved large-scale disk-based model checking by shifting complex numerical operations to the graphic card. As delayed elimination of duplicates is the performance bottleneck, the authors performed parallel processing on the GPU to improve the sorting speed significantly. Since existing GPU sorting solutions like Bitonic Sort and Quicksort do not obey any speed-up on state vectors, they propose a refined GPU-based Bucket Sort algorithm. Additionally, they study sorting a compressed state vector and obtain speed-ups for delayed duplicate detection of more than one order of magnitude with a 8800-GTX GPU.

34

D. Boˇsnaˇcki, S. Edelkamp, and D. Sulewski

Contribution. Traditionally the main bottleneck in practical applications of model checking has been the infamous state space explosion [35] and, as a direct consequence, large requirements in time and space. With the emergence of the new 64-bit processors there is no practical limit to the amount of shared memory that could be addressed. As a result the goals shift towards improving the runtime of the model checking algorithms [25]. In this paper we show that significant runtime gains can be achieved exploiting the power of GPUs in probabilistic model checking. This is because basic algorithms for probabilistic model checking are based on matrix-vector multiplication. These operations lend themselves to very efficient implementation on GPUs. Because of the massive parallelism – a standard commercial video card comprises hundreds of fragment processors – quite impressive speedups with regard to the sequential counterparts of the algorithms are quite common. We present an algorithm that is a parallel adaptation of the method of Jacobi for matrix-vector product. Jacobi was chosen over other methods that usually outperform it on sequential platforms because of its lower memory requirements and potential to be parallelized because of fewer data dependencies. The algorithm features sparse matrix vector multiplication. It requires a minimal number of copy operations from RAM to GPU and back. We implemented the algorithm on top of the probabilistic model checker PRISM [28]. The prototype implementation was evaluated on several case studies and remarkable speedups (up to factor 18) were achieved compared to the sequential version of the tool. Related Work. In [11] a distributed algorithm for model checking of Markov chains is presented. The paper focuses on continuous-time Markov chain models and Computational Stochastic Logic. They too use a parallel version of Jacobi’s method, which is different from the one presented in this paper. This is reflected in the different memory management (GPUs hierarchical shared memory model vs. the distributed memory model) and in the fact that their algorithm stores part of the state space on external memory (disks). Also, [11] is much more oriented towards increasing the state spaces of the stochastic models, than improving algorithm runtimes, which is our main goal. Maximizing the state space sizes of stochastic models by joining the storages of individual workstations of a cluster is the goal pursuit also in [12]. A significant part of the paper is on implicit representations of the state spaces with a conclusion that, although they can further increase the state space sizes, the runtime remains a bottleneck because of the lack of efficient solutions for the numerical operations. In [1] a shared memory algorithm is introduced for CTMC construction and numerical steady-state solution. The CTMCs are constructed from generalized stochastic Petri nets. The algorithm for computing steady state probability distribution is an iterative one. Compared to this work, our algorithm is more general as it can be used in CTMCs also to compute transient probabilities. Another shared memory approach is described in [6]. It targets Markov decision processes, which we do not consider in this paper. As such it differs from our work significantly since the quantitative numerical component of the

Efficient Probabilistic Model Checking on GPGP

35

algorithm reduces to solving systems of linear inequalities, i.e., using linear program solvers. In contrast, large-scale solutions support multiple scans over the search space on disks [17,13]. Layout. The paper is structured as follows. Section 2 briefly introduces probabilistic model checking. Section 3 describes the architecture, execution model and some challenges of GPU programming. Section 4 presents the algorithm for matrix-vector multiplication as used in the Jacobi iteration method and its port to the GPU. Section 5 evaluates our approach verifying examples shipped with the PRISM source showing significant speedups compared to the current CPU solution. The last section concludes the paper and discusses the results.

2

Probabilistic Model Checking

In this section we briefly recall along the lines of [29] the basics of probabilistic model checking for discrete-time Markov chains (DTMCs). More details can be found in, e.g., [29,2]. Discrete Time Markov Chains. Given a fixed finite set of atomic propositions AP we define a DTMC as follows: Definition 1. A (labeled) DTMC D is a tuple (S, sˆ, P, L) where – S is a finite set of states; – sˆ ∈ S is the initial state; – P : S ×S → [0, 1] is the transition probability matrix where Σs
∈S P(s, s ) = 1 for all s ∈ S; – L : S → 2AP is a labeling function which assigns to each state s ∈ S the set L(s) of atomic propositions that are valid in the state. Each P(s, s ) gives the probability of a transition from s to s . For each state the sum of the probabilities of the outgoing transitions must be 1. Thus, end states, i.e., states which will normally not have outgoing transitions are modeled by adding self-loops with probability 1. Probabilistic Computational Tree Logic. Properties of DTMCs can be specified using Probabilistic Computation Tree Logic (PCTL) [20], which is a probabilistic extension of CTL. Definition 2. PCTL has the following syntax: Φ ::= true | a | ¬Φ | Φ ∧ Φ | P∼p [φ]

φ ::= X Φ | Φ U

≤k

Φ

where a ∈ AP , ∼∈ {<, ≤, ≥, >}, p ∈ [0, 1], and k ∈ N ∪ {∞}. For the sake of presentation, in the above definition we use both state formulae Φ and path formulae φ, which are interpreted on states and paths, respectively,

36

D. Boˇsnaˇcki, S. Edelkamp, and D. Sulewski

of a given DTMC D. However, the properties are specified exclusively as state formulae. Path formulae have only an auxiliary role and they occur as a parameter in state formulae of the form P∼p [φ]. Intuitively, P∼p [φ] is satisfied in some state s of D, if the probability of choosing a path that begins in s and satisfies φ is within the range given by ∼p. To formally define the satisfaction of the path formulae one defines a probability measure, which is beyond the scope of this paper. (For example, see [29] for more detailed information.) Informally, this measure captures the probability of taking a given finite path in the DTMC, which is calculated as the product of the probabilities of individual transitions of this path. The intuitive meaning of the path operators is analogous to the ones in standard temporal logics. The formula X Φ is true if Φ is satisfied in the next state of the path. The bounded until formula Φ U ≤k Ψ is satisfied if Ψ is satisfied in one of the next k steps and Φ holds until this happens. For k = ∞ one obtains the unbounded until. In this case we omit the superscript and write Φ U Ψ . The interpretation of unbounded until is the standard strong until. Algorithms for Model Checking PCTL. Given a labeled DTMC D = (S, sˆ, P, L) and a PCTL formula Φ, usually we are interested whether the initial state of D satisfies Φ. Nevertheless, the algorithm works by checking the satisfaction of Φ for each state in S. The output of the algorithm is Sat (Φ), the set of all states that satisfy Φ. The algorithm starts by first constructing the parse tree of the PCTL formula Φ. The root of the tree is labeled with Φ and each other node is labeled by a subformula of Φ. The leaves are labeled with true or an atomic proposition. Starting with the leaves, in a recursive bottom-up manner for each node n of the tree the set of states is computed that satisfies the subformula that labels n. When we arrive at the root we can determine Sat (Φ). Except for the path formulae the model checking of PCTL formulae is actually the same as for their counterparts in CTL and as such quite straightforward to implement. In this paper we concentrate on the path formulae. They are the most computationally demanding part of the model checking algorithm and as such they are the targets of our improvement via GPU algorithms. To give a general flavor of the path formulae, we give a briefly consider the algorithm for the formulae of the form P[Φ U≤k Ψ ], where k = ∞. This case boils down to finding the least solution of the linear equation system: ⎧ if s ∈ Sat(Ψ ) ⎨1 if s ∈ Sat(¬Φ ∧ ¬Ψ ) W(s, Φ U Ψ ) = 0 ⎩
Σs ∈S P(s, s ) · W(s , Φ U Ψ ) otherwise where W(Φ U Ψ ) is the resulting vector of probabilities indexed by the states in S. The states in which the formula is satisfied with probabilities 1 and 0 are singled out. For each other state the probabilities are computed via the corresponding probabilities of the neighboring states. Before solving the system, the algorithm employs some optimizations by precomputing the states that satisfy the formula with probability 0 or 1. The (simplified) system linear equations

Efficient Probabilistic Model Checking on GPGP

37

can be solved using iterative methods that comprise matrix-vector multiplication. One such method is the one by Jacobi, which is also one of the methods that PRISM uses and which we describe in more detail in Section 4. We choose Jacobi’s method over methods that on sequential architectures usually perform better. This is because Jacobi has certain advantages in the parallel programming context. For instance, it has lower memory consumption compared to the Krylov subspace methods and less data dependencies than the Gauss-Seidel method, which makes ti easier to parallelize [11]. The algorithms for the next operator and bounded until boil down to a single matrix-vector product and a sequence of such products, respectively. Therefore they can also be resolved by using Jacobi’s method. PCTL can be extended with various rewards (costs) operators that we do not give here. The algorithms for those operators can also be reduced to matrixvector multiplication [29]. Model checking of a PCTL formula Φ on DTMC D is linear in |Φ|, the size of the formula, and polynomial in |S|, the number of states of the DTMC. The most expensive are the operators for unbounded until and also the rewards operators which too boil down to solving system linear equations of size at most |S|. The complexity is also linear in kmax , the maximal value of the bounds k in the bounded until formulae (which also occurs in some of the costs operators). However, usually this value is much smaller than |S|. Thus, the main runtime bottleneck of the probabilistic model checking algorithms remain the linear algebraic operations. Their share of the total runtime of the algorithms increases with |S|. So, for real world problems, that tend to have large state spaces, this dependence is even more critical. In the sequel we show how by using parallel versions of the algorithms on GPU, one can obtain substantial speedups of more than one order of magnitude compared to the original sequential algorithms. Beyond Discrete Time Markov Chains. Matrix-vector product is also in the core of model checking continuous-time Markov chains, i.e., the corresponding Computational Stochastic Logic (CSL) [29,3,11]. For instance, the next operator of CSL can be checked with in the same way like its PCTL counterpart. Both algorithms for steady state and transient probabilities boil down to matrix-vector multiplication. On this operation hinge also various extensions of CSL with costs. Thus, the parallel version of the Jacobi algorithm that we present in the sequel, can be used also for stochastic models, i.e., models based on CTMCs.

3

GPU Programming

A considerable part of the challenges that arise in model checking algorithms for GPUs is due to the specific architectural differences between GPUs and CPUs and the restrictions on the programs that can run on GPUs. Therefore, before describing our approach in more detail, we give an overview of the GPU architecture and the Compute Unified Device Architecture (CUDA) programming model by the manufacturer NVIDIA [14] along the lines of [10].

38

D. Boˇsnaˇcki, S. Edelkamp, and D. Sulewski

Modern GPUs are no longer dedicated only to graphics applications. Instead a GPU can be seen as a general purpose multi-threaded massively data parallel co-processor. Harnessing the power of GPUs is facilitated by the new APIs for general computation on GPUs. CUDA is an interface by NVIDIA which is used to program GPUs. CUDA programs are basically extended C programs. To this end CUDA features extensions like: special declarations to explicitly place variables in some of the memories (e.g., shared, global, local), predefined keywords (variables) containing the block and thread IDs, synchronization statements for cooperation between threads, runtime API for memory management (allocation, deallocation), and statements to launch functions on GPU. CUDA Programming Model. A CUDA program consists of a host program which runs on the CPU and a set of CUDA kernels. The kernels, which are the parallel parts of the program, are launched on the GPU device from the host program, which comprises the sequential parts. The CUDA kernel is a parallel kernel that is executed on a set of threads. Each thread of the kernel executes the same code. Threads of a kernel are grouped in blocks that form a grid. Each thread block of the grid is uniquely identified by its block ID and analogously each thread is uniquely identified by its thread ID within its block. The dimensions of the thread and the thread block are specified at the time of launching the kernel. The grid can be one- or two-dimensional and the blocks are at most three-dimensional. CUDA Memory Model. Threads have access to different kind of memories. Each thread has its own on-chip registers and off-cheap local memory, which is quite slow. Threads within a block cooperate via shared memory which is oncheap and very fast. If more than one block are executed in parallel then the shared memory is equally split between them. All blocks have access to the device memory which is large (up to 4GB), but slow since, like the local memory, it is not cached. The host has read and write access to the global memory (Video RAM, or VRAM), but cannot access the other memories (registers, local, shared). Thus, as such, global memory is used for communication between the host and the kernel. Besides the memory communication, threads within a block can cooperate via light-weight synchronization barriers. GPU Architecture. The architecture of GPU features a set of multiprocessors units called streaming multiprocessors (SMs). Each of those contains a set of processor cores called streaming processors (SPs). The NVIDIA GeForce GTX280 has 30 SMs each consisting of 8 SPs, which gives in total 240 SPs. CUDA Excution Model. Each block is mapped to one multiprocessor whereas each multiprocessor can execute several blocks. The logical kernel architecture allows flexibility to the GPU to schedule the blocks of the kernel depending of the concrete hardware architecture in an optimal and for the user completely transparent way. Each multiprocessor performs computations in SIMT (Single Instruction

Efficient Probabilistic Model Checking on GPGP

39

Multiple Threads) manner, which means that each thread is executed independently with its own instruction address and local state (registers and local memory). Threads are executed by the SPs and thread blocks are executed on the SMs. Each block is assigned to the same processor throughout the execution, i.e., it does not migrate. The number of blocks that can be physically executed in parallel on the same multiprocessor is limited by the number of registers and the amount of shared memory. Only one kernel at a time is executed per GPU. GPU Programming Challenges. To fully exploit the computational power of the GPUs some significant challenges will have to be addressed. The main performance bottleneck is usually the relatively slow communication (compared to the enormous peak computational power) with the off-chip device memory. To fully exploit the capacity of the GPU parallelism this memory latency must be minimized. Further, it is recommended to avoid synchronization between thread blocks. The inter-thread communication within a block is cheap via the fast shared memory, but the accesses to the global and local memories are more than hundred times slower. Another way to maximize the parallelism is by optimizing the thread mapping. Unlike the CPU threads, the GPU threads are very light-weight with negligible overhead of creation and switching. This allows GPUs to use thousands of threads whereas multi-core CPUs use only a few. Usually more threads and blocks are created than the number of SPs and SMs, respectively, which allows GPU to maximally use the capacity via smart scheduling - while some threads/blocks are waiting for data, the others which have their data ready are assigned for execution. Thread mapping is coupled with the memory optimization in the sense that threads that access physically close memory locations should be grouped together.

4

Matrix-Vector Multiplication on GPU

To speed up the algorithms we replace the sequential matrix-vector multiplication algorithm with a parallel one, which is adapted to run on GPU. In this section we describe our parallel algorithms which are derived from the Jacobi algorithm for matrix-vector multiplication. This algorithm was used for both bounded and unbounded until, i.e., also for solving systems of linear equations. Jacobi Iterations. As mentioned in Section 2 for model checking DTMCs, Jacobi iteration method is one option to solve the set of linear equations we have derived for until (U). Each iteration in the Jacobi algorithm involves a matrixvector multiplication. Let n be the size of the state space, which determines the dimension n × n of the matrix to be iterated. The formula of Jacobi for solving Ax = b iteratively for an n × n matrix A = (aij )0≤i,j≤n−1 and a current vector xk is ⎛ ⎞  xk+1 = 1/aii · ⎝bi − aij xki ⎠ , for i ∈ {0, . . . , n − 1}. i j=i

40

D. Boˇsnaˇcki, S. Edelkamp, and D. Sulewski

For better readability (and faster implementation), we may extract the diagonal elements and invert them prior to applying the formula. Setting Di = 1/aii , i ∈ {0, . . . , n − 1} then yields ⎛ ⎞  xk+1 = Di · ⎝ b i − aij xki ⎠ , for i ∈ {0, . . . , n − 1}. i j=i

The sufficient condition for Jacobi iteration to converge is that the magnitude of the largest eigenvalue (spectral radius) of matrix D−1 (A−D) is bounded by value 1. Fortunately, the Perron–Frobenius theorem asserts that the largest eigenvalue of a (strictly positive) stochastic matrix is equal to 1 and all other eigenvalues are smaller than 1, so that limk→∞ Ak exists. In the worst case, the number of iterations can be exponential in the size of the state space but in practice the number of iteration k until conversion to some sufficiently small  according to a termination criteria, like maxi |xki − xk+1 | < , is often moderate [34]. i Sparse Matrix Representation. The size of the matrix is Θ(n2 ), but for sparse models that usually appear in practice it can be compressed. Such matrix compaction is a standard technique used for probabilistic model checking and to this end special structures are used. In the algorithms that we present in the sequel we assume the so called modified compressed sparse row/column format [11]. We illustrate this format on the sparse transition probability matrix P given below: row col non-zero

0 0 0 1 1 2 2 2 3 4 4 1 2 4 2 3 0 3 4 0 0 2 0.2 0.7 0.1 0.01 0.99 0.3 0.58 0.12 1.0 0.5 0.5

The above matrix contains only the non-zero elements of P. The arrays labeled row, col, and non-zero contain the row and column indices, and the values of the non-zero elements, respectively. More formally, for all r of the index range of the arrays, non-zeror = P(rowr , colr ). Obviously, this is already an optimized format compared to the standard full matrix representation. Still, one can save even more space as shown in the table below, which is, in fact, the above mentioned modified compressed sparse row/column format :

rsize col non-zero

3 2 3 1 2 1 2 4 2 3 0 3 4 0 0 2 0.2 0.7 0.1 0.01 0.99 0.3 0.58 0.12 1.0 0.5 0.5

The difference with the previous representation is only in the top array rsize. Instead of the row indices, this array contains the row sizes, i.e., rsizei contains

Efficient Probabilistic Model Checking on GPGP

41

the number of non-zero elements in row i of P. To extract row i of the original matrix P, we take the elements non-zerorstarti , non-zerorstarti +1 , . . . , non-zerorstarti +rsizei −1 i−1 where rstarti = k=0 rsizek . Algorithm Implementation. The pseudo code of the sequential Jacobi algorithm that implements the aforementioned recurrent formula and which uses the compression given above is shown in Algorithm 1.. Algorithm 1. Jacobi iteration with row compression, as implemented in PRISM 1: k := 0 2: Terminate := f alse 3: while (not Terminate and k < maxk ) do 4: h := 0; 5: for all i := 0 . . . n do 6: d := bi ; 7: l := h; 8: h := l + rsizei − 1; 9: for all j = l . . . h do  10: d = d − non-zeroj · xkcol ; j 11: d := d · Di ; k+1 12: xi := d; 13: Terminate := true 14: for all i := 0 . . . n do 15: if |xk+1 − xki | >
then i 16: Terminate := f alse 17: k := k + 1;

The iterations are repeated until a satisfactory precision is achieved or the maximal number of iterations maxk is overstepped. In lines 6–8 (an element of) vector b is copied into the auxiliary variable d and the lower and upper bounds for the indices of the elements in array non-zero that correspond to row i are computed. In the for loop the product of row i and the result of the previous iteration, vector xk , is computed. The new result is recorded in variable xk+1 . Note that, since we are not interested in the intermediate results, only two vectors are needed: one, x, to store xk , and another, x , that corresponds to xk+1 , the result of the current iteration. After each iteration the contents of x and x are swapped, to reflect the status of x , which becomes the result of the previous iteration. We will use this observation to save space in the parallel implementation of the algorithm given below. In lines 13–16 the termination condition is computed, i.e., it is checked if sufficient precision is achieved. We assume that vector x is initialized appropriately before the algorithm is started.

42

D. Boˇsnaˇcki, S. Edelkamp, and D. Sulewski

Due to the fact that the iterations have to be performed sequentially the matrix-vector multiplication is the part to be distributed. As a feature of the algorithm (that contributed most to the speedup) the comparison of the two solution vectors, x and x in this case, is done in parallel. The GPU version of the Jacobi algorithm is given in Algorithms 2. and 3..

Algorithm 2. JacobiCPU: CPU part of the Jacobi iteration, for unbounded until computation 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15:

allocate global memory for x’ allocate global memory for col, non-zero, b, x,
, n and copy them allocate global memory for TerminateGPU to be shared between blocks rstart 0 := 0; for i = 1 . . . |rsize| + 1 do rstart i := rstarti−1 + rsizei−1 ; allocate global memory for rstartGPU and copy rstart to rstartGPU k := 0 Terminate := f alse while (not Terminate and k < maxk ) do <<>>JacobiKernel(); copy TerminateGPU to Terminate; Swap(x,x’) k = k + 1; copy x’ to RAM;

Algorithm 2., running on the CPU, copies vectors non-zero and col from the matrix representation, together with vectors x and b, and constants  and n, to the global memory (VRAM) and allocates space for the vector x . Having done this, space for the Terminate variable is allocated in the VRAM. Variable rstart defines the starting point of a row in the matrix array. The conversion from rsize to rstart is needed to let each thread find the starting point of a row immediately. (In fact, implicitely we use a new matrix representatin where rsize is replaced with rstart.) Array rstart is copied to the global memory variable rstartGPU. To specify the number of blocks and the size of a block CUDA supports additional parameters in front of the kernel (<<< number of blocks, block size >>>). Here the grid is defined with n/BlockSize + 1 blocks2 , and a fixed BlockSize. After the multiplication and comparison step on the GPU the Terminate variable is copied back and checked. This copy statement serves also as a synchronization barrier, since the CPU program waits until all the threads of the GPU kernel have terminated before copying the variable from the GPU global memory. If another iteration is needed x and x are swapped3 . After all iterations the result is copied back from global memory to RAM. 2 3

If BlockSize is a divisor of n threads in the last block execute only the first line of the kernel. Since C operates on pointers, only these are swapped in this step.

Efficient Probabilistic Model Checking on GPGP

43

Algorithm 3. JacobiKernel: Jacobi iteration with row compression on the GPU 1: i := BlockId · BlockSize + T hreadId; 2: if (i = 0) then 3: TerminateGPU := true; 4: if (i < n) then 5: d := bi ; 6: l := rstartGPU i ; 7: h := rstartGPU i+1 − 1; 8: for all j = l . . . h do 9: d := d − non-zeroj · xcolj ; 10: d := d · Di ; 11: x
i := d; 12: if |xi − x
i | >
then 13: TerminateGPU := f alse

JacobiKernel shown in Algorithm 3. is the so-called kernel that operates on the GPU. Local variables d, l, h, i and j are located in the local registers and they are not shared between threads. The other variables reside in the global memory. The result is first computed in d (locally in each thread) and then written to the global memory (line 11). This approach minimizes the access to the global memory from threads. At invocation time each thread computes the row i of the matrix that it will handle. This is feasible because each thread knows its ThreadId, and the BlockId of its block. Note that the size of the block (BlockSize) is also available to each thread. Based on value i only one thread (the first one in the first block) sets the variable TerminateGPU to true. Recall, this variable is located in the global memory, and it is shared between all threads in all blocks. Now, each thread reads three values from the global memory (line 5 to 7), here we profit from coalescing done by the GPU memory controller. It is able to detect neighboring VRAM access and combine it. This means, if thread i accesses 2 bytes at bi and thread i + 1 accesses 2 bytes at bi+1 the controller fetches 4 bytes at bi and divides the data to serve each thread its chunk. In each iteration of the for loop an elementary multiplication is done. Due to the compressed matrix representation a double indirect access is needed here. As in the original algorithm the result is multiplied with the diagonal value Di and stored in the new solution vector x . Finally, each thread checks if another iteration is needed and consequently sets the variable TerminateGPU to false. Concurrent writes are resolved by the GPU memory controller. The implementation in Algorithm 2. matches the one for bounded-until (U≤k ), except that bounded-until has a fixed upper bound on the number of iterations, while for until a termination criterion applies.

5

Experiments

All experiments were done on a PC with an AMD Athlon(tm) 64 X2 Dual Core Processor 3800+ with 4 GB of RAM; the operating system is 64-bit SUSE 11 with

44

D. Boˇsnaˇcki, S. Edelkamp, and D. Sulewski Table 1. Results for the herman protocol instance herman15.pm herman17.pm

n 32,768 131,072

iterations 245 308

seq. time 22.430 304.108

par. time speedup 21.495 1.04 206.174 1.48

CUDA 2.1 SDK and the NVIDIA driver version 177.13. This system includes a MSI N280GTX T20G graphic card with 1 GB global memory plugged into an ExpressPCI slot. The GTX200 chip on this card contains 10 texture processing clusters (TPC). Each TPC consists of 3 streaming multiprocessors (SM) and each SM includes 8 streaming processors (SPs) and 1 double precision unit. In total, it has 240 SPs executing the threads in parallel. Maximum block size for this GPU is 512. Given a grid, the TPCs divide the blocks on its SMs, and each SM controls at most 1024 threads, which are run on the 8 SPs. We verified three protocols, herman, cluster, and tandem, shipped with the source of PRISM. The protocols were chosen due to their scalability and the possibility to verify its properties by solving a linear function with the Jacobi method. Different protocols show different speedups achieved by the GPU, because the Jacobi iterations are only a part of the model checking algorithms, while the results show the time for the complete run. In all tables of this section n denotes the number of rows (columns) of the matrix, “iterations” denotes the number of iterations of the Jacobi method, “seq. time” and “par. time” denote the runtimes of the standard (sequential) version of PRISM and our parallel implementation extension of the tool, respectively. All times are given in seconds. The speedup is computed as the quotient between the sequential and parallel runtimes. The first protocol called herman is the Herman’s self-stabilizing algorithm [22]. The protocol operates synchronously on an oriented ring topology, i.e., the communication is unidirectional. The number in the file name denotes the number of processes in the ring, which must be odd. The underlying model is a DTMC. We verified the PCTL property 3 from the property file herman.pctl (R=? [ F "stable" {"k_tokens"}{max} ]). Table 1 shows the results of the verification. Even though the number of iterations is rather small compared to the other models, the GPU achieves a speedup factor of approx. 1.5. Since everything beyond multiplication of the matrix and vector is done on the CPU, we have not expected a larger speedup. Unfortunately, it is not possible to scale up this model, due to the memory consumption being too high; the next possible instance (herman19.pm) consumes more then 1 GB. The second case study is cluster [21] which models communication within a cluster of workstations. The system comprises two sub-clusters with N workstations in each of them, connected in a star topology. The switches connecting each sub-cluster are joined by a central backbone. All components can break down and there is a single repair unit to service all components. The underlying model is CTMC and the checked CSL property is property 1 from the corresponding property file (S=? [ "premium" ]). Fig. 1 shows that GPU performs significantly better, Table 2 contains some exact numbers for chosen instances.

Efficient Probabilistic Model Checking on GPGP

45 10

CPU GPU speedup 8

15000 6

10000 4

5000

speedup (CPU time / GPU time)

seconds to complete the model checking process

20000

2

0 0

100

200

300

400

500

0 600

choosen constant N

Fig. 1. Verification times for several instances of the cluster protocol. The x-axis shows the value of the parameter N . Speedup is computed as described in the text as a quotient between the runtime of standard PRISM and the runtime of our GPU extension of the tool. Table 2. Results for the cluster protocol. Parameter N is used to scale the protocol. The global memory usage (denoted as GPU mem) is in MB. N 122 230 320 410 446 464 500 572

n iterations 542,676 1,077 1,917,300 2,724 3,704,340 5,107 6,074,580 11,488 7,185,972 18,907 7,776,660 23,932 9,028,020 28,123 11,810,676 28,437

seq. time 31.469 260.440 931.515 3,339.307 6,440.959 8,739.750 11,516.716 15,576.977

par. time GPU mem speedup 8.855 21 3.55 54.817 76 4.75 165.179 146 5.63 445.297 240 7.49 767.835 284 8.38 952.817 308 9.17 1,458.609 694 7.89 1,976.576 908 7.88

The largest speedup reaches a factor of more then 9. Even for smaller instances, the GPU exceeds factor 3. In this case study a sparser matrix was generated, which in turn needed more iterations to converge then the herman protocol. In the largest instance (N = 572) checked by the GPU, PRISM generates a matrix with 11,810,676 lines and iterates this matrix 28,437 times. It was even necessary to increase the maximum number of iterations, set by default to 10,000, to obtain a solution. In this protocol, as well as in the next one, for large matrices

46

D. Boˇsnaˇcki, S. Edelkamp, and D. Sulewski

Table 3. Results from the verification of the tandem protocol. The constant c is used to scale the protocol. Global memory usage, shown as GPU mem, is given in MB (o.o.m denotes out of global memory). c 255 511 1,023 2,047 3,070 3,588 4,095

n 130,816 523,776 2,096,128 8,386,560 18,859,011 25,758,253 33,550,336

iterations 4,212 8,498 16,326 24,141 31,209 34,638 37,931

seq. time par. time GPU mem speedup 26.994 3.639 4 7.4 190.266 17.807 17 10.7 1,360.588 103.154 71 13.2 9,672.194 516.334 287 18.7 25,960.397 1,502.856 647 17.3 33,820.212 2,435.415 884 13.9 76,311.598 o.o.m

1000 dual precision CPU single precision GPU dual precision GPU

miliseconds per iteration

100

10

1

0.1

0.01 0

500

1000

1500

2000

2500

3000

3500

4000

4500

const c

Fig. 2. Time per iteration in the tandem protocol. The CPU is significantly slower then the GPU operating in single or double precision. Reducing the precision has nearly no effect on the speed.

we observed a slight deterioration of the performance of the GPU implementation for which, for the time being, we could not find a clear explanation. One plausible hypothesis would be that after some threshold number of threads GPU cannot profit any more from smart scheduling to hide the memory latencies. The third case study tandem is based on a simple tandem queueing network [HMKS99]. The model is represented as a CTMC which consists of a M/Cox(2)/1queue sequentially composed with a M/M/1-queue. We use c to denote the capacity of the queues. We verified property 1 from the corresponding CSL property file

Efficient Probabilistic Model Checking on GPGP

47

(R=? [ S ]). Constant T was set to 1 for all experiments and parameter c was scaled as shown in Table 3. In this protocol the best speedup was recorded. For the best instance (c = 2047) PRISM generates a matrix with 8,386,560 rows, which is iterated 24,141 times. For this operation standard PRISM needs 9, 672 seconds while our parallel implementation only needs 516 seconds, scoring a maximal speedup of a factor 18.7. As mentioned above, 8 SPs share one double precision unit, but each SP has an own single precision unit. Hence, our hypothesis was that reducing the precision from single to double should bring a significant speedup. The code of PRISM was modified to support single precision floats for examining the effect. As can be seen in Fig. 2 the hypothesis was wrong. The time per iteration in double precision mode is nearly the same as the single precision mode. The graph clearly shows that the GPU is able to hide the latency which occurs when a thread is waiting for the double precision unit by letting the SPs work on other threads. Nevertheless, it is important to note that the GPU with single precision arithmetic was able to verify larger instances of the protocol, given that the floating point numbers consumed less memory. It should be noted that in all cases studies we also tried the MTBDD and hybrid representations of the models, which are an option in PRISM, but in all cases the runtimes were consistently slower than the ones with the sparse matrix representation, which are shown in the tables.

6

Conclusions

In this paper we introduced GPU probabilistic/stochastic model checking as a novel concept. To this end we described a parallel version of Jacobi’s method for sparse matrix-vector multiplication, which is the main core of the algorithms for model checking discrete- and continuous-time Markov chains, i.e., the corresponding logics PCTL and CSL. The algorithm was implemented on top of the probabilistic model checker PRISM. Its efficiency and the advantages of the GPU probabilistic model checking in general were illustrated on several case studies. Speedups of up to 18 times compared to the sequential implementation of PRISM were achieved. We believe that our work opens a very promising research avenue on GPU model checking in general. To stay relevant for the industry, the area has to keep pace with the new technological trends. “Model checking for masses” gets tremendous opportunities because of the “parallelism for masses”. To this end model checking algorithms that are designed for the verification of parallel systems and exploit the full power of the new parallel hardware will be needed. In the future we intend to experiment with other matrix-vector algorithms for GPUs, as well as with combination of multi-core and/or multi-GPU systems. What is needed for analyzing the time complexity of GPU algorithms is a fine grained theoretical model of its operation.

48

D. Boˇsnaˇcki, S. Edelkamp, and D. Sulewski

References 1. Allmaier, S.C., Kowarschik, M., Horton, G.: State Space Construction and Steadystate Solution of GSPNs on a Shared-Memory Multiprocessor. In: Proc. 7th Int. Workshop on Petri Nets and Peformance Models (PNPM 1997), pp. 112–121. IEEE Comp. Soc. Press, Los Alamitos (1997) 2. Baier, C., Katoen, J.-P.: Principles of Model Checking, p. 950. MIT Press, Cambridge (2008) 3. Baier, C., Katoen, J.-P., Hermanns, H., Haverkort, B.: Model-Checking Algorithms for Contiuous-Time Markov Chains. IEEE Transactions on Software Engineering 29(6), 524–541 (2003) 4. Bal, H., Barnat, J., Brim, L., Verstoep, K.: Efficient Large-Scale Model Checking. In: IEEE International Parallel & Distributed Processing Symposium (IPDPS) (to appear, 2009) 5. Barnat, J., Brim, L., Roˇckai, P.: Scalable Multi-core Model-Checking. In: Boˇsnaˇcki, D., Edelkamp, S. (eds.) SPIN 2007. LNCS, vol. 4595, pp. 187–203. Springer, Heidelberg (2007) ˇ 6. Barnat, J., Brim, L., Cern´ a, I., Ceska, M., Tumova, J.: ProbDiVinE-MC: Multicore LTL Model Checker for Probabilistic Systems. In: International Conference on the Quantitative Evaluaiton of Systems QEST 2008, pp. 77–78. IEEE Compuer Society Press, Los Alamitos (2008) ˇ 7. Barnat, J., Brim, L., Simeˇ cek, P.: I/O efficient accepting cycle detection. In: Damm, W., Hermanns, H. (eds.) CAV 2007. LNCS, vol. 4590, pp. 281–293. Springer, Heidelberg (2007) 8. Barnat, J., Brim, L., Str´ıbrn´ a, J.: Distributed LTL Model Checking in SPIN. In: Dwyer, M.B. (ed.) SPIN 2001. LNCS, vol. 2057, pp. 200–216. Springer, Heidelberg (2001) ˇ 9. Barnat, J., Brim, L., Simeˇ cek, P., Weber, M.: Revisiting resistance speeds up I/Oefficient LTL model checking. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 48–62. Springer, Heidelberg (2008) 10. Baskaran, M.M., Bordawekar, R.: Optimzing Sparse Matrix-Vector Multiplication on GPUs Using Compile-time and Run-time Strategies, IBM Reserach Report, RC24704, W0812-047 (2008) 11. Bell, A., Haverkort, B.R.: Distribute Disk-based Algorithms for Model Checking Very Large Markov Chains. In: Formal Methods in System Design, vol. 29, pp. 177–196. Springer, Heidelberg (2006) 12. Ciardo, G.: Distributed and Structured Analysis Approaches to Study Large and Complex Systems. European Educational Forum: School on Formal Methods and Performance Analysis 2000, 344–374 (2000) 13. Dai, P., Mausam, Weld, D.S.: External Memory Value Iteration. In: Proc. of the Twenty-Third AAAI Conf. on Artificial Intelligence (AAAI), pp. 898–904 (2008) 14. http://www.nvidia.com/object/cuda_home.html# 15. Edelkamp, S., Sulewski, D.: Model Checking via Delayed Duplicate Detection on the GPU, Technical Report 821, Universit¨ at Dortmund, Fachberich Informatik, ISSN 0933-6192 (2008) 16. Edelkamp, S., Jabbar, S.: Large-scale directed model checking LTL. In: Valmari, A. (ed.) SPIN 2006. LNCS, vol. 3925, pp. 1–18. Springer, Heidelberg (2006) 17. Edelkamp, S., Jabbar, S., Bonet, B.: External Memory Value Iteration. In: Proc. 17th Int. Conf. on Automated Planning and Scheduling, pp. 128–135. AAAI Press, Menlo Park (2007)

Efficient Probabilistic Model Checking on GPGP

49

ˇ 18. Edelkamp, S., Sanders, P., Simeˇ cek, P.: Semi-external LTL model checking. In: Gupta, A., Malik, S. (eds.) CAV 2008. LNCS, vol. 5123, pp. 530–542. Springer, Heidelberg (2008) 19. Edelkamp, S., Sulewski, D.: Flash-efficient LTL model checking with minimal counterexamples. In: Software Engineering and Formal Methods, pp. 73–82 (2008) 20. Hansson, H., Jonsson, B.: A Logic for reasoning about time and reliability. Formal Aspects of Computing 6(5), 512–535 (1994) 21. Haverkort, B., Hermanns, H., Katoen, J.-P.: On the Use of Model Checking Techniques for Dependability Evaluation. In: Proc. 19th IEEE Symposium on Reliable Distributed Systems (SRDS 2000), pp. 228–237 (2000) 22. Herman, T.: Probabilistic Self-stabilization. Information Processing Letters 35(2), 63–67 (1990) 23. Hermanns, H., Meyer-Kayser, J., Siegle, M.: Multi Terminal Binary Decision Diagrams to Represent and Analyse Continuous Time Markov Chains. In: Proc. 3rd International Workshop on Numerical Solution of Markov Chains (NSMC 1999), pp. 188–207 (1999) 24. Holzmann, G.J., Boˇsnaˇcki, D.: The Design of a multi-core extension of the Spin Model Checker. IEEE Trans. on Software Engineering 33(10), 659–674 (2007); (first presented at: Formal Methods in Computer Aided Design (FMCAD), San Jose (November 2006)) 25. Holzmann, G.J., Boˇsnaˇcki, D.: Multi-core Model Checking with Spin. In: Proc. Parallel and Distributed Processing Symposium, IPDPS 2007, IEEE International, pp. 1–8 (2007) 26. Inggs, C.P., Barringer, H.: CTL∗ Model Checking on a Shared Memory Architecture. Electronic Notes in Theoretical Computer Science 128(4), 107–123 (2005) 27. Inggs, C.P., Barringer, H.: Effective State Exploration for Model Checking on a Shared Memory Architecture. Electronic Notes in Theoretical Computer Science 68(4) (2002) 28. Kwiatkowska, M.Z., Norman, G., Parker, D.: PRISM: Probabilistic Symbolic Model Checker. In: Field, T., Harrison, P.G., Bradley, J., Harder, U. (eds.) TOOLS 2002. LNCS, vol. 2324, pp. 200–204. Springer, Heidelberg (2002) 29. Kwiatkowska, M., Norman, G., Parker, D.: Stochastic Model Checking. In: Bernardo, M., Hillston, J. (eds.) SFM 2007. LNCS, vol. 4486, pp. 220–270. Springer, Heidelberg (2007) 30. Lerda, F., Sisto, R.: Distributed Model Checking in SPIN. In: Dams, D.R., Gerth, R., Leue, S., Massink, M. (eds.) SPIN 1999. LNCS, vol. 1680, pp. 22–39. Springer, Heidelberg (1999) 31. Marowka, A.: Parallel Computing on Any Desktop. Comm. of the ACM 50(9), 75–78 (2007) 32. Philips, J.C., Braun, R., Wang, W., Gumbart, J., Tajkhorshid, E., Villa, E., Chipot, C., Skeel, R.D., Kale, L., Sculten, K.: Scalable Molecular Dynamics with NAMD. Journal of Computational Chemistry 26, 1781–1802 (2005) 33. Stern, U., Dill, D.: Parallelizing the Murφ Verifier. In: Grumberg, O. (ed.) CAV 1997. LNCS, vol. 1254, pp. 256–278. Springer, Heidelberg (1997) 34. Stewart, W.J.: Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton (1994) 35. Valmari, A.: The State Explosion Problem. In: Reisig, W., Rozenberg, G. (eds.) APN 1998. LNCS, vol. 1491, pp. 429–528. Springer, Heidelberg (1998)

Improving Non-Progress Cycle Checks David Farag´o
and Peter H. Schmitt Universit¨ at Karlsruhe (TH), Institut f¨ ur Theoretische Informatik Logik und Formale Methoden {farago,pschmitt}@ira.uka.de

Abstract. This paper introduces a new model checking algorithm that searches for non-progress cycles, used mainly to check for livelocks. The algorithm performs an incremental depth-first search, i.e., it searches through the graph incrementally deeper. It simultaneously constructs the state space and searches for non-progress cycles. The algorithm is expected to be more efficient than the method the model checker SPIN currently uses, and finds shortest (w.r.t. progress) counterexamples. Its only downside is the need for a subsequent reachability depth-first search (which is not the bottleneck) for constructing a full counterexample. The new algorithm is better combinable with partial order reduction than SPIN’s method. Keywords: Model Checking, SPIN, Non-progress cycles, livelocks, depthfirst search, partial order reduction.

1

Introduction

In Section 1.1, we describe what non-progress cycles (NPCs) are and how SPIN currently searches for them. Section 1.2 presents SPIN’s method in more detail and reveals its redundant operation. Hence we apply a new idea (see Section 2.1) to design two new algorithms, the incremental DFS and DFSFIFO , see Section 2.2. We prove the correctness of DFSFIFO in Section 2.3. Section 2.4 shows that DFSFIFO has several advantages over SPIN’s method. The section ends by depicting the high relevance of partial order reduction. After describing how this reduction works (see Section 3.1), we show that its usage by DFSFIFO is correct (see Section 3.2) and yields many further advantages (see Section 3.3). The paper closes with a conclusion and future work. The main contributions of this paper are DFSFIFO and the theoretical basis for its upcoming implementation. 1.1

Non-Progress Cycle Checks by SPIN

NPC checks are mainly used to detect livelocks in the system being modeled, i.e., execution cycles that never make effective progress. NPC checks are often performed in formal verifications of protocols, where livelocks frequently occur.


This research received financial support by the Concept for the Future of KIT within the framework of the German Excellence Initiative from DFG.

C.S. P˘ as˘ areanu (Ed.): SPIN 2009, LNCS 5578, pp. 50–67, 2009. c Springer-Verlag Berlin Heidelberg 2009


Improving Non-Progress Cycle Checks

51

Using SPIN, livelocks were found, for instance, in the i-protocol from UUCP (see [3]) and GIOP from CORBA (see [10]), whereas DHCP was proved to be free of livelocks (see [9]). To be able to check for NPCs, desired activities of the system are marked in PROMELA by labeling the corresponding location in the process specification with a progress label: ”statementi ; progress: statementj ;”. This sets the local state between statementi and statementj to a local progress state (cf. Figure 7). A (global) progress state is a global system state in which at least one of the processes is in a local progress state. SPIN marks global progress states by setting the global variable np to false. Section 2.4 presents progress transitions as alternative for modeling progress. If no cycle without any progress-label exists, then the system definitely makes progress eventually (it never gets stuck in a livelock). A non-progress cycle check detects (and returns a path to) a reachable nonprogress cycle, i.e., a reachable cycle with no progress states, iff there exists one in the state transition system (S, T ) (with S being the set of states and T ⊆ S×S the set of transitions). SPIN puts the check into effect with the B¨ uchi automaton for the LTL formula ♦  np , which translates into the never claim of Listing 1 (cf. [6]). never { /∗ <>[] np ∗/ do /∗ n o n d e t e r m i n i s t i c a l l y d e l a y or swap t o NPC s e a r c h mode∗/ : : np −> break : : true /∗ n o n d e t e r m i n i s t i c d e l a y mode∗/ od ; a c c e p t : /∗NPC s e a r c h mode∗/ do : : np od } Listing 1. Never claim for NPC checks

The LTL formula is verified with SPIN’s standard acceptance cycle check , the nested depth-first search (NDFS ) algorithm (see [8,6]): Before the basic depthfirst search (DFS ) backtracks from an accepting state s and removes it from the stack, a second, nested DFS is started to check whether s can reach itself, thus resulting in an acceptance cycle. Pseudo-code for the nested DFS is given in Listing 2. 1.2

Motivation for Improving Non-Progress Cycle Checks

The following walkthrough depicts a detailed NPC check in SPIN (cf. Figure 1): 1. When traversal starts at init, the never claim immediately swaps to its NPC search mode because the never claim process firstly chooses np −> break in the first do-loop (if the order in this do-loop were swapped, the NPC check would descend the graph as deeply as possible in the nondeterministic

52

D. Farag´ o and P.H. Schmitt

proc DFS( s t a t e s ) i f e r r o r ( s ) then r e p o r t e r r o r f i ; add {s , 0 } t o hash t a b l e ; push s onto s t a c k ; f o r each s u c c e s s o r t o f s do i f {t , 0 }  ∈ hash t a b l e then DFS( t ) f i od ; i f a c c e p t i n g ( s ) then NDFS( s ) f i ; pop s from s t a c k ; end proc NDFS( s t a t e s ) /∗ t h e n e s t e d s e a r c h ∗/ add {s , 1 } t o hash t a b l e ; f o r each s u c c e s s o r t o f s do i f {t , 1 }  ∈ hash t a b l e then NDFS( t ) e l s e i f t ∈ s t a c k then r e p o r t c y c l e f i fi od ; end Listing 2. Nested DFS

delay mode). Hence a DFS is performed in which all states are marked as acceptance states by the never claim and progress states are omitted, i.e., truncated (see Listing 1). 2. Just before backtracking from each state being traversed in the NPC search mode DFS, the NDFS (i.e., the nested search) starts an acceptance cycle search (since all traversed states were marked as acceptance states). For these acceptance cycle searches, the non-progress states are traversed again. 3. If an acceptance cycle is found, it is also an NPC since only non-progress states are traversed. If no acceptance cycle is found, the NDFS backtracks from the state s where the NDFS was initiated, but immediately starts a new NDFS before the NPC search mode DFS backtracks from the predecessor of s. Fortunately, states that have already been visited by an NDFS are not revisited. But the NDFS is repeatedly started many times and at least one transition has to be considered each time. Eventually, when the NDFS has been performed for all states of the NPC search mode DFS, the NPC search mode DFS backtracks to init. 4. Now the nondeterministic delay mode DFS constructs the state space once more. During this, after each forward step, all previous procedures are repeated. Since most of the time the states have already been visited, these procedures are immediately aborted. During this nondeterministic delay mode DFS, also progress states are traversed. On the whole, the original state space (i.e., without the never claim) is traversed three times: in the NPC search mode DFS, in the NDFS and in the

Improving Non-Progress Cycle Checks

53

repeated in the nondet. delay mode for each state s

repetitive NDFSs NPC search mode Fig. 1. Walkthrough of SPIN’s NPC check

nondeterministic delay mode DFS. The state space construction for reaching an NPC and the NPC search are performed in separate steps.

2

Better NPC Checks

In this section, we firstly introduce our new approach and then our new algorithms: the incremental DFS and its improvement DFSFIFO . Thereafter, the correctness of DFSFIFO is proved. Finally, it is compared to SPIN’s method of NPC checks. 2.1

Approach

The detailed walkthrough in Section 1.2 has shown that SPIN’s NPC check unnecessarily often initializes procedures, touches transitions, and traverses the state space. The cause for this inefficiency is the general approach: acceptance cycle checks in combination with never claims are very powerful and cover more eventualities and options than necessary for NPC checks. So we are looking for a more specific algorithm for NPC checks that performs less redundantly and combines the construction and the NPC search phase. But with only one traversal of the state space, we have to cope with the following problem: Simply checking for each cycle found in a basic DFS whether it makes progress is an incomplete NPC search since the DFS aborts traversal in states which have already been visited. Hence not all cycles are traversed. Figure 2 shows an example of an NPC that is not traversed and therefore not found by the DFS: From s1 , the DFS first traverses path 1, which contains a progress state s2 . After backtracking from path 1 to s1 , the DFS traverses path 2, but aborts it at s3 before closing the (red, thick) NPC. Hence if an NPC has states that have already been visited, the cycle will not be found by the basic DFS. The idea for our alternative NPC checks is to guarantee that: After reaching an NPC for the first time, traversal (p-stop) of progress states is postponed as long as possible.

54

D. Farag´ o and P.H. Schmitt

s1 path1 s+

2

path 2

s3 Fig. 2. Not traversed NPC

This constraint enforces that NPCs are traversed before states from the NPC are visited through some progress cycle and thus break the NPC traversal. The following section introduces two new algorithms and checks (p-stop) for them. 2.2

The Incremental Depth-First Search Algorithms

Incremental Depth-First Search. This new algorithm searches for NPCs using a depth-first iterative deepening search with incrementally larger thresholds for the number of progress states that may be traversed. For this, the incremental DFS algorithm, described in Listing 3 and 4, repeatedly builds subgraphs GL where paths (starting from init) with maximally L progress states are traversed, for L = 0, 1 . . . , with a basic DFS algorithm. It terminates either with an error path (a counterexample to the absence of NPCs) when an NPC is found or without an error when L becomes big enough for the incremental DFS to build the complete graph G, i.e., GL = G. So in each state s we might prune some of the outgoing transitions by omitting those which exceed the current progress limit L, and only consider the remaining transitions. We can implement DFSstarting over by using a progress counter for the number of progress states on the current path. The progress counter is saved for every state on the stack, but is ignored when states are being compared. This causes an insignificant increase in memory (maximally log(Lmax )×depth(G) bits). With this concept, we can firstly update the progress counter when backtracking, secondly abort traversal when the progress counter exceeds its current limit L, and thirdly quickly check for progress whenever a cycle is found. To complete this implementation, we still have to determine the unsettled functions of DFSprune,NPC , underlined in listing 4: – – – –

pruned(s, t) returns true iff progress counter = L and t is a progress state. pruning action(t) sets DFS pruned to true. np cycle(t) returns true iff progress counter = (counter on stack for t). The error message can print out the stack, which corresponds to the path

from init to the NPC, inclusively.

Improving Non-Progress Cycle Checks

55

proc DFSstarting over ( s t a t e s ) L:=0; repeat DFS pruned := f a l s e ; DFSprune,NPC ( s ) ; L++; u n t i l ( ! DFS pruned ) ; end ; proc main ( ) DFSstarting over ( init ) ; p r i n t f ( ”LTS d o e s not c o n t a i n NPCs” ) ; end ; Listing 3. Incremental depth-first search

Unfortunately, this incremental DFS has several deficiencies: – The upper part of the graph (of the graph’s computation tree) is traversed repeatedly. But since we usually have several transitions leaving a state and relatively few progress states, this makes the incremental DFS require maximally twice the time of one complete basic DFS (i.e., of a safety check). – Depending on the traversal order of the DFS, the progress counter limit might have to become unnecessarily large until an NPC is found, cf. Figure 3. – As main disadvantage, the approach of the incremental DFS is not sufficient to fulfill the condition (p-stop): It can happen that a state s0 on an NPC is reached the first time for progress counter limit L0 (via path 3), but with progress counter(s0 ) < L0 . For this to be the case, path 3 was aborted for L < L0 . Hence for L < L0 , a state s1 on path 3 was already visited from another path (path 2) with more progress, see Figure 3. For L0 , s0 was reached via path 3, and thus path 2 was pruned. Therefore a state s2 on path 2 has already been visited via another path (path 1) for L0 , but not for L < L0 . This situation is depicted in Figure 3, with the traversal order equal to the path number, L0 = 3, progress counter(s0 ) = 2, and + marking progress. Hence we modify the incremental DFS algorithm in the following section. Incremental Depth-First Search with FIFO. Instead of repeatedly increasing the progress counter limit L and re-traversing the upper part of the graph’s computation tree, we save the pruned progress states to jump back to them later on to continue traversal. Roughly speaking, we perform a breadth-first search with respect to the progress states, and in-between progress states we perform DFSs (cf. Listing 5). To reuse the subgraph already built, we have to save some extra information to know which transitions have been pruned. One way to track these pruned transitions is by using a FIFO (or by allowing to push elements under the stack, not only on top). Hence we name the algorithm incremental DFS with FIFO (DFSFIFO ). Listing 5 shows that we do not repeatedly construct the graph from

56

D. Farag´ o and P.H. Schmitt

proc DFSprune,NPC ( s t a t e s ) add s t o hash t a b l e ; push s onto s t a c k ; f o r each s u c c e s s o r t o f s do if (t  ∈ hash t a b l e ) then i f ( ! pruned (s, t ) ) then DFSprune,NPC ( t ) else pruning action (t) fi e l s e i f ( t ∈ s t a c k && n p c y c l e ( t ) ) then h a l t with e r r o r m e s s a g e fi fi od ; pop s from s t a c k ; end ; Listing 4. Generic DFS with pruning and NPC check

init path 2

path 1

+

+ + +

s2

path 3 + +

s1

+

s0

Fig. 3. (p-stop) is not met for the incremental DFS

scratch, but rather use the graph already built, gradually pick the progress states out of the FIFO, and expand the graph further by continuing the basic DFS. When a new progress state is reached, traversal is postponed by putting the state into the FIFO. When the basic DFS is finished and the FIFO is empty, the complete graph G is built. The unsettled functions of DFSprune,NPC are defined for DFSFIFO as follows: – pruned(s, t) returns true iff t is a progress state. – pruning action(t) puts t into the F IF O. – np cycle(t) returns (t != first element of stack), since the first element is a progress state. (Using progress transitions (see Section 2.4), this exception becomes unnecessary and the constant true is returned.) – The error message can print out the stack, which now corresponds to the path of the NPC found, but no longer contains the path from init to the cycle. Note. This algorithm does not know which GL is currently constructed. If we want to clearly separate the different runs, as before, we can use two FIFOs, one for reading and one for writing. When the FIFO that is read from is empty, the current run is finished and we swap the FIFOs for the next run.

Improving Non-Progress Cycle Checks

57

proc DFSFIFO ( s t a t e s) put s i n F IF O ; repeat p i c k f i r s t s out o f F IF O ; DFSprune,NPC ( s ) u n t i l ( F IF O i s empty ) ; end ; proc main ( ) DFSFIFO ( init ) ; p r i n t f ( ”LTS d o e s not c o n t a i n NPCs” ) ; end ; Listing 5. Incremental depth-first search with a FIFO

With this technique, the deficiencies from the original incremental DFS are avoided: (p-stop) is fulfilled since progress state traversal is postponed as long as possible, the progress counter limit L does not become unnecessarily large, and we avoid the redundancy of the original incremental DFS by reusing the part of the graph already built previously. The consequent postponing guarantees a constraint stronger than (p-stop): Each state is visited through a path with the fewest possible progress states. So now GL is the maximal subgraph of G such that all paths in GL without cycles have at most L progress states. On the whole, DFSFIFO does not require more memory by using a FIFO compared to a basic DFS because progress states are stored only temporarily in the FIFO until they are stored in the hash table (cf. Listing 4). The time complexity is also about the same as for the basic DFS. DFSFIFO erases a large part of the stack: everything behind progress states, i.e. all of the stack between init and the last progress state, is lost. But for detecting NPCs, this is a feature and not a bug: Exactly the NPCs are detected. The cycles that go back to states from previous runs are progress cycles and stay undetected. Thus we no longer need to save a progress counter on the truncated stack, saving even more memory. A further benefit will arise in combination with partial order reduction (see Section 3). If an NPC is detected, the stack from the current run supplies the NPC, but an additional basic DFS for reaching the NPC is required to obtain a complete error path as counterexample. The shortest (w.r.t. progress) counterexample can be found quickly, for instance with the following method, which generally requires only little additional memory: Instead of storing only the last progress states in the FIFO, all progress states on the postponed paths are saved, e.g., in form of a tree. The shortest counterexample can then easily be reconstructed using the progress states on the error path as guidance for the additional basic DFS. 2.3

Correctness of DFSFIFO

Constructively proving that DFSFIFO finds a certain NPC is difficult: We would require to consider various complex situations and the technical details of the

58

D. Farag´ o and P.H. Schmitt

init

s sh1

1

p1 sh1

1

aborted traversal

Fig. 4. s1h1 cannot be twice on the current path at time tend

init

init s

s

1

p

2

1

sh

aborted traversal

aborted traversal

p

1

sh

1

1

1

1

sh +1

sh +1

1

1

Fig. 5. Constructing π 2 from π 1

algorithm, e.g., the order in which the transitions are traversed (cf. Figure 6). Hence we prefer a pure existence proof. Theorem 1. DFSFIFO finds an NPC if one exists and otherwise outputs that no NPC exists. An NPC is found at the smallest depth w.r.t. progress, i.e., after the smallest number (L0 ) of progress states that have to be traversed. Proof. DFSFIFO only postpones transitions, but does not generate new ones. It checks for NPCs by searching through the stack (except the first state), i.e., it only considers non-progress states. Thus it is sound, i.e., it does not output false negatives. To prove completeness, i.e., that NPCs are found if they exist, let there be an NPC. As long as DFSFIFO constructs GL for L < L0 , all paths leading to an NPC are pruned. Let L = L0 , s be the first state reached in the DFS which is on an NPC, tbegin be the time the DFS reaches s (the first time), and π 1 =  s11 =s, s12 , . . . , s1n1 =s  be an NPC containing s. Because of (p-stop), the DFS stops traversing progress states while all non-progress states reachable from s are being traversed. We assume no NPC is found in GL0 . Hence the traversal of π 1 must be aborted because a state s1h1  = s for h1 ∈ {2, . . . , n1 − 1} is revisited (i.e., visited when already in the hash table) before π 1 is closed, i.e., before s could be reached the second time. Let tmiddle1 be the time when s1h1 is visited the first time and

Improving Non-Progress Cycle Checks

59

init t1 found NPC

t2 s firstly visited NPC

Fig. 6. The found NPC does not contain s

tend be the time when s1h1 is revisited and π 1 is aborted. s1h1 cannot be twice on the current path (once at the end and once earlier) at time tend : the first occurrence cannot be above s (i.e., closer to init) because s is the first visited state of π 1 , and not below s, since then an NPC s1h1 , . . . , s1h1  would be found, see Figure 4. So our algorithm first visits s in tbegin , then visits s1h1 at tmiddle1 , then backtracks from s1h1 and finally revisits s1h1 at tend while traversing π 1 . Informally, since our algorithm backtracks from s1h1 without having found an NPC, the traversal of the path from s1h1 to s was aborted because some state on it was revisited, i.e., the state has already been visited before, but after tbegin . With this argument, we come successively closer to completing some NPC, which is a contradiction. Formally: Let π 2 =  s21 =s, s22 , . . . , s2n2 =s  be the path from s at time tbegin to 1 sh1 at time tmiddle1 concatenated with s1h1 +1 , s1h1 +2 , . . . , s1n1 =s , i.e., π 2 is also an NPC containing s, see Figure 5. Therefore we can apply the argumentation from above to π 2 instead of π 1 to obtain a state s2k (k ∈ {1, . . . , n2 }) on π 2 that is revisited before π 2 is closed. Let tmiddle2 be the time when s2k is visited the first time. Since on π 2 the state s1h1 is visited the first time (at tmiddle1 ), the DFS also reaches (maybe a revisit) s1h1 +1 on π 2 (at some time after tmiddle1 ). So s2k = s1h2 for h2 ∈ {h1 + 1, . . . , n1 − 1}. Let π 3 =  s31 =s, s32 , . . . , s3n3 =s  be the NPC from s at time tbegin to s1h2 at time tmiddle2 concatenated with s1h2 +1 , s1h2 +2 , . . . , s1n1 =s. Applying this argumentation iteratively, we get a strictly monotonically increasing sequence (hi )i∈N with all hi ∈ {2, . . . , n1 − 1}. Because of this contradiction, the assumption that no NPC is found in GL0 is wrong. If all cycles in the LTS make progress, L will eventually be big enough to contain the complete graph. After traversing it the algorithm terminates with the correct output that no NPC exists. Thus our algorithm is correct. Note. The proof shows that DFSFIFO finds an NPC before backtracking from s. But the NPC does not have to contain s: Figure 6 shows an example if t1 is traversed ahead of t2 . Since our pure existence proof assumed that no NPCs are found, it also covers this case (cf. Figure 4).

60

D. Farag´ o and P.H. Schmitt

statementi; progress:statementj; statementi

statementj

statementi; atomic{skip; progress:statementj}; statementi

s

s

statementj skip progress

progress

Fig. 7. Progress transition with atomic

2.4

Comparison

We firstly compare SPIN’s NPC checks with DFSFIFO by relating their performances to that of the basic DFS (which corresponds to a safety check): The runtime for a basic DFS, denoted tsafety , is linear in the number of reachable states and transitions, the memory requirement ssafety is linear in the number of reachable states. For SPIN’s NPC checks, the memory required in the worst case is about 2×ssafety because of the never claim. The runtime is about 3×tsafety because of the nested search and the doubled state space. For DFSFIFO , both time and memory requirements are about the same as for the basic DFS. To construct a full counterexample, maximally tsafety is required, but usually far less. But this asymptotic analysis only gives rough complexities. For a more precise comparison, we look at the steps in detail and see that the inefficiencies of the NDFS algorithm are eliminated for DFSFIFO : The redundancy is completely avoided as all states are traversed only once by a simultaneous construction and NPC search. Furthermore, only paths with minimal progress are traversed. Since many livelocks in practice occur after very little progress – e.g., for the i-protocol (cf. [3]) after 2 sends and 1 acknowledge – DFSFIFO comprises an efficient search heuristic. Additionally, shortest (w.r.t. progress) counterexamples are easier to understand and often reveal more relevant errors. Finally, we can also model progress in a better way using progress transitions instead of progress states. SPIN’s NPC check needs to mark states as having progress because never claims are used: The never claim process is executed in lockstep with the remaining automaton and thus only sees the states of the remaining automaton, not its transitions. Since our DFSFIFO does not require never claims, we can mark transitions (e.g., those switching np from false to true in the original semantics) as having progress. The most fundamental implementation of progress transitions is to change the semantics of PROMELA so that a progress label marks the following statement as a progress transition. If we do not want to change the PROMELA semantics, we can use the construct ”statementi ; atomic {skip; progress: statementj }” instead of ”statementi ; progress: statementj ;”. Figure 7 shows the difference in the automata: The progress moves from state s to the following composite transition. ”atomic{...} ” guarantees that the progress state is left immediately

Improving Non-Progress Cycle Checks

process 1

x

global automaton

process 2

s1

s1,t1 x

t1

61

s1,t2

t2

s2

s2,t1

progress

progress

s2,t2 progress

Fig. 8. Faked progress Table 1. Big difference between safety and NPC checks Problem safety checks Size time depth states 3 5” 33 66 4 5” 40 103 5 5” 47 148 6 5” 54 201 7 5” 61 262 254 100” 1790 260353

NPC checks via NDFS time depth states 5” 387 1400 5” 2185 18716 6” 30615 276779 70” 335635 4.3e+06 memory overflow (> 1GB) memory overflow (> 1GB)

after it was entered. Unfortunately, SPIN does not interleave atomic sequences with the never claim process, so this technique cannot be used for SPIN’s NPC checks. Trying nevertheless, SPIN sometimes claims to find an NPC, but returns a trace which has a progress cycle; At other times, SPIN gives the warning that a ”progress label inside atomic - is invisible”. SPIN’s inconsequent warning suggests that it does not always detect progress labels inside atomic. Using progress transitions, we can model more faithfully since in reality actions, not states, make progress. For example in Figure 8, if the action corresponding to the transition from a state s2 to a state s1 causes progress, PROMELA models s2 as progress state. So the cycle between (s2 , t1 ) and (s2 , t2 ) in the global automaton is considered as progress cycle, although the system does not perform any progress within the cycle. The other case of a path with several different local progress states visited simultaneously or directly after one another cannot be distinguished from one persistent local progress state as in Figure 8. Using progress transitions, all these cases can be differentiated and are simpler: The number of progresses on a path π is simply its number of progress transitions, denoted |π|p . The biggest advantages of using progress transitions emerge in combination with partial order reduction (see Section 3). The performance comparison from this section has to be considered with caution, though, as the effectiveness of a verification usually stands and falls with the strength of the additional optimization techniques involved, especially partial order reduction (cf. Section 3). The reduction strength can significantly decrease when changing from safety to liveness checks because the traversal algorithm

62

D. Farag´ o and P.H. Schmitt

changes and the visibility constraint C2 (cf. Section 3) becomes stricter. For instance, in a case study that verified leader election protocols (cf. [4]), the safety checks with partial order reduction were performed in quadratic time and memory (i.e., easily up to SPIN’s default limit of 255 processes), whereas the NPC checks could only be performed up to the problem size 6 (see Table 1). So a very critical aspect of NPC checks is how strongly partial order reduction can reduce the state space. In the next section, we show that DFSFIFO is compatible with partial order reduction and that the elimination of redundancy in DFSFIFO – as well as its further advantages (see Section 3.3) – enhance the strength of partial order reduction.

3

Compatibility with Partial Order Reduction

SPIN’s various reduction methods contribute strongly to its power and success. Many of them are on a technical level and easily combinable with our NPC checks, for instance Bitstate Hashing, Hash-compact and collapse compression. For Bitstate Hashing and Hash-compact, the reduction might be weakened by DFSFIFO because the FIFO temporarily stores complete states. One of the most powerful reduction methods is partial order reduction (POR). In this section, we firstly introduce SPIN’s POR, which uses the technique of ample sets (see [1,2], for technical details [7]). Thereafter, we prove that DFSFIFO can be correctly combined with POR. Finally, we again compare SPIN’s NPC checks with DFSFIFO , this time also considering POR. 3.1

Introduction

One of the main reasons for state space explosion is the interleaving technique of model checking to cover all possible executions of the asynchronous product of the system’s component automata. These combined executions usually cause an exponential blowup of the number of transitions and intermediate states. But often statements of concurrent processes are independent: ∀s ∈ S : α, β ∈ enabled(s) =⇒ α, β ∈ S are iff α ∈ enabled(β(s)) and β ∈ enabled(α(s)) (enabledness) independent and α(β(s)) = β(α(s)) (commutativity) α, β ∈ S are iff α, β are not independent dependent with enabled : S → P(S) and S being the set of all statements (we regard a statement as the subset of those global transitions T in which a specific local transition is taken). So the different combinations of their interleaving have the same effect. POR tries to select only few of the interleavings having the same result. This is done by choosing in each state s a subset ample(s) ⊆ enabled(s), called the ample set of s in [11]. The choice of ample(s) must meet the conditions C0 to C3 listed in Table 2. C3’ is a sufficient condition for C3 and can be checked locally in the current state. Since SPIN is an on-the-fly model checker, it uses C3’.

Improving Non-Progress Cycle Checks

63

Table 2. Constraints on ample(s) C0 : Emptiness

ample(s) = ∅ ⇔ enabled(s) = ∅ C1 : Ample decom- No statement α ∈ S\ample(s) that is dependent on some stateposition ment from ample(s) can be executed in the original, complete graph after reaching the state s and before some statement in ample(s) is executed. C2 : Invisibility ample(s)  = enabled(s) =⇒ ∀α ∈ ample(s) : α is invisible, which means that α is not a progress transition, or, when progress states are being used, that α does not change np . C3 : Cycle closing If a cycle contains a state s s.t. α ∈ enabled(s) for some statecondition ment α, it also contains a state s
s.t. α ∈ ample(s
). C3’ : NotInStack α ∈ ample(s) and α(s) is on the stack ⇒ ample(s) = enabled(s)

If these conditions are met, then the original graph G and the partial order reduced graph G are stuttering equivalent : For each path π ∈ G there exists a path π  ∈ G (and vice versa) such that π and π  are stuttering equivalent (cf. [11] and [2]). In our special case of NPCs, two paths π and π  are stuttering equivalent (π ∼st π  ) iff they make the same amount of progress. 3.2

Correctness of DFSFIFO in Combination with POR

For proving the correctness of DFSFIFO with POR activated, we have to look at the conditions for POR first. C3’ no longer implies C3 if DFSFIFO is used: Since a large part of the stack gets lost by postponing the traversal at progresses (progress states or progress transitions), progress cycles are not detected. To guarantee C3 for progress cycles being traversed, we traverse all pending transitions when we are about to destroy the stack by making progress. So for each state s we fulfill the condition: (∃α ∈ ample(s) : α is visible) =⇒ (ample(s) = enabled(s)). This is equivalent to C2. Note. When progress states are being used, C2 is not sufficient to guarantee C3 in the special case of cycles that solely contain progress states (e.g., as in Figure 8). Several solutions are possible: Firstly, we can alter C2 to C2’: (∃α ∈ ample(s) : α(s) is a progress state) =⇒ (ample(s) = enabled(s)). Secondly, these cycles might be avoidable by weak fairness (which is combinable with our algorithm) if they are caused by one process remaining in its progress state throughout the cycle. Thirdly, we can guarantee by hand that these long sequences of progress states never occur, e.g., by forcing quick exit from progress states (similarly to Figure 7). But we favor using progress transitions anyway, which is once more the simplest and most efficient solution. If DFSFIFO detects a cycle on the stack, it has already found an NPC and is finished. Hence we no longer need C3’, C2 suffices to fulfill C3. This fact helps in the following proof.

64

D. Farag´ o and P.H. Schmitt

Theorem 2. DFSFIFO in combination with POR finds an NPC if one exists and otherwise outputs that no NPC exists. An NPC is found at the smallest depth w.r.t. progress, i.e., after the smallest number (L0 ) of progresses that have to be traversed. Proof. Partial order reducing the graph G does not create new NPCs. Hence DFSFIFO still does not output false negatives. To prove completeness, let there be an NPC in G. If L < L0 , all paths leading to an NPC are pruned before the NPC is reached. Let L = L0 and π be a counterexample in GL0 . C3’ is unnecessary for DFSFIFO . C0, C1 and C2 are independent of the path leading to s. Thus ample(s) can be determined independently of the path leading to s. So all conditions C0, C1, C2 and C3 are met and ample(s) is not influenced by the differing traversal order. Hence stuttering equivalence is preserved. Thus the reduced graph from GL0 that DFSFIFO with POR constructs also has an infinite path with exactly L0 progresses like π, i.e., an NPC. Theorem 1 proves that after L0 progresses an NPC is found by DFSFIFO in combination with POR. 3.3

Comparison

Now we can do an overall comparison between SPIN’s NPC checks and DFSFIFO , both with POR activated (pros for DFSFIFO are marked with +): + DFSFIFO avoids all redundancies and therefore saves time and memory and enables stronger POR. + The use of progress transitions instead of progress states is possible, spawning several advantages: • The faithful modeling not only simplifies the basic algorithms, but also the application of POR: The visible transitions are exactly the progress transitions, and π ∼st π  iff |π|p = |π  |p . That is why progress transitions are the easiest solution to get by with C2 instead of C2’. • Only one of the originally two local transitions is now visible, i.e., we definitely have fewer visible global transitions. • In certain situations, this difference in the number of visible global transitions can get very large: Figure 9 depicts that the global automaton can have far more visible transitions when progress states are used instead of progress transitions. Consequently, also the ample sets strongly differ in size. The ample sets are marked with circles, the visible transitions with - (if np is switched to true) and +. + The constraint C3’ becomes unnecessary. – To obtain an error path from the initial state to the NPC, an additional basic DFS is necessary, but this requires less resources than the main check. + A shortest (w.r.t. progress) error path can be given, which is often easier to understand and more revealing than longer paths. + By avoiding progress as much as possible, DFSFIFO exhibits an efficient NPC search heuristic: In practice, NPCs often occur after only few progresses. Additionally, by avoiding progress as much as possible, its visibility weakens

Improving Non-Progress Cycle Checks

SPIN’s POR with progress states

65

DFSFIFO’s POR with progress transitions

+ + +

-

+

-

+

-

+

+ + + + + +

Fig. 9. Ample sets (red circles) are smaller for progress transitions

POR just as much as necessary. Since the time and memory requirements of DFSFIFO and the basic DFS are about the same, the performance of our NPC check is roughly the same as for a safety check if POR stays about as strong as for safety checks. + Our new NPC check is a more direct method. This is in line with SPIN’s paradigm of choosing the most efficient and direct approach and eases modifications, such as improvements, additional options and extensions. + It might be possible to improve POR: For finding NPCs, we only need to distinct |π|p = ∞ from |π|p < ∞ for an infinite path π. Therefore a stronger reduction that does not guarantee stuttering equivalence is sufficient, as long as at least one NPC is preserved. Note. We can also compare our DFSFIFO with SPIN’s former NPC check. The old check used the NDFS directly (see [5]). [8] explains that this algorithm is not compatible with POR because of condition C3. The authors of the paper ”do not know how to modify the algorithm for compatibility with POR” and suggest the alternative SPIN is now using (cf. Section 1.1). But DFSFIFO can be regarded as such modification of SPIN’s old NPC check: the state space creation and the search for an NPC are combined, and C3 is reduced to C2.

4 4.1

Closure Conclusion

Instead of separately constructing the state space and searching for NPCs, as SPIN does, DFSFIFO performs both at the same time. To be able to avoid a

66

D. Farag´ o and P.H. Schmitt

nested search, DFSFIFO postpones traversing progress for the (L + 1)-th time until the combined state space creation and NPC check for the subgraph GL is finished. Then DFSFIFO retrieves the postponed progresses and continues with GL+1 \ GL . When an NPC is found or the complete graph is built, DFSFIFO terminates. DFSFIFO is a more direct NPC check than SPIN’s method, with no redundancy, and enabling an efficient search heuristic, better counterexamples, the use of progress transitions, stronger POR and facilitation of improvements. With these enhancements, the verification by NPC checks becomes more efficient. As trade-off, DFSFIFO does not deliver an error path from the initial state to the NPC anymore, only the NPC itself. For a complete error path, an additional basic DFS is required - whose cost is, however, negligible.

4.2

Future Work and Open Questions

Having proved that DFSFIFO is correct and combinable with POR, we can now move from these important theoretical questions to the next step of implementing the algorithm. Thereafter, we will analyze DFSFIFO ’s performance. Because of the mentioned advantages, we are optimistic that DFSFIFO will strongly improve NPC checks in practice. Section 3.3 posed the open question whether POR can be further strengthened for our NPC checks by weakening stuttering equivalence to a constraint that solely preserves NPC existence. Solving this question might further speed up our NPC check.

References 1. Clarke, E.M., Grumberg, O., Minea, M., Peled, D.: State space reduction using partial order techniques. International Journal on Software Tools for Technology Transfer (STTT) 2, 279–287 (1999) 2. Clarke Jr., E.M., Grumberg, O., Peled, D.A.: Model Checking. The MIT Press, Cambridge (1999); third printing, 2001 edition 3. Dong, Y., Du, X., Ramakrishna, Y.S., Ramakrishnan, C.R., Ramakrishnan, I.V., Smolka, S.A., Sokolsky, O., Stark, E.W., Warren, D.S.: Fighting livelock in the i-protocol: a comparative study of verification tools. In: Cleaveland, W.R. (ed.) TACAS 1999. LNCS, vol. 1579, pp. 74–88. Springer, Heidelberg (1999) 4. Farag´ o, D.: Model checking of randomized leader election algorithms. Master’s thesis, Universit¨ at Karlsruhe (2007) 5. Holzmann, G.J.: Design and Validation of Computer Protocols. Prentice Hall Software Series (1992) 6. Holzmann, G.J.: The SPIN Model Checker: primer and reference manual, 1st edn. Addison Wesley, Reading (2004) 7. Holzmann, G.J., Peled, D.: An improvement in formal verification. In: Proceedings of the Formal Description Techniques 1994, Bern, Switzerland, pp. 197–211. Chapman & Hall, Boca Raton (1994) 8. Holzmann, G.J., Peled, D., Yannakakis, M.: On nested depth-first search. In: Proceedings of the Second SPIN Workshop, Rutgers Univ., New Brunswick, NJ, August 1996, pp. 23–32. American Mathematical Society. DIMACS/32 (1996)

Improving Non-Progress Cycle Checks

67

9. Islam, S.M.S., Sqalli, M.H., Khan, S.: Modeling and formal verification of DHCP using SPIN. IJCSA 3(2), 145–159 (2006) 10. Kamel, M., Leue, S.: Formalization and validation of the general inter-orb protocol (GIOP) using PROMELA and SPIN. In: Software Tools for Technology Transfer, pp. 394–409. Springer, Heidelberg (2000) 11. Peled, D.: Combining partial order reductions with on-the-fly model-checking. In: 6th International Conference on Computer Aided Verification, Stanford, California (1994)

Reduction of Verification Conditions for Concurrent System Using Mutually Atomic Transactions Malay K. Ganai1 and Sudipta Kundu2 1

2

NEC Labs America, Princeton, NJ, USA University of California, San Diego, CA, USA

Abstract. We present a new symbolic method based on partial order reduction to reduce verification problem size and state space of a multi-threaded concurrent system with shared variables and locks. We combine our method with a previous token-based approach that generates verification conditions directly without a scheduler. For a bounded unrolling of threads, the previous approach adds concurrency constraints between all pairs of global accesses. We introduce the notion of Mutually Atomic Transactions (MAT), i.e., two transactions are mutually atomic when there exists exactly one conflicting shared-access pair between them. We propose to reduce the verification conditions by adding concurrency constraints only between MATs. Such an approach removes all redundant interleavings, thereby, achieves state reduction as well. We guarantee that our MAT-based reduction is both adequate (preserves all the necessary interleavings) and optimal (no redundant interleaving), for a bounded depth analysis. Our experimental results show the efficacy of our approach in reducing the state space and the verification problem sizes by orders of magnitude, and thereby, improving the overall performance, compared with the state-of-the-art approaches.

1 Introduction Verification of multi-threaded programs is hard due to complex and un-expected interleaving between the threads [1]. In practice, verification efforts often use incomplete methods, or imprecise models, or sometimes both, to address the scalability of the problem. The verification model is typically obtained by composing individual thread models using interleaving semantics, and model checkers are applied to systematically explore the global state space. To combat the state explosion problem, most methods employ partial-order reduction techniques to restrict the state-traversal to only a representative subset of all interleavings, thereby, avoiding exploring the redundant interleaving among independent transitions [2, 3, 4]. Explicit model checkers [5, 6, 7, 8, 9] explore the states and transitions of concurrent system by explicit enumeration, while symbolic model checkers [10, 11, 12, 13, 14, 15, 16, 17] uses symbolic methods. We focus on symbolic approaches based on SMT (Satifiability Modulo Theory) to generate efficient verification conditions. Based on how verifications models are built, symbolic approaches can be broadly classified into: synchronous (i.e., with scheduler) and asynchronous (i.e., without scheduler) modeling. Synchronous modeling: In this category of symbolic approaches [10, 11, 12], a synchronous model of concurrent programs is constructed with a scheduler. The scheduler is then constrained—by adding guard strengthening—to explore only a subset C.S. P˘as˘areanu (Ed.): SPIN 2009, LNCS 5578, pp. 68–87, 2009. c Springer-Verlag Berlin Heidelberg 2009


Reduction of Verification Conditions for Concurrent System Using MAT

69

of interleaving. To guarantee correctness (i.e., cover all necessary interleavings), the scheduler must allow context-switch between accesses that are conflicting (i.e. dependent). One determines statically (i.e., conservatively) which pair-wise locations require context switches, using persistent [4]/ample [18] set computations. One can further use lock-set and/or lock-acquisition history analysis [19, 20, 21, 11], and conditional dependency [22, 16] to reduce the set of interleavings need to be explored (i.e., remove redundant interleavings). Even with these state reduction methods, the scalability problem remains. To overcome that, researchers have employed sound abstraction [7] with bounded number of context switches [23] (i.e., under-approximation), while some others have used finite-state model abstractions [13], combined with proof-guided method to discover the context switches [14]. Asynchronous Modeling: In this category, the symbolic approaches such as TCBMC [15] and token-based [17] generate verification conditions directly without constructing a synchronous model of concurrent programs, i.e., without using a scheduler. These verification conditions are then solved by satisfiability solvers. To our knowledge so far, the state-reduction based on partial-order has hardly been exploited in the asynchronous modeling approaches [15, 17]. We will focus primarily in that direction. Our Approach: We present a new SMT-based method—combining partial-order reduction with the previous token-based approach [17]—to reduce verification problem size and state-space for multi-threaded concurrent system with shared variables and locks. For a bounded unrolling of threads, the previous approach adds concurrency constraints between all pairs of global accesses, thereby allowing redundant interleavings. Our goal is to reduce the verification conditions by removing all redundant interleavings (i.e., guarantee optimality) but keeping the necessary ones (i.e., guarantee adequacy). We first introduce the notion of Mutually Atomic Transactions (MAT), i.e., two transactions are mutually atomic when there exists exactly one conflicting sharedaccess pair between them. We then propose an algorithm to identify an optimal and adequate set of MATs. For each MAT in the set, we add concurrency constraints only between the first and last accesses of the transactions, and not in-between. Our MATbased approach achieves reduction both in state-space as well as in the size of verification conditions. We guarantee that our MAT-based reduction is both adequate (preserves all the necessary interleavings) and optimal (no redundant interleaving), for a bounded depth analysis. We implemented our approach in a SMT-based prototype framework, and demonstrated the efficacy of our approach against the state-of-the-art SMT-based approaches based on asynchronous modeling [17], and synchronous modeling [16], respectively. Outline: We provide an informal overview of our MAT-based reduction approach in Section 2, followed by formal definitions and notations in Section 3. In Section 4, we present a flow diagram of our new SMT-based method. We give an algorithm for identifying an adequate and optimal set of MATs in Section 5, followed by a presentation of adequacy and optimality theorems in Section 6. We present our experimental results in Section 7, and conclusions in Section 8.

70

M.K. Ganai and S. Kundu

2 An Overview We motivate our readers with a following example, which we use to guide the rest of our discussion. Consider a two-threaded concurrent system comprising threads M1 and M2 with local variables ai and bi , respectively, and shared (global) variables x, y, z. This is shown in Figure 1(a), as a concurrent control flow graph (CCFG) with a forkjoin structure. Each shared statement associated with a node is atomic, i.e., it cannot be interrupted. Further, each node is associated with at most one shared access. A node with a shared write/read access of variable x is identified as W (x)/R(x). We use the notation ? to denote a non-deterministic input to a variable. Given such a concurrent system, the goal of the token-based approach [17] is to generate verification conditions that capture necessary interleaving for some bounded unrolling of the threads, aimed at detecting reachability properties such as data races and assertion violations. These verification conditions together with the property constraints are encoded and solved by an SMT solver. A satisfiable result is typically accompanied by a trace—comprising data input valuations, and a total-ordered thread interleaving— that is witness to the reachability property. On the other hand, an unsatisfiable result is followed by these steps (a)—(c): (a) increase unroll depths of the threads, (b) generate verification conditions for increased depths, and (c) invoke SMT solver on these conditions. Typically, the search process (i.e., to find witnesses) is terminated when a resource—such as time, memory or bound depth—reaches its limit. For effective implementation, these verifications constraints are added on-the-fly, lazily and incrementally at each unrolled depth. Though the approach captures all necessary interleaving, it however does not prevent redundant interleavings. In this work, our goal is to remove all the redundant interleavings but keep the necessary ones for a given unroll bound. We focus on reducing the verification conditions, as generated in the token-passing modeling approach [17]. To understand how we remove redundancy, we first present a brief overview of such a modeling approach. x=? y=? CCFG z=?

assume (-7 < x) assume (y < z+5)

I

Fork

x,y,z=? tk= ? ctk= ?

Token-Passing Model

W(y)

1a

y=0

b1=x-2

1b

R(x)

W(y)

1a

1b

R(x)

R(x)

2a

a1=x+3 z=b1-1

2b

W(z)

R(x)

2a

2b

W(z)

R(z)

3a

a2=z-1

3b

R(x)

R(z)

3a

3b

R(x)

W(y)

4a

y=a1-a2 y=b1+b2

4b

W(y)

W(y)

4a

4b

W(y)

b2=x+1

3b

Join

M1 R(y)

E

(a)

rs

M2

ws tk= ?

#pair-wise constraints = 4∗4∗2=32

assert (y > 0)

(b)

Fig. 1. (a) Concurrent system, shown as thread CFGs, with threads M1 , M2 and local variables ai , bi respectively, communicating with shared variable x, y, z, and (b) Token-passing Model [17]

Reduction of Verification Conditions for Concurrent System Using MAT

71

2.1 Token-Passing Model The main idea of token-passing model (TPM) is to introduce a single Boolean token tk and a clock vector ctk in a model, and then manipulate the passing of the token to capture all necessary interleavings in the given system. The clock vector records the number of times the token tk is passed and is synchronized when the token is passed. Unlike a synchronous model, TPM does not have a scheduler in the model. The verification model is obtained two phases. In the first phase, the goal is obtain abstract and decoupled thread models. Each thread is decoupled from the other threads by localizing all the shared variables. For the example shown in Figure 1(a), M1 and M2 are decoupled by renaming (i.e., localizing) shared variable such as x to x1 and x2 , respectively. Each model is then abstracted by allowing renamed (i.e., localized) variables to take non-deterministic values at every shared access. To achieve that, each shared access node (in every thread) is instrumented with two control states as follows: (a) an atomic pre-access control state, referred to as read sync block, is inserted before each shared access, and (b) an atomic post-access control state, referred to as write sync block, is inserted after each shared access. In read sync block, all localized shared variables obtain non-deterministic values. As an example, we show the token-passing model in the Figure 1(b). For clarity of presentation, we did not show renaming of the shared variables, but for all our purpose we consider them to be local to the thread, i.e., x of thread Mi and x of Mj are not the same variable. In such a model, atomic control states rs and ws are inserted pre and post of shared accesses in decoupled model, respectively. As highlighted for a control state 3b, we add the following statements in the corresponding rs node, i.e., x=?,y=?,z=?,tk=?,ctk=?. Similarly, we add tk=? in ws node. (? denotes the non-deterministic values.) Note, the transition (update) relation for each localized shared variable depends on other local variables, thereby, making the model independent (i.e., decoupled). However, due to non-deterministic read values, the model have additional behaviors, hence, it is an abstract model. In the second phase, the goal is to remove the imprecision caused due to abstraction. In this phase, the constraints are added to restrict the introduced non-determinism and to capture the necessary interleavings. More specifically, for each pair of shared access state (in different threads), token-passing constraints are added from the write sync node of a shared access to the read sync node of the other shared access. Intuitively, these token-passing constraints allow passing of the token from one thread to another, giving a total order in the shared accesses. Furthermore, these constraints allow to synchronize the values of the localized shared variables from one thread to another. Together, the token-passing constraints captures all and only the necessary interleavings that are sequentially consistent [24] as stated in the following theorem. Theorem 1 (Ganai, 2008 [17]). The token-based model is both complete, i.e., it allows only sequentially consistent traces, and sound, i.e., captures all necessary interleaving, for a bounded unrolling of threads. Further, the size of pair-wise constraints added grow quadratically (in the worse case) with the unrolling depth.

72

M.K. Ganai and S. Kundu

In Figure 1(b), we show a token-passing constraint as a directed edge from a write sync ws node of one thread to a read sync rs node of another. Note, these constraints are added for all pairs of ws and rs nodes. A synchronization constraint from M1 to M2 will include x2 = x1 ∧ y2 = y1 ∧ z2 = z1 ∧ tk2 = 1 ∧ tk1 = 0 ∧ ctk2 = ctk1 , where token-passing is enforced by assertion/de-assertion of corresponding token variable. (Recall, vi is localized variable in Mi corresponding to shared variable v). As shown, one adds 4 ∗ 4 ∗ 2 = 32 such token-passing constraints for this example. Improvement Scope: Though the above approach captures all and only necessary interleavings, it also allows interleavings that may be redundant (i.e. equivalent). For example, the interleaving σ1 ≡ 1b · 2b · 1a · 3b · 4b · 2a · 3a · 4a, and σ2 ≡ 1a · 2a · 1b · 2b · 3a · 3b · 4b · 4a, are equivalent as in these interleavings the conflicting pairs (2b, 3a), (1a, 4b), (4b, 4a) are in the same happens-before order, besides the thread program order pairs. (Note, “·” denotes concatenation). The previous-approach [17] will explore both the interleavings. In the following sections, we build our approach on such a token-passing model to identify pair-wise constraints that can be safely removed, without affecting soundness and completeness, and guaranteeing optimality by removing all redundant interleavings. For the example in Figure 1, our approach removes 24 such pair-wise constraints (as shown in Figure 4), and yet covers all the necessary interleavings with no redundancy. To illustrate, our approach allows σ1 , and not any other equivalent (to σ1 ) interleavings such as σ2 . Note, the choice of a representative interleaving will depend on a given thread prioritization, as discussed later. 2.2 Mutually Atomic Transactions Our partial-order reduction approach is based on the concept of mutually atomic transactions, MAT for short. Intuitively, let a transaction be a sequence of statements in a thread, then we say two transactions tri and trj of threads Mi and Mj , respectively, are mutually atomic transactions if and only if there exists exactly one conflicting shared-access pair between them, and the statements containing the shared-access pair is the last one in each of the transactions. (We will present a more formal definition later). Now we illustrate the concept of MAT using an example as shown in Figure 2. From the control state pair (1a, 1b), there are two reachable control states with conflicting accesses, i.e., (3a, 2b) and (1a, 4b). Corresponding to that we have two MATs m = (tr1 = 1a · · · 3a, tr2 = 1b · · · 2b) (Figure 2(a)) and m
= (tr1
= 1a, tr2
= 1b · · · 4b) (Figure 2(b)), respectively. Similarly, from (1a, 2b) we have m

= (tr1

= 1a, tr2

= 2b · · · 4b) (Figure 2(c)). In general, there could be multiple possible MATs for our examples. In a more general setting with conditional branching, we identify MATs by exploring beyond conditional branches, as illustrated in the Figure 2(d), with a conditional branch denoted as a diamond node, and control states Ai , Bi , Ci denoted as dark ovals. Starting from (A1 , A2 ), we have following control path segments, tr11 = A1 · · · B1 , tr12 = A1 · · · C1 , tr21 = A2 · · · B2 , and tr22 = A2 · · · C2 (shown as ovals). For each of the four combinations of tr1i , tr2j , we define MAT separately.

Reduction of Verification Conditions for Concurrent System Using MAT

tr1 W(y)

tr’1

tr2

1a

1b

R(x)

R(z)

W(y)

R(x)

2a

2b

W(z) R(x)

R(z)

3a

3b

R(x)

W(y)

4a

4b

W(y) W(y)

(a)

tr’2

tr’’2 1b

R(x)

1b

W(y)

1a

2a

2b

W(z)

R(x)

2a

2b

W(z)

3a

3b

R(x)

R(z)

3a

3b

R(x)

4a

4b

W(y)

W(y)

4a

4b

W(y)

1a

A1

(c)

A2

tr12

tr11

B1

(b)

M2

M1

tr’’1 R(x)

73

tr22

tr21

C1

B2

C2

(d)

Fig. 2. (a) m=(tr1 , tr2 ), (b) m
=(tr1
, tr2
), (c) m

=(tr1

, tr2

) (d) MATs for branches

Given a MAT (tri , trj ), we can have only two equivalent classes of interleavings [25]. One represented by tri · trj , i.e., tri executing before trj and other by trj · tri , i.e., trj executing before tri . (Note, “·” represent concatenations.) For a given MAT m = (tr1 , tr2 ) shown in Figure 2(a), the interleavings σ1 ≡ 1a · 2a · 3a · 1b · 2b and σ2 ≡ 1b · 2b · 1a · 2a · 3a represent the two equivalent classes, respectively. In other words, given a MAT, the associated transactions can be considered atomic pair-wise, and one can avoid interleaving them in-between. In general, transactions associated with different MATs may not be atomic. For example, tr1 is not atomic with tr2

(Figure 2(a),(c)). Intuitively, it would be desirable to have a set of MATs such that, by adding tokenpassing constraints only between MATs, we will not only miss any necessary interleaving but also remove all the redundant interleaving. In Section 5, we describe such an algorithm GenMAT to compute an optimal and adequate set of MATs. For our example one such set is {(1a · · · 3a, 1b · · · 2b), (4a, 1b · · · 4b), (1a, 3b · · · 4b), (4a, 3b · · · 4b), (2a · · · 4a, 3b · · · 4b)}. Based on the set, we add only 8 token-passing constraints (Figure 4), compared to 32 (Figure 1(b)). At this point we would like to highlight the salient features of our approaches vis-a-vis previous works. A previous approach [9] on partial-order reduction used in a explicit model checking framework does not guarantee optimality. Though such guarantee is provided in a recent symbolic approach (using synchronous modeling) [16], our approach goes further in reducing problem sizes, besides an optimal reduction in the state space. Our approach obtains state space reduction by removing constraints (i.e., adding fewer token-passing constraints), while the approach [16] obtains it by adding more constraints (i.e., constraining the scheduler). In our experiments, we observed that our approach is order-of-magnitude more memory efficient compared to the approaches [16,17]. Our approach is orthogonal to the approaches that exploit transactionbased reductions [19,20,11]. Nevertheless, we can exploit those to identify unreachable conflicting pairs, and further reduce the necessary token-passing constraints. Contributions Highlights: – We are first to exploit partial order reduction techniques in a SMT-based bounded model checking using token-passing modeling approach. We developed a novel approach—based on MAT—to reduce verification conditions, both in size and state space for concurrent systems.

74

M.K. Ganai and S. Kundu

– We prove that our MAT-based reduction is both adequate (preserves all and only the necessary interleavings) and optimal (no redundant interleaving, as determined statically), for a bounded depth analysis. – Our approach outperforms other approaches [17, 16] by orders of magnitude, both in performance and size of the verification problems.

3 Formal Definitions With the brief informal overview, we present our approach in a more formal setting. We consider a multi-threaded system CS comprising a finite number of deterministic bounded-stack threads communicating with shared variables, some of which are used as synchronization objects such as locks. Let Mi (1 ≤ i ≤ N ) be a thread model represented by a control and data flow graph of the sequential program it executes. Let Ti represent the set of 4-tuple transitions (c, g, u, c
) of thread Mi , where c, c
represent the control states, g is Boolean-valued enabling condition (or
guard) on program variables, u is an update function on program variables. Let T = i Ti be the set of all transitions. Let Vi be set of local variables in Ti and V be set of (global) shared variables. Let S be the set of global states of the system, and a state s ∈ S is valuation of all local and global variables of the system. A global transition system for CS is an interleaved composition of the individual thread models, Mi . Each transition consists of global firing of a local transition ti = (ai , gi , ui , bi ) ∈ T . If enabling predicate gi evaluates to true in s, we say that ti is enabled in s. 3.1 Notation We define the notion of a run of a multi-threaded program as an observation of events such as global accesses, thread creations and thread termination. If the events are ordered, we call it a total order run. We define a set Ai of shared accesses corresponding to a read Ri (x) and a write Wi (x) of a thread Mi where x ∈ V. For ai ∈ Ai , we use var(ai ) to denote the accessed shared variable. We use i to denote the beginning and i to denote the termination of thread Mi , respectively. The alphabets of events of thread Mi is a set Σi = Ai ∪ {i , i }. We use Σ = ∪i Σi to denote a set of all events. A word σ defined over the alphabet set Σ, i.e., σ ∈ Σ ∗ is a string of alphabet from Σ, with σ[i] denoting the ith access in σ, and σ[i, j] denoting the access substring from ith to j th position, i.e., σ[i] · · · σ[j] (· denotes concatenation). |σ| denotes the length of the word σ. We use π(σ) to denote a permutation of alphabets in the word σ. We use σ |i to denote the projection of σ on thread Mi , i.e., inclusion of the actions of Mi only. Transaction: A transaction is a word tri ∈ Σi∗ that may be atomic (i.e., uninterrupted by other thread) with respect to some other transactions. If it is atomic with respect to all other thread transactions, we refer it as independent transaction. Schedule: Informally, we define a schedule as a total order run of a multi-threaded program where the accesses of the threads are interleaved. Formally, a schedule is a word σ ∈ Σ ∗ such that σ |i is a prefix of the word i ·A∗i · i . Happens-before Relation (≺, ): Given a schedule σ, we say e happens-before e
, denoted as e ≺σ e
if i < j where σ[i] = e and σ[j] = e
. We drop the subscript if

Reduction of Verification Conditions for Concurrent System Using MAT

75

it is obvious from the context. Also, if the relation is not strict, we use the notation . If e, e
∈ Σi and e precedes e
in σ, we say that they are in a thread program order, denoted as e ≺po e
. Sequentially consistent: A schedule σ is sequentially consistent [24] iff (a) σ |i is in thread program order, (b) each shared read access gets the last data written at the same address location in the total order, and (c) synchronization semantics is maintained, i.e., the same locks are not acquired in the run without a corresponding release in between. We only consider schedules (and their permutations) that are sequentially consistent. Conflicting Access: We define a pair ai ∈ Ai , aj ∈ Aj , i  = j conflicting, if they are accesses on the same shared variable (i.e., var(ai ) = var(aj )) and one of them is write access. We use Cij to denote the set of tuples (ai , aj ) of such conflicting accesses. We use Shij to denote a set of shared variables—between Mi and Mj threads—with at
least one conflicting access, i.e., Shij = {var(ai )|(ai , aj ) ∈ Cij }. We define Shi = = i with at least one i =j Shij , i.e., a set of variables shared between Mi and Mk , k  conflicting access. In general, Shij ⊆ (Shi ∩ Shj ). Dependency Relation (D): A relation D ⊆ Σ × Σ is a dependency relation iff for all (e, e
) ∈ D, one of the following holds: (1) e, e
∈ Σi and e ≺po e
, (2) (e, e
) ∈ Cij , (3) e =i , e
=j for i  = j. Note, the last condition is required when the order of thread termination is important. If (e, e
)  ∈ D, we say the events e, e
are independent. The dependency relation in general, is hard to obtain; however, one can obtain such relation conservatively using static analysis [4], which may result in a larger dependency set than required. For our reduction analysis, we assume such a relation is provided and base our optimality and adequacy results on accuracy of such a relation. Equivalency Relation (): We say two schedules σ1 = w · e · e
· v and σ2 = w · e
· e · v are equivalent (Mazurkiewicz’s trace theory [25]), denoted as σ1  σ2 , if (e, e
)  ∈ D. An equivalent class of schedules can be obtained by iteratively swapping the consecutive independent events in a given schedule. Final values of both local and shared variables remains unchanged when two equivalent schedules are executed. A partial order is a relation R ⊆ Σ × Σ on a set Σ, that is reflexive, antisymmetric, and transitive. A partial order is also a total order if, for all e, e
∈ Σ, either (e, e
) ∈ R, or (e
, e) ∈ R. Partial order-based reduction (POR) methods [4] avoid exploring all possible interleavings of shared access events. Note, if (e, e
) ∈ D, all equivalent schedules agree on either e ≺ e
or e
≺ e, but not both. Definition 1 (MAT). We say two transactions tri and trj of threads Mi and Mj , respectively, are mutually atomic iff except for the last pair, all other event pairs in the corresponding transactions are independent. Formally, a Mutually Atomic Transactions (MAT) is a pair of transactions, i.e., (tri , trj ), i  = j iff ∀k 1 ≤ k ≤ |tri |, ∀h 1 ≤ h ≤ |trj |, (tri [k], trj [h])  ∈ D (k  = |tri | and h  = |trj |), and tri [|tri |], trj [|trj |]) ∈ D. Given a MAT (tri , trj ), an interesting observation (as noted earlier) is that a word w = tri · trj is equivalent to any word π(w) obtained by swapping any consecutive events tri [k] and trj [h] such that k  = |tri | and h  = |trj |. Similarly, the word w
= trj · tri is
equivalent to any word π(w ) obtained as above. Note, w   w
. Therefore, for a given MAT, there are only two equivalent classes, represented by w and w
. In other words, given a MAT, the associated transactions are atomic pair-wise.

76

M.K. Ganai and S. Kundu

4 Token-Passing Model Using MAT We exploit the pair-wise atomicity of MATs in a token-based model as follows: Let c(e) represent the control state of the thread where the corresponding event e occurs. For the given MAT (tri = fi · · · li , trj = fj · · · lj ), we only add token-passing constraints from c(lj ) to c(fi ), and c(li ) to c(fj ), respectively. Recall, such constraints are added between the corresponding pre and post- access blocks as discussed in Section 2.1. 1 n Adequacy of MATs. Given a schedule σ = w11 · · · wN · · · w1n · wN , wik ∈ Σi∗ , 1 ≤ k ≤ n, 1 ≤ i ≤ N . We define a set of ordered pairs CSP as follows: CSP (σ) =
{(lik , fik
)|1 ≤ i, i
≤ N, 1 ≤ k, k
≤ n} where fik and lik denote the first and last
accesses of wik ; and wik
is a non-empty word adjacent right of wik . Note, CSP (σ) captures the necessary interleaving pairs to obtain the schedule, i.e., if we add token passing constraints between every pair of control states (a, b) ∈ CSP (σ), we allow the schedule σ. For a given MAT α = (fi · · · li , fj · · · lj ), we define a set of interleaving ordered pairs,
T P (α) = {(li , fj )), (lj , fi ))}. Given a set of MAT ij , we define T P (MAT ij ) = α∈MAT ij T P (α), and denote it as T Pij . We say a tokenpassing pairs set T P is adequate iff for every schedule σ in the multi-threaded system, CSP (σ) ⊆ T P . A set MAT is adequate iff T P is adequate. Note, the size of T P is upper bounded by quadratic number of pair-wise accesses.

We use procedure GenM AT (ref. Section 5) to obtain a set of MAT ij . If Shij
Shi ∪ Shj , we use procedure GenExtraT P (ref. Section 6) to generate an extra token-passing pairs

set eT Pij from MAT ij . We then construct the adequate set T P as ( i=j T Pij ) ∪ ( i=j eT Pij ). We give an overview of using MATs in a token-passing model to selectively add token-passing constraints as shown in Figure 3.

C

Unrolled Thread CFGs M1…Mn

1. GenMAT: Given ij for a thread pair (Mi,Mj) find a set ij , 2. TPij = {(fi,lj),(fj,li) | (fi li, fj lj)∈ ) ij 3. GenExtraTP( ij ): find set eTPij 4. TP = (∪i≠jTPij ) ∪ (∪i≠jeTPij )

MAT ⇒ ⇒ MAT MAT

C

C C

Update ij ⇐ ij\c where c is a conflicting pair location that is simultaneously unreachable

5

NEW

For each thread pair (Mi,Mj) identify a set ij of pair thread locations with conflicting shared accesses

C

3

C

i={xi | (xi,xk)∈ ik k≠i}, TPij = {(xi,xj)(xj,xi) | (xi,xj) ∈ i × TP = ∪i≠jTPij

OLD

C C} j

4

Token-passing Model

Independent (decoupled) thread model For each (a,b) ∈ TP, add token passing constraint 6

OLD

1

2

NEW

Step 1,2: Given a set of unrolled threads M1 · · · MN , we obtain a set of conflicting pair of control locations Cij for each thread pair Mi , Mj . Step 3: From the set Cij , we remove the pairs that are unreachable simultaneously due to i) happens-before relation such as before and after fork/join, ii) mutual exclusion, iii) lock acquisition pattern [11].

Add bound constraints on number of token exchanges 7 Generate verification conditions and give to SMT/SAT solver 8

Fig. 3. Reducing verification conditions in a token-passing model using MAT

Reduction of Verification Conditions for Concurrent System Using MAT

77

Step 4: (Corresponds to previous scheme [17], denoted as OLD). An ordered set of token-passing pairs TP is obtained by considering every pair of control states in Ci × Cj , where Ci and Cj consist of control states of thread Mi and Mj that have some conflicting access, respectively. Step 5: (Corresponds to our proposed scheme, denoted as NEW). For each thread pairs Mi and Mj , and corresponding set Cij , we identify a set MAT ij using GenM AT . We obtain the set T Pij = T P (MAT ij ). Given a
set MAT ij , we
identify a set eT Pij using GenExtraT P . We construct T P = ( i=j T Pij ) ∪ ( i=j eT Pij ). Step 6: We now build token-passing model by first generating decoupled (unrolled) thread models. For each ordered pair (a, b) ∈ T P , we add token passing constraints between (a, b), denoting token may be passed from a to b. Step 7: Optionally, we add constraints CBil ≤ ctk ≤ CBiu to bound the number of times a token could be passed to a specific thread model Mi , with CBil and CBiu corresponding to user-provided lower and upper context-bounds, respectively. Step 8: We generate verification conditions (discussed in Section 2.1) comprising transition relation of each thread model, token-passing constraints, context-bounding constraints (optionally), and environmental assumptions and negated property constraints. These constraints are expressed in a quantifier-free formula and passed to a SMT/SAT solver for a satisfiability check.

5 Generating MATs Notation Shortcuts: Before we get into details, we make some notation abuse for ease of readability. When there is no ambiguity, we use ei to also indicate c(ei ), the control state of thread Mi where the access event ei belongs. Further, we use +ei to denote the event immediately after ei in program order, i.e., c(+ei ) = next(c(ei )). Similarly, we use −ei to denote event immediately preceding ei , i.e., c(ei ) = next(c(−ei )). We sometimes refer to tuple (a, b) as a pair. We provide a simple procedure, GenM AT (Algorithm 1) for generating MAT ij , given a pair of unrolled threads Mi and Mj and dependency relation D. For ease of explanation, we assume the threads are unrolled for some bounded depth, and there is no conditional branching. (For a further discussion with conditional branching, please refer [26]). We first initialize a queue Q with control state pair (i , j ) representing the beginning of the threads, respectively. For any pair (fi , fj ) in the Q, representing the current control pair locations, we can obtain a MAT m
= (tri
, trj
) as follows: we start tri
and trj
from fi and fj respectively, and end in li
and lj
respectively, such that (li
, lj
) ∈ D, and there is no other conflicting pair in-between. There may be many MATcandidates m
. Let Mc denote a set of such choices. The algorithm selects m ∈ Mc uniquely by assigning thread priorities and using the following selection rule. If a thread Mj is given higher priority over Mi , the algorithm prefers m = (tri = fi · · · li , trj = fj · · · lj ) over m
= (tri
= fi · · · li
, trj
= fi · · · lj
) if lj ≺po lj
. Note, the choice of Mj over Mi is arbitrary, but is required for the optimality result. We presented MAT selection (lines 7–9) in a declarative style for better understanding. However, algorithm finds the unique MAT using the selection rule, without constructing the set Mc . We show later that GenM AT can always find such a unique MAT with the chosen priority (lines 7—9).

78

M.K. Ganai and S. Kundu #I 1

p∈Q\Q’ (1a,1b)

2

(4a,1b)

3

(1a,3b)

4

(4a,3b)

5

(2a,3b)

MAT

12

⇒

(1a 3a,1b

⇒2b)

⇒ ⇒ (4a,3b⇒4b) (2a⇒4a,3b ⇒4b)

I

Q\Q’

Fork Constraints

(1a,1b)

W(y)

1a

1b

R(x)

(4a,1b)(1a,3b) (4a,3b)

R(x)

2a

2b

W(z)

R(z)

3a

3b

R(x)

W(y)

4a

4b

W(y)

(4a,1b 4b)

(1a,3b)(4a,3b)

(1a,3b 4b)

(4a,3b)(2a,3b) (2a,3b)

MAT

Token Passing pair-set (TP( 12))= {(2b,1a)(3a,1b)(4a,1b)(4b,4a),(1a,3b)(4b,1a) (4a,3b)(4b,2a)}

E

Join Constraints

#pair-wise constraints = 8

Fig. 4. Run of GenM AT on example in Figure 1(a)

We update MAT ij with m. If (li  =i ) and (lj  =j ), we update Q with three pairs, i.e., (+li , +lj ), (+li , fj ), (fi , +li ); otherwise, we insert selectively as shown in the algorithm (lines 11—15). Example: We present a run of GenM AT in Figure 4 for the example in Figure 1(a). We gave M2 higher priority over M1 . The table columns provide each iteration step (#I), the pair p ∈ Q\Q
selected, the chosen MAT 12 , and the new pairs added in Q\Q
(shown in bold). We add token-passing constraints (shown as directed edges) in the figure (on the right) between every ordered pair in the set T P (MAT 12 ). Total number of pair-wise constraints we add is 8, much less compared with all pair-wise constraints (in Figure 1). The fork/join constraints, shown as dotted edges, provide happens-before ordering between the accesses. In the first iteration of the run, out of the two MAT candidates m = (1a · · · 3a, 1b · · · 2b) and m
= (1a, 1b · · · 4b) (also shown in Figure 2(a)-(b)) GenM AT selects m, as M2 is given higher priority over M1 and 2b ≺po 4b. In the following section, we show the adequacy and optimality of the pair-wise constraints so obtained. Theorem 1. The algorithm GenM AT terminates. Proof. For bounded depth, number of pair-wise accesses are bounded. As each control state pair is picked only once (line 6), the procedure terminates.  

6 MAT-Based Reduction: Optimality and Adequacy For ease of understanding, we first present optimality and adequacy results for a twothreaded system i.e., Mi and Mj with i, j ∈ {1, 2}. For two-threaded system, Shij = (Shi ∪ Shj ), and as noted earlier, eT Pij = ∅. We ignore it for now; we discuss the general case later as the proof arguments are similar. Theorem 2 (Two-threaded Optimality). For two-threaded system with bounded unrolling, the set T P = T P (MAT ij ) is optimal i.e., it does not allow two equivalent schedules.

Reduction of Verification Conditions for Concurrent System Using MAT

79

Algorithm 1. GenM AT : Obtain a set of MATs 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17:

input: Unrolled Thread Models: Mi , Mj ; Dependency Relation D output: MAT ij . MAT ij := ∅; Q := {(i , j )}; Q
:= ∅ {Initialize Queue}; while Q  = Q
do Select (fi , fj ) ∈ Q\Q
Q := Q\{(fi , fj )}; Q
:= Q
∪ {(fi , fj )} MAT-candidates set, Mc = {m
| m
= (tri
= fi · · · li
, trj
= fj · · · lj
) is M AT }, Select a MAT m = (tri = fi · · · li , tri = fj · · · lj ) ∈ Mc such that
∀m
∈Mc ,m
 =m lj ≺po lj , (i.e., Mj has higher priority). MAT ij := MAT ij ∪ {m} if (li =i ∧lj =j ) then continue; elseif (li =i ) then q := {(fi , +lj )}; elseif lj =j ) then q := {(+li , fj )}; else q := {(+li , +lj ), (+li , fj ), (fi , +lj )}; Q := Q ∪ q; end while return MAT ij

Lemma 1. If (ai , aj ) ∈ T P (MAT ij ), then ∃m = (a
i · · · ai , aj · · · a
j ) ∈ MAT ij where i po a
i po ai and aj po a
j po j . Lemma 2. From a given pair (fi , fj ) ∈ Q, given possible MAT candidates m1 = (fi · · · ei , fj · · · ej ) or m2 = (fi · · · e
i , fj · · · e
j ), GenM AT selects only one of them, i.e., either m1 ∈ MAT ij or m2 ∈ MAT ij , but not both. Further, if the thread Mi is given higher priority than Mj , m1 is selected if (ei ≺po e
i ), otherwise m2 is selected. Optimality Proof. We show the optimality by arguing the contrapositive holds, i.e., if two schedules allowed by T P (MAT ij ) are equivalent, then they are same. We explain our proof steps using the Figure 5(a). Consider two equivalent schedules, i.e., σ1  σ2 . We assume that the necessary interleaving pairs for the two schedules be captured by the MAT set, i.e., CSP (σ1 ) ⊆ T P (MAT ij ), and CSP (σ2 ) ⊆ T P (MAT ij ). We show σ1 = σ2 by contradiction. Assume σ1  = σ2 , i.e., CSP (σ1 )  = CSP (σ2 ). Wlog, let σ1 = wi1 · wj1 · · · wik · wjk · · · win ·wjn and σ2 = vi1 ·vj1 · · · vik ·vjk · · · vin ·vjn , a sequence of words, wik , vik ∈ Σi∗ , wjk , vjk ∈ Σj∗ , 1 ≤ k ≤ n. (Note, if the words do not align, we pick the schedule with fewer words, say σ1 , and prefix it with empty words corresponding to each thread.) Starting from the end, let the difference first show up at the k th word, i.e., wjk  = vjk , t t t t and ∀t k < t ≤ n, wi = vi , wj = vj .
Let wjk = fjk · · · ljk and vjk = fjk · · · ljk . Note, both words end with the same access
event because the interleaving pairs matches till that point. Wlog, we assume fjk ≺po
fjk . Similarly, we have wik = fik · · · lik , and vik = fik · · · lik . Note, lik immediately precedes (in program order) wik+1 , i.e., lik = −wik+1 [1] (Recall, w[1] denotes the first event in word w). If k = 1, we get a trivial contradiction as wi2 = vi2 implies wi1 = vi1 . Therefore, we only need to consider k > 1. Further, as wjk+1 = vjk+1 , we have |vjk |  = 0 implies

80

M.K. Ganai and S. Kundu

fik

Mi

Mj fik lj(k-1)’ fjk’ f ljk-1 e fjk bik pjk

≤po e ≤po bik ≤po lk
Mi

Mj lj(k-1)’=-fjk’ < fjk’ ≤ po f ≤po ljk-1= -fjk fjk ≤po pjk ≤po

≅

Optimality Claims 1. (lik, pjk) ∈D 2. (f, e) ∉D 3. (f’,lj(k-1)) ∈D 4. ¬(ljk-1,fik) ∈TP∧(lik,fik’)∈TP)

Mj

σ2

lj k

≤po

≤po

lik-1 fjk aj +aj -fjk’ fjk’

cik ai

<po

lik fik+1

Mi

Mj ejk-1 ≤po lik-1 fjk aj ≤ po +aj -fjk’ k fj ’ ≤po rj

≤po

≤po

ai +ai lik

≤po

rj

<po ≤po

qi

≤po

qi

ljk

σe Conflict pair Program order (<,≤) Not established token passing order Established token passing order

fik

ejk-1

≤po

f’ ljk

σ1

Mi

+ai

lik fik+1

f’

fik

σ’e

ljk

Adequacy Claims

1. 2. 3. 4.

fjk <po fjk’ Case 1: ∃(ai, aj)∈D (lik, rj’) ∈ D (-fjk’,+a’i)∈TP (qi,f) ∈ D Case 2 : ∀ (ai, aj) ∉D (-fjk’,fik) ∈ TP

⇒

(a)

(b)

Fig. 5. (a) Optimality claim: σ1 σ2 ⇒ σ1 =σ2 (b) Adequacy claim: CSP(σ1 ) ⊆ T P (MAT ij )

|wjk |  = 0 (Note, |vjk |  = 0 implies j po −vjk+1 [1], which implies j po −wjk+1 [1], which implies |wjk |  = 0). Similarly, as wik+1 = vik+1 , |vik |  = 0 implies |wik |  = 0. As σ1 is a schedule prefixed with empty words, |wjk |  = 0 implies |vjk |  = 0, and |wik |  =0 k k implies |vi |  = 0. Thus, we only need to consider |vj |  = 0 where k > 1.


Claim 1: ∃pkj fjk ≺po fjk po pkj po ljk , s.t. (lik , pkj ) ∈ D.





As (lik , fjk ) ∈ T P (MAT ij ), ∃m1 = (bki · · · lik , fjk · · · pkj ) ∈ MAT ij with (lik , pkj ) ∈ D,
k bi po lik and fjk po pkj (as per lemma 1).

Further, fjk po pkj . If not, i.e., pkj ≺po fjk , then pkj ≺σ1 lik , and lik ≺σ2 pkj . Since, (lik , pkj ) ∈ D, we get σ1   σ2 (contradicting our assumption).


Claim 2: ∀f fjk po f ljk−1 (= −fjk ), and ∀e fik po e po lik s.t. (f, e)  ∈ D. For such f and e, we have f ≺σ1 e and e ≺σ2 f . Since σ1  σ2 , the claim (f, e)  ∈D follows. Claim 3: ∃f
lik ≺po f
s.t. (f
, ljk−1 ) ∈ D. Since (ljk−1 , fik ) ∈ T P (MAT ij ), ∃m2 = (fik · · · f
, f · · · ljk−1 ) ∈ MAT ij (as per lemma 1). Thus, (f
, ljk−1 ) ∈ D. Using claim 2, we have lik ≺po f
as well.


Claim 4: ¬((ljk−1 , fik ) ∈ T P (MAT ij ) ∧ (lik , fjk ) ∈ T P (MAT ij )), i.e., ¬(m1 ∈ MAT ij ∧ m2 ∈ MAT ij ).
Note, bki , fik po lik ≺po f
, and f, fjk po ljk−1 ≺po pkj . Applying lemma 2, following holds: with Mi higher priority, m2 will not be chosen as lik ≺po f
, and with Mj higher priority, m1 will not be chosen as ljk−1 ≺po pkj . Thus, the claim follows.   Theorem 3 (Two-threaded Adequacy). For two-threaded system with bounded unrolling, the set T P = T P (MAT ij ) is adequate.

Reduction of Verification Conditions for Concurrent System Using MAT

σ

(1a,3b) ∈ TP(

σe

12)

(4b,2a) ∈ TP(

MAT

12)

1a:W(y) 1b:R(x) 2b:W(z) 3b:R(x) 4b:W(y) 2a:R(x) 3a:R(z) 4a:W(y)

≅ σ’ ≅

MAT

1a:W(y) 1b:R(x) 2b:W(z) 2a:R(x) 3a:R(z) 3b:R(x) 4b:W(y) 4a:W(y) right move right move 1a:W(y) 1b:R(x) 2b:W(z) 2a:R(x) 3b:R(x) 4b:W(y) 3a:R(z) 4a:W(y)

MAT

Edges are token passing pairs in TP(

12)

right move 1b:R(x) 2b:W(z) 1a:W(y) 3b:R(x) 4b:W(y) 2a:R(x) 3a:R(z) 4a:W(y) 1a:W(y) 1b:R(x) 2b:W(z) 3b:R(x) 4b:W(y) 2a:R(x) 3a:R(z) 4a:W(y)

81

σe ≅ σ’e

(2b,1a) ∈ TP

(a)

(b)

Fig. 6. (a) Equivalent sched. σ, σ
, σe at each step of GenEqv. (b) Run of adequacy proof.

Proof Sketch: Equivalently, we claim that the token-passing constraints added between every pairs in T P (MAT ij ) adequately captures all sequentially consistent schedules. In the first step, we construct a procedure GenEqv (algorithm 2) to obtain an equivalent schedule σ
 σ, which is also a unique representative of the equivalence class. Second, we use that equivalent schedule σ
to show CSP (σ
) ⊆ T P (MAT ij ). Example: Given a schedule σ shown in Figure 6(a), we obtain equivalent schedules σ
and σe by right moving (shown as dotted edges) the last access of a word that does not conflict with the adjacent right word. Note, we use (1a : W (y)) to denote a write access on variable y at control state 1a, and similarly, the rest are denoted. We give the proof details later, but first present required lemmas whose proofs follow from the construction of GenEqv and GenM AT . (Please refer [26] for details). Lemma 3. σe = GenEqv(σ)  σ. Further, for σe = vi1 · vj1 · ·vin · vjn , the last event of a non-empty word is dependent on some access in the right adjacent non-empty word. Lemma 4. For some k < n, if |vik | = 0, |vik+1 |  = 0, then for 1 ≤ t ≤ k, |vit | = 0, h and for k < h ≤ n, |vi |  = 0. In other words, σe can have prefix of empty words, but remaining ones are non-empty. Lemma 5. Procedure GenEqv always terminates. Lemma 6. If (fi · · · ei , fj · · · ej ) ∈ MAT ij , then (1) (ei , ej ) ∈ D, (2) (fi , fj ) ∈ Q, (2) if ei  =i , (+ei , fj ) ∈ Q (4) if ej  =j , (fi , +ej ) ∈ Q (5) if ei  =i ∧(ej  =j ), (+ei , +ej ) ∈ Q (6) (ei , fj ), (ej , fi ) ∈ T P (MAT ij ). Lemma 7. For every pair (fi , fj ) ∈ Q, there is a MAT candidate, m = (fi · · · ei , fj · · · ej ), where (ei , ej ) ∈ D, and fi po ei , and fj po ej . Lemma 8. Given a pair (fi , fj ) ∈ Q, and a reachable pair (ei , ej ) ∈ D there exists a MAT (fi
· · · ei , fj
· · · ej ) ∈ MAT ij , where fi po fi
po ei , fj po fj
po ej and (fi
, fj
) ∈ Q. Lemma 9. Given a pair (fi , fj ) ∈ Q, and a reachable pair (ei , ej ) ∈ D, then (a) (ei , fj ) ∈ T P (MAT ij ) if Mi is given higher priority. (b) (ej , fi ) ∈ T P (MAT ij ) if Mj is given higher priority.

82

M.K. Ganai and S. Kundu

Algorithm 2. GenEqv: Obtain an equivalent schedule 1: input: A sequence of words, σ = wi1 · wj1 · ·win · wjn , wik ∈ Σi∗ , wjk ∈ Σj∗ , 1 ≤ k ≤ n. 2: output: σe ( σ). 3: repeat 4: Do one of the following, A or B 5: A Right move the last access event lik of the word wik (k ≤ n) to the beginning of the word wik+1 if lik is either independent of all events in wjk or |wjk | = 0 6: B Right move the last access event ljk of wjk (k < n) to the beginning of the word wjk+1 if ljk is independent of all events in wik+1 or |wik+1 | = 0. 7: until neither A nor B occurred 8: return σe

Adequacy Proof. We explain our proof using the Figure 5(b). We first obtain an equivalent schedule σe = GenEqv(σ) such that σe = vi1 · vj1 · · · vin · vjn . We remove the prefix empty words, and assume that |vi1 |  = 0. Using lemma 4, we have vik  = 0, vjk  =0 th for 1 ≤ k ≤ n. Assume that all interleaving pairs up to k word are captured in the set T P (MAT ij ), i.e., ∀t k < t ≤ n, we have (lit , fjt ) ∈ T P (MAT 12 ) and ∀h k ≤ h < n, we have (ljh , fih+1 ) ∈ T P (MAT 12 ). Let (lik , fjk )  ∈ T P (MAT ij ), but

(lik , fjk ) ∈ T P (MAT ij ), fjk  = fjk .


Claim 1: fjk ≺po fjk . Also, thread Mj is given higher priority over Mi in selecting MAT.

From the lemma 3, we have (aki , −fjk ) ∈ D, were fik po aki po lik . From the
lemma 6-8, we have ∃ai ai po aki s.t. (ai , fjk ) ∈ Q If we give Mi higher priority, we have (lik , fjk ) ∈ T P (MAT ij ), with (ai , fjk ) ∈ Q, and (lik , rjk ) ∈ D (using lemma 6, 9). This contradicts our assumption (lik , fjk )  ∈ T P (MAT ij ). Thus, we can not give
k k
Mi higher priority. Since fj  = fj , the claim fjk ≺po fjk follows. Claim 2: ∃rj ∀aj fjk po aj ≺po rj po ljk s.t. (lik , rj ) ∈ D and (lik , aj )  ∈ D. k From the lemma 3, we clearly have fj po rj . From claim 1, we have fjk ≺po rj .


Claim 3: ∃f fjk po f ≺po fjk , ∃qi lik ≺po qi , s.t. (qi , f ) ∈ D. If not true, then we move to the (k − 1)th word, as the schedules are equivalent up to k th word.


Claim 4: (−fjk , fik ) ∈ T P (MAT ij ).
We have fik ≺po qi (from claim 3), and fjk po −fjk (from claim 1). Using lemma 3, ∃ek−1 ek−1 ≺po fjk s.t. (−fik , ek−1 )) ∈ D. From (fik , +ek−1 ) ∈ Q (lemma 6), j j j j k
k with Mj higher priority (claim 1), the claim (−fj , fi ) ∈ T P (MAT ij ) holds (using lemma 9).


Case Scenario 1: fik · · · lik conflicts with fjk · · · − fjk .
Since (lik , −fjk )  ∈ D (claim 2), there ∃(aki , akj ) ∈ D, such that +aki · · · lik does not

conflict with +akj · · · − fjk , where fik ≺po aki ≺po lik and fjk po akj ≺po −fjk . Note,

Reduction of Verification Conditions for Concurrent System Using MAT

83




we have (+aki , +akj ) ∈ Q (lemma 6). Since (qi , −fjk ) ∈ D (claim 3), and with Mj
higher priority (claim 1), (−fjk , +aki ) ∈ T P (MAT ij ) (lemma 9). We rearrange the schedule σe (as shown in Figure 5(a)) to obtain an equivalent σe
= 1 vi · vj1 · · · vjk−1 · vi
· vj
· vi

· vj

· vjk+1 · vjk+1 · · · vin · vjn where vi
= fik · · · aki and


vj
= fjk · · · − fjk , and vi

= +aki · · · lik , and vj

= fjk · · · ljk . Note, (−fjk , +aki ) ∈
T P (MAT ij ) (by above argument) and (lik , fjk ) ∈ T P (MAT ij ) (by assumption). (k+1)

For the subsequence of σe
, vj
· vi

· vj

· vjk+1 · vj · · · vin · vjn , we have established that all the interleaving pairs are captured in the set T P (MAT ij ). We then obtain a prefix
subsequence σes = vi1 · vj1 · · · vjk−1 · vi
· vj
· vi

. Note, the last access of vi
, i.e., may not have conflict with vj
, but vi
and vj
are in conflict (case assumption). Therefore, we

obtain σese = GenEqv(σes ), and then reapply our above arguments on σe
.


Case Scenario 2: fik · · · lik does not conflict with fjk · · · − fjk .

We have (−fjk , fjk ) ∈ T P (MAT ij ) (claim 4) and (lik , fjk ) ∈ T P (MAT ij ) (by assumption). We rearrange the schedule σe to obtain an equivalent σe
= vi1 ·vj1 · · · vjk−1 ·
vj
· vi
· vik+1 · vjk+1 · · · vin · vjn where vj
= fjk · · · − fjk , and vi
= fik · · · lik . We apply
our above arguments on the subsequence of σes = vi1 · vj1 · · · vjk−1 .   Example: We show a run of the adequacy proof in Figure 6(b) on a schedule σ shown in Figure 6(a). We first apply procedure GenEqv to obtain σe . The solid edges show the token passing pairs in T P (MAT 12 ). Starting from left on σe , we find that the control state pair (4b, 2a) ∈ T P (MAT 12 ), but (1a, 1b)  ∈ T P (MAT 12 ). As 1a : W (y) not in conflict with 1b : R(x) · · · − 4b : W (y), we apply the Case Scenario 2, and rearrange the schedule as shown in σe
by right moving access 1a : W (y) after 2b : W (z). Note, (2b, 1a) ∈ T P (MAT 12 ), as (2b : W (z), 3a : R(z)) ∈ D. 6.1 Optimality and Adequacy for Multi-threaded System


For a thread pair Mi , Mj if Shij
(Shi ∪ Shj ) holds, then the set i=j T Pij is not adequate. This can happen for a schedule if a token passes from Mi or Mj to a conflicting access in another thread k  = i, j on a shared variable v ∈ (Shi ∪Shj )\Shij . We illustrate it with the following example. Example: Consider a three-threaded system with threads Ma , Mb and Mc communicating with shared variables x, y, and z as shown in Figure 7(a), and the corresponding pair-wise token-passing sets T Pab , T Pbc , and T Pac computed using GenM AT procedure. Consider a schedule σ as shown in the figure. One can obtain an equivalent schedule σe by performing right moves. (The procedure GenEqv can be modified to obtain σe for general case.) One can verify that the schedule σe can not be captured by the computed sets due to missing token-passing pairs such as (3a, 2b). This non-adequacy arise from the following observation: As y  ∈ Shab , the procedure GenM AT ignores any interference on such variables by the thread Mc , while considering threads Ma and Mb . Therefore, the token passing pair (3a, 2b) is not added in T Pab while considering the MAT (2a ⇒ 3a, 1b ⇒ 3b), although (1b, 1c) is added in T Pbc as y ∈ Shbc . To overcome that scenario, we propose the following construction GenExtraT P that uses MAT ij to generate eT Pij by adding token-passing pairs for such cases.

84

M.K. Ganai and S. Kundu

Ma

Mb

Mc

1a

W(x)

1b

R(y)

1c

W(y)

2a

W(z)

2b

R(x)

2c

R(z)

3a

┤a

3b

┤b

3c

┤c

Shab := {x} Shbc := {y} Shac := {z}

Sha := {x,z} Shb := {x,y} Sha := {y,z}

σ

MAT MAT MAT

TPab:=TP( TPbc:=TP( TPac:=TP(

{(1a,1b)(2b,1a)(3a,1b)(3b,2a)(3b,1a)(3a,3b)} {(1b,1c)(1c,1b)(3c,1b)(3b,2c)(3b,1c)(3c,2b)} ac)= {(2a,1c)(2c,1a)(3a,1c)(3c,3a)(3c,1a)(3a,3c)}

Token passing through some threads Mk, k≠i,j fi

fj

eTPab := {(1a,2b)(3a,2b)(3b,3a)} eTPbc := {(3b,3c),(3c,3b)} eTPac := {(2c,2a)(2a,2c)(3c,2a),(3a,2c)}

1a:W(x) 1b:R(y) 1c:W(y) 2c:R(z) 2a:W(z) 2b:R(x)

≅

σe

ab)=

bc)=

mj +mj

3a

3b

3c

2b:R(x)

3b

3c

li

lj

right moves 1b:R(y) 1c:W(y) 2c:R(z) 1a:W(x) 2a:W(z) (1b,1c) ∈ TPab

(2c,1a) ∈ TPac

3a

(3a,2b) ∈ eTPab

Mi

Mj

(3b,3c) ∈ eTPbc

(a)

(b)

Fig. 7. (a) Adequacy for a 3-thread example, (b) Example used in the proof

eT Pij = {(li ,+mj ), (lj , +mi )|(fi ⇒ li , fj ⇒ lj ) ∈ MAT ij , (fi mi ≺ li ) ∧ ∃k=j ck .(mi , ck ) ∈ T Pik ∧¬∃cj .(mi , cj ) ∈ T Pij , (fj mj ≺ lj ) ∧ ∃k=i ck .(mj , ck ) ∈ T Pjk ∧¬∃ci .(mj , ci ) ∈ T Pij } For the example, we need additional 9 token-passing pairs with a total of 27 such pairs for adequacy, as compared to 54 (=3*18) in all pair-wise approach [17]. Following result shows that the set is optimal as well. Theorem 4 (Optimality and Adequacy). For a multi-threaded system, the set (


∪(

eT Pij ) is both adequate and optimal. i =j


i =j

T Pij )

Proof sketch: The proof arguments are similar to that used in proving Theorems 2 and 3. We provide a proof sketch
here. Adequacy. Consider ( i=j eT Pij ) = ∅. We claim that for every ci such that (mj , ci ) ∈ T Pij , there exists
li such that ci po li , and (li , +mj ) ∈ T Pij . Consider ( i=j eT Pij )  = ∅, i.e., ∃i=j Shij
(Shi ∪ Shj ). Consider a MAT (fi ⇒ li , fj ⇒ lj ) ∈ MAT ij (shown in Figure 7(b)) with (mj , ck ) ∈ T Pik for some k  =j and fj mj ≺ lj . By construction of GenExtraT P procedure, (li , +mj ) ∈ eT Pij . In other words, if a token leaves at mj , it comes back from thread Mi at +mj . We then proceed the proof as follows: Given any schedule σ, we first obtain an equivalent schedule σe by right moving the last access until a fix point (similar to GenEqv procedure).
Then using the
argument similar to proving Theorem 3, we show that CSP (σe ) ∈ ( i=j eT Pij ) ∪ i=j T Pij ). Optimality. Given two equivalent schedules σ1 and σ2 , if CSP (σ1 ), CSP (σ2 ) ⊆
( i=j T Pij ), we show the optimality by applying Theorem 2 on consecutive words in the schedules. Otherwise, w.l.o.g assume (li , +mj ) ∈ CSP (σ1 ) with (li , +mj ) ∈ eT Pij (Figure 7(b)). We claim that the token passing path from mj to li (through some other thread(s)) necessarily contains the pair (mj , ak ) ∈ D with mj ≺ ak . We then show that (li , +mj ) ∈ CSP (σ2 ). Thereby, we show that σ1 = σ2 .  

Reduction of Verification Conditions for Concurrent System Using MAT

85

Table 1. Comparing MAT-based reduction with prior approaches Ex Program Size Unrolled cfg MAT anal. B [17] B+M Ext [16] (S/U) #SA #SV #T #P #PM #MAT Size NCB C1 D Size NCB C1 D Size NCB D E1S (1,4,4) 2 19 48 23 14 32K 00:0 00:0 11 26K 00:0 00:0 11 174K 00:0 14 E2S (2,8,8) 3 29 192 8 4 98K 00:1 00:1 15 18K 00:0 00:0 15 497K 00:2 24 E3S (1,20,20) 2 51 880 591 390 487K 22:1 00:9 27 375K 07:3 00:5 27 1.7M 00:8 46 E4S (2,40,40) 3 93 3520 200 100 1.9M 1550:5 08:5 47 163K 00:2 00:2 47 6.9M 04:2 88 E5U (2,40,40) 3 93 3520 200 100 1.9M TO 13:7 - 163K 50:5 00:2 - 6.9M 99:7 E6S (1,100,100) 2 211 20400 14951 9950 12M TO 497:8 107 8.7M TO 150:8 107 51M MO 206 E7S (2,200,200) 3 413 81600 5000 2500 48M TO TO 207 3.3M TO 16:4 207 256M MO 408 SA - Shared Accesses in each thread. SV - Shared Variables. T - Transitions B: [17] Basic. M: With MAT. Ext: [16]. P: All pair-wise constraints PM : P after MAT NCB: No context bound C1: One context bound. D: Witness depth. MO: Memory out. TO: Time out. Time is in sec:msec.

7 Experiments and Results We implemented our approach in a token-based modeling framework (similar to [17]) (Figure 3), and used the SMT solver Yices-1.0.13 [27]. We conducted our experiments on a linux box with Intel dual core CPU at 2.0 GHz with 1GB RAM running Ubuntu Linux 8.04, using a 1800 secs time limit. We also integrated context-bounding [23] by bounding the clock vector variable ctk. (Recall, such a variable is used to record the number of times the token is exchanged, i.e., number of context-switches). In our experiments, we automatically checked several three-threaded benchmarks of varied complexity with respect to the number of shared variable accesses. The property constraints correspond to assertion violations. All benchmarks are checked at a depth D equal to the longest path in the program (as it is unrolled). We used standard lockset analysis and inferred happens-before relation from fork/join constraints to reduce the size of Cij . The details of the benchmarks are shown in Table 1. Columns 1–4 include the name of benchmarks (Column 1), the number of shared variable accesses in each thread (#SA) (Column 2), the number of shared variables in the program (#SV ) (Column 3), and the number of transitions in the program (#T ) (Column 4). Each benchmark is suffixed with S or U corresponding to the satisfiable (i.e., has a reachable violation) or unsatisfiable instance. For example, benchmark E3S has a reachable violation with three threads with 1, 20, and 20, number of shared accesses, respectively. Also, E3S benchmark has 2 shared variables, and 51 transitions. The rest of the columns describes the comparison results. In Column 5 (unrolled cfg), we provide total number of pair-wise constraints(#P ). In the MAT analysis columns (6—7), we provide number of pair-wise constraints after MAT analysis (#PM ), and number of MAT (#M ). Note, we get significant reduction in (#PM ). In Columns 8—11, we present the results of token-based approach [17] using P constraints, referred to as basic encoding B. In these columns, we provide SMT formula size, time taken (in sec) with no context-bound constraint (N CB), time taken with one contextbound per thread (C1), and the witness length (D) (if any), respectively. As the formula sizes for N CB and C1 are almost the same, and we do not report them separately. In Columns 12—15, we present similar results for our approach using MAT analysis, denoted as B+M, i.e., token-based approach using PM constraints. In Columns 16—18, we

86

M.K. Ganai and S. Kundu

compare our results with the state-of-the-art symbolic approach [16] based on synchronous modeling, referred to as Ext, and present similar results. Since Ext does not support context-bounding, and it is not clear how to add those constraints efficiently, we do not have any reportable data. Our approach using MAT (B+M) outperforms the basic encoding B, and Ext in both performance and size of verification conditions by 1–2 orders of magnitude. Encoding using MATs and context bounding (B+M+C1) can find the SAT instances very quickly, whereas other encoding cannot find it within the time limit. Note, due to synchronous modeling, the witness length D tends to be larger for Ext, also noted in [17].

8 Conclusion We are first to exploit partial order reduction techniques in a symbolic model checking effort that generates verification conditions directly without an explicit scheduler. We discussed a novel approach to reduce verification problem sizes and state space for concurrent systems using MATs. We show that our approach gives both adequate and optimal set of token-passing constraints for a bounded unrolling of threads. Our experimental results demonstrates the efficacy of our approach. In future, we would like to exploit transaction-based reductions [19,20,11] to further reduce necessary token-passing pairs.

References 1. Ramalingam, G.: Context sensitive synchronization sensitive analysis is undecidable. In: ACM Transactions on Programming Languages and Systems (2000) 2. Valmari, A.: Stubborn sets for reduced state space generation. In: Application and theory of petri nets (1989) 3. Peled, D.: All from one, one for all: on model checking using representatives. In: Proc. of CAV (1993) 4. Godefroid, P.: Partial-order Methods for the Verification of Concurrent Systems: An Approach to the State-explosion Problem. PhD thesis (1995) 5. Holzmann, G.: The model checker spin. IEEE Transactions on Software Engineering (1997) 6. Godefroid, P.: Model checking for programming languages using verisoft. In: Proc. of POPL (1997) 7. Andrews, T., Qadeer, S., Rajamani, S.K., Rehof, J., Xie, Y.: ZING: Exploiting program structure for model checking concurrent software. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 1–15. Springer, Heidelberg (2004) 8. Flanagan, C., Godefroid, P.: Dynamic partial-order reduction for model checking software. In: Proc. of POPL (2005) 9. Gueta, G., Flanagan, C., Yahav, E., Sagiv, M.: Cartesian partial-order reduction. In: Boˇsnaˇcki, D., Edelkamp, S. (eds.) SPIN 2007. LNCS, vol. 4595, pp. 95–112. Springer, Heidelberg (2007) 10. Alur, R., Brayton, R.K., Henzinger, T.A., Qadeer, S., Rajamani, S.K.: Partial-order reduction in symbolic state space exploration. In: Grumberg, O. (ed.) CAV 1997. LNCS, vol. 1254, pp. 340–351. Springer, Heidelberg (1997) 11. Kahlon, V., Gupta, A., Sinha, N.: Symbolic model checking of concurrent programs using partial orders and on-the-fly transactions. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 286–299. Springer, Heidelberg (2006)

Reduction of Verification Conditions for Concurrent System Using MAT

87

12. Lerda, F., Sinha, N., Theobald, M.: Symbolic model checking of software. Electronic Notes Theoretical Computer Science (2003) 13. Cook, B., Kroening, D., Sharygina, N.: Symbolic Model Checking for Asynchronous Boolean Programs. In: Godefroid, P. (ed.) SPIN 2005. LNCS, vol. 3639, pp. 75–90. Springer, Heidelberg (2005) 14. Grumberg, O., Lerda, F., Strichman, O., Theobald, M.: Proof-guided UnderapproximationWidening for Multi-process Systems. In: Proc. of POPL (2005) 15. Rabinovitz, I., Grumberg, O.: Bounded model checking of concurrent programs. In: Etessami, K., Rajamani, S.K. (eds.) CAV 2005. LNCS, vol. 3576, pp. 82–87. Springer, Heidelberg (2005) 16. Wang, C., Yang, Z., Kahlon, V., Gupta, A.: Peephole Partial Order Reduction. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 382–396. Springer, Heidelberg (2008) 17. Ganai, M.K., Gupta, A.: Efficient modeling of concurrent systems in bmc. In: Havelund, K., Majumdar, R., Palsberg, J. (eds.) SPIN 2008. LNCS, vol. 5156, pp. 114–133. Springer, Heidelberg (2008) 18. Clarke, E., Grumberg, O., Peled, D.: Model Checking. MIT Press, Cambridge (1999) 19. Stoller, S.D., Cohen, E.: Optimistic synchronization-based state-space reduction. In: Garavel, H., Hatcliff, J. (eds.) TACAS 2003. LNCS, vol. 2619, pp. 489–504. Springer, Heidelberg (2003) 20. Flanagan, C., Qadeer, S.: Transactions for software model checking. In: Garavel, H., Hatcliff, J. (eds.) TACAS 2003. LNCS, vol. 2619. Springer, Heidelberg (2003) 21. Levin, V., Palmer, R., Qadeer, S., Rajamani, S.K.: Sound transaction-based reduction without cycle detection. In: Proc. of SPIN Workshop (2003) 22. Godefroid, P., Pirottin, D.: Refining dependencies improves partial-order verification methods. In: Proc. of CAV (1993) 23. Qadeer, S., Rehof, J.: Context-bounded model checking of concurrent software. In: Halbwachs, N., Zuck, L.D. (eds.) TACAS 2005, vol. 3440, pp. 93–107. Springer, Heidelberg (2005) 24. Lamport, L.: How to make multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers (1979) 25. Mazurkiewicz, A.: Trace theory. Advances in Petric nets (1986) 26. Ganai, M.K.: Conference notes, http://www.nec-labs.com/˜malay/notes.htm 27. SRI. Yices: An SMT solver, http://fm.csl.sri.com/yices

Probabilistic Reachability for Parametric Markov Models
Ernst Moritz Hahn1 , Holger Hermanns1,2 , and Lijun Zhang1 1

Saarland University, Saarbr¨ ucken, Germany INRIA Grenoble – Rhˆ one-Alpes, France

2

Abstract. Given a parametric Markov model, we consider the problem of computing the rational function expressing the probability of reaching a given set of states. To attack this principal problem, Daws has suggested to first convert the Markov chain into a finite automaton, from which a regular expression is computed. Afterwards, this expression is evaluated to a closed form function representing the reachability probability. This paper investigates how this idea can be turned into an effective procedure. It turns out that the bottleneck lies in the growth of the regular expression relative to the number of states (nΘ(log n) ). We therefore proceed differently, by tightly intertwining the regular expression computation with its evaluation. This allows us to arrive at an effective method that avoids this blow up in most practical cases. We give a detailed account of the approach, also extending to parametric models with rewards and with non-determinism. Experimental evidence is provided, illustrating that our implementation provides meaningful insights on non-trivial models.

1

Introduction

Markov processes have been applied successfully to reason about quantitative properties in a large number of areas such as computer science, engineering, mathematics, biological systems. This paper is about parametric Markov processes. In this model class certain aspects are not fixed, but depend on parameters of the model. As an example, consider a communication network with a lossy channel, where whenever a package is sent, it is received with probability x but lost with probability 1 − x. Such a network can be specified in a probabilistic variation of the PROMELA language [2]. In this context, we might aim, for instance, at determining parametric reachability probabilities, i.e., the probability to reach a given set of target states. This probability is a rational function in x. 

This work is supported by the NWO-DFG bilateral project VOSS, by the DFG as part of the Transregional Collaborative Research Center SFB/TR 14 AVACS and the Graduiertenkolleg “Leistungsgarantien f¨ ur Rechnersysteme”, and has received funding from the European Community’s Seventh Framework Programme under grant agreement no 214755.

C.S. P˘ as˘ areanu (Ed.): SPIN 2009, LNCS 5578, pp. 88–106, 2009. c Springer-Verlag Berlin Heidelberg 2009


Probabilistic Reachability for Parametric Markov Models

89

For (discrete-time) Markov chains (MCs), Daws [8] has devised a languagetheoretic approach to solve this problem. In this approach, the transition probabilities are considered as letters of an alphabet. Thus, the model can be viewed as a finite automaton. Then, based on the state elimination [16] method, the regular expression describing the language of such an automaton is calculated. In a postprocessing step, this regular expression is recursively evaluated resulting in a rational function over the parameters of the model. Recently, Gruber and Johannsen [11] have shown, however, that the size of the regular expression of a finite automaton explodes: it is nΘ(log n) where n is the number of states. This excessive growth is not only a theoretical insight, but also a very practical problem, as we will discuss. The goal of this paper is to nevertheless present an efficient and effective algorithm for parametric Markov models. Apart from Markov chains, we also consider extensions with rewards or non-determinism. Our method core is also rooted in the state elimination algorithm. The key difference to [8] is that instead of postprocessing a (possibly prohibitively large) regular expression, we intertwine the state elimination and the computation of the rational function. More precisely, in a state elimination step, we do not use regular expressions to label edges, but label the edges directly with the appropriate rational function representing flow of probabilities. This also means that we do not work on a finite automaton representation, but instead stay in the domain of MCs all along the process. We obtain the rational functions in a way inspired by the evaluation of [8]. But since we do this as early as possible, we can exploit symmetries, cancellations and simplifications of arithmetic expressions, especially if most of the transition probabilities of the input model are constants. In practice, this induces drastic savings in the size of the intermediate rational function representations, and hence is the key to an efficient implementation, as experimental evidence shows. We apply this idea to parametric Markov reward models (MRMs) in which states and transitions are additionally equipped with reward structures, and these reward structures are possibly parametric. We discuss how to compute the expected accumulated reward with respect to a set of target states B. Intuitively, this amounts to the sum of probabilities of paths leading to B, each weighted with the reward accumulated along this path. A direct extension of the state elimination approach does not work for MRMs, as in the final regular expression the probability of individual paths leading to B is lost. Surprisingly, our modified approach for parametric MCs can be extended in a straightforward way to handle reward models. Each time we eliminate a state, the transition probabilities are updated as for the underlying parametric MCs. Notably, we update the reward function corresponding to the weighted sum representing the local expected accumulated rewards. To round off the applicability of our method, we present an extension which can tackle parametric Markov decision processes (MDPs), models which involve both probabilistic and non-determinism choices. Here, we are interested in the maximum probability of reaching a given set of target states. In order to answer this question, we encode the non-deterministic choices via additional binary

90

E.M. Hahn, H. Hermanns, and L. Zhang

parameters, which induce a parametric MC. This is then submitted to the dedicated algorithm for parametric MCs. In all settings, we reduce the state space prior to state elimination, by extending standard strong [9] and weak bisimulation [3] lumping techniques (computing the quotient model for further analysis) to parametric MCs and MRMs. A very important observation is that for parametric MDPs we can apply the lumping on the encoded parametric MC, since this preserves the maximum reachability probability. This allows us to minimise parametric MDPs efficiently. We have implemented the algorithms in our tool Param, including the parametric bisimulation lumping. We illustrate the feasibility of the entire approach on a number of non-trivial parametric MCs, MRMs and MDPs. Our work has connections to several other recent scientific contributions. In [20], Lanotte et al. considered parametric MCs, showing that the problem whether there exists a well-defined evaluation is in PSPACE and whether such an evaluation induces a given reachability probability c is however undecidable. For parametric continuous-time Markov chains, Han et al. [13] have provided approximation algorithms to find valid valuations with respect to time bounded reachability properties. Recently, Damman et al. [7] have extended the approach of [8] to generate counterexamples for MC. The regular expressions generated can be seen as a more compact and structured representation of counterexamples than providing a set of paths. Organisation of the paper. In Section 2 we introduce the parametric models used in this paper. Then, in Section 3, we present our main algorithms for parametric models, and discuss bisimulation minimisation for parametric models and the complexity of our algorithms. We provide experimental results in Section 4. In Section 5, we compare our method to the original approach of Daws. Finally, Section 6 concludes this paper. Proofs can be found in [12].

2

Parametric Models

In this section we present the parametric models which we will use throughout the paper. Firstly, we introduce some general notations. Let S be a finite set. For a relation E ⊆ S × S, let E(s) = {s | (s, s ) ∈ E}, and E −1 (s) = {s | (s , s) ∈ E}. We let V = {x1 , . . . , xn } denote a set of variables with domain R. An evaluation u is a partial function u : V
R. We let Dom(u) denote the domain of u. We say u is total
if Dom(u) = V . A polynomial g over V is a sum of monomials g(x1 , . . . , xn ) = i1 ,...,in ai1 ,...,in xi11 · · · xinn where each ij ∈ N0 and each ai1 ,...,in ∈ R. A rational function f over a set of variables V is a fraction 1 ,...,xn ) f (x1 , . . . , xn ) = ff12 (x (x1 ,...,xn ) of two polynomials f1 , f2 over V . Let FV denote the set of rational functions from V to R. Given f ∈ FV , a set of variables X ⊆ V , and an evaluation u, we let f [X/u] denote the rational function obtained by substituting each occurrence of x ∈ X ∩ Dom(u) with u(x).

Probabilistic Reachability for Parametric Markov Models

91

Definition 1. A parametric Markov chain (PMC) is a tuple D = (S, s0 , P, V ) where S is a finite set of states, s0 is the initial state, V = {v1 , . . . , vn } is a finite set of parameters and P is the probability matrix P : S × S → FV . PMCs have already been introduced in [8,20]. We now define the underlying graph of a PMC. Definition 2. The underlying graph GD of a PMC D = (S, s0 , P, V ) is defined as GD = (S, ED ) where ED = {(s, s ) | P(s, s )  = 0}. We omit the subscript D if it is clear from the context. Based on the above definition, we introduce some more notations. For s ∈ S, we let pre(s) = E −1 (s) denote the set of predecessors of s, and let post (s) = E(s) denote the set of successors of s. We say that s is reachable from s, denoted by reach GD (s, s ), if s is reachable from s in the underlying graph GD . For A ⊆ S, we write reach GD (s, A) if reach GD (s, s ) for any s ∈ A. We omit the superscript GD if it is clear from the context. Now we define the induced PMC with respect to an evaluation: Definition 3. Given a PMC D = (S, s0 , P, V ) and an evaluation u. The induced PMC Du by u is defined by Du = (S, s0 , Pu , V \ Dom(u)) where the transition matrix Pu : S × S → FV is defined by Pu (s, s ) = P(s, s )[Dom(u)/u]. We introduce the notion of well-defined evaluations. A total evaluation u is well defined for D if Pu (s, s ) ∈ [0, 1] for
all s, s ∈ S,and Pu (s, S) ∈ [0, 1] for all s ∈ S where Pu (s, S) denotes the sum s
∈S Pu (s, s ). Intuitively, u is well-defined if and only if the resulting PMC Du is then an ordinary MC without parameters. For well-defined evaluation, state s is called stochastic if Pu (s, S) = 1, substochastic if Pu (s, S) < 1. If Pu (s, S) = 0, s is called absorbing. Let u be a well-defined evaluation, and consider the underlying graphs GD = (S, ED ) and GDu = (S, EDu ). Obviously, it holds that EDu ⊆ ED . We say that the total evaluation function u is strictly well-defined if the equality holds, i.e., EDu = ED . Intuitively, a strictly well-defined evaluation does not destroy the reachability property of the underlying graph. This implies that any edge with function f evaluates to a non-zero probability. As probabilities often correspond to failure probabilities, we often do not need to consider non-strictly well-defined evaluations; we are usually not interested in considering that the probability of a failure is 0 or, at the other hand, that the probability of success is 0. An infinite path is an infinite sequence σ = s0 s1 s2 . . . of states, and a finite path is a finite sequence σ = s0 s1 s2 . . . sn of states. A finite path σ = s0 s1 s2 . . . sn has length |σ| = n. Let first(σ) = s0 denote the first state, and last(σ) = sn denote the last state (for a finite path). A maximal path is either an infinite path or a finite path σ such that last(σ) is absorbing. With σ[i] we denote the ith state of σ. Let Path D denote the set of maximal paths of D, Path fin the set of finite paths. Let Path D (s) (Path D fin (s)) be the set of maximal (finite) paths starting in s. For a finite path σ, we define a rational function Pr D (σ) ∈ FV |σ|−1 by Pr D (σ) = i=0 P(σ[i], σ[i + 1]). For a set of paths C ⊆ Path D fin such that

92

E.M. Hahn, H. Hermanns, and L. Zhang


there are no σ, σ  ∈ C where σ is a prefix of σ  , let Pr D (C) = σ∈C Pr D (σ). The function Pr D can be uniquely extended to the set of paths Path D . For a well-defined evaluation u, Pr D (σ)[V /u] is exactly the probability of the path σ in Du , and Pr Du is the uniquely defined probability measure [24] over the set of paths Path D given a fixed initial state s0 . We omit the superscript D if it is clear from the context. Now we consider the extension of PMCs with rewards: Definition 4. A PMRM is a tuple R = (D, r) where D = (S, s0 , P, V ) is a PMC and r : (S ∪ (S × S)) → FV is the reward function. Intuitively, for states s, s ∈ S, r(s) is the reward gained by visiting s, and r(s, s ) denotes the reward gained if the transition from s to s is taken. Both r(s) and r(s, s ) are rational functions over V . The evaluation u is well-defined and strictly well-defined for R iff it is well-defined and strictly well-defined for D, respectively. We will also use paths as well as the underlying graph of R = (D, r) without referring to D explicitly. Finally, we consider parametric Markov decision processes which are extensions of PMCs with non-deterministic decisions: Definition 5. A parametric Markov decision process (PMDP) is a tuple M = (S, s0 , Act, P, V ) where S, s0 and V are as for PMCs, Act is a finite set of actions. The transition probability matrix P is a function P : S × Act × S → FV . As for PMCs, we introduce the PMDP induced by a valuation function: Definition 6. Given a PMDP M = (S, s0 , Act, P, V ) and an evaluation u, the PMDP induced by u is defined by Mu = (S, s0 , Act, Pu , V \ Dom(u)) where Pu : S × Act × S → FV is defined by Pu (s, a, s ) = P(s, a, s )[Dom(u)/u]. With Act(s) = {a | ∃s ∈ S. P(s, a, s )  = 0} we specify the set of enabled actions of a state. An infinite path of M is an infinite sequence σ = s0 a0 s1 a1 . . ., and a path is a finite sequence σ = s0 a0 s1 a1 . . . sn . The notations maximal path, σ[i], M Path M , Path M (s) and Path M fin , Path fin (s) are defined in a similar way as for PMCs. The non-deterministic choices are resolved by the notion of schedulers. M A scheduler is a function A : Path M fin (s0 ) → Act satisfying: for σ ∈ Path fin (s0 ), A(σ) = a implies a ∈ Act(last (σ)). We say that A is stationary (or called memoryless in the literature) if A depends only on the last state, i.e., A is a function A : S → Act. With MD(M) we denote the set of stationary schedulers of M. A stationary scheduler induces a PMC as follows: Definition 7. Given a PMDP M = (S, s0 , Act, P, V ) and a stationary scheduler A, the induced PMC by A is defined as MA = (S, s0 , PA , V ) where the transition matrix PA : S × S → FV is defined by PA (s, s ) = P(s, A(s), s ). A total evaluation u is called strictly well-defined for M if for each stationary scheduler A ∈ MD(M), u is strictly well-defined for MA . For strictly well-defined evaluation u, let Pr Mu ,A denote the probability measure in the PMC (MA )u .

Probabilistic Reachability for Parametric Markov Models

2.1

93

Bisimulation Relations

A bisimulation is an equivalence relation on states which subsumes states satisfying the same reachability probability properties. Now we extend the standard strong [18] and weak bisimulation [4] relations for Markov models to our parametric setting in an obvious way. Definition 8. Let D = (S, s0 , P, V ) be a PMC and R be an equivalence relation on S. R is a strong bisimulation on D with respect to B if for all s1 Rs2 it holds s1 ∈ B iff s2 ∈ B, and for all C ∈ S/R it holds P(s1 , C) = P(s2 , C) States s1 and s2 are strongly bisimilar, denoted s1 ∼D s2 iff there exists a strong bisimulation R on D. Note that we have operations on functions in the definition, instead of numbers. For PMRMs, strong bisimulation is obtained by additionally requiring that r(s1 ) = r(s2 ) and r(s1 , C) = r(s2 , C) for all C ∈ S/R if s1 Rs2 . Now we give the notion of weak bisimulation: Definition 9. Let D = (S, s0 , P, V ) be a PMC and R be an equivalence relation on S. Let B be a set of target states. R is a weak bisimulation on D with respect to B if for all s1 Rs2 s1 ∈ B iff s2 ∈ B, and 1. If P(si , [si ]R )  = 1 for i = 1, 2 then for all C ∈ S/R, C  = [s1 ]R = [s2 ]R : P(s1 ,C) P(s2 ,C) 1−P(s1 ,[s1 ]R ) = 1−P(s2 ,[s2 ]R ) 2. s1 can reach a state outside [s1 ]R iff s2 can reach a state outside [s2 ]R . We say that states s1 and s2 are weakly bisimilar, denoted s1 ≈D s2 iff there exists a weak bisimulation R on D. Weak bisimulation is strictly coarser than strong bisimulation. To the best of our knowledge, weak bisimulation has not been introduced for Markov reward models. The largest (strong or weak) bisimulation equivalence allows us to obtain the quotient, which is the smallest model bisimilar to the original model. As the reachability properties are preserved under bisimulations, we can work with the quotient instead of the original model.

3

Algorithms

In this section we first present an algorithm for the reachability probability for PMCs. Then, we extend our algorithm to PMRMs and PMDPs in Subsection 3.2 and Subsection 3.3 respectively. In Subsection 3.4 we discuss how to minimise parametric models using bisimulation, and we discuss the complexity of our algorithm in Subsection 3.5. 3.1

Parametric MCs

Let D be a PMC and let B be a set of target states. We are interested in the parametric reachability probability, i.e., the function representing the probability to reach a set of target states B from s0 , for all well-defined valuations. This is defined by Pr D ({σ | σ[0] = s0 ∧ ∃i.σ[i] ∈ B}).

94

E.M. Hahn, H. Hermanns, and L. Zhang

Algorithm 1. Parametric reachability probability for PMCs Require: PMC D = (S, s0 , P, V ) and the set of target states B. State s ∈ B is absorbing. For all s ∈ S, it holds reach(s0 , s) and reach(s, B). 1: for all s ∈ S \ ({s0 } ∪ B) do 2: for all (s1 , s2 ) ∈ pre(s) × post (s) do 1 3: P(s1 , s2 ) = P(s1 , s2 ) + P(s1 , s) 1−P(s,s) P(s, s2 ) 4: eliminate(s) 1 5: return 1−P(s P(s0 , B) 0 ,s0 )

Daws [8] has already solved this problem as follows. First, the PMC is transformed into a finite automaton, with the same initial state, and B as the final states. Transition probabilities are described by symbols from an alphabet of the automaton of the form pq or x representing rational numbers, or variables. Afterwards, based on the state elimination [16] method, the regular expression describing the language of such an automaton is calculated. Then, these regular expressions are evaluated into rational functions representing the probability to finally reach the target states. However, this approach can become very costly, as the length of a regular expression obtained from an automaton is nΘ(log n) [11]. In this section, we present an improved algorithm in which state elimination and the computation of rational functions are intertwined. As we do not compute the regular expressions as an intermediate step anymore, this allows for a more efficient implementation. The reason is that the rational functions can be simplified during the state elimination steps, thus avoiding the blowup of regular expressions. pd pc s1

pa

s

pb

s2

s1

1 pa 1−p p b + pd c

s2

The algorithm is presented in Algorithm 1.. The input is a PMC D and a set of target states B. Since we are interested in the reachability probability, w.l.o.g., we can make the target states absorbing, and remove states (and corresponding edges) not reachable from s0 , or which can not reach B a priori. We note that removing states could induce sub-stochastic states. A usual search algorithm is sufficient for this preparation. In the algorithm +, −, etc. are operations for rational functions, and exact arithmetic is used to avoid numerical problems. The key idea of the algorithm is to eliminate states from the PMC one by one, while maintaining the reachability probability. The elimination of a single state s  ∈ {s0 }∪B is illustrated in the figure above. The labels represent the corresponding transition probabilities. The function eliminate(s) eliminates state s from D. When eliminating s, we consider all pairs (s1 , s2 ) ∈ pre(s)×post (s). After eliminating s, pa pb the new transition probability from s1 to s2 becomes f (s1 , s2 ) := pd + 1−p . The c

Probabilistic Reachability for Parametric Markov Models

95


pa pb pa pb i second term 1−p is the geometric sum ∞ i=0 pa pc pb = 1−pc , which corresponds c to the probability of reaching s2 from s1 through s. Now we discuss the correctness of our algorithm. Consider the simple PMC in the figure above. Assume that we have V = {pa , pb , pc , pd }. For strictly welldefined evaluation, our computed rational function f (s1 , s2 ) is correct, which can be seen as follows. If u is strictly well-defined, we have that ED = EDu , implying that u(pc ) > 0, u(pb ) > 0 and u(pc ) + u(pb ) ≤ 1. This indicates also that the denominator 1 − u(pc ) is not zero. Obviously, for well-defined evaluation u with u(pc ) = 1, our result f (s1 , s2 ) is not defined at all. The problem is that state s can not reach s2 in GDu any more. Now consider another well-defined (but not strictly well-defined) evaluation u satisfying u(pc ) = 0 and u(pb ) = 1. It is easy to check that f (s1 , s2 ) returns the right result in this case. We introduce the notion of maximal well-defined evaluations for this purpose: Definition 10. Assume that the PMC D and set of states B satisfy the requirement of Algorithm 1.. The total evaluation u is maximal well-defined, if it is well-defined, and if for each s ∈ S it holds that reach Du (s, B). This means that under maximal well-defined evaluations we can still reach the set of target states from all states of the model after inserting values into the parametric model according to the evaluation. This does not mean that the reachability probability is 1, because we allow sub-stochastic models. Now we give the correctness of Algorithm 1.. Lemma 1. Assume that the PMC D and set of states B satisfy the requirement of Algorithm 1.. Assume that the algorithm returns f ∈ FV . Then, for maximal well-defined evaluation u it holds that Pr Du (s0 , B) = f [V /u]. The detailed induction-based proof can be found in [12]. We can handle nonmaximal evaluations by reducing it to maximal evaluations. The details are skipped here. 3.2

Parametric MRMs

Let R = (D, r) be a PMRM with D = (S, s0 , P, V ). Let B ⊆ S be a set of target states. We are interested in the parametric expected accumulated reward [19] until B, which is denoted by RR (s0 , B). Formally, RR (s0 , B) is the expectation of the random variable X : σ ∈ Path D (s0 ) → R≥0 which is defined by: X(σ) equals
min{j|σ[j]∈B}−1 0 if first(σ) ∈ B, ∞ if σ[i] ∈ / B for all i, and equals i=0 r(σ[i]) + r(σ[i], σ[i + 1]) otherwise. In Algorithm 2., we extend the algorithm for PMCs to handle PMRMs. The input model is a PMRM R = (D, r) where we have the same requirement of D as Algorithm 1. plus the assumption that the set of target states is reached with probability 1 (can be checked by Algorithm 1.) for the evaluations under consideration. We discuss briefly how other special cases can be dealt with by means of simple search algorithms. As for PMCs, states not reachable from s0 need not be considered. Assume that there exists a state s satisfying the

96

E.M. Hahn, H. Hermanns, and L. Zhang

Algorithm 2. Parametric Expected Reward for PMRM Require: PMRM R = (D, r) with D = (S, s0 , P, V ), the set of target states B. State s ∈ B is absorbing. For all s ∈ S, it holds that reach(s0 , s) and for all maximal well-defined evaluations u it is Pr Du (s, B) = 1 1: for all s ∈ S \ ({s0 } ∪ B) do 2: for all (s1 , s2 ) ∈ pre(s) × post (s) do 1 3: pe = P(s1 , s) 1−P(s,s) P(s, s2 ) re = r(s1 , s) + r(s, s2 ) + r(s) +

4:

P(s,s) 1−P(s,s)

(r(s, s) + r(s))

pe re +P(s1 ,s2 )r(s1 ,s2 ) pe +P(s1 ,s2 )

r(s1 , s2 ) = 6: P(s1 , s2 ) = P(s1 , s2 ) + pe 7: eliminate(s)
P(s ,s) P(s0 ,s0 )P(s0 ,s) 8: return s∈B { 1−P(s00 ,s0 ) (r(s0 )+r(s0 , s))+ (1−P(s 2 (r(s0 , s0 ) + r(s0 ))} 0 ,s0 )) 5:

pc /rc s1

pa /ra

s/rs

pb /rb

pe /re s2

s1

(pe + pd ) / s2



s1

pe re +pd rd pe +pd

 s2

pd /rd

pd /rd Fig. 1. For MRMs: pe =

pa pb 1−pc

, re = ra + rb + rs +

pc 1−pc

(rc + rs )

property that reach(s0 , s) and that ¬reach(s, B). By definition, any path σ containing s would have infinite reward, which implies also that RR (s0 , B) = ∞. Assume that D
satisfies the requirement of the algorithm. In this case we have RR (s0 , B) = σ Pr (σ) · X(σ) where σ ranges over all maximal paths of D. The key part of the algorithm is the adaption of the state elimination algorithm for R. Consider the pair (s1 , s2 ) ∈ pre(s) × post (s). The core is how to obtain the transition reward for the new transition (s1 , s2 ) after eliminating s. Consider Figure 1, where the label p/r of the edge (s, s ) denotes the transition probability and the transition reward of the transition respectively. We construct the transition from s1 to s2 in two steps. In the first step we assume that P(s1 , s2 ) =