Computer Science ›› 2017, Vol. 44 ›› Issue (Z6): 499-503, 533.doi: 10.11896/j.issn.1002-137X.2017.6A.111

Previous Articles     Next Articles

Efficiency Analysis of Different Statistical Algorithms on Statistical Model Checking

GAO Wan-ling, HONG Mei, YANG Qiu-hui and ZHAO He   

  • Online:2017-12-01 Published:2018-12-01

Abstract: Recently,statistical model checking technology has been widely used,and different statistical algorithms have different effects on the performance of the statistical model checking.This paper mainly compared the running time of different statistical algorithms,thus analyzed the applicable environment of the algorithms.The statistical algorithms include Chernoff algorithm,sequential algorithm,smart aim-listed probability estimation algorithm,smart content testing algorithm and Monte Carlo algorithm.Models are the Wireless LAN (WLAN) and the Dining Philosophers problem,using PLASMA model checking tool for validation.The result shows that different statistical algorithms have different influences on the efficiency of model checking when the environment is different.Sequential algorithm is fit for verifying the reachability of state,and the time performance is the best.Smart content testing algorithm and Monte Carlo algorithm are fit for verifying complex models.This conclusion can help the selection of statistical algorithms in model checking,in order to improve the efficiency of model checking.

Key words: Statistical model checking,Statistical algorithm,WLAN,Dining philosophers,PLASMA

[1] YOUNES H L S,SIMMONS R G.Statistical probabilistic modelchecking with a focus on time-bounded properties[J].Information and Computation (JIC),2006,204(9):1368-1409.
[2] ZULIANI P,PLATZER A,CLARKE E M.Bayesian statistical model checking with application to Stateflow/Simulink verification[J].Formal Methods in System Design,2010,3(2):243-252.
[3] YOUNES H L S,KWIATKOWSKA M,NORMAN G,et al.Numerical vs.statistical probabilistic model checking[J].Software Tools for Technology Transfer (STTT),2006,8(3):216-228.
[4] HENRIQUES D,MARTINS J G,ZULIANI P,et al.Statistical Model Checking for Markov Decision Processes[C]∥International Conference on Quantitative Evaluation of Systems.2012:84-93.
[5] 代声馨,洪玫,郭兵,等.多处理器实时系统可调度性分析的UPPAAL模型[J].软件学报,2015,6(2):279-296.
[6] DAVID A,LARSEN K G,LEGAY A,et al.Schedulability ofHerschel revisited using statistical model checking[J].International Journal on Software Tools for Technology Transfer,2012,7(2):293-307.
[7] HASTINGS W K.Monte Carlo sampling methods using Markovchains and their applications[J].Biometrika,1970,7(1):97-109.
[8] BUCKLEW J.A,Sadowsky,et al.A Contribution To The Theory Of Chernoff Bounds[J].IEEE Transactions on Information Theory,1991,39(1):75-75.
[9] 顾雅娟,仰枫帆.基于修正的切尔诺夫界的尾部概率的估计[C]∥全国青年通信学术会议.2010.
[10] MALLOY M,NOWAK R.Sequential analysis in high-dimen-sional multiple testing and sparse recovery[J].Mathematics,2011,42(4):2661-2665.
[11] http://plasma-lab.gforge.inria.fr/plasma_lab_doc/1.4.0/html/algorithms/mdp.html#smart-sampling-algorithms.
[12] KIM Y,KIM M,KIM T H.Statistical Model Checking for Safety Critical Hybrid Systems:An Empirical Evaluation[M].Hardware and Software:Verification and Testing.2013:162-177.
[13] KWIATKOWSKA M,NORMAN G,SPROTON J.Probabilistic Model Checking of the IEEE 802.11 Wireless Local Area Network Protocol[M].Process Algebra and Probabilistic Methods:Performance Modeling and Verification.Springer Berlin Heidelberg,2002:411-423.
[14] PNUELI A,ZUCK L D.Probabilistic Verification[J].Information & Computation,1993,103(1):1-29.
[15] https://project.inria.fr/plasma-lab.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .