research-article

ADDiff: semantic differencing for activity diagrams

Authors:

Jan Oliver Ringert,

Bernhard RumpeAuthors Info & Claims

ESEC/FSE '11: Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering

Pages 179 - 189

https://doi.org/10.1145/2025113.2025140

Published: 09 September 2011 Publication History

Abstract

Activity diagrams (ADs) have recently become widely used in the modeling of workflows, business processes, and web-services, where they serve various purposes, from documentation, requirement definitions, and test case specifications, to simulation and code generation. As models, programs, and systems evolve over time, understanding changes and their impact is an important challenge, which has attracted much research efforts in recent years.

In this paper we present addiff, a semantic differencing operator for ADs. Unlike most existing approaches to model comparison, which compare the concrete or the abstract syntax of two given diagrams and output a list of syntactical changes or edit operations, addiff considers the semantics of the diagrams at hand and outputs a set of diff witnesses, each of which is an execution trace that is possible in the first AD and is not possible in the second. We motivate the use of addiff, formally define it, and show two algorithms to compute it, a concrete forward-search algorithm and a symbolic fixpoint algorithm, implemented using BDDs and integrated into the Eclipse IDE. Empirical results and examples demonstrate the feasibility and unique contribution of addiff to the state-of-the-art in version comparison and evolution analysis.

References

[1]

M. Alanen and I. Porres. Difference and union of models. In P. Stevens, J. Whittle, and G. Booch, editors, Proc. 6th Int. Conf. on the UML, volume 2863 of LNCS, pages 2--17. Springer, 2003.

[2]

T. Apiwattanapong, A. Orso, and M. J. Harrold. JDiff: A differencing technique and tool for object-oriented programs. Autom. Softw. Eng., 14(1):3--36, 2007.

Digital Library

[3]

J. R. Burch, E. M. Clarke, K. L. McMillan, D. L. Dill, and L. J. Hwang. Symbolic model checking: 10²⁰ states and beyond. Inf. Comput., 98(2):142--170, 1992.

Digital Library

[4]

R. Cavada, A. Cimatti, C. A. Jochim, G. Keighren, E. Olivetti, M. Pistore, M. Roveri, and A. Tchaltsev. NuSMV User Manual, 2005.

[5]

EMF Compare. http://www.eclipse.org/modeling/emft/?project=compare.

[6]

K.-D. Engel, R. F. Paige, and D. S. Kolovos. Using a model merging language for reconciling model versions. In A. Rensink and J. Warmer, editors, ECMDA-FA, volume 4066 of LNCS, pages 143--157. Springer, 2006.

Digital Library

[7]

R. Eshuis. Symbolic model checking of UML activity diagrams. ACM Trans. Softw. Eng. Methodol., 15(1):1--38, 2006.

Digital Library

[8]

D. Fahland, C. Favre, B. Jobstmann, J. Koehler, N. Lohmann, H. Völzer, and K. Wolf. Instantaneous soundness checking of industrial business process models. In U. Dayal, J. Eder, J. Koehler, and H. A. Reijers, editors, BPM, volume 5701 of LNCS, pages 278--293. Springer, 2009.

Digital Library

[9]

D. Harel and A. Naamad. The STATEMATE Semantics of Statecharts. ACM Trans. Softw. Eng. Methodol., 5(4):293--333, 1996.

Digital Library

[10]

D. Harel and B. Rumpe. Meaningful modeling: What's the semantics of "semantics"? IEEE Computer, 37(10):64--72, 2004.

Digital Library

[11]

D. Jackson and D. A. Ladd. Semantic diff: A tool for summarizing the effects of modifications. In H. A. Müller and M. Georges, editors, ICSM, pages 243--252. IEEE Computer Society, 1994.

Digital Library

[12]

C. Knieke and U. Goltz. An executable semantics for UML 2 activity diagrams. In Proc. Int. Workshop on Formalization of Modeling Languages (FML), 2010.

Digital Library

[13]

H. Krahn, B. Rumpe, and S. Völkel. MontiCore: a framework for compositional development of domain specific languages. Int. J. on Software Tools for Technology Transfer (STTT), 12(5):353--372, 2010.

Digital Library

[14]

J. M. Küster, C. Gerth, and G. Engels. Dependent and conflicting change operations of process models. In R. F. Paige, A. Hartman, and A. Rensink, editors, ECMDA-FA, volume 5562 of LNCS, pages 158--173. Springer, 2009.

Digital Library

[15]

S. Maoz. Model-based traces. In M. R. V. Chaudron, editor, MoDELS Workshops, volume 5421 of LNCS, pages 109--119. Springer, 2008.

[16]

S. Maoz. Using model-based traces as runtime models. IEEE Computer, 42(10):28--36, 2009.

Digital Library

[17]

S. Maoz, J. O. Ringert, and B. Rumpe. An Operational Semantics for Activity Diagrams using SMV. Technical Report AIB 2011-07, RWTH Aachen University, Germany, 2011.

[18]

S. Maoz, J. O. Ringert, and B. Rumpe. CDDiff: Semantic differencing for class diagrams. In M. Mezini, editor, Proc. 25th Euro. Conf. on Object Oriented Programming (ECOOP'11), volume 6813 of LNCS, pages 230--254. Springer, 2011.

Digital Library

[19]

S. Maoz, J. O. Ringert, and B. Rumpe. A manifesto for semantic model differencing. In J. Dingel and A. Solberg, editors, MoDELS Workshops, volume 6627 of LNCS, pages 194--203. Springer, 2011.

Digital Library

[20]

K. McMillan. Symbolic Model Checking. Kluwer Academic Publishers, 1993.

Digital Library

[21]

A. Mehra, J. Grundy, and J. Hosking. A generic approach to supporting diagram differencing and merging for collaborative design. In ASE, pages 204--213. ACM, 2005.

Digital Library

[22]

MontiCore project. http://www.monticore.org/.

[23]

D. Ohst, M. Welle, and U. Kelter. Differences between versions of UML diagrams. In Proc. ESEC / SIGSOFT FSE, pages 227--236. ACM, 2003.

Digital Library

[24]

OMG. UML, version 2.2, OMG Specification, 2009.

[25]

S. Person, M. B. Dwyer, S. G. Elbaum, and C. S. Pasareanu. Differential symbolic execution. In SIGSOFT FSE, pages 226--237. ACM, 2008.

Digital Library

[26]

N. Piterman, A. Pnueli, and Y. Sa'ar. Synthesis of reactive(1) designs. In E. A. Emerson and K. S. Namjoshi, editors, VMCAI, volume 3855 of LNCS, pages 364--380. Springer, 2006.

Digital Library

[27]

A. Pnueli, Y. Sa'ar, and L. Zuck. JTLV: A framework for developing verification algorithms. In T. Touili, B. Cook, and P. Jackson, editors, CAV, volume 6174 of LNCS, pages 171--174. Springer, 2010.

Digital Library

[28]

Semantic diff project. http://www.se-rwth.de/materials/semdiff/.

[29]

SMV model checker. http://www.cs.cmu.edu/~modelcheck/smv.html.

[30]

F. Somenzi. CUDD: CU Decision Diagram package. http://vlsi.colorado.edu/~fabio/CUDD/, 1998.

[31]

H. Störrle. Semantics of control-flow in UML 2.0 activities. In VL/HCC, pages 235--242. IEEE Computer Society, 2004.

Digital Library

[32]

Z. Xing and E. Stroulia. Differencing logical UML models. Autom. Softw. Eng., 14(2):215--259, 2007.

Digital Library

Cited By

Rumpe BStachon MStüber SVoufo VCombemale BWimmer MChechik MEgyed A(2024)Semantic Difference Analysis with Invariant Tracing for Class Diagrams Extended by OCLProceedings of the ACM/IEEE 27th International Conference on Model Driven Engineering Languages and Systems10.1145/3652620.3687818(1066-1075)Online publication date: 22-Sep-2024
https://dl.acm.org/doi/10.1145/3652620.3687818
Sypsas AKalles D(2023)Analysis, Evaluation and Reusability of Virtual Laboratory Software Based on Conceptual Modeling and Conformance CheckingMathematics10.3390/math1109215311:9(2153)Online publication date: 4-May-2023
https://doi.org/10.3390/math11092153
Eshuis R(2023)Extracting Reusable Fragments From Data-Centric Process VariantsIEEE Transactions on Services Computing10.1109/TSC.2022.319098716:3(1833-1845)Online publication date: 1-May-2023
https://doi.org/10.1109/TSC.2022.3190987
Show More Cited By

Index Terms

ADDiff: semantic differencing for activity diagrams

Recommendations

Symbolic model checking of UML activity diagrams

Two translations from activity diagrams to the input language of NuSMV, a symbolic model verifier, are presented. Both translations map an activity diagram into a finite state machine and are inspired by existing statechart semantics. The requirements-...
An ArgoUML metamodel extension for the workflow systems
Selected papers from the International Conference on Computer Science, Software Engineering, Information Technology, e-Business, and Applications, 2004

The Unified Model Language (UML) has nine diagrams. One of them is the activity diagram. This allows the modeling of business processes. A business process is a set of logically related tasks executed to achieve a business result. Workflow systems are ...
An approach and tool for synchronous refactoring of UML diagrams and models using model-to-model transformations
WRT '12: Proceedings of the Fifth Workshop on Refactoring Tools

When refactorings are applied to software models that are specified using the Unified Modeling Language (UML), the actual model and the graphical presentation of the model using a diagram need to be distinguished. While UML refactoring tools exist, they ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ESEC/FSE '11: Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering

September 2011

548 pages

ISBN:9781450304436

DOI:10.1145/2025113

General Chair:
Tibor Gyimóthy
University of Szeged, Hungary
,
Program Chair:
Andreas Zeller
Saarland University, Germany

Copyright © 2011 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

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 September 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESEC/FSE'11

Sponsor:

SIGSOFT

ESEC/FSE'11: Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering

September 5 - 9, 2011

Szeged, Hungary

Acceptance Rates

Overall Acceptance Rate 17 of 128 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
882
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rumpe BStachon MStüber SVoufo VCombemale BWimmer MChechik MEgyed A(2024)Semantic Difference Analysis with Invariant Tracing for Class Diagrams Extended by OCLProceedings of the ACM/IEEE 27th International Conference on Model Driven Engineering Languages and Systems10.1145/3652620.3687818(1066-1075)Online publication date: 22-Sep-2024
https://dl.acm.org/doi/10.1145/3652620.3687818
Sypsas AKalles D(2023)Analysis, Evaluation and Reusability of Virtual Laboratory Software Based on Conceptual Modeling and Conformance CheckingMathematics10.3390/math1109215311:9(2153)Online publication date: 4-May-2023
https://doi.org/10.3390/math11092153
Eshuis R(2023)Extracting Reusable Fragments From Data-Centric Process VariantsIEEE Transactions on Services Computing10.1109/TSC.2022.319098716:3(1833-1845)Online publication date: 1-May-2023
https://doi.org/10.1109/TSC.2022.3190987
Pastore FMicucci DGuzman MMariani L(2022)TkT: Automatic Inference of Timed and Extended Pushdown AutomataIEEE Transactions on Software Engineering10.1109/TSE.2020.299852748:2(617-636)Online publication date: 1-Feb-2022
https://doi.org/10.1109/TSE.2020.2998527
Kautz O(2022)The complexities of the satisfiability checking problems of feature diagram sublanguagesSoftware and Systems Modeling10.1007/s10270-022-01048-322:4(1113-1129)Online publication date: 11-Oct-2022
https://doi.org/10.1007/s10270-022-01048-3
Deknop CMens KBergel AFabry JZaytsev V(2021)A Scalable Log Differencing Visualisation Applied to COBOL Refactoring2021 Working Conference on Software Visualization (VISSOFT)10.1109/VISSOFT52517.2021.00010(1-11)Online publication date: Sep-2021
https://doi.org/10.1109/VISSOFT52517.2021.00010
Cazzola WGhosh SAl-Refai MMaurina G(2021)Bridging the model-to-code abstraction gap with fuzzy logic in model-based regression test selectionSoftware and Systems Modeling10.1007/s10270-021-00899-6Online publication date: 21-Jul-2021
https://doi.org/10.1007/s10270-021-00899-6
Akiki PMaalouf H(2021)CHECKSUM: tracking changes and measuring contributions in cooperative systems modelingSoftware and Systems Modeling10.1007/s10270-020-00840-320:4(1079-1122)Online publication date: 5-Jan-2021
https://doi.org/10.1007/s10270-020-00840-3
Ringert JWali SSyriani ESahraoui H(2020)Semantic comparisons of Alloy modelsProceedings of the 23rd ACM/IEEE International Conference on Model Driven Engineering Languages and Systems10.1145/3365438.3410955(165-174)Online publication date: 16-Oct-2020
https://dl.acm.org/doi/10.1145/3365438.3410955
Deknop CFabry JMens KZaytsev V(2020)Improving a Software Modernisation Process by Differencing Migration LogsProduct-Focused Software Process Improvement10.1007/978-3-030-64148-1_17(270-286)Online publication date: 21-Nov-2020
https://doi.org/10.1007/978-3-030-64148-1_17
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents