Safety Analysis Using Coloured Petri Nets

Safety Analysis Using Coloured Petri Nets

Seung MO Cho, Hyoung Seok Hong, and Sung Deok Cha Department of Computer Science

Korea Advanced Institute of Science and Technology (KAIST) 373-1, Kusong-dong,

Yusong-gu,

Taejon, Korea

E-mail: { seung,hshong,cha) @salmosa.kaist .ac.kr

Abstract

I n this paper, we propose a safety analysis method using coloured Petri nets (CPN). Our method employs a backward approach where a hazard is assumed to have occurred and backward simulation from the hazard is performed in order to determine i f and how the hazard might occur. Using CPN, we define a hazard as a set of markings and perform backward simulation by gen- erating a reachability graph backwards f r o m the hazard.

To facilitate our safety analysis, we extend the seman- tics of C P N and define backward reachability graphs of CPN. To demonstrate our method, a shutdown system for a Korean nuclear power plant is used as an exam- ple.

1.

Introduction

Software control in safety-critical systems such as aerospace, military, nuclear power plant, and medical applications has become increasingly common in re- cent years. For example, many countries operate nu- clear power plants, and some, including Korea, are de- veloping software-based emergency shutdown systems.

Should emergency situations such as reactor overheat- ing occur, software is required t o initiate emergency shutdown procedures while maintaining the plant in a safe state. When software is used as a control agent in these systems, safety becomes a paramount concern.

In the worst case, software malfunctions, i.e., unsafe software control outputs can result in serious and un- acceptable consequences such as death, injury, or envi- ronmental damage. In order to ensure safety require- ments, developers of safety-critical systems should de- sign a model and analyze its behavior before the system is actually developed.

Petri nets[l2, 131 have been extensively studied since its invention in the early 1960s and have proven to be effective in modeling and analyzing the behaviour of concurrent and asynchronous systems. Various analy- sis techniques for Petri nets have been developed and

they include forward reachability, invariants and per- formance analysis. Forward reachability analysis starts from a known initial marking and identifies all the markings that a system can possibly reach as well as the necessary conditions and event sequences that lead to each marking. However, forward reachability anal- ysis is not effective when performing safety analysis because:

0 Brute-force generation and analysis of the entire reachable state spaces is often impractical. Fur- thermore, unless the system is inherently unsafe, almost all the states in forward reachability graphs will be considered safe, and thus “uninteresting”

from a safety viewpoint.

Claims on software safety can be established by demonstrating that all the states in forward reach- ability graphs are safe. But the same claim can be made more effectively by proving that un- safe states are unreachable. Hence, backward reachability analysis and proof-by-contradiction approach are often employed in performing safety analysis.

For these reasons, several methods for analyzing safety-critical systems employ a backward approach where a hazard is assumed to have occurred and the events and conditions of the system which might lead to the hazard are identified. FTA (fault tree analysis)[16] and SFTA (software fault tree analysis)[7, 2, 91 are some of the most frequently used methods in industry. In [SI, Leveson and Stolzy proposed a safety analysis method using primitive Petri nets, i.e., Place/Transition nets. In their method, starting from a marking which is assumed t o be hazardous, immedi- ate predecessor markings are generated backwards and each of them is examined t o see whether it is a criti- cal state. A critical state is one in which the system had multiple paths where subsequent states include not only a hazardous state but also a safe one. After iden- tifying critical states, their method modifies Petri nets with interlocks or timing constraints in order t o elim-

inate the unsafe paths from the critical state to the hazard.

In this paper, we propose a safety analysis method using coloured Petri nets (CPN) [4, 5 , 61. These are now in widespread use for many real-world applica- tions. The main reason for the success is that they have more expressive powers than primitive Petri nets while providing formal semantics and the same degree of the- oretical analysis power. Although various techniques such as forward reachability analysis[l, 6, 11, 1'51 and invariant analysis[l4] have been proposed, there have been few research efforts on safety analysis for CPN.

The goal of our method is t o determine whether a system is free from a hazard, i.e., all the status of a system cannot reach a hazard. When the system is not free from a hazard, our method also identifies the events and conditions which can lead t o the hazard.

The basic procedure of our method is t o assume that the hazardous status has occurred and then to work backwards t o determine the set of possible causes for the status t o occur. Using CPN, we define a hazard as a set of markings and perform backward simulations by generating reachability graphs backwards.

Our paper is organized as follows: Section 2 briefly reviews the syntax and semantics of CPN. Section 3 introduces a shutdown system for a Korean nuclear power plant as a case study. Section 4 extends the semantics of CPN with symbolic markings with don't care conditions. Section 5 defines backward reachabil- ity of CPN based on the extended markings. Section 6 presents our safety analysis method using SDS2 as an example. Finally, Section 7 concludes the paper.

2. Coloured Petri Nets

CPN extends Petri nets by allowing tokens to be as- sociated with colours, i.e., data types using a functional programming language, SML. Additionally, transitions and arcs can be augmented with guards and expres- sions, respectively. The readers may refer to [5, 61 for the formal syntax and semantics of CPN.

We require a notation for multisets t o describe CPN.

Let N denotes the set of all non-negative integers. A multiset m , over a non-empty set S, is a function from

S

t o N . If m, m l , m2 are multisets over S and n E N , then Addition, scalar multiplication, comparison, and subtraction of multisets are defined as follows:

vs E

s

^{: (m1}

+

m z ) ( s ) = m1(s)

+

^mz(s)

0 vs E

s

^{: ( n}

^*

m ) ( s ) = n

*

m(s)

0 m1 I m2

*

^{vs E}

^s

^{: ml(S) 5 m2(s)}

0 Vs E S : (mz - ml)(s) = m2(s) - ml(s) when Definition 2.1 A coloured Petri net is a tuple (E, P , T , A, N , C , G , E ) where

ml

5

m2

0 C is a finite set of non-empty types, called colour

0 P is a finite set of places.

0 T is a finite set of transitions.

0 A is a finite set of arcs.

0 N is a node function from A into P x T U T x P .

0 C is a colour function from P into

C.

0 G is a guard function from T into guard expres-

0 E is an arc expression function from A into arc sets.

sions.

expressions.

The colour function

C

associates a colour for each place. This implies that all the tokens in a place p can have only values whose type is C(p). The guard function G associates a condition for each transition which should be satisfied in order for the transition t o be fired. The arc expression function E associates an expression for each arc. The colour type of each expres- sion must be equal t o the colour set that is attached t o the corresponding place.

The followings are notations used for the definition of the dynamics of CPN. Let t be a transition and

( ~ 1 , ~ 2 ) E P x T U T x P.

0 I n ( t ) = { p

I

3a : N ( a ) = ( p , t ) } .

0 O u t ( t ) = { p

I

3a : N ( a ) = ( t , p ) } .

0 A ( t ) = { a E A I 3 p E P : N ( p , t ) = a V N ( t , p ) =

0 V a r ( t ) = ^{U

I

v E V a r ( G ( t ) ) V 3a E A(t) ^: v E a}.

V a r ( E ( a ) ) }

0 A(51,22) = { a E A

I

N ( a ) ⁼ (x1,z2)).

The global state of a system is defined in terms of marking which represents a distribution of tokens on the places. In CPN, the marking of each place is a multiset over the colour set attached to the place.

Definition 2.2 A token element is a pair ( p , U ) where p E P and v E C ( p ) . A marking M is a multiset over the set of all token elements.

In CPN, there exist variables in guards and arc ex- pressions. When a transition is t o be fired, these vari- ables should be bound t o specific values according to their colours. For each binding, we can check whether the transition, with that binding, is enabled in the cur- rent marking. Let v be a variable, T y p e ( v ) be the type of variable v and expr be an expression.

Definition 2.3 A binding b of a transition t is a func- tion defined on V a r ( t ) such that

Vu E V a r ( t ) : b(w) E Type(w) and G(t)(b).

where expr(b) denotes the evaluation of the expression expr in the binding b.

A binding element is a pair ( t , b) where t E T and b is a binding of t .

Definition 2.4 A binding element ( t , b) is enabled ixi a marking M iff

When a binding element ( t , b) is enabled in a mark- ing M I , it may fire changing the marking M I into M2 defined by:

\JP E p : M l b ) - E(P, t ) ( b )

+

E(t,P)(b).

We say that M2 is reachable from M I by the occur- rence of ( t , b ) .

3.

A Case Study: Wolsung SDS2

To demonstrate our method, we use a shutdown sys- tem (SDS2) for a Korean nuclear power plant as a case study. SDS2 monitors the state of a nuclear reactor such as pressure and power and generates a trip signal (shutdown) if the nuclear reactor becomes unsafe, i.e., the pressure is too high or too low. There are several trip parameters in SDS2 and we describe only PDL trip parameter. Fig. 1 shows a CPN for PDL trip parameter of SDS2.

To control the PDL trip parameter, SDS2 monitors the status of the nuclear reactor such as core differential pressure, A P and log power signal,

4 ~ 0 ~ .

In Fig. 1, the places Pressure and Power represent the current value of A P and +LOG, respectively. PI, ^{P 2 ,} and P3

represent the states of SDS2, respectively. PDLTrzp represents the PDL trip parameter whose value is de- termined as follows:

0 Determine the trip conditioning status: If $LOG

<

2739mV, disable the trip. Otherwise enable the trip.

0 Determine the PDL trip parameter: If the trip conditioning is enabled and ( A P

I

1287mV or A P 2 4810mV), open PDL trip parameter. Oth- erwise, close PDL trip parameter.

4. Symbolic Markings with Don’t Care Condition in CPN

We use CPN t o analyze safety properties of software in order t o determine if and how software can reach a hazard. In CPN, we can describe a hazard with a set of markings. For example, a hazard in SDS2 is defined as

MV Pressure

prev-m

R

t l 0

I 0 t2

I

TRIP

color MV = int with 0..5000; (* Pressure and power *) color PL = low I normal I ^{high; (*} Pressure level *) color CL = enable I disable; (* Conditioning state *) color SW = product PL * ^{CS; (*} Software state *) color TRIP = open I close; (* PDL trip *) var m, prevni : MV;

var p, prevq : PL;

var c, prevl: : CS;

var c, prevA : TRIP;

(* Determine pressure level *) fun Fl(ni) = if p 5 ¹²⁸⁷ then low

else if p 2 4810 then high else normal;

(* Determine conditioning state *) fun F2(m) = if m < 2739 then disable

else enable;

(* Determine PDL trip parameter *)

fun F3(p, c) = if (p = low or p = high) and c = enable then open

else close:

Figure 1. A CPN for PDL trip parameter

“When ( A P

5

1287mV or A P 2 4810mV) and +LOG 2 2739mV and the PDL trip pa- rameter is closed”

and there exist several markings which represent the hazard in Fig. 1:

(Pressure, 1)

+

(Power, 3000)

+

( P D L T r i p , close), (Pressure, 4900)

+

(Power, 4000)

+

( P D L T r i p , close),

When defining a hazard using CPN, there are two challenges which should be considered. The first one is that we might consider too many or infinite number of markings which represent a hazard in CPN. For ex- ample, the tokens in the places Pressure and Power in Fig. 1 can have an integer value from 0 t o 5000. In general, it is not practical t o analyze all the markings

which represent a hazard when the type of tokens is integer or enumerated types, and it is impossible when tokens can have an infinite range such as real numbers.

The second one is that we need a different way of in- terpreting the meaning of markings. Consider a mark- ing M = (Pressure, 1)

+

^{(Power, 3000)}

+

^(PDLTrip,

dose) which is one of the markings representing the hazard. When defining the hazard, we are only inter- ested in the fact that there exist tokens in the places Pressure, Pourer, and PDLTrip and we do not care whether or not there exist tokens in other places P I , P2, and P3. For example, consider another marking M‘ = M

+

( P I , lour). We interpret that M’ is also a hazard, because we do not care the current tokens of PI when defining the hazard.

To resolve the first challenge, we extend the seman- tics of CPN with the concept of symbolic markings.

Intuitively speaking, a symbolic marking represents a set of markings and is described by a predicate of sym- bols. We denote

C

as a symbol and Type($) as the type of 6.

Definition 4.1 A symbolic token element is a pair ( p , 6) such that p E P and $ is a symbol whose type is C ( p ) . A symbolic marking S M is a pair ( M , D) such that

0

d!

is a multiset over the set of all symbolic token

0

b

^{is a} predicate over the set of all symbols.

For example, we can define a set of markings which represent the current values of A P satisfying ( A P

5

1287mV or A P 2 4810mV) using a symbolic marking SMo =

(k, D)

such that

elements.

k o

⁼ (Pressure, 2 ) and

Do

= ( 2

5

1287 V 2

2:

4810).

Definition 4.2 Let SV be the set of all symbols. A mng

P

of a symbolic marking SM =

(Ak, 6 )

^{is a}

function defined on SV such that

V 6 ^E SV: p(6) E _Type(+) and &3)

where

h(P)

denotes the evaluation of D in the fixing

P.

For example, from the symbolic marking SMo, we get a marking (Pressure, 1) with the fixing

0

such that p(2) = 1.

Definition 4.3 Let S M =

(k, h)

^be a symbolic marking. A denotation of a symbolic marking S M is a set of markings V ( S M ) such that

V ( S M ) = { M

I

^{M =} A ~ ( P ) ^A

P

is a fixing of S M ) .

where M ( P ) denotes the evaluation of in the fixing

A denotation of a symbolic marking is the set of markings which the symbolic marking denotes. For example, the denotation of SMO is

{(Pressure,

P) I

⁽²

5

1287 V

P 2

4810)).

P.

To resolve the second challenge, we introduce the concept of don’t care condition ^as follows:

Definition 4.4 Let M be a marking and N E ( M ) C P is a set of places such that { p

I

M ( p )

# 0).

A marking with don’t care condition ( M , *) is a set of markings such that

{M’

I

^{v p E} N E ( M ) : M ’ ( p ) = M ( p ) } Intuitively, (M, *) represents all the markings which have the same tokens as M at the places in N E ( M ) and have any tokens at the places not in N E ( M ) . Finally, we conbine the concepts of symbolic marking and don’t care condition as follows:

Definition 4.5 Let S M = (ilk,

6 )

be a symbolic marking and N E ( & ) C P is a set of places such that { p

I

^Ak(p)

# 0).

A symbolic marking with don’t care condition ( S M , *) is a set of symbolic markings

{(A&

6 ) I

v p E N E ( & ) : &’(p) = k ( p ) ) Now we can define the hazard in SDS2 as a symbolic marking with don’t care condition (SMh, *) where SMh = (Mh,

fib)

such that

i f h = (Pressure, 2 )

+

(Power,

9) +

(PDLTrip, ?), Dh = ( 2

5

1287

v

2 2 4810) A

9

2 2739 A f = Close.

5. Backward Reachability in CPN

In this section, we define backward reachability t o generate a backward reachability graph from a hazard.

Intuitively, backward reachability is a dual concept of (forward) reachability, that is, if a marking M2 is reach- able from M I , we say that M I is backward reachable from M2. By backward reachability, we mean that M I is a cause or pre-condition of M2. For example, con- sider a marking MZ = ( p 2 , 2 )

+

^{( p 3 , 0)} in Fig. 2. M2 is reachable from M I = ( P I , 1) and we say that M I is backward reachable from M2.

However, when defining backward reachability of symbolic markings with don’t care condition, it is more complicated. There are two challenges which should be considered when defining backward reachability. The first one is that we should bind a transition with sym- bols not with specific values. In CPN, variables in the guard and arc expressions of a transition are bounded

l a

int int

Figure 2. An example of CPN

to a specific value when the transition is fired. For ex- ample, when we consider t l in Fig. 2 , a is bounded t o 1. However, in our method, variables in a transition should be bounded to symbols, because a marking in CPN is extended with symbols. For example, if we consider a symbolic marking SM1 = ( ( P I , ? I ) , -10

<

21

<

10) in Fig. 2, the variable a should be bounded to a symbol not t o a specific value.

Definition 5.1 A symbolic binding

b

of a transition t is a function defined on V a r ( t ) such that

Vu E V a r ( t ) : 6(v) is a symbol whose type is T y p e ( v ) . A symbolic binding element is a pair ( t , b ) where t

E T and

b

is a symbolic binding of t.

We denote that a symbolic binding

6

^{as [VI t} 61,

I J ~ +- 02,

...,

^{21, +-} dn] where E V a r ( t ) and 8 j is a symbol for 1 2 i 2 n.

The second challenge is that we should consider don’t care condition when defining backward reacha- bility. Consider a marking M3 = ( B , 2) in Fig. 2 . M3 is not reachable from M I = ( P I , 1) because M33p3) =

0,

i.e., there exist no tokens at p3 in the marking M3.

However, when considering markings with don’t care condition, the situation is different. Suppose that we define a hazard as a marking with don’t care condition

( M 3 , *). That is, if there is a token 1 in p2, then the status of the system is hazardous regardless of the to- kens in p l and p s . After defining the hazard, we want to know if and how the hazard might occur, i.e., causes or pre-conditions of the hazard. In Fig. 2, the hazard can occur when the current marking is M I and t l is fired. Note that ( M 3 , *) is a set of markings which contains M2 = ( p z , 2)

+

^{( p 3 , 0)} that is reachable from M I , Therefore, there exists a case where it is reachable from MI to one of the markings in (M3, e ) , i.e., M2.

This implies that it is possible that the status of the system can change from M I into ( M 3 , *) and we regard M I ^as a cause of the hazard.

Let

t

be a transition and S M =

(k,

D ) be a sym- bolic marking. We adopt the following notations t o define backward reachability.

O ut l(t ,

if)

= { p

I

^{p E} out(t) A if(p)

#

fl}

0ut2(t, &f) = { p

I

^{p E} out(t) ^{A if(p)} =

0)

Intuitively, Outl(t,

if)

is a set of places where don’t care condition is not considered and Out2(t,

k)

is a set of places where don’t care condition should be consid- ered. For example, consider a symbolc marking SM3

= ( 6 3 , b3)

=

( ( p z , 3z), 2 2

<

10) in Fig. 2 . Then, Outl(t1, $ 3 ) = { p z } and Out2(t1, ^{$ 3 )} = { p 3 } . Definition 5.2 Let S M =

(k, D ) ,

SM’ = (A?’,

D’)

be symbolic markings and ( t ,

6)

be a symbolic binding element. SM‘ is backward reachable from ( S M , *) with the occurrence of ( t ,

6)

iff

v

p E ( P - Out2(t,

if)):

v

p E Out2(t,

k): Gyp)

= E ( p , t) ( 6), k ’ ( P ) = k ( P )

+

E(P,

t m

- E @ , P ) ( b ,

5’

=

fi

A G(t)(6) A Ijovt and

Bout

⁼

A

^{(8 =} & ? @ , p i ) ( & ) ) where ( p i , $ ) E

&f

Pi€OZLtl (t,n;r)

For example, consider a symbolic marking SM3 =

(k3,

&.)

= ( ( p ~ ,

az),

2 2

<

10) and a symbolic binding element ( t l , [a c

4)

in Fig. 2. We generate a symbolic marking SM1 =

(&I, fi,)

which is backward reachable from (SM3, *) as follows:

0 Calculate Outl(t1,

G3)

and OutS(t1,

G3).

Outl(t1, k 3 ) = { p 2 } , P - Out2(t,

if)

= { P I , p z } . 0ut2(t1, 6 3 ) = { p 3 } , and

0 Determine from A& and t l .

- For each place in { p l , p 2 } , h;r’(p) = &(p)

+

E ( P , t ) ( b ) - E ( t , P ) ( b ) .

f i l ( p 1 ) = & f 3 ( p l ) f t ) ( b ) - E ( t , pl)(6)

=

0 +

^B

- ⁰

= B,

m p 2 ) = G3(p2)

+

^E(p2, t ) ( b ) - E ( t , pz)(i)

= 22

+ 0

- ( B

+

1) =

0

- For each place in { p 3 } ,

kl

( p ) = E ( p , t )

( b ) .

f i l ( p 3 ) = E ( p S , t l ) ( b ) =

8

Determine f i 1 from b 3 and t l .

61 = 6 3 A G( t l) (6) A &)out where

6 3 = (22

<

10) and G ( t l ) ( & ) = (6

>

0) and

bout

= (22 = &

+

^1).

Finally, we define a backward reachability graph of CPN as follows:

Definition 5.3 A backward reachability graph of a CPN is a directed graph G = ( N , E ) such that

0 N is a set of symbolic markings.

0 E is a set of edges, (SM1, sbe, SM2) such that SM1, SM2 are symbolic markings and sbe is a symbolic binding element and SM1 is backward reachable from (SM2, *) with the occurrence of sbe.

Fig. 3 shows a backward reachability graph whose initial node is SM3.

Figure 3. An example of backward reachabil- ity graph

6. Safety Analysis Using CPN

As mentioned before, we perform safety analysis by defining a hazard as a set of markings and performing backward simulation from the hazard. More specifi- cally, in our method

A hazard is defined as a symbolic marking with

0 A backward reachability graph whose root node is We present our safety analysis method using Wol- sung SDSP as an example. Our method begins with the hazard represented as a symbolic marking with don’t care condition (SM h , *) where SMh = ( k h ,

fib)

and

don’t care condition.

the hazard is generated.

Figure 4. A part of the backward reachability graph for PDL trip parameter

Fig. 4 shows a backward reachability graph for PDL trip parameter. Starting from SMh, we can identify that all the transitions t l , t2, t3, and t4 in Fig. 1 can be executed backwards. That is, we can generate four symbolic markings SM1, SM2, SM3, and SM4 which are backward reachable from ( S M h , *). Let 6 1

= [prev-m ^t ml, m ^t m 2 ] and 6 2 = [prevm ^t r h 3 ,

m e &4]. S M I = (k1, 61) and SM2 = (A&,

h2)

are backward reachable from (SMh, *) with the occurrence of ( t l , & ) and ( t 2 , 62) such that

kl= (Pressure, ^{h 1 )}

+

(Power,

9) +

(PDLTrip, 2)

61 =

&

^{A ( 2} = ^m2)

SM3 and SM4 are generated with the occurrence of (t3, ^{6 3 )} and (t4, 6 4 ) where ^$3 = Iprevq ^t $ 1 , p ^t

&,

c t 21, prev-t ^t t*1] and 64 = [p $3, prevl: ^{t 2 2 ,} c

t 23, prev-t ^{t i2].}

k 3 = (Pressure, 2 )

+

^(Power,

⁹⁾ +

^{(PI, $ 2 )}

+

(P3, ^{( $ 1 ,} 2 1 ) )

+

^{(PDLTrip, t*1)}

b 3 =

bh

A ( k = F3(&7 6 1 ) )

k4= (Pressure, 5)

+

(Power,

6) +

( ~ 2 , 2 3 1

+

a 4 = Dh A (2 = F3($3, 2 3 ) )

From now on, we demonstrate only the expansion of SM3 due t o the limit of space. We can simplify D3

(P3, ($3, 2 2 ) )

+

^(PDLTTiP,

id

with unfolding the function F3 and eliminating symbols in D 3 which are irrelevant t o M 3 . For example, the symbol B in D 3 does not contribute t o any definition of symbols in A&. Therefore, we can eliminate

P

from

&

without loss of information.

h3

=

hh

^{A (2 =} F3($2, 61))

= ( 2

5

1287 V 2 2 4810) A

(6

2 2739) A

= ( 2

5

1287 V

2

4810) A

(6 2

2739) A

= ( 2

5

1287 V & 2 4810) A

(6

2 2739) A

( B = dose) A (2 = F3(&, &)) (dose = F3($2,

;I))

~ ( ( $ 2 = low V p2 = high) A C1 = enable) (eliminating 2)

(unfolding F3)

=

( 2

I

1287 V 2

2

4810) A (jj

2

2739) A (& = normal ^V 21 = disable)

Starting from (SM3, *), sM31, SM32, ^SM33, and SM34 are backward reachable from (SM3, *) with the occurrence of ( t l , 6 3 1 ) j ( t 2 , 6 3 2 1 , (tl, 6 3 3 1 , and ( t 4 , 6 3 4 ) ,

respectively. Among them, we only consider SM31 =

(.&I, 5 3 1 ) with &1 = b e v m + f i 5 , m +-- 73261.

i 1 3 1

=

(Pressure, r i 2 5 )

+

^{(Power, y)}

+

^{( P 3 , ($1, 21))}

+

(PDLTrip,

h)

6 3 1 = ^{D3 A} ( 2 = ^{f i 6} A ’$2 = F l ( m 6 ) )

I ( 2

5

1287 V 2

2

4810) A (y 2 2739) A

(& = normal V E1

=

disable) A ( 2 = ⁷³²⁶⁾ A

($2 = ^Fl(k6))

Note that 2 , kf3, and $2 do not contribute any def- inition of symbols in M 3 1 . Therefore, we can further simplify h31 as

=

(6

2 2739) A (21 = disable)

By h31, we mean that in SM3, it holds that

3

2 2739 A el = disable and there exist no constraints on f i g , e l , and t l , i.e., they can have any values.

Our method iteratively generates backward reach- able markings from each uncovered marking until the known initial marking of CPN has been arrived or it is impossible t o generate backward reachable markings further. It should be emphasized that the hazard need not be a marking that is ultimately reachable from the initial marking. In other words, if it is impossible to generate markings further, it implies that the hazard cannot be reached from the initial marking, hence the system is free from the hazard being analyzed. When the initial marking has been arrived from the hazard, we can identify the failure scenario that could lead to the hazard from the initial marking. Based on the fail- ure scenario, we can modify or re-design CPN and de- termine run-time assertions to prevent the failure sce- nario.

7. Conclusion

In this paper, the use of coloured Petri nets in ana- lyzing safety-critical systems has been described. The purpose of our safety analysis method is t o determine if and how the hazard of the system might occur and to provide safety analysts with deeper understanding on the failure scenarios of the system. We have identi- fied several challenges when performing safety analysis using CPN and resolved them as follows:

0 In general, a hazard is represented as a set of mark- ings in CPN. It is not practical or impossible t o generate a backward reachability graph for each hazard, because there exist too many or infinite number of markings which should be considered.

To resolve this, we have proposed symbolic mark- ings which denote a set of markings.

e When defining a hazard, we need a different way of interpreting the meaning of markings. Given a marking, we are only interested in the fact that there exist tokens in CPN as described in the marking and we do not care the existence or Val- ues of other tokens which are not described in the marking. To resolve this, we have defined don’t care condition and a hazard is defined as a sym- bolic marking with don’t care condition.

0 In order t o analyze a hazard, we have generated a backward reachability graph from the hazard.

When considering only simple markings, we can easily define backward reachability because back- ward reachability is a dual concept of (forward) reachability. However, it is more complicated due to the extensions of markings and we have defined backward reachability of symbolic markings with don’t care condition.

Our method can be used for analyzing safety-critical systems in several ways. First, by generating whole backward reachability graphs from a hazard, all fail- ure scenarios which contribute the hazard are identified and safety properties of a system can be verified. But in general, the complexity of a system prohibits one from generating whole backward reachability graphs.

Without the entire analysis, our method can be ap- plied for identifying run-time assertions or interlocks which monitor the status of a system and prevent a hazard from occurring. We can also identify safety- critical portions of a system when we generate back- ward reachability graphs.

References

[l] G. Chiola, C. Dutheillet, G. Franceschinis, and S. Haddad, “On Well-Formed Coloured Nets and Their Symbolic Reachability Graph,” in High-level

Petri Nets. Theory and Application, Springer- [16] W.E. Vesely, F.F. Goldberg, N.H. Roberts, and Verlag, pp. 373-396, 1991. D.F. H a d , Fault Dee Handbook, Reg. 0492, US [2] S.D. Cha, N.G. Leveson and T.J. Shimeall, Nuclear Regulatory Comm., Washington, D.C.

“Safety Verification in Murphy Using Falut Tree Jan. 1991.

Analysis,” in Proceedings of the 10th International Conference on Software Engineering, Singapole, [3] S.D. Cha, “AeSOP: An Interactive Failure Mode Analysis Tool,” in Proceedings ^of the 8th Com- puter Assurance, Gaithersburg, MD, pp. 9-16, 1994.

[4]

K.

Jensen, ‘Coloured Petri Nets: A High-level Language for System Design and Analysis,” in Ad- vances in Petri Nets 1990, Lecture Notes in Com- puter Science, Vol. 483, pp. 342-416, Springer- Verlag, 1991.

[5]

K.

Jensen, Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use. Vol. 1: Ba- sic Concepts, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1992.

[SI

K.

Jensen, Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use. Vol. 2: Anal- ysis Methods, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1994.

[7] N.G. Leveson and P.R. Harvey, “Software Fault Tree Analysis,” Journal of Systems and Software, [8] N.G. Leveson and J.L. Stolzy, “Safety Analysis Using Petri Nets,” IEEE l’ransactions on Soft- ware Engineering, Vol. 13, No. 3, pp. 386-397, Mar. 1987.

[9] N,G. Leveson, S.D. Cha, and T.J. Shimeall,

“Safety Verification of Ada Programs using Soft- ware Fault Trees,” IEEE Software, Vol. 8, No. 4, [lo] N. Leveson, Safeware: System Safety and Com-

puters, Addison-Wesley, 1995.

[ll] M. Lindqvist, “Parametrized Reachability Trees for Predicate/Transition Nets,” in Advances in Petri Nets 1993, Lecture Notes in Computer Sci- ence, Vol. 674, pp. 301-324, Springer-Verlag, 1993.

[12] J.L. Peterson, Petri Net Theory and the Modeling of Systems, Englewood Cliffs, Prentice-Hall, 1981.

[13] W. Reisig, Petri Nets: An Introduction, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1985.

[14] M. Silva, J. Martinez, P. Ladet, and H. Alla, “Gen- eralized Inverses and the Calculation of Symbolic Invariants for Coloured Petri Nets,’’ in High-Level Petri Nets, Theory and Application, Springer- Verlag, pp. 303-315,1991.

[15] A. Valmari, “Stubborn Sets of Coloured Petri Nets,” in Proceedings of the International Confer- ence on Application and Theory ^of Petri Nets, pp.

102-121, 1991.

pp. 377-386, 1988.

Vol. 3, NO. 2, pp. 173-181, 1983.

pp. 48-59, July 1991.