research-article

Multi-granular conflict and dependency analysis in software engineering based on graph transformation

Authors:

Daniel Strüber,

Gabriele Taentzer,

Kristopher Born,

Jevgenij HuebertAuthors Info & Claims

ICSE '18: Proceedings of the 40th International Conference on Software Engineering

Pages 716 - 727

https://doi.org/10.1145/3180155.3180258

Published: 27 May 2018 Publication History

Abstract

Conflict and dependency analysis (CDA) of graph transformation has been shown to be a versatile foundation for understanding interactions in many software engineering domains, including software analysis and design, model-driven engineering, and testing. In this paper, we propose a novel static CDA technique that is multi-granular in the sense that it can detect all conflicts and dependencies on multiple granularity levels. Specifically, we provide an efficient algorithm suite for computing binary, coarse-grained, and fine-grained conflicts and dependencies: Binary granularity indicates the presence or absence of conflicts and dependencies, coarse granularity focuses on root causes for conflicts and dependencies, and fine granularity shows each conflict and dependency in full detail. Doing so, we can address specific performance and usability requirements that we identified in a literature survey of CDA usage scenarios. In an experimental evaluation, our algorithm suite computes conflicts and dependencies rapidly. Finally, we present a user study, in which the participants found our coarse-grained results more understandable than the fine-grained ones reported in a state-of-the-art tool. Our overall contribution is twofold: (i) we significantly speed up the computation of fine-grained and binary CDA results and, (ii) complement them with coarse-grained ones, which offer usability benefits for numerous use cases.

References

[1]

A. Alshanqiti and R. Heckel, "Extracting Visual Contracts from Java Programs (T)," in ASE, 2015, pp. 104--114.

[2]

Z. Altahat, T. Elrad, L. Tahat, and N. Almasri, "Detection of syntactic aspect interaction in UML state diagrams using critical pair analysis in graph transformation," CoRR, vol. abs/1312.6939, 2013.

[3]

T. Arendt, E. Biermann, S. Jurack, C. Krause, and G. Taentzer, "Henshin: advanced concepts and tools for in-place EMF model transformations," in MoDELS. Springer, 2010, pp. 121--135.

Digital Library

[4]

S. Arzt, S. Rasthofer, C. Fritz, E. Bodden, A. Bartel, J. Klein, Y. Le Traon, D. Octeau, and P. McDaniel, "Flowdroid: Precise context, flow, field, object-sensitive and life cycle-aware taint analysis for android apps," SIGPLAN Not., vol. 49, no. 6, pp. 259--269, Jun. 2014.

Digital Library

[5]

G. G. Azzi, J. S. Bezerra, L. Ribeiro, A. Costa, L. M. Rodrigues, and R. Machado, "The Verigraph System for Graph Transformation," in Graph Transformation, Specifications, and Nets. In Memory of Hartmut Ehrig. Springer, 2018, pp. 160--178.

[6]

L. Baresi, K. Ehrig, and R. Heckel, "Verification of model transformations: A case study with BPEL," in TGC, 2007, pp. 183--199.

Digital Library

[7]

B. Becker, D. Beyer, H. Giese, F. Klein, and D. Schilling, "Symbolic invariant verification for systems with dynamic structural adaptation," in ICSE, 2006, pp. 72--81.

Digital Library

[8]

P. Bhattacharya, M. Iliofotou, I. Neamtiu, and M. Faloutsos, "Graph-based analysis and prediction for software evolution," in ICSE, 2012, pp. 419--429.

Digital Library

[9]

C. Blume, H. J. S. Bruggink, and B. König, "Recognizable graph languages for checking invariants," ECEASST, vol. 29, 2010.

[10]

K. Born, L. Lambers, D. Strüber, and G. Taentzer, "Granularity of conflicts and dependencies in graph transformation systems," in ICGT, 2017, pp. 125--141.

[11]

K. Born and G. Taentzer, "An algorithm for the critical pair analysis of amalgamated graph transformations," in ICGT, 2016, pp. 118--134.

[12]

P. Bottoni, G. Taentzer, and A. Schürr, "Efficient parsing of visual languages based on critical pair analysis and contextual layered graph transformation," in VL/HCC, 2000, pp. 59--60.

Digital Library

[13]

A. Bucchiarone, P. Pelliccione, C. Vattani, and O. Runge, "Self-repairing systems modeling and verification using AGG," in WICSA/ECSA, 2009, pp. 181--190.

[14]

E. M. Clarke, O. Grumberg, S. Jha, Y. Lu, and H. Veith, "Counterexample-guided abstraction refinement," in CAV, 2000, pp. 154--169.

Digital Library

[15]

S. Degrandsart, S. Demeyer, J. Van den Bergh, and T. Mens, "A transformation-based approach to context-aware modelling," Software & Systems Modeling, vol. 13, no. 1, pp. 191--208, 2014.

Digital Library

[16]

F. Durán and J. Meseguer, "A Church-Rosser Checker Tool for Conditional Order-Sorted Equational Maude Specifications," in WRLA, 2010, pp. 69--85.

Digital Library

[17]

H. Ehrig, K. Ehrig, U. Prange, and G. Taentzer, Fundamentals of Algebraic Graph Transformation, ser. Monographs in Theoretical Computer Science. Springer, 2006.

Digital Library

[18]

H. Ehrig, G. Engels, H.-J. Kreowski, and G. Rozenberg, Eds., Handbook of Graph Grammars and Computing by Graph Transformation: Vol. 3: Applications, Languages, and Tools. World Scientific Publishing, 1999.

Digital Library

[19]

H. Ehrig, U. Golas, A. Habel, L. Lambers, and F. Orejas, "M-adhesive transformation systems with nested application conditions, part 2: Embedding, critical pairs and local confluence," Fundam. Inform., vol. 118, no. 1--2, pp. 35--63, 2012.

Digital Library

[20]

C. Ermel, J. Gall, L. Lambers, and G. Taentzer, "Modeling with plausibility checking: Inspecting favorable and critical signs for consistency between control flow and functional behavior," in FASE. Springer, 2011, pp. 156--170.

Digital Library

[21]

A. H. Ghamarian, M. de Mol, A. Rensink, E. Zambon, and M. Zimakova, "Modelling and analysis using GROOVE," STTT, vol. 14, no. 1, pp. 15--40, 2012.

[22]

J. D. Gibbons and S. Chakraborti, "Nonparametric statistical inference," in International encyclopedia of statistical science. Springer, 2011, pp. 977--979.

[23]

H. Giese, S. Hildebrandt, and L. Lambers, "Bridging the gap between formal semantics and implementation of triple graph grammars," Software & Systems Modeling, vol. 13, no. 1, pp. 273--299, 2014.

Digital Library

[24]

D. Gopher and R. Braune, "On the psychophysics of workload: Why bother with subjective measures?" Human Factors, vol. 26, no. 5, pp. 519--532, 1984.

[25]

A. Habel and K. Pennemann, "Correctness of high-level transformation systems relative to nested conditions," Mathematical Structures in Computer Science, vol. 19, no. 2, pp. 245--296, 2009.

Digital Library

[26]

J. H. Hausmann, R. Heckel, and G. Taentzer, "Detection of Conflicting Functional Requirements in a Use Case-Driven Approach: A Static Analysis Technique Based on Graph Transformation," in ICSE, 2002, pp. 105--115.

Digital Library

[27]

R. Heckel, J. M. Küster, and G. Taentzer, "Confluence of Typed Attributed Graph Transformation Systems," in ICGT, 2002, pp. 161--176.

Digital Library

[28]

T. A. Henzinger, R. Jhala, and R. Majumdar, "Race checking by context inference," in PLDI, 2004, pp. 1--13.

Digital Library

[29]

F. Hermann, H. Ehrig, U. Golas, and F. Orejas, "Efficient analysis and execution of correct and complete model transformations based on triple graph grammars," in MDI, 2010, pp. 22--31.

Digital Library

[30]

F. Hermann, H. Ehrig, F. Orejas, and U. Golas, "Formal analysis of functional behaviour for model transformations based on triple graph grammars," in ICGT, 2010, pp. 155--170.

Digital Library

[31]

S. Hildebrandt, L. Lambers, and H. Giese, "Complete specification coverage in automatically generated conformance test cases for tgg implementations," in ICMT, K. Duddy and G. Kappel, Eds., 2013, pp. 174--188.

[32]

D. Jackson, "Alloy: A lightweight object modelling notation," ACM Trans. Softw. Eng. Methodol, vol. 11, no. 2, pp. 256--290, Apr. 2002.

Digital Library

[33]

P. Jayaraman, J. Whittle, A. M. Elkhodary, and H. Gomaa, "Model composition in product lines and feature interaction detection using critical pair analysis," in MoDELS, 2007, pp. 151--165.

Digital Library

[34]

B. Jones and M. G. Kenward, Design and analysis of cross-over trials. CRC Press, 2014.

[35]

T. Kehrer, U. Kelter, and G. Taentzer, "Consistency-Preserving Edit Scripts in Model Versioning," in ASE, 2013, pp. 191--201.

Digital Library

[36]

G. Kniesel, "Detection and resolution of weaving interactions," Trans. Aspect-Oriented Software Development, vol. 5, pp. 135--186, 2009.

Digital Library

[37]

B. König and V. Kozioura, "Counterexample-guided abstraction refinement for the analysis of graph transformation systems," in TACAS, 2006, pp. 197--211.

Digital Library

[38]

C. Krause, Z. Maraikar, A. Lazovik, and F. Arbab, "Modeling dynamic reconfigurations in reo using high-level replacement systems," Sci. Comput. Program., vol. 76, no. 1, pp. 23--36, 2011.

Digital Library

[39]

J. M. Küster, C. Gerth, and G. Engels, "Dependent and conflicting change operations of process models," in ECMDA-FA, 2009, pp. 158--173.

Digital Library

[40]

L. Lambers, K. Born, F. Orejas, D. Strüber, and G. Taentzer, "Initial conflicts and dependencies: Critical pairs revisited," in Graph Transformation, Specifications, and Nets. In Memory of Hartmut Ehrig. Springer, 2018, pp. 105--123.

[41]

L. Lambers, H. Ehrig, L. Mariani, and M. Pezzè, "Iterative model-driven development of adaptable service-based applications," in ASE, 2007, pp. 453--456.

Digital Library

[42]

L. Lambers, H. Ehrig, and F. Orejas, "Efficient conflict detection in graph transformation systems by essential critical pairs," Electr. Notes Theor. Comput. Sci., vol. 211, pp. 17--26, 2008.

Digital Library

[43]

L. Lambers, D. Strüber, G. Taentzer, K. Born, and J. Hübert, "Multi-granular conflict and dependency analysis in software engineering based on graph transformation: Extended version," 2018, https://www.unimarburg.de/fb12/arbeitsgruppen/swt/forschung/publikationen/.

Digital Library

[44]

P. Leenheer and T. Mens, "Using graph transformation to support collaborative ontology evolution," in AGTIVE, 2008, pp. 44--58.

Digital Library

[45]

K. Mehner-Heindl, M. Monga, and G. Taentzer, "Analysis of Aspect-Oriented Models Using Graph Transformation Systems," in Aspect-Oriented Requirements Engineering, A. Moreira, R. Chitchyan, J. Araújo, and A. Rashid, Eds. Springer, 2013, pp. 243--270.

[46]

T. Mens, G. Taentzer, and O. Runge, "Analysing refactoring dependencies using graph transformation," Software and System Modeling, vol. 6, no. 3, pp. 269--285, 2007.

[47]

T. Mens, R. Van Der Straeten, and M. D'Hondt, "Detecting and resolving model inconsistencies using transformation dependency analysis," in MoDELS, 2006, pp. 200--214.

Digital Library

[48]

D. Plump, "Critical Pairs in Term Graph Rewriting," in Mathematical Foundations of Computer Science, vol. 841, 1994, pp. 556--566.

Digital Library

[49]

C. M. Poskitt and D. Plump, "Verifying monadic second-order properties of graph programs," in ICGT, 2014, pp. 33--48.

[50]

F. Qayum and R. Heckel, "Local search-based refactoring as graph transformation," in SSBSE, 2009, pp. 43--46.

Digital Library

[51]

A. Rensink, Á. Schmidt, and D. Varró, "Model checking graph transformations: A comparison of two approaches," in ICGT, 2004, pp. 226--241.

[52]

M. C. Rinard, "Analysis of multithreaded programs," in SAS, 2001, pp. 1--19.

Digital Library

[53]

G. Rozenberg, Ed., Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations. World Scientific, 1997.

Digital Library

[54]

O. Runge, T. A. Khan, and R. Heckel, "Test case generation using visual contracts," ECEASST, vol. 58, 2013.

[55]

S. S. Shapiro and M. B. Wilk, "An analysis of variance test for normality (complete samples)," Biometrika, vol. 52, no. 3/4, pp. 591--611, 1965.

[56]

Y. Smaragdakis, J. Evans, C. Sadowski, J. Yi, and C. Flanagan, "Sound predictive race detection in polynomial time," SIGPLAN Not., vol. 47, no. 1, pp. 387--400, Jan. 2012.

Digital Library

[57]

D. Strüber, K. Born, K. D. Gill, R. Groner, T. Kehrer, M. Ohrndorf, and M. Tichy, "Henshin: A usability-focused framework for emf model transformation development," in ICGT. Springer, 2017, pp. 196--208.

[58]

D. Strüber, T. Kehrer, T. Arendt, C. Pietsch, and D. Reuling, "Scalability of Model Transformations: Position Paper and Benchmark Set," in BigMDE, 2016, pp. 21--30.

[59]

G. Taentzer, "AGG: A graph transformation environment for modeling and validation of software," in AGTLVE, 2003, pp. 446--453.

[60]

G. Taentzer, C. Ermel, P. Langer, and M. Wimmer, "Conflict detection for model versioning based on graph modifications," in ICGT, 2010, pp. 171--186.

Digital Library

[61]

J. Whitehead, "Collaboration in software engineering: A roadmap," in Future of Software Engineering @ ICSE, 2007, pp. 214--225.

Digital Library

[62]

J. Whittle, P. Jayaraman, A. Elkhodary, A. Moreira, and J. Araújo, "MATA: A unified approach for composing UML aspect models based on graph transformation," Transactions on Aspect-Oriented Software Development VI: Special Issue on Aspects and Model-Driven Engineering, pp. 191--237, 2009.

Digital Library

[63]

D. W. Zimmerman, "Teacher's corner: A note on interpretation of the paired-samples t test," Journal of Educational and Behavioral Statistics, vol. 22, no. 3, pp. 349--360, 1997.

Cited By

Sakizloglou LKhakharova TRuehs FLambers LAntonino PBae DBertolino ALonetti FSantos Í(2024)On an Exemplar Supporting Model-based Quality Assurance Research for Healthcare Systems-of-SystemsProceedings of the 12th ACM/IEEE International Workshop on Software Engineering for Systems-of-Systems and Software Ecosystems10.1145/3643655.3643879(57-60)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3643655.3643879
Ghorbani NSingh TGarcia JMalek S(2024)Darcy: Automatic Architectural Inconsistency Resolution in JavaIEEE Transactions on Software Engineering10.1109/TSE.2024.339643350:6(1639-1657)Online publication date: 3-May-2024
https://dl.acm.org/doi/10.1109/TSE.2024.3396433
Janke MMäder P(2024)7 Dimensions of software change patternsScientific Reports10.1038/s41598-024-54894-014:1Online publication date: 13-Mar-2024
https://doi.org/10.1038/s41598-024-54894-0
Show More Cited By

Index Terms

Multi-granular conflict and dependency analysis in software engineering based on graph transformation
1. Software and its engineering
  1. Software organization and properties
    1. Software functional properties
      1. Formal methods
        Automated static analysis

Recommendations

Dependency analysis for component-based software systems

Interaction in component-based systems (CBS) happens when a component provides an interface and other components use it, and also when a component submits an event and other component receives it. Interactions promote dependencies. Higher dependency ...
Exploring Conflict Reasons for Graph Transformation Systems
Graph Transformation
Abstract
Conflict and dependency analysis (CDA) is a static analysis for the detection of conflicting and dependent rule applications in a graph transformation system. Recently, granularity levels for conflicts and dependencies have been investigated ...
Feature Dependency Modeling for Software Product Line
ICCET '09: Proceedings of the 2009 International Conference on Computer Engineering and Technology - Volume 02

Feature dependency Modeling describes model of mutual constraints among features. It is essential activities for development of software product line. This paper introduces local dependency and global dependency of feature. With analyzing relationship ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICSE '18: Proceedings of the 40th International Conference on Software Engineering

May 2018

1307 pages

ISBN:9781450356381

DOI:10.1145/3180155

Conference Chair:
Michel Chaudron
Chalmers University of Technology, University of Gothenburg, Sweden
,
General Chair:
Ivica Crnkovic
Chalmers University of Technology, University of Gothenburg, Sweden
,
Program Chairs:
Marsha Chechik
University of Toronto, Canada
,
Mark Harman
Facebook and University College London, United Kingdom

Copyright © 2018 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
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 May 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ICSE '18

Sponsor:

SIGSOFT
IEEE-CS

ICSE '18: 40th International Conference on Software Engineering

May 27 - June 3, 2018

Gothenburg, Sweden

Acceptance Rates

Overall Acceptance Rate 276 of 1,856 submissions, 15%

Upcoming Conference

ICSE 2025

2025 IEEE/ACM 46th International Conference on Software Engineering

April 26 - May 3, 2025

Ottawa , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
327
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)5

Reflects downloads up to 25 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sakizloglou LKhakharova TRuehs FLambers LAntonino PBae DBertolino ALonetti FSantos Í(2024)On an Exemplar Supporting Model-based Quality Assurance Research for Healthcare Systems-of-SystemsProceedings of the 12th ACM/IEEE International Workshop on Software Engineering for Systems-of-Systems and Software Ecosystems10.1145/3643655.3643879(57-60)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3643655.3643879
Ghorbani NSingh TGarcia JMalek S(2024)Darcy: Automatic Architectural Inconsistency Resolution in JavaIEEE Transactions on Software Engineering10.1109/TSE.2024.339643350:6(1639-1657)Online publication date: 3-May-2024
https://dl.acm.org/doi/10.1109/TSE.2024.3396433
Janke MMäder P(2024)7 Dimensions of software change patternsScientific Reports10.1038/s41598-024-54894-014:1Online publication date: 13-Mar-2024
https://doi.org/10.1038/s41598-024-54894-0
de Lara JGuerra EBottoni P(2024)Modular language product lines: concept, tool and analysisSoftware and Systems Modeling10.1007/s10270-024-01179-9Online publication date: 28-May-2024
https://doi.org/10.1007/s10270-024-01179-9
Lambers LSakizloglou LAl-Wardi OKhakharova T(2024)Taint Analysis for Graph APIs Focusing on Broken Access ControlGraph Transformation10.1007/978-3-031-64285-2_10(180-200)Online publication date: 2-Jul-2024
https://doi.org/10.1007/978-3-031-64285-2_10
Horcas JStrüber DBurdusel AMartinez JZschaler S(2023)We’re Not Gonna Break It! Consistency-Preserving Operators for Efficient Product Line ConfigurationIEEE Transactions on Software Engineering10.1109/TSE.2022.317140449:3(1102-1117)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1109/TSE.2022.3171404
Motzfeldt IYu IDin CPun VStolz V(2023)Modular Soundness Checking of Feature Model Evolution PlansTheoretical Aspects of Computing – ICTAC 202310.1007/978-3-031-47963-2_25(417-437)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-47963-2_25
de Lara JGuerra EBottoni PSyriani ESahraoui H(2022)Modular language product linesProceedings of the 25th International Conference on Model Driven Engineering Languages and Systems10.1145/3550355.3552444(334-344)Online publication date: 23-Oct-2022
https://dl.acm.org/doi/10.1145/3550355.3552444
Kosiol JStrüber DTaentzer GZschaler S(2022)Sustaining and improving graduated graph consistencyScience of Computer Programming10.1016/j.scico.2021.102729214:COnline publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1016/j.scico.2021.102729
Zadahmad MSyriani EAlam OGuerra Ede Lara J(2022)DSMCompare: domain-specific model differencing for graphical domain-specific languagesSoftware and Systems Modeling (SoSyM)10.1007/s10270-021-00971-121:5(2067-2096)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10270-021-00971-1
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents