Correctly slicing extended finite state machines

Book chapter


Amtoft, T., Androutsopoulos, K. and Clark, D. 2020. Correctly slicing extended finite state machines. in: Di Pierro, A., Malacaria, P. and Nagarajan, R. (ed.) From lambda calculus to cybersecurity through program analysis - essays dedicated to Chris Hankin on the occasion of his retirement Switzerland Springer International Publishing.
Chapter titleCorrectly slicing extended finite state machines
AuthorsAmtoft, T., Androutsopoulos, K. and Clark, D.
Abstract

We consider slicing extended finite state machines. Extended finite state machines (EFSMs) combine a finite state machine with a store and can model a range of computational phenomena, from high-level software to cyber-physical systems. EFSMs are essentially interactive, possibly non-terminating or with multiple exit states and may be nondeterministic, so standard techniques for slicing, developed for control flow graphs of programs with a functional semantics, are not immediately applicable.
This paper addresses the various aspects of correctness for slicing of EFSMs, and provides syntactic criteria that we prove are sufficient for our proposed notions of semantic correctness. The syntactic criteria are based on the ``weak commitment" and ``strong commitment" properties highlighted by Danicic et alia. We provide polynomial-time algorithms to compute the least sets satisfying each of these two properties. We have conducted experiments using widely-studied benchmark and industrial EFSMs that compare our slicing algorithms with those using existing definitions of control dependence.
We found that our algorithms produce the smallest average slices sizes, 21% of the original EFSMs when ``weak commitment'' is sufficient and 58% when ``strong commitment'' is needed (to preserve termination properties).

KeywordsOptimization
Book titleFrom lambda calculus to cybersecurity through program analysis - essays dedicated to Chris Hankin on the occasion of his retirement
EditorsDi Pierro, A., Malacaria, P. and Nagarajan, R.
PublisherSpringer International Publishing
Place of publicationSwitzerland
SeriesTheoretical Computer Science and General Issues
ISBN
Paperback9783030411022
Electronic9783030411039
Publication dates
Online15 Feb 2020
Print01 Jan 2020
Publication process dates
Deposited09 Jun 2020
Accepted10 Dec 2019
Output statusPublished
Additional information

Part of the Lecture Notes in Computer Science book series (LNCS, volume 12065), also part of the Theoretical Computer Science and General Issues book sub series (LNTCS, volume 12065).

Web address (URL)https://link.springer.com/chapter/10.1007/978-3-030-41103-9_6
Digital Object Identifier (DOI)https://doi.org/10.1007/978-3-030-41103-9_6
LanguageEnglish
JournalFrom Lambda Calculus to Cybersecurity Through Program Analysis Essays Dedicated to Chris Hankin on the Occasion of His Retirement
Permalink -

https://repository.mdx.ac.uk/item/88z92

  • 50
    total views
  • 0
    total downloads
  • 1
    views this month
  • 0
    downloads this month

Export as

Related outputs

Evelyne Lutton, Nathalie Perrot, Alberto Tonda: Evolutionary algorithms for food science and technology, Wiley, 2016, 182 pp, ISBN: 978-1-119-13683-5 [Book review]
Androutsopoulos, K. 2018. Evelyne Lutton, Nathalie Perrot, Alberto Tonda: Evolutionary algorithms for food science and technology, Wiley, 2016, 182 pp, ISBN: 978-1-119-13683-5 [Book review]. Genetic programming and Evolvable Machines. https://doi.org/10.1007/s10710-018-9335-2
MIRTO: an open-source robotic platform for education
Androutsopoulos, K., Aristodemou, L., Boender, J., Bottone, M., Currie, E., El-Aroussi, I., Fields, B., Gheri, L., Gorogiannis, N., Heeney, M., Micheletti, M., Loomes, M., Margolis, M., Petridis, M., Piermarteri, A., Primiero, G., Raimondi, F. and Weldin, N. 2018. MIRTO: an open-source robotic platform for education. 3rd European Conference on Software Engineering Education. Seeon, Germany 14 - 15 Jun 2018 Association for Computing Machinery (ACM). pp. 55-62 https://doi.org/10.1145/3209087.3209106
A racket-based robot to teach first-year computer science
Androutsopoulos, K., Gorogiannis, N., Loomes, M., Margolis, M., Primiero, G., Raimondi, F., Varsani, P., Weldin, N. and Zivanovic, A. 2014. A racket-based robot to teach first-year computer science. 7 th European Lisp Symposium. IRCAM, Paris, France 05 - 06 May 2014 pp. 54-61
An alternative characterization of weak order dependence
Amtoft, T., Androutsopoulos, K., Clark, D., Harman, M. and Li, Z. 2010. An alternative characterization of weak order dependence. Information Processing Letters. 110 (21), pp. 939-943. https://doi.org/10.1016/j.ipl.2010.07.023
Model projection: simplifying models in response to restricting the environment
Androutsopoulos, K., Binkley, D., Clark, D., Gold, N., Harman, M., Lano, K. and Li, Z. 2011. Model projection: simplifying models in response to restricting the environment. Proceedings of the 33rd International Conference on Software Engineering, ICSE 2011. Waikiki, Honolulu, HI, USA 21 - 28 May 2011 pp. 291-300
State-based model slicing: a survey
Androutsopoulos, K., Clark, D., Harman, M., Krinke, J. and Tratt, L. 2013. State-based model slicing: a survey. ACM Computing Surveys. 45 (4), p. 53. https://doi.org/10.1145/2501654.2501667
An analysis of the relationship between conditional entropy and failed error propagation in software testing
Androutsopoulos, K., Clark, D., Dan, H., Hierons, R. and Harman, M. 2014. An analysis of the relationship between conditional entropy and failed error propagation in software testing. 36th International Conference on Software Engineering, ICSE '14. Hyderabad, India 31 May - 07 Jun 2014 Association for Computing Machinery (ACM). pp. 573-583 https://doi.org/10.1145/2568225.2568314
Model projection: simplifying models in response to restricting the environment
Androutsopoulos, K., Binkley, D., Clark, D., Gold, N., Harman, M., Lano, K. and Li, Z. 2011. Model projection: simplifying models in response to restricting the environment. in: Proceedings of the 33rd International Conference on Software Engineering - ICSE '11 ACM. pp. 291-300
Amorphous slicing of extended finite state machines
Androutsopoulos, K., Clark, D., Harman, M., Hierons, R., Li, Z. and Tratt, L. 2013. Amorphous slicing of extended finite state machines. IEEE Transactions on Software Engineering. 39 (7), pp. 892-909. https://doi.org/10.1109/TSE.2012.72
A theoretical and empirical study of EFSM dependence.
Androutsopoulos, K., Gold, N., Harman, M., Li, Z. and Tratt, L. 2009. A theoretical and empirical study of EFSM dependence. IEEE Computer Society. pp. 287-296 https://doi.org/10.1109/ICSM.2009.5306309
Control dependence for extended finite state machines.
Androutsopoulos, K., Clark, D., Harman, M., Li, Z. and Tratt, L. 2009. Control dependence for extended finite state machines. Fundamental Approaches to Software Engineering (FASE '09). Springer. https://doi.org/10.1007/978-3-642-00593-0_15