💻 computer science

The Machine Proposes. The Proof Disposes: Neuro-Symbolic Synthesis of Formally Verified Markov Usage Models from Natural Language Requirements

Cet article introduit Neuro-Symbolic MBST, un cadre qui automatise la synthèse de modèles d'usage de Markov formellement vérifiés à partir d'exigences en langage naturel en intégrant l'apprentissage L*, des LLM contraints par une grammaire et l'optimisation convexe, atteignant ainsi une détection de fautes et une couverture de haute fidélité qui surpassent significativement les bases purement neurales tout en éliminant les goulots d'étranglement de la modélisation manuelle pour les systèmes critiques de sécurité.

Auteurs originaux : Nathan Ginting

Publié 2026-07-28

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Nathan Ginting

Article original sous licence CC BY 4.0 (https://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

Imaginez que vous essayez d'apprendre à un robot à conduire une voiture ou à naviguer sur un site web. Pour ce faire en toute sécurité, vous avez besoin d'une carte de tous les mouvements possibles que le robot peut effectuer. Dans le monde des tests logiciels, cette carte est appelée un « modèle d'usage ». C'est comme un organigramme qui montre chaque état dans lequel le système peut se trouver (comme « freinage » ou « panier d'achat plein ») et la probabilité de passer d'un état à un autre (comme « il y a 80 % de chances que l'utilisateur clique sur 'acheter' »).

Pendant des décennies, des experts ont utilisé ces cartes pour exécuter des « tests statistiques ». Au lieu de simplement vérifier si le code fonctionne une seule fois, ils utilisent la carte pour simuler des milliers de parcours aléatoires à travers le système. Si la carte est précise, les tests trouveront des bugs cachés qui n'apparaissent que dans des situations rares et complexes. Cependant, il y a un énorme problème : dessiner ces cartes à la main est lent, ennuyeux et sujet à l'erreur humaine. C'est comme essayer de dessiner une carte détaillée d'une ville entière les yeux bandés. Récemment, nous avons eu un nouvel outil : l'Intelligence Artificielle (IA) qui peut lire du texte et deviner à quoi la carte devrait ressembler. Mais voici le hic : l'IA est douée pour deviner la forme de la carte, mais elle est très mauvaise pour obtenir les chiffres corrects. Elle peut inventer une route qui n'existe pas, ou dire qu'il y a 150 % de chances de pluie (ce qui est impossible). Cette publication pose la question suivante : pouvons-nous combiner la créativité de l'IA avec un « livre de règles » mathématique strict pour construire automatiquement une carte parfaite ?

Le document, intitulé « The Machine Proposes. The Proof Disposes » (La machine propose. La preuve dispose), présente un nouveau système appelé NeSy-MBST. Voyez cela comme l'union entre un écrivain créatif et un professeur de mathématiques strict. Le « écrivain » est un Modèle de Langage Étendu (LLM), une IA qui lit les exigences en langage naturel (comme « l'utilisateur doit pouvoir ajouter des articles au panier ») et propose une ébauche de la carte du système. Le « professeur de mathématiques » est un solveur symbolique, un programme informatique qui vérifie l'ébauche par rapport aux lois des mathématiques.

Voici comment l'équipe travaille ensemble :

La Proposition : L'IA lit les exigences et esquisse les états et les transitions. Elle est rapide et comprend bien le langage humain.
La Preuve : Le professeur de mathématiques vérifie immédiatement l'esquisse. L'IA a-t-elle inventé une transition physiquement impossible ? A-t-elle oublié une étape ? Le professeur dit : « Non, cette route n'existe pas » ou « Vous avez manqué un tournant ».
La Correction : L'IA reçoit le feedback, corrige la carte et réessaie.
Les Chiffres : Une fois que la forme de la carte est parfaite, le professeur de mathématiques prend le relais pour attribuer les probabilités. Au lieu que l'IA ne devine les chiffres (ce qui mène souvent à des erreurs), le professeur utilise un « optimiseur convexe » pour calculer les probabilités exactes afin qu'elles totalisent correctement 100 % et reflètent l'utilisation réelle.

Les chercheurs ont testé ce système sur deux types de défis : un véhicule autonome (un système de voiture autonome) et deux sites de commerce électronique (une page de shopping utilisateur et un tableau de bord administrateur). Ils ont comparé ce nouveau système de « collaboration » à l'utilisation de l'IA seule et à l'utilisation des méthodes manuelles traditionnelles.

Les résultats sont impressionnants. En utilisant l'IA seule, le système manquait environ la moitié des chemins importants et commettait des erreurs dans la structure de la carte. Mais avec l'équipe NeSy-MBST, le système a obtenu un score de 0,9125 sur une échelle où 0,90 est le seuil de sécurité requis pour les systèmes critiques comme les voitures autonomes. Cela signifie que l'IA seule n'était pas suffisante, mais que l'équipe a réussi le test de sécurité.

Plus précisément, le nouveau système a réussi à couvrir 85,7 % des transitions possibles (les chemins que le système peut prendre), alors que la version utilisant uniquement l'IA n'en couvrait que 50 %. Il s'agit d'un gain massif de 35,7 points de pourcentage. En clair, le nouveau système a trouvé une plus grande variété de bugs potentiels car il n'a pas manqué les « impasses » ou les « routes impossibles » que l'IA seule continuait d'halluciner.

L'article a également examiné la précision des chiffres. Il a utilisé une métrique appelée divergence de Jensen–Shannon pour mesurer à quel point les estimations de probabilité de l'IA étaient proches des mathématiques réelles. Le nouveau système a obtenu un score de 0,012, ce qui est extrêmement proche de la perfection, tandis que la version IA seule était beaucoup plus éloignée avec 0,157. Cela prouve que le professeur de mathématiques a réussi à corriger les mauvais calculs de l'IA.

Les chercheurs ont mené une expérience spéciale appelée « étude d'ablation » pour voir quelle partie de l'équipe effectuait le plus gros du travail. Ils ont découvert que la boucle de vérification symbolique (le professeur de mathématiques vérifiant la structure de la carte) était la raison principale pour laquelle le système trouvait tellement plus de chemins. L'optimiseur convexe (le professeur de mathématiques effectuant les calculs de probabilité) était la raison principale pour laquelle les chiffres étaient si précis. La boucle de rétroaction fermée (où le système apprend en exécutant des tests) aidait un peu, mais la magie centrale résidait dans la collaboration initiale.

En conclusion, cet article suggère que nous n'avons pas à choisir entre la vitesse de l'IA et la sécurité des experts humains. En laissant l'IA proposer des idées et un système mathématique strict vérifier et corriger ses propositions, nous pouvons construire des cartes de tests logiciels qui sont à la fois rapides à créer et assez sûres pour les systèmes critiques. Les auteurs notent que si cela fonctionne très bien pour les systèmes testés (jusqu'à 42 états), des travaux supplémentaires sont nécessaires pour voir si cela s'adapte à des systèmes industriels massifs et complexes. Mais pour l'instant, ils ont démontré que « La machine propose » est un excellent début, tant que « La preuve dispose » de toute erreur avant que la carte finale ne soit utilisée.

Résumé Technique : Synthèse Neuro-Symbolique de Modèles d'Usage de Markov Formellement Vérifiés

1. Énoncé du Problème

Le principal goulot d'étranglement empêchant l'adoption généralisée des tests statistiques basés sur les modèles (MBST - Model-Based Statistical Testing) au-delà des niches critiques pour la sécurité est la construction manuelle des modèles de chaînes de Markov d'usage. Ces modèles sont essentiels pour déplacer les objectifs de test de la couverture de code absolue vers l'inférence statistique concernant la qualité attendue sur le terrain. Cependant, traduire des exigences en langage naturel ambiguës et non structurées en topologies de transition d'états vérifiées et en matrices de probabilités mathématiquement cohérentes nécessite une expertise significative en méthodes formelles.

Bien que les grands modèles de langage (LLM) aient démontré des capacités d'extraction syntaxique, les approches purement neuronales souffrent de quatre limitations critiques lorsqu'elles sont appliquées au MBST :

Volatilité Stochastique et Hallucination : Les LLM peuvent omettre des cas limites critiques, construire des transitions impossibles ou violer les invariants du système, conduisant à des cas de test invalides.
Échec de Calibrage : Les LLM peinent avec le raisonnement numérique précis, échouant souvent à satisfaire les contraintes strictes de stochasticité de ligne ( $\sum_j p_{ij} = 1$ ) et les contraintes multi-variables complexes requises pour des chaînes de Markov valides.
Explosion de l'Espace d'États : Les LLM opérant dans des fenêtres de contexte finies ne peuvent pas suivre ou générer efficacement des modèles de transition hautement concurrents et multi-flux sans perdre leur cohérence structurelle.
Divergence de Faisabilité Sémantique : Les LLM excellent dans la progression sémantique mais violent fréquemment les contraintes de faisabilité physique et logique (par exemple, exécuter une transition de paiement avec un panier vide), générant des chemins qui sont logiquement cohérents mais physiquement inexécutables.

La littérature existante manque d'une évaluation de bout en bout pour savoir si la construction automatisée de modèles peut préserver les propriétés structurelles et probabilistes nécessaires aux garanties de détection de fautes du MBST.

2. Méthodologie : Le Cadre NeSy-MBST

Le document introduit le Neuro-Symbolic Model-Based Statistical Testing (NeSy-MBST), un cadre hybride qui découple l'analyse sémantique de la résolution des contraintes mathématiques. L'architecture intègre cinq étapes étroitement couplées :

A. Architecture de Mémoire Duale Progrès-Faisabilité

Le système partitionne la construction du modèle en deux systèmes de mémoire complémentaires :

Mémoire de Progrès Neurale : Un LLM affiné analyse les exigences en langage naturel pour rédiger un graphe de flux sémantique (le « quoi »), capturant les topologies comportementales prévues.
Mémoire de Faisabilité Symbolique : Un moteur à base de règles impose des invariants logiques stricts, des préconditions et des gardes de transition (le « comment »), validant chaque transition candidate avant son admission.

B. Apprentissage d'Automates Actif via $L^*$ avec Oracles LLM

Le cadre emploie une variante spécialisée de l'algorithme d'apprentissage d'automates actif $L^*$ pour découvrir l'espace d'états.

Requêtes d'Appartenance (Membership Queries) : L'algorithme interroge un oracle LLM contraint par la grammaire (restreint aux sorties : Oui, Non, Incertain) pour déterminer si une séquence d'entrée candidate est acceptée.
Requêtes d'Équivalence (Equivalence Queries) : L'automate d'hypothèse actuel est testé contre le Système Sous Test (SUT). Les divergences produisent des contre-exemples utilisés pour affiner l'hypothèse.
Escalade : Si le LLM répond « Incertain », la requête est escaladée vers des experts humains ou l'exécution du SUT en temps réel, garantissant que la boucle d'apprentissage n'incorpore jamais d'informations non vérifiées.

C. Modélisation Hiérarchique Dépendante du Chemin

Pour traiter la dépendance de chemin sans explosion combinatoire, NeSy-MBST utilise une hiérarchie à deux niveaux :

Structure d'Arbre Supérieure : Les séquences fréquentes et dépendantes du chemin sont modélisées comme une chaîne de Markov d'ordre supérieur intégrée dans un arbre.
Modèle de Markov Inférieur : Les parcours infrequents ou d'exception sont modélisés à l'aide de chaînes de Markov de premier ordre standards.

D. Optimisation des Contraintes Mathématiques

Au lieu de demander au LLM de générer directement des probabilités numériques, le cadre délègue cette tâche à un solveur symbolique :

Extraction de Contraintes : Le LLM extrait des relations comparatives (par exemple, $P(\text{paiement}|\text{panier}) > P(\text{navigation}|\text{panier})$ ) à partir des exigences.
Optimisation Convexe : Un moteur de programmation convexe (SLSQP) résout la matrice de probabilité de transition $P$ qui satisfait toutes les contraintes extraites, la stochasticité de ligne et les bornes spécifiques au domaine, tout en maximifiant l'entropie pour éviter tout biais injustifié.

E. Adaptation du Modèle en Boucle Fermée

Le cadre traite le modèle d'usage comme un artefact vivant. La télémétrie d'exécution (journaux d'exécution, métriques de couverture, données de défaillance) est réinjectée dans le moteur de modélisation. Le LLM analyse les divergences entre le comportement prédit et observé, et le solveur symbolique recalibre les probabilités, assurant que le modèle converge vers les schémas d'utilisation réels.

3. Contributions Clés

Cadre NeSy-MBST : Une nouvelle architecture combinant l'apprentissage actif $L^*$ , des oracles LLM contraints par la grammaire, des solveurs symboliques et un feedback en boucle fermée pour automatiser la synthèse de modèles d'usage.
Vérification Formelle de la Sortie LLM : L'introduction d'une boucle de vérification symbolique qui détecte les violations structurelles (états inaccessibles, boucles d'auto-transition manquantes) et déclenche un re-prompt ciblé, transformant un problème de génération limité par le rappel en un problème de complétion guidé par la vérification.
Décomposition Orthogonale des Erreurs : L'article établit que la complétude structurelle (topologie) et le calibrage probabiliste (poids) sont des propriétés orthogonales, traitées séparément par la boucle symbolique et l'optimiseur convexe, respectivement.
Validation Empirique : Une évaluation complète sur un benchmark de systèmes cyber-physiques (CPS) de véhicules autonomes (AV) et deux spécifications d'e-commerce, comparant NeSy-MBST aux bases purement neurales et aux approches manuelles traditionnelles.

4. Résultats Expérimentaux

Évalué sur un benchmark de CPS pour véhicules autonomes (9 états, 13 transitions) et des modèles d'e-commerce (jusqu'à 42 états, 218 transitions), NeSy-MBST a obtenu les résultats suivants :

Précision d'Extraction (RQ1) : A atteint un score F1 systémique de 0,9125, dépassant le seuil de sécurité critique de 0,90. Cela représente une amélioration de 39,1 % par rapport à la meilleure base GPT-4o (SMF hybride) et une améliation de 14,8 % par rapport à la base de modèle unique la plus forte (Claude 3.5 Sonnet).
Couverture de Détection de Fautes (RQ2) : A atteint 85,7 % de couverture de transition, un gain de 35,7 points de pourcentage par rapport à la base purement neurale (50 %). Cela suggère une augmentation significative de la diversité des chemins révélant des fautes.
Calibrage Probabiliste (RQ3) : A atteint une divergence de Jensen–Shannon (JSD) de 0,012 (contre 0,157 pour la base purement neurale), confirmant que l'optimiseur convexe préserve la fidélité de l'allocation de tests opérationnels. La distance de Frobenius normalisée était de 0,0654, indiquant une haute similitude structurelle avec la distribution de référence.
Efficacité : A généré des suites de tests couvrant l'intégralité du modèle en moins de six minutes pour des modèles comprenant jusqu'à 42 états.
Étude d'Ablation (RQ4) :
- La Boucle Symbolique a été identifiée comme le principal moteur de la complétude structurelle (augmentant le F1 de transition de 0,78 à 0,96).
- L'Optimiseur Convexe a montré qu'il régit le calibrage probabiliste sans modifier les métriques structurelles.
- Le Feedback en boucle fermée a fourni des améliorations marginales de la fidélité distributionnelle, principalement utiles pour les campagnes de tests à long terme.

5. Signification et Revendications

L'article affirme que NeSy-MBST élimine le goulot d'étranglement de la modélisation manuelle sans compromettre la rigueur statistique exigée par les systèmes cyber-physiques (CPS) critiques pour la sécurité.

Combler le Fossé : Les résultats démontrent que l'intégration neuro-symbolique peut atteindre la fidélité structurelle (F1 $\ge$ 0,90) et le calibrage probabiliste requis pour le MBST, là où les approches purement neurales échouent à garantir ces propriétés.
Proxy de Détection de Défauts : Bien que l'étude n'ait pas mesuré directement les taux de détection de défauts par rapport à un corpus de fautes injectées, l'article soutient que l'augmentation de 35,7 % de la couverture de transition observée est un proxy robuste pour la détection de fautes, cohérent avec les améliorations de 25 à 40 % rapportées dans la littérature de déploiement industriel du MBT.
Standard d'Ingénierie : Les auteurs proposent que l'augmentation des LLM pour la génération de modèles de tests formels passe d'une curiosité de recherche à une pratique d'ingénierie standard, à condition que deux conditions soient remplies : (1) les LLM opèrent sous des contraintes structurelles (sortie contrainte par la grammaire, vérification symbolique) pour prévenir les hallucinations, et (2) les paramètres numériques sont assignés par des solveurs certifiés, et non par le LLM directement.

L'article conclut que cette approche rend les tests statistiques rigoureux accessibles à des pratiques de développement de logiciels plus larges, les déplaçant au-delà des équipes spécialisées en sécurité, tout en reconnaissant que des travaux futurs sont nécessaires pour valider ces conclusions sur des systèmes industriels de plus grande échelle et avec des styles d'exigences diversifiés.