X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/251b65007a909068d3344bd82b7c5ec0ffb0a21a..44a56c5eb4a1dfdf7dc67735c5c00f478cef2ede:/modelchecking.tex diff --git a/modelchecking.tex b/modelchecking.tex index f69df76..dd4bf2e 100644 --- a/modelchecking.tex +++ b/modelchecking.tex @@ -1,4 +1,113 @@ -\JFC{donner dans les rappels les délais et les propriétés de convergence uniforme} + +Sur des petits exemples, l'étude de convergence de systèmes +dynamiques discrets est simple à vérifier +pratiquement pour le mode synchrone. Lorsqu'on introduit des stratégies +pseudo-périodiques pour les modes unaires et généralisés, le problème +se complexifie. C'est pire encore lorsqu'on traite des itérations asynchrones +et mixtes prenant de plus en compte les délais. + +Des méthodes de simulation basées sur des stratégies et des délais générés aléatoirement +ont déjà été présentées~\cite{BM99,BCV02}. +Cependant, comme ces implantations ne sont pas exhaustives, elles ne donnent un résultat +formel que lorsqu'elles fournissent un contre-exemple. Lorsqu'elles exhibent une convergence, +cela ne permet que de donner une intuition de convergence, pas une preuve. +Autant que nous sachions, aucune démarche de preuve formelle automatique +de convergence n'a jamais été établie. +Dans le travail théorique~\cite{Cha06}, Chandrasekaran a montré que les itérations asynchrones sont convergentes +si et seulement si on peut construire une fonction de Lyaponov décroissante, mais il ne donne pas de méthode +automatique pour construire cette fonction. + +Un outil qui construirait automatiquement toutes +les transitions serait le bienvenu. +Pour peu qu'on établisse la preuve de correction et de complétude de la +démarche, la convergence du réseau discret ne reposerait + alors que sur le verdict +donné par l'outil. +Cependant, même pour des réseaux discrets à peu d'éléments, +le nombre de configurations induites explose rapidement. +Les \emph{Model-Checkers}~\cite{Hol03,nusmv02,Blast07,MCErlang07,Bogor03} +sont des classes d'outils qui adressent le problème de détecter automatiquement +si un modèle vérifie une propriété donnée. Pour traiter le problème d'explosion +combinatoire, ces outils appliquent des méthodes d'ordre partiel, d'abstraction, +de quotientage selon une relation d'équivalence. + +Ce chapitre montre comment nous simulons +des réseaux discrets pour établir +formellement leur convergence (ou pas). +Nous débutons par un exemple et faisons quelques rappels sur +le langage PROMELA qui est le langage du model-checker +SPIN~\cite{Hol03} (\Sec{sec:spin:promela}). +Nous présentons ensuite la démarche de traduction +de réseaux discrets dans PROMELA (\Sec{sec:spin:translation}). +Les théorèmes de correction et de complétude de la démarche +sont ensuite donnés à la \Sec{sec:spin:proof}. +Des données pratiques comme la complexité et des synthèses d'expérimentations +sont ensuite fournies (\Sec{sec:spin:practical}). +Ce chapitre a fait l'objet du rapport~\cite{Cou10:ir}. + + + + + + +%\section{Exemple jouet} + + +\begin{figure}[ht] + \begin{center} + \subfigure[Fonction à itérer]{ + $ F(x)= \left \{ + \begin{array}{rcl} + f_1(x_1,x_2,x_3) & = & x_1.\overline{x_2} + x_3 \\ + f_2(x_1,x_2,x_3) & = & x_1 + \overline{x_3} \\ + f_3(x_1,x_2,x_3) & = & x_2.x_3 + \end{array} + \right. + $ + \label{fig:map} + } + \hfill + \subfigure[Graphe d'intéraction]{ + \includegraphics[width=4cm]{images/xplCnxMc.eps} + \label{fig:xplgraph:inter:mc} + } + \end{center} + \caption{Exemple pour SDD $\approx$ SPIN.} +\end{figure} + + + +\begin{xpl} + On considère un exemple à trois éléments dans $\Bool$. + Chaque configuration est ainsi un élément de $\Bool^3$, \textit{i.e.}, + un nombre entre 0 et 7. + La \Fig{fig:map} précise la fonction $f$ considérée et + la \Fig{fig:xplgraph:inter:mc} donne son graphe d'intéraction. + + + + + + + +On peut facilement vérifier que toutes les itérations parallèles +synchrones initialisées +avec $x^0 \neq 7$ soit $(111)$ +convergent vers $2$ soit $(010)$; celles initialisées avec +$x^0=7$ restent en 7. +Pour les modes unaires ou généralisés avec une +stratégie pseudo-périodique, on a des comportements qui dépendent +de la configuration initiale: +\begin{itemize} +\item initialisées avec 7, les itérations restent en 7; +\item initialisées avec 0, 2, 4 ou 6 les itérations convergent vers 2; +\item initialisées avec 1, 3 ou 5, les itérations convergent vers un des +deux points fixes 2 ou 7. +\end{itemize} +\end{xpl} + + + \section{Rappels sur le langage PROMELA} @@ -32,59 +141,62 @@ chan sync_mutex=[1] of {bool}; \end{figure} -Les types primaires de PROMELA sont \texttt{bool}, \texttt{byte}, -\texttt{short} et \texttt{int}. Comme dans le langage C par exemple, -on peut déclarer des tableaux à une dimension de taille constante +% Les types primaires de PROMELA sont \texttt{bool}, \texttt{byte}, +% \texttt{short} et \texttt{int}. +Comme en C, +on peut déclarer des tableaux à une dimension ou des nouveaux types de données (introduites par le mot clef -\verb+typedef+). Ces derniers sont utilisés pour définir des tableaux à deux -dimension. +\verb+typedef+). % Ces derniers sont utilisés +% pour définir des tableaux à deux +% dimensions. \begin{xpl} Le programme donné à la {\sc Figure}~\ref{fig:arrayofchannels} correspond à des -déclarations de variables qui serviront dans l'exemple jouet de ce chapitre. -Il définit tout d'abord: +déclarations de variables qui servent dans l'exemple de ce chapitre. +Il définit: \begin{itemize} \item les constantes \verb+N+ et \verb+d_0+ qui précisent respectivement le nombre - $n$ d'éléments et le délais maximum $\delta_0$; + ${\mathsf{N}}$ d'éléments et le délai maximum $\delta_0$; \item les deux tableaux (\verb+X+ et \verb+Xp+) de \verb+N+ variables booléennes; -les cellules \verb+X[i]+ et \verb+Xp[i]+ sont associées à la variables $X_{i+1}$ -d'un système dynamique discret -(le décalages d'un entier est dû à l'indexation à partir de zéro des cellules d'un tableau); -Elles mémorisent les valeurs de $X_{i+1}$ respectivement avant et après sa mise à jour; -il suffit ainsi de comparer \verb+X+ et \verb+Xp+ pour constater si $X$ à changé ou pas; +les cellules \verb+X[i]+ et \verb+Xp[i]+ sont associées à la variables $x_{i+1}$ +d'un système dynamique discret; +elles mémorisent les valeurs de $X_{i+1}$ respectivement avant et après sa mise à jour; +il suffit ainsi de comparer \verb+X+ et \verb+Xp+ pour constater si $x$ a changé ou pas; \item le tableau \verb+mods+ contient les éléments qui doivent être modifiés lors de l'itération -en cours; cela correspond naturellement à l'ensemble des éléments $S^t$; +en cours; cela correspond naturellement à l'ensemble des éléments $s^t$; \item le type de données structurées \verb+vals+ et le tableau de tableaux - \verb+Xd[+$i$\verb+].v[+$j$\verb+]+ qui vise à mémoriser $X_{j+1}^{D^{t-1}_{i+1j+1}}$ - pour l'itération au temps $t$ (en d'autres termes, utile lors du calcul de $X^{t}$). + \verb+Xd[+$i$\verb+].v[+$j$\verb+]+ qui vise à mémoriser $x_{j+1}^{D^{t-1}_{i+1j+1}}$ + pour l'itération au temps $t$. +%(en d'autres termes, utile lors du calcul de $x^{t}$). \end{itemize} -Puisque le décalage d'un indices ne change pas fondamentalement -le comportement de la version PROMELA par rapport au modèle initial -et pour des raisons de clarté, on utilisera par la suite la même -lettre d'indice entre les deux niveaux (pour le modèle: $X_i$ et pour PROMELA: -\texttt{X[i]}). Cependant, ce décalage devra être conservé mémoire. +% Puisque le décalage d'un indices ne change pas fondamentalement +% le comportement de la version PROMELA par rapport au modèle initial +% et pour des raisons de clarté, on utilisera par la suite la même +% lettre d'indice entre les deux niveaux (pour le modèle: $x_i$ et pour PROMELA: +% \texttt{X[i]}). Cependant, ce décalage devra être conservé mémoire. -Une donnée de type \texttt{channel} permet le +Déclarée avec le mot clef \verb+chan+, +une donnée de type \texttt{channel} permet le transfert de messages entre processus dans un ordre FIFO. -Elles serait déclarée avec le mot clef \verb+chan+ suivi par sa capacité -(qui est constante), son nom et le type des messages qui sont stockés dans ce canal. +% Elles serait suivi par sa capacité +% (qui est constante), son nom et le type des messages qui sont stockés dans ce canal. Dans l'exemple précédent, on déclare successivement: \begin{itemize} -\item un canal \verb+sent+ qui vise à mémoriser\verb+d_0+ messages de type +\item un canal \verb+sent+ qui vise à mémoriser \verb+d_0+ messages de type \verb+bool+; le tableau nommé \verb+channels+ de \verb+N+*\verb+N+ - éléments de type \verb+a_send+ est utilisé pour mémoriser les valeurs intermédiaires $X_j$; - Il permet donc de temporiser leur emploi par d'autres elements $i$. + éléments de type \verb+a_send+ est utilisé pour mémoriser les valeurs intermédiaires $x_j$; + Il permet donc de temporiser leur emploi par d'autres éléments $i$. \item les deux canaux \verb+unlock_elements_update+ et \verb+sync_mutex+ contenant -chacun un message booléen et utilisé ensuite comme des sémaphores. +chacun un message booléen et sont utilisés ensuite comme des sémaphores. \end{itemize} \end{xpl} %\subsection{PROMELA Processes} Le langage PROMELA exploite la notion de \emph{process} pour modéliser la concurrence -au sein de systèmes. Un process est déclaré avec le mot-clé -\verb+proctype+ et est instancié soit immédiatement (lorsque sa déclaration est préfixée +au sein de systèmes. Un process est instancié soit immédiatement +(lorsque sa déclaration est préfixée par le mot-clef \verb+active+) ou bien au moment de l'exécution de l'instruction \texttt{run}. Parmi tous les process, \verb+init+ est le process initial qui permet @@ -92,15 +204,15 @@ d'initialiser les variables, lancer d'autres process\ldots Les instructions d'affectation sont interprétées usuellement. -Les canaux sont cernés par des instructions particulières d'envoi et de +Les canaux sont concernés par des instructions particulières d'envoi et de réception de messages. Pour un canal -\verb+ch+, ces instruction sont respectivement notées -\verb+ch ! m+ et \verb+ch ? m+. +\verb+ch+, ces instructions sont respectivement notées +\verb+ch ! m+ et \verb+ch ? m+. L'instruction de réception consomme la valeur en tête du canal \verb+ch+ et l'affecte à la variable \verb+m+ (pour peu que \verb+ch+ soit initialisé et non vide). -De manière similaire,l'instruction d'envoi ajoute la valeur de \verb+m+ à la queue du canal -\verb+ch+ (pour peu que celui-ci soit initialisé et non rempli). -Dans les cas problématiques, canal non initialisé et vide pour une réception ou bien rempli pour un envoi, +De manière similaire, l'instruction d'envoi ajoute la valeur de \verb+m+ à la queue du canal +\verb+ch+ (pour peu que celui-ci soit initialisé et pas plein). +Dans les cas problématiques, canal non initialisé et vide pour une réception ou plein pour un envoi, le processus est bloqué jusqu'à ce que les conditions soient remplies. La structures de contrôle \verb+if+ (resp. \verb+do+) définit un choix non déterministe @@ -109,20 +221,19 @@ si plus d'une des conditions est établie, l'ensemble des instructions correspon sera choisi aléatoirement puis exécuté. Dans le process \verb+init+ détaillé à la {\sc Figure}~\ref{fig:spin:init}, -une boucle de taille $N$ initialise aléatoirement la variable globale de type tableau \verb+Xp+. +une boucle de taille ${\mathsf{N}}$ initialise aléatoirement la variable globale de type tableau \verb+Xp+. Ceci permet par la suite de vérifier si les itérations sont convergentes pour n'importe -quelle configuration initiale $X^{(0)}$. +quelle configuration initiale $x^{0}$. Pour chaque élément $i$, si les itérations sont asynchrones \begin{itemize} \item on stocke d'abord la valeur de \verb+Xp[i]+ dans chaque \verb+Xd[j].v[i]+ -puisque la matrice $S^0$ est égale à $(0)$, +puisque la matrice $s^0$ est égale à $(0)$, \item puis, la valeur de $i$ (représentée par \verb+Xp[i]+) devrait être transmise à $j$ s'il y a un arc de $i$ à $j$ dans le graphe d'incidence. Dans ce cas, - c'est la fonction \verb+hasnext+ (non détaillée ici) - \JFC{la détailler} + c'est la fonction \verb+hasnext+ (détaillée à la~\Fig{fig:spin:hasnext}) qui mémorise ce graphe en fixant à \texttt{true} la variable \verb+is_succ+, naturellement et à \texttt{false} dans le cas contraire. @@ -130,7 +241,7 @@ puisque la matrice $S^0$ est égale à $(0)$, \end{itemize} \begin{figure}[t] - \begin{minipage}[h]{.52\linewidth} + \begin{minipage}[h]{.32\linewidth} \begin{tiny} \begin{lstlisting} init{ @@ -167,7 +278,7 @@ init{ \end{tiny} \caption{Process init.}\label{fig:spin:init} \end{minipage}\hfill - \begin{minipage}[h]{.42\linewidth} + \begin{minipage}[h]{.32\linewidth} \begin{tiny} \begin{lstlisting} active proctype scheduler(){ @@ -190,9 +301,31 @@ active proctype scheduler(){ } \end{lstlisting} \end{tiny} -\caption{Process scheduler pour la stratégie pseudo pérodique. +\caption{Process scheduler pour la stratégie pseudo-périodique. \label{fig:scheduler}} \end{minipage} +\begin{minipage}[h]{.30\linewidth} +\begin{tiny} +\begin{lstlisting} +inline hasnext(i,j){ + if + :: i==0 && j ==0 -> is_succ = 1 + :: i==0 && j ==1 -> is_succ = 1 + :: i==0 && j ==2 -> is_succ = 0 + :: i==1 && j ==0 -> is_succ = 1 + :: i==1 && j ==1 -> is_succ = 0 + :: i==1 && j ==2 -> is_succ = 1 + :: i==2 && j ==0 -> is_succ = 1 + :: i==2 && j ==1 -> is_succ = 1 + :: i==2 && j ==2 -> is_succ = 1 + fi +} +\end{lstlisting} +\end{tiny} +\caption{Codage du graphe d'intéraction de $f$. + \label{fig:spin:hasnext}} +\end{minipage} + \end{figure} @@ -206,47 +339,46 @@ ces notions est traduite vers un modèle PROMELA. \subsection{La stratégie}\label{sub:spin:strat} -Regardons comment une stratégie pseudo périodique peut être représentée en PROMELA. +Regardons comment une stratégie pseudo-périodique peut être représentée en PROMELA. Intuitivement, un process \verb+scheduler+ (comme représenté à la {\sc Figure}~\ref{fig:scheduler}) -est iterrativement appelé pour construire chaque $S^t$ représentant +est itérativement appelé pour construire chaque $s^t$ représentant les éléments possiblement mis à jour à l'itération $t$. Basiquement, le process est une boucle qui est débloquée lorsque la valeur du sémaphore \verb+sync_mutex+ est 1. Dans ce cas, les éléments à modifier sont choisis -aléatoirement (grâce à $n$ choix successifs) et sont mémorisés dans le tableau +aléatoirement (grâce à ${\mathsf{N}}$ choix successifs) et sont mémorisés dans le tableau \verb+mods+, dont la taille est \verb+ar_len+. Dans la séquence d'exécution, le choix d'un élément mis à jour est directement -suivi par des mis à jour: ceci est réalisé grâce à la modification de la valeur du sémaphore +suivi par des mises à jour: ceci est réalisé grâce à la modification de la valeur du sémaphore \verb+unlock_elements_updates+. -\subsection{Itérer la fonction $F$}\label{sub:spin:update} -La mise à jour de l'ensemble $S^t=\{s_1,\ldots, s_m\}$ des éléments qui constituent la stratégie -$(S^t)^{t \in \Nats}$ est implanté à l'aide du process \verb+update_elems+ fourni à la +\subsection{Itérer la fonction $f$}\label{sub:spin:update} +La mise à jour de l'ensemble $s^t=\{s_1,\ldots, s_m\}$ des éléments qui constituent la stratégie +$(s^t)^{t \in \Nats}$ est implantée à l'aide du process \verb+update_elems+ fourni à la {\sc Figure}~\ref{fig:proc}. -Ce process actif attend jusqu'à ce qu'il soit débloqué par le process +Ce processus actif attend jusqu'à ce qu'il soit débloqué par le process \verb+scheduler+ à l'aide du sémaphore \verb+unlock_elements_update+. -L'implantation contient donc cinq étapes: - -\begin{enumerate} -\item elle commence en mettant à jour la variable \texttt{X} avec les valeurs de \texttt{Xp} - dans la fonction \texttt{update\_X} (non détaillée ici); -\item elle mémorise dans \texttt{Xd} la valeurs disponibles des éléments grâce à - la fonction \texttt{fetch\_values} (cf. \Sec{sub:spin:vt}); -\item une boucle sur les \texttt{ar\_len} éléments qui peuvent être modifiés - met à jour iterrativement la valeur de $j$ (grâce à l'appel de fonction \texttt{F(j)}) - pour peu que celui-ci doive être modifié, \textit{i.e.}, pour peu qu'il soit renseigné dans - \texttt{mods[count]}; le code source de \texttt{F} est donné en {\sc Figure}~\ref{fig:p} et est une - traduction directe de l'application $F$; -\item les nouvelles valeurs des éléments \texttt{Xp} sont symboliquement envoyés aux - autres éléments qui en dépendent grâce à la fonction - \texttt{diffuse\_values(Xp)} (cf. \Sec{sub:spin:vt}); -\item finalement, le process informe le scheduler de la fin de la tâche - (au travers du sémaphore \texttt{sync\_mutex}). -\end{enumerate} - +L'implantation se déroule en cinq étapes: \begin{figure}[t] - \begin{minipage}[h]{.475\linewidth} +\begin{minipage}[b]{.32\linewidth} +\begin{tiny} +\begin{lstlisting} +inline update_X(){ + int countu; + countu = 0; + do + :: countu == N -> break ; + :: countu != N -> + X[countu] = Xp[countu]; + countu ++ ; + od +} +\end{lstlisting} +\end{tiny} +\caption{Sauvegarde de l'état courant}\label{fig:spin:sauve} +\end{minipage}\hfill% +\begin{minipage}[b]{.32\linewidth} \begin{tiny} \begin{lstlisting} active proctype update_elems(){ @@ -274,11 +406,11 @@ active proctype update_elems(){ } \end{lstlisting} \end{tiny} -\caption{Mise à jour des éléments.}\label{fig:proc} +\caption{Mise à jour des éléments}\label{fig:proc} \end{minipage}\hfill% %\end{figure} %\begin{figure} - \begin{minipage}[h]{.45\linewidth} + \begin{minipage}[b]{.33\linewidth} \begin{tiny} \begin{lstlisting} inline F(){ @@ -294,17 +426,41 @@ inline F(){ } \end{lstlisting} \end{tiny} -\caption{Application de la fonction $F$.}\label{fig:p} +\caption{Application de la fonction $f$}\label{fig:p} \end{minipage} \end{figure} +\begin{enumerate} +\item elle commence en mettant à jour la variable \texttt{X} avec les valeurs de \texttt{Xp} dans la fonction \texttt{update\_X},~\Fig{fig:spin:sauve} +\item elle mémorise dans \texttt{Xd} la valeur disponible pour chaque élément grâce à la fonction \texttt{fetch\_values}; cette fonction est détaillée +dans la section suivante; +\item une boucle %sur les \texttt{ar\_len} éléments qui peuvent être modifiés + met à jour itérativement la valeur de $j$ (grâce à l'appel de fonction \texttt{f(j)}) + pour peu que celui-ci doive être modifié, \textit{i.e.}, pour peu qu'il soit renseigné dans + \texttt{mods[count]}; le code source de \texttt{F} est donné en {\sc Figure}~\ref{fig:p} et est une + traduction directe de l'application $f$; +\item les nouvelles valeurs des éléments \texttt{Xp} sont symboliquement + envoyés aux autres éléments qui en dépendent grâce à la fonction + \texttt{diffuse\_values(Xp)}; cette dernière fonction est aussi détaillée + dans la section suivante; +\item finalement, le process informe le scheduler de la fin de la tâche + (au travers du sémaphore \texttt{sync\_mutex}). +\end{enumerate} + + + + + + + + \subsection{Gestion des délais}\label{sub:spin:vt} Cette section montre comment les délais inhérents au mode asynchrone sont traduits dans le modèle PROMELA grâce à deux fonctions \verb+fetch_values+ et \verb+diffuse_values+. -Celles-ci sont données en {\sc Figure}~\ref{fig:val} et~\ref{fig:broadcast}, -qui récupèrent et diffusent respectivement les valeurs des elements. +Celles-ci sont données en {\sc Figure}~\ref{fig:val} et~\ref{fig:broadcast}. +Elles récupèrent et diffusent respectivement les valeurs des éléments. \begin{figure}[t] \begin{minipage}[h]{.475\linewidth} @@ -377,30 +533,28 @@ La première fonction met à jour le tableau \verb+Xd+ requis pour les éléme qui doivent être modifiés. Pour chaque élément dans \verb+mods+, identifié par la variable $j$, la fonction récupère les valeurs des autres éléments (dont le libellé est $i$) -dont $j$ dépend. \JFC{vérifier si c'est ce sens ici} +dont $j$ dépend. Il y a deux cas. \begin{itemize} \item puisque $i$ connaît sa dernière valeur (\textit{i.e.}, $D^t_{ii}$ est toujours $t$) \verb+Xd[i].v[i]+ est donc \verb+Xp[i]+; -\item sinon, il y a deux sous cas qui peuvent peuvent potentiellement modifier la valeur +\item sinon, il y a deux sous-cas qui peuvent peuvent potentiellement modifier la valeur que $j$ a de $i$ (et qui peuvent être choisies de manière aléatoire): \begin{itemize} - \item depuis la perspective de $j$ la valeur de $i$ peut ne pas avoir changé ( - c'est l'instruction \verb+skip+) ou n'est pas utile; ce dernier cas apparaît + \item depuis la perspective de $j$ la valeur de $i$ peut ne pas avoir changé (c'est l'instruction \verb+skip+) ou n'est pas utile; ce dernier cas apparaît lorsqu'il n'y a pas d'arc de $i$ à $j$ dans le graphe d'incidence, \textit{i.e.}, lorsque - la valeur de \verb+is_succ+ qui est calculée par \verb+hasnext(i,j)+ is 0; + la valeur de \verb+is_succ+ qui est calculée par \verb+hasnext(i,j)+ est 0; dans ce cas, la valeur de \verb+Xd[j].v[i]+ n'est pas modifiée; \item sinon, on affecte à \verb+Xd[j].v[i]+ la valeur mémorisée dans le canal \verb+channels[i].sent[j]+ (pour peu que celui-ci ne soit pas vide). - Les valeurs des éléments sont ajoutées dans ce canal au travers de la fonction \verb+diffuse_values+ - donnée juste après. \end{itemize} \end{itemize} -L'objectif de la fonction \verb+diffuse_values+ est de stocker les valeurs de $X$ représenté -dans le modèle par \verb+Xp+ dans le canal \verb+channels+. -Il permet au modèle-checker SPIN d'exécuter -le modèle PROMELA comme s'il pouvait y avoir des délais entre processus +Les valeurs des éléments sont ajoutées dans ce canal au travers de la fonction \verb+diffuse_values+. L'objectif de cette fonction +est de stocker les valeurs de $x$ (représenté +dans le modèle par \verb+Xp+) dans le canal \verb+channels+. +Il permet au model-checker SPIN d'exécuter +le modèle PROMELA comme s'il pouvait y avoir des délais entre processus. Il y a deux cas différents pour la valeur de $X_{j}$: \begin{itemize} \item soit elle est \og perdue\fg{}, \og oubliée\fg{} pour permettre à $i$ de ne pas tenir compte d'une @@ -412,10 +566,10 @@ n'y a pas d'arc de $j$ à $i$ dans le graphe d'incidence; L'introduction de l'indéterminisme à la fois dans les fonctions \verb+fetch_values+ et \verb+diffuse_values+ est nécessaire dans notre contexte. Si celui-ci n'était présent que dans la fonction \verb+fetch_values+, nous ne pourrions pas par exemple récupérer -la valeur $X_i^{(t)}$ sans considérer la valeur $X_i^{(t-1)}$. +la valeur $x_i^{(t)}$ sans considérer la valeur $x_i^{(t-1)}$. De manière duale, si le non déterminisme était uniquement utilisé dans la fonction \verb+diffuse_values+, alors chaque fois qu'une valeur serait -mise dans le canal, elle serait immédiatement consommé, ce qui est contradictoire avec la notion de +mise dans le canal, elle serait immédiatement consommée, ce qui est contradictoire avec la notion de délai. % \subsection{Discussion} @@ -434,50 +588,60 @@ délai. % instructions, making the PROMELA code and the DDN as closed as possible. \subsection{Propriété de convergence universelle} -Il reste à formaliser dans le model checker SPIN que les itérations d'un système -dynamique à $n$ éléments est universellement convergent. +Il reste à formaliser dans le model checker SPIN le fait que les +itérations d'un système +dynamique à ${\mathsf{N}}$ éléments est universellement convergent. Rappelons tout d'abord que les variables \verb+X+ et \verb+Xp+ -contiennent respectivement la valeur de $X$ avant et après la mise à jour. +contiennent respectivement la valeur de $x$ avant et après la mise à jour. Ainsi, si l'on effectue une initialisation non déterministe de -\verb+Xp+ et si l'on applique une stratégie pseudo périodique, +\verb+Xp+ et si l'on applique une stratégie pseudo-périodique, il est nécessaire et suffisant de prouver la formule temporelle linéaire (LTL) suivante: \begin{equation} \diamond (\Box \verb+Xp+ = \verb+X+) \label{eq:ltl:conv} \end{equation} -où les opérateur $\diamond$ et $\Box$ on la sémantique usuelle \textit{i.e.}, à savoir +où les opérateurs $\diamond$ et $\Box$ ont +la sémantique usuelle, à savoir respectivement {\em éventuellement} et {\em toujours} dans les chemins suivants. -On note que cette propriété assure seulement la stabilisation du système, -mais ne donne aucune métrique quant à la manière dont celle-ci est obtenue. +On note que cette propriété, si elle est établie, garantit +la stabilisation du système. +Cependant elle ne donne aucune métrique quant à +la manière dont celle-ci est obtenue. En particulier, on peut converger très lentement ou le système peut même disposer de plusieurs points fixes. -vers plusieurs + \section{Correction et complétude de la démarche}\label{sec:spin:proof} -Cette section présente les théorème de correction et de complétude de l'approche. +Cette section présente les théorèmes +de correction et de complétude de l'approche (Théorèmes~\ref{Theo:sound} et~\ref{Theo:completeness}). Toutes les preuves sont déplacées en -annexes~\ref{anx:promela}. +annexe~\ref{anx:promela}. -\begin{theorem}[Correction]\label{Theo:sound} +\begin{restatable}[Correction de la traduction vers Promela]{theorem}{promelasound} +\label{Theo:sound} +% Soit $\phi$ un modèle de système dynamique discret et $\psi$ sa traduction PROMELA. Si $\psi$ vérifie la propriété LTL (\ref{eq:ltl:conv}) sous hypothèse d'équité faible, alors les itérations de $\phi$ sont universellement convergentes. -\end{theorem} - +\end{restatable} -\begin{theorem}[Complétude]\label{Theo:completeness} +\begin{restatable}[Complétude de la traduction vers Promela]{theorem}{promelacomplete} +\label{Theo:completeness} +% Soit $\phi$ un modèle de système dynamique discret et $\psi$ sa traduction. Si $\psi$ ne vérifie pas la propriété LTL (\ref{eq:ltl:conv}) sous hypothèse d'équité faible, alors les itérations de $\phi$ ne sont pas universellement convergentes. -\end{theorem} +\end{restatable} + + @@ -487,13 +651,14 @@ annexes~\ref{anx:promela}. Cette section donne tout d'abord quelques mesures de complexité de l'approche puis présente ensuite les expérimentations issues de ce travail. -\begin{theorem}[Nombre d'états ] - Soit $\phi$ un modèle de système dynamique discret à $n$ éléments, $m$ arc dans le graphe d'incidence +\begin{theorem}[Nombre d'états] + Soit $\phi$ un modèle de système dynamique discret à ${\mathsf{N}}$ éléments, $m$ + arcs dans le graphe d'incidence et $\psi$ sa traduction en PROMELA. Le nombre de configurations - de l'exécution en SPIN de $\psi$ est bornée par $2^{m\times(\delta_0+1)+n(n+2)}$. + de l'exécution en SPIN de $\psi$ est borné par $2^{m(\delta_0+1)+n(n+2)}$. \end{theorem} -\begin{Proof} - Une configuration est une valuation des variables globales. +\begin{proof} + Une configuration est une évaluation des variables globales. Leur nombre ne dépend que de celles qui ne sont pas constantes. Les variables \verb+Xp+ et \verb+X+ engendrent $2^{2n}$ états. @@ -502,37 +667,41 @@ puis présente ensuite les expérimentations issues de ce travail. Chaque canal de \verb+array_of_channels+ peut engendrer $1+2^1+\ldots+2^{\delta_0}= 2^{\delta_0+1}-1$ états. Puisque le nombre d'arêtes du graphe d'incidence est $m$, - il y a $m$ canaux non constants, ce qui génère approximativement $2^{m\times(\delta_0+1)}$ états. - Le nombre de configurations est donc borné par $2^{m\times(\delta_0+1)+n(n+2)}$. - On remarque que cette borne est traitable par SPIN pour des valeurs raisonnables de $n$, + il y a $m$ canaux non constants, ce qui génère approximativement $2^{m(\delta_0+1)}$ états. + Le nombre de configurations est donc borné par $2^{m(\delta_0+1)+n(n+2)}$. + On remarque que cette borne est traitable par SPIN pour des valeurs raisonnables de ${\mathsf{N}}$, $m$ et $\delta_0$. - \JFC{Donner un ordre de grandeur de cet ordre de grandeur} + %\JFC{Donner un ordre de grandeur de cet ordre de grandeur} -\end{Proof} +\end{proof} -La méthode détaillée ici a pu être appliquée sur l'exemple jouet -pour prouver formellement sa convergence uniforme. +La méthode détaillée ici a pu être appliquée sur l'exemple +pour prouver formellement sa convergence universelle. On peut remarquer que SPIN n'impose l'équité faible qu'entre les process -alors que les preuves des deux théorèmes précédentes reposent sur le fait que -celle-ci est établie dès qu'un choix indéterministe est effectué. +alors que les preuves des deux théorèmes précédents reposent sur le fait que +cette équité est établie dès qu'un choix indéterministe est effectué. Naïvement, on pourrait considérer comme hypothèse la formule suivante chaque fois qu'un choix indéterministe se produit entre $k$ événements -respectivement notés $l1$, \ldots $lk$: +respectivement notés $l_1$, \ldots $l_k$: $$ -[] <> (l == l0) \Rightarrow -(([] <> (l== l1)) \land \ldots \land ([] <> (l == lk))) +\Box \diamond (l == l_0) \Rightarrow +((\Box \diamond (l== l_1)) \land \ldots \land (\Box \diamond (l == l_k))) $$ -où le libellé $l0$ dénote le libellé de la ligne précédent le choix indéterministe. +où le libellé $l_0$ dénote le libellé de la ligne précédent +le choix indéterministe. Cette formule traduit exactement l'équité faible. Cependant en raison de l'explosion de la taille du produit entre l'automate de Büchi issu de cette formule et celui issu du programme PROMELA, -SPIN n'arrive pas à vérifier si la convergence uniforme est établie ou non sur des exemples -simples\JFC{faire référence à un tel exemple}. - -Ce problème a été pratiquement résolu en laissant SPIN générer toutes les traces d'exécution, -même les non équitables, puis en le laissant vérifier la propriété de convergence dessus. +SPIN n'arrive pas à vérifier si la convergence universelle est établie +ou non sur des exemples +simples.%\JFC{faire référence à un tel exemple}. + +Ce problème a été pratiquement résolu en laissant SPIN +générer toutes les traces d'exécution, +même celles qui ne sont pas équitables, +puis ensuite vérifier la propriété de convergence sur toutes celles-ci. Il reste alors à interpréter les résultats qui peuvent être de deux types. Si la convergence est établie pour toutes les traces, elle le reste en particulier pour les traces équitables. Dans le cas contraire on doit analyser le contre exemple produit par SPIN. @@ -551,106 +720,118 @@ Dans le cas contraire on doit analyser le contre exemple produit par SPIN. La méthode détaillée ici a été appliquée sur des exemples pour prouver formellement -leur convergence ou leur divergence (Fig.~\ref{fig:async:exp}). -Dans ces expériences, les délais on été bornés par $\delta_0=10$. -Dans ce tableau, $P$ est vrai ($\top$) si et seulement si la convergence uniforme -est établie et faux ($\bot$) sinon. Le nombre $M$ et la taille de la mémoire consommée (en MB) et +leur convergence ou leur divergence (\Fig{fig:exp:promela}) +avec ou sans délais. +Dans ces expériences, les délais ont été bornés par $\delta_0=10$. +Dans ce tableau, $P$ est vrai ($\top$) si et seulement si la convergence +universelle +est établie et faux ($\bot$) sinon. Le nombre $M$ est +la taille de la mémoire consommée (en MB) et $T$ est le temps d'exécution sur un Intel Centrino Dual Core 2 Duo @1.8GHz avec 2GB de mémoire vive pour établir un verdict. -L'exemple RE est l'exemple jouet de ce chapitre, -AC2D est un automate cellulaire avec 9 elements prenant des valeurs booléennes en fonction de -de 4 voisins et BM99, issu de~\cite{BM99} consiste en 10 process -qui modifient leur valeur booléennes dans un graphe d'adjacence proche du graphe complet. - -\begin{figure} -\begin{center} -\tiny -\begin{tabular}{|*{13}{c|}} -\cline{2-13} -\multicolumn{1}{c|}{ } -&\multicolumn{6}{|c|}{Mixed Mode} & \multicolumn{6}{|c|}{Only Bounded} \\ -\cline{2-13} -\multicolumn{1}{c|}{ } -&\multicolumn{3}{|c|}{Parallel} & \multicolumn{3}{|c|}{Pseudo-Periodic} & -\multicolumn{3}{|c|}{Parallel} & \multicolumn{3}{|c|}{Pseudo-Periodic} \\ -\cline{2-13} -\multicolumn{1}{c|}{ } -&P & M & T & -P & M & T & -P & M & T& -P & M & T \\ -\hline %cline{2-13} -Running Example & -$\top$ & 409 & 1m11s& -$\bot$ & 370 & 0.54 & -$\bot$ & 374 & 7.7s& -$\bot$ & 370 & 0.51s \\ -\hline %\cline{2-13} -AC2D -&$\bot$ & 2.5 & 0.001s % RC07_async_mixed.spin -&$\bot$ & 2.5 & 0.01s % RC07_async_mixed_all.spin -&$\bot$ & 2.5 & 0.01s % RC07_async.spin -&$\bot$ & 2.5 & 0.01s \\ % RC07_async_all.spin -\hline %\cline{2-13} -BM99 -&$\top$ & & %BM99_mixed_para.spin -&$\top$ & & % RC07_async_mixed_all.spin -&$\bot$ & & % RC07_async.spin -&$\bot$ & & \\ % RC07_async_all.spin -\hline %\cline{2-13} -\end{tabular} -\end{center} -\caption{Expérimentations avec des itérations asynchrones}\label{fig:async:exp} +\begin{figure}[ht] + \begin{center} + \begin{tiny} + \subfigure[Sans délais]{ + \begin{tabular}{|*{7}{c|}} + \cline{2-7} + \multicolumn{1}{c|}{ } + &\multicolumn{3}{|c|}{Synchrones} & \multicolumn{3}{|c|}{Généralisées} \\ + \cline{2-7} + \multicolumn{1}{c|}{ }& + P & M & T& + P & M & T \\ + \hline %\cline{2-7} + \textit{RE} & + $\top$ & 2.7 & 0.01s & + $\bot$ & 369.371 & 0.509s \\ + \hline %\cline{2-7} + \cite{RC07} & + $\bot$ & 2.5 & 0.001s & % RC07_sync.spin + $\bot$ & 2.5 & 0.01s \\ % RC07_sync_chao_all.spin + \hline + \cite{BM99} & + $\top$ & 36.7 & 12s & % BM99_sync_para.spin + $\top$ & & \\ % BM99_sync_chao.spin + \hline + \end{tabular} + \label{fig:sync:exp} + } + + \subfigure[Avec délais]{ + \begin{tabular}{|*{13}{c|}} + \cline{2-13} + \multicolumn{1}{c|}{ } + &\multicolumn{6}{|c|}{Mode Mixte} & \multicolumn{6}{|c|}{Seulement borné} \\ + \cline{2-13} + \multicolumn{1}{c|}{ } + &\multicolumn{3}{|c|}{Synchrones} & \multicolumn{3}{|c|}{Pseudo-Périodique} & + \multicolumn{3}{|c|} {Synchrones} & \multicolumn{3}{|c|}{Pseudo-Périodique} \\ + \cline{2-13} + \multicolumn{1}{c|}{ } + &P & M & T & + P & M & T & + P & M & T& + P & M & T \\ + \hline %cline{2-13} + \textit{RE} & + $\top$ & 409 & 1m11s& + $\bot$ & 370 & 0.54 & + $\bot$ & 374 & 7.7s& + $\bot$ & 370 & 0.51s \\ + \hline %\cline{2-13} + \cite{RC07} + &$\bot$ & 2.5 & 0.001s % RC07_async_mixed.spin + &$\bot$ & 2.5 & 0.01s % RC07_async_mixed_all.spin + &$\bot$ & 2.5 & 0.01s % RC07_async.spin + &$\bot$ & 2.5 & 0.01s \\ % RC07_async_all.spin + \hline %\cline{2-13} + \cite{BM99} + &$\top$ & & %BM99_mixed_para.spin + &$\top$ & & % RC07_async_mixed_all.spin + &$\bot$ & & % RC07_async.spin + &$\bot$ & & \\ % RC07_async_all.spin + \hline %\cline{2-13} + \end{tabular} + \label{fig:async:exp} + } + \end{tiny} + \end{center} + \caption{Résultats des simulations Promela des SDDs}\label{fig:exp:promela} \end{figure} -L'exemple~\cite{RC07} concerne un réseau composé de deux gènes à valeur dans $\{0,1,2\}$. -Comme la convergence n'est déjà pas établie pour les itérations parallèles, il en est donc +L'exemple \textit{RE} est l'exemple de ce chapitre, +\cite{RC07} concerne un réseau composé de deux gènes +à valeur dans $\{0,1,2\}$ et +\cite{BM99} consiste en 10 process +qui modifient leurs valeurs booléennes dans un graphe d'adjacence proche +du graphe complet. + + +L'exemple \textit{RE} a été prouvé comme universellement convergent. +%\JFC{statuer sur AC2D} +Comme la convergence n'est déjà pas établie pour les itérations synchrones +de~\cite{RC07}, il en est donc de même pour les itérations asynchrones. -LA {\sc Figure}~\ref{fig:RC07CE} donne une trace de la sortie de SPIN de menant à la violation +La {\sc Figure}~\ref{fig:RC07CE} donne une trace de la sortie de SPIN menant à la violation de la convergence. Celle-ci correspond à une stratégie périodique qui répète -$\{1,2\};\{1,2\};\{1\};\{1,2\};\{1,2\}$ et débute avec $X=(0,0)$. - - -Dans l'exemple issu de~\cite{BM99}, nous avons 10 process -à valeur booléennes. En raison de la dépendance forte entre les éléments, +$\{1,2\};\{1,2\};\{1\};\{1,2\};\{1,2\}$ et débute avec $x=(0,0)$. +En raison de la dépendance forte entre les éléments +de~\cite{BM99}, $\delta_0$ est réduit à 1. Cela aboutit cependant à $2^{100}$ -configurations dans le mode des itérations asynchrones. -La convergence des itérations asynchrones de l'exemple~\cite{BCVC10:ir} n'est pas établie -lorsque pour $\delta_0$ vaut 1. Il ne peut donc y avoir convergence uniforme. +configurations dans le mode des itérations asynchrones, montrant les limites de +l'approche. \begin{figure} -\begin{center} -\begin{tiny} -\begin{tabular}{|*{7}{c|}} -\cline{2-7} -\multicolumn{1}{c|}{ } -&\multicolumn{3}{|c|}{Parallel} & \multicolumn{3}{|c|}{Pseudo-Periodic} \\ -\cline{2-7} -\multicolumn{1}{c|}{ }& -P & M & T& -P & M & T \\ -\hline %\cline{2-7} -Running & -$\top$ & 2.7 & 0.01s & -$\bot$ & 369.371 & 0.509s \\ -\hline %\cline{2-7} -\cite{RC07} exemples & -$\bot$ & 2.5 & 0.001s & % RC07_sync.spin -$\bot$ & 2.5 & 0.01s \\ % RC07_sync_chao_all.spin -\hline -\cite{BM99} exemple & -$\top$ & 36.7 & 12s & % BM99_sync_para.spin -$\top$ & & \\ % BM99_sync_chao.spin -\hline -\end{tabular} -\end{tiny} -\end{center} -\caption{Expérimentations avec des itérations synchrones}\label{fig:sync:exp} -\end{figure} +\centering +\includegraphics[scale=0.6]{images/RC07ce.eps} +\caption{Contre exemple de convergence pour~~\cite{RC07}} \label{fig:RC07CE} +\end{figure} + @@ -680,28 +861,19 @@ $\top$ & & \\ % BM99_sync_chao.spin \section{Conclusion} \label{sec:spin:concl} -Des méthodes de simulation basées sur des stratégies et des délais générés aléatoirement -ont déjà été présentées~\cite{BM99,BCV02}. -Cependant, comme ces implantations ne sont pas exhaustives, elles ne donnent un résultat -formel que lorsqu'elles fournissent un contre-exemple. Lorsqu'elles exhibent une convergence, -cela ne permet que donner une intuition de convergence, pas une preuve. -Autant que nous sachions, aucune démarche de preuve formelle de convergence n'a jamais été établie. -Dans le travail théorique~\cite{Cha06}, Chandrasekaran a montré que les itérations asynchrones sont convergentes -si et seulement si on peut construire une fonction de Lyaponov décroissante, mais il ne donne pas de méthode -automatique pour construire cette fonction. - -\JFC{Déplacer ceci dans les perspective} -Among drawbacks of the method, one can argue that bounded delays is only -realistic in practice for close systems. -However, in real large scale distributed systems where bandwidth is weak, -this restriction is too strong. In that case, one should only consider that -matrix $S^{t}$ follows the iterations of the system, \textit{i.e.}, -for all $i$, $j$, $1 \le i \le j \le n$, we have$ -\lim\limits_{t \to \infty} S_{ij}^t = + \infty$. -One challenge of this work should consist in weakening this constraint. -We plan as future work to take into account other automatic approaches -to discharge proofs notably by deductive analysis~\cite{CGK05}. +L'idée principale de ce chapitre est que l'on peut, +pour des réseaux booléens à délais bornés de petite taille, obtenir +une preuve de la convergence ou de sa divergence et ce +de manière automatique. +L'idée principale est de traduire le réseau en PROMELA et de laisser +le model checker établir la preuve. +Toute l'approche a été prouvée: le verdict rendu par l'approche +a donc valeur de vérité. +L'approche a cependant ses limites et ne peut donc pas être +apliquée qu'à des modèles simplifiés de programmes. +La suite de ce travail consiste à se focaliser sur les systèmes qui ne +convergent pas.