Contribution à la modélisation et à la vérification de processus workflow

Zohra Sbai

Description

Sous la direction de Kamel Barkaoui
Thèse soutenue le 13 novembre 2010: Université de Tunis et Ecole nationale d'Ingénieur de Tunis, CNAM
La technologie de workflow, tendant à automatiser les processus d'entreprise et à fournir un support pour leur gestion, est aujourd'hui un secteur actif de recherche. C'est dans ce contexte que se situent ces travaux de thèse qui portent aussi bien sur la modélisation des processus workflow que sur leur vérification. Ces processus, pouvant être contraints par des ressources partagées ou encore par des durées de traitement, doivent être vérifiés avant d'être confiés aux systèmes de gestion de workflow qui vont les exécuter. Nous nous sommes intéressés par la vérification de la propriété de cohérence (soundness) des réseaux de workflow (WF-net) : sous-classes des réseaux de Petri (RdPs) modélisant les processus workflow.Dans ce cadre, en explorant la théorie structurelle des RdPs, nous avons identifié des sous-classes de WF-nets pour lesquelles la cohérence peut être vérifiée et caractérisée efficacement. Nous nous sommes focalisés en outre sur l'extension de ces sous-classes en tenant compte de la présence de ressources partagées et sur la propriété de cohérence en présence d'un nombre arbitraire d'instances prêtes à s'exécuter. Dans cette partie, nous avons dû automatiser le calcul des siphons minimaux dans un RdP. Pour ce faire, nous avons choisi un algorithme de la littérature et l'amélioré par la recherche et la contraction de circuits alternés.Ensuite, nous avons abordé la modélisation et la vérification de processus workflow tenant compte des contraintes temporelles. Nous avons en premier lieu proposé un modèle de TWF-net (WF-net Temporisé). Pour ce modèle, nous avons défini la propriété de cohérence temporelle et proposé une condition nécessaire et suffisante pour la vérifier. En deuxième lieu, nous avons relaxé les contraintes temporelles adoptées par la proposition d'un modèle temporel visant des processus à contraintes temporelles variant dans des intervalles de temps. Nous avons défini formellement le modèle de ITWF-net (Interval Timed WF-net) et donné sa sémantique. Par ailleurs, nous avons développé et testé un prototype de modélisation et de simulation des ITWF-nets.La dernière partie de cette thèse a concerné la vérification formelle des processus workflow par SPIN model checker. Nous avons dû en premier lieu traduire la spécification des workflows adoptée vers Promela : le langage de description des modèles à vérifier par SPIN. En second lieu, nous avons exprimé les propriétés de cohérence en Logique Linéaire Temporelle (LTL) et utilisé SPIN pour tester si chaque propriété est satisfaite par le modèle Promela du WF-net en question. Enfin, nous avons exprimé les propriétés de k-cohérence pour les WF-nets modélisant plusieurs instances et de (k,R)-cohérence pour les processus workflow concurrents et qui possèdent des ressources partagées.
-Processus workflow
-Modélisation
-Vérification
-Réseaux de Petri
-Model Checking
Workflow technology, whose role is to automate business processes and to provide a support for their management, is today an active sector of research. This thesis deals with the modelling of the workflow processes and their analysis. These processes, probably constrained by shared resources or by durations of treatment, must be checked before being executed by their workflow management systems. In this direction, we were interested by the checking of the soundness property of workflow nets (WF-nets): subclasses of Petri nets modelling the workflow processes.To begin with, by exploring the structure theory of Petri nets, we have identified subclasses of WF-nets for which soundness can be checked and characterized effectively. We also extended these subclasses by taking account of the presence of shared resources and we focused on the soundness property in the presence of an arbitrary number of instances ready to be carried out. In this part, we had to automate the computation of minimal siphons in a Petri net. For that, we chose an algorithm of the literature and improved it by the research and the contraction of alternate circuits.Then, we were concerned by the modelling and the analysis of workflow processes holding temporal constraints. We initially proposed the model of TWF-net (Timed WF-net). For this model, we defined its soundness and proposed a method to check it. Then, we released the adopted temporal constraints by the proposal of a model covering workflow processes for witch temporal constraints vary in time intervals. We formally defined the model of ITWF-net (Interval Timed WF-net) and gave its semantics. In addition, we developed and tested a prototype of modelling and simulation of ITWF-nets.The last part of this thesis concerns the formal analysis of workflow processes with SPIN model checker. We initially translated the workflow specification into Promela: the model description language used by SPIN. Then, we expressed the soundness properties in Linear Temporal Logic (LTL) and used SPIN to test if each property is satisfied by the Promela model of a given WF-net. Moreover, we expressed the properties of k-soundness for WF-nets modelling several instances and (k,R)-soundness for competitive workflow processes which share resources.
-Workflow process
-Modelling
-Analysis
-Petri nets
-Model Checking
Source: http://www.theses.fr/2010CNAM0731/document

Sujets

• Modélisation
• Vérification
• Réseau de Petri

Informations

• Publié par: Thesee
• Nombre de lectures: 144
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

Titre,
ENIT
P
V
ENIT
A
Présiden
TOIRE
aris
NA
CNAM
TIONAL
Samir
DES
JUR
AR
de
TS
T
ET
BEN
MÉTIERS
BARKA
Ecole
Rahma
Do
T
ctorale
aris
Informatique,
hnique
Télécomm
ANE
u
GUEMARA
nications
OBBANA
et
de
Electronique
Samir
de
Professeur,
P
Maître
aris
ar
[Cen
Kamel
tre
A
d'Etudes
de
et
TEURS
De
T
Rec
TELECOM
herc
OBBANA
he
P
en
T
Informatique
:
du
Professeur,
CNAM]
du
THÈSE
Professeur,
présen
unis
tée
Professeur,
par
c
:
uni
[Zohra
T
SBAÏ]
TELECOM
souten
OUI
ue
P
le
YED
:
conférences,
13
p
no
:
v
OUI
em
Professeur,
bre
BEN
2010
YED
p
Maître
our
Conférences,
obtenir
RAPPOR
le
:
grade
A
de
A
:
Professeur,
Do
SudP
cteur
R
du
Riadh
Conserv
Ecole
atoire
olytec
National
de
des
unis
Arts
Y
et
JAÏD
Métiers
Mériem
Discipline/
ENIT,
Sp
t
éciali
jury
té
Sihem
:
SUP'COM
Informatique
T
Con
R
tribu
Riadh
t
Ecole
i
olyte
on
hnique
à
T
la
s
Mo
A
délisation
A
et
Professeur,
à
SudP
la
BARKA
Vérication
Kamel
de
CNAM
Pro
aris
cessus
A
W
Rahma
orko
de
w
dirigée
THÈSE
CONSER
tel-00553383, version 1 - 7 Jan 2011tel-00553383, version 1 - 7 Jan 2011uni-
la
ces
ts
p
Les
re
tra
f
v
oratoire
aux
son
présen
d
tés
à
dans
au
cette
p
thèse
v
on
le
t
ce
été
GUEMARA,
eectués
oir
au
ici
Lab
BEN
oratoire
our
Systèmes
v
de
s'adresse
Comm
National
unication
t
de
qu'il
l'
mes
Ecole
u
Nationale
fourni.
d'Ingénieurs
qu'il
de
a
T
Je
unis,
Sup
et
unis
au
partie
Cen
Qu'ell
tre
profond
d
emen
'Etude
des
et
de
de
dirigé
Rec
et
herc
son
he
années.
en
BARKA
Informatique
au
du
Métiers
Conserv
oir
atoire
ces
N
conseil
a
endan
ti
v
o
mem
n
et
al
du
des
orable
Arts
e
et
l'analyse
Métiers
menée
d
et
e
tribué
P
hissemen
aris
Madame
.
à
Mes
des
remerciemen
de
ts
d'a
v
de
on
mem
t
jury
à
trouv
Madame
de
Mériem
ect.
JAID
très
AN
Madame
E,
YED,
Professeur
n
à
Nationale
l'Ecole
unis,
Nationale
v
d'Ingénieurs
endan
de
v
T
our
unis,
accordé
p
précieux
our
de
le
profonde
grand
Monsieur
honneur
P
qu'elle
s
m'a
v
fait
Arts
en
P
acceptan
m'a
t
to
de
long
présider
p
ce
et
jury
a
de
accordés
th
ce
è
Je
s
emen
e.
et
Qu'elle
du
trouv
de
e
bres
ici
oratoire
le
p
témoignage
fa
de
m'on
ma
3
resp
reconnaissance
e
our
ctu
rigoureuse
euse
a
gratitude
à
et
mémoire
mon
qui
profond
con
resp
à
ect.
enric
Je
t.
tiens
remercie
à
Sihem
exprimer
Professeur
ma
l'Ecole
gratitude
érieure
en
Comm
v
cations
ers
T
Monsieur
(SUP'COM),
Riadh
v
R
accepté
OBBANA
faire
,
des
Professeu
bres
r
u
à
.
l'Ecole
e
P
e
olytec
l'expression
hnique
mon
de
resp
T
Je
unis,
mercie
qui
viv
m'a
t
honoré
Rahma
en
A
acceptan
Maître
t
Co
de
férences
j
l'Ecole
uger
d'Ingénieurs
ce
T
tra
p
v
m'a
ail.
oir
Q
p
u
t
'il
tra
trouv
aux
e
p
ici
m'a
l'expression
oir
de
de
ma
temps
profonde
tout
gratitude
long
et
ces
mon
Ma
resp
gratitude
ect.
à
Je
Kamel
suis
OUI,
égalemen
ro
t
e
très
seur
reconnaissan
Conser-
te
atoire
en
des
v
et
ers
de
Monsieur
aris,
Samir
our
T
v
A
guidé
T
u
A,
au
Professeur
de
à
années,
TE-
our
LECOM
conance
S
les
udP
s
aris,
visés
qui
m'a
m'a
p
fait
t
un
tra
grand
ail.
honneu
remercie
r
iv
en
t
acce
amis
p
collègues
tan
bres
t
Lab
d
Sys'Com
e
l'ENIT
juger
mem
ce
d
tra
Lab
v
CEDRIC
ail.
CNAM
Je
our
tiens
climat
à
v
lui
qu'ils
exprimer
t
toute
viv
ma
Remerciemen
tel-00553383, version 1 - 7 Jan 2011MENTS
4
E
CI
REMER
tel-00553383, version 1 - 7 Jan 2011del
our
king.
La
mo
tec
satisfaite.
hnologie
(WF-net
de
visan
w
délisation
orko
nous
w,
ts
tend
temp
a
propriété
n
temp
t
in-
à
ailleurs,
autom
a
atis
lieu
e
TL)
r
délisan
les
Pro
pro
t
cessus
lieu
d'en
dèle,
treprise
osé
et
a
à
ro
fournir
tes
un
ons
supp
WF-net)
ort
et
p
dernière
our
o
leur
v
gestion,
ws
est
cohérence
aujourd'h
c
ui
propriétés
un
our
secteur
s
actif
Réseaux
d
w
e
des
rec
v
herc
mo
he.
P
C'est
on
dans
temp
ce
et
con
En
texte
les
que
adoptées
se
mo
situen
cessus
t
arian
ces
temps.
tra
leme
v
(In
aux
séman
de
ons
thèse
yp
qui
ulation
p
thèse
orten
des
t
par
aussi
er.
bien
p
sur
écication
la
Promela.
mo
exprimé
délisation
T
des
p
pro
propriété
cessus
v
w
our
orko
et
w
w
que
ossèden
sur
partagées.
leur
w,
v
etri,
éric
pro
ation
w
.
p
Ces
train
pro
Nous
cessus,
en
p
osé
ouv
de
an
emp
t
ce
être
a
con
déni
train
co-
ts
et
par
condition
des
te
ress
v
o
lieu,
u
ons
rce
train
s
l
partagées
la
ou
osition
encore
temp
par
des
d
con
es
orelles
durées
dans
d
alles
e
a
traitemen
forme
t,
t
doiv
de
en
al
t
donné
être
P
v
a
ériés
elopp
a
un
v
de
an
de
t
ITWF-nets.
d'être
de
conés
concerné
aux
érication
systèm
cessus
es
o
de
m
ge
hec
s
s
tion
dû
de
i
w
la
orko
w
w.
v
Nous
second
nous
v
sommes
propriétés
in
Logique
téressés
orelle
par
utilisé
la
tester
v
a
érication
s
de
nous
la
exprimé
propriété
k-cohérence
d
WF-nets
e
plusieurs
cohéren
(k,R)-coh