Emulink: a graphical modelling environment for PVS

(1)

Dipartimento di Ingegneria dell’Informazione

Laurea magistrale in Ingegneria Informatica

Master’s thesis

Emulink:

a graphical modelling environment for PVS

Candidate:

Enrico D’Urso

Supervisors:

Prof. Cinzia Bernardeschi Prof. Andrea Domenici

(2)

enthusiasm. [Churchill]

Odio gli indifferenti. L’indifferenza è abulia, è parassitismo, è vigliaccheria, non è vita. Perciò odio gli indifferenti. [Gramsci]

Dum Romae consulitur, Saguntum expugnatur. [Livio]

Istud quod tu summum putas gradus est. [Seneca]

Dum differtur, vita transcurrit. [Seneca]

(3)

Abstract

Software testing is one of the most important phases in software development process. It can be used to show the presence of bugs, but never to show their absence. A complementary approach to make software safer is to use formal verification techniques. They guarantee correctness of an implementation with respect to given specifications and they can greatly increase our under-standing of a system by revealing inconsistencies, ambiguities, and incom-pleteness that might otherwise go undetected. Experience has demonstrated that software engineers without significant mathematical ability can hardly use verification tools and techniques. In this thesis we present Emulink, a tool that can help software engineers to create formal specifications in PVS (Prototype Verification System) starting from a stateCharts based diagram. Emulink has a cloud-based architecture, and a simple Internet browser can be used to run its front end. We show an application of Emulink to model and analyse software from a commercial medical device. The tool and the presented example were developed in collaboration with researchers working within the CHI+MED research project (http://www.chi-med.ac.uk), which aims to improve the safety of medical devices.

(4)

Acknowledgements

I would like to thank my tutors, Paolo Masci and Paul Curzon, whose exper-tise, understanding, and patience, added considerably to my graduate expe-rience. They have made available their support in a number of ways during my period at the School of Electronic Engineering and Computer Science at Queen Mary University of London. I would like to express my deep gratitude and respect to Michael Harrison whose advices and insight was invaluable to me. I would also like to thank my supervisors at University of Pisa, Cinzia Bernardeschi and Andrea Domenici, who made this thesis possible. I would like to thank my family, especially my mother and father without whom I could not have made it here. Thanks to my supportive friends who accompa-nied me during these years of study. Thanks to Ivana whose understanding, and patience, really helped me. Lastly, I offer my regards and blessings to all of those who supported me in any respect during the completion of my studies.

(5)

List of Figures

2.1 Software development costs (source: [1] ) - On the left(right)

costs without(with) the use of formal verification . . . 15

2.2 Example of POS . . . 20

2.3 Secret combination : A state machine model . . . 21

2.4 PVS Graphical User Interface based on Emacs . . . 26

2.5 PVS Graphical User Interface: parse command . . . 26

2.6 PVS Graphical User Interface: parse command without any error . . . 26

2.7 PVS Graphical User Interface: typecheck command result . . 27

2.8 PVS Graphical User Interface: pvsio . . . 28

3.1 States of a process in a simple OS . . . 31

3.2 Simulink StateCharts: SubChart example . . . 34

3.3 Simulink StateCharts: SubChart- History notation example . . 34

3.4 Simulink StateCharts: SubChart- Junction example . . . 35

3.5 Simulink StateCharts: SubChart- AND states example . . . . 36

4.1 PVSio-web: Client Server architecture . . . 38

4.2 PVSio-web: Client front-end . . . 39

4.3 PVSio-web: Editor . . . 40

4.4 PVSio-web: Client Architecture . . . 41

4.5 POS used in this example . . . 43

4.6 Display area fields . . . 44

4.7 Setting of the OK BUTTON . . . 45

4.8 Pin Machine: partial combination . . . 45

5.1 Emulink: Blocks System . . . 49

5.2 Emulink: Opening the Statechart Editor Area . . . 50

5.3 Emulink: Creating a new Emulink model . . . 50

5.4 Emulink: Statecharts Editor . . . 51

5.5 Emulink: A state example . . . 57

(8)

5.6 Emulink: A transition example . . . 58

5.7 Emulink: An other transition example . . . 60

5.8 Emulink: Default transition example . . . 61

5.9 Emulink: A Condition example . . . 62

5.10 Emulink: An action example . . . 63

5.11 Emulink: Action and condition in the transition . . . 66

5.12 Emulink: Action and condition in the transition . . . 70

5.13 Emulink: Enabling SAM . . . 71

5.14 Emulink: SAM in action . . . 72

5.15 Emulink: Highlighting Emucharts, an overview . . . 73

6.1 Emucharts model . . . 77

6.2 Displaying 99.3 . . . 79

6.3 Inserting a value higher than 1199 . . . 79

6.4 The decimal point completely ignored . . . 79

6.5 EmuCharts model . . . 81

(9)

Chapter 1 Introduction

Almost all devices in use today rely on software to perform their intended functionalities. We can now find software virtually in any application domain: from everyday objects such as calculators and watches, to safety-critical do-mains such as avionics and healthcare. This amazingly high diffusion has definitely led to an improvement of our life, making it in some cases easier. On the other hand, it is also true that poorly designed software can cause problems.

In safety critical domains, poor design may even endanger people’s lives. Sometimes, software products are released early due to market constraints. This implies poor software testing and verification. In particular software verification, which is a powerful method for finding software errors, is seldom used. There are some reasons for that, for instance formal specification and analysis are often considered very expensive and they require highly qualified engineers.

However, the use of formal methods is increasingly being required by international standards and guidelines for the development of safety critical digital control systems. Formal methods are in fact recognized as a fault avoidance technique that can increase dependability by removing errors at the requirements, specification and design stages of development. Formal methods are highly recommended by such standards as the EN 50128:2001 European Standard [2] in the requirements specification and in the design and the validation of railway control and protection systems, and the IAEA NS-G-1.1 Standard [3] in digitalized instrumentation and control systems in nuclear power plants.

Two main lines of research emerge from the formal methods literature, addressing methods based on model checking [4] and theorem proving [5], respectively.

Model checking relies on generating a state model of system behavior. 8

(10)

Properties of the system are then expressed in a temporal logic language with respect to this model; for example, one may specify that a given relationship among system variables (such as signal values) holds for certain subsets of the state space, e.g., for all states, or for some states following a state where an-other condition holds, or an-other possible time orderings. Properties expressed in temporal logic are automatically verified by model-checking algorithms.

Model-checking approaches are attractive because they are highly auto-matic: the user simply provides a description of the system implementation and a temporal logic formula specifying the property to be proved, and the system automatically carries out the proof by generating the state space and checking, by an exhaustive search, that the state space is a model of the for-mula. Model checking algorithms incur the problem of state space explosion, i.e., the extremely large size of the state space that must be explored for most systems of interest.

Theorem proving relies on specifying a system as a theory, i.e., a set of logical statements that define the system’s structure and its fundamental properties. Further derived properties about the system’s behavior can then be verified with respect to the theory, employing a collection of inference rules specific to the logic used to define the theory.

Verification is done by executing proofs assisted by a theorem proving tool that can apply inference rules in an entirely or partially automatic manner. Theorem provers may require a considerable involvement of the user in constructing a proof. An example of theorem prover is the Prototype Ver-ification System (PVS) [6]. This environment provides also the means to execute logical specifications using the PVSio package [7].

PVS has been used for formal reasoning in several application domains, (see [8, 6, 9, 10, 11, 12]). Recently, in [13] a formal verification approach based on PVS for detecting design issues related to user interaction, with a focus on user interface of medical devices, has been used. A less often used PVS component is its ground evaluator [14] that can be used to ani-mate functional specifications. In order to still be able to aniani-mate theories that also involve non-executable constructs, such as declarative specifications, the ground evaluator can be augmented by so-called semantic attachments, through which the user can supply pieces of Lisp code and attach them to the declarative parts. Using this mechanism the PVSio package [7] extends the ground evaluator with a predefined library of imperative programming language features such as side effects, unbounded loops, and input/output operations, and also provides a high-level interface for writing user-defined semantic attachments. Thus, PVS specifications can be conveniently ani-mated within the read-eval-print-loop of the ground evaluator.

(11)

In this thesis, we present Emulink, a graphical environment to produce state-machine based specifications and translate them automatically into PVS theories. In particular Emulink is a plugin of PVSio-web, a web-based ex-tension for PVS specifications.

PVSio-web and Emulink enable developers to:

• Model systems using EmuCharts notation, which is a subset of the popular StateChart notation.

• Generate PVS specification starting from an EmuChart diagram. • Demonstrate the behaviour of the software using a level of abstraction

adequate to the property being verified.

In literature there are some works about the translation from the state-Charts notation into some formal specification language. [15] presents a tool to translate STATEMATE stateCharts 1 _{into SMV (Symbolic Model}

Veri-fier) specification language. SMV is an input language for model checking. In [16] a translation from a subset of UML Statechart Diagrams into PROMELA is presented. PROMELA is a process language, based on the interleaving model of computation. It is the specification language of the SPIN model checker. The choice of SPIN is mainly motivated by the variety of highly efficient state-space representations techniques and search algorithms it pro-vides. Two implementations of the base translation exist: one has been de-veloped in National Research Council of Pisa and is written in Standard ML. The other has been developed at the Technical University of Budapest[17]. In particular, [16] presents an approach for the formalization of one of the diagrams of UML, namely statecharts diagrams. That is achieved by using the PVS Specification Language as formal semantics domain. The general approach of the work consists of the following steps:

• The UML statechart diagram is converted in an abstract syntax using PVS-SL.

• Then on the basis of that syntax which is specific to the model con-sidered, a set of well-formedness rules are provided under the form of PVS theorems.

• The rules are checked and the model is updated.

(12)

• The formal semantics of the model in the PVS specification language is generated.

• The model obtained will serve as basis for the verification of the model using the model-checker available in PVS and the system properties specified by the user.

The author of the paper prefers using a model checker approach rather than use a theorem proving approach because model-checking is largely automatic Emulink and PVSio-web have been developed within the CHI+MED (Computer-Human Interaction for Medical Devices) project. It is a UK project aimed to improve the safety of interactive (programmable) medical devices, such as infusion pumps. CHI+MED brings together an interna-tionally leading team of researchers from four universities and two hospitals working with a wide range of stakeholders.

The University College London Interaction Centre is a leading centre on in-teraction design. They bring expertise in the understanding of cognition. They also are a world leading team in research on understanding complex situations within which computer-based devices are employed.

City University brings expertise in the design and evaluation of mobile de-vices.

The Swansea University Future Interaction Technology Laboratory brings ex-pertise in emerging technologies, device design and the design of tools to help manufacturers.

Queen Mary University of London brings expertise in mathematical analysis of complex systems that include humans.

The Royal Free and Singleton Hospitals bring practical expertise in all as-pects of medical practice, from clinicians to procurement specialists [18].

PVSio-web has been used to simulate the behaviour of some medical de-vices, binding a picture, which reproduces the device physical appearance, to the corresponding PVS specification. It makes possible a realistic simulation of the interaction human-machine. The main limitation with the original version of PVSio-web was that PVS specification needed to be previously developed by some expert in PVS specification. Emulink overcomes this limitation, through an environment which allows users to develop PVS spec-ification using Emucharts, a state-machine based graphical notation similar to the Statecharts notation, currently used also in industry.

(13)

This thesis is organized as follows:

• Chapter 2: Background chapter about formal specification with PVS. • Chapter 3: Introduction to the StateCharts notation.

• Chapter 4: The PVSio-web distributed environment.

• Chapter 5: The Emulink system, main contribution of this thesis. • Chapter 6: Application of PVSio-web and Emulink to the validation of

a commercial medical device.

(14)

Chapter 2 The Prototype Verification

System

2.1 Introduction

In ’traditional’ engineering disciplines, such as electrical and civil engi-neering, progress has usually involved the development of better mathemat-ical techniques. The engineering industry has had no difficulty accepting the need for mathematical analysis and incorporating mathematical analysis into its processes. Mathematical analysis is a routine part of the process of developing and validating a product design. However, software engineering has not followed the same path. Although there has now been more than 30 years of research into the use of mathematical techniques in the software pro-cess, these techniques have had a limited impact. So called formal methods of software development are not widely used in industrial software develop-ment. Most software development companies do not consider it cost effective to apply them in their software development process [1].

There are some main reasons for this:

Successful software engineering The use of other software engineering methods such as structured methods, configuration management and information hiding in software design and development processes have resulted in improvements in software quality.

Market changes Software must be developed quickly, and customers are sometimes willing to accept software with some faults if rapid delivery can be achieved. Techniques for rapid software development do not work effectively with formal specification.

(15)

Limited scope of formal methods Formal methods are not well suited to specifying user interfaces and user interaction. The user interface component has become a more and more important part of most sys-tems, therefore formal methods, when adopted within the development process, are not used to analyse the user interface.

Existing tools are not popular/friendly Existing tool for formal meth-ods are not popular and are not easy to use.

Learning curve is high Learning curve is steep. Many software compa-nies do not have in house expertise in formal methods and need to rely on external consulting companies.

However, formal specification is an excellent way of discovering speci-fication errors and presenting the system specispeci-fication in an unambiguous way. Organizations that have made the investment in formal methods have reported fewer errors in the delivered software without an increase in devel-opment costs. For instance, Intel started to use formal verification routinely since a bug was discovered in the floating point unit of the Pentium processor [19]. As you develop the specification in detail, your understanding of that specification increases. Creating a formal specification forces you to make a detailed systems analysis that usually reveals errors and inconsistencies in the informal requirements specification. This error detection is probably the most potent argument for developing a formal specification. Finally, we can also add that using formal methods and verification tools, specification and implementation costs are comparable and system validation costs are sig-nificantly reduced. As the development of the formal specification uncovers requirements problems, rework to correct these problems after the system has been designed is avoided as shown by figure 2.1.

In the next section we show PVS (Prototype Verification System), which is a powerful system for writing formal specifications. Also, an example of PVS specification is provided.

2.2 PVS environment

PVS is a system for writing formal specifications and constructing proofs. The Formal Methods group at NASA Langley develops and applies PVS the-orem proving technology for verification of safety-critical aerospace applica-tions.

(16)

Figure 2.1: Software development costs (source: [1] ) - On the left(right) costs without(with) the use of formal verification

checker that supports top-down proof exploration and construction.

In addition to its proof checker, the PVS system includes a parser, pret-typrinter and type-checker. A PVS specification consists of a collection of theories. Each theory consists of a signature for the type names and con-stants introduced in the theory, and the axioms, definitions, and theorems associated with the signature.

The whole PVS system packet can be downloaded here: http://pvs. csl.sri.com/download.shtml. Describing PVS system in its entirety is beyond the scope of this thesis, in the following sections a description of a subset of the PVS language is provided, in particular the parts of the PVS language which are used in the next chapters. The main source of the in-formation about the PVS language is [20], please refer to that for further details. Also, a simple but complete example of a PVS theory is provided.

2.2.1 Theories

Specifications in PVS are built from theories. A theory consists of a theory identifier, a list of formal parameters, an EXPORTING clause, an assumptions part, a theory body and an ending id. In the PVS system, the set of theories currently available to the session form a context. There is

(17)

an initial context available, called the prelude, which provides, among other things, the Boolean operators, equality, and the real, rational, integer, and natural number types and their associated properties

The simplest example of theory is the following empty theory: MyTheory : THEORY

BEGIN

END MyTheory

In the following only simple theories with the use of IMPORTING and EX-PORTING clauses are taken into account. Names declared in a theory may be made available to other theories in the same context by means of EX-PORTING clauses. Names exported by a given theory may be imported into another theory by means of the IMPORTING clause. Note that the pre-lude is automatically imported in every theory, without requiring an explicit IMPORTING clauses.

2.2.2 Declarations

Entities of PVS are introduced by means of declarations, which are the main constituents of PVS specifications. Declarations are used to introduce types, variables, constants, formulas, judgements and conversions. Each dec-laration has an identifier and belongs to a unique theory. Decdec-larations in-troduced in one theory may be referenced in another by means of the IM-PORTING and EXIM-PORTING clauses.

Type Declaration

Type declarations are used to introduce new type names to the context. There are four kinds of type declaration:

1. uninterpreted type declaration, for example: T: TYPE

2. uninterpreted subtype declaration, for example: S: TYPE FROM T 3. interpreted type declaration, for example T: TYPE = int

4. enumeration type declarations, for example T: TYPE = {r, g, b} In the following all of them are described except uninterpreted subtype dec-laration.

(18)

Uninterpreted types introduce a type with a minimum of assumptions on the type.

This means that using that type there are almost no constraints on an im-plementation of the specification, except for the fact that an uninterpreted type T is disjoint from all other types, except for subtypes of T.

A specification which uses uninterpreted types has a high level of abstraction and this is important to decouple specification from implementation.

Interpreted type declarations are primarily a means for providing names for type expressions. A simple example of interpreted type is the following: T: TYPE = int

A more complex example is the following:

intfun: TYPE = [int -> int]

It introduces the type name intfun as an abbreviation for the type of functions with integer domain and range. This way, any type expression T involving intfun is equivalent to the type expression obtained by substituting [int → int] for intfun in T.

Enumeration types are on the form: enum: TYPE = {X1, X2 ..., Xn}

where the Xi are distinct identifiers which are taken to completely enumerate the type.

2.2.3 Expressions

The PVS language offers the usual panoply of expression constructs, in-cluding logical and arithmetic operators, quantifiers, lambda abstractions, function application, tuples, a polymorphic IF-THEN-ELSE, and function and record types. The language has a number of predefined operators, in the following a relevant subset of them is described.

Boolean Expressions include the constants TRUE and FALSE, the unary operator NOT, and the binary operators AND (also written &), OR, IMPLIES (→), WHEN and IFF (⇔).

(19)

and inequality (/=) are both polymorphic, the type depending on the types of the left and right hand sides.

If the types are compatible, meaning that there is a common supertype, then the (in)equality is of the greatest common supertype. Otherwise it is a type error.

For example, S,T: TYPE

eq1: FORMULA s = t

Eq1 will cause a type error, because S and T are uninterpreted type, then they are assumed to be disjoint.

IF- THEN-ELSE Expressions The IF-THEN-ELSE expression IF cond THEN

expr1

ELSE expr2 ENDIF

is polymorphic; its type is the common type of expr1 and expr2 . The cond must be of type boolean. Note that the ELSE part is not optional as this is an expression, not an executable statement.

Any number of ELSIF clauses may be present.

LET Expressions are provided for convenience, making some forms easier to read.

They provide local bindings for variables that may then be referenced in the body of the expression. Here an example:

LET x:int = 3, y:int = x * x IN x + y

The value of this expression is 12. The type declaration is optional, so the above expression could be written as:

LET x = 3, y = x * x IN x + y

In this case the typechecking of these expressions depends on whether x and/or y have been previously declared as variables. If they have, then those declarations are used to determine the type. Otherwise, the right-hand side of the = is typechecked and if it is unambiguous is used to determine the type of variable. In the remainder of this thesis the second option is often used.

(20)

( # a1 := e1, ... an := en # ) they have type:

[ # a1: t1, ..., an: tn # ]

The components of an expression of a record type are accessed using the corresponding field name. There are two forms of access. For example if State is of type:

[# current_input: real, current_output : int # ] the current input component may be accessed using either

State‘current_input or

current_input(State)

The COND construct is a multi-way extension to the polymorphic IF-THEN-ELSE construct of PVS. Its form is :

COND be_1 -> e_1, be_2 -> e_2, ... be_n -> e_n ENDCOND

be i are boolean expressions and e i are expressions of some common super-type. It is required that the boolean expressions are pairwise disjoint and that their disjunction is a tautology.

2.2.4 PVS Theory: an example

In this section a simple PVS theory is developed step by step. The main purpose of the example is to allow the reader to acquire familiarity with some of the PVS constructs described in the previous sections, because they are also used in chapter 5.

(21)

Figure 2.2: Example of POS Modelling a simple POS using PVS

The example is about a hypothetical POS (Point Of Sale) device, like the one shown in figure 2.2.

The device specification, written in ’natural language’, is the following: • The user must be able to enter a PIN, which can be composed of up to

four digits.

• After the fourth digit, any additional digit must be ignored.

• The user completes entering the combination by pressing OK, and the device checks the correctness of the entered PIN.

• To ease the presentation, the correct secret PIN is assumed to be 748. The specification above can be modelled as a state machine. The state machine concept, which is explained in chapter 3.1, is a tool to model reactive systems such as the one in our example. In figure 2.3 the state machine model is shown.

The state machine model consists of three states: ENTER PIN, PIN OK, PIN ERROR. In this model there are two events to handle, click digit and click ok.

The first one is triggered when the user clicks on any digit, the second one when the user clicks on ’OK’ button in order to verify the PIN. Consider state ENTER PIN, if the user clicks on any digit the self transition is taken

(22)

Figure 2.3: Secret combination : A state machine model

and the display is properly updated, else if the user clicks on ’OK’ button the system transitions either to PIN OK or PIN ERROR, depending on whether the pin is correct or not. In any case, the system goes back to ENTER PIN again as soon as the user types a new digit.

Writing the PVS specification

In this section, the PVS specification is developed step by step. As previ-ously explained, a PVS specification is formed by theories. In our example, just one theory is required. A theory needs to have an identifier, let us call it ’CombinationTheory’, the PVS code is then the following:

CombinationTheory: THEORY BEGIN

END CombinationTheory

Since we modelled the device behaviour following a state machine approach, we need to define the following machine states:

(23)

• ENTER PIN • PIN OK • PIN ERROR

In PVS we can use an enumeration type for this purpose:

StateName: TYPE = { ENTER_PIN, PIN_OK, PIN_ERROR }; Also, we need to identify a data structure which contains the information we need to describe our device, its fields are updated when the system is running to reflect the current state of the system. By doing that, we have all information enclosed in just one PVS type. You can think it similar to a structure in ’C’ language, if it helps. In the following we refer to that using the name ’PVS state’. For our example the PVS state should at least have:

• A field to indicate which state-machine state is the current one. • A field to indicate the value which is to be displayed on the screen

(i.e., either current combination or messages indicating if PIN has been correctly recognized ).

To put all this information together in one PVS type, we can use a record type, each field just listed will be then a record accessor ( or field) of this record type. Of course, we need to choose a type for each of the fields. For the first one, the answer is obvious, that is StateName. For the second one we can use a string type. Finally, the PVS code could be the following: State: TYPE = [#

current_state: StateName,%StateMachine current state display: string

#]

Note the symbol ’%’, it is followed by a comment which terminates when a new line is reached. Now, we need to write in PVS the click digit and click ok event, on which the whole system is based.

First of all, focus on click digit. Click digit can be modelled in PVS as a function which takes the current PVS State and an integer (that is the digit just inserted by the user) as arguments and returns a new PVS State.

Therefore, the PVS code is the following:

(24)

The body of the function should update the display and set current state in PVS state equal to ENTER PIN, indeed click digit transition has always ENTER PIN as target state. It can be written in PVS like this:

LET new_val = update_display(digit)(st)

IN st WITH [display := new_val,current_state := ENTER_PIN] Basically we obtain a new value for the display and then we update it using the WITH construct and we also update the current state record. Here the update display function body:

update_display(digit: int) (st : State): string = IF strlen(st‘display) < MAX_LENGTH_PIN THEN

IF st‘current_state /= ENTER_PIN THEN "" + digit ELSE st‘display + "" + digit ENDIF ELSE st‘display ENDIF

It takes as arguments the digit just typed by the user and the current PVS State. It checks if display can be updated, note that MAX LENGTH PIN is a constant which can be declared like this:

MAX_LENGTH_PIN : int = 4

If the current display length is less than four, the function checks if cur-rent state is diffecur-rent from ENTER PIN, if this is true the display value is updated using just the current digit, else the display current value is used, too. It makes sense because if the current state is different from ENTER PIN it can be either PIN OK or PIN ERROR, but in both cases the value of the display must be updated only with the digit just typed. Finally, if the current display length is greater than or equal to four, the display is not updated and the current value is returned.

Now, let us focus on click ok. When the user clicks on OK button, the device screen should show a positive message like ’OK’ or a negative message like ’Err’ depending on the correctness of the combination just entered. Also, the right target state must be entered. All of this can be written in PVS as follows:

(25)

IF st‘display = myPIN THEN

st WITH [ display := "OK", current_state := PIN_OK ] ELSE

st WITH [ display := "Err", current_state := PIN_ERROR] ENDIF

It takes as argument the current PVS state and returns back a new one. It checks if the current display value is equal to the right PIN, that is defined using the myPIN constant.

myPIN: string = "748"

If this condition is verified then display is updated with a positive mes-sage and current state record is updated with PIN OK. Else, display is up-dated with a negative message and the current state record is upup-dated with PIN ERROR.

The whole PVS specification is shown in listing 2.1. Listing 2.1: PVS initial theory

1 CombinationTheory : THEORY 2 BEGIN

3

4 strlen(s: string): int = strfind("\r", s + "\r") 5

6 StateName: TYPE = { ENTER_PIN, PIN_OK, PIN_ERROR

}; 7 8 myPIN: string = "748" 9 MAX_LENGTH_PIN : int = 4 10 11 State: TYPE = [#

12 current_state: StateName, % State machine

current state

13 display: string

14 #]

15

16 update_display(digit: int) (st : State): string

=

17 IF strlen(st‘display) < MAX_LENGTH_PIN THEN 18 IF st‘current_state /= ENTER_PIN THEN 19 "" + digit

20 ELSE

21 st‘display + "" + digit 22 ENDIF

(26)

24 st‘display 25 ENDIF

26

27 click_digit(digit: int)(st : State): State = 28 LET new_val = update_display(digit)(st) 29 IN st WITH [ display := new_val,

current_state := ENTER_PIN ]

30

31 click_OK(st: State): State =

32 IF st‘display = myPIN THEN st WITH [ display

:= "OK", current_state := PIN_OK ]

33 ELSE st WITH [ display := "Err",

current_state := PIN_ERROR] 34 ENDIF 35 36 37 38 END CombinationTheory

2.3 PVS: parsing, typechecking and

explor-ing the specification

In this section, we show how to parse, typecheck and explore the speci-fication described in the previous section. To do that, we interact with the PVS system through a customized Emacs. Instructions are issued to PVS by means of Emacs commands. The PVS specification shown in 2.1 should be pasted in a file called CombinationTheory.pvs. Also the PVS system should be opened, to do that just open a unix command line window and type: pvs

by doing that the PVS GUI-interface will be opened, as shown in figure 2.4. Finally, to load the specification, just click on file - open file in the Emacs top left corner.

2.3.1 Parsing the specification

The parser checks theories for syntactic consistency and builds an internal representation that is used by other components of the system. When errors are detected by the parser or other components of PVS, the cursor is generally placed at the location where the error was detected and an error message is

(27)

Figure 2.4: PVS Graphical User Interface based on Emacs displayed in a pop-up [21].

To parse, type alt-x and then type ’parse’ as shown in figure 2.5. When an

Figure 2.5: PVS Graphical User Interface: parse command

error is detected, the file is displayed with the cursor at the location where the error was detected, which is frequently after the actual source of the error. If there is no error, the message ”CombinationTheory parsed in # seconds ” is displayed. This latter case should be our one, as shown in figure 2.6.

(28)

2.3.2 Typechecking the specification

Typechecking a PVS specification checks semantic constraints, deter-mines the types of expressions, and resolves names. Typechecking is invoked much like parsing, and automatically parses the file if necessary. Errors are indicated in the same manner as for parsing, although the cursor is usually more accurately positioned at the error [21]. The type system of PVS is not algorithmically decidable; theorem proving may be required to establish the type-consistency of a PVS specification. The theorems that need to be proved are called type-correctness conditions (TCCs). TCCs are attached to the internal representation of the theory and displayed on request. To typecheck type alt-x and then typecheck. The result should be as shown in figure 2.7. We can observe the presence of a message, which can be read by typing show-theory-messages. It is the following:

LET/WHERE variable new_val at line 27, col 9

is given type string from its value expression.

It is not an error, and it and can be neglected.

Figure 2.7: PVS Graphical User Interface: typecheck command result

2.3.3 Exploring the specification

To explore the specification and therefore to make rapid prototyping, PVS system provides PVSio. The core of PVSio is a translator that compiles PVS expressions into Common Lisp code. It presents itself as an interactive command prompt with a read-eval-print loop that allows developers to enter commands and execute PVS specifications on-demand. For instance, the behaviour of a function defined in a PVS specification can be executed within PVSio by writing the name of the function in the PVSio command prompt: PVSio evaluates the function and returns a result [22]. To use PVSio, type alt-x and ’pvsio’ in emacs command line. By doing that, there should be a visible pvsio command line on the right of the Emacs window, as shown in figure 2.8

(29)

Figure 2.8: PVS Graphical User Interface: pvsio

To start the exploration of the specification, type the following code in PVSio:

click_digit(1)((#current_state:=ENTER_PIN,display:=""#)); By doing that, click digit function is invoked with two parameters, the first one is:

1

which is the digit to process, while the second one is:

(# current_state := ENTER_PIN, display := "" #) which is a PVS state.

The result should be:

(# current_state := ENTER_PIN, display := "1" #)

It should be noted how the PVS state fields have been updated, in particular ’display’ reflects the digit just typed.

If we want to insert a complete combination, we should type: LET tmp = click_digit(7) ((# current_state := ENTER_PIN, display := "" #)), tmp = click_digit(4)(tmp), tmp = click_digit(8)(tmp) IN click_OK(tmp);

Basically, we save the new PVS state in ’tmp’ and we reuse that each time. Because the combination is correct the result is:

(# current_state := PIN_OK, display := "OK" #) If the combination is wrong:

(30)

LET tmp = click_digit(7) ((# current_state := ENTER_PIN, display := "" #)), tmp = click_digit(4)(tmp), tmp = click_digit(1)(tmp) IN click_OK(tmp);

the result which PVSio returns is:

(# current_state := PIN_ERROR, display := "Err" #)

Conclusions

A short explanation of PVS system has been given to the readers. Also, the concept of state machine has been introduced. It will be detailed in chapter 3.1, in particular the concept of StateCharts will be explained, that is an extension of state machine. This brief introduction shows that PVS enables users to write precise formal specifications, but requires knowledge of a complex language. The purpose of this thesis is then to create an in-terface that reduces the complexity of PVS making it a tool usable even by non-highly trained engineers. In particular we present Emulink and PVSio-web which allow to create PVS specification using Emucharts notation and also it allows to explore a specification behaviour in a natural way. Before introducing PVSio-web and Emulink the StateCharts concept is explained in detail in the next chapter.

(31)

Chapter 3 StateCharts

3.1 Introduction

StateCharts were introduced by David Harel in 1987 as a modelling tool for complex and reactive systems. A reactive system is one which must con-tinuously react to external and internal stimuli, examples include communi-cation networks, computer operating systems and human-machine interfaces. Using StateCharts a system may be modelled in a clear and realistic way and at the same time in a formal and rigorous way. Also, states and events are a rather natural medium to describe the dynamic behaviour of complex sys-tems. StateCharts notation is a kind of extended Finite State Machine with abstraction, concurrency, and communication. Because StateCharts extend Finite State Machine, before describing StateCharts the concept of State Machine is introduced in the following section.

3.2 Finite State Machine

A finite state machine (FSM) is a mathematical model of a system that attempts to reduce the model complexity by making simplifying assumptions. Some of the simplifications are:

• The system can assume only a finite number of conditions, called states. • The system may change these conditions only in a finite number of

well-defined ways, called transitions.

• Transitions are the response of the system to events.

A state describes a mode of an event-driven system. The activity or inactivity of the states dynamically changes based on events and conditions.

(32)

Consider a process in an operating system. Such a process can be in one of the following states:

New The process is in the stage of being created.

Ready The process has all the resources it needs to run, but CPU is not currently working on this process’s instructions.

Running The CPU is working on this process’s instructions.

Waiting The process cannot run, because it is waiting for some resource to become available or for some event to occur.

End The process has completed.

This simple model is shown in figure 3.1 1_.

Figure 3.1: States of a process in a simple OS

States here are shown as rounded rectangles. Transitions are directed lines beginning at the starting state for the transitions and ending at the target state. Transitions here have the following general form:

label[condition] / action

(33)

where label is the name of the event, condition is a boolean expression which is to be verified to take the transition and action is an operation which is executed when the transition is taken. Note that condition and action are optional. The state machine in our example consists of five states and six transitions. The solid circle indicates the starting state where the system starts, in this example the first state of a process is New state. In the New state, the process is in the stage of being created; when the operating system inserts it in the Ready queue, it transitions to the Ready state. After it becomes the process which has the highest priority2 _{among the processes in}

the Ready queue, it transitions to the Running state, because the condition of this transition is verified. As a result of the transition, one action is performed, some CPU registers are properly set with new values which belong to the incoming process3_{. Once in the Running state, the process can respond}

to three transitions: I/O or event wait, interrupt and exit. In the first case, the process context is saved and the process transitions to the Waiting state. In the second case, the process context is saved as well, but the process transitions to the Ready state. In the last case, the process transitions to the Exit state.

3.3 Problems with Classical FSMs

It is difficult to represent complex systems with FSM models. FSM work well for simple, event-driven systems, but do not ’scale up’ to larger systems. This is unfortunate because the more complex the system to be modelled, the greater our need for modelling tools.

The limited scalability of FSMs stems from two fundamental problems: • Flatness of the state model.

• No concurrency support.

Almost all conceptual modelling techniques rest on constructing layers of abstraction. For example, consider computer programming. All program-ming can be fully described by the states of all transistors in the CPU. Moving up a level in abstraction, we can consider the numerical op code being ex-ecuted by the CPU. Even better than op codes is to use mnemonic names for the op codes, in assembly language. Finally, the abstraction level can be further moved up using a high level language like JAVA. Using the right

2_{Supposed that the OS has a priority based scheduling system}

3_{If the reader is interested in the subject in the literature can find a lot of information} about the context switching

(34)

layer of abstraction is important to move the problem solution away from the domain of the implementation to the problem domain. Flat state machines do not provide the means to construct higher layers of abstraction. All states are equally visible and are considered to be at the same level of abstraction. Another problem with traditional state machines is its lack of support for concurrency. This leads to a combinatorial explosion in the number of states to model.

3.4 StateCharts

StateCharts are an attempt to overcome the limitations of traditional FSMs while retaining their good features. The StateCharts concept was cre-ated by Harel [23], in the following we show the Stateflow[24] notation to describe StateCharts. StateCharts include both the notions of nested, hi-erarchical states and of concurrency, while extending the notion of actions. Statecharts are represented as rounded rectangles, directed lines indicate transitions from state to state. Note that there are a number of differences between Statecharts and traditional state diagrams. The most noticeable is the appearance of states within states. The outer enclosing state is called a superstate. The inner states are called subcharts. Subcharts enable you to reduce a complex chart to a set of simpler, hierarchically organized diagrams. This makes the chart easier to understand and maintain. You can define ac-tions and default transiac-tions for subcharts just as you can for superstates. You can also create transitions to and from subcharts just as you can cre-ate transitions to and from superstcre-ates. Further, you can crecre-ate transitions between states residing outside a subchart and any state within a subchart. In figure 3.2 SC1 and SC2 are subchart inside the superstate S0. While the system is in state S0, it must be in exactly one of the nested subcharts as well.

Transitions may be drawn to the specific substate, or may be drawn to the containing superstate. In this latter case, some rules must be applied to determine which substate is entered. When there is ambiguity, an initial state must be identified using the filled circle, just as in traditional FSMs. Additionally, a history mechanism may be included, it keeps track of the last active substate when a superstate is exited, so the execution restarts from that substate when the superstate is re-entered. For instance, observe a simple CPU model in figure 3.3.

In the model there is a superstate called running, containing two sub-charts called Normal mode and Overclock mode, there is also a non-structured state called idle. Basically, when the CPU is running, it can be either in

(35)

Nor-Figure 3.2: Simulink StateCharts: SubChart example

Figure 3.3: Simulink StateCharts: SubChart- History notation example mal mode or in OverClock mode. The first time when the running state is entered, the normal mode state is entered due to the default transition. If the OverClock modeOn event is triggered, the CPU transitions to the Over-Clock state. The next time the running state is entered, the active state will be OverClock, because it was the last active state. In Statecharts, be-haviour may be more elaborate than in Mealy-Moore FSMs. Transitions can have actions, just as they do in Mealy FSMs. Additionally, states may have both entry and exit actions. Entry actions are operations that are performed when the state is entered. Exit actions are performed when the state exits. This rich behavioural modelling allows efficient representation of a wide set of behaviours. An other interesting feature in StateCharts are connective junctions. Connective junctions are decision points in the system. Tran-sitions connected to junctions are called transition segments. TranTran-sitions, apart from default transitions, must go state to state. However, once the

(36)

transition segments taken complete a state to state transition, the accumu-lation of the transition segments taken forms a complete transition. Observe the example in figure 3.4.

Figure 3.4: Simulink StateCharts: SubChart- Junction example The transition executes as follows:

• If CPU temperature exceeds the limitOne, the condition is true, the action is executed and the default transition to the top junction is taken.

• Then, if CPU temperature exceeds also limitTwo the CPU frequency is further lowered.

• Otherwise, no further actions are executed.

The above steps describe the execution of the example diagram for con-nective junctions with Stateflow semantics.

Finally, StateCharts support also parallel state. Parallel (AND) state decomposition for a superstate is indicated when its substates have dashed borders. In figure 3.5, when state S is active, S1 and S2 are both active at the same time.

(37)

(38)

Chapter 4 PVSio-web: a tool for

prototyping device interfaces in

PVS

4.1 Introduction and motivation

Section 2.1 describes briefly PVS. The description given there is just a hint, PVS is a complex subject and it takes time to become familiar with it. PVSio-web is a tool developed at Queen Mary University of London1. The software has the purpose to break down barriers between the PVS system and engineers. At the beginning it was designed to extend one component of PVS, i.e., PVSio. PVSio provides a prototyping environment that allows one to explore the behaviour of a PVS specification. Using PVSio, developers can enter commands and execute PVS specifications. Exploring the behaviour of a specification is useful for debugging purposes and for discussing the speci-fication before verifying it in the PVS theorem prover. The main problem is that using PVSio sometimes is hard, in fact a list of nested commands must be provided for evaluating functions and the result could be a long list of fields. A more natural way of exploring the behaviour of a user interface is by means of interactions with buttons and keys on a user interface, this was the first purpose of PVSio-web. Also PVSio-web is extended by Emulink, one of its plugins. Through Emulink, PVSio-web gives users the opportunity to develop PVS specification starting from a stateChart based notation2. Emulink is shown and explained in detail in chapter 5. In the following

sec-1

http://www.eecs.qmul.ac.uk/˜masci/

2_{As explained in section 5 Emulink supports just a subset of the whole StateChart} notation

(39)

tion, the PVSio-web architecture is shown, and its prototype builder plugin is described. Also an example which shows how to prototype a device user interface is provided.

4.2 PVSio-web architecture

PVSio has a client server architecture. The client presents the graphical front-end of the tool as an interactive web page within a web-browser, this implies that to use PVSio-web a user just needs a modern web-browser able to execute JavaScript code. A web-server encapsulates the tool back-end, based on NodeJS. A process in the web-server is dedicated to PVSio for executing the PVS specification on-demand. Other processes are executed on the web-server for additional functionalities, such as type-checking the PVS specification and creating PDF report. PVSio-web follows the SaaS (Software as a Service) paradigm, it means that the server can be installed in a machine connected to a network and clients can use PVSio - web service using a thin client. Also server and client can be run in the same machine. It should be noted that PVS is available just for Unix machines, using PVSio-web this limitation is overcome, in fact clients running Microsoft OS can connect easily to the Server which acts as an interface. Figure 4.1 shows the PVSio-web client server architecture. In the following, client and server are

Figure 4.1: PVSio-web: Client Server architecture described in detail.

(40)

4.3 PVSio-web: Client

Client GUI

The client front end is shown in figure 4.2

Figure 4.2: PVSio-web: Client front-end

At the top, there is a toolbar which allows the user to manage a PVSio-web project, creating, saving and restoring projects. Projects data are lo-cated in the server machine. The dashed rectangle, is the one where a picture of the user interface layout can be loaded. This is covered in detail in 4.3.1 and also in section 4.5.

In the GUI there are also three expandable areas:

•

PVS Editor.

•

Visualisation of State Transition Diagram.

•

StateChart Editor.

The PVSio-web editor relies on Ace3, which is an embeddable code editor

(41)

written in JavaScript. It matches the features and performance of native editors such as Sublime, Vim and TextMate. By using the PVSio-web editor, a developer can also typecheck the PVS specification without opening PVS itself.

Figure 4.3 shows PVSio-web editor.

Figure 4.3: PVSio-web: Editor

Visualisation of State Transition Diagram is a new experimental sub tool of PVSio-web which is designed to create a graph starting from PVS states when a simulation is running. Basically, each node of the graph is a PVS state, studying this graph and how nodes are connected, some conclusions about the device design can be drawn. the StateChart Editor area is related to Emulink and as already said, it is described in detail in the next chapter. Client Architecture The PVSio-web client is entirely written in JavaScript and it has a modular architecture. This allows adding new functionalities without having problems with the old ones. Also, it implies that different functionalities can be developed in parallel. Currently, the PVSio-web client is composed by four main modules:

•

Prototype builder.

•

PVSio-web Editor.

•

Visualisation of State Transition Diagram.

(42)

PVSio-web modularity relies on RequireJS4. It is a well known JavaScript module and file loader which is supported in the latest versions of popular browsers. By using RequireJS code is separated into modules, each of them handles a single responsibility.

The PVSio-web main JavaScript file registers plugins by using RequireJS. Each plugin creates dynamically its own html content which occupies a por-tion of the whole PVSio-web html page. There is no dependence between the various plugins, this means for instance that Prototype builder can run even if Emulink is not loaded.

Figure 4.4 summarizes the client architecture.

Figure 4.4: PVSio-web: Client Architecture

4.3.1 Prototype builder

Prototype builder is formed by a user interface (UI) builder and a simu-lator. The UI builder allows designers to load a picture of the user interface layout, and bind interactive areas of the layout to function calls in a PVS specification. Two types of interactive areas can be defined: button areas, which are input elements whose behaviour is specified by functions in the PVS specification, and display areas, which are output elements whose value is specified in the state of the user interface defined in the PVS specification.

(43)

The Ui simulator allows designers to explore the behaviour of the user inter-face through point-and-click interactions. When the user clicks on a button a PVS function is invoked, it will be executed at the server side through PVSio. The server returns the result of the execution to the client and after parsing, the corresponding display areas are properly updated.

4.4 Server

The server back-end is a web-server. It hosts processes executing PVS and PVSio on demand. PVS is used for type-checking the PVS specification of the device user interface, PVSio is used for executing the same PVS spec-ification. The server is written in JavaScript and runs in Node.js5. Node.js is a software platform for scalable server-side and networking applications. It is built on Google’s V8 JavaScript engine[25]. The execution model of the platform is event driven with asynchronous, non blocking function calls. Using Node it is possible to spawn processes and access their output, this mechanism is used in PVSio-web to get PVS/PVSio results. The server exchanges messages with the client using WebSockets, which is a protocol intended for use on the web to enable bidirectional communication. The payload messages is specified in JavaScript Object Notation (JSON) format6.

4.5 Example: prototyping the data entry

sys-tem of a POS

We now demonstrate the capabilities of the PVSio-web prototype builder plugin through an example based on a POS. In particular, the PVS specifi-cation used in this example is the same as in the example provided in section 2.2.4. A picture of the POS is shown in figure 4.5. It is a typical POS, in particular in this example just digit buttons and ’OK’ button (green button) are taken into account.

For prototyping the device user interface described above, the designer performs the following steps in the UI builder of PVSio-web. A picture of the device user interface is loaded in the PVSio-web front-end, and the associated PVS specification defining the interactive behaviour of the user interface is typed in or loaded in the UI specification editor of PVSio-web. The designer then defines interactive areas over the loaded picture. For each interactive

5_{http://nodejs.org/} 6_{http://json.org/}

(44)

Figure 4.5: POS used in this example

area: a rectangle that surrounds a desired area of the picture is selected by click and dragging the mouse pointer; the intended type of area is specified (either button or display); buttons areas are bound to functions defined in the PVS specification; display areas are bound to terms in the PVS specification that model the state of visible elements on the user interface. For instance, to create the display element of the POS, the designer creates an area around the display element by clicking and dragging the mouse pointer. By doing so, a contextual menu for setting the binding options of the area is displayed by PVSio-web. The area type is display in this case, also the area identifier (Display Name) is display. We also need to set other two fields:

•

Value Type.

•

Regex.

The Value Type field is used in order to indicate the type of the display field in the PVS state returned by the server during a simulation. In our example, it should be set to String and then the regex, automatically created, should be slightly modified as follows:

display:="(\w+)"

The regex is used by web for parsing messages returned by the PVSio-web back-end. In this case, the PVSio-PVSio-web client, after receiving a message by the server, will search for the string

display:=”(

followed by one or

(45)

more word characters (i.e.,

\w+

), followed by

)”

. Figure 4.6 summarizes the steps described above. Note that Cursor name field should be left blank in our example.

Of course, also the digit buttons interactive areas need to be defined. Here

Figure 4.6: Display area fields

the steps to define the interactive area related to the digit ”1”:

•

Create an area around the button ”1”.

•

click on button tab. In the menu that will open, set:

•

Base Function Name: digit(1).

•

Bind Events: Click.

To create interactive areas for the rest of the digits, the task is the same as just explained except for the Base Function Name which is to be set digit(n) where

0 <= n <= 9

. Finally, we need to set the interactive area for the OK button. The task is the same as above except for the Base Function Name which is to be set as follows

OK

Picture 4.7 shows the OK Button setting.

After defining interactive areas with the UI builder, the UI simulator of PVSio-web is used for exploring the behaviour of the device. The designer can interact with button areas and observe changes in display areas. In

(46)

Figure 4.7: Setting of the OK BUTTON

particular, the designer can digit a PIN and then press on OK button, the device display is updated according to the correctness of the PIN just digited. Figure 4.8 shows the device after that user has typed seven and four.

(47)

4.6 Conclusions

In this chapter PVSio-web has been described. It is a tool with the purpose to break down barriers between engineers and PVS system. In par-ticular, its Prototype builder plugin has been shown and an example based on a POS has been provided. It should be noted that the PVS specification used to explore the POS behaviour has been previously developed and then loaded to run the simulation. This was a PVSio-web limitation because de-veloping PVS specification can be a task which requires time and experience. Emulink overcomes this limitation. It helps users to create PVS specifica-tion starting from Emuchart notaspecifica-tion. This way, PVSio-web becomes a tool useful both to create PVS specification and explore them using interactive areas. Emulink is described in detail in the next chapter.

(48)

Chapter 5 Emulink

Emulink allows software engineers to develop formal PVS specifications1

by using a graphical formalism called Emucharts. Emucharts is a graphical language similar to StateCharts2_{. Emulink presents itself as a typical}

Stat-echarts editor environment with functionalities such as creating nodes and adding transitions. It has been designed to reduce the barriers that prevent non-experts in formal methods from creating PVS specifications. Also, after creating a PVS specification a simulation can be run, exploiting the PVSio-web prototype plugin as explained in section 4.3.1. During the simulation the current and the previous Emucharts states are highlighted, this way users can follow the device behaviour just looking at the diagram. Finally, an other Emulink feature is the possibility to visualize a PVS specification, it means that a PVS specification can be displayed in the form of Emucharts.

In the following we describe its design and implementation, describing its main components.

5.1 Introduction and motivation

Safety-critical systems must be verified against safety requirements be-fore being marketed. The use of formal methods has been largely neglected by manufactures, this is mainly due to barriers created by verification tools. For instance, PVS relies on Emacs3 _{to write specifications, it is a text editor}

having syntax highlighting and pretty printer function to format code and makes it easier to read and understand. Emacs has no features to help in writing PVS specifications.

1_{PVS is described in section 2.2}

2_{Statecharts modelling tool is described in section 3.1} 3_{http://www.gnu.org/software/emacs/}

(49)

A more natural way of modelling reactive system is to use a graphical for-malism similar to Statecharts, which is very appealing to engineers.

5.1.1 Emulink, an overview

Emulink extends PVSIO-web [22], with an environment that allows users to:

• Model system using Emucharts notation.

• Create PVS specification starting from Emucharts notation. • Visualize PVS specification in the form of Emucharts notation. • Animate the diagram when a simulation is executed.

Figure 5.1 shows the Emulink system architecture, where we can identify the main Emulink modules.

Emucharts editor module (EEM) allows users to create a model of a system by using Emucharts notation.

Emucharts specification is translated into PVS specification by the Translator module (TM) which writes the specification in the PVSIO-Web embedded editor.

Specification parser module (SPM) is responsible to create an Emucharts diagram starting from a PVS specification which can be either pasted into editor, or got by a file specified by user.

Finally, Emucharts Animation module (EAM) highlights an Emucharts node depending on the actual PVS state, when a simulation is running.

The next sections cover the following topics:

• Emulink architecture, in particular how Emulink fits with PVSio-Web. • Emucharts Editor description.

• Translator description.

• Specification parser description. • Emucharts Animation description.

(50)

Figure 5.1: Emulink: Blocks System

5.2 Emucharts Editor

Emucharts is a graphical language which allows users to draw: • States. • Transition. • Self transition. • Default transition. • Transition Condition. • Transition Action.

The current set of the supported graphical objects has been sufficient for our purposes of modelling. However in future work the subset will be extended by features such as parallel states and connective junctions. The next sections contain the following topics:

• Description of the steps to create a new diagram.

(51)

5.2.1 Creating an Emulink model

A new empty Emulink Diagram can be created by the following steps: • Open the Statecharts editor area clicking on the plus like in figure 5.2. • Hover the mouse over the ’MAIN MENU’.

• Click on ’Create New Diagram’ button.

Figure 5.3 summarizes the last two steps just described.

Figure 5.2: Emulink: Opening the Statechart Editor Area

Figure 5.3: Emulink: Creating a new Emulink model

5.2.2 Using the Emucharts Editor

This section describes each part of the Statecharts editor. Emucharts Editor Window

Emucharts Editor has the appearance shown in figure 5.4. The Emucharts editor window includes the following elements: Menu bar All editor commands are available from the menu bar.

(52)

Figure 5.4: Emulink: Statecharts Editor

Toolbar The toolbar contains buttons to create states and transitions as well as to handle the zoom of the drawing area.

Status bar Displays information about the Emulink activation.

Properties bar Displays information about the graphical object just clicked. Debug panel Shows inconsistencies between the PVS code generated and

the diagram (if any)

Drawing area It is the area where the Statechart has to be drawn. Using states in Emucharts Editor

This section describes how to create and specify a state in a chart and contains the following topics:

• Creating a state. • Editing a State Label. • Deleting a State.

(53)

Creating a State

There are two ways to start the creation of a new State: 1. Click on ’New State’ button in the toolbar.

2. Mouse hover on ’Editor Menu’ in the Menu bar, mouse hover on ’State Editor’, then click on ’New State’ button.

At this point to create the new state just click on any point of the ’drawing area’. A new state will be created with a default name.

Editing a State label

Initially, a state has a default label. To change it:

1. Select the state (left click on it).

2. Hover the mouse on ’Editor Menu’ in the Menu bar, mouse hover on ’State Editor’, then click on ’Edit State Label’ button.

3. Type the new label and then press ok. Deleting a State

To delete a node:

1. Select the state (left click on it).

2. Hover the mouse on ’Editor Menu’ in the Menu bar, mouse hover on ’State Editor’, then click on ’Delete State’ button.

Moving and resizing a state To move a state, do the following:

• Left-click and drag the state. • Release it in a new position. To resize a state, do the following:

• Place the cursor over the corner at the bottom right of the state (the cursor will change).

• Left-click and drag the state’s corner to resize the state. • Release the left mouse button.

(54)

Using Transitions in Emucharts Editor

This section describes how to create, change, and specify properties for Emulink transitions:

• Creating a Transition.

• Creating a Self-Loop Transition. • Deleting a Transition.

• Editing a Transition label.

• Adding a Condition in a Transition. • Adding an Action in a Transition. Creating a Transition

There are two ways to start the creation of a new transition between two states:

1. Click on ’new transition’ button in the toolbar.

2. Mouse hover on Editor Menu in the Main bar, mouse hover on Transi-tion Editor, then click on ’transiTransi-tion’ button.

After that the following steps need following: 1. Place the cursor on the source state.

2. Click and drag a transition to a destination state. 3. Release the mouse click.

This way, a new transition is created with a default label.

Creating a Self-Loop Transition A self-loop transition is a transition whose source and destination are the same state. The following steps need following:

1. Mouse hover on Editor Menu in the Main bar. 2. Mouse hover on Transition Editor.

3. Click on ’Self-Transition’ button. 4. Click on a State.

Emulink: a graphical modelling environment for PVS

Emulink:

a graphical modelling environment for PVS

Contents

List of Figures

Chapter 1

Introduction

Chapter 2

The Prototype Verification

System

2.1

Introduction

2.2

PVS environment

2.2.1

Theories

2.2.2

Declarations

2.2.3

Expressions

2.2.4

PVS Theory: an example

2.3

PVS: parsing, typechecking and

explor-ing the specification

2.3.1

Parsing the specification

2.3.2

Typechecking the specification

2.3.3

Exploring the specification

Chapter 3

StateCharts

3.1

Introduction

3.2

Finite State Machine

3.3

Problems with Classical FSMs

3.4

StateCharts

Chapter 4

PVSio-web: a tool for

prototyping device interfaces in

PVS

4.1

Introduction and motivation

4.2

PVSio-web architecture

4.3

PVSio-web: Client

•

•

•

•

•

•

4.3.1

Prototype builder

4.4

Server

4.5

Example: prototyping the data entry

sys-tem of a POS

•

•

display:="(\w+)"

display:=”(

\w+

)”

•

•

•

•

0 <= n <= 9

OK

4.6

Conclusions

Chapter 5

Emulink