The DOI matches its Crossref record; 73 of the 73 references it cites were found in a registry or an index.
A Survey of Statistical Model Checking
Abstract
Interactive, distributed, and embedded systems often behave stochastically, for example, when inputs, message delays, or failures conform to a probability distribution. However, reasoning analytically about the behavior of complex stochastic systems is generally infeasible. While simulations of systems are commonly used in engineering practice, they have not traditionally been used to reason about formal specifications. Statistical model checking (SMC) addresses this weakness by using a simulation-based approach to reason about precise properties specified in a stochastic temporal logic. A specification for a communication system may state that within some time bound, the probability that the number of messages in a queue will be greater than 5 must be less than 0.01. Using SMC, executions of a stochastic system are first sampled, after which statistical techniques are applied to determine whether such a property holds. While the output of sample-based methods are not always correct, statistical inference can quantify the confidence in the result produced. In effect, SMC provides a more widely applicable and scalable alternative to analysis of properties of stochastic systems using numerical and symbolic methods. SMC techniques have been successfully applied to analyze systems with large state spaces in areas such as computer networking, security, and systems biology. In this article, we survey SMC algorithms, techniques, and tools, while emphasizing current limitations and tradeoffs between precision and scalability.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Probability Inequalities for sums of Bounded Random Variables
Hoeffding, W. (1994) · Springer Series in Statistics · doi:10.1007/978-1-4612-0865-5_26 · Cited by 6,666
Probability Inequalities for Sums of Bounded Random Variables
Hoeffding, W. (1963) · Journal of the American Statistical Association · doi:10.1080/01621459.1963.10500830 · Cited by 4,852
Conjectures and Refutations: The Growth of Scientific Knowledge.
Hutchison, T. W., & Popper, K. R. (1964) · Economica · doi:10.2307/2551371 · Cited by 4,197
Conjectures and Refutations: The Growth of Scientific Knowledge.
Hesse, M., & Popper, K. R. (1965) · The Philosophical Quarterly · doi:10.2307/2218271 · Cited by 4,189
Automatic verification of finite-state concurrent systems using temporal logic specifications
Clarke, E. M., Emerson, E. A., & Sistla, A. P. (1986) · ACM Transactions on Programming Languages and Systems · doi:10.1145/5397.5399 · Cited by 3,605
Probability and Statistics With Reliability, Queuing, and Computer Science Applications.
Thompson, W. A., & Trivedi, K. S. (1983) · Journal of the American Statistical Association · doi:10.2307/2288237 · Cited by 2,601
PRISM 4.0: Verification of Probabilistic Real-Time Systems
Kwiatkowska, M., Norman, G., & Parker, D. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22110-1_47 · Cited by 2,361
Statistical Decision Functions
Wald, A. (1949) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177730030 · Cited by 2,176
Sequential Tests of Statistical Hypotheses
Wald, A. (1945) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177731118 · Cited by 1,671
A logic for reasoning about time and reliability
Hansson, H., & Jonsson, B. (1994) · Formal Aspects of Computing · doi:10.1007/bf01211866 · Cited by 1,372
Sequential Tests of Statistical Hypotheses
Wald, A. (1992) · Springer Series in Statistics · doi:10.1007/978-1-4612-0919-5_18 · Cited by 1,345
Bisimulation through probabilistic testing
Larsen, K. G., & Skou, A. (1991) · Information and Computation · doi:10.1016/0890-5401(91)90030-6 · Cited by 1,206
Formal verification of a realistic compiler
Leroy, X. (2009) · Communications of the ACM · doi:10.1145/1538788.1538814 · Cited by 1,187
Exact sampling with coupled Markov chains and applications to statistical mechanics
Propp, J. G., & Wilson, D. B. (1996) · Random Structures and Algorithms · doi:10.1002/(sici)1098-2418(199608/09)9:1/2<223::aid-rsa14>3.0.co;2-o · Cited by 1,159
Model-checking algorithms for continuous-time markov chains
Baier, C., Haverkort, B., Hermanns, H., & Katoen, J.-P. (2003) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2003.1205180 · Cited by 767
Statistical Decision Functions.
Lindley, D. V., & Wald, A. (1951) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2980980 · Cited by 475
Tartakovsky, A., Nikiforov, I., & Basseville, M. (2014) · Chapman & Hall/CRC eBooks · doi:10.1201/b17279 · Cited by 437
Model-checking continuous-time Markov chains
Aziz, A., Sanwal, K., Singhal, V., & Brayton, R. (2000) · ACM Transactions on Computational Logic · doi:10.1145/343369.343402 · Cited by 419
Probabilistic Verification of Discrete Event Systems Using Acceptance Sampling
Younes, H. L. S., & Simmons, R. G. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45657-0_17 · Cited by 373
Sequential Analysis: Hypothesis Testing and Changepoint Detection
Gillard, J. (2015) · Journal of the Royal Statistical Society Series A (Statistics in Society) · doi:10.1111/rssa.12122_5 · Cited by 352
Verifying continuous time Markov chains
Aziz, A., Sanwal, K., Singhal, V., & Brayton, R. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-61474-5_75 · Cited by 344
SEQUENTIAL ANALYSIS: SOME CLASSICAL PROBLEMS AND NEW CHALLENGES
Lai, T. L. (2001) · Cited by 310
Approximate Probabilistic Model Checking
Hérault, T., Lassaigne, R., Magniette, F., & Peyronnet, S. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24622-0_8 · Cited by 295
Statistical Model Checking of Black-Box Probabilistic Systems
Sen, K., Viswanathan, M., & Agha, G. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-27813-9_16 · Cited by 281
Self-citationSample size determination: a review
Adcock, C. J. (1997) · Journal of the Royal Statistical Society: Series D (The Statistician) · doi:10.1111/1467-9884.00082 · Cited by 275
Adaptive Multilevel Splitting for Rare Event Analysis
Cérou, F., & Guyader, A. (2007) · Stochastic Analysis and Applications · doi:10.1080/07362990601139628 · Cited by 266
A Bayesian Approach to Model Checking Biological Systems
Jha, S. K., Clarke, E. M., Langmead, C. J., Legay, A., Platzer, A., & Zuliani, P. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-03845-7_15 · Cited by 239
On Statistical Model Checking of Stochastic Systems
Sen, K., Viswanathan, M., & Agha, G. (2005) · Lecture Notes in Computer Science · doi:10.1007/11513988_26 · Cited by 237
Self-citationA Survey of Applications of Markov Decision Processes
White, D. J. (1993) · Journal of the Operational Research Society · doi:10.1057/jors.1993.181 · Cited by 208
Statistical probabilistic model checking with a focus on time-bounded properties
Younes, H. L. S., & Simmons, R. G. (2006) · Information and Computation · doi:10.1016/j.ic.2006.05.002 · Cited by 193
Lindley, D. V. (1997) · Journal of the Royal Statistical Society: Series D (The Statistician) · doi:10.1111/1467-9884.00068 · Cited by 192
Approximate Model Checking of Stochastic Hybrid Systems
Abate, A., Katoen, J.-P., Lygeros, J., & Prandini, M. (2010) · European Journal of Control · doi:10.3166/ejc.16.624-641 · Cited by 181
Statistical Model Checking for Cyber-Physical Systems
Clarke, E. M., & Zuliani, P. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-24372-1_1 · Cited by 174
VESTA: A statistical model-checker and analyzer for probabilistic systems
Sen, K., Viswanathan, M., & Agha, G. (2005) · Second International Conference on the Quantitative Evaluation of Systems (QEST'05) · doi:10.1109/qest.2005.42 · Cited by 167
Self-citationYmer: A Statistical Model Checker
Younes, H. L. S. (2005) · Lecture Notes in Computer Science · doi:10.1007/11513988_43 · Cited by 160
PMaude: Rewrite-based Specification Language for Probabilistic Object Systems
Agha, G., Meseguer, J., & Sen, K. (2006) · Electronic Notes in Theoretical Computer Science · doi:10.1016/j.entcs.2005.10.040 · Cited by 158
Self-citationGrosu, R., & Smolka, S. A. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-31980-1_18 · Cited by 150
Raz, T. (1992) · SIAM Review · doi:10.1137/1034111 · Cited by 146
Baarir, S., Beccuti, M., Cerotti, D., Pierro, M. D., Donatelli, S., & Franceschinis, G. (2009) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/1530873.1530876 · Cited by 133
PVeStA: A Parallel Statistical Model Checking and Quantitative Analysis Tool
Alturki, M. A., & Meseguer, J. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22944-2_28 · Cited by 112
Model-Checking Markov Chains in the Presence of Uncertainties
Sen, K., Viswanathan, M., & Agha, G. (2006) · Lecture notes in computer science · doi:10.1007/11691372_26 · Cited by 110
Self-citationBayesian statistical model checking with application to Stateflow/Simulink verification
Zuliani, P., Platzer, A., & Clarke, E. M. (2013) · Formal Methods in System Design · doi:10.1007/s10703-013-0195-3 · Cited by 110
Clarke, E. M., Faeder, J. R., LANGMEAD, C. J., Harris, L. A., Jha, S. K., & Legay, A. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88562-7_18 · Cited by 105
Importance Splitting for Statistical Model Checking Rare Properties
Jégourel, C., Legay, A., & Sedwards, S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-39799-8_38 · Cited by 91
MultiVeStA: Statistical Model Checking for Discrete Event Simulators
Vandin, A., & Sebastio, S. (2014) · International ICST Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS) · doi:10.4108/icst.valuetools.2013.254377 · Cited by 77
Srinivasan, R. (2002) · Springer eBooks · doi:10.1007/978-3-662-05052-1 · Cited by 74
How Fast and Fat Is Your Probabilistic Model Checker? An Experimental Performance Comparison
Jansen, D. N., Katoen, J.-P., Oldenkamp, M., Stoelinga, M. I. A., & Zapreev, I. S. (2008) · Springer eBooks · doi:10.1007/978-3-540-77966-7_9 · Cited by 68
Scalable Verification of Markov Decision Processes
Legay, A., Sedwards, S., & Traonouez, L. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-15201-1_23 · Cited by 59
Smart sampling for lightweight verification of Markov decision processes
D’Argenio, P. R., Legay, A., Sedwards, S., & Traonouez, L. (2015) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-015-0383-0 · Cited by 58
Statistical Model Checking Using Perfect Simulation
Rabih, D. E., & Pekergin, N. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-04761-9_11 · Cited by 53
Error Control for Probabilistic Model Checking
Younes, H. L. S. (2005) · Lecture notes in computer science · doi:10.1007/11609773_10 · Cited by 46
Statistical Verification of Probabilistic Properties with Unbounded Until
Younes, H. L. S., Clarke, E. M., & Zuliani, P. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19829-8_10 · Cited by 46
Statistical model checking QoS properties of systems with SBIP
Nouri, A., Bensalem, S., Bozga, M. D., Delahaye, B., Jégourel, C., & Legay, A. (2014) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-014-0313-6 · Cited by 45
Reasoning about MDPs as Transformers of Probability Distributions
Korthikanti, V. A., Viswanathan, M., Agha, G., & Kwon, Y. (2010) · International Conference on the Quantitative Evaluation of Systems (QEST) · doi:10.1109/qest.2010.35 · Cited by 40
Self-citationProbabilistic Verification for “Black-Box” Systems
Younes, H. L. S. (2005) · Lecture notes in computer science · doi:10.1007/11513988_25 · Cited by 40
Statistical Model Checking Based Calibration and Analysis of Bio-pathway Models
Palaniappan, S. K., Gyori, B. M., Liu, B., Hsu, D., & Thiagarajan, P. S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40708-6_10 · Cited by 35
Formal Modeling and Analysis of DoS Using Probabilistic Rewrite Theories
Agha, G., Greenwald, M. B., Gunter, C. A., Khanna, S., Meseguer, J., Sen, K., & Thati, P. (2005) · Cited by 34
Self-citationStatistical Model Checking for Biological ApplicationsPreprint
Zuliani, P. (2016) · Cited by 33
Statistical model checking for biological applications
Zuliani, P. (2014) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-014-0343-0 · Cited by 32
Probabilistic verification and approximation
Lassaigne, R., & Sylvain Peyronnet, D. (2007) · Annals of Pure and Applied Logic · doi:10.1016/j.apal.2007.11.006 · Cited by 29
Sankaranarayanan, S., & Fainekos, G. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33636-2_19 · Cited by 27
Approximate Verification of Probabilistic Systems
Lassaigne, R., & Sylvain Peyronnet, D. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45605-8_16 · Cited by 27
Feedback Control for Statistical Model Checking of Cyber-Physical Systems
Kalajdzic, K., Jégourel, C., Lukina, A., Bartocci, E., Legay, A., Smolka, S. A., & Grosu, R. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-47166-2_4 · Cited by 25
A comparative study of stochastic analysis techniques
Heiner, M., Röhr, C., Schwarick, M., & Streif, S. (2010) · Computational Methods in Systems Biology · doi:10.1145/1839764.1839776 · Cited by 23
Verifying the Evolution of Probability Distributions Governed by a DTMC
Kwon, Y., & Agha, G. (2010) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2010.80 · Cited by 20
Self-citationJha, S. K., & LANGMEAD, C. J. (2012) · BMC Bioinformatics · doi:10.1186/1471-2105-13-s5-s8 · Cited by 17
Towards semantic model composition via experiments
Peng, D., Ewald, R., & Uhrmacher, A. M. (2014) · ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation (PADS) · doi:10.1145/2601381.2601394 · Cited by 15
Approximate Model Checking of PCTL Involving Unbounded Path Properties
Basu, S., Ghosh, A. P., & He, R. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10373-5_17 · Cited by 13
Rare Event Simulation for Highly Dependable Systems with Fast Repairs
Reijsbergen, D., de Boer, P.-T., Scheinhardt, W., & Haverkort, B. R. H. M. (2010) · International Conference on the Quantitative Evaluation of Systems (QEST) · doi:10.1109/qest.2010.39 · Cited by 11
Hölzl, J., & Nipkow, T. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-28756-5_24 · Cited by 9
Performance evaluation of sensor networks by statistical modeling and euclidean model checking
Kwon, Y., & Agha, G. (2013) · ACM Transactions on Sensor Networks · doi:10.1145/2489253.2489256 · Cited by 9
Self-citationImportance Sampling with Unequal Support
Thomas, P. S., & Brunskill, E. (2017) · AAAI Publications (The Association for the Advancement of Artificial Intelligence (AAAI)) · doi:10.1609/aaai.v31i1.10932 · Cited by 8
Cited by
Himeur, Y., Elnour, M., Fadli, F., Meskin, N., Petri, I., Rezgui, Y., Bensaali, F., & Amira, A. (2023) · Artificial Intelligence Review · doi:10.1007/s10462-022-10286-2 · Cited by 541
Relating simulation studies by provenance—Developing a family of Wnt signaling models
Budde, K., Smith, J., Wilsdorf, P., Haack, F., & Uhrmacher, A. M. (2021) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1009227 · Cited by 23
“, in a temporal logic) and automatically be checked [90, 91].”
BackgroundFormal Methods for Autonomous Systems
Wongpiromsarn, T., Ghasemi, M., Cubuktepe, M., Bakirtzis, G., Carr, S., Karabag, M. O., Neary, C., Gohari, P., & Topcu, U. (2023) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000029 · Cited by 17
Conceptual Models in Simulation Studies: Making it Explicit
Wilsdorf, P., Haack, F., & Uhrmacher, A. M. (2020) · 2020 Winter Simulation Conference (WSC) · doi:10.1109/wsc48552.2020.9383984 · Cited by 15
Metadata
- Authors
- Agha, G., & Palmskog, K.
- Venue
- ACM Transactions on Modeling and Computer Simulation
- Published
- 2018-01-31
- Volume
- 28
- Issue
- 1
- Pages
- 1-39
- ISSN
- 1049-3301 (ISSN-L)
- 1558-1195
- OpenAlex
- W2787596386
- Cited by
- 285
- References
- 73
- FWCI
- 22.90
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.