La quantification du premier ordre en logique temporelle

Sylvain Hallé

Sylvain Hallé

La

b

Université du Québec à MontréalMontréal, CANADA

Laboratoire de téléinformatiqueUQAM

La quantification du premier ordre enlogique temporelle: applications auxdocuments XML et aux services web

Sylvain Hallé

Mise en contexte

Mise en contexte #1: requêtes sur documents XML

Arbre de couples paramètre-valeur: cas particulier de document XML

On considère un sous-ensemble de XPath 1.0:

Ex.: a=1/b=5 ou a=2/d=3

a = 1

b = 5 d = 3

1

3 4

<a>1 5 <d>3</d></a>

p : p=v | p, p=vj : Ø j | j Ù j | p

Sylvain Hallé

Mise en contexte

Un arbre ressemble à une structure de Kripke:

Afanasiev et al. (TIME 2004): Simple XPath peut être plongé dans CTL

a = 1

b = 5 d = 3

1

3 4

a = a b = 1

a = b b = 5 a = d b = 3

p=v p, p=vØ jj Ù y

Û a=p Ù b=vÛ p Ù EX (a=p Ù b=v)Û Ø jÛ j Ù y

Sylvain Hallé

Mise en contexte

On étend Simple XPath ( :

Ex: <; a=x> <a=x ; b=y> x y

Utilité: propriétés de configurations réseau (et autres)

Þ Í XPath 2.0)

¹

CL

a = 1

b = 5 d = 3

1

3 4

p : p=v | p, p=vj : Ø j | j Ù j | j | x=y

Sylvain Hallé

Un arbre ressemble (toujours) à une structure de Kripke:

Peut-on (et comment) plonger CL dans CTL?

a = 1

b = 5 d = 3

1

3 4

a = a b = 1

a = b b = 5 a = d b = 3

p=v Û a=p Ù b=vp, p=v Û p Ù EX (a=p Ù b=v)Ø j Û Ø jj Ù y Û j Ù y j Û ???

Mise en contexte

Sylvain Hallé



a = 1

b = 5 d = 3

1

3 4

p=v Û a=p Ù b=vp, p=v Û p Ù EX (a=p Ù b=v)Ø j Û Ø jj Ù y Û j Ù y j Û p Ù EX ( a=p Ù b= Ù j( ))$x : x x

a = a b = 1

a = b b = 5 a = d b = 3

Mise en contexte

Sylvain Hallé



a = 1

b = 5 d = 3

1

3 4

p=v Û a=p Ù b=vp, p=v Û p Ù EX (a=p Ù b=v)Ø j Û Ø jj Ù y Û j Ù y j Û p Ù EX ( a=p Ù b= Ù j( ))$x : x x

a = a b = 1

a = b b = 5 a = d b = 3

Mise en contexte

Sylvain Hallé

Mise en contexte #2: interaction de

! Deux entités échangent des

services web

messages

UtilisateurService

Mise en contexte

Sylvain Hallé



services web

messages

A

UtilisateurService

Mise en contexte

Sylvain Hallé



services web

messages

B

UtilisateurService

Mise en contexte

Sylvain Hallé



services web

messages

D

UtilisateurService

Mise en contexte

Sylvain Hallé



services web

messages

D

UtilisateurService

Mise en contexte

Sylvain Hallé



services web

messages

UtilisateurService

Impossibled'envoyer D après

avoir envoyéun A !

Mise en contexte

Sylvain Hallé


! Deux entités échangent des ! L'interaction possède une mémoire (memoryful behaviour)

services web

messages

UtilisateurService


avoir envoyéun A !

Mise en contexte

Sylvain Hallé


! Deux entités échangent des ! L'interaction possède une mémoire (memoryful behaviour)

services web

messages

UtilisateurService


avoir envoyéun A !

Commentle

savoir?

Mise en contexte

Sylvain Hallé


! Deux entités échangent des ! L'interaction possède une mémoire (memoryful behaviour)! Deutsch, Sui, Vianu (PODS 2006): utiliser une logique

temporelle (disons CTL) pour définir les contraintes

services web

messages

UtilisateurService


avoir envoyéun A !

Commentle

savoir?

Mise en contexte

Sylvain Hallé


! Deux entités échangent des ! L'interaction possède une mémoire (memoryful behaviour)! Deutsch, Sui, Vianu (PODS 2006): utiliser une logique

temporelle (disons CTL) pour définir les contraintes

services web

messages

Service


avoir envoyéun A !

AG (a AX AG d)® Ø

Mise en contexte

Sylvain Hallé

Qu'en est-il du des messages?contenu

ServiceUtilisateur

Mise en contexte

Sylvain Hallé


A3

ServiceUtilisateur

Mise en contexte

Sylvain Hallé


A3

ServiceUtilisateur

Si A est reçu avecvaleur ( 0), envoyer Cavec valeur .Sinon, envoyer Bavec valeur .

xx+1

9

¹

Mise en contexte

Sylvain Hallé


C4

ServiceUtilisateur


xx+1

9

¹

Mise en contexte

Sylvain Hallé

Qu'en est-il du des messages?

! Le contenu des données influencele comportement

contenu

Service

C4


xx+1

9

¹

Utilisateur

Mise en contexte

Sylvain Hallé



contenu

M6

ServiceUtilisateur

Mise en contexte

Sylvain Hallé



contenu

Service

M6

Utilisateur

Mise en contexte

Sylvain Hallé

Service

M6


! Le contenu des données influencele comportement... entre

contenu

plusieurs messages

Utilisateur

M doit avoirla même valeurqu'un A envoyé

auparavant!

Mise en contexte

Sylvain Hallé



contenu

plusieurs messages

Service

M6

Utilisateur


auparavant!

Commentle

savoir?

Mise en contexte

Sylvain Hallé



! CTL peut-il encore exprimer ceci?

contenu

plusieurs messages

Service

M6

Utilisateur


auparavant!

Commentle

savoir?

Mise en contexte

Sylvain Hallé




contenu

plusieurs messages

Service


auparavant!

AF ( : a( ) AF m( ))$x x xÙ

Mise en contexte

Sylvain Hallé




contenu

plusieurs messages

Service


auparavant!

AF ( : a( ) AF m( ))$x x xÙ

Mise en contexte

Sylvain Hallé

Deux contextes:

! Plongement de XPath/XQuery en CTL! Vérification de transactions de services web

Même besoin:

! et plusieurs éléments d'un (ou plusieurs) document(s) XML...

! ... = quantification du premier ordre en logique temporelle(ici CTL)

Comment faire?

extraire comparer

Mise en contexte

Sylvain Hallé

Hallé, Villemaire, Cherkaoui, Tremblay (WS-FM 2007): = structure de Kripke "spéciale"

! Les états contiennent k ! ... = messages XML d'arité ! ... (pas de hiérarchie (pour le moment))

workflow messaging model

couples paramètre-valeurbornée

plats

<message> <a>1</a> <a>3</a> 9</message>

<message> <q>8</q> <q>3</q></message>

aaa

= a= a= b

bbb

= 1= 3= 9

1

2

3

1

2

3

aaa

= q= q= #

bbb

= 8= 3= #

1

2

3

1

2

3

Workflow messaging model

Sylvain Hallé

CTL-FO+ = CTL + quantification du premier ordre sur les couples

Ex: AF ($ x : AX AF ($ y : x=y))a q

<message> <a>1</a> <a>3</a> 9</message>

<message> <q>8</q> <q>3</q></message>

aaa

= a= a= b

bbb

= 1= 3= 9

1

2

3

1

2

3

aaa

= q= q= #

bbb

= 8= 3= #

1

2

3

1

2

3

$ x : j(x) Û $i : a=p Ù b=k Ù j(k)p i i

CTL-FO+

Sylvain Hallé

Model checking de CTL-FO+ sur un workflow messaging model?

Complexité du model checking (domaines finis): (Hallé et al., EDOC 2007) pas pire que LTL

Trois solutions:

1. Nouveau model checker

2. Adapter model checker existant

3. Retraduire le problème en CTL classique

PSPACE-completÞ

Model checking de CTL-FO+

Sylvain Hallé

Tentative #1: quantification

Transformer une formule quantifiée comme:

en

pour toutes les valeurs du domaine de x. Devient formule CTL classique.

idée (on verra plus loin).

explicite

Mauvaise


Sylvain Hallé

Tentative #2: quantification

Adaptation d'une idée de Alur et Henzinger (1994)

Utilisée comme moyen de la quantification du premier ordre en CTL

Principe: ajouter des variables d'état au système qui vont "geler" la valeur d'une autre variable d'état à un moment précis

freeze

simuler


Sylvain Hallé

AF ($ x : AX AF ($ y : x=y))a q

aaa

= a= a= b

bbb

= 1= 3= 9

1

2

3

1

2

3

aaa

= q= q= #

bbb

= 8= 3= #

1

2

3

1

2

3

Freeze quantification

Sylvain Hallé

AF ($ x : AX AF ($ y : x=y))a q

aaan

= a= a= b= #

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= #

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2


Sylvain Hallé

AF ($ x : AX AF ($ y : x=y))a q

aaan

= a= a= b= #

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= a= a= b= 1

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= #

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2

x=1


Sylvain Hallé

AF ($ x : AX AF ($ y : x=y))a q

aaan

= a= a= b= #

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= a= a= b= 1

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= #

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2

x=1

aaan

= q= q= #= 1

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2


Sylvain Hallé

AF ($ x : AX AF ($ y : x=y))a q

aaan

= a= a= b= #

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= a= a= b= 1

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= #

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 8

1

2

3

1

1

2

3

2

x=1

y=8aaan

= q= q= #= 1

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2


Sylvain Hallé

AF ($ x : AX AF ($ y : x=y))a q

aaan

= a= a= b= #

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= a= a= b= 1

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= #

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 3

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 8

1

2

3

1

1

2

3

2

x=1

y=8

y=3

aaan

= q= q= #= 1

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2


Sylvain Hallé

AF ($ x : AX AF ($ y : x=y))a q

aaan

= a= a= b= #

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= a= a= b= 1

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= #

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 3

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 8

1

2

3

1

1

2

3

2

x=1

. . .

y=8

y=3

aaan

= q= q= #= 1

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2


Sylvain Hallé

AF ($ x : AX AF ($ y : x=y))a q

aaan

= a= a= b= #

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= a= a= b= 1

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= #

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 3

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 8

1

2

3

1

1

2

3

2

x=1

x=3

. . .

. . .

y=8

y=3

aaan

= q= q= #= 1

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2


Sylvain Hallé

Hallé, Villemaire, Cherkaoui, IEEE TSE 2008: on peut systématiser cette construction

Workflow messaging model M + variables et qualificatif workflow messaging model M'

Deuxième étape: on se débarrasse de la quantification dans la formule

Formule CTL-FO+ j formule CTL y'

Garde: "les t premières variables sur n ont pris une valeur"

Þ

Þ

freeze


Sylvain Hallé

Traduction récursive w: paramétrisée par n (nombre total de variables quantifiées) et t (nombre de variables freeze qui ont déjà une valeur)

Connecteurs booléens et égalité: direct


Sylvain Hallé

Traduction du EX:

aaan

= a= a= b= #

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= a= a= b= 1

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= #

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 3

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 8

1

2

3

1

1

2

3

2

x=1

x=3

. . .

. . .

y=8

y=3

aaan

= q= q= #= 1

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2


Sylvain Hallé

Traduction du AF:

aaan

= a= a= b= #

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= a= a= b= 1

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= #

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 3

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 8

1

2

3

1

1

2

3

2

x=1

x=3

. . .

. . .

y=8

y=3

aaan

= q= q= #= 1

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2


Sylvain Hallé

Traduction du AF:

aaan

= a= a= b= #

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= a= a= b= 1

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= #

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 3

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 8

1

2

3

1

1

2

3

2

x=1

x=3

. . .

. . .

y=8

y=3

aaan

= q= q= #= 1

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2

Généralisation:

Si on remplace par true, on retrouvela définition classique

i.e. le garde est un "filtre"


Sylvain Hallé

Traduction du EU:

aaan

= a= a= b= #

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= a= a= b= 1

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= #

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 3

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 8

1

2

3

1

1

2

3

2

x=1

x=3

. . .

. . .

y=8

y=3

aaan

= q= q= #= 1

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2


Sylvain Hallé

Traduction de la quantification existentielle:

aaan

= a= a= b= #

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= a= a= b= 1

bbbn

= 1= 3= 9= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= #

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 3

1

2

3

1

1

2

3

2

aaan

= q= q= #= 1

bbbn

= 8= 3= #= 8

1

2

3

1

1

2

3

2

x=1

x=3

. . .

. . .

y=8

y=3

aaan

= q= q= #= 1

bbbn

= 8= 3= #= #

1

2

3

1

1

2

3

2


Sylvain Hallé

Théorème (Hallé et al., IEEE TSE 2008):

ssi

Traduction exponentielle...

...mais s'il en existe une meilleure => P = NP

Minute! La quantification explicite était elle aussi une traduction exponentielle!

CTL-FO+PSPACE-complet

CTLEXPTIME


Sylvain Hallé

Quantification explicite Freeze quantification

- Formule dépend du - Formule indépendantedomaine du domaine

- Petit système - Grand système

- Grande formule - Petite formule

On dit qu'un model checker est optimisé pour de grands espaces d'états, mais des formules (relativement) courtes. Est-ce vrai?

Comparaison

Sylvain Hallé

Formules CTL-FO+ tirées d'un scénario de commerce électronique

F1- "Un même produit ne peut apparaître que dans un seul message dans toute la transaction" (2 quantificateurs)

F2- "Chaque produit dans unecommande apparaît plus tard dansune confirmation de commande"(4 quantificateurs)

F3- "Au moins un produit est acheté"(6 quantificateurs)

Get all stocks

Get stock details

Place buy order(s)

Place sell order(s)

Confirm buy order(s)

Confirm sell order(s)

Cash transfer

Cancel transaction

Customer

Online stock trading

Résultats expérimentaux

Sylvain Hallé


Sylvain Hallé


Sylvain Hallé

Out of memory (exp)


Sylvain Hallé

Quantification explicite: plus appropriée (et plus efficace) pour des formules avec peu de quantificateurs (< 3)

Quantification freeze: seule méthode qui donne des temps raisonnables pour toutes les formules

>10000 fois plus rapide dans certains cas

Conclusion

Sylvain Hallé

S. Hallé, R. Villemaire, O. Cherkaoui, B. Ghandour. (2007). Model-checking Data-Aware Temporal Workflow Properties with CTL-FO+. Proc. EDOC 2008, IEEE Computer Society.

S. Hallé, R. Villemaire, O. Cherkaoui, J. Tremblay, B. Ghandour. (2007). Extending Model Checking to Data-Aware Temporal Properties of Web Services. Proc. WS-FM 2008, Springer LNCS 4937.

S. Hallé, R. Villemaire, O. Cherkaoui. Specifying and Validating Data-aware Temporal Web Service Properties. IEEE Transactions on Software Engineering (en révision).

Références

Technology

La quantification du premier ordre en logique temporelle