Je dois admettre: je lis
ACM Magazine . Cela fait de moi un «nerd», même selon les normes des programmeurs. Entre autres choses, j'ai appris de ce magazine sur les «tests métamorphiques». Je n'avais jamais entendu parler de lui auparavant, comme toutes les personnes à qui j'ai demandé. Mais la littérature scientifique sur ce sujet est étonnamment volumineuse: il existe de nombreux exemples incroyablement réussis de son application dans des domaines de recherche complètement différents. Alors, pourquoi n'avons-nous pas entendu parler de lui avant? Il n'y a qu'un
seul article pour les personnes extérieures à la communauté scientifique. Maintenant, qu'il y en ait deux.
Bref historique
La plupart des tests écrits utilisent des
oracles . Autrement dit, vous connaissez la réponse et vérifiez explicitement si les calculs donnent la bonne réponse.
def test_dist(): p1 = (0, 3) p2 = (4, 0) assert dist(p1, p2) == 5
En plus des tests Oracle, il existe également des tests manuels. Le testeur s'assoit devant l'ordinateur et compare les données d'entrée avec les résultats. À mesure que les systèmes deviennent plus complexes, les tests manuels deviennent de moins en moins utiles. Chacun d'eux ne vérifie qu'un seul point dans un espace d'état beaucoup plus grand, et nous avons besoin de quelque chose qui explore tout l'espace d'état.
Cela nous amène à
des tests génératifs : écrire des tests couvrant un ensemble aléatoire dans un espace d'états. Le style de test génératif le plus populaire est le
test basé sur les propriétés , ou PBT. Nous trouvons la «propriété» de la fonction, puis générons les valeurs d'entrée et vérifions si les valeurs de sortie correspondent à cette propriété.
def test_dist(): p1 = random_point() p2 = random_point() assert dist(p1, p2) >= 0
L'avantage du PBT est qu'il couvre plus d'espace. Son inconvénient est la perte de spécificité. Ce n'est
plus un test Oracle! Nous ne savons pas quelle devrait être la réponse, et la fonction peut être erronée, mais d'une manière qui a la même propriété. Ici, nous nous appuyons sur l'heuristique.
Un problème sérieux avec PBT est de trouver de bonnes propriétés. La plupart des fonctions ont des propriétés générales simples et des propriétés spécifiques complexes.
Les propriétés générales peuvent être appliquées à un grand nombre de fonctions, mais elles ne nous donnent pas beaucoup d'informations. Des propriétés plus spécifiques donnent plus d'informations, mais elles sont plus difficiles à trouver et ne sont applicables que dans des zones de tâches limitées. Si vous avez une fonction qui détermine si un graphe est acyclique, alors quels tests de propriétés écrirez-vous? Vont-ils vous donner l'assurance que la fonction est correcte?
La motivation
Considérons maintenant une tâche plus complexe. Imaginez que vous vouliez écrire un convertisseur parole-texte (STT) pour l'anglais. Il reçoit un fichier son et affiche le texte. Comment le testeriez-vous?
La façon la plus simple d'utiliser un oracle à main. Dictez la phrase et vérifiez si le texte de sortie correspond. Mais ce n'est même pas assez proche! La gamme de la parole humaine
est immense . Il serait préférable de tester 1 000 voire 10 000 fichiers audio différents. Les oracles portables avec transcription seraient trop coûteux. Cela signifie que nous devons utiliser à la place des tests basés sur les propriétés.
Mais comment générer des entrées? Par exemple, nous pouvons créer des lignes aléatoires, les passer à travers un convertisseur texte-parole (text-to-speech, TTS), puis nous assurer que notre STT produit le même texte. Mais cela nous donne encore une fois une gamme très limitée de voix humaine. Le TTS peut-il créer des changements d'intonation, «avaler» des mots, imiter un fort accent? Si nous ne pouvons pas les traiter, le STT sera-t-il particulièrement utile? Il est préférable d'utiliser des textes arbitraires, par exemple, des enregistrements de la radio, des podcasts et des vidéos en ligne.
Maintenant, un nouveau problème se pose. Lors de l'utilisation de TTS, nous avons commencé avec du texte écrit. Dans le cas de fichiers sonores arbitraires, nous ne les avons pas, et en même temps, nous ne voulons pas transcrire manuellement. Au lieu de cela, nous sommes limités à utiliser des propriétés. Quelles propriétés devons-nous tester? Exemples des propriétés les plus simples: «le programme ne plante pas avec les données entrantes» (une bonne propriété) ou «il ne convertit pas la musique acoustique en mots» (peut-être?). Ces propriétés ne couvrent pas très bien la vérification de la tâche principale du programme et augmentent légèrement la confiance dans sa qualité.
Nous avons donc deux tâches. Premièrement, nous avons besoin d'une grande quantité de données sous forme de discours. Deuxièmement, nous devons comprendre comment les convertir en tests utiles sans passer de longues heures à transcrire manuellement des voix en oracles.
Test métamorphique
Pour tout cela, la sortie est considérée séparément. Et si nous les intégrions dans un contexte plus large? Par exemple, si un clip audio est transcrit dans la sortie de sortie, alors nous devons
toujours out avec:
- Double volume
- Fréquence croissante
- Accélérez
- Ajout de bruit de fond
- Ajout de bruit de véhicule
- Toute combinaison de ce qui précède.
Ce sont toutes des transformations «simples» que nous pouvons facilement tester. Par exemple, pour un test avec «bruit de véhicule», nous pouvons prélever 10 échantillons de bruit de voiture, les mettre sur un clip audio et vérifier si les résultats de reconnaissance des 11 versions correspondent. Nous pouvons doubler ou augmenter le volume, transformant 11 versions en 33 versions, puis doubler le rythme pour obtenir 66 versions. Ce principe peut être appliqué à chaque clip audio de notre base de données, augmentant considérablement l'espace des données entrantes.
La présence de 66 versions pour comparaison est assez pratique. Mais ce n'est pas tout: nous n'avons toujours pas besoin de savoir quelle devrait être la sortie. Si les 66 conversions reviennent, le test a réussi, si au moins une renvoie autre chose, le test a échoué. À aucun moment, nous n'avons besoin de vérifier ce qui est contenu dans
out . C'est extrêmement important. Nous augmentons donc considérablement l'espace de test avec très peu d'implication humaine. Par exemple, nous pouvons télécharger un épisode de la série, effectuer des conversions et vérifier si tous les résultats de leur conversion en texte
1 correspondent. Nous avons obtenu des tests utiles
sans écouter le clip vocal . Maintenant, nous pouvons générer des tests complexes et profonds sans utiliser d'oracle!
Deux ensembles de données d'entrée, ainsi que leurs données de sortie, sont connectés l'un à l'autre. Une telle propriété liée à l'ensemble des données entrantes / sortantes est appelée
lien métamorphique 2 . Les tests qui appliquent cette propriété sont appelés
tests métamorphiques . Dans les systèmes complexes, les relations métamorphiques intéressantes peuvent être trouvées plus facilement que les propriétés intéressantes des données entrantes / sortantes individuelles.
Disons-le un peu plus formellement: si nous avons
x et
f(x) , alors nous pouvons effectuer quelques transformations de
x pour obtenir
x2 et
f(x2) . Dans le cas de STT, nous vérifions simplement
f(x) = f(x2) , mais nous pouvons utiliser toutes les relations entre les deux ensembles de données. Il peut y avoir des relations métamorphiques comme
f(x2) > f(x) ou "est
f(x2)/f(x) une valeur entière." De manière similaire, ce principe peut être étendu à plusieurs ensembles de données d'entrée à l'aide de
f(x) et
f(x3) . Un exemple de ceci est la comparaison des résultats d'un moteur de recherche sans filtres avec les résultats d'un moteur avec un ou deux filtres. Dans la majorité des descriptions des cas d'utilisation que j'ai lus, seuls deux ensembles de données d'entrée sont utilisés, car même ils sont suffisants pour trouver des bugs fous.
Exemples d'utilisation
En parlant de cas d'utilisation: quelle est l'efficacité des tests métamorphiques dans la pratique? C'est une chose de parler d'une technique de façon abstraite ou de donner des exemples artificiels. Les études de cas sont utiles pour trois raisons. Premièrement, il montre si la méthode fonctionne réellement. Deuxièmement, vous pouvez en apprendre davantage sur les difficultés potentielles lors de l'utilisation de MT. Troisièmement, les exemples nous montrent
comment utiliser la technique. Toute connexion métamorphique utilisée dans l'exemple d'utilisation peut être essayée pour s'adapter à la solution de nos problèmes.
Tests métamorphiques: un examen des défis et des opportunités fournit une liste de nombreuses études, mais ce sont tous des articles scientifiques. Voici les plus intéressants. Les articles marqués d'un
(pdf) sont présentés, comme vous pouvez le deviner, au format PDF.
Le problème
Oh, donc
toutes ces sources sont en PDF.
Il a fallu plusieurs heures pour trouver tous ces articles. Et ce problème est associé au plus grand obstacle au développement de la MT: tous les liens ci-dessus sont des
prépublications ou des premières ébauches d'articles scientifiques futurs. Quand je commence à comprendre des techniques peu connues, je me pose d'abord la question: "pourquoi sont-elles peu connues?" Parfois, la raison est évidente, parfois c'est un ensemble complexe de petites raisons, parfois le problème est simplement que la méthodologie est «malheureuse».
Dans le cas de MT, le problème est évident.
Presque toutes les informations sont cachées derrière un paywall scientifique. Si vous voulez étudier la MT, vous devez soit avoir accès au journal, soit passer plusieurs heures à chercher des prépublications
3 .
Etude complémentaire
L'inventeur de MT est
Ty Chen . Il est devenu le moteur de nombreuses études. D'autres chercheurs dans ce domaine sont
Zhi Quan Zhou et
Sergio Segura ; tous deux ont publié toutes leurs prépublications sur Internet. La plupart des travaux de recherche sont effectués par l'une de ces personnes.
Le meilleur endroit pour commencer est probablement le
test métamorphique: un examen des défis et des opportunités et
une enquête sur le test métamorphique . Bien que cet article soit écrit sur les
tests métamorphiques, les chercheurs ont également appliqué les relations métamorphiques en général à une grande variété d'autres disciplines, par exemple, la vérification de code formelle et le débogage. Je n'ai pas encore étudié ces domaines d'application de la technique en détail, mais cela vaut probablement la peine de les examiner également.
Du point de vue de l'applicabilité, il peut théoriquement être possible d'adapter la plupart des bibliothèques PBT pour vérifier les propriétés métamorphiques. En fait, le premier exemple de
Quickcheck teste la SEP, et dans
cet essai sur PBT, la SEP est indirectement appliquée.
En général, il me semble que la plupart des recherches PBT se concentrent sur la génération et le découpage efficaces des données entrantes, et la recherche MT se concentre principalement sur la détermination de ce que nous devons vraiment tester. Par conséquent, ces techniques sont susceptibles de se compléter.
Merci à Brian Ng pour son aide à la recherche.Post-scriptum: demande
En fait, il n'est pas surprenant que je n'avais jamais entendu parler de cette technique auparavant. Il existe de nombreuses techniques vraiment intéressantes et utiles qui n'ont pas pu laisser leur minuscule bulle. J'ai découvert les MT par hasard plutôt que par des recherches actives.
Si vous savez quelque chose qui mérite d'être largement utilisé,
écrivez-moi .
- Eh bien, il peut y avoir des problèmes évidents: il peut y avoir de la musique dans le podcast, des fragments de discours dans d'autres langues, etc. Mais la théorie est fiable: si nous pouvons obtenir des échantillons de parole, nous pouvons les utiliser dans le cadre des tests sans transcription / balisage manuel préalable.
- Dans les spécifications, l'idée correspondante est les hyperpropriétés - les propriétés des ensembles de comportements, plutôt que les comportements individuels. La plupart des études hyperspécifiques sont liées à la sécurité du HS. Si je comprends bien, ses HS sont un surensemble de MS.
- J'avais une deuxième hypothèse, aujourd'hui réfutée: puisque la plupart des principaux chercheurs de Chine et de Hong Kong, cette technique est peut-être mieux connue dans les communautés de programmeurs qui communiquent en mandarin plutôt qu'en anglais. Brian Eun a testé cette hypothèse pour moi, mais n'a trouvé aucun signe significatif de l'utilisation de la technique par les Chinois.