Refinement Checking Based on Simulation Relations
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61103044, U1509214); Natural Science Foundation of Zhejiang Province of China (LQ15E050006, LY16F020035)

  • Article
  • | |
  • Metrics
  • |
  • Reference [21]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    Refinement checking is an important method in formal verification to convey a refinement relationship between an implementation model and a specification model in the same language.If the specification satisfies certain property and the refinement relationship is strong enough to preserve the property, then implementation satisfies the property.Refinement checking was developed in order to verify different kinds of properties, traces, stables failures and failures/divergence.Refinement checking often relies on the subset construction, thus suffers from state space explosion.Recently, some researchers proposed a simulation based approach for solving the language inclusion problem of NFA, which outperforms the previous methods significantly and can be directly used in traces refinement checking.Base on this advancement, this work further proposes stable failures and failures-divergence refinement checking algorithms based on simulation relations.In addition, this work also extends the idea of trace refinement checking to timed systems, and proposes timed automata traces refinement checking based on simulation relations.Experimental results confirm the efficiency of the presented approaches.

    Reference
    [1] Gibson-Robinson T, Armstrong P, Boulgakov A, Roscoe AW. FDR3:A modern refinement checker for CSP. In:Proc. of the 20th Int'l Conf. on Tools and Algorithms for the Construction and Analysis of Systems. 2014. 187-201.[doi:10.1007/978-3-642-54862-8_13]
    [2] Roscoe AW. Model-Checking CSP. Prentice-Hall, 1994.
    [3] Roscoe AW. On the expressive power of CSP refinement. Formal Aspects of Computing, 2005,17(2):93-112.[doi:10.1007/s00165-005-0065-x]
    [4] Sun J, Liu Y, Dong JS, Pang J. PAT:Towards flexible verification under fairness. In:Proc. of the 21st Int'l Conf. on Computer Aided Verification. 2009. 709-714.[doi:10.1007/978-3-642-02658-4_59]
    [5] Wulf MD, Doyen L, Henzinger TA, Raskin JF. Antichains:A new algorithm for checking universality of finite automata. In:Proc. of the 18th Int'l Conf. on Computer Aided Verification. 2006. 17-30.[doi:10.1007/11817963_5]
    [6] Abdulla PA, Chen YF, Holik L, Mayr R, Vojnar T. When simulation meets antichains. In:Proc. of the 16th Int'l Conf. on Tools and Algorithms for the Construction and Analysis of Systems. 2010. 158-174.[doi:10.1007/978-3-642-12002-2_14]
    [7] Song SZ. Model checking stochastic systems in PAT[Ph.D. Thesis]. National University of Singapore, 2013.
    [8] Wang T, Sun J, Liu Y, Wang X, Li S. Are timed automata bad for a specification language? Language inclusion checking for timed automata. In:Proc. of the 20th Int'l Conf. on Tools and Algorithms for the Construction and Analysis of Systems. 2014. 310-325.[doi:10.1007/978-3-642-54862-8_21]
    [9] Roscoe AW. The Theory and Practice of Concurrency. Prentice-Hall, 1999.
    [10] Sun J, Liu Y, Dong JS. Model checking CSP revisited:Introducing a process analysis toolkit. In:Proc. of the 3rd Int'l Symp. on Leveraging Applications of Formal Methods, Verification and Validation. 2008. 307-322.[doi:10.1007/978-3-540-88479-8_22]
    [11] Glabbeek RJV, Weijland WP. Branching time and abstraction in bisimulation semantics. Journal of the ACM, 1996,43(3):555-600.[doi:10.1145/233551.233556]
    [12] Bonchi F, Pous D. Checking NFA equivalence with bisimulations up to congruence. In:Proc. of the 40th Annual ACM SIGPLANSIGACT Symp. on Principles of Programming Languages. 2013. 457-468.[doi:10.1145/2429069.2429124]
    [13] Griffioen WD, Vaandrager F. A theory of normed simulations. ACM Trans. on Computational Logic, 2004,5(4):577-610.[doi:10.1145/1024922.1024923]
    [14] Seipp J, Helmert M. Counterexample-Guided cartesian abstraction refinement. In:Proc. of the 23rd Int'l Conf. on Automated Planning and Scheduling. 2013. 347-351.
    [15] Giannakopoulou D, Corina SP. Special issue on learning techniques for compositional reasoning. Formal Methods in System Design, 2008,32(3):173-174.[doi:10.1007/s10703-008-0054-9]
    [16] Doyen L, Raskin JF. Antichains for the automata-based approach to model checking. Logical Methods in Computer Science, 2009, 5(1):1-20.[doi:10.2168/LMCS-5(1:5)2009]
    [17] Wulf MD, Doyen L, Maquet N, Raskin JF. Antichains:Alternative algorithms for LTL satisfiability and model-checking. In:Proc. of the 14th Int'l Conf. on Tools and Algorithms for the Construction and Analysis of Systems. 2008. 63-77.[doi:10.1007/978-3-540-78800-3_6]
    [18] Bengtsson J, Wang Y. Timed Automata:Semantics, Algorithms and Tools. Lectures on Concurrency and Petri Nets, 2004. 87-124.[doi:10.1007/978-3-540-27755-2_3]
    [19] Wang T, Song SZ, Sun J, Liu Y, Dong JS, Wang X, Li S. More anti-chain based refinement checking. In:Proc. of the 14th Int'l Conf. on Formal Engineering Methods. 2012. 364-380.[doi:10.1007/978-3-642-34281-3_26]
    [20] Bouajjani A, Habermehl P, Holik L, Touili T, Vojnar T. Antichain-Based universality and inclusion testing over nondeterministic finite tree automata. In:Proc. of the 13th Int'l Conf. on Implementation and Applications of Automata. 2008. 57-67.[doi:10.1007/978-3-540-70844-5_7]
    [21] Alur R, Dill DL. A theory of timed automata. Theoretical Computer Science, 1994,126(2):183-235.[doi:10.1016/0304-3975(94) 90010-8]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

王婷,陈铁明,刘杨.基于模拟关系的精化检测方法.软件学报,2016,27(3):580-592

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 15,2015
  • Revised:October 20,2015
  • Online: January 06,2016
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063