💻 computer science

Complexity Theory of Randomised Testing

Cet article établit les premiers fondements de la théorie de la complexité pour les tests randomisés en modélisant les générateurs comme des transducteurs de Turing afin de caractériser les limites de la génération d'entrées efficace et à espace borné, révélant des distinctions fondamentales entre la complexité de génération et de décision tout en prouvant que la génération efficace nécessite des schémas de certificats spécifiques et ne peut être dérivée compositionnellement de prédicats logiques généraux.

Auteurs originaux : Pingshi Yu, Chengsong Tan, Nicolas Wu, Alastair Donaldson

Publié 2026-07-14

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Pingshi Yu, Chengsong Tan, Nicolas Wu, Alastair Donaldson

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

Imaginez que vous êtes un développateur de jeux vidéo essayant de tester un nouveau monde massif. Vous voulez vous assurer que votre jeu ne plante pas, vous avez donc besoin d'un robot capable de recracher des millions de niveaux, personnages et objets aléatoires pour voir si quelque chose casse. Ce robot est appelé un générateur. Pendant des années, les développeurs ont construit ces robots à la main, en les ajustant jusqu'à ce qu'ils fonctionnent suffisamment bien. Mais personne ne connaissait réellement les limites théoriques de ce que ces robots pouvaient réellement faire. Pouvaient-ils générer n'importe quel niveau possible ? Pouvaient-ils le faire assez vite pour être utiles ?

Une équipe de chercheurs de l'Imperial College London et de Kaihong a décidé de passer ces robots au microscope en utilisant la Théorie de la Complexité — les mathématiques qui étudient la difficulté des problèmes à résoudre. Ils n'ont pas seulement regardé le code ; ils ont modélisé les robots comme des « machines de Turing » (les ordinateurs théoriques ultimes) qui « mangent » des bits de données aléatoires et recrachent des niveaux de jeu. Voici ce qu'ils ont découvert.

La liste de « Ce qui peut être fabriqué »

D'abord, ils ont demandé : Quelle est la limite absolue de ce qu'un générateur peut produire ?

Ils ont découvert que si vous donnez à un générateur un temps et une mémoire illimités, il peut produire exactement le même ensemble de choses qu'un ordinateur standard peut reconnaître. Dans le monde des mathématiques, cela s'appelle les langages récursivement énumérables (RE).

La bonne nouvelle : Si un ensemble d'entrées (comme « tous les programmes C valides ») peut être reconnu par un ordinateur, un générateur peut théoriquement les produire.
La mauvaise nouvelle : Si un ensemble d'entrées est trop bizarre pour être reconnu par un ordinateur (comme « tous les programmes qui ne s'arrêteront jamais de s'exécuter »), aucun générateur ne pourra jamais les produire. Ce n'est pas un bug dans votre code ; c'est une loi fondamentale de l'univers. Vous ne pouvez pas construire un robot qui recrache toutes les boucles infinies possibles, car les mathématiques disent qu'il est impossible de toutes les lister.

Le problème du « Dos d'âne »

Ensuite, ils ont demandé : Et si nous avons besoin que le générateur soit rapide ? Dans le monde réel, on ne peut pas attendre un million d'années pour un cas de test. Il faut des résultats en quelques secondes.

Les chercheurs ont découvert un rebondissement surprenant : Être capable de vérifier si quelque chose est valide n'est pas la même chose que d'être capable de fabriquer quelque chose de valide.

L'exemple du solveur SAT : Imaginez un puzzle où vous devez trouver une combinaison spécifique d'interrupteurs pour allumer une lumière. Vérifier si une combinaison fonctionne est difficile (c'est « NP-complet »). Mais les chercheurs ont montré que vous pouvez construire un robot rapide qui génère ces combinaisons fonctionnelles. Cela fonctionne en « plantant un témoin » : le robot choisit secrètement d'abord une combinaison gagnante, puis construit le puzzle autour de celle-ci.
Le piège de la collision de hachage : Cependant, ils ont également prouvé que pour certains problèmes, même si vérifier la réponse est facile, fabriquer la réponse peut être impossible à faire rapidement. Ils ont examiné les « collisions de hachage » (trouver deux entrées différentes qui produisent la même empreinte numérique). Vérifier si deux empreintes correspondent est extrêmement rapide. Mais trouver une paire qui correspond ? Si vous pouviez construire un robot rapide pour faire cela, vous briseriez la sécurité de presque tous les cryptages modernes.
- Le verdict : À moins que le monde de la cryptographie ne soit brisé, il existe des problèmes où la vérification est facile, mais la génération est difficile. Vous ne pouvez pas simplement souhaiter un générateur rapide ; parfois, les mathématiques ne le permettent tout simplement pas.

La contrainte de la « Mémoire » (Fuzzing et Feedback)

De nombreux outils de test modernes, comme les « fuzzers », ne se contentent pas de recracher des données aléatoires ; ils se souviennent de ce qu'ils ont essayé auparavant. Si un test fait planter le programme, le fuzzer s'en souvient et essaie de modifier l'entrée pour le faire planter à nouveau. C'est comme un détective qui apprend de chaque indice.

Les chercheurs ont modélisé cela comme un générateur avec une quantité limitée de mémoire (espace). Ils ont découvert que même avec ce « feedback » et cette boucle de rétroaction, le générateur reste limité.

La limite : Si le générateur possède une quantité polynomiale de mémoire (ce qui couvre presque tous les outils pratiques), il ne peut générer que des choses qui appartiennent à une classe appelée PSPACE.
Le rappel à la réalité : Cela signifie que même les outils de fuzzing les plus intelligents et les plus gourmands en mémoire ne peuvent pas générer des entrées pour des problèmes qui sont « EXPTIME-complets » (problèmes qui prennent un temps exponentiel à résoudre). Si un problème est trop complexe pour être résolu par une machine PSPACE, aucun amount de feedback ou de mémoire n'aidera un générateur à créer des cas de test pour lui.

Le mythe de la « Composabilité »

Enfin, ils se sont attaqués à un rêve des ingénieurs logiciels : Pouvons-nous construire un « kit Lego » de générateurs ?
Imaginez avoir un outil où vous dites : « Je veux un générateur pour A ET B », ou « Je veux un générateur pour NON A », et l'outil combine automatiquement ces éléments en un nouveau générateur rapide.

L'article délivre un NON catégorique à ce rêve, selon les hypothèses standards.

La règle : Vous ne pouvez pas combiner automatiquement des générateurs en utilisant « ET » (conjonction) ou « NON » (négation) et garantir qu'ils seront toujours rapides.
Pourquoi ? Si vous pouviez faire cela, vous pourriez résoudre des problèmes qui sont actuellement considérés comme impossibles à résoudre rapidement.
L'exception : Vous pouvez le faire pour des types de logique très simples et restreints (comme le « Datalog linéaire » ou les problèmes « NL »), mais dès que vous ajoutez des « ET » ou des « NON » complexes, la magie s'arrête. Si vous voulez combiner des règles complexes, vous devez renoncer aux garanties de vitesse ou accepter que votre générateur puisse simplement « essayer et échouer » (échantillonnage de rejet) jusqu'à ce qu'il ait de la chance.

La vue d'ensemble

L'article conclut que générer des données est un défi distinct, et souvent plus difficile, que de décider si des données sont valides.

Ce qui est prouvé : Ils ont prouvé que l'ensemble de toutes les choses générables est exactement l'ensemble des choses récursivement énumérables. Ils ont prouvé que des générateurs rapides pour certains problèmes difficiles existent (comme SAT) mais pas pour d'autres (comme les collisions de hachage, en supposant que la crypto est sûre). Ils ont prouvé que les outils pilotés par le feedback sont limités par PSPACE.
Ce qui est écarté : Ils ont écarté la possibilité d'une bibliothèque universelle, rapide et compositionnelle capable de gérer n'importe quelle combinaison de règles logiques. Ils ont écarté l'idée que « facile à vérifier » signifie toujours « facile à générer ».

En bref, si vous construisez un robot de test, vous ne pouvez pas simplement souhaiter qu'il soit rapide et intelligent. Les mathématiques ont tracé une ligne dans le sable : certaines choses sont impossibles à générer, certaines sont impossibles à générer rapidement, et certaines choses ne peuvent pas être mélangées sans briser la vitesse. Mais maintenant, nous savons enfin exactement où se trouvent ces lignes.

Résumé Technique : Théorie de la Complexité des Tests Randomisés

Énoncé du Problème

Les tests randomisés, particulièrement le Test Basé sur les Propriétés (Property-Based Testing - PBT), reposent largement sur des générateurs pour produire des entrées destinées à un Système Sous Test (SUT). Malgré un développement pratique intensif, les fondements théoriques de ces générateurs restent sous-explorés. Plus précisément, la question fondamentale de savoir ce que signifie être « générable » (tant en termes d'existence que d'efficacité) n'a pas encore été rigoureusement résolue. Les praticiens sont souvent confrontés à l'incertitude concernant les limites de l'expressivité des générateurs : quels langages peuvent être générés du tout, et lesquels peuvent être générés efficacement ? De plus, il existe un manque de compréhension formelle concernant la relation entre la complexité de décision d'un langage (complexité de décision) et la complexité de génération d'instances de ce langage (complexité de génération).

Méthodologie

Les auteurs établissent un cadre de complexité théorique en modélisant les générateurs randomisés comme des transducteurs de machines de Turing.

Modèle Formel : Un générateur est défini comme une machine de Turing déterministe possédant trois rubans : un ruban d'entrée à lecture unique (consommant des bits aléatoires), un ruban de travail, et un ruban de sortie à écriture unique.
Aléatoire : Le caractère aléatoire est modélisé comme une chaîne de bits d'entrée explicite (un flux infini de lancers de pièces équitables). Un générateur est considéré comme « éventuellement productif » s'il produit une sortie pour presque tous les flux de bits infinis (probabilité 1).
Contraintes de Ressources : Les auteurs introduisent des familles de générateurs indexées par la taille de la sortie (par exemple, la longueur de la chaîne $n$ $n$ ). Ils définissent des classes de complexité basées sur des bornes de temps et d'espace relatives à cette taille de sortie :
- GEN : Tous les langages générables (sans contrainte).
- PG : Langages générables en temps polynomial.
- EPG : Langages générables en temps polynomial attendu.
- LG : Langages générables en espace logarithmique.
- PSPACEG : Langages générables en espace polynomial.
Génération Corrélée : Pour modéliser les techniques pilotées par le feedback, telles que le fuzzing guidé par la couverture ou l'exécution concolique, les auteurs étendent le modèle pour inclure un accès oracle au SUT, analysant la génération à espace borné où les sorties précédentes influencent les futures.

Contributions Clés et Résultats

1. Limites d'Expressivité (Génération sans Contrainte)

L'article établit que l'ensemble des langages générables coïncide exactement avec les langages Récursivement Énumérables (RE).

Théorème 3.1 : $GEN = RE$.
Implication : Un langage est générable si et seulement s'il est RE. Par conséquent, les langages hors de RE (tels que l'ensemble des programmes non terminants, par le théorème de Rice) ne peuvent pas être générés par aucun algorithme. Cela implique que les propriétés avec des préconditions non-RE (par exemple, tester un compilateur sur tous les programmes non terminants) ne peuvent pas être pleinement testées via des tests randomisés ; tout générateur devra nécessairement échantillonner un sous-ensemble strict, testant ainsi une propriété plus faible.

2. Génération Efficace (Temps Polynomial)

Les auteurs étudient la classe PG (langages générables en temps polynomial) et sa relation avec les classes de complexité classiques.

Inclusion dans NP : $PG \subseteq NP$ . Une génération efficace nécessite que la précondition soit dans NP ; si une précondition est PSPACE-difficile ou coNP-difficile (par exemple, des formules booléennes quantifiées ou des formules insatisfaisables), aucun générateur polynomial complet n'existe.
Séparation Stricte de P : Sous les hypothèses cryptographiques standards (spécifiquement l'existence de fonctions de hachage résistantes aux collisions), il existe des langages dans P qui ne sont pas dans PG.
- Théorème 5.1 : Si des fonctions de hachage résistantes aux collisions existent, alors $P \not\subseteq PG$ .
- Implication : Une faible complexité de décision n'est ni nécessaire ni suffisante pour une génération efficace. On peut décider efficacement si une collision de hachage existe (en P), mais on ne peut pas générer efficacement une telle collision (à moins que les fonctions de hachage ne soient cassées).
NP-Complétude : Malgré la séparation de P, PG contient des problèmes NP-complets. Par exemple, les auteurs montrent que CNF-SAT appartient à PG en construisant un générateur qui échantillonne une affectation aléatoire et construit une formule satisfaite par cette affectation (plantation de témoin/witness planting).

3. Caractérisation de la Générabilité Efficace

L'article fournit une caractérisation structurelle des langages PG.

Théorème 7.1 : Un langage $L$ $L$ appartient à PG si et seulement s'il admet un schéma de certificat. Cela signifie qu'il existe un vérificateur en temps polynomial $V$ $V$ tel qu'il est possible de :
1. Échantillonner un certificat aléatoire $c$ .
2. Reconstruire efficacement une instance aléatoire $w$ à partir de $c$ telle que $V(w, c)$ accepte.
Signification : Cela formalise la « plantation de témoin » (générer une instance autour d'une solution connue) comme le mécanisme fondamental de tous les générateurs efficaces. Cela implique que tout générateur efficace pour un langage NP opère essentiellement en échantillonnant un témoin et en reconstruisant l'instance du problème.

4. Génération à Espace Borné et Feedback

Les auteurs analysent des générateurs produisant des échantillons corrélés, modélisant des techniques comme l'exécution concolique et le fuzzing guidé par la couverture.

Théorème 6.1 : $PSPACEG = PSPACE$.
Implication : Les techniques de génération pilotées par le feedback, même avec un accès oracle au SUT, sont limitées par PSPACE. Si le SUT lui-même ne résout pas de problèmes PSPACE-complets, alors les techniques pilotées par le feedback ne peuvent pas générer des entrées pour des ensembles EXPTIME-complets. Cela limite la puissance théorique du fuzzing guidé par la couverture pour certains problèmes de haute complexité.

5. Limitations des Bibliothèques Compositionnelles

L'article aborde la conception de bibliothèques de PBT visant à composer des générateurs à partir de prédicats logiques.

Théorème 7.2 : Sous les hypothèses standards ( $NP \neq coNP$ et existence de fonctions de hachage résistantes aux collisions), la classe PG n'est pas fermée par complémentation ou intersection.
Implication : Aucune bibliothèque ne peut composer de manière structurelle des prédicats logiques impliquant la négation ( $\neg$ ) ou la conjonction ( $\land$ ) tout en préservant les garanties d'efficacité. Les concepteurs doivent soit restreindre le langage des prédicats (par exemple, vers NL ou le Datalog linéaire, qui sont fermés sous ces opérations), soit recourir à l'échantillonnage par rejet, ce qui peut être inefficace.

Signification

L'article affirme fournir les premières fondations de complexité théorique pour les générateurs de tests randomisés. Sa signification réside dans :

Clarification des Limites : Il définit rigoureusement ce qui peut et ne peut pas être généré, en distinguant la complexité de décision de la complexité de génération.
Validation et Réfutation des Intuitions : Il confirme que la « plantation de témoin » est la structure nécessaire pour une génération efficace et prouve que des propriétés faciles à décider (comme les collisions de hachage) peuvent être difficiles à générer.
Orientation de la Conception d'Outils : Il offre des résultats négatifs pour la conception de bibliothèques de test compositionnelles, montrant qu'une compositionnalité générale avec des garanties d'efficacité est impossible pour les opérateurs logiques standards.
Large Applicabilité : Bien que motivé par le test de logiciels, le cadre s'applique à tout domaine nécessitant la génération aléatoire à partir d'ensembles contraints, comme les méthodes de Monte Carlo par chaînes de Markov (MCMC) et la génération d'espaces chimiques.

Les auteurs concluent que leur cadre permet une analyse rigoureuse des campagnes de test, passant des heuristiques empiriques à des garanties formelles concernant la faisabilité et l'efficacité de la génération d'entrées.