💻 computer science

A rewriting-logic-with-SMT-based formal analysis and parameter synthesis framework for parametric time Petri nets

Cet article présente un cadre d'analyse formelle et de synthèse de paramètres pour les réseaux de Petri temporels paramétriques avec arcs inhibiteurs, basé sur une sémantique en logique de réécriture implémentée dans Maude couplée à la résolution SMT, offrant des garanties de bisimilarité, une terminabilité garantie et des performances supérieures à l'outil Romeo.

Auteurs originaux : Jaime Arias, Kyungmin Bae, Carlos Olarte, Peter Csaba Ölveczky, Laure Petrucci

Publié 2026-04-08

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jaime Arias, Kyungmin Bae, Carlos Olarte, Peter Csaba Ölveczky, Laure Petrucci

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🕰️ Le Problème : L'Horloge Mystérieuse

Imaginez que vous êtes l'architecte d'une usine très complexe. Dans cette usine, des pièces circulent sur des tapis roulants (ce sont les places d'un réseau de Petri) et des machines les transforment (ce sont les transitions).

Le problème, c'est que vous ne connaissez pas exactement le temps que mettent les machines pour travailler. Vous savez juste que ça prend "entre 2 et 5 minutes", ou peut-être "entre 2 et X minutes", où X est une valeur inconnue que vous devez trouver. De plus, certaines machines ne démarrent que si une autre machine est vide (c'est l'arc inhibiteur).

C'est ce qu'on appelle un Réseau de Petri Temporel Paramétrique (PITPN). Le but est de trouver la valeur de X (et d'autres paramètres) pour que l'usine fonctionne parfaitement sans jamais se bloquer ou produire trop de pièces en même temps.

🛠️ Les Anciens Outils : Le "Roméo"

Jusqu'à présent, les experts utilisaient un outil très puissant appelé Roméo. C'est comme un super-calculateur spécialisé qui peut dire : "Si vous réglez X à 3, ça marche. Si vous le réglez à 4, ça plante."

Mais Roméo a des limites :

Il est un peu rigide : il ne peut pas répondre à des questions trop compliquées ou trop abstraites.
Il ne peut pas dire : "Quelle quantité de pièces initiales faut-il mettre pour que ça marche ?"
Parfois, il dit "Peut-être" (ce qui n'est pas une réponse satisfaisante) ou il s'égare dans des calculs infinis.

🚀 La Nouvelle Solution : Maude + SMT

Les auteurs de ce papier ont créé une nouvelle méthode basée sur Maude (un langage de programmation logique très flexible) couplé à un Solveur SMT (un détective mathématique ultra-rapide).

Voici comment ils ont fait, avec une analogie :

1. La Traduction (Le Dictionnaire)

Imaginez que Roméo parle une langue très technique et spécifique. Maude, lui, parle une langue universelle et très expressive. Les auteurs ont créé un "traducteur" (une sémantique formelle) qui convertit le plan de l'usine (le PITPN) en un langage que Maude comprend parfaitement. Ils ont prouvé que cette traduction est fidèle : l'usine traduite se comporte exactement comme l'originale.

2. Le Détective Mathématique (SMT)

Au lieu de tester chaque valeur de X une par une (ce qui prendrait une éternité), ils utilisent le SMT.

Analogie : Imaginez que vous cherchez un trésor. Au lieu de creuser chaque mètre carré de la plage (méthode ancienne), vous utilisez un détecteur de métaux qui vous dit : "Le trésor se trouve quelque part dans cette zone, et il doit être plus lourd que 5kg". Le SMT fait cela avec les mathématiques : il trouve toute la zone de valeurs possibles pour X qui fonctionne, sans avoir à tester chaque nombre individuellement.

3. Le Grand Pliage (La Méthode de "Folding")

C'est la grande innovation du papier.

Le problème : Quand on simule une usine avec des paramètres inconnus, le nombre de situations possibles devient infini. C'est comme essayer de dessiner toutes les branches d'un arbre qui grandit sans cesse.
La solution : Les auteurs ont inventé une technique de "pliage" (folding).
Analogie : Imaginez que vous explorez une grotte. Vous tombez sur une pièce qui ressemble exactement à une pièce que vous avez déjà visitée plus tôt, même si les détails sont légèrement différents. Au lieu de continuer à explorer cette nouvelle pièce (ce qui serait une perte de temps), vous dites : "Attends, j'ai déjà vu ça ! Je vais 'plier' cette nouvelle carte sur l'ancienne."
Grâce à cette astuce intelligente, leur méthode s'arrête toujours quand il y a une solution, là où d'autres méthodes s'épuisent.

🏆 Les Résultats : Qui gagne ?

Les auteurs ont comparé leur nouvelle méthode (Maude + SMT) avec l'ancien champion (Roméo) sur plusieurs cas d'usines complexes.

Vitesse : Étonnamment, leur prototype (qui est encore une "maquette" en langage de haut niveau) bat souvent Roméo, qui est pourtant un logiciel très optimisé écrit en C++. C'est comme si un vélo de course fait par des amateurs battait une Formule 1 dans certains virages !
Puissance : Leur méthode réussit à trouver des solutions là où Roméo dit "Je ne sais pas" ou "Peut-être".
Nouveautés : Ils peuvent maintenant répondre à des questions que Roméo ne pouvait pas poser, comme : "Quelle est la configuration initiale des pièces pour que l'usine soit sûre ?" ou "Que se passe-t-il si je force toujours la machine A à travailler avant la machine B ?"

💡 En Résumé

Ce papier nous dit essentiellement :

"Nous avons pris un problème complexe de gestion du temps et d'incertitude dans les systèmes industriels. Au lieu de forcer le problème à rentrer dans un moule rigide, nous l'avons traduit dans un langage flexible (Maude) et nous avons utilisé un détective mathématique (SMT) pour trouver toutes les solutions possibles d'un coup. De plus, nous avons inventé une astuce de pliage pour éviter de tourner en rond. Le résultat ? Une méthode plus rapide, plus complète et capable de répondre à des questions que personne ne pouvait poser avant."

C'est une avancée majeure qui ouvre la porte à la conception de systèmes plus sûrs et plus intelligents, des réseaux de transport aux systèmes biologiques, en passant par les logiciels critiques.

1. Problématique

Les Réseaux de Petri Temporels Paramétriques avec arcs inhibiteurs (PITPNs) sont un modèle puissant pour les systèmes temps réel où les bornes de temps des transitions peuvent être inconnues ou partiellement connues (représentées par des paramètres). L'objectif est de synthétiser les valeurs de ces paramètres (ainsi que des marquages initiaux) pour garantir que le système satisfasse certaines propriétés (sûreté, vivacité, etc.).

Bien que l'outil Roméo soit l'état de l'art pour l'analyse des PITPNs, il présente plusieurs limitations :

Il ne supporte pas les propriétés temporelles logiques complètes (LTL imbriquée).
Il ne permet pas de synthétiser des marquages initiaux paramétriques.
Il ne permet pas facilement d'analyser le système sous des stratégies d'exécution définies par l'utilisateur (ex: priorités de tir de transitions).
Il manque d'un environnement flexible pour prototyper rapidement de nouvelles méthodes d'analyse.
Dans certains cas, il renvoie des résultats « peut-être » (approximations) ou échoue à trouver des solutions existantes.

Le défi principal réside dans le fait que l'analyse des systèmes temps réel denses avec paramètres est souvent indécidable, et les méthodes explicites (états concrets) ne sont pas complètes ou sûres pour les domaines denses.

2. Méthodologie

Les auteurs proposent un cadre formel basé sur la Logique de Réécriture (Rewriting Logic) implémentée dans l'outil Maude, couplé à des solveurs SMT (Satisfiability Modulo Theories).

A. Sémantique Logique de Réécriture

L'article définit deux types de sémantique pour les PITPNs :

Sémantique « Concrète » (R0, R1, R2) : Une modélisation en style « Real-Time Maude » utilisant des horloges pour suivre le temps écoulé depuis que les transitions sont activées. Cette sémantique est prouvée bisimilaire à la sémantique standard des PITPNs. Cependant, elle n'est pas directement exécutable pour l'analyse symbolique car elle introduit des variables de temps non bornées dans les règles de réécriture.
Sémantique « Symbolique » (RS1, RS2, RS3) : Une transformation de la sémantique concrète pour permettre l'exécution symbolique. Les états sont représentés par des termes contenant des variables SMT (entiers et réels) et des contraintes logiques accumulées. Cela permet de raisonner sur tous les paramètres simultanément.

B. Analyse Symbolique et Synthèse de Paramètres

L'approche utilise Maude-SE (une extension de Maude avec SMT) pour effectuer des réécritures symboliques sur des termes contraints ( $\phi \parallel t$ ), où $\phi$ est une contrainte SMT et $t$ un état.

Synthèse de paramètres : Au lieu de tester des valeurs, le système explore l'espace d'états symbolique et accumule les contraintes nécessaires pour atteindre un état cible (ex: « place $p$ a $>n$ jetons »).
Stratégies d'exécution : L'utilisation du langage de stratégies de Maude permet de restreindre l'exploration à des comportements spécifiques définis par l'utilisateur.

C. Le Défi de la Terminaison et la Nouvelle Méthode de « Folding »

Un problème majeur de l'analyse symbolique est la terminaison : même si le graphe des classes d'états est fini, l'analyse symbolique peut ne pas terminer car les états symboliques équivalents ne sont pas identiques syntaxiquement (à cause de variables SMT fraîches générées à chaque pas de temps).

Les auteurs proposent une nouvelle méthode de « folding » (repliement) pour les états symboliques :

Ils définissent une relation de subsumption ( $\preceq$ ) basée sur l'élimination des variables existentielles (quantification existentielle) des horloges passées.
Deux implémentations sont proposées :
1. Une version utilisant la commande standard search de Maude avec une transformation de théorie (repliement local à une branche).
2. Une version utilisant les fonctionnalités de méta-niveau de Maude pour implémenter une recherche en largeur (BFS) avec un ensemble global d'états visités, permettant de replier des états équivalents sur différentes branches de l'arbre de recherche.
Élimination de Fourier-Motzkin : Pour gérer les quantificateurs existentiels de manière indépendante du solveur SMT, les auteurs ont implémenté la procédure d'élimination de Fourier-Motzkin (FME) directement comme une théorie équationnelle dans Maude, remplaçant la dépendance exclusive au solveur Z3.

3. Contributions Clés

Sémantique Bisimilaire : Preuve formelle que la sémantique de réécriture proposée est bisimilaire à la sémantique standard des PITPNs.
Cadre d'Analyse Unifié : Un framework Maude capable de réaliser presque toutes les analyses supportées par Roméo, plus des fonctionnalités avancées :
- Synthèse de marquages initiaux paramétriques (pas seulement des bornes de tir).
- Vérification de modèles LTL complète (formules imbriquées).
- Analyse sous stratégies d'exécution définies par l'utilisateur.
- Support de propriétés sur les horloges de transitions (pas seulement sur les marquages).
Méthode de Folding Nouvelle et Complète : Développement d'une procédure de repliement d'états symboliques garantissant que l'analyse de reachabilité termine si le graphe des classes d'états du PITPN est fini.
Indépendance du Solveur SMT : Grâce à l'implémentation de Fourier-Motzkin en Maude, le framework fonctionne avec n'importe quel solveur SMT connecté (Yices2, CVC4, Z3).

4. Résultats Expérimentaux

Les auteurs ont comparé leur approche (Maude + SMT) avec l'outil Roméo (v3.9.4) sur six benchmarks (systèmes producteur-consommateur, ordonnancement, tutoriels, etc.).

Performance : Dans de nombreux cas, le prototype Maude (surtout avec le solveur Yices2) surpasse Roméo en temps d'exécution.
Terminaison et Complétude :
- Maude termine là où Roméo échoue (timeout ou boucle infinie).
- Maude trouve des solutions que Roméo rate (parfois en renvoyant « maybe »).
- Les solutions trouvées par Maude ont été validées en les injectant dans Roméo.
Comparaison des versions : La nouvelle version utilisant l'élimination de Fourier-Motzkin et le folding global (méta-niveau) est nettement plus performante que la version précédente (conférence [35]) qui dépendait de Z3 pour l'élimination de quantificateurs et n'avait pas de folding global.
Limites : L'utilisation de solveurs comme Z3 ou CVC4 avec Maude-SE est plus lente que l'utilisation directe de Maude avec Yices2.

5. Signification et Impact

Cet article représente une avancée significative dans l'analyse formelle des systèmes temps réel paramétriques :

Flexibilité et Prototypage : L'approche basée sur Maude offre un « bac à sable » idéal pour développer et tester rapidement de nouvelles méthodes d'analyse et de synthèse, ce qui est difficile avec des outils dédiés et optimisés comme Roméo (écrit en C++).
Extension des Capacités d'Analyse : Il comble le vide laissé par les outils existants en permettant la synthèse de marquages initiaux et l'analyse LTL complète, élargissant ainsi le champ d'application des PITPNs.
Preuve de Concept pour les Systèmes Denses : Il démontre qu'il est possible de transformer des modèles d'interpréteurs complexes (avec fonctions, équations et marquages non bornés) en théories de réécriture symboliques pour lesquelles des analyses sûres et complètes sont possibles, ouvrant la voie à l'extension de cette approche à d'autres classes de systèmes temps réel denses.

En résumé, ce travail propose une alternative puissante et plus flexible à l'outil Roméo, prouvant que la combinaison de la logique de réécriture et des solveurs SMT peut non seulement égaler, mais souvent dépasser les performances des outils spécialisés tout en offrant des fonctionnalités d'analyse inédites.