Software model checking
ACM Computing SurveysPublished 1 October 2009
Ranjit Jhala, Rupak Majumdar
Citations419
SJR quartileQ1
SJR score5.80
SNIP11.03
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We survey recent progress in software model checking.
Keywords
Computer Science
Choice Reviews OnlineArtificial intelligence: a modern approach
22,205 Citations1995Stuart Russell, Peter Norvig +2 more
IEEE Transactions on Systems Science and CyberneticsA Formal Basis for the Heuristic Determination of Minimum Cost Paths
12,265 Citations1968Peter Hart, Nils J. Nilsson +1 more
How heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching is described and an optimality property of a class of search strategies is demonstrated.
IEEE Transactions on ComputersGraph-Based Algorithms for Boolean Function Manipulation
8,829 Citations1986Bryant
Experimental results from applying a new data structure for representing Boolean functions and an associated set of manipulation algorithms to problems in logic design verification demonstrate the practicality of this approach.
Lecture notes in computer scienceZ3: An Efficient SMT Solver
6,309 Citations2008Leonardo de Moura, Nikolaj Bjørner
Z3 is a new and efficient SMT Solver freely available from Microsoft Research that is used in various software verification and analysis applications.
Abstract interpretation
6,131 Citations1977Patrick Cousot, Radhia Cousot
The temporal logic of programs
5,586 Citations1977Amir Pnueli
A unified approach to program verification is suggested, which applies to both sequential and parallel programs, and the main proof method is that of temporal reasoning in which the time dependence of events is the basic concept.
Communications of the ACMAn axiomatic basis for computer programming
3,886 Citations1969C. A. R. Hoare
An attempt is made to explore the logical foundations of computer programming by use of techniques which were first applied in the study of geometry and have later been extended to other branches of mathematics by elucidation of sets of axioms and rules of inference.
IEEE Transactions on Software EngineeringThe model checker SPIN
3,736 Citations1997Gerard J. Holzmann
An overview of the design and structure of the verifier, its theoretical foundation, and an overview of significant practical applications are given.
Communications of the ACMSymbolic execution and program testing
2,991 Citations1976James C. King
A particular system called EFFIGY which provides symbolic execution for program testing and debugging is described, which interpretively executes programs written in a simple PL/I style programming language.
The Temporal Logic of Reactive and Concurrent Systems
2,952 Citations1992Zohar Manna, Amir Pnueli
This volume offers an introduction to temporal logic and to the computational model for reactive programs which has been developed by the authors.
Chaff
2,859 Citations2001Matthew W. Moskewicz, Conor Madigan +3 more
The development of a new complete solver, Chaff, is described which achieves significant performance gains through careful engineering of all aspects of the search-especially a particularly efficient implementation of Boolean constraint propagation (BCP) and a novel low overhead decision strategy.
Lecture notes in computer scienceSymbolic model checking
2,843 Citations1996Emma L. Clarke, K. McMillan +2 more
Using symbolic model checking techniques it is possible to verify industrial-size finite state systems and models with more than 10120 states have been verified using special techniques.
Information and ComputationSymbolic model checking: 1020 States and beyond
2,674 Citations1992Jerry R. Burch, E. M. Clarke +3 more
It is shown how the novel mu-calculus model checking algorithm can be used to derive efficient decision procedures for CTL model checking, satisfiability of linear-time temporal logic formulas, strong and weak observational equivalence of finite transition systems, and language containment of finite omega -automata.
Lecture notes in computer scienceAn Extensible SAT-solver
2,610 Citations2004Niklas Eén, Niklas Sörensson
This article presents a small, complete, and efficient SAT-solver in the style of conflict-driven learning, as exemplified by Chaff, and includes among other things a mechanism for adding arbitrary boolean constraints.
Advanced Compiler Design and Implementation
2,312 Citations1997Steven S. Muchnick
Advanced Compiler Design and Implementation by Steven Muchnick Preface to Advanced Topics
Lecture notes in computer scienceDesign and synthesis of synchronization skeletons using branching time temporal logic
2,137 Citations2005Edmund M. Clarke, E. Allen Emerson
It is shown that it is possible to automatically synthesize the synchronization skeleton of a concurrent program from a Temporal Logic specification and it is believed that this approach may in the long run turn out to be quite practical.
Separation logic: a logic for shared mutable data structures
2,127 Citations2003John Reynolds
An extension of Hoare logic that permits reasoning about low-level imperative programs that use shared mutable data structure is developed, including extensions that permit unrestricted address arithmetic, dynamically allocated arrays, and recursive procedures.
Elsevier eBooksTemporal and Modal Logic
1,890 Citations1990E. Allen Emerson
The chapter describes the framework of linear temporal logic, which has been widely employed in the specification and verification of programs and explains how temporal logic structures can be used to model concurrent programs using non-determinism and fairness.
CUTE
1,653 Citations2005Koushik Sen, Darko Marinov +1 more
A method to represent and track constraints that capture the behavior of a symbolic execution of a unit with memory graphs as inputs is developed and an efficient constraint solver is proposed to facilitate incremental generation of such test inputs.
Lecture notes in computer scienceCounterexample-Guided Abstraction Refinement
1,649 Citations2000Edmund M. Clarke, Orna Grümberg +3 more
Systematic design of program analysis frameworks
1,598 Citations1979Patrick Cousot, Radhia Cousot
The systematic and correct design of program analysis frameworks with respect to a formal semantics is devoted to the main elements of the lattice theoretic approach to approximate semantic analysis of programs.
Automatic discovery of linear restraints among variables of a program
1,576 Citations1978Patrick Cousot, Nicolas Halbwachs
Artificial IntelligenceDepth-first iterative-deepening
1,549 Citations1985Richard E. Korf
A depth·first iterative·deepening algorithm is shown to be asymptotically optimal along all three dimmsions for exponential tree searches and is the only known algorithm that is capable of finding optimal solUtions to randomly generated instances of the Fif/un Puzzle within practical resource.
DART
1,501 Citations2005Patrice Godefroid, Nils Klarlund +1 more
DART is a new tool for automatically testing software that combines three main techniques, automated extraction of the interface of a program with its external environment using static source-code parsing, and dynamic analysis of how the program behaves under random testing and automatic generation of new test inputs to direct systematically the execution along alternative program paths.
Lecture notes in computer scienceConstruction of abstract state graphs with PVS
1,471 Citations1997Susanne Graf, Hassen Saı̈di
This paper proposes a method for the automatic construction of an abstract state graph of an arbitrary system using the Pvs theorem prover.
Automated Software EngineeringModel Checking Programs
1,353 Citations2003Willem Visser, Klaus Havelund +3 more
A verification and testing environment for Java, called Java PathFinder (JPF), which integrates model checking, program analysis and testing, and uses state compression to handle large states and partial order reduction, slicing, abstraction and run-time analysis techniques to reduce the state space.
Extended static checking for Java
1,339 Citations2002Cormac Flanagan, K. Rustan M. Leino +4 more
The Extended Static Checker for Java (ESC/Java) is introduced, an experimental compile-time program checker that finds common programming errors and provides programmers with a simple annotation language with which programmer design decisions can be expressed formally.
Lecture notes in computer scienceSpecification and verification of concurrent systems in CESAR
1,277 Citations1982J. P. Queille, Joseph Sifakis
By an example, the alternating bit protocol, the use of CESAR, an interactive system for aiding the design of distributed applications, is illustrated.
Lazy abstraction
1,146 Citations2002Thomas A. Henzinger, Ranjit Jhala +2 more
This work presents an algorithm for model checking safety properties using lazy abstraction and describes an implementation of the algorithm applied to C programs and provides sufficient conditions for the termination of the method.
Precise interprocedural dataflow analysis via graph reachability
1,135 Citations1995Thomas Reps, Susan Horwitz +1 more
The paper shows how a large class of interprocedural dataflow-analysis problems can be solved precisely in polynomial time by transforming them into a special kind of graph-reachability problem.
Studies in cognitive systemsAssigning Meanings to Programs
1,082 Citations1993Robert W. Floyd
This paper attempts to provide an adequate basis for formal definitions of the meanings of programs in appropriately defined programming languages, in such a way that a rigorous standard is established for proofs about computer programs, including proofs of correctness, equivalence, and termination.
Points-to analysis in almost linear time
1,074 Citations1996Bjarne Steensgaard
This is the asymptotically fastest non-trivial interprocedural points-to analysis algorithm yet described and is based on a non-standard type system for describing a universally valid storage shape graph for a program in linear space.
Implementing Mathematics with The Nuprl Proof Development System
995 Citations1986Robert L. Constable, Stuart F. Allen +10 more
This ebook presents full variant of this ebook in DjVu, PDF, ePub, doc, txt forms, and on the website you may read guides and different art eBooks online, either downloading or downloading.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Symbolic model checking: an approach to the state explosion problem
980 Citations1992Kenneth L. McMillan
The S <scp>LAM</scp> project
919 Citations2002Thomas Ball, Sriram K. Rajamani
This work has successfully applied the SLAM toolkit to Windows XP device drivers, to both validate behavior and find defects in their usage of kernel APIs.
Program Analysis and Specialization for the C Programming Language
917 Citations2005Lars Ole Andersen, Peter Lee
This thesis presents an automatic partial evaluator for the Ansi C programming language, and proves that partial evaluation at most can accomplish linear speedup, and develops an automatic speedup analysis.
Model checking for programming languages using VeriSoft
823 Citations1997Patrice Godefroid
This paper discusses how model checking can be extended to deal directly with "actual" descriptions of concurrent systems, e.g., implementations of communication protocols written in programming languages such as C or C++, and introduces a new search technique that is suitable for exploring the state spaces of such systems.
International Journal on Software Tools for Technology TransferModel checking JAVA programs using JAVA PathFinder
800 Citations2000Klaus Havelund, Thomas Pressburger
An effort to formally analyze, using Spin, a multi-threaded operating system for the Deep-Space 1 space craft, and of previous work in applying existing model checkers and theorem provers to real applications.
Information and ComputationReasoning about Infinite Computations
794 Citations1994Moshe Y. Vardi, Pierre Wolper
This work investigates extensions of temporal logic by connectives defined by finite automata on infinite words and shows that they do not increase the expressive power of the logic or the complexity of the decision problem.
Computers & Mathematics with ApplicationsComputer-aided verification of coordinating processes: The automata-theoretic approach
793 Citations1995
EXE
789 Citations2006Cristian Cadar, Vijay Ganesh +3 more
This paper presents EXE, an effective bug-finding tool that automatically generates inputs that crash real code instead of running code on manually or randomly constructed input, and solves the current path constraints to find concrete values using its own co-designed constraint solver, STP.
ACM Transactions on Programming Languages and SystemsParametric shape analysis via 3-valued logic
784 Citations2002Mooly Sagiv, Thomas Reps +1 more
A parametric framework for shape analysis that can be instantiated in different ways to create different shape-analysis algorithms that provide varying degrees of efficiency and precision is presented.
Partial-Order Methods for the Verification of Concurrent Systems: An Approach to the State-Explosion Problem
771 Citations1996Patrice Godefroid, Jan Van Leeuwen +3 more
IEEE Transactions on Software EngineeringA System to Generate Test Data and Symbolically Execute Programs
761 Citations1976Lori A. Clarke
A system that attempts to generate test data for programs written in ANSI Fortran by symbolically executing the path and creating a set of constraints on the program's input variables, which facilitates error detection and being a possible aid in assertion generation and automatic program documentation.
ACM SIGPLAN NoticesAutomatic predicate abstraction of C programs
703 Citations2012Thomas Ball, Rupak Majumdar +2 more
This work presents the first algorithm to automatically construct a predicate abstraction of programs written in am industrial programming language such as C, and its implementation in a tool -- C2BP, part of the SLAM toolkit.
Lecture notes in computer scienceChecking Safety Properties Using Induction and a SAT-Solver
702 Citations2000Mary Sheeran, Satnam Singh +1 more
Some novel induction-based methods are described, and it is shown how they are related to more standard fixpoint algorithms for invariance checking and preliminary experimental results in the verification of FPGA cores are presented.
Symbolic model checking using SAT procedures instead of BDDs
688 Citations1999Armin Biere, Alessandro Cimatti +3 more
This paper applies bounded model checking to equivalence and invariant checking and presents several optimizations that reduce the size of generated propositional formulas in hardware verification.
Lecture notes in computer scienceA Fast Linear-Arithmetic Solver for DPLL(T)
667 Citations2006Bruno Dutertre, Leonardo de Moura
A new Simplex-based linear arithmetic solver that can be integrated efficiently in the DPLL(T) framework by enabling fast backtracking, supporting a priori simplification to reduce the problem size, and providing an efficient form of theory propagation.
Lecture notes in computer scienceAn automata-theoretic approach to linear temporal logic
654 Citations1996Moshe Y. Vardi
The automata-theoretic approach to linear temporal logic uses the theory of automata as a unifying paradigm for program specification, verification, and synthesis and considers the relationships between programs and their specifications as relationships between languages.
Lecture notes in computer scienceReachability analysis of pushdown automata: Application to model-checking
646 Citations1997Ahmed Bouajjani, Javier Esparza +1 more
This work considers the more general class of alternating pushdown systems and uses alternating finite-state automata as a representation structure for sets of their configurations and gives a simple and natural procedure to compute sets of predecessors using this representation structure.
IEEE Transactions on Software EngineeringTypestate: A programming language concept for enhancing software reliability
612 Citations1986Robert E. Strom, Shaula Yemini
The authors introduce a new programming language concept, called typestate, which is a refinement of the concept of type, which determines the subset of operations which is permitted in a particular context.
ACM Transactions on Programming Languages and SystemsTentative steps toward a development method for interfering programs
605 Citations1983Cliff B. Jones
Extensions to the specification method based on postconditions that are predicates of two states and the development methods of operation decomposition and data refinement are proposed for the rigorous development of interfering programs.
International Journal on Software Tools for Technology TransferThe software model checker Blast
594 Citations2007Dirk Beyer, Thomas A. Henzinger +2 more
This paper gives an introduction to Blast and demonstrates, through two case studies, how it can be applied to program verification and test-case generation.
Cloning-based context-sensitive pointer alias analysis using binary decision diagrams
593 Citations2004John Whaley, Monica S. Lam
This paper presents the first scalable context-sensitive, inclusion-based pointer alias analysis for Java programs, and develops a system called bddbddb that automatically translates Datalog programs into highly efficient BDD implementations.
Pointer analysis
580 Citations2001Michael Hind
Issues related to pointer analysis and remaining open problems are described.
ACM SIGPLAN NoticesA static analyzer for large safety-critical software
577 Citations2003Bruno Blanchet, Patrick Cousot +6 more
Dependent types in practical programming
576 Citations1999Hongwei Xi, Frank Pfenning
An approach to enriching the type system of ML with a restricted form of dependent types, where type index objects are drawn from a constraint domain C, leading to the DML(C) language schema, which allows specification and inference of significantly more precise type information, facilitating program error detection and compiler optimization.
Formal Methods in System DesignA stubborn attack on state explosion
572 Citations1992Antti Valmari
The LTL-preserving stubborn set method is presented for reducing the amount of work needed in the automatic verification of concurrent systems with respect to linear-time temporal logic specifications.
Distributed ComputingRecognizing safety and liveness
552 Citations1987Bowen Alpern, Fred B. Schneider
A formal characterization for safety properties and liveness properties is given in terms of the structure of the Buchi automaton that specifies the property.
ESP
544 Citations2002Manuvir Das, Sorin Lerner +1 more
This paper presents a new algorithm for partial program verification that runs in polynomial time and space, and shows that property simulation scales to large programs and is accurate enough to verify meaningful properties.
Communications of the ACMSocial processes and proofs of theorems and programs
535 Citations1979Richard A. De Millo, Richard J. Lipton +1 more
It is argued that formal verifications of programs will not play the same key role in the development of computer science and software engineering as proofs do in mathematics because of the absence of continuity, the inevitability of change, and the complexity of specification.
ACM Transactions on Programming Languages and SystemsSpecifying Concurrent Program Modules
524 Citations1983Leslie Lamport
A method for specifying program modules in a concurrent program is described, based upon temporal logic, but uses new kinds of temporal assertions to make the specifications simpler and easier to understand.
Journal of Computer and System SciencesAutomata-theoretic techniques for modal logics of programs
523 Citations1986Moshe Y. Vardi, Pierre Wolper
Journal of the ACMFast Decision Procedures Based on Congruence Closure
509 Citations1980Greg Nelson, Derek C. Oppen
A simple proof is given that the congruence closure algorithm provides a decision procedure for the quantifier-free theory of equality and the problem of determining the satisfiability of a conjunction of literals becomes NP-complete if the axiomatization of the theory of list structure is changed slightly.
Philosophical Transactions of the Royal Society of London Series A Mathematical and Physical SciencesConstructive mathematics and computer programming
502 Citations1984Per Martin-Löf
If programming is understood not as the writing of instructions for this or that computing machine but as the design of methods of computation that it is the computer’s duty to execute, then it no longer seems possible to distinguish the discipline of programming from constructive mathematics.
Formal Methods in System DesignMemory-efficient algorithms for the verification of temporal properties
498 Citations1992C. Courcoubetis, M. Vardi +2 more
Algorithms are presented that solve the emptiness problem without explicitly constructing the strongly connected components of the graph representing the product automaton by allowing the algorithms to err with some probability.
IEEE Transactions on Software EngineeringProofs of Networks of Processes
497 Citations1981Jayadev Misra, K. Mani Chandy
The proof method is based upon specifying a process by a pair of assertions, analogous to pre-and post-conditions in sequential program proving, and the correctness of network specification is proven by applying inference rules to the specifications of component processes.
Formal Methods in System DesignBetter verification through symmetry
491 Citations1996C. Norris Ip, David L. Dill
This work provides a proof of the soundness of the new symmetry-based verification algorithm based on a definition of the formal semantics of a simple description language with scalarsets, and leads to an alternative characterization of data independence.
Iterative context bounding for systematic testing of multithreaded programs
483 Citations2007Madanlal Musuvathi, Shaz Qadeer
This paper proposes iterative context-bounding, a new search algorithm that systematically explores the executions of a multithreaded program in an order that prioritizes executions with fewer context switches, and shows both theoretically and empirically that context-bounded search is an effective method for exploring the behaviors of multith readed programs.
ACM SIGPLAN NoticesAbstractions from proofs
483 Citations2014Thomas A. Henzinger, Ranjit Jhala +2 more
The model checker BLAST is extended with predicate discovery by Craig interpolation, and applied successfully to C programs with more than 130,000 lines of code, which was not possible with approaches that build less parsimonious abstractions.
Science of Computer ProgrammingThe Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems
466 Citations2008Roberto Bagnara, Patricia M. Hill +1 more
The main features of the current version of the Parma Polyhedra Library are presented, emphasizing those that distinguish it from other similar libraries and those that are important for applications in the field of analysis and verification of hardware and software systems.
ACM Transactions on Programming Languages and SystemsComposing specifications
459 Citations1993Martı́n Abadi, Leslie Lamport
This work examines the precise distinction between a system and its environment, and provides the requisite proof rule when modules are specified with safety and liveness properties.
Journal of Symbolic LogicLinear reasoning. A new form of the Herbrand-Gentzen theorem
457 Citations1957William Craig
This paper provides a description of how ascent to A ⊃ A′ from a quantifier-free level will be replaced by movement from A to A′ on the quantificational level, and makes use of a set L of rules of inference, the L-rules.
SIAM Journal on ComputingSoundness and Completeness of an Axiom System for Program Verification
452 Citations1978Stephen Cook
The main new results are the completeness theorem, and a careful treatment of the procedure call rules for procedures with global variables in their declarations.
ACM Transactions on Programming Languages and SystemsConjoining specifications
451 Citations1995Martı́n Abadi, Leslie Lamport
It is shown how to specify components of concurrent systems and considers both the decomposition of a given system into parts, and the composition of given parts to form a system.
Princeton University Press eBooksComputer-Aided Verification of Coordinating Processes
441 Citations1995Robert P. Kurshan
Theories of L-automaton/L-process, L-matrix, and String Acceptors are compared to Boolean Algebra, which describes the construction of language-based Algebra.
ACM SIGPLAN NoticesAnalysis of pointers and structures
432 Citations2004David Chase, Mark N. Wegman +1 more
Automatic predicate abstraction of C programs
432 Citations2001Thomas Ball, Rupak Majumdar +2 more
This work presents the first algorithm to automatically construct a predicate abstraction of programs written in an industrial programming language such as C, and its implementation in a tool — C2BP.
Lecture notes in computer scienceContext-Bounded Model Checking of Concurrent Software
403 Citations2005Shaz Qadeer, Jakob Rehof
This paper proves that the problem of verifying a concurrent boolean program is decidable, even in the presence of unbounded parallelism, if the analysis is restricted to executions in which the number of context switches is bounded by an arbitrary constant.
Liquid types
388 Citations2008Patrick M. Rondon, Ming Kawaguci +1 more
Logically Qualified Data Types, abbreviated to Liquid Types, is a system that combines Hindley-Milner type inference with Predicate Abstraction to automatically infer dependent types precise enough to prove a variety of safety properties.
Formal Methods in System DesignSymmetry and model checking
386 Citations1996E. Allen Emerson, A. Prasad Sistla
This work shows how to exploit symmetry in model checking for concurrent systems containing many identical or isomorphic components, and focuses in particular on those composed of many isomorphic processes.
Lecture notes in computer scienceMOCHA: Modularity in model checking
384 Citations1998Rajeev Alur, T. A. Henzinger +4 more
This paper presents a parallel version of the Celada–Seiden cellular automaton that automates the very labor-intensive and therefore time-heavy and therefore expensive and expensive and therefore computationally burdensome process of integrating these two systems.
MOPS
383 Citations2002Hao Chen, David Wagner
A formal approach for finding bugs in security-relevant software and verifying their absence and experience suggests that this approach will be useful in finding a wide range of security vulnerabilities in large programs efficiently.
Flow-sensitive type qualifiers
377 Citations2002Jeffrey S. Foster, Tachio Terauchi +1 more
An efficient constraint-based inference algorithm is obtained that integrates flow-insensitive alias analysis, effect inference, and ideas from linear type systems to support strong updates.
Lecture notes in computer scienceBebop: A Symbolic Model Checker for Boolean Programs
376 Citations2000Thomas Ball, Sriram K. Rajamani
Bbop represents control flow explicitly, and sets of states implicitly using BDDs, and is able to model check boolean programs with several thousand lines of code, hundreds of procedures, and several thousand variables in a few minutes.
Thorough static analysis of device drivers
376 Citations2006Thomas Ball, Ella Bounimova +7 more
The Static Driver Verifier tool (SDV) uses this engine to find kernel API usage errors in a driver, and discusses the techniques used in SDV to meet these requirements, and empirical results from running SDV on over one hundred Windows device drivers.
Lecture notes in computer scienceLazy Abstraction with Interpolants
371 Citations2006Kenneth L. McMillan
A model checker for infinite-state sequential programs, based on Craig interpolation and the lazy abstraction paradigm, which observes a speedup of up to two orders of magnitude relative to a similar tool using predicate abstraction.
Formal Methods in System DesignProperty preserving abstractions for the verification of concurrent systems
357 Citations1995Claire Loiseaux, Susanne Graf +4 more
Results are given on the preservation of properties expressed in sublanguages of the branching time μ-calculus when two systemsS andS' are related via (α, γ)-simulations, using simulations parameterized by Galois connections.
Model checking and abstraction
348 Citations1992Edmund M. Clarke, Orna Grümberg +1 more
A method for using abstraction to reduce the complexity of temporal logic model checking by constructing an abstract model of a program without ever examining the corresponding unabstracted model is described.
ACM SIGPLAN NoticesTermination proofs for systems code
322 Citations2006Byron Cook, Andreas Podelski +1 more
Formal Methods in System DesignExploiting symmetry in temporal logic model checking
322 Citations1996E. M. Clarke, Reinhard Enders +2 more
What it means for a finite state system to be symmetric is formalized and techniques for reducing such systems when the transition relation is given explicitly in terms of states or symbolically as a BDD are described.
Lecture notes in computer scienceA Local Shape Analysis Based on Separation Logic
311 Citations2006Dino Distefano, Peter W. O’Hearn +1 more
This work describes a program analysis for linked list programs where the abstract domain uses formulae from separation logic in a manner similar to that described in the previous chapter.
ACM Transactions on Computer SystemsUsing model checking to find serious file system errors
309 Citations2006Junfeng Yang, Paul Twohey +2 more
This article shows how to use model checking to find serious errors in file systems by building a system, FiSC, and applying it to four widely-used, heavily-tested file systems: ext3, JFS, ReiserFS and XFS.
Verification of Sequential and Concurrent Programs
307 Citations1991Krzysztof R. Apt, Ernst-Rüdiger Olderog
This widely anticipated third edition provides a systematic exploration of one of the most common approaches to program verification, known as the assertional approach, applied to deterministic and nondeterministic sequential programs of varying complexity, together with both parallel and distributed concurrent programs.
A static analyzer for large safety-critical software
302 Citations2003Bruno Blanchet, Patrick Cousot +6 more
It is shown that abstract interpretation-based static program analysis can be made efficient and precise enough to formally verify a class of properties for a family of large programs with few or no false alarms.
Abstractions from proofs
301 Citations2004Thomas A. Henzinger, Ranjit Jhala +2 more
The model checker Blast is extended with predicate discovery by Craig interpolation, and applied successfully to C programs with more than 130,000 lines of code, which was not possible with approaches that build less parsimonious abstractions.
…