This content is not included in
your SAE MOBILUS subscription, or you are not logged in.
Simplifying the Review of Communicating Finite State Machines Implementation using Static Analysis
Technical Paper
2016-01-0035
ISSN: 0148-7191, e-ISSN: 2688-3627
Annotation ability available
Sector:
Language:
English
Abstract
Finite State Machines (FSMs) are used at various stages of software development, from the initial concept of software system to the lowest level implementation. These FSMs communicate non-deterministically with the other FSMs and the environment of the underlying system. Any inappropriate handling of the communication across multiple FSMs or environment may lead to unexpected behavior of the underlying system. Manual detection of the root cause of such unexpected behavior is effort intensive. Moreover, state of art techniques focus mainly on design level review of communicating FSMs (Comm-FSMs), and no technique is available for systematic review of Comm-FSMs at implementation level. In this paper we present a review technique for detecting inconsistencies in the implementation of Comm-FSMs. The proposed technique includes: a) identification of all possible FSMs and external entities in the system code, and b) identification of Comm-FSMs and checking the impact of external entities (events, signals, timers etc.) on the identified Comm-FSMs. The proposed technique assists user’s review to detect incorrect handling of communicating signals and external entities in the implementation that may halt the progress of Comm-FSMs. Our experimental evaluation using two well-tested real world applications demonstrated that the presented technique is effective in detecting critical defects with the overall reduction of manual review effort by 60% to 80%.
Recommended Content
Authors
Citation
Zare, A., Datar, A., Venkatesh, R., and Hasegawa, M., "Simplifying the Review of Communicating Finite State Machines Implementation using Static Analysis," SAE Technical Paper 2016-01-0035, 2016, https://doi.org/10.4271/2016-01-0035.Also In
References
- Lindlar , Felix , and Armin Zimmermann A code generation tool for embedded automotive systems based on finite state machines In Industrial Informatics, 2008. INDIN 2008. 6th IEEE International Conference on 1539 1544 IEEE 2008
- Ted Carmely Using finite state machines to design software http://www.embedded.com/design/prototyping-and-development/4008260/Using-finite-state-machines-todesign-software March 30 2009
- Shue , Shyhpyng Jack , and Shillings John J. Vehicle management system using finite state machines U.S. Patent 8,948,936 February 3 2015
- Bringmann , Eckard , and Andreas Kramer Model-based testing of automotive systems In Software Testing, Verification, and Validation, 2008 1st International Conference on 485 493 IEEE 2008
- Specification and design of embedded systems Englewood Cliffs New Jersey, USA PTR Prentice Hall 1994
- Jilles , J. Van Gurp , and Bosch Jan On the implementation of finite state machines Variability in Software Systems the Key to Software Reuse 2000 45
- Bollig , Benedikt Communicating Finite-State Machines Formal Models of Communicating Systems: Languages, Automata, and Monadic Second-Order Logic 2006 117 150
- Ostroff , Jonathan S. Formal methods for the specification and design of real-time safety critical systems Journal of Systems and Software 18 1 1992 33 60
- Knight , John C. Safety critical systems: challenges and directions In Software Engineering, 2002. ICSE 2002. Proceedings of the 24rd International Conference on 547 550 IEEE 2002
- Wallace , Dolores R. , and Fujii Roger U. Software verification and validation: an overview IEEE Software 3 1989 10 17
- Yoo , Junbeom , Eunkyoung Jee , and Sungdeok Cha Formal modeling and verification of safety-critical software Software, IEEE 26 3 2009 42 49
- ISO 26262 standard Road vehicles - Functional safety - Part 6: Product development: software level ISO standard 26262-6 Nov. 2011
- Venkatesh R , Advaita Datar , and Pragati Srivastava Consideration of External Signals to resolve non-progressive behavior in communicating state machines Patent application no. 1236/MUM/2013 28 March 2013
- TCS Embedded Code Analyzer (TCS ECA) http://www.tcs.com/offerings/engineering_services/Pages/TCS-Embedded-Code-Analyzer.aspx 02 Feb 2016
- Scriptonium Designs Introduction to Embedded Programming http://www.scriptoriumdesigns.com/embedded/timers.php
- Gouda , Mohamed G. , Manning Eric G. , and Yao-Tin Yu On the progress of communication between two finite state machines Information and control 63 3 1984 200 216
- Kanellakis , Paris C. , and Smolka Scott A. On the analysis of cooperation and antagonism in networks of communicating processes Algorithmica 3 1-4 1988 421 450
- Peng , Wuxu , and Purushothaman S. Analysis of communicating processes for non-progress In Distributed Computing Systems, 1989, 9th International Conference on 280 287 IEEE 1989
- Reif , John H. Data flow analysis of communicating processes Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages 257 268 ACM 1979
- Taylor , Richard N. A general-purpose algorithm for analyzing concurrent programs Communications of the ACM 26 5 1983 361 376
- Yu , Yao-Tin , and Gouda Mohamed G. Deadlock detection for a class of communicating finite state machines Communications, IEEE Transactions on 30 12 1982 2514 2518
- Dill , David L. Timing assumptions and verification of finite-state concurrent systems Automatic verification methods for finite state systems 197 212 Springer Berlin Heidelberg 1990
- Gouda , Mohamed G. , Ching-Hua Chow , and Lam Simon S. On the Decidability of Livelock Detection in Networks of Communicating Finite State Machines In PSTV 85 47 56 1984