IDEAS home Printed from https://ideas.repec.org/a/eee/reensy/v191y2019ics0951832018307920.html
   My bibliography  Save this article

Using evolutionary algorithms for reachability analysis of complex software systems specified through graph transformation

Author

Listed:
  • Pira, Einollah
  • Rafe, Vahid
  • Nikanjam, Amin

Abstract

Assessing the reliability of safety-critical systems is an important and challenging task because even a minor failure in these systems may result in catastrophic consequences, like losing human life. A well-known and fully automatic technique in reliability assessing approaches is model checking. However, applying this technique to verify some properties such as safety may lead to the state space explosion problem in which all reachable states cannot be checked due to computational limitations. In such situations that the verification of a safety property is infeasible, it is possible to refute the safety property by searching a reachable state in which a special configuration (e.g., an error or an undesirable behaviour) occurs. Therefore, checking reachability can be done instead of refuting the corresponding safety property. Finding such reachable states, in the worst case, may cause the state space explosion problem again. Hence, using evolutionary algorithms to explore the state space efficiently can be a promising idea. In this paper, at first, we propose an evolutionary algorithm to check reachability properties and refute safety ones in software systems specified formally through graph transformations. Since the accuracy and convergence speed of the proposed approach can still be improved, we employ the Bayesian Optimization Algorithm (BOA) to propose another approach. In BOA, a Bayesian network is learnt from the population and then sampled to generate new solutions. The proposed approaches can be used to analyse the reachability and safety properties. The proposed approaches are implemented in GROOVE which is an open source toolset for designing and model checking graph transformation systems. To evaluate the efficiency of the proposed approaches, different benchmark problems are employed. Experimental results show that the proposed approaches are faster and more accurate than the existing methods.

Suggested Citation

  • Pira, Einollah & Rafe, Vahid & Nikanjam, Amin, 2019. "Using evolutionary algorithms for reachability analysis of complex software systems specified through graph transformation," Reliability Engineering and System Safety, Elsevier, vol. 191(C).
  • Handle: RePEc:eee:reensy:v:191:y:2019:i:c:s0951832018307920
    DOI: 10.1016/j.ress.2019.106577
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0951832018307920
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ress.2019.106577?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Herbert, L.T. & Hansen, Z.N.L., 2016. "Restructuring of workflows to minimise errors via stochastic model checking: An automated evolutionary approach," Reliability Engineering and System Safety, Elsevier, vol. 145(C), pages 351-365.
    2. Lahtinen, Jussi & Kuismin, Tuomas & Heljanko, Keijo, 2015. "Verifying large modular systems using iterative abstraction refinement," Reliability Engineering and System Safety, Elsevier, vol. 139(C), pages 120-130.
    3. Sharvia, Septavera & Papadopoulos, Yiannis, 2015. "Integrating model checking with HiP-HOPS in model-based safety analysis," Reliability Engineering and System Safety, Elsevier, vol. 135(C), pages 64-80.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Bolton, Matthew L. & Molinaro, Kylie A. & Houser, Adam M., 2019. "A formal method for assessing the impact of task-based erroneous human behavior on system safety," Reliability Engineering and System Safety, Elsevier, vol. 188(C), pages 168-180.
    2. Bolbot, Victor & Theotokatos, Gerasimos & Bujorianu, Luminita Manuela & Boulougouris, Evangelos & Vassalos, Dracos, 2019. "Vulnerabilities and safety assurance methods in Cyber-Physical Systems: A comprehensive review," Reliability Engineering and System Safety, Elsevier, vol. 182(C), pages 179-193.
    3. Waqar Ahmad & Osman Hasan & Sofiène Tahar & Mohamed Salah Hamdi, 2018. "Formal reliability analysis of oil and gas pipelines," Journal of Risk and Reliability, , vol. 232(3), pages 320-334, June.
    4. Cuer, Romain & Piétrac, Laurent & Niel, Eric & Diallo, Saidou & Minoiu-Enache, Nicoleta & Dang-Van-Nhan, Christophe, 2018. "A formal framework for the safe design of the Autonomous Driving supervision," Reliability Engineering and System Safety, Elsevier, vol. 174(C), pages 29-40.
    5. Pakonen, Antti & Buzhinsky, I & Björkman, K, 2021. "Model checking reveals design issues leading to spurious actuation of nuclear instrumentation and control systems," Reliability Engineering and System Safety, Elsevier, vol. 205(C).
    6. Gan, Chenyu & Ding, Shuiting & Qiu, Tian & Liu, Peng & Ma, Qinglin, 2024. "Model-based safety analysis with time resolution (MBSA-TR) method for complex aerothermal–mechanical systems of aero-engines," Reliability Engineering and System Safety, Elsevier, vol. 243(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:reensy:v:191:y:2019:i:c:s0951832018307920. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/reliability-engineering-and-system-safety .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.