MARS

MARS

A MetAmodel Recovery System Using Grammar Inference

Project Members:

Faizan Javed, Marjan Mernik, Jeff Gray, and Barrett Bryant

SoftCom Lab, Department of Computer & Information Sciences,

Overview

The aim of the MARS system is to be able to infer a metamodel from a collection of instance models. The motivating problem was to address the issue of metamodel drift, which occurs when instance models in a repository are separated from their defining metamodel. In most metamodeling environments, the instance models cannot be loaded properly into the modeling tool without the metamodel. Some examples of problems that require the need to recover or reverse engineer a metamodel are: losing a metamodel definition due to a hard-drive crash, and encountering versioning conflicts when trying to load instance models (also called domain models) based on obsolete metamodels. From our experience in model-driven engineering, it is often the case that a metamodel undergoes frequent evolution, which may result in previous instances being orphaned from the new definition. The key contribution of this system is the application of grammar inference algorithms to the metamodel recovery problem. Although the application of MARS has focused specifically on recovering metamodels for the GME, we believe that the same process can be applied to other metamodeling tools, such as MetaCase’s metaEdit+ (http://www.metacase.com) and Honeywell’s Domain Modeling Environment (DOME) (http://www.htc.honeywell.com/dome/). As an area of future work, we plan to explore the ability to apply MARS to these other environments. The remainder of this concluding section provides a discussion of experimental results, limitations of the current approach, and details about where to find more information about the MARS project.

The MARS system

The figure below gives an overview of the MARS system:

The key technologies used in MARS are:

1 Grammar Inference

Inductive learning is the process of learning from examples. The related area of grammatical inference can be defined as a particular instance of inductive learning where the examples are sets of strings defined on a specific alphabet. In MARS, grammar inference techniques are used to mine information about metamodels from available instance models by first representing the visual metamodels as an equivalent textural representation in a Domain-Specific Language, MRL, and then performing language inference techniques on it.

2 Generic Modeling Environment

The Generic Modeling Environment (GME) is a modeling tool used in MARS. The GME is a modeling environment that can be configured and adapted from meta-level specifications (called the metamodel, or modeling paradigm) that describe the domain. When using the GME, a modeler loads a metamodel into the tool to define an environment containing all the modeling elements and valid relationships that can be constructed in a specific domain. Models are stored in the GME as objects in a database repository, and an API is provided by GME for model traversal using a standard integration mechanism (i.e., Microsoft Component Object Model – http://www.microsoft.com/com).

The GME tool can be downloaded from http://www.isis.vanderbilt.edu/Projects/gme

3 The LISA Language Development Environment

LISA is an interactive environment for programming language development where users can specify, generate, compile-on-the-fly and execute programs in a newly specified language. From the formal language specifications and attribute grammars, LISA produces a language-specific environment that includes a compiler/interpreter and various language-based tools (e.g., language knowledgeable editor, visualizers, and animators) for the specified language. LISA was created to assist language designers and implementers in incremental language development of Domain Specific Languages. The Model Representation Language (MRL) and the metamodel inference engine in MARS were implemented using LISA.

The LISA tool can be downloaded from

http://marcel.uni-mb.si/lisa/

Case Studies

To measure the effectiveness of MARS, we applied the system to the following diverse domains:

Finite State Machine (FSM) (case study of the paper – see the publications section)
Network Diagram Modeling Language
AudioVideo System Modeling Language
Petri Net Modeling Language

The FSM model is a simple model of computation consisting of a set of states, a start state, an input alphabet, a transition function, and a set of end states. It is also smaller and less elaborate than the Network model. The Network metamodel contains networking concepts (e.g., routers, hosts, and ports) as well as the valid connections among all entities. The Petri Net metamodel consists of the elements Place and Transition, as well as the connections between them. A Place can also hold a certain number of tokens. The AudioVideo System metamodel describes a language for configuring a home entertainment system consisting of domain elements (e.g., VCR, DVD, LD, MiniDisc, and other assorted electronics) and the connections between them.

The MARS system is a step-by-step application of the following tasks:

Affirm that you have Internet Explorer (version 6.0 or above), LISA, and GME installed
Apply the XSLT Transformer file to the GME instance model XML file.
Save the resulting MRL output as a LISA source file.
Load the mars_LisaTransformer file into LISA, and click on Compiler -> Build
Open the LISA source file from step 3.
Click on Run->run in LISA.
The resulting output will consist of a “grammar” text file and an “Inferred Meta-Model” XML file.
Load the inferred meta-model XML file into GME.

Download the files here:

XSLT Transformer [step2] Latest: Version 2.0

Mars LisaTransformer [step4] Latest: Version 4.1

Experimental Results

In this section, we provide snapshots and results of our experiments on the aforementioned domains.

Finite State Machine :

Download four instance models here:

Original Meta-Model:

Inferred Meta-Model:

Inferred CFG:

1. STATEDIAGRAM -> 'model' StateDiagram { PARTS0 }

2. PARTS0 -> MODELATOM0 FIELDS0 CONNECTIONS0

3. MODELATOM0 -> STARTSTATES ENDSTATES STATES

4. STARTSTATES -> STARTSTATE

5. ENDSTATES -> ENDSTATE ENDSTATES | ENDSTATE

6. STATES -> STATE STATES | ε

7. FIELDS0 -> ε

8. CONNECTIONS0 -> 'connection' TRANSITION

9. TRANSITION -> transition : SRC0 -> DST0 ; TRANSITION | transition : SRC0 -> DST0 ;

10. SRC0 -> 'fco' FCO1

11. FCO1 -> STARTSTATE|STATE

12. DST0 -> 'fco' FCO2

13. FCO2 -> ENDSTATE|STATE

14. STARTSTATE -> 'atom' StartState { FIELDS1 }

15. FIELDS1 -> ε

16. ENDSTATE -> 'atom' EndState { FIELDS2 }

17. FIELDS2 -> ε

18. STATE -> 'atom' State { FIELDS3 }

19. FIELDS3 -> ε

Network Diagram Modeling Language:

Download a sample instance model here

Original Meta-Model:

Inferred Meta-Model:

Inferred CFG:

1. NETDIAGRAM -> 'model' NetDiagram { PARTS0 }

2. PARTS0 -> MODELATOM0 FIELDS0 CONNECTIONS0

3. MODELATOM0 -> HOSTS WSGROUPS PERIMETERS NETWORKS ROUTERS NETDIAGRAMS

4. HOSTS -> HOST HOSTS | ε

5. WSGROUPS -> WSGROUP WSGROUPS | ε

6. PERIMETERS -> PERIMETER PERIMETERS | ε

7. NETWORKS -> NETWORK NETWORKS | ε

8. ROUTERS -> ROUTER ROUTERS | ε

9. NETDIAGRAMS -> NETDIAGRAM NETDIAGRAMS | ε

10. FIELDS0 -> ε

11. CONNECTIONS0 -> 'connection' NETCONNECTION NETWORKEQUIV

12. NETCONNECTION -> NetConnection : SRC0 -> DST0 ; NETCONNECTION | ε

13. SRC0 -> 'fco' FCO1

14. FCO1 -> HOST|WSGROUP|PORT

15. DST0 -> 'fco' FCO2

16. FCO2 -> PERIMETER|NETWORK

17. NETWORKEQUIV -> NetworkEquiv : PERIMETER -> DST1 ; NETWORKEQUIV | ε

18. DST1 -> FCO2

19. ROUTER -> 'model' Router { PARTS1 }

20. PARTS1 -> MODELATOM1 FIELDS1 CONNECTIONS1

21. MODELATOM1 -> PORTS

22. PORTS -> PORT PORTS | ε

23. FIELDS1 -> 'fields' Family

24. CONNECTIONS1 -> ε

25. HOST -> 'atom' Host { FIELDS2 }

26. FIELDS2 -> 'fields' IPAddress

27. WSGROUP -> 'atom' WSGroup { FIELDS3 }

28. FIELDS3 -> 'fields' AddressFirst AddressLast Number RoomLocation Workload

29. PERIMETER -> 'atom' Perimeter { FIELDS4 }

30. FIELDS4 -> ε

31. NETWORK -> 'atom' Network { FIELDS5 }

32. FIELDS5 -> 'fields' NetMask NetworkAddress

33. PORT -> 'atom' Port { FIELDS6 }

34. FIELDS6 -> 'fields' IFSpeed IFType IPAddress

Petri Net Modeling Language:

Download a sample instance model here

Original Meta-Model:

Inferred Meta-Model:

Inferred CFG:

1. PETRINET -> 'model' PetriNet { PARTS0 }

2. PARTS0 -> MODELATOM0 FIELDS0 CONNECTIONS0

3. MODELATOM0 -> TRANSITIONS PLACES

4. TRANSITIONS -> TRANSITION TRANSITIONS | TRANSITION

5. PLACES -> PLACE PLACES | PLACE

6. FIELDS0 -> ε

7. CONNECTIONS0 -> 'connection' TRANS2PLACE PLACE2TRANS

8. TRANS2PLACE -> trans2place : TRANSITION -> PLACE ; TRANS2PLACE | trans2place : TRANSITION -> PLACE ;

9. PLACE2TRANS -> place2trans : PLACE -> TRANSITION ; PLACE2TRANS | place2trans : PLACE -> TRANSITION ;

10. TRANSITION -> 'atom' Transition { FIELDS1 }

11. FIELDS1 -> 'fields' Name Description

12. PLACE -> 'atom' Place { FIELDS2 }

13. FIELDS2 -> 'fields' Name numberOfTokens Description

AudioVideo System Modeling Language:

Download an instance model here

Original Meta-Model:

Inferred Meta-Model:

Inferred CFG:

1. AUDIOSYSTEM -> 'model' audiosystem { PARTS0 }

2. PARTS0 -> MODELATOM0 FIELDS0 CONNECTIONS0

3. MODELATOM0 -> SPEAKERS MICS LDS VCRS LPS DVDS TVS DATS CDS AUDIOPROCESSORS

4. SPEAKERS -> SPEAKER SPEAKERS | SPEAKER

5. MICS -> MIC

6. LDS -> LD

7. VCRS -> VCR

8. LPS -> LP

9. DVDS -> DVD

10. TVS -> TV

11. DATS -> DAT

12. CDS -> CD

13. AUDIOPROCESSORS -> AUDIOPROCESSOR

14. FIELDS0 -> eps

15. IOPORTCONN -> ioportconn : SRC0 -> DST0 ; IOPORTCONN | ioportconn : SRC0 -> DST0 ;

16. SRC0 -> 'fco' FCO1

17. FCO1 -> OUTPUTPORT|MIC

18. DST0 -> 'fco' FCO2

19. FCO2 -> SPEAKER|INPUTPORT

20. COAXIALCABLE -> coaxialcable : LD -> AUDIOPROCESSOR ; COAXIALCABLE | coaxialcable : LD -> AUDIOPROCESSOR ;

21. RCACABLE -> rcacable : SRC1 -> AUDIOPROCESSOR ; RCACABLE | rcacable : SRC1 -> AUDIOPROCESSOR ;

22. SRC1 -> 'fco' FCO5

23. FCO5 -> VCR|LP|TV|CD

24. FIBEROPTICCABLE -> fiberopticcable : SRC2 -> AUDIOPROCESSOR ; FIBEROPTICCABLE | fiberopticcable : SRC2 -> AUDIOPROCESSOR ;

25. SRC2 -> 'fco' FCO7

26. FCO7 -> DVD|DAT

27. CONNECTIONS0 -> 'connection' IOPORTCONN COAXIALCABLE RCACABLE FIBEROPTICCABLE

28. AUDIOPROCESSOR -> 'model' audioprocessor { PARTS1 }

29. PARTS1 -> MODELATOM1 FIELDS1 CONNECTIONS1

30. MODELATOM1 -> HOUSECURRENTS BATTERYS OUTPUTPORTS INPUTPORTS AUDIOPROCESSORS

31. HOUSECURRENTS -> HOUSECURRENT

32. BATTERYS -> BATTERY

33. OUTPUTPORTS -> OUTPUTPORT OUTPUTPORTS | OUTPUTPORT

34. INPUTPORTS -> INPUTPORT | eps

35. AUDIOPROCESSORS -> AUDIOPROCESSOR AUDIOPROCESSORS | eps

36. FIELDS1 -> eps

37. PORT2PORTCONN -> port2portconn : SRC3 -> DST1 ; PORT2PORTCONN | eps

38. SRC3 -> 'fco' FCO9

39. FCO9 -> OUTPUTPORT|INPUTPORT

40. DST3 -> FCO9

41. CONNECTIONS1 -> 'connection' PORT2PORTCONN

42. HOUSECURRENT -> 'atom' housecurrent{ FIELDS2 }

43. FIELDS2 -> eps

44. BATTERY -> 'atom' battery{ FIELDS3 }

45. FIELDS3 -> eps

46. OUTPUTPORT -> 'atom' outputport{ FIELDS4 }

47. FIELDS4 -> 'fields' Impedance

48. INPUTPORT -> 'atom' inputport{ FIELDS5 }

49. FIELDS5 -> 'fields' Impedance

50. SPEAKER -> 'atom' speaker{ FIELDS6 }

51. FIELDS6 -> 'fields' Quality

52. MIC -> 'atom' mic{ FIELDS7 }

53. FIELDS7 -> 'fields' Quality

54. LD -> 'atom' ld{ FIELDS8 }

55. FIELDS8 -> eps

56. VCR -> 'atom' vcr{ FIELDS9 }

57. FIELDS9 -> eps

58. LP -> 'atom' lp{ FIELDS10 }

59. FIELDS10 -> eps

60. DVD -> 'atom' dvd{ FIELDS11 }

61. FIELDS11 -> eps

62. TV -> 'atom' tv{ FIELDS12 }

63. FIELDS12 -> eps

64. DAT -> 'atom' dat{ FIELDS13 }

65. FIELDS13 -> eps

66. CD -> 'atom' cd{ FIELDS14 }

67. FIELDS14 -> eps

We have also applied MARS on the large multi-tiered ESML domain. ESML is a domain-specific graphical modeling language developed for modeling Real-Time Mission Computing Embedded Avionics applications. The ESML contains instance models representing mission computing avionics scenarios. The ESML is a large domain, with models arranged in multiple folders. Currently MARS is limited to inferring single folder metamodel domains. We hope to extend this capability to infer multi-tiered metamodels.

Publications:

1) Faizan Javed, Marjan Mernik, Jeff Gray and Barrett Bryant, "MARS: A MetaModel Recovery System Using Grammar Inference",

Technical Report UABCIS-TR-2006-0724-1, UAB, 2006 [PDF]

This paper has been accepted by the journal Information and Software Technology, Elsevier, 2007, doi:10.1016/j.infsof.2007.08.003

Contact : Faizan Javed, email: javedf At cis.uab.edu