Control flow analysis of UML 2.0 sequence diagrams

Carleton University TR SCE-05-09

Updated: September 2005

Control Flow Analysis of UML 2.0 Sequence Diagrams Vahid Garousi, Lionel Briand and Yvan Labiche Software Quality Engineering Laboratory (SQUALL) www.sce.carleton.ca/squall Department of Systems and Computer Engineering, Carleton University 1125 Colonel By Drive, Ottawa, ON K1S5B6, Canada {vahid|briand|labiche}@sce.carleton.ca

Abstract This article presents a control flow analysis methodology based on UML 2.0 sequence diagrams (SD). In contrast to the conventional code-based control flow analysis techniques, this technique can be used earlier in software development life cycle, when the UML design model of a system becomes available. Among many applications, this technique can be used in SD-based test techniques, model comprehension and model execution in the context of MDA. Based on the well-defined UML 2.0 activity diagrams, we propose an extended activity diagram metamodel, referred to as Concurrent Control Flow Graph (CCFG), to support control flow analysis of UML 2.0 sequence diagrams. Our strategy in this article is to define an OCL-based mapping in a formal and verifiable form as consistency rules between a SD and a CCFG, so as to ensure the completeness of the rules and the CCFG metamodel with respect to our control flow analysis purpose and allow their verification. Completeness here means if the CCFG metamodel has all classes and associations needed, and the rules are adequate with respect to our purpose. Furthermore, we define Concurrent Control Flow Paths, which are a generalization of the conventional Control Flow Path concept. The control flow analysis technique is applied to an example SD to demonstrate the feasibility of the approach.

1

Carleton University TR SCE-05-09

Updated: September 2005

Table of Contents 1 INTRODUCTION ....................................................................................................................................................... 6 1.1 MOTIVATION AND GOAL ......................................................................................................................................... 6 1.2 APPROACH .............................................................................................................................................................. 7 1.3 STRUCTURE ............................................................................................................................................................. 7 2 BACKGROUND.......................................................................................................................................................... 8 2.1 CODE- VS. MODEL-BASED CONTROL FLOW ANALYSIS............................................................................................ 8 2.2 RELATED WORKS .................................................................................................................................................. 10 2.3 MOTIVATIONS ....................................................................................................................................................... 13 2.4 PROBLEM STATEMENT .......................................................................................................................................... 14 3 AN OVERVIEW ON UML 2.0 SEQUENCE DIAGRAMS .................................................................................. 14 3.1 NEW FEATURES AND METAMODEL ....................................................................................................................... 14 3.2 FEATURES SUPPORTED IN THIS WORK ................................................................................................................... 17 4 CONCURRENT CFG: A CONTROL FLOW MODEL FOR SDS ...................................................................... 18 4.1 CHALLENGES OF SDS’ CFA .................................................................................................................................. 18 4.1.1 Impact of Asynchronous Messages................................................................................................................ 18 4.1.2 Impact of par Interaction Operator............................................................................................................... 19 4.2 TOWARDS A CFM FOR SDS ................................................................................................................................... 19 4.3 A BRIEF LOOK AT UML 2.0 ACTIVITY DIAGRAMS................................................................................................ 20 4.3.1 Choosing the Right Package.......................................................................................................................... 21 4.3.2 Metamodel of the IntermediateActivities Package ........................................................................................ 22 4.4 CONCURRENT CFG (CCFG).................................................................................................................................. 23 4.4.1 Extension to the IntermediateActivities Package........................................................................................... 23 4.4.2 CCFG Metamodel ......................................................................................................................................... 24 4.4.3 OCL Constraints of the Metamodel............................................................................................................... 25 5 A SET OF CONSISTENCY RULE-BASED MAPPING RULES FROM SDS TO CCFGS .............................. 25 5.1 LIST OF CONSISTENCY RULES ............................................................................................................................... 26 5.2 INTERACTIONFRAGMENTàACTIVITY ....................................................................................................................... 26 5.3 FIRST MESSAGE ENDàFLOW BETWEEN INITIALNODE AND FIRST CONTROL NODE ................................................. 27 5.4 SYNCHCALL/SYNCHSIGNALàCALLNODE ................................................................................................................ 28 5.5 ASYNCHCALL/ASYNCHSIGNALà(CALLNODE+FORKNODE)/REPLYNODE ................................................................ 29 5.6 MESSAGE.SENDEVENT/MESSAGE.RECEIVEEVENTàCONTROLFLOW ........................................................................ 32 5.7 LIFELINEàOBJECTPARTITION ................................................................................................................................ 33 5.8 PARALLEL (PAR) COMBINEDFRAGMENTàFORKNODE ........................................................................................... 34 5.9 LOOP COMBINEDFRAGMENTà DECISIONNODE ...................................................................................................... 36 5.10 ALT/OPT COMBINEDFRAGMENTàDECISIONNODE................................................................................................. 37 5.11 BREAK COMBINEDFRAGMENTàACTIVITYEDGE..................................................................................................... 39 5.12 LAST MESSAGE ENDSàFLOWS BETWEEN ENDING CONTROL NODES AND ACTIVITYFINALNODE ........................... 39 5.13 INTERACTIONOCCURRENCEàCONTROL FLOW ACROSS CCFGS........................................................................... 41 5.14 POLYMORPHIC MESSAGEàDECISIONNODE ......................................................................................................... 42 5.14.1 Metamodel of Generalization Relationships in CDs ................................................................................... 43 5.14.2 Consistency Rule ......................................................................................................................................... 44 5.15 INTERACTION FRAGMENT AND ITS ENCLOSING INTERACTION FRAGMENTàCCFG AND ITS PARENT CCFG...... 46 5.16 UTILITY FUNCTIONS ............................................................................................................................................ 47 5.16.1 getCCFG ..................................................................................................................................................... 48 5.16.2 getTypeOfMessage ...................................................................................................................................... 48 5.16.3 getObjectPartition ....................................................................................................................................... 49 5.16.4 getFirstMessage .......................................................................................................................................... 49 5.16.5 getLastMessages.......................................................................................................................................... 49 5.16.6 getFirstEventOccurrence ............................................................................................................................ 50

2

Carleton University TR SCE-05-09

Updated: September 2005

5.16.7 getInitialNode.............................................................................................................................................. 50 5.16.8 getFinalNodes ............................................................................................................................................. 51 5.16.9 MultipleIncomingControlsFlowToMergeNode ........................................................................................... 51 6 CONCURRENT CONTROL FLOW PATHS........................................................................................................ 52 6.1 GRAMMAR ............................................................................................................................................................. 52 6.2 INTER-SD CCFPS .................................................................................................................................................. 53 6.3 REPRESENTATION OF CCFPS AS GRAPHS .............................................................................................................. 53 7 ACKNOWLEDGEMENTS...................................................................................................................................... 54 8 CONCLUSIONS AND FUTURE WORKS ............................................................................................................ 54 REFERENCES ............................................................................................................................................................. 54

3

Carleton University TR SCE-05-09

Updated: September 2005

List of Figures

FIGURE 1-DEPENDENCIES OF THE DIFFERENT SECTIONS OF THIS ARTICLE ......................................................................... 7 FIGURE 2-APPLICATION AREAS OF CBCFA AND MBCFA ................................................................................................ 8 FIGURE 3-AN EXAMPLE ILLUSTRATING THE NEW FEATURES OF THE UML 2.0 SDS ........................................................ 16 FIGURE 4-NOTATIONS FOR SYNCHRONOUS/ASYNCHRONOUS MESSAGES AND REPLIES IN UML 1.X AND 2.0................... 17 FIGURE 5-UML 2.0 SEQUENCE DIAGRAM METAMODEL ................................................................................................. 17 FIGURE 6-A SD WITH ASYNCHRONOUS MESSAGES.......................................................................................................... 19 FIGURE 7- A SD WITH PAR INTERACTION OPERATOR ...................................................................................................... 19 FIGURE 8- DEPENDENCIES OF THE UML 2.0 ACTIVITY PACKAGES AND OUR PROPOSED CCFG ACTIVITY PACKAGE ....... 21 FIGURE 9- METAMODEL OF THE UML 2.0 INTERMEDIATEACTIVITIES PACKAGE ............................................................ 22 FIGURE 10- CCFG METAMODEL ..................................................................................................................................... 24 FIGURE 12-PART OF THE CCFG INSTANCE CCFG BASED ON SD IN FIGURE 6 THAT SATISFIES CONSISTENCY RULE 2 ..... 27 FIGURE 13-PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN FIGURE 12 ........................................... 28 FIGURE 14-PART OF THE CCFG INSTANCE CORRESPONDING TO MESSAGE A IN SD OF FIGURE 6 THAT SATISFIES CONSISTENCY RULE 3 ............................................................................................................................................. 29 FIGURE 15-PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN FIGURE 14 ........................................... 29 FIGURE 16-PART OF THE CCFG INSTANCE CORRESPONDING TO THE ASYNCHRONOUS MESSAGE C IN SD OF FIGURE 6 THAT SATISFIES CONSISTENCY RULE 4 ................................................................................................................... 31 FIGURE 17-PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN FIGURE 16 ........................................... 31 FIGURE 18-PART OF THE CCFG INSTANCE CORRESPONDING TO THE REPLY MESSAGE B IN SD OF FIGURE 6 THAT SATISFIES CONSISTENCY RULE 4............................................................................................................................. 31 FIGURE 19-PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN FIGURE 18 ........................................... 32 FIGURE 20-PART OF THE CCFG INSTANCE CORRESPONDING TO THE CONTROL FLOW BETWEEN MESSAGES A AND B IN SD OF FIGURE 6 THAT SATISFIES CONSISTENCY RULE 5 ............................................................................................... 33 FIGURE 21-PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN FIGURE 20 ........................................... 33 FIGURE 22-PART OF THE CCFG INSTANCE CORRESPONDING TO LIFELINE PF:PROCESSORFACTORY IN SD OF FIGURE 6 THAT SATISFIES CONSISTENCY RULE 6 ................................................................................................................... 34 FIGURE 23-PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN FIGURE 22 ........................................... 34 FIGURE 24-PART OF THE CCFG INSTANCE CORRESPONDING TO PAR COMBINED FRAGMENT IN SD OF FIGURE 7 THAT SATISFIES CONSISTENCY RULE 7............................................................................................................................. 35 FIGURE 25-PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN FIGURE 24 ........................................... 36 FIGURE 26-PART OF THE CCFG INSTANCE CORRESPONDING TO LOOP COMBINED FRAGMENT IN SD OF FIGURE 6 THAT SATISFIES CONSISTENCY RULE 8............................................................................................................................. 37 FIGURE 27-PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN FIGURE 26 ........................................... 37 FIGURE 28-PART OF THE CCFG INSTANCE CORRESPONDING TO ALT COMBINED FRAGMENT IN SD OF FIGURE 6 THAT SATISFIES CONSISTENCY RULE 9............................................................................................................................. 38 FIGURE 29-PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN FIGURE 28 ........................................... 39 FIGURE 30-PART OF THE CCFG INSTANCE LOOPCCFG CORRESPONDING TO LOOP COMBINED FRAGMENT IN SD OF FIGURE 6 THAT SATISFIES CONSISTENCY RULE 11 .................................................................................................. 40 FIGURE 31-PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN FIGURE 30 ........................................... 40 FIGURE 32-PART OF THE CCFG INSTANCE CCFG CORRESPONDING TO THE INTERACTION OCCURRENCE N IN SD OF FIGURE 6 THAT SATISFIES CONSISTENCY RULE 12 .................................................................................................. 42 FIGURE 33-PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN FIGURE 32 ........................................... 42 FIGURE 34-A SEQUENCE AND A CLASS DIAGRAM SHOWING THE EFFECT OF CLASSES WITH POLYMORPHISM IN CFA ...... 43 FIGURE 35-PART OF THE UML 2.0 ‘CLASSIFIER DIAGRAM’, SECTION 7.8 OF [11] .......................................................... 43 FIGURE 36-PART OF THE CCFG INSTANCE CCFG CORRESPONDING TO THE MESSAGE SEND(DATE) IN SD M OF FIGURE 34 THAT SATISFIES CONSISTENCY RULE 13.................................................................................................................. 46 FIGURE 37-PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN FIGURE 36 ........................................... 46 FIGURE 38-(A): PART OF THE TWO CCFG INSTANCES SDCCFG AND LOOPIOCCFG CORRESPONDING TO THE SD AND LOOP COMBINEDFRAGMENT IN FIGURE 6 THAT SATISFIES CONSISTENCY RULE 14 - (B): PART OF THE CCFG, CORRESPONDING TO THE INSTANCES SHOWN IN (A)................................................................................................. 47 FIGURE 39-UTILITY CLASS UTIL CONTAINING A SET OF UTILITY FUNCTIONS USED IN THE CONSISTENCY RULES ............. 48 FIGURE 40-RELATIONSHIP BETWEEN EVENTOCCURRENCE‘S AND EXECUTIONOCCURRENCE‘S ........................................ 48 FIGURE 41-ORDERING EVENTOCCURRENCES WITH GENERALORDERINGS ..................................................................... 50

4

Carleton University TR SCE-05-09

Updated: September 2005

FIGURE 42-(A): PART OF THE CCFG INSTANCE CCFG CORRESPONDING TO THE INCOMING FLOWS OF CONTROL NODE H IN SD OF FIGURE 6 THAT HAS BEEN CREATED AFTER APPLYING THE FUNCTION MULTIPLEINCOMINGCONTROLSFLOWTOMERGENODE -(B): PART OF THE CCFG, CORRESPONDING TO THE INSTANCE SHOWN IN (A) .......................................................................................................................................................... 52 FIGURE 43- CCFPS OF THE CCFG IN FIGURE 11............................................................................................................. 53 FIGURE 44- REPRESENTATION OF CCFPS AS GRAPHS ..................................................................................................... 54

5

Carleton University TR SCE-05-09

Updated: September 2005

1 INTRODUCTION 1.1 Motivation and Goal Control Flow Analysis (CFA) [1] is a widely used approach for analyzing structured and object-oriented programs. A Control Flow Graph (CFG) [1] is a static representation of a program that represents all alternatives of control flow. For example, both choices of an IF statement are represented in a CFG. A cycle in a CFG may imply that there is a loop in the code. The concept of CFG was first used as a data structure in compilers [1] for code optimization purposes. Later, it was adopted extensively in the software engineering community and in particularly the software testing community (e.g., [2-5]). In a CFG, different paths from the start node to the end node are called Control Flow Paths (CFP), which show the different paths a program may follow during execution. More advanced CFA models have been proposed to study inter-procedural control flow such as call graphs and call chains [1]. Furthermore, Data Flow Analysis (DFA) and data flow-based testing techniques (such as [69]) are also, to a great extent, based on CFA: different control flow paths (CFP), derived by CFA, are examined to extract data flow information such as def-use pairs (definition-uses of data). Based on the source of information to derive the control flow information of a system, we can divide the CFA techniques into two groups: code-based and model-based. Code-based CFA (CBCFA) is the traditional CFA [1], in which control flow information is derived from the available source code. CBCFA has been greatly used in the software testing literature [2-5] and is based on strong mathematical foundations [1]. On the other hand, we define model-based CFA (MBCFA) to be the derivation of control flow information from the design model (such as UML [10-12]) of a software system. To the best knowledge of the authors, there have been few works [13-17] on MBCFA and in particular on UML-based CFA. UML provides ways to model the behavior of an OO system using interaction (sequence and collaboration) diagrams. However, as it will be discussed in Section 4.1, derivation and analysis of control flow information are not straightforward in UML interaction diagrams for instance because of asynchronous messages and parallel combined fragments. The motivation of our work is twofold: (1) When and where is MBCFA preferable over CBCFA? and (2) What is missing in the existing works and has to be addressed by a comprehensive MBCFA technique? These two aspects will be discussed in Sections 2.1 and 2.2, respectively. Because of higher level of abstraction, one of the advantages of MBCFA over CBCFA is easier extraction of concurrent control flow and dynamic control flow information (such as polymorphism), which will benefit applications such as testing and refactoring. As another benefit, MBCFA techniques can be used as a model-based test requirements generation methodology, needed by various testing techniques, earlier in the software development life cycle, i.e., as early as the UML design model of a system is available. Our MBCFA technique can also be useful in most of the existing SD-based testing techniques, such as [13, 18-22]. SDs have been the basis for several approaches for testing of object-oriented software [11, 18-20, 23-25]. The advantage of using our approach will be to have a formal and fully automatable method to derive control flow information from SDs. Some of the possible applications of our approach in the context of MDA [26] include the testing phase of the MDA software development life cycle (Figure 1-2 of [26]) and also model compilation, comprehension, and execution. Model execution, model comprehension, model checking, model optimization, and model walk-through are other possible applications of MBCFA in the context of MDA. These tentative application areas remain to be further investigated. As to the advantage of this work over the related works [13-17], our MBCFA technique provides a formal metamodel-based approach to derive concurrent control flow information from SDs. Unlike the existing

6

Carleton University TR SCE-05-09

Updated: September 2005

works, it does not only cover all UML 2.0 SD features, but it also proposes a Control Flow Model1 (CFM) referred to as Concurrent Control Flow Graph (CCFG). Our goals are then to present a set of formal mappings from an instance of SD metamodel to an instance of CCFG metamodel and to propose a representation for CFPs, referred to as Concurrent CFPs (CCFPs), as a grammar, which will account for concurrency in CCFGs. 1.2 Approach Our MBCFA technique assumes that the SDs and CDs (class diagrams) of a system’s UML 2.0 [11] design model are available. The technique derives the control flow information for each SD. SDs will be used as the input for the derivation of control flow information, while CDs will be used to find any possible polymorphic behavior of classes in SD lifelines (Section 5.14). To perform a MBCFA based on UML 2.0, the following three sub-problems will be addressed in this article: 1.

The first problem is to find a suitable CFM (Control Flow Model) for MBCFA, which we will call CCFG.

2.

Assuming the SDs and CDs of a system’s UML 2.0 design model are given, the second problem is to devise a formal transformation technique from SDs to the chosen CFM, considering the inheritance relationships of classes in CDs, which might affect control flow.

3.

The third problem is to develop a formal approach to derive different CFPs of a CCFG.

1.3 Structure The paper is structured as follows. The background information is given in Section 2, where we briefly discuss CBCFA versus MBCFA and present the related works, the motivations, and the problem statement. Section 3 provides a brief overview on UML 2.0 SDs. A Control Flow Model (referred to as CCFG), for MBCFA, is presented in Section 4. Section 5 presents a set of OCL-based mapping rules from SDs to CCFGs. Our MBCFA technique is validated on an example SD in Sections 5. Based on CCFGs metamodel, Section 6 discusses how different control flow paths (CFP) of a SD can be derived. Section 7 finally concludes this article and points out some of the future work directions. For clarity, the dependencies of the different sections of this article are shown in Figure 1. Background Information (Sec. 2)

A review of UML 2.0 SDs (Sec. 3)

Finding a CFM for CFA of SDs (referred to as CCFG) (Sec. 4)

Formal Mapping from SDs to CCFGs (Sec. 5)

Formalism and Derivation of CCFPs (Sec. 6)

CFM: Control Flow Model CCFG: Concurrent Control Flow Graph CCFP: Concurrent Control Flow Path

Figure 1-Dependencies of the different sections of this article

1

A Control Flow Model (CFM) here is a model to represent SD’s control flow information. 7

Carleton University TR SCE-05-09

Updated: September 2005

2 BACKGROUND 2.1 Code- vs. Model-based Control Flow Analysis CBCFA and MBCFA were defined in Section 1.1. To classify the usefulness of CBCFA and MBCFA, some of their application areas and their inter-relationships are shown in Figure 2. Application areas

void o1::m1(o2:C2, o3:C3): float { … if (x) o2.m2() else o3.m3() … }

CBCFA

Control/data flow information, e.g. control flow paths (CFPs), def-use

-End3 *1

sd m1 o

o

-End4

o MBCFA

alt

CB

- Software testing CB/MB - Re-engineering - Refactoring - Conformance validation/verification of model with code*

UML Model

Class Diagram

- Reverse Engineering - Code optimization - Code walk-through - Code (traditional) compilers - Program comprehension

[x] m2()

Control/data flow information, e.g. control flow paths (CFPs), def-use

[else] m3()

- Pre-implementation model-based validation and verification - Model execution - Model compilers - Model comprehension - Model check* - Model optimization* MB - Model walk-through* * indicates the possible application areas that have to be studied further.

other diagrams...

Figure 2-Application areas of CBCFA and MBCFA

The application area group, tagged with CB, indicates some of the uses of CBCFA. CBCFA has been used in areas such as reverse engineering [27], code optimization [1], program comprehension [28] and code walkthrough. The CB/MB group in Figure 2 lists some of the areas which use (or can use) either CBCFA, MBCFA or both. Software testing [2-5] is one such area where control flow information play an important role in deriving test cases. White-box test technique use CBCFA. Some existing SD-based testing techniques, such as [13, 18-22], may utilize a MBCFA technique to generate test cases. An advantage of using a formal MBCFA technique (such as ours) will be to have a formal and fully automatable method to derive control flow information from SDs. As another application area, many reengineering techniques (such as [29, 30]) use CBCFA. An area, to be investigated in the future, is to reengineer software products based on their design models. MBCFA will be one of the required components in such techniques. As another suggested application, we can think of a combined use of MBCFA and CBCFA. They can be applied separately to design model and source code of a system, respectively. Afterwards, their generated CFMs (control flow models) can be compared to validate the correct implementation of the design model or to find missing functionality in any of the design or implementation stages. This is what we refer to as conformance validation/verification of model with code in Figure 2. The application area group, tagged with MB, denotes the areas that benefit from MBCFA directly. Some of these areas are model compilers and model execution [31], model comprehension [17, 32], which have already been exploited and our MBCFA technique can be applied to directly. In the context of UML, a model compiler turns an executable UML model into an implementation using a set of decisions about the target hardware and software environment [31]. Model execution is to execute the automatically-generated implementation of a model. This is the concept usually referred to as “automatic code generation from models” in CASE tools. Pre-implementation model-based verification and testing are also among other application of a MBCFA method. Model check, model optimization and model walk-through are the other possible applications that will find the output of MBCFA useful. Feasibility of these tentative application areas remain to be investigated further.

8

Carleton University TR SCE-05-09

Updated: September 2005

UML provides ways to model behavior of an OO system using interaction (sequence and collaboration) diagrams. Furthermore, UML 2.0 [11] has proposed a set of rich features such as interaction and combined fragments which enable designers to model code-like program structures such as conditions, loops and call to other SDs. The degree of formality in these modeling features has enhanced considerably in UML 2.0 [11] comparing to its previous 1.x versions (1.3 [10], 1.5 [12]). Therefore, a comprehensive MBCFA seems feasible. We believe that the use of either CBCFA or MBCFA does not violate the use of the other. They can be considered as complements and alternatives to each other as described next. In order to better understand the differences between CBCFA and MBCFA and analyze their advantages over one another, let us compare these two groups of CFA techniques in terms of their usefulness and the usage goals and constraints in application areas where they are to be utilized. A comparison of CBCFA and MBCFA is shown in Table 1, where they are compared according to six criteria. Source of information Lifecycle stage Extraction of concurrent control flow information Extraction of dynamic control flow information Control flow information accuracy in post-implementation stages Statement-level completeness

CBCFA

MBCFA

Source code Implementation Hard

Design model Design Easy

Hard

Easy

High

Low

High

Low

Table 1- Comparison of Code-based (CBCFA) vs. Model-based CFA (MBCFA)

Considering the first criterion in Table 1, CBCFA uses source code while MBCFA makes use of design model of a system as the source of information. The second criterion indicates that the earliest stage in a system lifecycle, when CBCFA is feasible, is the implementation stage, while MBCFA can be done as early as the design stage. This indicates that MBCFA can be employed before CBCFA and hence it can be used by testers to generate test requirements or test cases even before the source code of a system is ready. The third criterion in Table 1 is to take into account intra-method (CBCFA) or intra-SD (MBCFA) concurrency in control flow. Intra-method concurrency in CBCFA is when an asynchronous method call is made from a caller method. In MBCFA, two features (asynchronous message and parallel interaction fragments) of UML 2.0 SDs entail intra-SD concurrency in control flow. CBCFA is usually done either by static analysis or by dynamical execution (through instrumentation) of source code [1]. In both of these cases, the extraction of intra-method concurrent control flow seems to be a challenging task. In other words, conventional CBCFA techniques consider a process (or a procedure) at a time and derive the corresponding sequential control flow information. If the CFA of several concurrent processes is to be done using CBCFA, a separate CFG should be generated for each of them. In other words, concurrently-interleaved control flow information of several processes cannot be easily derived using traditional CBCFA techniques. While, on the other hand, concurrency-supporting SD features (asynchronous message and parallel interaction fragments) are easier to be located and analyzed to derive intra-SD concurrent control flow by MBCFA techniques. This is because in the case of CBCFA, the target of an asynchronous message is not explicitly found in the source code and identifying it requires static and dynamic analysis of the source code. On the other hand, the target of an asynchronous message is explicit in a SD. The concept of concurrent control flow is discussed in more detail in Section 4.1. The fourth criterion of Table 1 compares the two CFA methodologies from the standpoint of extraction of dynamic control flow information such as dynamic binding and polymorphism. As stated by Briand et al [33], extraction of such information from source code has many challenges. However, as we will discuss in

9

Carleton University TR SCE-05-09

Updated: September 2005

Section 5.14, determining polymorphic method calls is rather easy in MBCFA. Achieving such determinism is needed in many CFA applications areas, such as testing and program comprehension. In terms of control flow information accuracy in post-implementation stages (the fifth criterion), CBCFA provides more accurate information than MBCFA. What we mean by control flow information accuracy is whether the generated information corresponds to the software system at hand. Design models of systems are not always kept up-to-date with all changes in post-design stages. Therefore, based on such asynchrony between model and code, MBCFA will fail to provide accurate control flow information for the “real” software. While CBCFA will generate the truthful control flow information of the system, since it uses source code (the modified one in this case). Comparison in the sixth criterion is based on the statement-level completeness in the generated control flow information. Behavioral design models (such as UML SDs) provide message-level details, i.e., they do not include all the statements that are required to execute a use-case scenario. Therefore, control flow information from MBCFA only contains the messages exchanged among objects, and does not include nonmessage statements such as those manipulating local variables or calls to libraries. While source code is actually the set of statements that will really run. CBCFA works directly on source code and its output should be enough for this purpose. We briefly compared CBCFA and MBCFA above and discussed some of their advantages and drawbacks compared to one another. Since model-driven software engineering is rather recent, therefore MBCFA techniques are more recent than CBCFA ones. Depending on the usage goals and constraints of a specific application area, it seems that MBCFA can be a complement or an alternative to CBCFA. In the following, we give an overview on the related works. Since CBCFA has been around for several decades [34] and the related literature is very extensive (for instance [35-41]), we do not survey the related works on CBCFA in this article. However, we focus on the existing works on MBCFA. We will briefly compare the related works and use it to clarify the second part of our work’s motivation in Section 2.3. 2.2 Related Works Conventional CFA techniques (CBCFA in our definition) have been addressed with solid mathematical foundations and have been used in numerous testing approaches (for instance [2-5]). There are even numerous tools that use CBCFA to support code-coverage based test case generation, such as Parasoft Jtest and C++ Test [42], Rational Purify, PureCoverage and Test RealTime [43], Telcordia xSuds [44], McCabe Test and Coverage Server [45], and IPL Cantata and Cantata++ [46]. To the authors’ knowledge, none of these tools handle concurrency in control flow. On the other hand, with the increased focus on the model-driven design and testing techniques in the recent years, the need for MBCFA techniques is arising. UML has become the de facto standard for modeling object-oriented software for nearly seventy percent of IT industry [47]. It would be useful to derive control flow information directly from the UML design models. To the best knowledge of the authors, there have been relatively few works on MBCFA techniques based on UML. Differences among existing approaches [13-17] and the current work are summarized in Table 2. The strategies reported in Table 2 are compared according to eleven criteria: 1.

Source of information: The source model on which MBCFA is applied. It can be either SD or reverse engineered SD.

2.

UML version supported: UML 1.x (1.3 [10], 1.5 [12]) or 2.0 [11]. We do not distinguish between 1.x versions in this comparison.

3.

CFM produced: The output Control Flow Model (CFM) produced by a MBCFA technique. Different works have used different CFMs. Some of the CFMs reported are IRCFG (Inter-procedural

10

Carleton University TR SCE-05-09

Updated: September 2005

Restricted Control-Flow Graph)1, CRE (Concurrent Regular Expressions)2, and LGSPN (Labeled Generalized Stochastic Petri-Net)3. As it will be discussed, we propose a new UML activity-diagram like CFM referred to as Concurrent Control Flow Graph (CCFG) in this article. Rountev et al. [13] REng’d SD4 UML 1.x IRCFG By example

Okazaki et al. [14] SD UML 1.x CRE Set theory

Bernardi et al. [15] SD UML 1.x LGSPN By example

Cardoso et al. [16] SD UML 1.x Petri-Net By example

5. Transformation/mapping technique’s semantic style 6. Asynchronous message control flow support

By example

By example

No

7. Inter-SD control flow support 8. Loop support

No No

9. Condition support 10. Support for polymorphism in SD lifelines 11. CFP formalism

Yes No

No (but can be extended) No Only7 in CFM No No

Semiformal6 Yes

Yes

Yes

1. 2. 3. 4.

Source of information UML version supported Produced CFM Produced CFM’s formalism

This work

Formal

Burd et al. [17] SD UML 1.x None By example None

Yes

Not clear

Yes

No No

No No

No No

Yes Yes

No No

No No

Yes No

Yes Yes

No

No

No

Yes

SD UML 2.0 CCFG5 Metamodel Formal

Table 2- Comparison of existing MBCFA techniques

4.

Produced CFM’s semantic style: The degree of formality employed when defining the CFM (if any), ranging from a set of examples to a formal metamodel.

5.

Transformation/mapping technique’s semantic style: The degree of formality employed in defining the transformation/mapping from SDs to the CFM (if any), ranging from a set of examples to formal mapping rules.

6.

Asynchronous message control flow support: Whether the MBCFA technique supports the control flow resulted from asynchronous messages in SDs.

7.

Inter-SD control flow support: Whether inter-SD control flow is supported. As UML allows SDs to refer to each other using the concept of InteractionOccurrences in UML 2.0 (Section 14.3.10 of [11]), and an unnamed informal notation in UML 1.5 (Figure 3-58 of [12]), a complete UML-based MBCFA technique should support this feature.

8.

Loop support: If loops (in SD) are supported. It is good to mention that UML 2.0 has an enhanced loop support compared to 1.x versions.

“An IRCFG contains a set of Restricted CFGs (RCFGs), together with edges which connect these RCFGs. Each RCFG corresponds to a particular method and is similar to the CFG for that method, except that it is restricted to the flow of control that is relevant to message sending.” [13 2005]

1

CRE was proposed as algebraic descriptions of the language of Petri nets by Garg et al. [48]. It is an extension of regular expressions with four operators: interleaving, interleaving-closure, synchronous composition and renaming. 2

LGSPN is an extension to GSPN where labels are assigned to Petri-net places and transitions. GSPN is itself an extension to Petri nets that allows both timed transitions and immediate transitions [49].

3

Reverse engineered SD (from source code) Concurrent CFG (Section 4) 6 Plain English pseudo-code with some formal definitions 7 No discussion about loops in the transformation 4

5

11

Carleton University TR SCE-05-09

9.

Updated: September 2005

Condition support: Whether conditions on SD messages are supported by the MBCFA technique. It is good to mention that UML 1.x versions had less formal support for conditional interactions than UML 2.0.

10. Support of polymorphism in SD lifelines: If a lifeline class of a SD is the base class for several subclasses and at least one of its methods are overwritten by the sub-classes, then a polymorphic behavior can occur at runtime. This needs to be taken into consideration in MBCFA. 11. CFP formalism: If the technique has a formalism for CFPs and offers an algorithm to derive CFPs of a CFM. Considering the comparison given in Table 2, all of the existing works are based on UML 1.x versions. Only one of them ([14]) proposes a formal definition for the produced CFM. Only two ([15] and [16]) have formal transformation/mapping techniques. None of the existing works support inter-SD control flow (across SDs when a SD calls another SD) and polymorphism in SD lifelines. None of the approaches cover all criteria and this is the goal of the research reported in this paper (the last column in Table 2). There has been another group of related works which we can classify them as CBCFA techniques with concurrency analysis. To the best of the author’s knowledge, [41, 50-54] are among main contributions in this field, whereas most of them are based on formal method with high levels of abstraction. Differences between these approaches are summarized in Table 3.

1. Source language

2. CFM produced

3. Produced CFM’s semantic style 4. Transformation technique’s semantic style 5. Loop support 6. Condition support 7. CFP formalism

Gasser et al. [50] CML

Nielson et al. [41] CML

Blasio et al. [51] FHM OO calculus1

Bauer [52] Tiny Java2

Long et al. [53] Generic source code

Chamillard et al. [54] Generic source code (Ada as an example) TIG-based Petri-nets

Abstract analysis form Formal

Type and effect system

A-normal form

TIG3

Formal

Formal

Type and effect system Formal

Formal

By example

Formal (setbased analysis4) No Yes None

Formal (process algebra) Yes Yes None

Formal (setbased analysis) Not clear Not clear None

Formal (setbased analysis) No Yes None

By example

By example

No Yes None

Yes Yes Yes

Table 3- Comparison of existing CBCFA techniques with concurrency control flow support

The strategies reported in Table 3 are compared according to the following criteria: 1.

Source language: The language on which a technique is based. Source language can be either a dedicated formal language (such as CML5), generic source code, or an specific programming language.

2.

CFM produced: The output Control Flow Model (CFM) used/produced by a technique.

3.

Produced CFM’s semantic style: The degree of formality employed defining the CFM (if any), ranging from a set of examples to a formal representation.

Fisher- Honsell-Mitchell functional object-oriented calculus [55] A modified (reduced) abstract syntax of Java 3 Task Interaction Graph 4 Set-based analysis [56] gathers static information about the values program variables may assume at runtime. 5 Concurrent Meta Language [57] 1

2

12

Carleton University TR SCE-05-09

Updated: September 2005

4.

Transformation technique’s semantic style: The degree of formality employed in defining the transformation from the source language to the CFM (if any), ranging from a set of examples to formal mapping rules.

5.

Loop support: If loops are supported.

6.

Condition support: Whether conditional statements are supported by a technique.

7.

CFP formalism: If the technique has a formalism for CFPs and offers an algorithm to derive CFPs of a CFM.

Considering the comparison given in Table 3, it seems that the level of abstraction is usually high for CBCFA techniques, with concurrency control flow support, proposed for compilers. In fact, this is needed due to the rigor used in compiler and language design fields. Another finding is that there are not so many such techniques (only [52] and [53] in our comparisons) to extract control low directly from source code. Discussion on CFPs was only addressed in one ([54]) of the techniques. There has been another group of contributions [27, 33, 58-66] which aim at reverse engineering SDs from either source code (or its instrumented version), virtual machines (such as JVM1), customized debuggers, or debug interfaces of programming languages. Most of the existing works produce just a partial version of SDs (a scenario diagram2 [33, 65]). One of the big challenges in this research direction is to reverse engineer complete SDs, which requires triggering all possible scenarios through multiple executions of the system, and their analysis/grouping into one sequence diagram. Such reverse engineering requires CBCFA. Another body of work (for instance [17 2002, 67]) present techniques to visualize the executions of SDs [17 2002] and statecharts [67]. These works indeed belong to model execution and model comprehension techniques. Although control flow information is vital for the visual execution of SDs and statecharts, the details of such visualization in terms of control flow information are not presented in [17 2002] nor in [67]. 2.3 Motivations The motivation of our work is twofold: (1) When and where is MBCFA preferable over CBCFA? and (2) What is missing in the related works and has to be addressed by a comprehensive MBCFA technique? We discussed these two aspects in Sections 2.1 and 2.2, respectively. The motivations of this work can be drawn from them as given next. We categorized CFA techniques into Code (CBCFA) and Model-based (MBCFA) groups in Section 2.1. The advantages and drawbacks for each of them were discussed. One advantage of MBCFA over CBCFA was that MBCFA can be employed earlier than CBCFA in the software lifecycle, i.e. as soon as a design model (in UML for example) of a system is ready. This can be useful for testing techniques that have to generate test cases before the system is implemented. Figure 2 presented the inter-relationships and some of the application areas of CBCFA and MBCFA in OO software engineering. Depending on the usage goals and constraints of a specific application area (Figure 2), any of those two CFA techniques may be used. As to the state-of-the-art of MBCFA and related works, we compared some of the MBCFA techniques in Section 2.2. As shown by our comparisons (Table 2), all of the previous related works have been based on UML 1.x version and, to the best of our knowledge, no UML 2.0-based MBCFA has been reported. In addition, none of the existing works satisfy all of the comparisons criteria, listed in Table 2. We believe that those criteria are crucial for a complete MBCFA technique to be formally presented, verified, and finally to

1

Java Virtual Machine

A scenario diagram is an incomplete sequence diagrams only denoting what happens in one particular scenario instead of modeling all possible alternatives for a use case [65].

2

13

Carleton University TR SCE-05-09

Updated: September 2005

generate comprehensive control flow information of a given SD. To address all these needs, we propose a MBCFA technique based on UML 2.0 SDs. 2.4 Problem Statement Our MBCFA technique assumes that the SDs and CDs of a system’s UML 2.0 design model are given. Our method will use the given SD and CDs to derive the control flow information of each SD. SDs will be used as the input for control flow information, while CDs will be used to find any possible polymorphic behavior of any class in SD lifelines. According to the above discussions, we divide the problem into three sub-problems: 1.

The first problem is to find a suitable CFM for MBCFA (Section 4). A suitable CFM, in this context, is one which supports all UML 2.0 SD features.

2.

Assuming the SDs and CDs of a system’s UML 2.0 design model are given, the second problem is to devise a mapping from an instance of SD metamodel to an instance of the CFM (Section 5).

3.

The third problem is to propose a formal representation for CFPs of the CFM (Section 6).

Before starting to address the above problems, we first present an overview on UML 2.0 SDs in the following section.

3 AN OVERVIEW ON UML 2.0 SEQUENCE DIAGRAMS According to the UML 2.0 specification [11], seven UML diagrams can be used to specify the behavior of a system. As shown in Appendix A of [11], they are Activity, Sequence, Collaboration (also called Communication in Section 14 of [11]), Interaction Overview, Timing, Use case and State machine diagrams. Among all those diagrams, sequence and communication diagrams provide message-level details of a program, which are needed for the Control Flow Analysis (CFA). SDs are essential UML artifacts for modeling the behavioral aspects of a system [11, 25]. The diagrams are particularly well-suited for object-oriented software, where they represent the flow of control during object interactions. A SD shows a set of interacting objects and the sequence of messages exchanged among them. The diagram may also contain additional information about the flow of control during the interaction, such as if-then-else conditions ("if c then send message m else send message n") and iteration ("send message m multiple times") or state-dependent behavior [11]. The UML 2.0 [11] syntax of SDs is used in this work. Comparing to UML 1.x [10, 12], UML 2.0 has proposed a set of new features to SDs. The features of UML 1.x SDs, such as object lifeline and message, have been studied extensively in the literature since the early times of UML and are well known to many researchers. We provide a brief definition of the new features of UML 2.0 SDs and present its metamodel in Section 3.1. We then state the SD features that are supported by the MBCFA technique proposed in this work in Section 3.2. 3.1 New Features and Metamodel A glimpse of SD new features is shown in Table 4. Some of the new features are illustrated with an example in Figure 3. The SD metamodel showing the class diagram of SD features is shown in Figure 5. •

Interaction: An interaction is a sequence of messages passed between objects to accomplish a particular task. The rational behind defining interactions is to reuse them in other contexts as InteractionOccurrences. For example, SD seqname1 in Figure 3 is an interaction.

•

InteractionOccurrence: An InteractionOccurrence is a symbol that refers to an interaction that is used within another interaction or context. seqname1 and seqname2 are two interaction occurrences which refer to SDs seqname1 and seqname2.

•

EventOccurrence: EventOccurrences represents moments in time to which actions are associated. An EventOccurrence is the basic semantic unit of Interactions. The sequences of EventOccurrences are the

14

Carleton University TR SCE-05-09

Updated: September 2005

meanings of interactions. EventOccurrences are ordered along a Lifeline. A message has two types of EventOccurrences: sendEvent and receiveEvent. The SendEvent is at the base of the message arrow where the message departs from the lifeline of the sending object, while ReceiveEvent is at the point of the message arrow where the arrow hits the lifeline of the receiving object. The ReceiveEvent of message m3 is pointed in Figure 3. Concept Object Lifeline Stimulus (Message) Time observation and constraint Activation Interaction InteractionOccurrence EventOccurrence CombinedFragment InteractionOperator InteractionOperand Duration observation and constraint

New/Existing Existing Existing (but just called Message in the new version) Existing Existing New New New New New New New

Table 4-New and existing features of the UML 2.0 SDs, compared to UML 1.x (taken from [47])

•

CombinedFragment: A CombinedFragment consists of one or more InteractionOperands. A CombinedFragment has an InteractionOperator that defines the number of allowed InteractionOperands and also how the messages in the CombinedFragment will be treated. As an example, a CombinedFragment with alt InteractionOperator is shown in Figure 3.

•

InteractionOperand: An InteractionOperand describes a grouping mechanism inside combined fragments. Interaction operands are features similar to Interactions, except the fact that they are part of a CombinedFragment. As example, the alt CombinedFragment in Figure 3 has two interaction operands.

•

InteractionOperator: An InteractionOperator defines how to use the interaction operands within the context of the combined fragment. The following interaction operators are defined: alternatives (alt), option (opt), break (break), parallel (par), weak sequence (seq), strict sequence (strict), negative (neg), critical region (region), ignore/consider (ignore/consider), assertion (assert), and loop (loop). Description of each of the interaction operators can be found in [11]. We briefly describe next the ones we intend to use in our MBCFA technique: •

Alternatives (alt): Provides alternatives, only one of which will be taken. The InteractionOperands are evaluated on the basis of guards. An else guard is provided that evaluates to TRUE if and only if all guards of the other InteractionOperands evaluate to FALSE.

•

Option (opt): Defines an optional interactions segment. The model for an opt combined fragment looks like an alt that offers only one interaction.

•

Break (break): Is a shorthand for an Alternative operator where one operand is given and the other assumed to be the rest of the enclosing InteractionFragment. In the course of executing an interaction, if the guard of the break is satisfied, then the containing interaction abandons its normal execution and instead performs the clause specified by the break fragment.

•

Parallel (par): Supports parallel execution of a set of InteractionOperands.

•

Loop (loop): Indicates that the interaction operand will be executed repeatedly and also includes a mechanism to stop the iteration.

15

Carleton University TR SCE-05-09 •

Updated: September 2005

Duration observation and constraint: UML 2.0 provides two types of constraints on the performance characteristics of interactions: duration and time. Furthermore, these features are enhanced by the UML-SPT profile [68]. sd seqName1

o1

o3

o2

ReceiveEvent: EventOccurrence

m2() m3() return

InteractionConstraint

alt [x>0] InteractionOperator

ref seqName2 N

InteractionOperand separator InteractionOperand

[else]

InteractionOccurrence ref

CombinedFragment seqName3

Figure 3-An example illustrating the new features of the UML 2.0 SDs

A message in a SD is the basic form of communication in interactions. Communication can raise a signal, invoke an operation, and create or destroy an object instance. UML 2.0 no longer draws a distinction between message and stimulus as ULM 1.x did. In the new version, a message can be one of the following two types: • •

Operation call: which expresses the invocation of an operation on the receiving object. An operation call must match the signatures of an operation on the target object (receiver of the message). Signal: which represents a message object sent out by one object and handled by the other object that is equipped to respond to it.

UML also provides four varieties (or sorts as UML 2.0 calls them) for a message. Message sorts identify the sort of communication reflected by a message. The sorts of messages supported are defined in an enumeration called MessageSort (in Figure 328 of [11]) as: • • • •

SynchCall: synchronous call AsynchCall: asynchronous call SynchSignal: synchronous signal AsynchSignal: asynchronous signal

The notational representations of reply and asynchronous messages in UML 2.0 have changed compared to UML 1.x, as shown in Figure 4.

16

Carleton University TR SCE-05-09

Updated: September 2005

in UML 1.x

in UML 2.0

synchronous message

synchronous message

reply message

reply message

asynchronous message

asynchronous message

Figure 4-Notations for synchronous/asynchronous messages and replies in UML 1.x and 2.0

As another property for messages is the so-called message kind. UML 2.0 defines the following message kinds: • • • •

complete: sendEvent and receiveEvent are present lost: sendEvent present and receiveEvent absent found: sendEvent absent and receiveEvent present unknown: sendEvent and receiveEvent absent (should not appear)

The difference between message sort and kind properties is that message sort specifies the synchrony of a message, while message kind categorizes a message by on its message ends. The SD metamodel is not shown in one place in UML 2.0 specification [11], rather divided in several small metamodel diagrams, since it is composed of many elements. By omitting unnecessary details, we show the complete metamodel generated from the specification in Figure 5. For space limitations, only some of the role names and multiplicities are shown in this figure. -{ordered}

Continuation

InteractionFragment *

InteractionConstraint

InteractionOccurrence * 0..1

toBefore * toAfter *

0..1

* refers to Interaction

StateInvariant

[0..1] startExec finishExec [0..1]

ExecutionOccurrence

* 1

1

Value Specification

1

1 *

Named Element

1 start finish 1

before 1

Message 0..1 0..1 sendEvent -messageKind -End2 -End1 -messageSort receiveEvent -return_value 0..1 0..1 signature * *

«enumeration» MessageKind complete lost found unknown

MessageEnd

after 1

EventOccurrence

Constraint

argument 1 *

*

guard 0..1 1 -guard 0..1

GeneralOrdering

1

«enumeration» MessageSort synchCall synchSignal asynchCall asynchSignal

Lifeline covered * Gate

InteractionOperand 0..1 * CombinedFragment

0..1

-InteractionOperator

«enumeration» InteractionOperator 0..1 alt opt break neg loop seq strict par region assert ignore consider

* *

Figure 5-UML 2.0 Sequence Diagram Metamodel

3.2 Features Supported in this Work Although none of the related works [13 2005, 14-16, 17 2002] support all the features of UML SDs in their CFA technique (Section 2.2), we intend to do so. In Section 5, we will discuss the details and propose formal consistency rules to transform features of SDs into the features of the CFM, which we will choose next in Section 4.

17

Carleton University TR SCE-05-09

Updated: September 2005

4 CONCURRENT CFG: A CONTROL FLOW MODEL FOR SDS One might argue that an intermediate CFM is not needed for MBCFA and an algorithm can be built to derive CFPs directly from a SD. However, a requirement that necessitates an intermediate CFM for SD is that concurrent control flow information of SD (due to asynchronous messages and parallel interaction operands) cannot be explicitly derived without an intermediate CFM. Furthermore, such a CFM can be graphically represented by UML CASE tools to visualize/animate concurrent control flow in SDs. This can be useful in model execution/comprehension/walk-through/etc. To better justify our choice, we first briefly identify the challenges of SDs’ CFA in Section 4.1. Using the discussion in Section 2.2 on the existing CFMs in the literature, Section 4.2 presents the candidate CFMs suitable for our work. Afterwards in Section 4.3, we customize a CFM to suit best our goals. We finally propose the formal metamodel of our CFM in Section 4.4. 4.1 Challenges of SDs’ CFA Conventional Control Flow Analysis (CFA) [1] techniques such as those used by compilers are usually applied to sequential programs. What we mean by a sequential program here is that there cannot be any concurrency in a single module. Control Flow Graphs (CFG) [1] are one of the most common CFMs used. However, the use of the CFG model is only limited to sequential programs and its standard model cannot be easily used to perform CFA in a module where there is intra-module concurrency, where some of the statements can run in parallel with others. If we consider the UML 2.0 SDs metamodel (Figure 5), asynchronous messages and par interaction operator entail intra-SD concurrency. However, such concurrency cannot be analyzed by conventional CFGs. Concurrency resulting from the above two modeling features has to be taken into account when analyzing the control flow in SDs. The impacts of the above two modeling features, leading to concurrency inside SDs, will be discussed in the following sections. 4.1.1 Impact of Asynchronous Messages In terms of message synchronizations, all 1.x and 2.0 versions of UML introduce two types of messages for SDs: synchronous and asynchronous. As discussed in Section 3.1, four types of messages are defined in UML 2.0: synchCall, asynchCall, synchSignal, and asynchSignal. In a synchronous message, the caller waits for completion of the invoked behavior and expects a return values. On the other hand, in an asynchronous message, the caller proceeds immediately and does not expect a return value. Therefore, asynchronous messages of a SD will entail a concurrent control flow in the SD. In order to better show the impact in CFA due to presence of asynchronous messages, let us consider an example. The SD of Figure 6 shows an asynchronous request processing approach. Message are prefixed with alphabetical symbols, which will be used later for easier reference to the messages. There are both synchronous and asynchronous messages in the SD. To see the effect of asynchronous messages in the control flow of the SD, let us consider the case when the object c of class Controller sends the message addToQueue() to the object apr of class AsyncProcessor. Since the message addToQueue() is asynchronous, the caller (object c) will not wait for the reply message (AynchTicket) of the asynchCall message addToQueue() and will continue running the other messages in its lifeline (interaction occurrence N). At the same time, object apr will start executing the method addToQueue(). In other words, in addition to the thread of control for object c, a new concurrent thread of control will be created for object apr. The other asynchronous messages in the SD of Figure 6 is the asynchCall message Process() from object apr to ap, whose control flow can be discussed in a similar fashion. Therefore, asynchronous messages impact the control flow of a SD by initiating two separate concurrent threads of control, one in the sender object and another in the receiver object of a message.

18

Carleton University TR SCE-05-09

Updated: September 2005

sd AsynchronousRequestProcessing jjjjjjjjjjjjjjjjjjjjjjjjjjjjjj c:Controller jjjjjjjjjjjjjjjjjj

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjj dummy:Class jjkkkkkkkkkkkkkkkk

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjj pf:ProcessorFactory jjkkkkkkkkkkkkkkkk

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjj apr:AsyncProcessor jjkkkkkkkkkkkkkkkk

jjjjjjjjjjjjjjjjjjjjjjjjjjjjjj ap:AsyncProcess jjkkkkkkkkkkkkkkkk

A-getAsynchProcessor() B-AsyncProcessor C-addToQueue() D-at=AsynchTicket

E-Process()

[at=NULL]

opt

loop while (s!=FINISHED)

ref

N F-getProcessResult()

H-getStatus()

G-AsynchProcessResult

I-s=Status

Figure 6-A SD with asynchronous messages

4.1.2 Impact of par Interaction Operator The par interaction operator is a new feature in UML 2.0 to support parallel execution of a set of interaction fragments. A simple SD showing the use of the par interaction operator is shown in Figure 7. This SD corresponds to a cook use case of a microwave oven. Object Controller is the controller the oven. As their names indicate, RotatingPlate and SignalEmitter objects are the other two objects in the cook SD. The controller receives a startCook(duration) message, where duration is the cooking time. Afterwards, the controller sends two messages, one to RotatingPlate and one to SignalEmitter to start doing their tasks. These two messages are sent in a parallel manner, meaning that the two interaction fragments containing message rotate(duration) and emit(duration) run concurrently. As shown by the above example, par interaction operators impact the control flow of a SD by entailing two or more concurrent threads of control. sd Cook :Object1 :Controller

Object2Object2Obj :RotatingPlate

Object8Object8Ob :SignalEmitter

startCook(duration) par rotate(duration) Interaction fragment emit(duration)

Figure 7- A SD with par interaction operator

4.2 Towards a CFM for SDs In this section, we briefly survey some of the existing CFMs in the literature. We then choose a CFM which suits best for MBCFA. As discussed in the related works (Section 2.2), there have been CFMs such as “type and effect system” ([41], [52]), abstract analysis form [50], a-normal form [51], Petri-nets [69], TIG (Task Interaction Graph) [53] and TIG-based Petri-nets [54] for analysis of concurrent programs in the literature. The first three CFMs are used in the context of compilers, languages, and formal methods and we believe that they cannot be easily

19

Carleton University TR SCE-05-09

Updated: September 2005

used in the context of UML and metamodel-based transformations. The work in both [53] and [54] reports on Petri net-based CFMs. Petri-nets can be considered as a generalization of CFGs, where fork and join nodes (bars) are used to model synchronization of concurrent executions. For example, Zhang and Cheung [70] model the flow and concurrency control of multimedia systems using Petri-nets. One advantage of Petri-nets is that they have a well-established formal notation that has been widely used for the modeling of dynamic behavior, as well as extensive tool support. UML has adopted a Petri-net like semantics for control and object flow modeling referred to as Activity Diagrams (AD). ADs have been in UML since its early 1.x versions [10, 12]. UML 2.0 [11] has enhanced the semantics of ADs in many ways (refer to different “Changes from previous UML” subsections in Section 12.3 of [11]). Among many enhancements compared to the earlier versions, it accounts for sequential versus concurrent control flow and data flow analysis. As UML 2.0 points out (Section 12.1 of [11]): “These [UML activities] are commonly called control flow and object flow models.” Among the choice of TIG, TIG-based Petri-nets, Petri-nets and UML AD, we choose the latter for the CFA of SDs. The reasoning for this decision is threefold: 1.

AD already has a well-defined metamodel, which is needed by our MBCFA technique and, as we will see, is complete enough.

2.

Since SD and AD are both in the context of UML. Therefore, our technique will potentially benefit from the contextual consistency between two metamodels in this context.

3.

Resulting from the previous reason, the generated CFM (a slightly modified version of ADs in our case) can be easily visualized/analyzed by standard UML 2.0 CASE tools.

AD’s metamodel is very useful in our work since we intend to provide OCL-based mapping rules from SD metamodel to that of our to-be-chosen CFM. However, as it will be discussed next, we will need to add some features to ADs (extend them) to allow automated MBCFA of SDs. 4.3 A Brief Look at UML 2.0 Activity Diagrams In order to account for sequential and concurrent control and data flow analysis, UML 2.0 proposes six different but dependent activity packages (Section 12 of [11]). 1.

BasicActivities (BA): The basic level supports modeling of traditional sequential flow charts.

2.

StructuredActivities (SA): The structured level supports modeling of traditional structured programming constructs, such as loops and conditionals, as an addition to the basic activity. It requires the basic level.

3.

IntermediateActivities (IA): The intermediate level supports modeling of activity diagrams that include concurrent control and data flow. It supports modeling similar to traditional Petri-nets with queuing. It requires the structured level.

4.

CompleteStructuredActivities (CSA): This level adds support for advanced data flow features such as output pins on conditions and loops. A pin is an object node for inputs and outputs to actions. For example, one of the output pins of a loop node is the set of data flows which are the loop variables.

5.

ExtraStructuredActivities (ESA): The extra structure level supports exception handling as found in traditional programming languages and invocation of behaviors on sets of values. It requires the structured level.

6.

CompleteActivities (CA): The complete level adds constructs that enhance the lower level models, such as edge weights and streaming. In a UML activity, the weight attribute of an edge dictates the minimum number of tokens (control or data) that must traverse the edge at the same time. Streaming allows an action execution to take data inputs and provide outputs while it is executing. During one execution, the action may consume multiple tokens on each streaming input and produce multiple tokens on each streaming output. 20

Carleton University TR SCE-05-09

Updated: September 2005

Note that the above list of activity packages is shown in increasing order of complexity. Dependencies of the activity packages are shown in Figure 8 (Figure 175 of [11]). Note that UML 2.0 standard packages are shown in white background. For example, some of the classes of the IA package extend some of the classes in the BA and SA packages. UML 2.0 does not clearly distinguish the above packages in terms of control or data flow modeling. Based on the analysis of the metamodel and class descriptions of the above activity packages in UML 2.0 specification (Section 12 of [11]), it can be realized that control and data flow are not distinguished per each UML 2.0 activity. However, since our focus in this section is to only analyze the control flow of SDs by converting them into ADs, we have to select one of the UML activity packages which is simple enough and includes all the necessary model elements to be an appropriate CFM. In the current work, we do not consider data flow as part of the CFM. From UML 2.0 standard

Support for more complex modeling features

BasicActivities (BA)



Our extended activity package



StructuredActivities (SA)



ExtraStructuredActivities (ESA)

IntermediateActivities (IA)



CCFG



CompleteStructuredActivities (CSA)

CompleteActivities (CA)

Figure 8- Dependencies of the UML 2.0 Activity packages and our proposed CCFG activity package

4.3.1 Choosing the Right Package Based on the analysis of the metamodel and class descriptions of the activity packages, we decided to use the IA package as the activity model for the MBCFA. The reasons for this selection are the followings. •

The IA package fits the needs of MBCFA, since it supports modeling both concurrency (by being Petri-net like, i.e. including ForkNode and JoinNode) and structured control constructs (by generalizing SA and BA).

•

The IA is simpler than the other three packages (CSA, ESA and CA), as it does not include the modeling features needed for: o

Advanced data flow modeling, such as output pins (modeled by CSA), edge weights and streaming (modeled by CA).

o

Extra structure level support for exception handling, so IA’s metamodel is simpler than that of ESA in terms of control flow (we do not consider specific CFA of exceptions in the current work, they may be modeled as conventional conditions).

Therefore, it seems that the IA package is a good starting point for a CFM. However, due to specific requirements in our MBCFA technique, which will be explained below, we need to extend the IA package to a new activity package called CCFG. The package CCFG is shown in Figure 8 with gray background. In extending CCFG from the IA package, we use extension mechanism similar to what has already been used in UML 2.0 activity packages. Considering Figure 8, some of the classes in the activity package at the tail of a dependency extend some of the classes in the package at the head of the dependency relationship. Therefore, as we will discuss in Section 4.4.1, some of the classes in the CCFG package will extend some of the classes in the IA package. In the following section, we present the IA package metamodel (only the control flow features) from the UML 2.0 specification. In Section 4.4, we will discuss the ways in which we extend the IA classes to the classes in the CCFG package to accommodate for MBCFA. The CCFG metamodel will be given finally. 21

Carleton University TR SCE-05-09

Updated: September 2005

4.3.2 Metamodel of the IntermediateActivities Package The simplified1 metamodel of the IA package can be derived by merging the parts of the UML activity metamodel and descriptions of the metamodel classes (Section 12 of [11]). The simplified metamodel is shown in Figure 9. 1 Activity 1 1

1

ActivityGroup

1 StructuredActivityNode

ActivityPartition

subgroup

1 ConditionalNode

superPartition

LoopNode

1 Clause

ActivityNode

ObjectNode

incoming outgoing

1 target 1 source

ExecutableNode

Action

ControlNode

ForkNode

MergeNode

JoinNode

DecisionNode

FinalNode

ActivityFinalNode

ValueSpecification

1

ControlFlow

InitialNode

guard 1

ActivityEdge

ObjectFlow

FlowFinalNode

Figure 9- Metamodel of the UML 2.0 IntermediateActivities Package

The top-most class (Activity) in the class diagram (metamodel) of Figure 9 is the UML concept which is usually represented graphically as Activity Diagrams (AD). The formal class descriptions of other classes in this metamodel can be found in Section 12.3 of [11]. In the next section, we use the metamodel of the IA package as the basis to propose a metamodel for MBCFA. We will see that the IA package has all the modeling features we need for MBCFA. However, some of its features should be removed (e.g. ObjectNode and ObjectFlow) because our MBCFA technique takes into account only the control flow analysis. We will refer to the slightly modified metamodel of IA package as Concurrent CFG (CCFG) to account for the concept of CFG and also intra-SD concurrency.

Due to space constraints, the metamodel does not include all the association names and cardinalities. Only the important ones are mentioned. 1

22

Carleton University TR SCE-05-09

Updated: September 2005

4.4 Concurrent CFG (CCFG) We propose CCFGs to analyze the concurrent control flow of SDs. A CCFG will be generated for each SD. In cases where a SD calls (refers to) another SD, there will be control flow edges connecting their corresponding CCFGs to form an Inter-SD CCFG. Inter-SD CCFG here is similar to the concept of interprocedural CFG [1]. As mentioned in Section 4.3.2, we extend CCFG from the UML IA activity package. Here, we first discuss the reasons to make such extensions to the metamodel of IA packages and then the effect of resulting extensions will be given as the CCFG metamodel. 4.4.1 Extension to the IntermediateActivities Package Here we discuss the reasons to make extension to the metamodel of IA package. We group the extensions in three groups: extensions to Activity, extensions to ActivityNode, and extensions to ActivityPartition. Extensions to Activity In our MBCFA technique, each activity class of the CCFG metamodel corresponds to an interaction fragment class of the SD metamodel. Therefore, in order to access the interaction fragment associated with an activity, we need to add an association from the activity class in the CCFG metamodel to the interaction fragment class in SD metamodel. Since SD interaction fragments can be nested, therefore, to be consistent, their corresponding activities have to be nested too. Therefore, we add a reflexive bidirectional association from the activity class with role names parent and child. Each CCFG has one parent CCFG and can have multiple child CCFGs. The former has the cardinality of one and indicates the parent activity of the current activity instance. The later has the cardinality of * and is the set of child activities of the current activity instance, i.e., the activities inside the current activity. Extensions to ActivityNode The metamodel of IntermediateActivities (Figure 9) includes three subclasses of ObjectNode and ExecutableNode. As defined by UML 2.0 [11]:

ActivityNode.

They are ControlNode,

•

“A control node is an abstract activity node that coordinates flows in an activity.”

•

“An object node is an abstract activity node that is part of defining object flow in an activity.”

•

“An executable node is an abstract class for activity nodes that may be executed. It is used as an attachment point for exception handlers.”

According to the above definitions, we can find out that only ControlNode is of interest in the CFA of our context. We do not deal with objects and objects flows in our definition of CFA. Although, the current CFA technique can be generalized to include objects flow concepts such as Def-Use. ExecutableNode is used as an attachment point for executable actions and exception handlers. As two generalizations to ExecutableNode, we add two subclasses to it: CallNode and ReplyNode, which specialize the ExecutableNode for call/signal and reply messages, respectively. Since each CallNode/ReplyNode in a CCFG will correspond to a call/reply message in the corresponding SD, one other important extension to ActivityNode is to make it possible to access the corresponding message of a ControlNode. We have two options to do so: (1) either to define a set of new associations (fields) for a ControlNode and basically copy all the information of the corresponding message into these fields, or (2) just build a reference from each ControlNode to the corresponding message. Out of these two options, the second one seems to be much better, since there is no need to create an extra redundant copy of a message inside every ControlNode. This extension is shown by adding an association to ActivityNode, which is entitled message and is targeting the SD::Message class.

23

Carleton University TR SCE-05-09

Updated: September 2005

The need for another important extension to ActivityNode arose when we started to design our transformation technique (Section 5). We found out that, in order to build all control flows (edges) among all activity nodes of a CCFG, we need to associate activity nodes with message ends. In summary, we add two associations to ActivityNode, inFlow and outFlow, which are both targeted to SD::Message class (Figure 10). The reason why we assign cardinality * for these two associations is that there might be cases in which more than one in/out flows have to be built towards/from a node. These two associations will keep track of in and out flows of an activity node. In Section 5, the rational for having them will be made more precise. Extensions to ActivityPartition is defined as (Section 12.3.8 of [11]): “An activity partition is a kind of activity group for identifying actions that have some characteristic in common”. ActivityGroup is itself defined as (Section 12.3.5 of [11]): “An activity group is an abstract class that for defining sets of nodes and edges in an activity”. To enrich our MBCFA technique for analytical and even graphical purposes, we intend to group the activity nodes based on the object names where their corresponding messages are executed (receive event of messages in SDs). Therefore we define an ActivityPartition called ObjectPartition, which has an association objectName of UML type NamedElement (Figure 10). ActivityPartition

We also change the semantic of activity final nodes in a way that they can have outgoing edges. This is needed to be done since when a SD calls another SD using an interaction occurrence, there needs to be a control flow from the activity final node of the CCFG corresponding to the called SD to a message node in the CCFG corresponding to the caller SD. An example will be discussed in Section 5. 4.4.2 CCFG Metamodel Using the metamodel of IntermediateActivities package as the basis and performing the list of extensions described in the previous section, the metamodel for CCFG package is presented in Figure 10. The guard association of the MessageEnd is intended for storing guard conditions when storing in/out flows of a node. The guard will be later copied to the corresponding activity edge. Note that we do not show the data-flow related classes inherited from the IA package. SD::InteractionFragment

*

1 activity 1

1

parent 1 Activity

ActivityGroup

ValueSpecification * node

1 guard 0..1 SD::MessageEnd outFlow*

children 1

1 activity 1 ActivityPartition

inPartition 1

1

objectName 1

inFlow*

NamedElement

* nodes ActivityNode

ControlNode

1 target

incoming *

1 source

outgoing *

ExecutableNode

SD::Message message 1

InitialNode

ForkNode

JoinNode

MergeNode

DecisionNode

FinalNode

ActivityFinalNode

ObjectPartition

* edge

interFrag

MessageNode CallNode

ActivityEdge

1 ValueSpecification guard 0..1

ControlFlow

ReplyNode

FlowFinalNode

Figure 10- CCFG metamodel

As an example, the CCFG corresponding to the SD of Figure 6 is shown in Figure 11. The procedure to build this CCFG will be described in the next section, when we present the set of rule-based mapping rules from SDs to CCFGs. 24

Carleton University TR SCE-05-09

Updated: September 2005

4.4.3 OCL Constraints of the Metamodel We define the following OCL constraints on the CCFG metamodel. •

Uniqueness of object partitions 1

CCFG::objectPartition.allInstances->forAll(op1,op2:ObjectPartition|

2

op1.objectName=op2.objectName and

3

op1.className=op2.className

4 5 6

•

implies op1=op2 )

Only one InitialNode per CCFG instance 1

CCFG::Activity.allInstances->forAll(ccfg:Activity|

2 3

ccfg.nodes->select(an:ActivityNode|an.oclType=InitiaNode)->size=1 )

5 A SET OF CONSISTENCY RULE-BASED MAPPING RULES FROM SDS TO CCFGS Using OCL [71], we propose a consistency rulebased approach to map SDs into CCFGs. The mapping rules are described in OCL and are useful in several ways: (1) They provide a logical specification and guidance for our transformation algorithms that derive a CCFG from a SD (both being instances of their respective metamodel), and (2) They help us ensure that our CCFG metamodel is correct and complete with respect to our control flow analysis purpose, as the OCL expression composing the rules must be based on the metamodels. The mapping rules are not algorithms, though they provide a specification and insights into how to implement such algorithms. In other words, those OCL expressions can be considered as the postcondition of a single operation responsible for transforming an instance of the SD metamodel into an instance of the CCFG metamodel. We have derived fourteen consistency rules, expressed in OCL, that relate different parts of an instance of a SD metamodel to different components of an instance of the CCFG metamodel. For each consistency rule, we provide a graphical representation (“visualization” as we refer to) to depict how each mapping works and also apply the consistency rule on the SD of either of Figure 6 or Figure 7. In the OCL expressions, we will use SD

25

Legend A

getAsynchProcessor()

Call Node

AsyncProcessor

Reply Node

B

C

addToQueue()

CCFG(N)

D

AsynchTicket [at=NULL]

...

[else] E

Process()

[else] [s!=FINISHED]

H

getStatus()

I

s=Status

getProcessResult()

F

AsynchProcessResult

G

Figure 11- CCFG of the SD in Figure 6

Carleton University TR SCE-05-09

Updated: September 2005

and CCFG context1 to refer to SD and CCFG metamodel features, respectively. For example SD::Message and CCFG::Activity will indicate a reference to SD message and CCFG activity classes. We present in Section 5.1 the list of consistency rules from SD to CCFG features. The consistency rules are proposed in Section 5.2- 5.15. Section 5.16 defines the utility functions, which are used by our consistency rules. 5.1 List of Consistency Rules In our MBCFA technique, the consistency rules map all or a subset of instances in a SD feature to all or a subset of instances in a CCFG feature and are listed in Table 5. In the following, we describe each of the consistency rules. The name of mapping consistency rules are in the following format: All or a subset of instances in a SD featureà All or a subset of instances in a CCFG feature. Rule #

SD feature

CCFG feature

1 2

InteractionFragment First message end

3 4

SynchCall/SynchSignal AsynchCall or AsynchSignal

5 6 7 8 9 10 11

Message SendEvent and message ReceiveEvent Lifeline par CombinedFragment loop CombinedFragment alt/opt CombinedFragment break CombinedFragment Last message ends

Activity Flow between InitialNode and first control node CallNode (CallNode+ForkNode) or ReplyNode ControlFlow

12 13 14

InteractionOccurrence Polymorphic message Nested InteractionFragments

ObjectPartition ForkNode DecisionNode DecisionNode ActivityEdge Flows between ending control nodes and ActivityFinalNode Control Flow across CCFGs DecisionNode Nested CCFGs

Described in Section 5.2 Section 5.3 Section 5.4 Section 5.5 Section 5.6 Section 5.7 Section 5.8 Section 5.9 Section 5.10 Section 5.11 Section 5.12 Section 5.13 Section 5.14 Section 5.15

Table 5-Mapping rules from SD features to CCFG features

5.2 InteractionFragmentàActivity Consistency Rule 1 checks if there exists an instance of activity (CCFG) for every instance of interaction fragment. 1

SD::InteractionFragment.allInstances->forAll(interFrag:InteractionFragment|

2 3

)

CCFG::Activity.allInstances->exits(act:Activity|act.interFrag=interFrag)

Consistency Rule 1- Checking the existence of an instance of activity (CCFG) for every instance of interaction fragment

The context definition of an OCL expression specifies the model entity for which the OCL expression is defined [72].

1

26

Carleton University TR SCE-05-09

Updated: September 2005

5.3 First message endàFlow between InitialNode and first control node This consistency rule checks if there is a flow from initial node of every CCFG to its first control node. The first control node of a CCFG is the one which correspond to the first message of the corresponding SD. The utility function getFirstMessage() is used to retrieve such message. This consistency rule uses the message ends of the first message, therefore even if the message is inside a combined fragment, the correct control flow connection will be made. OCL Mapping 1

SD::InteractionFragment.allInstances->forAll(inter:InteractionFragment|

2

CCFG::InitialNode.allInstances->exits(in:InitialNode|

3

in.activity=getCCFG(inter) and

4

in.outgoing->exists(flow:ControlFlow|

5

getCCFG(inter).nodes->exits(an:ActivityNode|

6

an.inFlow->includes(Utility::Util.getFirstMessage(interFrag).sendEvent)and

7

flow.target=an

8

)

9

)

10 11

) )

Consistency Rule 2-Mapping first message end to flow between InitialNode and first control node

Visualization CCFG(inter)

inter: Interaction

in:InitialNode

m flow:ControlFlow cn Mapping

cn.message=m

getFirstMessage(inter): Message

CCFG of each interaction fragment is checked to have an initial node (lines 1-3). There should be a control flow from each initial node in to the activity node corresponding to the first message of each interaction fragment (lines 4-7). Example Figure 12 shows part of the CCFG instance that satisfies the Consistency Rule 2 based on SD in Figure 6. The corresponding part of the resulting CCFG is represented in Figure 13. Note that executable node enA and message end Ase correspond to message getAsynchProcessor() and its send event, respectively, in the SD of Figure 6. ccfg:Activity

A:SD::Message message

1 1 in:InitialNode

enA:ExecutableNode target

source outgoing

flow:ControlFlow

incoming

enAse:SD::MessageEnd

inflow

Figure 12-Part of the CCFG instance ccfg based on SD in Figure 6 that satisfies Consistency Rule 2

27

Carleton University TR SCE-05-09

Updated: September 2005

ccfg=getCCFG(AsynchronousRequestProcessing) in:InitialNode flow:ControlFlow enA.sendEvent enA:ExecutableNode enA.message=A

Figure 13-Part of the CCFG, corresponding to the instance shown in Figure 12

5.4 SynchCall/SynchSignalàCallNode This consistency rule maps SynchCall and SynchSignal messages of a SD to call nodes of a CCFG. OCL Mapping 1

SD::Message.allInstances->forAll(m:Message|

2

(m.MessageSort=SD::MessageSort.synchCall) or

3

(m.MessageSort=SD::MessageSort.synchSignal)

4

implies

5

CCFG::CallNode.allInstances->exits(cn:CallNode|

6

cn.message=m and -- check object partition

7

cn.inPartition=Utility::Util.getObjectPartition( m.receiveEvent.covered.connectable_element_name) and -- make sure cn is prepared for control flow (edge) connections -- m.SendEvent/m.ReceiveEvent should be in inFlow/outFlow of cn

8

cn.inFlow->includes(m.sendEvent) and

9

cn.outFlow->includes(m.receiveEvent) and

10 11 12

Utility::Util.getCCFG(m.interaction).node->includes(cn) ) )

Consistency Rule 3-Mapping synchCall or synchSignal message instances to CallNode instances

Visualization CCFG(inter)

inter: Interaction

connectable_element_name: class_name ...

:Partition

cn.inFlow:Set(MessageEnd)

m()

cn.inPartition

cn:CallNode Mapping

m.sendEvent

cn.outFlow:Set(MessageEnd) m.receiveEvent

m.sendEvent.covered

...

and SynchSignal messages of a SD are selected in lines 1-3. The existence of a call node c is checked in lines 5-10. The call node c ‘s message association value should be m (line 6), its object partition should be lifeline of message m (line 7), and its inflow and outflow sets should include m’s send and receive events, respectively (lines 8-9). These inflow and outflow information are needed since the control flow consistency rule (Consistency Rule 5) will use them to connect subsequent control nodes to each other. Line 10 makes sure that node cn is a part of the CCFG corresponding to interaction containing message m. SynchCall

Example Figure 14 shows part of the CCFG instance corresponding to message A in SD in Figure 6 that satisfies the Consistency Rule 3. The corresponding part of the resulting CCFG is represented in Figure 15.

28

Carleton University TR SCE-05-09

Updated: September 2005

1 “pf”:NamedElement

message

ccfg:Activity

A:SD::Message

1

objectName op:ObjectPartition “ProcessorFactory” :NamedElement

inPartition

cn:CallNode

inFlow className

outFlow

A.sendEvent: SD::MessageEnd

A.receiveEvent: SD::MessageEnd

Figure 14-Part of the CCFG instance corresponding to message A in SD of Figure 6 that satisfies Consistency Rule 3 ccfg=getCCFG(AsynchronousRequestProcessing) op:ObjectPartition A.sendEvent cn:CallNode

cn.message=A

A.receiveEvent

Figure 15-Part of the CCFG, corresponding to the instance shown in Figure 14

Call node cn in corresponds to message A in Figure 6. Since the receiver lifeline of message A is pf:ProcessorFactory, the inPartition association of cn corresponds to ObjectPartition instance op which is associated with object and class names pf and ProcessorFactory, respectively. 5.5 AsynchCall/AsynchSignalà(CallNode+ForkNode)/ReplyNode This consistency rule maps AsynchCall and AsynchSignal messages to a combination of call nodes and fork node, entailing intra-SD concurrency (Section 4.1.1). Reply messages with AsynchSignal type are mapped to CCFG reply nodes. Visualization •

AsynchCall/AsynchSignalà(CallNode+ForkNode) CCFG(int)

int: Interaction

:Partition

cn.inFlow:Set(MessageEnd) connectable_element_name: class_name ...

cn.inPartition m.sendEvent

sig()

m.sendEvent

m.receiveEvent

cn:CallNode

Mapping

flow:ControlFlow fn.outFlow:Set(MessageEnd)

m.sendEvent.covered

•

fn m.sendEvent

...

m.receiveEvent

AsynchSignalàReplyNode int: Interaction

CCFG(int)

connectable_element_name: class_name

:Partition

rn.inFlow:Set(MessageEnd)

... rn:ReplyNode attribute=sig():return_value m.receiveEvent

Mapping

m.sendEvent

rn.outFlow:Set(MessageEnd)

m.receiveEvent.covered ...

29

rn.inPartition

Carleton University TR SCE-05-09

Updated: September 2005

Messages with AsynchCall or AsynchSignal type are selected in lines 1-3. The consistency rule is then divided into two sections by an if statement (line 5). Based on the message type (call or reply), the first section (lines 5-13) handles reply messages, while the second part (lines 14-25) maps asynchronous calls or signals. For each reply message, the consistency rule makes sure that there exists a CCFG reply node (line 6) whose message association points to the message (line 7), has the object partition as the lifeline of the message (line 8), and the inflow and outflow of the reply node sets include the send and receive ends of the message (line 9 and 10). Line 11 checks if the node rn is in the corresponding activity.

OCL Mapping 1

SD::Message.allInstances->forAll(m:Message|

2

(m.MessageSort=SD::MessageSort.asynchCall) or

3

(m.MessageSort=SD::MessageSort.asynchSignal)

4

implies -- check if m is a reply or call/signal

5

if Utility::Util.getTypeOfMessage(m)=”reply” then {

6

CCFG::ReplyNode.allInstances->exits(rn:ReplyNode|

7

rn.message=m and

8

rn.inPartition=getObjectPartition( -- set object partition m.receiveEvent.covered.connectable_element_name) and -- prepare rn for control flow (edge) connections

9

rn.inFlow.allInstances->exists(me:MessageEnd|me=m.sendEvent) and

10

rn.outFlow.allInstances->exists(me:MessageEnd|me=m.receiveEvent) and

11

Utility::Util.getCCFG(m.interaction).node->includes(rn)

12

)

13

}

14

else -- m is an asynch call/signal {

15

CCFG::ActivityNode.allInstances->exits(cn:CallNode,fn:ForkNode|

16

cn.message=m and fn.message=m and

17

cn.inPartition=Utility::getObjectPartition( -- set object partition

18

fn.inPartition=cn.inPartition and

m.receiveEvent.covered.connectable_element_name) and -- connection from cn to fn 19

cn.outgoing.target->includes(fn) and cn.outgoing->size=1 and -- prepare cn for control flow (edge) connections

20

cn.inFlow->exists(me:MessageEnd|me=m.sendEvent) and -- build the asynch control flow from fn

21

fn.outFlow->includes(m.sendEvent) and fn.outFlow->includes(m.receiveEvent)

22

Utility::Util.getCCFG(m.interaction).node->includes(cn) and

and fn.outFlow->size=2 and 23

Utility::Util.getCCFG(m.interaction).node->includes(fn)

24

)

25 26

} )

Consistency Rule 4-Mapping asynchCall or asynchSignal message instances to (CallNode+ ForkNode) (or ReplyNode instances

On the other hand, for each asynchronous call or signal message, the consistency rule makes sure that there exist a CCFG one call and one fork node (line 15) whose message associations point to the message (line 16) and have the object partitions as the lifeline of the message (lines 17 and 18). Line 19 confirms that there is a connection the call node to the fork node. Inflow connections of the control node are checked in line 20. According to the concept of asynchronous SD messages, such a message will entail two threads of control, one in the message sender object and another one in the receiver object of the message. Therefore, line 21 makes sure that there are two outflow instances associated with the fork node to handle the concurrency

30

Carleton University TR SCE-05-09

Updated: September 2005

resulting from an asynchronous call or signal message. These two outflow (message end) instances correspond to the send and receive message ends. Lines 22 and 23 check if the nodes cn and fn are in the corresponding activity. Examples •

AsynchCall/AsynchSignalà(CallNode+ForkNode)

Figure 16 shows part of the CCFG instance corresponding to the asynchronous message C in SD in Figure 6 that satisfies the Consistency Rule 4. The corresponding part of the resulting CCFG is represented in Figure 17. 1 “c”:NamedElement

message

ccfg:Activity

C:SD::Message

1

objectName inPartition 1

op:ObjectPartition

“Controller”: NamedElement

C.sendEvent: inFlow SD::MessageEnd

cn:CallNode

inPartition

source

outFlow

outgoing className

flow:ControlFlow incoming target C.receiveEvent: outFlow SD::MessageEnd

fn:ForkNode

Figure 16-Part of the CCFG instance corresponding to the asynchronous message C in SD of Figure 6 that satisfies Consistency Rule 4 ccfg=getCCFG(AsynchronousRequestProcessing) op:ObjectPartition C.sendEvent cn:CallNode

cn.message=C

flow:ControlFlow fn C.sendEvent

C.receiveEvent

Figure 17-Part of the CCFG, corresponding to the instance shown in Figure 16

•

AsynchSignalàReplyNode

Figure 18 shows part of the CCFG instance corresponding to the reply message B in SD in Figure 6 that satisfies the Consistency Rule 4. The corresponding part of the resulting CCFG is represented in Figure 19. 1 “c”:NamedElement

message

ccfg:Activity

op:ObjectPartition

inPartition

rn:ReplyNode

inFlow “Controller”: NamedElement

B:SD::Message

1

objectName

className

B.sendEvent: SD::MessageEnd

outFlow B.receiveEvent: SD::MessageEnd

Figure 18-Part of the CCFG instance corresponding to the reply message B in SD of Figure 6 that satisfies Consistency Rule 4

31

Carleton University TR SCE-05-09

Updated: September 2005

ccfg=getCCFG(AsynchronousRequestProcessing) op:ObjectPartition B.sendEvent rn:ReplyNode

rn.message=B

B.receiveEvent

Figure 19-Part of the CCFG, corresponding to the instance shown in Figure 18

5.6 Message.SendEvent/Message.ReceiveEventàControlFlow This consistency rule maps the ordering of message-end events (send and receive), from a synchronous message to any message type, to control flows in CCFG. OCL Mapping 1

SD::EventOccurrence.allInstances->forAll(eo1,eo2:EventOccurrence|

2

eo1.covered=eo2.covered and

3

Utility::Util.getFirstEventOccurrence(eo1.toAfter, eo1.covered)=eo2

4

implies

5

CCFG::ControlNode.allInstances->exits(cn1, cn2:ControlNode|

6

cn1.outFlow.includes(eo1) and

7

cn2.inFlow.includes(eo2) and

8

cn1.outgoing->exists(flow:ControlFlow|flow.target=cn2 and

9

flow.guard=cn1.outFlow.select(oflow|oflow=eo1).guard

10 11 12

) ) )

Consistency Rule 5-Mapping Message.SendEvent/Message.ReceiveEvent instances to ControlFlow between nodes

Visualization CCFG(inter)

inter: Interaction

cn1 m1.SE

m1

cn1.message=m1

m1.RE Mapping

flow:ControlFlow

ll m2 m2.SE

cn2

m2.RE

cn2.message=m2

m2.SE=Utility::getFirstEventOccurrence(m1.RE.toAfter, ll) SE: sendEvent RE: receiveEvent

Lines 1-3 use the getFirstEventOccurrence utility function to select two immediate subsequent EventOccurrences eo1 and eo2. For each such pair, lines 5-11 check whether there is a control flow from a control node cn1 containing the EventOccurrences eo1 to another control flow cn2 containing the EventOccurrences eo2. The guard of such flow should be equal to the guard stored in the out flow instance of cn1 (line 9). Incorporating such guard conditions into control flows are needed for instance in Consistency Rule 13. Example

32

Carleton University TR SCE-05-09

Updated: September 2005

Figure 20 shows part of the CCFG instance corresponding to the control flow between messages A and B in SD in Figure 6 that satisfies the Consistency Rule 5. The corresponding part of the resulting CCFG is represented in Figure 21. outFlow

A.receiveEvent: SD::MessageEnd

cn1:ControlNode source

message

A:SD::Message

1 outgoing ccfg:Activity

flow:ControlFlow incoming

1 target cn2:ControlNode

B.sendEvent: SD::MessageEnd

message

B:SD::Message

inFlow

Figure 20-Part of the CCFG instance corresponding to the control flow between messages A and B in SD of Figure 6 that satisfies Consistency Rule 5 ccfg=getCCFG(AsynchronousRequestProcessing)

cn1

cn1.message=A

A.receiveEvent flow:ControlFlow B.sendEvent cn2

cn2.message=B

Figure 21-Part of the CCFG, corresponding to the instance shown in Figure 20

5.7 LifelineàObjectPartition This consistency rule maps each lifeline of a SD into an object partition in a CCFG. OCL Mapping 1

SD::Lifeline.allInstances->forAll(l:Lifeline|

2

CCFG::ObjectPartition.allInstances->exits(op:ObjectPartition| -- make sure l and op refer to the same object and class

3

op.objectName=l.connectable_element_name and

4

op.className=l.class_name and -- make sure all the control nodes of op are on l

5

op.nodes->forAll(cn:ControlNode|

6

cn.inPartition=op and

7

l.EventOccurrence.includes(cn.outFlow)

8 9 10

) ) )

Consistency Rule 6-Mapping Lifeline instances to ObjectPartition instances

For each lifeline (line 1-2), the consistency rule checks (line 2) whether there exists an object partition with the same object and class names (lines 3-4). Lines 5-8 verify that all the control nodes of the object partition are on the selected lifeline. Visualization

33

Carleton University TR SCE-05-09

Updated: September 2005

CCFG(int)

int: Interaction

objectName: className

connectable_element_name: class_name

Mapping

l:Lifeline op:ObjectPartition

Example Figure 22 shows part of the CCFG instance corresponding to lifeline pf:ProcessorFactory in SD in Figure 6 that satisfies the Consistency Rule 6. The corresponding part of the resulting CCFG is represented in Figure 23. ccfg:Activity 1 op:ObjectPartition

className “ProcessorFactory” :NamedElement

objectName “pf”:NamedElement

Figure 22-Part of the CCFG instance corresponding to lifeline pf:ProcessorFactory in SD of Figure 6 that satisfies Consistency Rule 6 ccfg=getCCFG(AsynchronousRequestProcessing) op:ObjectPartition

Figure 23-Part of the CCFG, corresponding to the instance shown in Figure 22

5.8 Parallel (par) CombinedFragmentàForkNode Parallel combined fragments are mapped by this consistency rule into fork node constructs, which correspond to intra-SD concurrency (Section 4.1.2). Visualization par

io1:InteractionOperand fn.inFlow:Set(MessageEnd)

sendEvent

fn flow:ControlFlow io2:InteractionOperand

Mapping

CCFG(io1)

CCFG(io2)

...

ion:InteractionOperand

...

CCFG(ion) ...

receiveEvent jn

OCL Mapping

34

outFlow:Set(MessageEnd)

Carleton University TR SCE-05-09

1

Updated: September 2005

SD::CombinedFragment.allInstances->forAll(cf:CombinedFragment|

2

cf.InteractionOperator=SD::InteractionOperator.par

3

implies

4

CCFG::ControlNode.allInstances->exits(fn:ForkNode, jn:JoinNode | -- check if there is a corresponding CCFG for each interaction operand -- of cf and if fn and jn is connected to them

5

cf.operand->forAll(io:InteractionOperand|

6

CCFG::Activity.allInstances->exits(act:Activity|

7

act= Utility::Util.getCCFG(io) and

8

fn.outgoing->exists(flow|flow.target= Utility::Util.getInitialNode(act)) and

9

jn.incoming->exists(flow|flow.source= Utility::Util.getFinalNodes(act))

10

) and

11

fn.inFlow->exists(se:messageEnd|se=Utility::Util.getFirstMessage(io).sendEvent) and

-- check for control flow connections 12

jn.outFlow->exists(re:messageEnd|re=Utility::Util.getLastMessage(io).receiveEvent)

13 14 15

) ) )

Consistency Rule 7-Mapping par CombinedFragment instances to ForkNode instances

For each parallel combined fragment cf (lines 1-2), there should exist a fork fn and a join jn node (line 4). For each interaction operands of cf, there should exist a CCFG (lines 5-7). There should be control flow from fn to initial nodes of all interaction operands of cf (line 8), and from their flow final nodes to jn (line 9). Lines 11-12 check for inflow and outflow message ends of fn and jn. Example Figure 24 shows part of the CCFG instance corresponding to par combined fragment in SD of Figure 7 that satisfies the Consistency Rule 7. In this CCFG instance, ccfg, ioRotateCCFG and ioEmitCCFG are the CCFGs of Cook SD, first and second interaction fragments of the par combined fragment in Figure 7, respectively. Initial and final flow nodes of CCFGs are named as *in and *fn, respectively where * indicates the CCFG name, such as ioEmitCCFGin and ioRotateCCFGfn. The corresponding part of the resulting CCFG is represented in Figure 25. source source

flow2:ControlFlow

fn:ForkNode inFlow

inFlow 1

Rotate.sendEvent: SD::MessageEnd

Emit.sendEvent: SD::MessageEnd

ccfg:Activity

RotateReply.receiveEvent: SD::MessageEnd

1

EmitReply.receiveEvent: SD::MessageEnd

outFlow

outFlow jn:JoinNode

target

target

ioEmitCCFGin: InitialNode 1

ioRotateCCFGin: InitialNode 1

ioEmitCCFG :Activity

ioRotateCCFG :Activity

1 ioEmitCCFGfn: FlowFinalNode

1 ioRotateCCFGfn: FlowFinalNode

source flow4:ControlFlow

target target

flow1:ControlFlow

source flow3:ControlFlow

Figure 24-Part of the CCFG instance corresponding to par combined fragment in SD of Figure 7 that satisfies Consistency Rule 7

35

Carleton University TR SCE-05-09

Updated: September 2005

ccfg=getCCFG(Cook)

fn.inFlow

fn flow1:ControlFlow ioRotateCCFG

flow2 ioEmitCCFG

ioRotateCCFGin

ioEmitCCFGin

...

...

ioRotateCCFGfn

ioEmitCCFGfn flow3

flow4 jn jn.outFlow

Figure 25-Part of the CCFG, corresponding to the instance shown in Figure 24

5.9 loop CombinedFragmentà DecisionNode This consistency rule maps loop combined fragments into decision node constructs. OCL Mapping 1

SD::CombinedFragment.allInstances->forAll(cf:CombinedFragment|

2

cf.interactionOperator=SD::InteractionOperator.loop

3

implies -- get the only interaction operand of cf

4

loopIO=cf.operand.asOrderedSet().first() and

5

CCFG::DecisionNode.allInstances->exits(dn:DecisionNode|

6

CCFG::Activity.allInstances->exits(act:Activity|

7

act=Utility::Util.getCCFG(loopIO) and

8

dn.outgoing->exists(flow:ControlFlow|

9

Utility::getFinalNodes(act)->forAll(afn|

flow.target=Utility::Util.getInitialNode(act) and flow.guard=loopIO.guard) and afn.outgoing->exists(flow:ControlFlow|flow.target=dn)) and -- check for control flow connections 10

dn.inFlow->exists(se:MessageEnd|

11

dn.outFlow->exists(re:MessageEnd|

se=Utility::Util.getFirstMessage(act).sendEvent) and re=Utility::Util.getLastMessage(act).receiveEvent and re.guard=!loopIO.guard) 12

)

13 14

) )

Consistency Rule 8-Mapping loop combined fragment instances to DecisionNode instances

Visualization loop

dn.inFlow:Set(MessageEnd)

[guard] sendEvent

dn:DecisionNode dn.outFlow:Set(MessageEnd) ![guard] [guard] Mapping

CCFG(io)

io:InteractionOperand

...

receiveEvent

36

Carleton University TR SCE-05-09

Updated: September 2005

For each loop combined fragment cf (lines 1-2), the only interaction operand is fetched (line 4). There should exits a decision node dn (line 5) and an activity act (lines 6-7) corresponding to the loop interaction operand such that there is a control flow from dn to act’s initial node with guard condition equal to loop interaction operand’s guard (line 8). There should also be a control flow (with no guard) from act’s final flow node to dn. Lines 10-11 check for inflow and outflow message ends in dn. There should be an inflow/outflow message end(s) in dn equal to send/receive event(s) of the first/last message(s) of act. Example Figure 26 shows part of the CCFG instance corresponding to loop combined fragment in SD of Figure 6 that satisfies the Consistency Rule 8. In this CCFG instance, loopIOCCFG is the CCFG of the loop combined fragment. loopIO is the loop interaction operand in the SD of Figure 6. Initial and final flow nodes of this CCFG are referred to as loopIOCCFGin and loopIOCCFGfn, respectively. The corresponding part of the resulting CCFG is represented in Figure 27. Utility::getFirstMessage( loopIO).sendEvent

ccfg:Activity

flow1:ControlFlow

inFlow

target

loopIOCCFGin: InitialNode 1

1 1

source

guard

dn:DecisionNode

“[s!=FNISHED]”: ValueSpecification

loopIOCCFG :Activity

target outFlow Utility::getLastMessage( loopIO).receiveEvent 1

“[s=FNISHED]”: guard ValueSpecification

flow2:ControlFlow

source

1 loopIOCCFGfn: FlowFinalNode

Figure 26-Part of the CCFG instance corresponding to loop combined fragment in SD of Figure 6 that satisfies Consistency Rule 8 ccfg=getCCFG(AsynchronousRequestProcessing) dn.inFlow

dn.outFlow [guard] flow1 ioloopCCFG flow2 ioloopCCFGin ... ioloopCCFGfn

Figure 27-Part of the CCFG, corresponding to the instance shown in Figure 26

5.10 alt/opt CombinedFragmentàDecisionNode This consistency rule maps alt/opt combined fragments into decision node constructs. Visualization alt

[guard1]

dn.inFlow:Set(MessageEnd)

sendEvent

dn:DecisionNode

receiveEvent

[guard1]

io1:InteractionOperand Mapping

[guard2] io2:InteractionOperand

CCFG(io1)

dn.outFlow:Set(MessageEnd)

[guard2] CCFG(io2)

CCFG(ion)

receiveEvent ...

...

[guardn]

ion:InteractionOperand

[guardn]

outFlow:Set(MessageEnd)

receiveEvent

OCL Mapping

37

...

Carleton University TR SCE-05-09

1

Updated: September 2005

SD::CombinedFragment.allInstances->forAll(cf:CombinedFragment|

2

cf.interactionOperator=SD::InteractionOperator.alt or

3

cf.interactionOperator=SD::InteractionOperator.opt

4

implies

5

CCFG::DecisionNode.allInstances->exits(dn:DecisionNode|

6

cf.operand->forAll(io:InteractionOperand|

7

CCFG::Activity.allInstances->exits(act:Activity|

8

act=Utility::Util.getCCFG(io) and

9

dn.outgoing->exists(flow:ControlFlow|

10

flow.target=Utility::Util.getInitialNode(act) and

11

flow.guard=io.guard)

12

) and -- check for control flow connections

13

dn.inFlow->exists(me:MessageEnd|

14

Utility::Util.getFirstMessage(io)->forAll(m|me=m.sendEvent)) and

15

Utility::getFinalNodes(io)->forAll(afn|afn.outFlow->exists(me:MessageEnd| Utility::Util.getLastMessages(io)->forAll(m|me=m.receiveEvent))

16

) and -- an dn.outFlow should exist if no IO with “else” guard exists

17

if cf.operand->select(io|io.guard=”else”).isEmpty() -- get the last receive event using cf’s general ordering

18

lastGO=cf.generalOrdering.select(go|go.after.toAfter.isEmpty()) and

19

dn.outFlow->exists(me:MessageEnd|me.guard=”else” and me=lastGO.after))

20

end if

21 22

) )

Consistency Rule 9-Mapping alt/opt combined fragment instances to DecisionNode instances

For each alt (alternative) or opt (option) combined fragment cf (lines 1-3), there should exits a decision node dn (line 5), such that for each interaction operands of cf (line 6), there should be an activity act (lines 7-8) and there is control flow from dn to the initial node of each interaction operands of cf (lines 9-10). The guard for this flow is the same as the interaction operand’s (lines 11). Lines 13-15 make sure that the inflow and outflow message ends are included in dn and each interaction operands of cf. The condition (lines 17-20) is responsible for checking that dn has an outflow with else guard condition if none of the cf’s interaction operands are guarded with else. The rational behind this is that if none of the interaction operands’ conditions hold, the whole combined fragment is bypassed by transferring the control flow to the next message in SD. Example Figure 28 shows part of the CCFG instance corresponding to alt combined fragment in SD in Figure 6 that satisfies the Consistency Rule 9. The corresponding part of the resulting CCFG is represented in Figure 29. Utility::getFirstMessage( altIOCCFG).sendEvent

ccfg:Activity

flow:ControlFlow

inFlow

target

altIOCCFGin: InitialNode 1

1 1

source

dn:DecisionNode

outFlow Utility::getLastMessage( altIOCCFG).receiveEvent 1

“[else]”: guard ValueSpecification

guard

“[at=NULL]”: ValueSpecification

altIOCCFG :Activity

1 altIOCCFGfn: FlowFinalNode

Figure 28-Part of the CCFG instance corresponding to alt combined fragment in SD of Figure 6 that satisfies Consistency Rule 9

38

Carleton University TR SCE-05-09

Updated: September 2005

ccfg=getCCFG(AsynchronousRequestProcessing) dn.inFlow dn:DecisionNode

dn.outFlow

flow:ControlFlow altCCFG

...

outFlow

Figure 29-Part of the CCFG, corresponding to the instance shown in Figure 28

5.11 break CombinedFragmentàActivityEdge break

combined fragments are mapped into activity edges (control flows).

OCL Mapping 1

SD::CombinedFragment.allInstances->forAll(cf:CombinedFragment|

2

cf.interactionOperator=SD::InteractionOperator.break

3

implies

4

Utility::Util.getCCFG(cf.enclosingInteraction).node->forAll(an:ActivityNode|

5

implies

6

CCFG::ControlFlow.allInstances->exists(flow:ControlFlow|

7

flow.source=an and

8

flow.target=Utility::Util.getInitialNode(

9

flow.guard=cf.guard

Utility::Util.getCCFG(cf.operand.asOrderedSet().first())) and 10 11 12

) ) )

Consistency Rule 10-Mapping break combined fragment instances to ActivityEdge instances

Visualization CCFG(inter)

inter: Interaction

CCFG(io) in:InitialNode

in:InitialNode m1 ... m2

[guard]

break m3

flow:ControlFlow

[guard]

...

[guard] ...

...

... m4

io:InteractionOperand

en3

[guard]

Mapping en1 ...

... en2

... en4

...

...

...

... eni corresponds to message mi.

For each break combined fragment cf (lines 1-2), all the nodes of cf’s enclosing interaction (SD) are checked (line 4). For each such activity node an, there should exit a control flow from an (line 7) to the initial node of the break combined fragment (line 8). The guard condition of this control flow is the same as the cf’s (line 9). 5.12 Last message endsàFlows between ending control nodes and ActivityFinalNode This consistency rule checks if there are connections from last control nodes of every CCFG to its final flow node. The last control nodes of a CCFG are those which correspond to the last messages of the corresponding SD. The utility function getLastMessages() is used to retrieve such messages.

39

Carleton University TR SCE-05-09

Updated: September 2005

OCL Mapping 1

SD::InteractionFragment.allInstances->forAll(inter:InteractionFragment|

2

implies

3

CCFG::ActivityFinalNode.allInstances->exits(afn:ActivityFinalNode|

4

afn.activity=Utility::Util.getCCFG(inter) and

5

Utility::Util.getCCFG(inter).node->select(an:ActivityNode|

6

Utility::Util.getLastMessages(inter)->includes(an.message)

7

)->forAll(endNode:ActivityNode|

8

afn.incoming->exists(flow:ControlFlow|flow.source=endNode))

9 10

) )

Consistency Rule 11-Mapping last message ends to flows between ending control nodes and ActivityFinalNode

Visualization int: Interaction

CCFG(int) ...

getLastMessages(int): Set(Message) .m=m1

.m=m2

...

Mapping

m1 m2

afn:ActivityFinalNode

...

.m means ControlNode.message

CCFG of each SD is checked to have a flow final node (lines 1-3). All end nodes of the CCFG are selected using Utility::getLastMessages(SD::Interaction) (lines 5-7). Control flow connectivity between the end nodes and the flow final node are checked in line 8. Example Figure 30 shows part of the CCFG instance corresponding to loop combined fragment in SD of Figure 6 that satisfies the Consistency Rule 11. The corresponding part of the resulting CCFG is represented in Figure 31. 1 loopCCFG: Activity 1

message

rn:ReplyNode =getLastMessages(loopCCFG)

ffn:FlowFinalNode target

outgoing

K:SD::Message

source flow:ControlFlow

incoming

Figure 30-Part of the CCFG instance loopCCFG corresponding to loop combined fragment in SD of Figure 6 that satisfies Consistency Rule 11 loopCCFG rn:ReplyNode

rn.message=K

flow:ControlFlow ffn:FlowFinalNode

Figure 31-Part of the CCFG, corresponding to the instance shown in Figure 30

40

Carleton University TR SCE-05-09

Updated: September 2005

5.13 InteractionOccurrenceàControl Flow across CCFGs UML 2.0 SDs can refer to each other using InteractionOccurrence. Such referrals cause a control flow across SDs. This consistency rule maps cross-SD calls to activity edges across CCFGs. OCL Mapping 1

SD::InteractionOccurrence.allInstances->forAll(io:InteractionOccurrence|

2

implies

3

CCFG::ActivityFinalNode.allInstances->exits(cn1,cn2:ControlNode|

4

cn1.outgoing->exists(flow|

5

cn2.incoming->exists(flow|

6

cn1.inFlow->exists(me:MessageEnd|

flow.target=Utility::Util.getInitialNode(getCCFG(io.refersTo))) and getFinalNodes(Utility::Util.getCCFG(io.refersTo))->includes(flow.source)) and Utility::Util.getFirstMessage(io)->forAll(m|me=m.sendEvent) ) 7

cn2.outFlow->exits(me:MessageEnd| Utility::Util.getLastMessages(io)->forAll(m|me=m.receiveEvent) )

8 9

) )

Consistency Rule 12-Mapping InteractionOccurrence to control flow across two CCFGs

Visualization sd M

CCFG(M)

sd N

CCFG(N) ...

m1

inFlow:Set(MessageEnd)

cn1

InteractionOccurrence getFirstMessages(N) :Set(Message)

Mapping ...

cn2

ref N getLasstMessages(N): Set(Message) m2

outFlow:Set(MessageEnd) ...

For each interaction occurrence io (line 1), there should be two control nodes cn1 and cn2 (line 3), such that is a flow from cn1 to the start node of the activity io is referring to (line 4), and also a flow from the final nodes of such activity to cn2 (line 5). Lines 6-7 check for inflow and outflow message ends in cn1 and cn2. Example Figure 32 shows part of the CCFG instance corresponding to lifeline pf:ProcessorFactory in SD in Figure 6 that satisfies the Consistency Rule 12. The corresponding part of the resulting CCFG is represented in Figure 33.

41

Carleton University TR SCE-05-09

Utility::getFirstMessage( nCCFG).sendEvent *

Updated: September 2005

ccfg:Activity

flow:ControlFlow

target

inFlow 1 cn1:ControlNode

nCCFGin: InitialNode 1

source nCCFG :Activity

cn2:ControlNode *

outFlow

target

Utility::getLastMessage( nCCFG).receiveEvent

flow:ControlFlow

source

1 nCCFGfn: FlowFinalNode

Figure 32-Part of the CCFG instance ccfg corresponding to the interaction occurrence N in SD of Figure 6 that satisfies Consistency Rule 12 ccfg=getCCFG(AsynchronousRe questProcessing)

nCCFG=getCCFG(N) nCCFGin

cn1

cn2 nCCFGfn

Figure 33-Part of the CCFG, corresponding to the instance shown in Figure 32

5.14 Polymorphic messageàDecisionNode According to [73], polymorphism introduces a new challenge in software testing because it enables messages to be bounded to different methods based on the class of the receiver object. In a SD, any of the participating lifelines’ corresponding class might be super-class to some other classes (defined in a class diagram). Therefore, depending on the type of an object instantiated from that super-class, the object may behave differently in the SD. To be specific, since we have signal and method calls in a SD, a particular method of a class in a polymorphism relationship might get bounded to different overridden methods of its sub-classes at runtime, which in turn, causes a message to be handled differently in term of control flow by the receiver object of a message. We discuss in this section how to taken into account this polymorphism behavior in lifelines. It is required that the control flows of all the sub-class methods (if a method is overridden) of a super-class have to be analyzed for polymorphic message. For example, suppose the SDs and the CD shown in Figure 34. In the CD of Figure 34, NetworkInterface abstract class is the super-class of three sub-classes Wired, Wireless and Adhoc. Class Process uses an object of NetworkInterface abstract class to send data. Depending on the communication scheme in the system, the nodes may communicate in Wired, Wireless or Adhoc network mode. An adhoc network is a wireless network composed of stations without access points. Due to differences in the underlying network concepts for each of the above network types, the send() method for each of them has to be different. Therefore, three network interface classes Wired, Wireless and Adhoc are inherited from NetworkInterface class where send() is overridden in each of them to suit the features of the underlying network. Now consider the SD of Figure 34, where a send() call has been made from an object of the Process class to an object of type NetworkInterface. Depending on which sub-class this object has been bound to at runtime, the control flow of send() will change accordingly. Three other SDs (shown in the lower portion of Figure 34) represent the different behavior each sub-class will have for message send(). Note that these three SDs have different set of messages inside, i.e., they handle send(data) differently.

42

Carleton University TR SCE-05-09

Updated: September 2005

sd M NetworkInterface p:Proces

:NetworkInterface

Process

+send(in data)

send(data)

sd Wired::send(data)

Wired

Wireless

Adhoc

+send(in data)

+send(in data)

+send(in data)

sd Wireless::send(data)

:Wired

sd Adhoc::send(data)

:Wireless

send(data)

:Adhoc

send(data)

send(data)

m1()

m2()

...

m3()

...

...

Figure 34-A sequence and a class diagram showing the effect of classes with polymorphism in CFA

In the context of UML, we have to use class diagrams (CDs) to find out about the generalization (inheritance) relationships among classes and therefore be able to appropriately handle polymorphic behaviors of objects in SD lifelines in term of CFA. In order to do so, we present the metamodel of generalization relationship in CDs in the following (Section 5.14.1). Afterwards (in Section 5.14.2), we will present a consistency rule which identifies such polymorphic behaviors in SD lifelines and devises appropriate control flow structure. 5.14.1 Metamodel of Generalization Relationships in CDs Version 2.0 of UML has enhanced the metamodel of CDs, compared to the earlier 1.x version (Section 7 of [11]). Since our goal here is to only find out about the generalization relationships among classes and therefore be able to appropriately handle polymorphic behaviors of objects in SD lifelines in term of CFA, hence we only consider the part of the CD metamodel which deal with generalizations. According to Section 7.8 of [11] (‘Classifier Diagrams’), we present in Figure 35 the part of CD’s metamodel which focuses on generalization relationships. 1 general

general * Classifier

Generalization

-isAbstract : bool = false specific 1 1 inheritedMember NamedElement

generalization *

* Class

Figure 35-Part of the UML 2.0 ‘Classifier Diagram’, Section 7.8 of [11]

In Figure 35, Class inherits from Classifier. Association inheritedMember specifies all classes inherited from a class. Association general specifies all parents (super-classes) of a class, which it is inherited from. Association generalization specifies the generalization relationships hierarchies a class is associated with. Generalization is itself a class which is described in Section 7.8.2 of [11]. As we will see in the following consistency rule, inheritedMember association is enough for our purpose of identifying generalization relationships among classes. In the following, we present a consistency rule

43

Carleton University TR SCE-05-09

Updated: September 2005

which identifies polymorphic behaviors in SD lifelines and uses the information from generalization relationships among classes to devise appropriate control flow. 5.14.2 Consistency Rule Identifies polymorphic behaviors in SD lifelines and devises appropriate control flow structures for such cases. OCL Mapping 1

SD::Message.allInstances->forAll(m:Message|

2

mReceiverClass=CD::Classifier.allInstances->select(c:Classifier|

3

if mReceiverClass.inheritedMember.size>0 then (

c.name=m.receiveEvent.covered.class_name).asOrderedSet().first() and -- this means that the class receiving the message m has at least one inherited class -- map the scenario to a conditional control flow structure 4

CCFG::ConditionalNode.allInstances->exits(dn:DecisionNode|

5

dn.message=m and -- for all sub-classes

6

mReceiverClass.inheritedMember->forAll(inheritedClass| -- if m is redefined in inheritedClass

7

if inheritedClass.ownedOperation->exits(op:Operation| op.name=m.signature) then (

8

dn.outgoing->exits(flow|

9

inheritedClassAct=

10

SD::Interaction.allInstances->select(int|int.className=

11

inheritedClass.name and int.methodName=m.name) and

12

flow.target=getCCFG(inheritedClassAct).initialNode and

13

flow.guard=‘[m.receiveEvent.covered.class_name=inheritedClass]’

14

) and

15

getCCFG(inheritedClassAct).activityFinalNode.outFlow ->exists(me|me=m.receiveEvent)

16

) else ( -- if m is NOT redefined in inheritedClass, then just -- use ‘else’ as the guard. base-class’s m() will execute in this case

17

cn.outgoing->exits(flow|

18

superClassAct=SD::Interaction.allInstances->select(inter|

19

inter.className=mReceiverClass and inter.methodName=m.name)

20

and flow.target=getCCFG(superClassAct).initialNode

21

and flow.guard=’else’

22

) and

23

getCCFG(superClassAct).activityFinalNode.outFlow ->exists(me|me=m.receiveEvent)

24

) endif

25

) and

26

dn.inFlow->exists(me|me=m.sendEvent)

27 28 29

) ) endif )

Consistency Rule 13- Handling polymorphic lifelines in CFA

Visualization

44

Carleton University TR SCE-05-09

Updated: September 2005

sd M

dn.inFlow:Set(MessageEnd) baseClas

dn:DecisionNode

:baseClas m() receiveEvent

+m()

subClass

subClass

+m() Mapping

sd subClass1::m()

sd subClass2::m()

sd baseClass::m()

[m.receiveEvent. covered.class_name=subClass2]

CCFG( subClass1,m()) :subClass

:subClass

m()

CCFG( subClass2,m())

CCFG( baseClass,m())

:baseClas

m()

m() ...

...

] se [el

subClass

co ve red [m.r .cla ece ss ive _n Ev am en e= t. su bC las s1 ]

+m() sendEvent

...

...

...

...

outFlow:Set(MessageEnd)

Each message is checked (line 1). The class mReceiverClass of message’s receiver lifeline is retrieved (line 3). The consistency rule further proceeds if mReceiverClass has at least one inherited classes (line 4). This indicates that the polymorphic message will be handled differently depending on which object type receives it. The OCL expression block in lines 5-29 ensures that the polymorphic message is mapped to a conditional control flow, whose description is given next. For each polymorphic message m, there should exist a corresponding decision node dn (lines 5-6). For each (line 7) sub-classes inheritedClass of the class mReceiverClass (the message’s receiver lifeline), message m is checked whether it has been redefined in inheritedClass (line 8). If yes, there should be a control flow from the decision node dn to the initial node of the activity corresponding to message m defined in the context of inheritedClass (lines 9-13).This control flow bares the guard condition of the receive class of lifeline being this particular inheritedClass (lines 14-15).The final flow node of the activity corresponding to message m defined in the context of inheritedClass is also checked to have appropriate outflow message end (line 17). In the case when the message m is not redefined in inheritedClass (line 18), this means that the super class’s m activity will be the target of control flow. In this case, there should be a control flow from the decision node dn to the initial node of the activity corresponding to message m defined in the context of the super class (lines 19-22). The guard condition of this flow is ‘else’ (line 23), indicate that m is not redefined in inheritedClass. The final flow node of the activity corresponding to message m defined in the context of the super class is also checked to have appropriate outflow message end (line 25). Finally line 28 ensures the proper inflow message end in dn. Example Figure 36 shows part of the CCFG instance corresponding to the message send(data) in SD M of Figure 34 that satisfies the Consistency Rule 13. The corresponding part of the resulting CCFG is represented in Figure 37.

45

Carleton University TR SCE-05-09

Updated: September 2005

ccfg:Activity

1 m.sendEvent

inFlow

dn:DecisionNode

message

m:SD::Message

source

flow1:ControlFlow

flow2:ControlFlow

target

target

flow3:ControlFlow

target

WiredCCFGin: InitialNode 1

WirelessCCFGin: InitialNode 1

AdhocCCFGin: InitialNode 1

WiredCCFG :Activity

WirelessCCFG :Activity

AdhocCCFG :Activity

1 WiredCCFGfn: FlowFinalNode

1 WirelessCCFGfn: FlowFinalNode

1 AdhocCCFGfn: FlowFinalNode

outFlow m.receiveEvent

Figure 36-Part of the CCFG instance ccfg corresponding to the message send(date) in SD M of Figure 34 that satisfies Consistency Rule 13 ccfg=getCCFG(M) dn.inFlow

oc t. en dh Ev e=A i ve m ce na .re s_ [m .clas d re ve co

co ve [ m re .re d.c ce las ive s_ Ev na en me t. =W ire d]

dn:DecisionNode

flow1

flow3

flow2

WiredCCFG= CCFG( Wired::send(data))

...

WirelessCCFG= CCFG( Wireless::send(data))

...

]

[m.receiveEvent. covered.class_name=Wireless]

AdhocCCFG= CCFG( Adhoc::send(data))

...

outFlow

Figure 37-Part of the CCFG, corresponding to the instance shown in Figure 36

5.15 Interaction Fragment and its Enclosing Interaction FragmentàCCFG and its Parent CCFG Each interaction fragments (InterFrag) and its enclosing InterFrag are mapped into CCFGs where the CCFG corresponding to the enclosing InterFrag is the parent of the CCFG corresponding to the enclosed InterFrag.

46

Carleton University TR SCE-05-09

Updated: September 2005

OCL Mapping 1

SD::InteractionFragment.allInstances->forAll(childInterFrag, parentInterFrag:InteractionFragment|

2

childInterFrag.enclosingInteraction=parentInterFrag

3

implies

4

CCFG::Activity.allInstances->exists(childCCFG, parentCCFG:Activity|

5

parentCCFG=Utility::getCCFG(parentInterFrag) and

6

childCCFG=Utility::getCCFG(childInterFrag) and

7

childCCFG.parent=parentCCFG and

8

parentCCFG.children->includes(childCCFG)

9

parentCCFG.nodes->exists(an:ActivityNode|

10

an.outgoing->exists(flow:ControlFlow|

11

)

flow.target=Utility::getInitialNode(childCCFG) 12

)

13 14

) )

Consistency Rule 14-Mapping InteractionFragment and its enclosing InteractionFragment to CCFG and its parent CCFG

Visualization parentCCFG=getCCFG(parentInterFrag)

parentInterFrag

an

childInterFrag

Mapping

childCCFG= getCCFG(childInterFrag)

An InterFrag (childInterFrag) and its enclosing InterFrag (parentInterFrag) are selected in lines 1-2. For each such pair, there should be (line 4) two CCFGs childCCFG and parentCCFG being the CCFG of the two InterFrag’s, respectively (lines 5-6). The parent association of childCCFG is set to parentCCFG (line 7) and parentCCFG’s list of children should include childCCFG (line 8). There should be an activity node an inside parentCCFG (line 9) such that there is a flow from an to childCCFG‘s initial node (line 10). Example SDCCFG= getCCFG(AsynchronousRequestProcessing)

flow:ControlFlow

source an: ActivityNode 1

SDCCFG :Activity

an

target loopIOCCFGin: InitialNode 1

parent

child

loopIOCCFG :Activity

flow:ControlFlow loopIOCCFG= getCCFG(loopIO)

in:InitialNode

Figure 38-(a): Part of the two CCFG instances SDCCFG and loopIOCCFG corresponding to the SD and loop CombinedFragment in Figure 6 that satisfies Consistency Rule 14 - (b): Part of the CCFG, corresponding to the instances shown in (a)

5.16 Utility Functions To reduce the complexity of the consistency rules and also make them more readable, we define a set of utility functions in this section. The utility class, containing the functions, is shown in Figure 39. OCL 47

Carleton University TR SCE-05-09

Updated: September 2005

context Utility will be used in OCL expressions of the consistency rules to refer to the functions of utility class such as Utility::Util.getCCFG().

Util,

We present a function called MultipleIncomingControlFlowsToMergeNode in Section 5.16.9 to keep the well formed-ness of CCFGs (AD) in terms of nodes with multiple incoming flows. The function transforms each activity nodes with more than one incoming control flow to a merge node and a new activity node such that the multiple incoming flows are towards the merge node and there is a single flow from the merge node to the activity node. This function has to be applied to the instances of ControlNode after the operation responsible for transforming an instance of the SD metamodel into an instance of the CCFG metamodel, suing the consistency rules, has been performed. The result of applying this function on CCFG activity node H of Figure 6 is shown with a merge node before it in the CCFG. Util +getCCFG(in interFrag:SD::InteractionFragment) +getTypeOfMessage(in m:SD::Message) +getObjectPartition(in objectName:NamedElemenet, in className:NamedElemenet) +getFirstMessage(in interFrag:SD::InteractionFragment) +getLastMessages(in interFrag:SD::InteractionFragment) +getFirstEventOccurrence(in events:Set(SD::EventOccurrence)) +getInitialNode(in act:CCFG::Activity) +getFinalNodes(in act:CCFG::Activity) +MultipleIncomingControlFlowsToMergeNode()

Figure 39-Utility class Util containing a set of utility functions used in the consistency rules

5.16.1 getCCFG This function returns the CCFG::Activity instance associated with an instance of SD::InteractionFragment. 1

context Utility::Util.getCCFG(interFrag:SD::InteractionFragment):CCFG::Activity

2

pre: CCFG::Activity.allInstances->select(act:Activity|act.interFrag=interFrag)->size=1

3

post: result = CCFG::Activity.allInstances->select(act:Activity|act.interFrag=interFrag)

4

.asOrderedSet().first();

Utility Function 1-Utility function to returns the CCFG::Activity instance associated with an instance of SD::InteractionFragment

5.16.2 getTypeOfMessage As shown in the CCFG metamodel (Figure 10), we intend to distinguish between SD call and reply messages by mapping them into CCFG call and reply nodes. We also saw in Section 3.1 that UML 2.0 does not have a standard defined way in its SD metamodel to distinguish between call and reply messages. We intend to compare the SendEvent and ReceiveEvent attributes of every message with its corresponding ExecutionOccurrence to determine if a message is a call or a reply. Let us present the rational using the Figure 40 which shows the relationship between EventOccurrence’s and ExecutionOccurrence’s. Each EventOccurrence of a message has two associations startExec and finishExec referring to the start and finish events of the ExecutionOccurrence’s associated with the message. For example, the ExecutionOccurrence eo in Figure 40 is executed when message m1 is sent. The expression for building this association is m1.receiveEvent.startExec=eo or m1.receiveEvent=eo.start. Similarly, m2 starts when eo ends its execution, i.e., m2.sendEvent.endExec=eo or m2. sendEvent=eo.finish.

m1.sendEvent

m1 m1.receiveEvent

eo:ExecutionOccurrence

m2 m2.receiveEvent

eo.start

m2.sendEvent

eo.finish

Figure 40-Relationship between EventOccurrence‘s and ExecutionOccurrence‘s

48

Carleton University TR SCE-05-09

Updated: September 2005

Using the above discussion and also since the cardinality of startExec and finishExec associations of EventOccurrence is [0..1], we can say that the receiveEvent of a call message has an EventOccurrence in its startExec field, while its finishExec is empty. Conversely, the sendEvent of a reply message has an EventOccurrence in its finishExec field, while its startExec is empty. We use this criterion to determine the type of a message. We define a function called getTypeOfMessage here to make the distinction between call and reply messages.

1 2

context Utility::Util.getTypeOfMessage(m:SD::Message):String post: result =

3

if not (m.receiveEvent.oclAsType(SD::EventOccurence).startExec->isEmpty())

4

“call”

5

else if not (m.sendEvent.oclAsType(SD::EventOccurence).finishExec->isEmpty())

6

“reply”

7

end if

Utility Function 2-Utility function to distinguish between call and reply messages

5.16.3 getObjectPartition This utility function returns the CCFG objects partition associated with a SD lifeline, which is identified by an object name. 1 2

context Utility::Util.getObjectPartition(objectName:NamedElement):CCFG::ObjectPartition pre: CCFG::ObjectPartition.allInstances->select(op:ObjectPartition|

3

op.objectName=objectName

4 5

)->size=1 post: result = CCFG::ObjectPartition.allInstances->select(op:ObjectPartition|

6

op.objectName=objectName

7

).asOrderedSet().first()

Utility Function 3- Utility function to return CCFG object partition instance given an object and class name

5.16.4 getFirstMessage This function returns the first message of a given interaction fragment according to the ordering in its SD::GeneralOrdering. 1 2 3 4 5 6

context Utility::Util.getFirstMessage(interFrag:SD::InteractionFragment):SD::Message pre: SD::Message.allInstances->select(m:Message| m.interaction=inter and m.sendEvent.oclAsType(SD::EventOccurence).toBefore->isEmpty() )->sizeselect(m:Message|

7

m.interaction=inter and

8

m.sendEvent.oclAsType(SD::EventOccurence).toBefore->isEmpty()

9

).asOrderedSet().first()

Utility Function 4-Utility function to return the first message(s) of a given interaction

5.16.5 getLastMessages This function returns the last message(s) of a given interaction (SD) according to the ordering in its SD::GeneralOrdering. Since a SD::Interaction may have more than one last message, i.e. more than one message without any messages after it in SD::GeneralOrdering, therefore this function may return a set of messages.

49

Carleton University TR SCE-05-09

1 2

Updated: September 2005

context Utility::Util.getLastMessages(interFrag:SD::InteractionFragment):Set(SD::Message) post: result = SD::message.allInstances->select(m:Message|

3

m.interaction=inter and

4

m.sendEvent.oclAsType(SD::EventOccurence).toAfter->isEmpty()

5

)

Utility Function 5-Utility function to return the last message(s) of a given interaction

5.16.6 getFirstEventOccurrence Using the partial ordering available in SD::GeneralOrdering, this function returns the first event occurrence in a set of event occurrences. The first event occurrence here denotes the event occurrence which is before all event occurrences in the set. UML 2.0 does not enforce ordering of event occurrences in sets of GeneralOrdering by accessing m.receiveEvent.toAfter, where m is a message. Therefore, we define a function named getFirstEventOccurrence here to find the event occurrence just after a given one on a given lifeline. As an overview, a piece of a SD showing how to order EventOccurrences with GeneralOrderings is shown in Figure 41. GeneralOrdering

eo1 eo2

goi.before

goi.after

go1

eo1

eo2

go2

eo1

eo3

go3

eo1

eo4

go5

eo1

eo5

go6

eo2

eo3

go7

eo2

eo4

go8

eo2

eo5

eo3

eo5

eo3 eo4

eo5

… gon

Figure 41-Ordering EventOccurrences with GeneralOrderings

Function getFirstEventOccurrence receives a set of event occurrences, eos:Set(SD::EventOccurrence), as well as a lifeline ll, where the order of event occurrences should be compared in. The first such event occurrence is returned. 1

context Utility::Util.getFirstEventOccurrence(eos:Set(SD::EventOccurrence), ll:SD::Lifeline): SD::EventOccurrence

2 3

post: result = SD::EventOccurrence.allInstances->select(feo|feo.covered=ll and SD::GeneralOrdering.allInstances->select(go|

4

eos->includes(go.before) and

5

go.before.covered=ll and go.after.covered=ll and

6 7 8

go.after=feo )->size=0 ).asOrderedSet().first()

Utility Function 6-Utility function to return the first event occurrence in a set of event occurrences on a given lifeline

5.16.7 getInitialNode This function returns the initial node of the given activity.

50

Carleton University TR SCE-05-09

9

Updated: September 2005

context Utility::Util.getInitialNode(act:CCFG::Activity):CCFG::InitialNode

10

pre: act.nodes->select(an:ActivityNode|an.oclType=InitiaNode)->size=1

11

post: result = act.nodes->select(an:ActivityNode|an.oclType=InitiaNode).asOrderedSet().first()

Utility Function 7-Utility function to return the initial node of the given activity

5.16.8 getFinalNodes This function returns the activity final nodes of the given activity. 1

context Utility::Util.getFinalNodes(act:CCFG::Activity):Set(CCFG::ActivityFinalNode)

2

post: result = act.nodes->select(an:ActivityNode|an.oclType=ActivityFinalNode)

Utility Function 8-Utility function to return the activity final nodes of the given activity

5.16.9 MultipleIncomingControlsFlowToMergeNode This function has to be applied to all the activity nodes instances with more than one incoming control flow. It transforms each activity nodes with more than one incoming control flow to a merge node and a new activity node such that the multiple incoming flows are toward the merge node and there is a single flow from the merge node to the activity node. This is done to keep the well formed-ness of CCFGs (AD) in terms of nodes with multiple incoming flows. Although the number of incoming control flows into an activity node can be more than one (shown with an * on the binary association between ActivityNode and ActivityEdge in Figure 177 of [11] and there is no constraint limiting the number of incoming flows, however it seems that UML 2.0 recommend the use of merge node when there is more than one incoming control flow into an activity node. To keep our CCFGs well-formed, this consistency rule will search for activity nodes with more than one incoming control flow and will map them to a merge node along with the necessary modifications in the control flows. OCL Expression 1

context Utility::Util.MultipleIncomingControlsFlowToMergeNode(an:CCFG::ActivityNode)

2

pre:

3

an.oclType!=CCFG::MergeNode and

4 5

an.incoming.size>1 and an.oclType!=CCFG::DecisionNode

post:

an.activity.includes(mn:CCFG::MergeNode|

6

an.incoming->forAll(flow_i|flow_i.target=mn) and

7 8

an.activity.edges->exists(flow|flow.source=mn and flow.target=an) )

Utility Function 9-Utility function to transform multiple incoming control flows of an activity node to merge node

Visualization ccfg

ccfg

flow_n

flow_1 ...

flow_1 [n>1]

... mn

Mapping

an

flow_n

flow

an

As the pre-condition states, the function should be applied to any activity node an with more than one incoming flow (lines 2-4), which is neither a merge nor a decision node. The function’s post-condition 51

Carleton University TR SCE-05-09

Updated: September 2005

indicates that there should exist a merge node mn (line 5) in the CCFG (activity) instance of an, such that the incoming flows to an should be changed towards mn (line 6), and there should be a control flow from mn to an (line 7). Example Figure 42-(a) shows part of the CCFG instance corresponding to the incoming flows of control node H in SD of Figure 6 that has been created after applying the above function. Part (b) of Figure 42 visualizes the instance shown in part (a). flow1:ControlFlow

flow2:ControlFlow

incoming

incoming

target ccfg:Activity

flow1

target

flow2

mn:MergeNode 1

source

mn

outcoming

flow

flow:ControlFlow incoming

H

target H:ControlNode (a)

(b)

Figure 42-(a): Part of the CCFG instance ccfg corresponding to the incoming flows of control node H in SD of Figure 6 that has been created after applying the function MultipleIncomingControlsFlowToMergeNode -(b): Part of the CCFG, corresponding to the instance shown in (a)

6 CONCURRENT CONTROL FLOW PATHS In the previous sections, we discussed how a SD can be mapped into a CCFG. To derive all different Concurrent Control Flow Paths (CCFPs) of a CCFG, a grammar is given here. CCFG and CCFP in this context correspond to the conventional CFG and CFP concepts, except that, in addition to all features of CFG and CFP, CCFG and CCFP take into account the intra-SD concurrency (Section 4.1) as well. 6.1 Grammar The CCFG corresponding to a SD M, CCFG(M) includes one or more CCFPs. CCFG(M) is defined as a set of concurrent paths, each starting from the initial node of CCFG(M) to its activity final node (Figure 10). A concurrent path is a path which includes all the paths going out from a fork node in CCFG (see the example in Figure 11). A CCFP is made by traversing from the initial node to the final node and concatenating all the nodes in the path. Similar to conventional CFA techniques, special considerations regarding decision nodes should be made in terms of conditions and loops, i.e. two different CCFPs for true/false edges of a conditional should be derived. Formally, the set of all CCFPs of a CCFG can be derived using the following grammar.  CCFP    CCFP ::= CCFP .CCFP | FlowNode |  L  | LoopCCFP | ConditionalCCFP | ε  CCFP    FlowNode ::= InitialNode | FinalNode | CallNode | Re plyNode | ForkNode | JoinNode LoopCCFP ::= CCFP | (CCFP ) | (CCFP ) ConditionalCCFP ::= TrueCCFP | FalseCCFP avg

max

|ε

TrueCCFP ::= CCFP FalseCCFP ::= CCFP Equation 1- A grammar for the CCFPs of a CCFG

In Equation 1, the first line indicates that: (1) The concatenation of two CCFPs gives a CCFP, (2) FlowNode is actually the basic building block for CCFPs, (3) The notation of two parentheses is for CCFPs with intra-SD

52

Carleton University TR SCE-05-09

Updated: September 2005

concurrency. In the case when there is a fork and join nodes in a CCFG, it means that there is intra-SD concurrency in the CCFG. An open (close) parenthesis corresponds to a fork (join) node, and (4) LoopCCFP and ConditionalCCFP denote that a CCFP can be built from loop and conditional blocks of a CCFG. ε is the standard empty string notation in regular expressions, meaning an empty CCFP in our context. The second line indicates that the flow nodes can be any of the listed nodes. The third line is for loop CCFPs and has a strategy similar to what is used to test loops in code, i.e. each loop is bypassed (ε) – if possible, taken only once (CCFP), a representative or average number above 1 (avg), and a maximum number of times (max). The fourth line is for conditional CCFPs and specifies that either the true or false path of a condition may be followed to derive two different CCFPs. The fifth and sixth lines state that the true and false paths of a conditional CCFP are CCFPs as well. Equation 1 can also be considered as the grammar for a well-formed CCFP. The main difference between CCFPs (shown with the grammar in Equation 1) with regular CFPs is the inclusion of concurrency in CCFPs (shown as parentheses in the first line of Equation 1). As a constraint for a well-formed CCFP is that the first and the last flow nodes of a CCFP should be the initial and activity final nodes of the CCFG corresponding to an interaction (SD). As examples of CCFPs, considering the CCFG in Figure 11, the set of all CCFPs is shown in Figure 43. The symbol ρ will be used in the rest of this article to refer to CCFPs.      JK    DE     DE    ρ1 = ABC  ρ ABC = 2       FGHI   FGHI         ( JK )2    ( JK )3    DE         ρ 4 = ABC  DE   ρ3 = ABC       FGHI   FGHI      Figure 43- CCFPs of the CCFG in Figure 11

Four CCFPs for the CCFG in Figure 11 are due to the decision node (corresponding to a loop) in the CCFG. According to the grammar of CCFPs (Equation 1), a loop can either be bypassed (ε) – if possible, taken only once, a representative or average number, and a maximum number of times. These possibilities have derived the four CCFPs: ρ1, ρ2, ρ3 and ρ4. The loop is bypassed in ρ1, taken once in ρ2, repeated twice in ρ3, and a maximum number (m) of times in ρ4. 6.2 Inter-SD CCFPs Similar to the concept of inter-procedural CFG and CFPs [1], inter-SD CCFG and CCFPs can be defined. An inter-SD CCFG is a CCFG where a SD calls another SD by using UML 2.0’s interaction occurrences. Similarly, an inter-SD CCFP is a CCFP where the CFP goes across two CCFGs due to a call from a node in one of the CCFGs to a node in the other CCFG. 6.3 Representation of CCFPs as Graphs A graph representation can be used to show CCFPs. For example, graph representation of CCFPs ρ1 and ρ3 (Figure 43) is shown in Figure 44.

53

Carleton University TR SCE-05-09

Updated: September 2005

ρ1

F A

B

G

H

I

Legend Call Node

C

Reply Node

ρ3 A

B

D

E

F

G

D

E

H

I

C

J

K

J

K

Figure 44- Representation of CCFPs as graphs

7 ACKNOWLEDGEMENTS This work was in part supported by Siemens Corporate Research, Princeton, NJ and a Canada research chair.

8 CONCLUSIONS AND FUTURE WORKS This article presents a control flow analysis methodology for UML 2.0 sequence diagrams, which is based on defining formal mapping rules between metamodels. In contrast to the conventional code-based control flow analysis techniques, this technique can be used earlier in the software development life cycle, when the UML design model of a system becomes available. The output of our MBCFA can be used as a modelbased test requirements generation methodology, needed by various testing techniques. Other usages of the generated control flow information include model execution, model comprehension, and conformance verification of model with code. Based on well-defined UML 2.0 activity diagrams, we used a customized activity diagram metamodel, referred to as Concurrent Control Flow Graph (CCFG), as the control flow model in this work. Our strategy was to define an OCL-based mapping in a formal and verifiable form as consistency rules between a SD and a CCFG, so as to ensure the completeness of our metamodels and allow their verification. Furthermore, a grammar was defined for Concurrent Control Flow Paths (CCFPs). CCFPs are a generalization to the conventional Control Flow Path concept handling nested concurrent paths. Some of our future research directions are: (1) definition of test-based coverage criteria in CCFGs and CCFPs, (2) a metamodel for CCFPs and consistency rules to derive all CCFPs from a CCFG (this can provide a formal technique for derivation of CCFPs), (3) defining a consistency-rule based Data Flow Analysis (DFA) technique to derive data flow information from SDs, and (4) implementing OCL transformation rules to transform a SD into a CCFG, i.e., using MDA’s [26] transformation definition language. The last idea is similar to the transformation rules given in [26] to transform a PIM (Platform Independent Model) to a PSM (Platform Specific Model) in the context of the MDA framework.

REFERENCES [1]

S. Muchnick, Advanced Compiler Design and Implementation, First ed: Morgan Kaufmann, 1997.

[2]

A. T. Chusho, "Test data selection and quality estimation based on the concept of essential branches for path testing," IEEE Tran. on Soft. Eng., vol. 13, no. 5, pp. 509-517, 1987.

[3]

A. Bertolino and M. Marre, "Automatic Generation of Path Covers Based on the Control Flow Analysis of Computer Programs," IEEE Tran. on Soft. Eng., vol. 20, no. 12, pp. 885-899, 1994.

54

Carleton University TR SCE-05-09

Updated: September 2005

[4]

B. Marick, "Experience With the Cost of Different Coverage Goals For Testing," Proc. Pacific Northwest Soft. Quality Conf., pp. 147-164, 1991.

[5]

Z. Jin and J. Offutt, "Coupling-based Criteria for Integration Testing," Soft. Testing, Verification, and Reliability, vol. 8, no. 3, pp. 133-154, 1998.

[6]

S. Rapps and E. J. Weyuker, "Data flow analysis techniques for test data selection," Proc. Int. Conf. on Soft. Eng., pp. 272-278, 1982.

[7]

M. Harrold and M. Soffa, "Interprocedual data flow testing," Proc. Symp. on Soft. Testing, Analysis, and Verification, pp. 158-167, 1989.

[8]

M. J. Harrold and G. Rothermel, "Performing data flow testing on classes," Proc. Symp. on Foundations of Soft. Eng., pp. 154-163, New Orleans, Louisiana, United States, 1994.

[9]

N. Gupta and R. Gupta, "Data Flow Testing," in The Compiler Design Handbook: Optimizations and Machine Code Generation: CRC Press, 2002.

[10]

OMG, "Unified Modeling Language Specification (v1.3)," 1999.

[11]

OMG, "UML 2.0 Superstructure Final Adopted specification," 2003.

[12]

OMG, "Unified Modeling Language Specification (v1.5)," 2003.

[13]

A. Rountev, S. Kagan, and J. Sawin, "Coverage Criteria for Testing of Object Interactions in Sequence Diagrams," Proc. Conf. Fundamental Approaches to Soft. Eng., pp. 289-304, 2005.

[14]

M. Okazaki, T. Aoki, and T. Katayama, "Formalizing sequence diagrams and state machines using Concurrent Regular Expression," Proc. Int. Workshop on Scenarios and State Machines: Models, Algorithms, and Tools, pp. 74-79, 2003.

[15]

S. Bernardi, S. Donatelli, and J. Merseguer, "From UML sequence diagrams and statecharts to analyzable Petri-net Models," Proc. Int. Workshop on Soft. and Performance, pp. 35-45, 2002.

[16]

J. Cardoso and C. Sibertin-Blanc, "Ordering actions in sequence diagrams of UML," Proc. Int. Conf. on Information Technology Interfaces, pp. 3-14, 2001.

[17]

E. Burd, D. Overy, and A. Wheetman, "Evaluating Using Animation to Improve Understanding of Sequence Diagrams," Proc. Int. Workshop on Program Comprehension, pp. 07-113, 2002.

[18]

Y. Wu, M.-H. Chen, and J. Offutt, "UML-Based Integration Testing for Component-Based Software," Proc. Int. Conf. on COTS-Based Software Systems, pp. 251-260, 2003.

[19]

A. Abdurazik and J. Offutt, "Using UML Collaboration Diagrams for Static Checking and Test Generation," Proc. Int. Conf. on the Unified Modeling Language, pp. 383-395, 2000.

[20]

F. Fraikin and T. Leonhardt, "SeDiTeC-testing based on sequence diagrams," Proc. Int. Conf. on Automated Soft. Eng., pp. 261-266, 2002.

[21]

S. Pickin, C. Jard, Y. L. Traon, T. Jéron, J.-M. Jézéquel, and A. L. Guennec, "System Test Synthesis from UML Models of Distributed Software," Proc. Int. Conf. Formal Techniques for Networked and Distributed Systems, pp. 97-113, 2002.

[22]

O. Pilskalns, A. Andrews, S. Ghosh, and R. France, "Rigorous Testing by Merging Structural and Behavioral UML Representations," Proc. Int. Conf. on the Unified Modeling Language and Applications, pp. 234-248, 2003.

[23]

R. Binder, Testing Object-Oriented Systems: Models, Patterns, and Tools: Addison-Wesley, 1999.

55

Carleton University TR SCE-05-09

Updated: September 2005

[24]

L. Briand and Y. Labiche, "A UML-based approach to system testing," J. of Software and Systems Model, vol. 1, no. 1, pp. 10-42, 2002.

[25]

J. Rumbaugh, I. Jacobson, and G. Booch, UML Reference Manual: Addison-Wesley, 1999.

[26]

A. Kleppe, J. Warmer, and W. Bast, MDA Explained: The Model Driven Architecture-Practice and Promise, 1st ed: Addison-Wesley Prof., 2003.

[27]

A. Rountev, O. Volgin, and M. Reddoch, "Control Flow Analysis for Reverse Engineering of Sequence Diagrams," Technical Report OSU-CISRC-3/04-TR12, Dept. of Comp. Sci. and Eng., Ohio State Uni. 2004.

[28]

E. Glynn, I. Hayes, and A. MacDonald, "Integration of generic program analysis tools into a software development environment," Australasian Computer Science Conf., pp. 249–258, 2005.

[29]

M. Ward, "The FermaT Assembler Re-engineering Workbench," Proc. Int. Conf. on Softw. Maint., pp. 659-662, 2001.

[30]

M. M. Moore, "User Interface Reengineering," in PhD thesis, CS Dept., Georgia Inst. of Tech., 1995.

[31]

S. J. Mellor and M. J. Balcer, Executable UML: Foundation for Model-Driven Architecture, 1st ed: Addison-Wesley Professional, 2002.

[32]

R. J. Pooley and C. Kabajung, "Simulation of UML Sequence Diagrams," Proc. UK Performance Eng. Workshop, pp. 198-207, 1998.

[33]

L. C. Briand, Y. Labiche, and J. Leduc, "Towards the Reverse Engineering of UML Sequence Diagrams for Distributed Real-Time Java Software," Technical Report SCE-04-04, Carleton Uni. 2004.

[34]

F. E. Allen, "Control flow analysis," Proc. Symp. on Compiler Optimization, pp. 1-19, 1970.

[35]

J. M. Ashley, "A practical and flexible flow analysis for higher-order languages," Proc. Int. Symp. on Principles of Programming Languages, pp. 184-194, 1996.

[36]

K.-F. Faxén, "Optimizing Lazy Functional Programs Using Flow Inference," Static Analysis Symposium, 1995.

[37]

S. Jagannathan and S. Weeks, "Analyzing stores and references in a parallel symbolic language," Proc. Conf. on LISP and Functional Programming, pp. 294-305, 1994.

[38]

S. Jagannathan and S. Weeks, "A unified treatment of flow analysis in higher-order languages," Proc. Symp. on Principles of Programming Languages, pp. 393-407, 1995.

[39]

S. Jagannathan and A. K. Wright, "Effective Flow Analysis for Avoiding Run-Time Checks," Proc. Int. Symp. on Static Analysis, pp. 207-224, 1995.

[40]

N. D. Jones and F. Nielson, "Abstract interpretation: a semantics-based tool for program analysis," Handbook of logic in computer science: semantic modelling, vol. 4, pp. 527-636, 1995.

[41]

H. R. Nielson and F. Nielson, "Infinitary Control Flow Analysis: a Collecting Semantics for Closure Analysis," Symp. on Principles of Programming Languages, pp. 332-345, 1997.

[42]

Parasoft Corporation, "Parasoft Jtest and C++ Test tools," www.parasoft.com.

[43]

IBM Rational, "Rational Purify, PureCoverage and Test RealTime tools," http://www.ibm.com/software/rational.

[44]

Telcordia Corporation, "Telcordia xSuds tool," xsuds.argreenhouse.com.

56

Carleton University TR SCE-05-09

Updated: September 2005

[45]

McCabe Corporation, "McCabe Test and Coverage Server," www.mccabe.com.

[46]

IPL Corporation, "IPL Cantata and Cantata++ tools," www.ipl.com.

[47]

T. Pender, UML Bible: Wiley, 2003.

[48]

V. K. Garg and M. T. Ragunath, "Concurrent regular expressions and their relationship to Petri nets," Theoretical Computer Science, vol. 96, no. 2, pp. 285-304, 1992.

[49]

S. Donatelli and G. Franceschinis, "PSR Methodology: integrating hardware and software models," Proc. Int. Conf. in Application and Theory of Petri Nets, pp. 133-152, 1996.

[50]

K. L. S. Gasser, F. Nielson, and H. R. Nielson, "Systematic realisation of control flow analyses for CML," Proc. Int. Conf. on Functional Programming, pp. 38-51, 1997.

[51]

P. D. Blasio, K. Fisher, and C. Talcott, "A Control-Flow Analysis for a Calculus of Concurrent Objects," IEEE Trans. on Soft. Eng., vol. 26, no. 7, 2000.

[52]

J. Bauer, "A control-flow-analysis for multi-threaded java with security applications," Master’s thesis, Universitat des Saarlandes, 2001, pp. 97.

[53]

D. L. Long and L. A. Clarke, "Task interaction graphs for concurrency analysis," Proc. Int. Conf. on Soft. Eng., pp. 44-52, 1989.

[54]

A. T. Chamillard and L. A. Clarke, "Improving the accuracy of Petri net-based analysis of concurrent programs," Proc. Int. Symp. on Soft. testing and analysis, pp. 24-38, 1996.

[55]

K. Fisher, F. Honsell, and J. C. Mitchell, "A Lambda Calculus of Objects and Method Specialization," Nordic J. of Computing, vol. 1, no. 1, pp. 3-37, 1994.

[56]

N. Heintze, "Set Based Program Analysis," PhD thesis, Carnegie-Mellon University, 1992.

[57]

J. H. Reppy, "Concurrent ML: Design, Application and Semantics," LNCS, vol. 693, pp. 165-198, 1993.

[58]

W. D. Pauw, E. Jensen, N. Mitchell, G. Sevitsky, J. Vlissides, and J. Yang, "Visualizing the Execution of Java Programs," LNCS, pp. 151-162, 2002.

[59]

R. J. Walker, G. C. Murphy, B. Freeman-Benson, D. Wright, D. Swanson, and J. Isaak, "Visualizing Dynamic Software System Information through High-Level Models," Proc. Int. Conf. on ObjectOriented Programming, Systems, Languages and Applications, pp. 271-283, 1998.

[60]

T. Systa, K. Koskimies, and H. Muller, "Shimba - An Environment for Reverse Engineering Java Software Systems," Software - Practice and Experience, vol. 31, no. 4, pp. 371-394, 2001.

[61]

R. Kollmann and M. Gogolla, "Capturing Dynamic Program Behaviour with UML Collaboration Diagrams," Proc. European Conf. on Soft. Maint. and Reeng., pp. 58-67, 2001.

[62]

R. Oechsle and T. Schmitt, "JAVAVIS: Automatic Program Visualization with Object and Sequence Diagrams Using the Java Debug Interface (JDI)," Int. Seminar on Soft. Visualization, pp. 176-190, 2001.

[63]

Borland Corporation, "Together," www.borland.com/together.

[64]

IBM Rational, "Rational Test RealTime," www-306.ibm.com/software/awdtools/test/realtime.

[65]

L. Briand, Y. Labiche, and Y. Miao, "Towards the Reverse Engineering of UML Sequence Diagrams," Proc. Conf. on Reverse Eng., pp. 57-66, 2003.

57

Carleton University TR SCE-05-09

Updated: September 2005

[66]

P. Tonella and A. Potrich, "Reverse Engineering of the Interaction Diagrams from C++ Code," Proc. Int. Conf. on Soft. Maint., pp. 159-168, 2003.

[67]

IBM Rational, "Rational Rose RealTime," http://www.ibm.com/software/rational.

[68]

OMG, "UML Profile for Schedulability, Performance, and Time (v1.0)," 2003.

[69]

W. Brauer, W. Reisig, and G. R. (eds.), "Petri nets, central models and their properties," in LNCS, vol. 254, 1987.

[70]

J. Zhang and S. C. Cheung, "Automated Test Case Generation for the Stress Testing of Multimedia Systems," Software Practice & Experience, vol. 32, no. 15, pp. 1411-1435, 2002.

[71]

OMG, "UML 2.0 OCL Draft Adopted Specification," 2003.

[72]

J. Warmer and A. Kleppe, The Object Constraint Language: Getting Your Models Ready for MDA: Addison Wesley, 2003.

[73]

B. Bruegge and A. H. Dutoit, Object-Oriented Software Engineering: Using UML, Patterns, and Java, 2nd Edition ed: Prentice Hall, 2003.

58