Artículo

D'Ippolito, N.; Braberman, V.; Piterman, N.; Uchitel, S. "Synthesizing nonanomalous event-based controllers for liveness goals" (2013) ACM Transactions on Software Engineering and Methodology. 22(1)
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We present SGR(1), a novel synthesis technique and methodological guidelines for automatically constructing event-based behavior models. Our approach works for an expressive subset of liveness properties, distinguishes between controlled and monitored actions, and differentiates system goals from environment assumptions. We show that assumptions must be modeled carefully in order to avoid synthesizing anomalous behavior models. We characterize nonanomalous models and propose assumption compatibility, a sufficient condition, as a methodological guideline. © 2013 ACM.

Registro:

Documento: Artículo
Título:Synthesizing nonanomalous event-based controllers for liveness goals
Autor:D'Ippolito, N.; Braberman, V.; Piterman, N.; Uchitel, S.
Filiación:Department of Computing, Imperial College, 180 Queen's Gate, London, SW7 2RH, United Kingdom
Departamento de Computación, Facultad de Ciencias Exactas Y Naturales, Universidad de Buenos Aires, Pabellon 1, Ciudad Universitaria, C1428EHA, Argentina
Department of Computer Science, University of Leicester, Leicester, LE1 7RH, United Kingdom
Palabras clave:Algorithms; Design; Anomalous behavior; Behavior model; Event-based; Liveness; Liveness properties; Methodological guidelines; Sufficient conditions; Synthesis techniques; Algorithms; Computer software; Design; Software engineering
Año:2013
Volumen:22
Número:1
DOI: http://dx.doi.org/10.1145/2430536.2430543
Título revista:ACM Transactions on Software Engineering and Methodology
Título revista abreviado:ACM Trans. Software Eng. Methodol.
ISSN:1049331X
CODEN:ATSME
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_1049331X_v22_n1_p_DIppolito

Referencias:

  • Armoni, R., Fix, L., Flaisher, A., Grumberg, O., Piterman, N., Tiemeyer, A., Vardi, M., Enhanced vacuity detection in linear temporal logic (2003) Financial Cryptography, pp. 368-380. , R. Wright, Ed. Lecture Notes in Computer Science Series, vol. 2742. Springer, Berlin
  • Asarin, E., Maler, O., Pnueli, A., Sifakis, J., Controller synthesis for timed automata (1998) Proceedings of the IFAC Symposium on System Structure and Control
  • Autili, M., Inverardi, P., Tivoli, M., Garlan, D., Synthesis of "correct" adaptors for protocol enhancement in component-based systems (2004) Specification and Verification of Component-Based Systems, p. 79. , ACM
  • Beatty, D.L., Bryant, R.E., Formally verifying a microprocessor using a simulation methodology (1994) Proceedings of the 31st Annual Design Automation Conference (DAC'94), pp. 596-602. , ACM, New York
  • Beer, I., Ben-David, S., Eisner, U., Rodeh, Y., Efficient detection of vacuity in ACTL formulas (1997) Lecture Notes in Computer Science, (1254), pp. 279-290. , Computer Aided Verification
  • Beer, I., Ben-David, S., Eisner, C., Rodeh, Y., Efficient detection of vacuity in temporal model checking (2001) Formal Methods in System Design, 18 (2), pp. 141-163. , DOI 10.1023/A:1008779610539
  • Bertoli, P., Cimatti, A., Pistore, M., Roveri, M., Traverso, P., MBP: A model based planner (2001) Proceedings of the IJCAIŠ01 Workshop on Planning under Uncertainty and Incomplete Information
  • Bertolino, A., Inverardi, P., Pelliccione, P., Tivoli, M., Automatic synthesis of behavior protocols for composable web-services (2009) Proceedings of the the 7th Joint Meeting of the European Software Engineering Conference and the ACMSIGSOFT Symposium on the Foundations of Software Engineering, (ESEC/FSE'09), pp. 141-150. , ACM, New York
  • Bloem, R., Galler, S., Jobstmann, B., Piterman, N., Pnueli, A., Weiglhofer, M., Automatic hardware synthesis from specifications: A case study (2007) Proceedings -Design, Automation and Test in Europe, DATE, pp. 1188-1193. , DOI 10.1109/DATE.2007.364456, 4211966, Proceedings - 2007 Design, Automation and Test in Europe Conference and Exhibition, DATE 2007
  • Bontemps, Y., Schobbens, P.-Y., Löding, C., Synthesis of open reactive systems from scenario-based specifications (2004) Fundamenta Informaticae- Application of Concurrency to System Design (ACSD'03), 62, pp. 139-169
  • Bryant, R.E., Graph-based algorithms for boolean function manipulation (1986) IEEE Trans. Comput., 35, pp. 677-691
  • Buchi, J., Landweber, L., Solving sequential conditions by finite-state strategies (1969) Trans. AMS., pp. 295-311
  • Chatterjee, K., Henzinger, T.A., Jobstmann, B., Environment assumptions for synthesis (2008) Proceedings of the 19th International Conference on Concurrency Theory (CONCUR '08)., pp. 147-161. , Springer-Verlag, Berlin
  • Chechik, M., Gheorghiu, M., Gurfinkel, A., Finding environment guarantees (2007) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4422 LNCS, pp. 352-367. , Fundamental Approaches to Software Engineering - 10th International Conference, FASE 2007. Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007, Proceedings
  • Cobleigh, J.M., Giannakopoulou, D., Pǎsǎreanu, C.S., Learning assumptions for compositional verification (2003) Proceedings of the 9th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'03), pp. 331-346. , Springer-Verlag, Berlin
  • Dalpiaz, F., Giorgini, P., Mylopoulos, J., An architecture for requirements-driven selfreconfiguration (2009) Proceedings of the 21st International Conference on Advanced Information Systems Engineering (CAiSE '09), pp. 246-260. , Springer-Verlag, Berlin
  • Damas, C., Lambeau, B., Van Lamsweerde, A., Scenarios, goals, and state machines: A win-win partnership for model synthesis (2006) Proceedings of the ACM SIGSOFT Symposium on the Foundations of Software Engineering, pp. 197-207. , DOI 10.1145/1181775.1181800, 1181800, Proceedings of the 14th ACM SIGSOFT International Symposium on Foundations of Software Engineering
  • De Alfaro, L., Henzinger, T.A., Interface automata (2001) Proceedings of the ACM SIGSOFT Symposium on the Foundations of Software Engineering, pp. 109-120
  • D'Ippolito, N., Fischbein, D., Chechik, M., Uchitel, S., MTSA: The modal transition system analyser (2008) Proceedings of the 2008 23rd IEEE/ACM International Conference on Automated Software Engineering, (ASE '08), pp. 475-476. , IEEE Computer Society, Washington, DC
  • D'Ippolito, N.R., Braberman, V., Piterman, N., Uchitel, S., Synthesis of live behavior models (2010) Proceedings of the 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering, (FSE '10), pp. 77-86. , ACM, New York
  • D'Ippolito, N.R., Braberman, V., Piterman, N., Uchitel, S., Synthesis of live behavior models for fallible domains (2011) Proceedings of the 33rd International Conference of Software Engineering (ICSE '11), pp. 211-220. , ACM, New York, DOI: 10.1145/1985799.1985823
  • Emmi, M., Giannakopoulou, D., Pǎsǎreanu, C.S., Assume-guarantee verification for interface automata (2008) Proceedings of the 15th International Symposium on Formal Methods (FM '08), pp. 116-131. , Springer- Verlag, Berlin
  • Etessami, K., Wilke, T., Schuller, R.A., Fair simulation relations, parity games, and state space reduction for Büchi automata (2005) SIAM Journal on Computing, 34 (5), pp. 1159-1175. , DOI 10.1137/S0097539703420675
  • Gat, E., Bonnasso, R.P., Murphy, R., Press, A., On three-layer architectures (1997) Artificial Intelligence and Mobile Robots, pp. 195-210. , AAAI Press
  • Giannakopoulou, D., Magee, J., Fluent model checking for event-based systems (2003) Proceedings of the 9th European Software Engineering Conference Held Jointly with 11th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE-11), pp. 257-266. , ACM, New York
  • Giunchiglia, F., Traverso, P., Planning as model checking (2000) Proceedings of the 5th European Conference on Planning: Recent Advances in AI Planning, pp. 1-20. , Springer-Verlag, Berlin
  • Godefroid, P., Piterman, N., LTL generalized model checking revisited (2009) Proceedings of the 10th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI '09), pp. 89-104. , Springer-Verlag, Berlin
  • Gurfinkel, A., Chechik, M., How vacuous is vacuous? (2004) Tools and Algorithms for the Construction and Analysis of Systems, pp. 451-466
  • Heaven, W., Sykes, D., Magee, J., Kramer, J., Software engineering for self-adaptive systems (2009) A Case Study in Goal-driven Architectural Adaptation, pp. 109-127. , Chapter, Springer-Verlag, Berlin
  • Hoare, C.A.R., Communicating sequential processes (1978) Commun. ACM, 21, pp. 666-677
  • Huang, A.-C., Garlan, D., Schmerl, B., Rainbow: Architecture-based self-adaptation with reusable infrastructure (2004) Proceedings of the 1st International Conference on Autonomic Computing, pp. 276-277. , IEEE Computer Society, Washington, DC
  • Inverardi, P., Tivoli, M., A reuse-based approach to the correct and automatic composition of web-services (2007) ESSPE '07 - International Workshop on Engineering of Software Services for Pervasive Environments - In conjunction with the 6th ESEC/FSE Joint Meeting, pp. 29-33. , DOI 10.1145/1294904.1294908, ESSPE '07 - International Workshop on Engineering of Software Services for Pervasive Environments - In conjunction with the 6th ESEC/FSEJoint Meeting
  • Jackson, M., (1995) Software Requirements & Specifications: A Lexicon of Practice, Principles and Prejudices, , ACM Press/Addison-Wesley Publishing Co. New York
  • Jackson, M., The world and the machine (1995) Proceedings of the 17th International Conference on Software Engineering (ICSE '95), pp. 283-292. , ACM, New York
  • Jurdziński, M., Small progress measures for solving parity games (2000) Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, pp. 290-301. , H. Reichel and S. Tison, Eds. Lecture Notes in Computer Science Series, vol. 1770, Springer-Verlag, Berlin
  • Juvekar, S., Piterman, N., Minimizing generalized BCHI automata (2006) Proceedings 18th International Conference on Computer Aided Verification, pp. 45-58. , T. Ball and R. Jones, Eds. Lecture Notes in Computer Science Series, vol. 4144, Springer, Berlin
  • Kazhamiakin, R., Pistore, M., Roveri, M., Formal verification of requirements using SPIN: A case study on web services (2004) Proceedings of the Second International Conference on Software Engineering and Formal Methods. SEFM 2004, pp. 406-415. , Proceedings of the Second International Conference on Software Engineering and Formal Methods. SEFM 2004
  • Keller, R.M., Formal verification of parallel programs (1976) Commun. ACM, 19, pp. 371-384
  • Kesten, Y., Piterman, N., Pnueli, A., Bridging the gap between fair simulation and trace inclusion (2005) Information and Computation, 200 (1), pp. 35-61. , DOI 10.1016/j.ic.2005.01.006, PII S0890540105000234
  • Konighofer, R., Hofferek, G., Bloem, R., Debugging formal specifications using simple counterstrategies (2009) Proceedings of the Symposium on Formal Methods in Computer-Aided Design, 2009 (FMCAD 2009), pp. 152-159. , IEEE
  • Kramer, J., Magee, J., Self-managed systems: An architectural challenge (2007) FoSE 2007: Future of Software Engineering, pp. 259-268. , DOI 10.1109/FOSE.2007.19, 4221625, FoSE 2007: Future of Software Engineering
  • Kupferman, O., Vardi, M., Vacuity detection in temporal model checking (2003) Int. J. Softw. Tools Technol. Trans. (STTT), 4 (2), pp. 224-233
  • Kupferman, O., Vardi, M.Y., Safraless decision procedures (2005) Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pp. 531-542. , IEEE Computer Society, Washington, DC
  • Lamsweerde, A.V., Goal-oriented requirements engineering: A guided tour (2001) Proceedings of the 5th IEEE International Symposium on Requirements Engineering, , IEEE Computer Society Washington, DC
  • Letier, E., Kramer, J., Magee, J., Uchitel, S., Deriving event-based transition systems from goaloriented requirements models (2008) Automat. Softw. Eng., 15, pp. 175-206
  • Letier, E., Van Lamsweerde, A., Agent-based tactics for goal-oriented requirements elaboration (2002) Proceedings - International Conference on Software Engineering, pp. 83-93
  • Lewerentz, C., Lindner, T., (1995) Formal Development of Reactive Systems- Case Study Production Cell, , Eds. Lecture Notes in Computer Science Series, vol. 891, Springer-Verlag, Berlin
  • Lynch, N., Tuttle, M., An introduction to input/output automata (1989) CWI Quart, 2, pp. 219-246
  • Maler, O., Pnueli, A., Sifakis, J., On the synthesis of discrete controllers for timed systems (an extended abstract) (1995) Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), pp. 229-242. , Lecture Notes in Computer Science, Vol. 95, Springer, Berlin
  • Manna, Z., Pnueli, A., (1992) The Temporal Logic of Reactive and Concurrent Systems, , Springer-Verlag New York, Inc. New York
  • Parnas, D.L., Madey, J., Functional documents for computer systems (1995) Sci. Comput. Prog., 25 (1), pp. 41-61
  • Pistore, M., Barbon, F., Bertoli, P., Shaparau, D., Traverso, P., Planning and monitoring web service composition (2004) Artificial Intelligence: Methodology, Systems, and Applications, pp. 106-115. , C. Bussler and D. Fensel, Eds. Lecture Notes in Computer Science Series, vol. 3192, Springer, Berlin, 10.1007/978-3-540- 30106-6 11
  • Piterman, N., Pnueli, A., Sa'ar, Y., Synthesis of reactive (1) designs (2006) Proceedings of the 7th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI 2006), pp. 364-380. , Lecture Notes in Computer Science, vol. 3855. Springer, Berlin
  • Pnueli, A., Rosner, R., On the synthesis of a reactive module (1989) Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'89), pp. 179-190. , ACM, New York
  • Rabin, M., Weakly definable relations and special automata (1970) Proceeding of the Symposium on the Mathematical Logic and Foundations of Set Theory, pp. 1-23
  • Ramadge, P., Wonham, W., The control of discrete event systems (1989) Proc. IEEE, 77 (1), pp. 81-98
  • Russell, S., Norvig, P., (1995) Artificial Intelligence: A Modern Approach, , Prentice Hall, Englewood Cliffs, N.J
  • Schewe, S., Finkbeiner, B., Bounded synthesis (2007) Proceedings of the 5th International Conference on Automated Technology for Verification and Analysis (ATVA'07), pp. 474-488. , Springer-Verlag, Berlin
  • Sohail, S., Somenzi, F., Ravi, K., A hybrid algorithm for LTL games (2008) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4905 LNCS, pp. 309-323. , DOI 10.1007/978-3-540-78163-9-26, Verification, Model Checking, and Abstract Interpretation - 9th International Conference, VMCAI 2008, Proceedings
  • Sykes, D., Heaven, W., Magee, J., Kramer, J., Plan-directed architectural change for autonomous systems (2007) ESEC/FSE 2007: 6th Joint Meeting - Sixth International Workshop on Specification and Verification of Component-Based Systems, SAVCBS 2007, pp. 15-21. , DOI 10.1145/1292316.1292318, ESEC/FSE 2007: 6th Joint Meeting - Sixth International Workshop on Specification and Verification of Component-Based Systems, SAVCBS 2007
  • Uchitel, S., Brunet, G., Chechik, M., Synthesis of partial behavior models from properties and scenarios (2009) IEEE Trans. Softw. Eng., 35, pp. 384-406
  • Van Lamsweerde, A., (2009) Requirements Engineering- From System Goals to UML Models to Software Specifications, , Wiley
  • Van Lamsweerde, A., Handling obstacles in goal-oriented requirements engineering (2000) IEEE Transactions on Software Engineering, 26 (10), pp. 978-1005. , DOI 10.1109/32.879820
  • Young, M., Devanbu, P.T., (2006) Proceedings of the 14th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2005), , Eds. ACM
  • Zave, P., Jackson, M., Four dark corners of requirements engineering (1997) ACM Transactions on Software Engineering and Methodology, 6 (1), pp. 1-30

Citas:

---------- APA ----------
D'Ippolito, N., Braberman, V., Piterman, N. & Uchitel, S. (2013) . Synthesizing nonanomalous event-based controllers for liveness goals. ACM Transactions on Software Engineering and Methodology, 22(1).
http://dx.doi.org/10.1145/2430536.2430543
---------- CHICAGO ----------
D'Ippolito, N., Braberman, V., Piterman, N., Uchitel, S. "Synthesizing nonanomalous event-based controllers for liveness goals" . ACM Transactions on Software Engineering and Methodology 22, no. 1 (2013).
http://dx.doi.org/10.1145/2430536.2430543
---------- MLA ----------
D'Ippolito, N., Braberman, V., Piterman, N., Uchitel, S. "Synthesizing nonanomalous event-based controllers for liveness goals" . ACM Transactions on Software Engineering and Methodology, vol. 22, no. 1, 2013.
http://dx.doi.org/10.1145/2430536.2430543
---------- VANCOUVER ----------
D'Ippolito, N., Braberman, V., Piterman, N., Uchitel, S. Synthesizing nonanomalous event-based controllers for liveness goals. ACM Trans. Software Eng. Methodol. 2013;22(1).
http://dx.doi.org/10.1145/2430536.2430543