Building Stochastic Petri Net models for the veriﬁcation of complex software systems

(1)

UNIVERSIT ` A DEGLI STUDI DI TORINO

Dipartimento di Informatica

C.so Svizzera, 185 - 10149 Torino (Italia)

DOTTORATO DI RICERCA IN INFORMATICA (CICLO XV)

TITOLO DELLA TESI

Building Stochastic Petri Net models for the verification of complex software systems

TESI PRESENTATA DA:

Simona Bernardi

TUTOR:

Prof.ssa Susanna Donatelli

COORDINATORE DEL CICLO:

Prof. Piero Torasso

ANNI ACCADEMICI:

’99/’00 - ’00/’01 - ’01/’02

(2)

I would like to thank Gianfranco Balbo, who convinced me to follow this “way” and Susanna Donatelli, who has been supported me from the beginning. I thank also Javier Campos, Giovanna Dondossola, An- dras Horváth, Juan López-Grao and José Merseguer for their contribution to this research work, Giuseppe Berio for the clarifications about UML, Massimiliano De Pierro, Roberto Esposito and Fabrizio Nunnari for their technical help in a critical moment.

The work presented in this thesis has been possible thanks to the fi- nancial support of the EEC project DepAuDE and of the “Progetto di Azione Integrata Italia-Spagna”.

Finally, I am grateful to my mother and my sister, the most “dependable”

people that I know, for their daily support.

Simona Bernardi

2

(3)

Introduction

The work presented in this thesis is focused on the construction of stochastic models for the verification of non-functional properties of complex software systems in the early stages of the software development process.

As it has been emphasized in [79], verification of non-functional properties should be integrated early in the software development process (i.e., in the stages of requirement analysis, functional architecture specification and preliminary design) in order to identify ambiguities in the requirement definition, to determine the feasibility of the proposed system functionalities in terms of costs and of fulfillment of the fixed requirements and to detect errors in the design specifications that, if not identified and corrected from the beginning, may have a drastic impact on the cost and time of the subsequent phases.

Modeling plays a fundamental role in the early verification since measurements of the final system are not yet available. However, the modeling activity at the pre-implementation stages is not an easy task since information on the system are limited, uncertainties may introduce the risk of model omissions that can have serious consequences on the system assessment, and different types of models are often required to assess different aspects of the system .

In the context of performance evaluation of software systems, the Software Performance Engineering (SPE) method, introduced by C.Smith [78], has tackled these problems by proposing a general model-based approach to be applied in each stage of the software life-cycle and by providing principles for creating responsive software systems as well as techniques for gathering data, constructing and evaluating performance models.

In particular the general model-based approach proposed by SPE, for an early assessment of system responsive- ness and throughput, consists of the following steps: 1) capture performance requirements, understand the system functions and rates of operations; 2) understand the structure of the system and develop a model representing its

“performance” abstraction; 3) capture the resource requirements and insert them as model parameters; 4) solve the model and compare the results to the requirements, and, finally, 5) interpret the predictions to suggest changes if needed.

Beside performance, another important non-functional aspect of software systems that needs to be early verified

5

(6)

is the dependability, that is the ability of a system to avoid failures that are more frequent (or more severe) and failure durations that are longer than is acceptable to the users [53]. Dependability is a wide concept that encompasses several basic properties of the system (called “attributes of dependability” [52, 53]), such as: availability, i.e., the readiness to deliver a correct service, reliability, i.e., the continuity of correct service delivery, safety, i.e., the guarantee of the absence of catastrophic consequences on the users and the environment, confidentiality, i.e., the guarantee of the absence of unauthorized disclosure of information, integrity, i.e., the guarantee of the absence of improper alterations of information, and maintainability, i.e., the ability to undergo repairs and modifications.

Dependability models differs from performance models since changes in the structure of the system due to the presence of faults, errors and failures and their relationships have to be represented and, possibly, fault-tolerance and repair mechanisms have to be included [32, 49]. Although different type of models are required, the general dependability analysis procedure, as suggested by the International Electrotechnical Commission (IEC) [21] is similar to the model-based approach established by SPE. Moreover, some of the modeling formalisms and related analysis techniques adopted for the system verification can be used for both performance and dependability assessment.

Nowadays, among the modeling languages used for the specification of complex software systems, Unified Modeling Language (UML) [64] has found the major agreement both in the software engineering community and in the industry.

UML is a graphical semi-formal language, developed by the Object Management Group (OMG), based on the object-oriented paradigm; it provides several diagrams that allow to represent different aspects of the systems, such as its functionalities, its static structure, the dynamic behavior of each system components and their interactions, and physical implementation details.

The main reasons for which UML has become a standard notation can be synthesized as follows: 1) it is a general purpose language, then it can be used for the specification of a wide range of software systems; 2) its graphical notations are intuitive, then it is well accepted by system developers, traditionally skeptics against formal methods, and it facilitates the exchange of information among the people involved in software development process, finally 3) there are lot of commercial tools [63] supporting UML notations as well as code generation from UML models.

During these last five years, one of the major challenges of the researchers working on modeling of software systems has been to produce, more or less automatically and systematically, formal models from UML-based system descriptions, so there is a lot of literature on the topic. The works are mainly addressed to the derivation of models from UML design specifications for either the verification of correctness [15, 54, 55, 56, 76] or the performance assessment. In particular on deriving performance models from software architecture specifications, a good survey of the different approaches can be found in [4]: most of the mentioned works use an UML-based description for the system and comply with the SPE method.

(7)

CHAPTER 1. INTRODUCTION 7 For example, in [22] Sequence Diagrams are used in conjunction with Use Case and Deployment Diagrams inside a methodological framework to obtain extended queuing network models. Use Case Diagram is enriched with branching probabilities to derive the probability of execution of the set of Sequence Diagrams associated to each use case: this leads to the definition of the workload of the performance model. An algorithm is given to obtain automatically an execution graph from Sequence Diagrams and the use of Deployment Diagrams allows to represent hardware restrictions. The three types of diagrams are used also in [23] to derive a reliability formal model: Use Case Diagrams are annotated as specified in [22] to derive the probability of execution of a given scenario represented by a Sequence Diagram. Sequence Diagrams are used instead to identify the busy periods of each interacting component that allow to estimate the probability of failure of each component in each scenario.

Finally, Deployment Diagrams are annotated with the probabilities of failure of the connectors among sites that allow to consider the communication failures in the final model. These information are used to build a formula for the rate of failure of the whole system. The reliability of the system is estimated by using the probability distribution of the system failure rate that is obtained through simulation generating random observations from the beta distributions of the failure probabilities of components and connectors.

In [50, 72] instead, two similar approaches are exemplified to obtain from combined UML behavioral diagrams Stochastic Petri Net (SPN) models and Stochastic Process Algebra (SPA) models, respectively. The proposed combined diagram consists of a Collaboration Diagram with StateCharts representing the behavior of the objects taking part in the collaboration. The basic idea is to translate each StateChart into a formal model and then to combine them to obtain a unique final analyzable model. While in [72] the composition of the SPA models is well stated through the use of PEPA [41] cooperation primitives, in [50] the merging procedure of SPN models is not formally defined.

As observed in [73] additional information on timings and branching probabilities are required to assess quantitative properties by using UML-based description of the system. Different proposals have been made on how to annotate UML diagrams with timing and probability specifications [12, 22, 60, 25, 38, 58]. These efforts contributed to the definition of a standard UML Profile for Schedulability, Performance and Time Specification [65].

The major problems researchers had to face to automatically derive formal models from UML specifications have been 1) the lack of a formal semantics of UML, since specific choices were needed to solve ambiguities (especially in UML behavioral models) and 2) consistency of information when different UML diagrams were considered in the translation.

At the same time, these issues have been tackled by other research lines: a number of attempts to provide formal semantics to UML have been made [89], in particular a relevant contribution to clarify basic concepts has been given by the precise UML working group [39].

Consistency problem is extensively treated in [84], where a method for the verification of consistency and completeness of UML specifications based on Class Diagrams, Sequence Diagrams and Statecharts is proposed.

(8)

Paper [71] proposes instead a method to rebuild consistent Activity Diagrams from a set of Sequence Diagrams by means of graph transformations.

For the best of our knowledge, most of the works on the derivation of formal models from UML for the assessment of non-functional properties have as a starting point the specifications of the system given in the (preliminary) design phase; as a consequence, the construction of the analyzable models is not driven by the metrics that need to be computed and compared against the requirements during the verification activities. Moreover, these efforts have been mainly concentrated on correctness performance and schedulability aspects of software systems. An interesting work on generation of dependability formal models from UML high level models is presented in [12], where a two step transformation is proposed. In the first step, UML specification, consisting of use case, class, object and deployment diagrams, are transformed into an intermediate model (i.e., an hyper-graph) that allows to extract the relevant dependability information, such as the fault activation, the fault propagation, the derived failures in the system, the repair process, and the measure of interest to be verified. In the second step of the transformation a modular approach is adopted: a set of timed Petri Net basic subnets are generated from each element of the intermediate model that capture the internal state of each system component, their failure and repair processes: these subnets can be further refined when more detailed information on the system are available. Finally, the whole Petri Net model is obtained by composing the basic subnets over interface places and transitions.

In this thesis we present our contributions to the derivation of SPN models from UML specification for the quantitative assessment of complex software systems in the early stages of the software life cycle.

A first contribution is related to the development of a methodological approach to the collection, definition and analysis of dependability requirements and fault-tolerance strategies that has been devised within the project DepAuDE¹.

DepAuDE methodology addresses the domain of automation systems and complies with the recommendation given by the IEC [21] of integrating different methods during the dependability analysis process. Automation systems are an example of complex software distributed systems in which different non-functional aspects have to be verified at the early stages of the software life-cycle, such as dependability and performance requirements and soft real-time constraints [88].

Three different and complementary modeling formalisms are used in the DepAuDE methodology: UML Class Diagrams, a static paradigm, TRIO logic and Stochastic Petri Nets, an operational paradigm. The thesis contribution is on the use of UML Class Diagrams and Stochastic Petri Nets.

Class Diagrams (CDs) are meant as a support for the requirement collection and for structuring but they can be used also for reviewing the completeness of already available requirement specifications. Being inspired by the work on patterns in [35, 33], we have proposed a set of CDs, i.e., the generic CD scheme, as a dependability

1IST 25434 DepAuDE EEC project

(9)

CHAPTER 1. INTRODUCTION 9 and fault-tolerance strategy analysis pattern. Together with the proposed generic CD scheme, we have provided guidelines and rules on how to adapt it to a specific application.

The role of Stochastic Petri Nets within the methodology is to support dependability and performance analysis and the design validation through modeling. We have provided a set of predefined reusable SPN models (i.e., SPN library), a suggested structure of interaction of the model components, guidelines on how extract information from Class Diagrams of the application-specific scheme to support the construction of SPN models by following a compositional approach.

CDs being static in nature, the set up of a SPN model suitable to be analyzed to get dependability/performance results requires that the information derived from the CDs are integrated with information coming from the design.

Then, at the same time, we have tackled the issue of deriving automatically SPN models from the UML behavioral specifications, represented by UML StateCharts and Sequence Diagrams. The automatic translation of UML StateCharts and Sequence Diagrams into Generalized Stochastic Petri Net (GSPN) models is the second main contribution presented in this thesis.

The approach adopted for the automatic derivation of GSPN models from the two UML behavioral notations is compositional and it consists in translating the basic concepts as defined in the metamodels of the UML State Machines and Collaborations packages that describe informally the semantics underlying the Statecharts and the Sequence Diagrams, respectively. So that, even though each UML notation has been translated in a separate way, the reference to the UML metamodels accounts for the relations that exist among a set of Statecharts representing the behavior of a set of objects and Sequence Diagrams, representing their interactions, since the two metamodels contain common classes. Assuming that a software system is specified by a set of Statecharts and that a Sequence Diagram is used to emphasize specific a pattern of interaction among StateCharts, we have proposed a joint analysis of the translated UML diagrams. Such analysis allows to verify the consistency of the information contained in the StateCharts and in the Sequence Diagram and to evaluate from a stochastic point of view those behaviors of the system that are consistent with the pattern of interaction described by the Sequence Diagram.

Moreover, since the approach is compositional, the GSPN models obtained from the automatic translations of StateCharts and Sequence Diagrams, can be easily reused as component models for completing the setting of the SPN models constructed by following the DepAuDE methodology and used for the quantitative verification of automation systems.

Structure of the thesis The thesis is structured in two main parts: Part I, after giving an overview of the DepAuDE methodology, is devoted to the description of the use of Class Diagrams and Stochastic Petri Nets within the DepAuDE methodology. In particular, the generic CD scheme, proposed as dependability and fault- tolerance analysis pattern, and the guidelines supporting the analyst in its customization for a specific application are described in Chapter 3. Chapter 4 is instead devoted to the description of the role of SPN in the methodology:

(10)

it is focused on the structuring of the SPN model, on the derivation of a library of predefined GSPN models from the generic CD scheme and on the issues of extracting information from the application specific CD scheme to get an analyzable SPN model.

The automatic translation of UML behavioral specifications (StateCharts and Sequence Diagrams) into GSPN models is dealt in Part II of the thesis. An introduction of the approach adopted is given at the beginning of this part together with a description of the translation of basic concepts of UML StateCharts. The translation of Se- quence Diagrams in GSPN models is described in Chapter 5. Chapter 6 is dedicated to the description of the joint analysis of the GSPN models derived from the translation of a set of StateCharts, modeling the system objects behavior, and of a Sequence Diagram, representing a possible interaction among the objects. The last section of this chapter (Section 6.5) deals with the issue concerning the insertion of the GSPN models derived from the automatic translations of UML behavioral specifications (StateCharts) within the layered structure proposed in Section 4.1 for the setting of SPN models of automation systems.

Part I is preceded by an introductory chapter (Chapter 2) devoted to the description of the main features of the modeling formalisms used in this thesis, i.e., Unified Modeling Language and Petri Nets.

Finally, in Chapter 7 comparisons with the other works of the literature and open research issues are given.

Thesis work context The work presented in the first part of the thesis has been developed within the EEC project DepAuDE. DepAuDE (Dependability for embedded automation systems in dynamic environments with intra-site and inter-site distribution aspects) [26] is a ongoing EEC project, started in January 2001 and ending on March 2003, aimed at developing a methodology and an architecture to improve dependability for distributed embedded automation systems with both IP (inter-site) and dedicated (intra-site) connections. Example of target applications of DepAuDE are the command and control of electrical energy transport and distribution, health care applications based on distributed embedded systems and remotely controlled and maintained airfield lighting control system with sensor feedback. To improve dependability of automation systems DepAuDE provides, from an operational point of view, a framework consisting of 1) a library of basic fault-tolerance software solutions, implemented as parametric functions to be adaptable to the specific application; 2) a distributed application called

“backbone” that maintains information on the status of the controlled automation system in a replicated database and coordinates the fault-tolerance actions at run-time via the interpretation of user-defined recovery strategies;

and 3) an high-level configuration and recovery language (ARIEL) that is used to configure the basic tools and to define recovery strategies.

The methodology developed in DepAuDE is meant as a support for the users of the framework to identify the best fault-tolerance solutions for their automation systems, starting from the system dependability requirements, and to use the modeling to drive the development and the assessment of the identified solutions. Within the project we have taken care of the methodological aspects of DepAuDE in collaboration with CESI Automation

& Information Technology, one of the industrial partners of the project. In particular, the definition of the CD

(11)

CHAPTER 1. INTRODUCTION 11 scheme and of the customization process are the result of a joint work with CESI that has provided the knowledge of the automation system domain as well as the case study of the automation system for primary substation of electricity distribution network (PSAS). Concerning the other two formalisms used in the methodology, CESI has contributed in defining the role of TRIO and its usage for analyzing dependability and schedulability aspects in a formal logic context [30], while we have taken care of establishing the role of SPNs.

The work on the translation of UML behavioral specifications in GSPNs, presented in the second part of the thesis, has been carried out in collaboration with our spanish colleagues of the group of Formal Methods of the University of Zaragoza and it has been supported by the project “Azione Integrata Italia-Spagna” co-financed by the Italian “Ministero dell’Istruzione, dell’Universit`a e della Ricerca” and by the Spanish “Ministerio de Educaci´on y Ciencia”. In particular, the spanish group has taken care of the translation of StateCharts, that has been extensively presented in the work of PhD thesis of Merseguer J. [59]. They have also implemented a prototype of software performance tool supporting the graphical notation of Activity Diagrams, a special case of StateCharts, and their translation into GSPNs [57]. We have charged, instead, with the translation of Sequence diagrams in GSPNs and with the definition of a possible joint analysis of the translated StateCharts and Sequence Diagrams.

(12)

Background

This chapter is devoted to the introduction of the modeling formalisms that have been used in this thesis. In Section 2.1 we will give an overview of UML by describing only the relevant features that are useful for the comprehension of both the methodological part (Part I) and the part dedicated to the automatic translation of UML notations into Petri Nets (part II).

In Section 2.2 we describe Petri Nets, focusing on Stochastic Petri nets, in particular Generalized Stochastic Petri Nets (GSPNs) and Stochastic Well Formed Nets (SWNs), on their labeling and on net composition opera- tors.

2.1 UML semi-formalism

The Unified Modeling Language (UML) is a general purpose visual modeling language widely used in the software development process for the specification of systems based on the object-oriented paradigm. It is considered the successor of several Object-Oriented Analysis and Design (OOA&D) methodologies developed between the end of ’80s and the beginning of ’90s. In particular, it results from the fusion of the concepts derived from the Booch, the OMT (Object Modeling Technique) and the OOSE (Object Oriented Software Engineering) methods proposed by G. Booch, J. Rumbaugh and I. Jacobson, respectively. Furthermore, other new concepts have been added in UML, such as the extension mechanisms (stereotypes, tagged values, constraints).

The OMG (Object Management Group) takes care of the standardization process of UML since 1997 when the version 1.1 was issued. The current release is UML version 1.4, that has been approved on September 2001: the work of translation of a subset of UML diagrams into Petri Nets that is dealt in the second part of this thesis refers to this release (see [64]). However, the work of standardization continues and the next version (2.0) is expected for the beginning of 2003.

12

(13)

CHAPTER 2. BACKGROUND 13

1..*

0..* 1 1..*

1 Customer

name address

Order date status calcTax calcTotal

Payment

amount

OrderDetail quantity taxStatus calcSubTotal

line_item

1 0..*

1

Item description getPriceForQuantity getWeight

Cash Check

Credit

order_#

paid_by abstract class

aggregation association qualifier

class name attributes

operations

multiplicities bidirectional

association

one-way association

generalization

rolename sale

bankID expDate

authorized

Figure 2.1: Example of UML Class Diagram.

2.1.1 The UML graphical notations

UML provides several types of diagrams which allow to capture different aspects and views of the system. The semantics of UML diagrams is defined by the metamodel layer that is described in the next section. A detailed description of each UML notation is out of the scope of this chapter. We will give, instead, a brief description of them, lingering on those diagrams and their corresponding features that have been used in the thesis.

Class Diagram Class Diagrams (CDs) describe the static structure of the system, i.e., in terms of classes and their relationships. This UML notation comes from a melding of OMT, Booch and class diagrams of most other object-oriented methods. The Class Diagram depicted in Figure 2.1 models for example a customer order. A class is a description of a set of objects with similar structure, behavior, relations and semantics. At run time execution objects as instances of classes are used and all objects of a class share the same list of attributes and operations. The scope of an attribute can be at instance level, in this case each object holds its own value for the attribute, or at class level, in this case there is just one value of the attribute for the entire class: class-scope attributes are shown underlined while instance-scope attributes are shown not marked. A class, e.g., class Order in the Figure 2.1, is drawn as a rectangle in which the upper part contains the class name. Names of abstract classes, i.e., not instantiable classes, are written in italics (e.g., class Payment). In case the attributes and the operations of the class are shown as well, the rectangle is divided into three parts: the upper part contains the

(14)

class name, the central part contains the (partial) list of the attributes and the bottom part contains the (partial) list of the operations. Structural relations between two classes are specified by associations and generalizations.

In particular, a binary association between two classes is represented by a line connecting the classes and an optional association name, e.g., association sale depicted in Figure 2.1 represents a binary association between classes Customer and Order.

The UML metamodel distinguishes the association itself from its ends: binary associations have exactly two association ends. Different adornments specifying association properties, such as navigability, aggregation, role names, qualifier and multiplicities, may be attached to the association ends.

An association is navigable if, given an object at one end, it is possible to get to objects at the other end directly, usually because of the existence in the source object of some references to target objects. Navigability in one direction is graphically represented with an arrowhead attached to the end of the line representing the association, e.g., like association paid by in Figure 2.1; while the simple line without any arrows represents the navigability in both directions.

A special kind of binary association is the aggregation that represents a part-of relationship. There are two forms of aggregation: 1) a weaker form of aggregation, whose intended meaning is to distinguish the whole from a part and that is graphically denoted as a diamond attached to the association end closer to the class representing the whole. 2) A stronger form of aggregation, i.e., the composition, expressing that the part is strongly owned by the composite and may not be part of any other object. Composition association is graphically depicted as a filled diamond attached to the association end closer to the composite class.

Another adornment that may be attached to an association end is the rolename that indicates the role played by the class attached to the end of the path near the rolename. For example in Figure 2.1 the rolename line item, attached to an association end of the aggregation between classes Order and OrderDetail, allows to represent an order as an aggregation of lines, each line specifying in detail each ordered item. The rolename represents a pseudo-attribute of the source class and it provides a name for traversing from a source instance across the association to the target instance(s), e.g., by using the dotted syntax we can represent an order o∈ Order as a set of order details o.line item ={od1, ..., od_n}.

A qualifier is an attribute of an association, whose values allow to partition the set of instances associated with an instance across the association. A qualifier is shown as a small rectangle attached to the end of an association and close to the class that it connects to, see in Figure 2.1 the qualifier order #. An instance of the source class together with a value of the qualifier select a partition in the set of the target instances on the other end of the association.

An association end may be characterized by multiplicity specifying the number of target instances that may be associated with a source instance. The multiplicity is a (set of) range(s) of non negative integers denoted as lower-bound..upper-bound. If a single integer value is specified, then the integer range contains exactly the single integer value. In addition, the star character (“*”) may be used either for the upper bound to denote an unlimited

(15)

CHAPTER 2. BACKGROUND 15 upper bound or alone with the same meaning of 0..*. For example, in Figure 2.1 an order detail specifies a single item and, vice-versa, a single item can be mentioned in zero or more orders.

Classes of a CD can be related by a generalization/specialization relationship which is used to model inheritance between classes. The subclass inherits all the properties of the superclass, i.e., attributes, operations, associations.

Moreover, additional properties can be specified in the subclass. Generalization is graphically represented by a solid-line path from the subclass to the superclass with a large hollow triangle at the end of the path, close to the superclass; e.g., in the CD of Figure 2.1 classes Credit, Cash and Check are subclasses of the class Payment.

Interaction diagrams There are two forms of Interaction diagrams: Collaboration Diagrams and Sequence Diagrams (SDs). A Collaboration Diagram shows an interaction among a set of participants and it is used to emphasize the roles played by the participants and their relationships. A SD shows instead an explicit sequence of communications among the participants of an interaction. Both the types of Interaction Diagrams convey the same underlying information described by the Collaboration metamodel and they can be used either at specifi- cation level, in which participants are generic objects of classes, or at instance level, in which participants are objects with its own identities.

SDs are more suitable for real-time specifications and for representation of complex scenarios in which it is important to represent explicitly the temporal aspects. They have been used in a variety of Object-Oriented methods under the names of interaction diagrams, message trace diagrams, event trace diagrams, and, in general, they can be considered as successors of message sequence charts [47]. A SD shows an interaction arranged in time sequence: usually, the time is represented by the vertical axis of the SD and it proceeds downward while the participants are represented by the horizontal dimension. In Figure 2.2 an example of SD modeling a possible interaction among a set of tasks performing a distributed synchronization is depicted. Each object participating to the interaction modeled by a SD is represented by a vertical dashed line called lifeline together with a rectangular box (i.e, object symbol) superscribed with the string: Objectname ‘/’ ClassifierRolename ‘:’ Classifiername, where Objectname is name of the object, ClassifierRolename is the name of the role played by the object in the interaction and, finally, Classifiername is the name of the class the object belongs to. In general, it is not required a complete specification of the string written above for each participating object. For example, the name of the role can be omitted if there is only one role to be played by the objects of a given class, as well as the name of the object when it represents a generic object of a given class¹. In Figure 2.2 the participants to the interaction are: a generic object belonging to the Synchronizer class, the three tasks task1, task2, task3 belonging to classes TK node1, TK node2, TK node3, respectively, and a generic object aAgent of class Agent. The task1 plays the role of Master while task2 and task3 play the role of Slave. When the participating objects interact also with an external environment then the latter can be included into the SD and it is represented by an actor symbol.

A message exchanged between two objects in the SD is graphically represented by an arrow from the sender’s

1A generic object can also be named as “aClass”, where “Class” is the name of the class it belongs to.

(16)

:Synchronizer

task1/

Master:TK_node1

task2/

Slave:TK_node2

init

2.a:include

object class role

actor symbol

synchronous action

asynchronous action

timed message branching:

concurrency

branching:

mutual exclusion iteration

conditional message create

action

return action

destroy action

ready

ready 2.b:include

2.c:include

synchronized

task3/

Slave:TK_node3

operation

signal

aAgent:Agent

m10:not_avail(#3)

ready ready

synchronized

[failed=true]restart

[failed=false]exclude 1..n

Time

generic object

Figure 2.2: Example of UML Sequence Diagram.

to the receiver’s lifeline. Depending on the type of action performed by the sender that caused the message to be sent the arrow corresponding to the message can be of different type. Messages caused by synchronous actions are drawn as filled solid arrowhead arrows, while messages caused by asynchronous actions are drawn as stick arrowhead arrows. Among the latter, messages representing return from procedure calls are further distinguished and depicted as dashed arrows. Moreover, message arrows can be either drawn horizontally, indicating the time required to send the message is “atomic” (instantaneous message), or slanted downward, indicating that the message requires some time to arrive (timed message). If an object is created in consequence of the execution of a create action, then the creation message arrow points to the created object symbol (e.g., the message labeled as init in Figure 2.2); whilst if an object is destroyed in consequence of the execution of a destroy action then the destruction message arrow is followed by a large “X” along the lifeline of the destroyed object (e.g., the message labeled as exclude).

Message arrows are labeled with the name of the operation to be invoked or with the name of the signal to be raised. The arrow may also be labeled with a sequence expression, consisting of a dot-separated list of

(17)

CHAPTER 2. BACKGROUND 17

entry/continue do/activity recv_msg/send_ack

/initiate

/Iamalive reset

reconfigure [down=node]

fault

Application

heartbeat

setup

/notify

termination

Watchdog

compute

error wait

reset [down=application] unused

paused

count

expired

do/counting_down exit/timeout

do/configure heartbeat

start initial

pseudostate

simple state

trigger entry action

exit action doActivity action

outgoing transition internal transition

effect deferred event

guard

Figure 2.3: Example of UML Statechart.

sequence terms followed by a colon, to show the sequence of the messages in the overall interaction and/or condition/iteration expression.

Sequence numbers/names are often omitted in SDs, as the physical location of the arrow shows the relative sequences; however they are useful for example to emphasize concurrent messages as is the case of the branch- ing messages labeled as 2.a: include, 2.b: include and 2.c: include characterized by the same sequence number and by concurrent threads of control. Branching points are shown by multiple message arrows leaving a single point: branch construct may represent either concurrency or conditionality depending on the labels attached to the messages belonging to the branch. The branch depicted in Figure 2.2, consisting of the two messages la- beled as [failed=true]restart and [failed=false]exclude, represents conditionality being the conditional messages characterized by mutual exclusive conditions.

A set of arrows in a SD can be enclosed in a rectangle and labeled with an iteration clause: the iteration indicates that the set of messages belonging to the iteration can occur multiple times. UML does not prescribe any format neither for iteration clauses nor for conditional clauses, they can be expressed in pseudo-code or in an actual programming language, e.g., in Figure 2.2 the iteration clause is equal to 1..n meaning that the sequence of messages enclosed in the rectangle is repeated n times. Note that this specification may correspond to either a while-true statement or a for statement depending on meaning assigned by the modeler to n.

(18)

StateCharts Statecharts (SCs) are the graphical representation of UML State Machines, they are basically Harel [40] statecharts with minor modification. The execution of a state machine is based on the run-to- completion step algorithm in which an event instance can only be dequeued and dispatched if the processing of the previous current event instance is fully completed. In particular, a state machine is characterized by the following components: an event queue, that holds incoming event instances until they are dispatched; an event dispatch mechanism, that selects and dequeues event instances from the event queue and, finally, an event pro- cessor that executes dispatched events.

SCs are used to model the behavior of class objects and they describe possible sequences of states and ac- tions through which objects can proceed during their lifetimes as a result of reacting to occurrence of discrete events (e.g., signals, operation invocations)[64]. An example of two statecharts representing the behavior of an application process and its error detector (i.e., the watchdog mechanism), are depicted in Figure 2.3.

A SC basically consists of states and transitions. States represent situations during the life of the object in which either it satisfies some condition, or it performs some action or it waits for some event to occur. A simple state, such as states wait, compute, error in SC Application and states unused, paused, count and expired in SC Watchdog of Figure 2.3, is drawn as a rectangle with rounded corners subdivided in two compartments separated by a horizontal line: the upper part contains the name of the state, the lower part may contain actions, that are performed while the represented object is in the state, deferred events and internal transitions. Initial states are instead special states (pseudo-states), and they are drawn as a small solid filled circle.

Actions within a state are denoted as action label / action expression where action label allows to determine whether the action specified by action espression is an entry action or a do action or an exit action. Entry actions are performed upon entry to the state (e.g., action continue in state compute in SC Application), do actions correspond to an ongoing activity performed as long as the object is in the state or until the computation specified by the action is completed (e.g., action counting down in state count of SC Watchdog), exit actions are instead performed upon exit from the state (e.g., action timeout in state count of SC Watchdog).

The events received by an object are results of actions either carried out by the object itself or by other objects interacting with the former. In particular, deferred events are those events that do not cause a change of the state:

they are simply retained to be processed subsequently. For example, in the SC Watchdog the event heartbeat in state paused is a deferred event, meaning that while the watchdog is in a pause state potentially can consume an heartbeat event but is not able to process it so that the event is retained to be processed when the watchdog is in another state.

A transition indicates that specific actions will be performed when a specified event occurs provided that a certain condition is satisfied. In general in a SC, a transition is labeled as event name ( parameter-list ) [ guard- condition ] / action expression. A transition is triggered by at most one event that represents the reception of either a signal or a request to invoke a specific operation, in this latter case a list of parameters are associated that conform to the operation’s list of parameters. The guard provides control over the firing of the transition:

(19)

CHAPTER 2. BACKGROUND 19 it is represented as boolean expression and, when not explicitly specified, is assumed always true. When the transition fires, an action (or a sequence of actions) may be performed. When the transition has not an explicit trigger event is called completion transition and it fires only after all the events and actions present in the current state are processed and completed.

There are two main types of transitions: internal and outgoing. Internal transitions, as deferred events, do not cause a change of state when fire but, unlike deferred events, the event that triggers the transition is processed and, when specified, the associated action(s) are executed.

Firing of an outgoing transition causes an exit from the state and an entry into the target state, possibly the source state itself in case of self-loop transition. Self-loop transitions are different from internal transitions:

indeed, while the firing of the formers cause the execution of entry and exit actions, the firing of an internal transition do not cause neither an entry in the state or an exit from the state.

StateCharts may represent other important constructs, such as synchronization states, stub states, composite states, sub-machine states and pseudo-states that are mainly meant for a hierarchical definition of the underlying state machines, and for introducing concurrency inside a state machine or between different state machines. We omit to describe such features, since we have not dealt with them explicitly, while we focus on the relationships between StateCharts and Class Diagrams and between Statecharts and Sequence Diagrams for a better under- standing of the second part of the thesis devoted to the automatic translation of UML Sequence Diagrams into Generalized Stochastic Petri Nets for their combined use with the translated StateCharts. StateCharts are related to both Class Diagrams and Sequence Diagrams. A CD defines attributes, operations and relations for a class of objects: this static structure is fundamental for the inter-object behavior (represented by Sequence Diagrams) and for the intra-object behavior (represented by StateCharts).

Let us assume to have a set of StateCharts representing interacting objects; among the actions executed by an object there exist some actions that invoke operations of the called object or that generate signals that can be perceived by other objects. The invocation of an operation (or the generation of a signal) provokes one or more event occurrences that are perceived by other objects.

The interactions between StateCharts, and the relationships between StateCharts and Class Diagrams, can be exemplified by looking at two SCs of Figure 2.3: the application, whose behavior is modeled by the SC Appli- cation, and the watchdog, whose behavior is modeled by the SC Watchdog, are two communicating processes.

Both the application and the watchdog can be considered as two objects belonging to two different classes, e.g., AP and WD respectively. In particular, let us assume class WD be characterized by an attribute timer and by two operations init(timervalue) and confirm(). A first type of interaction between the two objects occurs when, being both the application and the watchdog in their corresponding initial states wait and unused, the application initializes the watchdog setting up the watchdog timer. This interaction is carried out through the call action initiate that invokes the operation init(timervalue) in order to set the timer attribute to the value timervalue. The invocation of such operation provokes the occurrence of a setup event in the watchdog and the processing of such

(20)

event brings the watchdog in the paused state. Other interactions between the application and the watchdog occur through either the causal chain: action continue - operation confirm() - event start, when the application confirms the settings and the watchdog starts its count-down to expiration, or the causal chain: action Iamalive - signal kick - event heartbeat, when the application sends an “Iamalive” to the watchdog in order to reset its timer to the initial value.

On the other hand, a message exchanged between two objects in a SD is caused by the execution of an action (e.g., a call action when an operation is invoked, a send action when a signal is generated), that causes the reception of an event in the receiver object. Looking at the SCs of Figure 2.3 we can represent their interactions with a SD showing the sequence of messages, generated by either call actions or send actions, exchanged between the application and the watchdog.

Use Cases Use Case diagrams describe the system’s functionality, that is what a system does from the point of view of an external observer. They are closely connected to scenarios, i.e., examples of what happens when users interact with the system being modeled. Although Use Cases are typically used in the phase of requirement specification of a software system, we have decided to not consider them in the DepAuDE methodology, since we think that they are more suitable for the description of the functional requirements of a system. Use Cases can also be used in the later stages of the software life-cycle, in particular during the validation and verification activities for test cases generation: for this reason their relationships with other UML notations, in particular Sequence Diagrams, and their role played within the dependability analysis will be subject of future research studies.

Activity Diagrams An Activity Diagram (AD) is a special case of StateChart in which most of the states are actions or sub-activity states and most of the transitions are triggered by completion of the actions or sub- activities in the source states. A translation of ADs into Generalized Stochastic Petri Nets has been proposed in [57] by following the same approach adopted for the translation of SCs and SDs described in part II of the thesis.

Moreover, a prototype of software performance tool supporting AD graphical notation and its translation into GSPNs has been implemented: it will be our starting point for a future implementation of the translation of SDs.

Implementation Diagrams Implementation diagrams show aspects of physical implementation of the system.

There are two forms of implementation diagrams: Component Diagrams, that allow to represent the structure of the system components, and Deployment Diagrams, that allow to specify the physical configurations at run-time of software and hardware. From the point of view of quantitative evaluation of the system, deployment diagrams can be used as suggested in [22], for example, to specify the features of communication means used by the interacting components (e.g., network bandwidth) that have an impact on the communication delays. Since in the DepAuDE methodology we have not considered these diagrams, because we think that they are more suitable to

(21)

CHAPTER 2. BACKGROUND 21 be used in the later stages of the software life-cycle when a more detailed design of the system or a prototype is available, we have specified communication features of the system by using the Class Diagram notation.

Packages Packages allow to organize large UML models in order to reduce their complexity, to separate domains and to enforce a cleaner structure. A package may contain subordinated packages as well as other UML model elements. Moreover, model elements inside a package can be related with other model elements defined in other packages, in this case there is a dependency between the packages. Dependency relationships can be drawn automatically by most of the UML tools and packages can usually be exported/imported between models.

Within the DepAuDE methodology, packages allow to give a structure to the analysis pattern consisting of a set of CDs and to define an order of customization of the pattern to the specific application.

2.1.2 The UML semantics

The UML architecture is based on a metamodel structure, consisting of four layers: user object, model, meta- model and meta-metamodel. In particular, the metamodel layer provides the semantics of each UML notation.

The metamodel layer is described in a semi-formal manner as a combination of graphical notation, natural language (English) and formal language. The graphical notation is used to define the abstract syntax and actually consists of a set of UML Class Diagrams.

To avoid confusion between Class Diagrams used to represent specific systems and Class Diagrams used to specify the abstract syntax of the UML notation we will refer to the latter as metamodels.

The formal language - Object Constraint Language (OCL) - together with the natural language are used instead to define the Well-formedness rules which specify constraints over attributes and associations defined in the metamodels. The natural language is also used to describe in detail the meaning of the constructs, i.e., metaclasses and their associations, present in the metamodels.

In order to manage the complexity, the metamodel layer is logically decomposed into a package structure that allows to group those metaclasses that show strong cohesion with each other and to loose coupling with classes in other packages. The top-level packages are the Foundation package, the Behavioral Elements package and the Model Management package. The Foundation package is the language infrastructure that specifies the static structure of models. It is further decomposed in the following sub-packages:

• Data Types that defines the basic data structures for the language, for example, the primitive data types such as Integer, String, and Boolean.

• Core that defines the basic concepts required for an elementary metamodel and the mechanisms to at- tach additional language constructs. Concrete constructs specified in this package are for example, Class, Association, Attribute and Operation.

(22)

• Extension Mechanisms that specifies how the model elements are customized and extended with new se- mantics. It defines the semantics for stereotypes, constraints and tagged values. Stereotypes may introduce additional constraints, additional tagged values and new graphical representation, but it is not necessary to stereotype a model element in order to give it individually distinct constraints or tagged values. Con- straints and tagged values can be directly attached to model elements either to change its semantics (by using for example a constraint language like OCL) or to specify a certain property. Constraints are defined by boolean expressions that, for the model to be well formed, must always yield the “true” value when the system is evaluated.

Behavioral Elements package is the language superstructure that specifies the behavioral model elements. It is decomposed into the Common Behavior package, the Collaborations package, the Use Cases package, the State Machines package and the Activity Graphs package.

• The Common Behavior package specifies the core concepts required for behavioral elements. In particular the concept of action is specified together with its classification into different type of actions (e.g., call action that results in the invocation of an operation, send action that results in the generation of a signal, create action that results in the creation of an object and destroy action that results in the destruction of an object). The metamodel specifying the action concept and its relationships with other basic concepts (operation, signal) has been fundamental for the formalization of the translation of Sequence Diagrams into Generalized Stochastic Petri Nets (GSPNs) that conforms to the translation of Statecharts into GSPNs.

• The Collaboration package provides the concepts needed to define collaborations and interactions among system components. The metamodels specified in this package have been used for the translation of Se- quence Diagrams into GSPNs.

• The Use Cases package specifies the behavior using actors and use cases.

• The State Machine package provides the concepts needed to model discrete behavior through finite state- transition systems. The metamodels specified in this package have been used for the translation of State- charts into GSPNs. It contains also the semantic foundation for activity graphs.

• The Activity Graphs package defines this special form of state machines.

The third top-level package of the UML metamodel is the Model Management package that specifies how model elements are organized into models, packages and subsystems.

2.1.3 Object Constraint Language

Additional constraints among model elements can be specified by the modeler; constraint expressions can be written in any of the UML notations: in Class Diagrams, e.g., to specify constraints among class objects, in

(23)

CHAPTER 2. BACKGROUND 23 Sequence Diagrams, e.g., to specify timing constraints on messages, etc.

These constraints can be specified either in natural language or through the use of a predefined constraint language provided by the UML standard: the Object Constraint Language (OCL) [64]. OCL provides a number of predefined data types like Boolean, Integer, String and Set and operations on these data to be used in the constraints for attributes, parameters, return values, etc. Besides these predefined types, all classes in the model can be used as types for OCL expressions and the OCL dotted-syntax allows to navigate along the associations of a class using the rolenames. There are also several reserved keywords to denote special part of the constraint, among them we report the ones that have been used in this thesis:

• context: it is used to declare the context for the constraint expression,

• inv: it is used to state an invariant for the corresponding context class,

• self: it is used as reference to an object of the context class.

An example of constraint written in OCL on the class Order of the CD shown in Figure 2.1 is the following:

context Order inv :

self.paid by→ exists(p : Payment | p.amount > 0)

This expression evaluates to true if the amount of at least a payment related to the order is greater than zero.

2.1.4 UML tools

There are a lot of CASE tools supporting UML or aspects of UML: a complete list together with their main features can be found in [63]; herein, we give a review of the UML tools that we have used for modeling with UML. Most of them are drawing editors that check the syntax of UML models and often generate code from the latter. The best known is Rose[44] from Rational Inc.: it starts by default with two packages, one for Use Case Diagrams and the other for Class Diagrams. This organization is not restrictive since any kind of diagram can be put into any package, moreover use cases can be dragged onto Class Diagrams and vice-versa. Keywords and invariants are not well supported and there is not a checking of the constraints written in OCL syntax;

constraints have to be written as comments, e.g., by using note symbols. Together [45], produced by Borland- TogetherSoft Inc., is a UML tool with many variants of code generation (e.g., C++, Java, Visual Basic) and supports round-trip engineering: while drawing a diagram the code appears in a separate window and if the code is edited the diagram changes according to the modifications. Concerning limitations, some of the UML basic concepts of State Machines are not supported, e.g., it does not allow to define “do” actions within states in the StateCharts. Also the UML tool Rhapsody [43], produced by I-Logix Inc., permits to generate code automatically from UML diagrams (in C,C++, Java and ADA) and interesting feature of this tool is that it allows to debug code through Sequence Diagrams and StateChart animation. Finally, ArgoUML [82] from Tigris, is an open-source

(24)

tool implemented in Java that supports checking of constraints written in OCL. Some of the UML notations, such as Sequence Diagrams, are not fully supported.

Most of the UML tools, such as the ones described above, support the import/export of UML diagrams in XMI exchange format [66]. However, usually tools generate XMI files that do not contain all the UML features characterizing the UML models: each tool uses a subset of XMI tags.

To define the analysis pattern for automation systems and for its customization to the case study, described in part I of this thesis, we have used Rose and Rhapsody tools (the latter with minor modifications with respect to the type of usage of the class attributes), although the figures depicting the various CDs have been produced by using a “simpler” graphical editor (Tgif [16]) mainly due to readability purposes. We come up against several limitations in creating the CDs by using both Rose and Rhapsody, for example that associations are inherited, that is a good think but, they are not visualized so that when we want to emphasize that two subclasses are in a given association a copy of the inherited association has to be explicitly created.

2.1.5 UML Profile for Schedulability, Performance and Time Specification

Different proposals have been made by the researchers on how to annotate UML diagrams with timing and probability specifications [12, 22, 60, 25, 38, 58]. These efforts together with opinions coming from many experts in the real-time domain contributed to the definition of a standard UML Profile for Schedulability, Performance and Time Specification [65] presented in [46]. The main purpose of this UML Profile is to facilitate the construction of UML models that can be used for the verification of quantitative properties of software systems and to enable the inter operability between various design and analysis tools. The Profile is partitioned into a number of sub-profiles defining specific quantitative aspects of software systems: the core of the Profile is the General Resource Modeling Framework, a set of sub-profiles in which the basic concepts of resources and of their quality of service (QoS) attributes, of concurrency and of time are defined. In particular, the sub-profile General Time Modeling introduces the concepts for modeling time and time values, event in time and time-related stimuli, timing mechanisms (e.g., clock, timers), timing services as those found in real-time operating systems. The three sub-profiles for schedulability, performance and real-time are based on the General Resource Modeling Frame- work. All the new concepts introduced in the sub-profiles are defined through the use of stereotypes and related tagged values. The sub-profile Performance Modeling, for example, provides concepts that allows to specify performance requirements and execution parameters in UML models (i.e., Collaboration, Sequence and Activity Diagrams). Execution parameters, that can be used as input parameters in formal models to compute the pre- dicted performance characteristics, and performance requirements are placed in scenarios, where each scenario consists of a sequence of one or more steps. The step is a basic concept that is mapped to the UML stereotype

<<PAstep>> and can be associated, for example, to messages of a Sequence Diagrams or to action states of an Activity Diagram. A step is characterized by several attributes, such as responseTime, representing the total delay to execute the step, and probability, representing the probability to execute the step. As basic concepts are

(25)

CHAPTER 2. BACKGROUND 25 mapped in stereotypes, their attributes are mapped in the related tagged values. In the DepAuDE methodology, we have preferred not to use the extensions defined in the UML Profile for the specification of CD scheme in order to maintain it as simple as possible by using the CD basic notation. However, the formats associated to some of the tagged values defined in the General Time Modeling and in the Performance Modeling sub-profiles, have inspired us for the definition of the type of usage of class attributes of the CD scheme and of a general format for the specification of the attribute values in the customized classes. In the translation of Sequence Diagrams we have used instead the tagged values associated to the step stereotype to map the timing specification and the branching probabilities in input parameters of the translated GSPN models. Finally, OMG has anticipated future profiles for the specification of other quantitative aspects of software system, such as dependability, that can be integrated in the structure of the current UML Profile. Within the last UML Conference held in Dresden [90] have been made different proposals of extension of UML for covering dependability aspects of critical systems, mainly security and safety, and of fault-tolerance. In particular, in [68] is presented a proposal of extending the General Resource Modeling sub-profile to include basic concepts such as faults and errors that affect the dependability of software systems.

2.2 Petri Net formalism

Petri Nets (PNs) is a modeling formalism used for the analysis of a wide range of systems coming from different domains (e.g., distributed computing, flexible manufacturing, telecommunication, control systems, work-flow management) and characterized by situations of concurrency, synchronization, causality and conflict. PNs were introduced for the first time by Carl Adam Petri in his doctoral thesis [70] to describe the behavior of concurrent systems in terms of cause/effect relations. A PN is basically characterized by places, transitions and weighted arcs defining its structure and it is graphically represented by a directed bipartite graph in which places are drawn as circles, transitions are drawn as bars, input and output arcs are drawn as arrows, and inhibitor arcs are drawn as circle headed arrows. In particular, PN models in which arcs have weights at most one are called ordinary PN models.

PNs incorporate a notion of (distributed) state, called marking, graphically represented by black dots (tokens) in places.

Transitions model events that may modify the system state so that the dynamic behavior of a PN is governed by transition firing rules. In an ordinary PN model, a transition can fire if all its input places contain at least one token and if all its inhibitor places do not contain tokens. When these conditions are satisfied then the transition is enabled and its firing removes one token from all its input places and generates one token in each of its output places. For example, in the ordinary PN model shown in Figure 2.4, transition T1is enabled since its input place P1is marked with one token and its inhibitor place P7 is empty. Once enabled, transition T1 can fire consuming the token from its input place and depositing a token into its output places P₂, P₃and P₄.

(26)

P1

P2

P3

P4

P5

P6

P7 T1

T2

T3

T4 T5

T6

T9

Figure 2.4: Example of a PN model.

In case of non ordinary PN models, enabling and firing rules depend on the weights of the arcs connecting input,output and inhibitor places to the transitions. It is worth to notice that the enabling conditions and the firing rules for a generic transition are “local”: indeed, only local information (i.e. input, inhibitor and output places) need to be considered to establish whether the transition can fire and to compute the change of marking.

A marking M⁰is said to be immediately reachable from marking M if M⁰can be obtained by firing a transition enabled in M. The set of transitions enabled in the marking M is denoted with E(M) and the firing of a transition t is denoted with M[ ti M⁰.

Starting from the initial marking M0it is possible to compute the set of all the reachable markings, the so called Reachability Set (RS) of the model. The RS does not contain information about the transition sequences fired to reach each marking. This information is captured by the Reachability Graph (RG) whose nodes are labeled with the reachable markings and whose arcs are labeled with the transitions whose firing provoke the changing of marking.

PN models can be used for the (qualitative) analysis of logical properties of systems such as the presence of system deadlocks or live-lock, relationships between events (causality, mutual exclusion, concurrency) and boundedness of the system state space. Classical analysis techniques [20] are 1) structural analysis techniques that check system properties by exploiting the topology of the net (and, at most, by considering the initial marking), and 2) state-based analysis techniques that require, instead, the construction of the reachability graph of the PN model for the verification of properties.

In their original definition PNs do not include time concepts; temporal specification in PN models were introduced several years later, with different approaches, based on the use of deterministic timing first and on stochastic timing later. The introduction of temporal specifications in a PN has been done mostly by associating a delay to transitions. In particular, in Stochastic Petri Nets (SPN)[61] transition firing delays are exponentially distributed random variables: so that, to each transition t_i is associated a random firing delay whose probability density function is a negative exponential with rateλi.

Building Stochastic Petri Net models for the veriﬁcation of complex software systems

UNIVERSIT ` A DEGLI STUDI DI TORINO

Dipartimento di Informatica

C.so Svizzera, 185 - 10149 Torino (Italia)

DOTTORATO DI RICERCA IN INFORMATICA (CICLO XV)

TITOLO DELLA TESI

Building Stochastic Petri Net models for the verification of complex software systems

TESI PRESENTATA DA:

Simona Bernardi

TUTOR:

Prof.ssa Susanna Donatelli

COORDINATORE DEL CICLO:

Prof. Piero Torasso

ANNI ACCADEMICI:

’99/’00 - ’00/’01 - ’01/’02

Contents

Chapter 1

Introduction

Background

2.1 UML semi-formalism

2.2 Petri Net formalism