research-article

Open access

Synthesis-based resolution of feature interactions in cyber-physical systems

Authors:

Benjamin Gafford,

Tobias Dürschmid,

Gabriel A. Moreno,

Eunsuk KangAuthors Info & Claims

ASE '20: Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering

Pages 1090 - 1102

https://doi.org/10.1145/3324884.3416630

Published: 27 January 2021 Publication History

Abstract

The feature interaction problem arises when two or more independent features interact with each other in an undesirable manner. Feature interactions remain a challenging and important problem in emerging domains of cyber-physical systems (CPS), such as intelligent vehicles, unmanned aerial vehicles (UAVs) and the Internet of Things (IoT), where the outcome of an unexpected interaction may result in a safety failure. Existing approaches to resolving feature interactions rely on priority lists or fixed strategies, but may not be effective in scenarios where none of the competing feature actions are satisfactory with respect to system requirements. This paper proposes a novel synthesis-based approach to resolution, where a conflict among features is resolved by synthesizing an action that best satisfies the specification of desirable system behaviors in the given environmental context. Unlike existing resolution methods, our approach is capable of producing a desirable system outcome even when none of the conflicting actions are satisfactory. The effectiveness of the proposed approach is demonstrated using a case study involving interactions among safety-critical features in an autonomous drone.

References

[1]

Björn Andersson, Sagar Chaki, and Dionisio de Niz. 2017. Combining Symbolic Runtime Enforcers for Cyber-Physical Systems. In Runtime Verification - 17th International Conference, RV 2017, Seattle, WA, USA, September 13--16, 2017, Proceedings. 68--84.

[2]

K. Angelopoulos, A. V. Papadopoulos, V. E. S. Souza, and J. Mylopoulos. 2016. Model Predictive Control for Software Systems with CobRA. In 2016 IEEE/ACM 11th International Symposium on Software Engineering for Adaptive and Self-Managing Systems (SEAMS). 35--46.

[3]

Sven Apel, Wolfgang Scholz, Christian Lengauer, and Christian Kästner. 2010. Detecting Dependences and Interactions in Feature-Oriented Design. In IEEE 21st International Symposium on Software Reliability Engineering, ISSRE 2010, San Jose, CA, USA, 1--4 November 2010. 161--170.

[4]

Sven Apel, Hendrik Speidel, Philipp Wendler, Alexander von Rhein, and Dirk Beyer. 2011. Detection of feature interactions using feature-aware verification. In 26th IEEE/ACM International Conference on Automated Software Engineering (ASE 2011), Lawrence, KS, USA, November 6--10, 2011. 372--375.

Digital Library

[5]

Sven Apel, Alexander von Rhein, Thomas Thüm, and Christian Kästner. 2013. Feature-interaction detection based on feature-based specifications. Computer Networks 57, 12 (2013), 2399--2409.

Digital Library

[6]

Sven Apel, Alexander von Rhein, Philipp Wendler, Armin Größlinger, and Dirk Beyer. 2013. Strategies for product-line verification: case studies and experiments. In 35th International Conference on Software Engineering, ICSE '13, San Francisco, CA, USA, May 18--26, 2013. 482--491.

[7]

Joanne M. Atlee, Uli Fahrenberg, and Axel Legay. 2015. Measuring Behaviour Interactions between Product-Line Features. In 3rd IEEE/ACM FME Workshop on Formal Methods in Software Engineering, FormaliSE 2015, Florence, Italy, May 18, 2015. 20--25.

Digital Library

[8]

Howard S. Bloom. 2012. Modern Regression Discontinuity Analysis. Journal of Research on Educational Effectiveness 5, 1 (2012), 43--82.

[9]

Cecylia Bocovich and Joanne M. Atlee. 2014. Variable-specific resolutions for feature interactions. In Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, (FSE-22), Hong Kong, China, November 16 - 22, 2014. 553--563.

Digital Library

[10]

Yuriy Brun, Giovanna Di Marzo Serugendo, Cristina Gacek, Holger Giese, Holger Kienle, Marin Litoiu, Hausi Müller, Mauro Pezzè, and Mary Shaw. 2009. Engineering self-adaptive systems through feedback loops. In Software engineering for self-adaptive systems. Springer, 48--70.

Digital Library

[11]

Muffy Calder, Mario Kolberg, Evan H. Magill, and Stephan Reiff-Marganiec. 2003. Feature interaction: a critical review and considered forecast. Computer Networks 41, 1 (2003), 115--141.

Digital Library

[12]

A. Chavan, L. Yang, K. Ramachandran, and W. H. Leung. 2007. Resolving Feature Interaction with Precedence Lists in the Feature Language Extensions. In Feature Interactions in Software and Communication Systems IX, International Co nference on Feature Interactions in Software and Communication Systems, ICFI 2007, 3--5 September 2007, Grenoble, France. 114--128.

[13]

Yi-Liang Chen, Stéphane Lafortune, and Feng Lin. 1997. Resolving Feature Interactions Using Modular Supervisory Control with Priorities. In Feature Interactions in Telecommunications Networks IV, June 17--19, 1997, Montréal, Canada. 108--122.

[14]

Betty H. C. Cheng, Rogério de Lemos, Holger Giese, Paola Inverardi, Jeff Magee, Jesper Andersson, Basil Becker, Nelly Bencomo, Yuriy Brun, Bojan Cukic, Giovanna Di Marzo Serugendo, Schahram Dustdar, Anthony Finkelstein, Cristina Gacek, Kurt Geihs, Vincenzo Grassi, Gabor Karsai, Holger M. Kienle, Jeff Kramer, Marin Litoiu, Sam Malek, Raffaela Mirandola, Hausi A. Müller, Sooyong Park, Mary Shaw, Matthias Tichy, Massimo Tivoli, Danny Weyns, and Jon Whittle. 2009. Software Engineering for Self-Adaptive Systems: A Research Roadmap. In Dagstuhl Seminar Report. 1--26.

[15]

Andreas Classen, Patrick Heymans, Pierre-Yves Schobbens, Axel Legay, and Jean-François Raskin. 2010. Model checking lots of systems: efficient verification of temporal properties in software product lines. In Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 1, ICSE 2010, Cape Town, South Africa, 1--8 May 2010. 335--344.

Digital Library

[16]

Jacob Cohen. 1977. Academic Press.

[17]

Thomas D Cook and Donald T Campbell. 1979. The design and conduct of true experiments and quasi-experiments in field settings. In Reproduced in part in Research in Organizations: Issues and Controversies. Goodyear Publishing Company.

[18]

Jyotirmoy V. Deshmukh, Alexandre Donzé, Shromona Ghosh, Xiaoqing Jin, Garvit Juniwal, and Sanjit A. Seshia. 2017. Robust online monitoring of signal temporal logic. Formal Methods in System Design 51, 1 (2017), 5--30.

Digital Library

[19]

Adel Dokhanchi, Bardh Hoxha, and Georgios E. Fainekos. 2014. On-Line Monitoring for Temporal Logic Robustness. In Runtime Verification - 5th International Conference, RV 2014, Toronto, ON, Canada, September 22--25, 2014. Proceedings. 231--246.

[20]

Alma L. Juarez Dominguez, Nancy A. Day, and Jeffrey J. Joyce. 2008. Modelling feature interactions in the automotive domain. In International Workshop on Modeling in Software Engineering (MiSE). 45--50.

[21]

Alexandre Donzé, Thomas Ferrère, and Oded Maler. 2013. Efficient Robust Monitoring for STL. In Computer Aided Verification - 25th International Conference, CAV 2013, Saint Petersburg, Russia, July 13--19, 2013. Proceedings. 264--279.

[22]

Alexandre Donzé and Oded Maler. 2010. Robust Satisfaction of Temporal Logic over Real-Valued Signals. In Formal Modeling and Analysis of Timed Systems - 8th International Conference, FORMATS 2010, Klosterneuburg, Austria, September 8--10, 2010. Proceedings. 92--106.

[23]

Dronecode Project. 2020. PX4 autopilot. https://px4.io.

[24]

Georgios E. Fainekos and George J. Pappas. 2006. Robustness of Temporal Logic Specifications. In Formal Approaches to Software Testing and Runtime Verification, First Combined International Workshops, FATES 2006 and RV 2006, Seattle, WA, USA, August 15--16, 2006, Revised Selected Papers. 178--192.

[25]

Yliès Falcone, Laurent Mounier, Jean-Claude Fernandez, and Jean-Luc Richier. 2011. Runtime enforcement monitors: composition, synthesis, and enforcement abilities. Formal Methods in System Design 38, 3 (2011), 223--262.

Digital Library

[26]

Nancy D. Griffeth and Hugo Velthuijsen. 1994. The negotiating agents approach to runtime feature interaction resolution. In Feature Interactions in Telecommunications Systems, May 8--10, 1994, Amsterdam, The Netherlands. 217--235.

[27]

Jonathan D. Hay and Joanne M. Atlee. 2000. Composing features and resolving interactions. In ACM SIGSOFT Symposium on Foundations of Software Engineering, an Diego, California, USA, November 6--10, 2000, Proceedings. 110--119.

[28]

D.E. Kirk. 2004. Optimal Control Theory: An Introduction. Dover Publications. https://books.google.com/books?id=fCh2SAtWIdwC

[29]

Ron Koymans. 1990. Specifying real-time properties with metric temporal logic. Real-time systems 2, 4 (1990), 255--299.

[30]

Christian Krupitzer, Felix Maximilian Roth, Sebastian VanSyckel, Gregor Schiele, and Christian Becker. 2015. A survey on engineering approaches for self-adaptive systems. Pervasive and Mobile Computing 17 (2015), 184--206.

Digital Library

[31]

Oded Maler and Dejan Nickovic. 2004. Monitoring Temporal Properties of Continuous Signals. In Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems. Springer Berlin Heidelberg, 152--166.

[32]

Andreas Metzger. 2004. Feature interactions in embedded control systems. Computer Networks 45, 5 (2004), 625--644.

Digital Library

[33]

Gabriel A. Moreno, Javier Cámara, David Garlan, and Bradley Schmerl. 2015. Proactive Self-Adaptation under Uncertainty: A Probabilistic Model Checking Approach. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering (ESEC/FSE 2015).

Digital Library

[34]

Masahide Nakamura, Hiroshi Igaki, Yuhei Yoshimura, and Kousuke Ikegami. 2009. Considering Online Feature Interaction Detection and Resolution for Integrated Services in Home Network System. In ICFI. IOS Press, 191--206.

[35]

Armstrong Nhlabatsi, Robin Laney, and Bashar Nuseibeh. 2008. Feature interaction: The security threat from within software systems. Progress in Informatics 5 (2008), 75--89.

[36]

Peyman Oreizy, Michael M. Gorlick, Richard N. Taylor, Dennis Heimbigner, Gregory Johnson, Nenad Medvidovic, Alex Quilici, David S. Rosenblum, and Alexander L. Wolf. 1999. An Architecture-Based Approach to Self-Adaptive Software. IEEE Intelligent Systems 14, 3 (May 1999), 54--62.

Digital Library

[37]

Srinivas Pinisetty, Partha S. Roop, Steven Smyth, Stavros Tripakis, and Reinhard von Hanxleden. 2017. Runtime enforcement of reactive systems using synchronous enforcers. In Proceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software, Santa Barbara, CA, USA, July 10--14, 2017. 80--89.

Digital Library

[38]

Amir Pnueli. 1977. The Temporal Logic of Programs. In 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977. 46--57.

Digital Library

[39]

Santhana Gopalan Raghavan, Kosuke Watanabe, Eunsuk Kang, Chung-Wei Lin, Zhihao Jiang, and Shinichi Shiraishi. 2018. Property-Driven Runtime Resolution of Feature Interactions. In Runtime Verification - 18th International Conference, RV 2018, Limassol, Cyprus, November 10--13, 2018, Proceedings. 316--333.

[40]

Mazeiar Salehie and Ladan Tahvildari. 2009. Self-adaptive software: Landscape and research challenges. TAAS 4, 2 (2009), 14:1--14:42.

[41]

Wolfgang Scholz, Thomas Thüm, Sven Apel, and Christian Lengauer. 2011. Automatic detection of feature interactions using the Java modeling language: an experience report. In Software Product Lines - 15th International Conference, SPLC 2011, Munich, Germany, August 22--26, 2011. Workshop Proceedings (Volume 2). 7.

[42]

Norbert Siegmund, Sergiy S. Kolesnikov, Christian Kästner, Sven Apel, Don S. Batory, Marko Rosenmüller, and Gunter Saake. 2012. Predicting performance via automated feature-interaction detection. In 34th International Conference on Software Engineering, ICSE 2012, June 2--9, 2012, Zurich, Switzerland. 167--177.

Digital Library

[43]

Prasanna Thati and Grigore Rosu. 2005. Monitoring Algorithms for Metric Temporal Logic Specifications. Electr. Notes Theor. Comput. Sci. 113 (2005), 145--162.

[44]

Donald L Thistlethwaite and Donald T Campbell. 1960. Regression-discontinuity analysis: An alternative to the ex post facto experiment. Journal of Educational psychology 51, 6 (1960), 309.

[45]

US NHTSA. 2010. ABS ECU Programming, 2010 Toyota Prius Recalls. https://www.nhtsa.gov/vehicle/2010/TOYOTA/PRIUS/4%252520DR/FWD#recalls.

[46]

Meng Wu, Haibo Zeng, Chao Wang, and Huafeng Yu. 2017. Safety Guard: Runtime Enforcement for Safety-Critical Cyber-Physical Systems: Invited. In Proceedings of the 54th Annual Design Automation Conference, DAC 2017, Austin, TX, USA, June 18--22, 2017. 84:1--84:6.

Digital Library

[47]

Lana Yarosh and Pamela Zave. 2017. Locked or Not?: Mental Models of IoT Feature Interaction. In Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems, Denver, CO, USA, May 06--11, 2017. 2993--2997.

Digital Library

[48]

Pamela Zave. 1993. Feature Interactions and Formal Specifications in Telecommunications. IEEE Computer 26, 8 (1993), 20--30.

Digital Library

[49]

Mohammad Hadi Zibaeenejad, Chi Zhang, and Joanne M. Atlee. 2017. Continuous variable-specific resolutions of feature interactions. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2017, Paderborn, Germany, September 4--8, 2017. 408--418.

Digital Library

[50]

P. Ann Zimmer and Joanne M. Atlee. 2012. Ordering features by category. Journal of Systems and Software 85, 8 (2012), 1782--1800.

Digital Library

Cited By

Chu SShedden EZhang CMeira-Góes RMoreno GGarlan DKang E(2023)Runtime Resolution of Feature Interactions through Adaptive Requirement Weakening2023 IEEE/ACM 18th Symposium on Software Engineering for Adaptive and Self-Managing Systems (SEAMS)10.1109/SEAMS59076.2023.00025(115-125)Online publication date: May-2023
https://doi.org/10.1109/SEAMS59076.2023.00025
Sartaj HGrundy J(2021)Automated approach for system-level testing of unmanned aerial systemsProceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE51524.2021.9678902(1069-1073)Online publication date: 15-Nov-2021
https://dl.acm.org/doi/10.1109/ASE51524.2021.9678902

Recommendations

Multi-resolution feature fusion for face recognition

For face recognition, image features are first extracted and then matched to those features in a gallery set. The amount of information and the effectiveness of the features used will determine the recognition performance. In this paper, we propose a ...
Variable-specific resolutions for feature interactions
FSE 2014: Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering

Systems assembled from independently developed features suffer from feature interactions, in which features affect one another's behaviour in surprising ways. The feature-interaction problem states that the number of potential interactions is ...
Multi-branch-feature fusion super-resolution network
Abstract
Deep network attracts extensive attention in the single image super-resolution field. Most of the deep network-based super-resolution methods usually employ a feature extraction stream to generate the input for the next extraction module during ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASE '20: Proceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering

December 2020

1449 pages

ISBN:9781450367684

DOI:10.1145/3324884

General Chair:
John Grundy,
Program Chairs:
Claire Le Goues,
David Lo

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

In-Cooperation

IEEE CS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 January 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

U.S. Department of Defense

Conference

ASE '20

Sponsor:

ASE '20: 35th IEEE/ACM International Conference on Automated Software Engineering

December 21 - 25, 2020

Virtual Event, Australia

Acceptance Rates

Overall Acceptance Rate 82 of 337 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
256
Total Downloads

Downloads (Last 12 months)88
Downloads (Last 6 weeks)10

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chu SShedden EZhang CMeira-Góes RMoreno GGarlan DKang E(2023)Runtime Resolution of Feature Interactions through Adaptive Requirement Weakening2023 IEEE/ACM 18th Symposium on Software Engineering for Adaptive and Self-Managing Systems (SEAMS)10.1109/SEAMS59076.2023.00025(115-125)Online publication date: May-2023
https://doi.org/10.1109/SEAMS59076.2023.00025
Sartaj HGrundy J(2021)Automated approach for system-level testing of unmanned aerial systemsProceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE51524.2021.9678902(1069-1073)Online publication date: 15-Nov-2021
https://dl.acm.org/doi/10.1109/ASE51524.2021.9678902

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents