La couverture de chemin garantit-elle la recherche de tous les bogues?

64

Si chaque chemin dans un programme est testé, est-ce que cela garantit de trouver tous les bogues?

Si non pourquoi pas Comment pouvez-vous passer en revue toutes les combinaisons possibles de flux de programmes sans trouver le problème s'il en existe un?

J'hésite à suggérer que "tous les bugs" peuvent être trouvés, mais c'est peut-être parce que la couverture de chemin n'est pas pratique (car elle est combinatoire) et qu'elle n'est donc jamais expérimentée?

Remarque: cet article fournit un résumé rapide des types de couverture auxquels je pense.


la source
33
Ceci est équivalent au problème d’arrêt .
31
Et si le code qui aurait dû être là, n'est-ce pas?
RemcoGerlich
6
@ Snowman: Non, ce n'est pas. Il n’est pas possible de résoudre le problème d’arrêt pour tous les programmes, mais il est possible de le résoudre pour de nombreux programmes spécifiques. Pour ces programmes, tous les chemins de code peuvent être énumérés dans un laps de temps fini (bien que éventuellement long).
Jørgen Fogh
3
@ JørgenFogh Mais lorsque vous essayez de trouver des bogues dans un programme, ne savez -vous pas a priori si le programme s'arrête ou non? Cette question ne concerne-t-elle pas la méthode générale consistant à "rechercher tous les bogues dans un programme via la couverture de chemin"? Dans quel cas, cela ne ressemble-t-il pas à "déterminer si un programme est arrêté"?
Andres F.
1
@AndresF. on ne sait que si le programme s'arrête si le sous - ensemble de la langue dans laquelle il est écrit est capable d'exprimer un programme qui ne s'arrête pas. Si votre programme est écrit en C sans utiliser de boucles / récursions / setjmp, etc. non liées, ou en Coq, ou en ESSL, il doit être arrêté et tous les chemins peuvent être suivis. (La complétude de Turing est sérieusement surévaluée)
Leushenko

Réponses:

128

Si chaque chemin dans un programme est testé, est-ce que cela garantit de trouver tous les bogues?

Non

Si non pourquoi pas Comment pouvez-vous passer en revue toutes les combinaisons possibles de flux de programmes sans trouver le problème s'il en existe un?

Car même si vous testez tous les chemins possibles , vous ne les avez toujours pas testés avec toutes les valeurs possibles ou toutes les combinaisons de valeurs possibles . Par exemple (pseudocode):

def Add(x as Int32, y as Int32) as Int32:
   return x + y

Test.Assert(Add(2, 2) == 4) //100% test coverage
Add(MAXINT, 5) //Throws an exception, despite 100% test coverage

Cela fait maintenant deux décennies qu'il a été souligné que les tests de programme peuvent démontrer de manière convaincante la présence de bugs, mais ne peuvent jamais démontrer leur absence. Après avoir cité avec dévotion cette remarque très médiatisée, l’ingénieur logiciel revient à l’ordre du jour et continue d’affiner ses stratégies de test, à l’instar de l’alchimiste d’aujourd’hui, qui a continué d’affiner ses purifications chrysocosmiques.

- EW Dijkstra (non souligné dans le texte original). Rédigé en 1988. Cela fait considérablement plus de deux décennies maintenant.)

Maçon Wheeler
la source
7
@ digitgopher: Je suppose, mais si un programme n'a pas d'entrée, quelle fonction utile fait-il?
Mason Wheeler
34
Il existe également la possibilité de manquer des tests d'intégration, des bogues dans les tests, des bogues dans les dépendances, des bogues dans le système de génération / déploiement ou des bogues dans la spécification / les exigences d'origine. Vous ne pouvez jamais garantir la recherche de tous les bugs.
Ixrec
11
@Ixrec: SQLite fait un effort assez vaillant, cependant! Mais regardez quel effort énorme c'est! Cela ne serait pas bien adapté aux grandes bases de code.
Mason Wheeler
13
Non seulement vous n’avez pas testé toutes les valeurs possibles ni leurs combinaisons, vous n’avez pas testé tous les chronomètres relatifs, dont certains pourraient exposer des conditions de concurrence fulgurantes ou même forcer votre test à entrer dans une impasse, ce qui l’empêcherait de signaler quoi que ce soit . Ce ne serait même pas un échec!
Iwillnotexist Idonotexist
14
Mon souvenir (étayé par de tels écrits ) est que Dijkstra croyait que dans les bonnes pratiques de programmation, la preuve qu'un programme est correct (dans toutes les conditions) devrait faire partie intégrante de son développement. Vu de ce point de vue, le test est comme une alchimie. Plutôt que l'hyperbole, je pense que c'était une opinion très forte exprimée dans un langage très fort.
David K
71

En plus de la réponse de Mason , il y a aussi un autre problème: la couverture ne pas vous dire quel code a été testé, il vous indique quel code a été exécuté .

Imaginez que vous ayez une suite de tests avec une couverture de chemin à 100%. Supprimez maintenant toutes les assertions et exécutez à nouveau la suite de tests. Voilà, la suite de tests a toujours une couverture de chemin de 100%, mais elle ne teste absolument rien.

Jörg W Mittag
la source
2
Cela permet de s'assurer qu'il n'y a pas d'exception lors de l'appel du code testé (avec les paramètres du test). C'est un peu plus que rien.
Paŭlo Ebermann
7
@ PaŭloEbermann D'accord, un peu plus que rien. Cependant, c'est beaucoup moins que "trouver tous les bugs";)
Andres F.
1
@ PaŭloEbermann: Les exceptions sont un chemin de code. Si le code peut être lancé mais que certaines données de test ne le sont pas, le test n'atteint pas une couverture de chemin de 100%. Cela n'est pas spécifique aux exceptions en tant que mécanisme de gestion des erreurs. De Visual Basic ON ERROR GOTOest aussi un chemin, comme C de if(errno).
MSalters
1
@MSalters Je parle de code qui (par spécification) ne devrait renvoyer aucune exception, quelle que soit l'entrée. S'il en jette un, ce serait un bug. Bien sûr, si vous avez un code qui spécifie une exception, cela devrait être testé. (Et bien sûr, comme Jörg l’a dit, vérifier que le code ne lève pas une exception n’est généralement pas suffisant pour s’assurer que c’est la bonne chose à faire, même pour du code non jeté.) Et certaines exceptions peuvent être lancées par un non Chemin de code invisible, comme pour la déréférence ou la division par zéro du pointeur null. Est-ce que votre outil de couverture de chemin attrape ceux-ci?
Paŭlo Ebermann
2
Cette réponse le cloue. J'irais même plus loin en affirmant que, pour cette raison, la couverture de chemin ne garantit jamais la découverte d'un seul bogue. Il existe des métriques qui peuvent au moins garantir que les modifications seront détectées. Cependant, les tests de mutation peuvent en réalité garantir que (certaines) modifications du code seront détectées.
eis
34

Voici un exemple plus simple pour arrondir les choses. Considérez l'algorithme de tri suivant (en Java):

int[] sort(int[] x) { return new int[] { x[0] }; }

Maintenant, testons:

sort(new int[] { 0xCAFEBABE });

Maintenant, considérons que (A) cet appel particulier sortrenvoyant le résultat correct, (B) tous les chemins de code ont été couverts par ce test.

Mais, évidemment, le programme ne trie pas réellement.

Il s'ensuit que la couverture de tous les chemins de code n'est pas suffisante pour garantir que le programme ne comporte aucun bogue.

Atsby
la source
12

Considérons la absfonction, qui renvoie la valeur absolue d'un nombre. Voici un test (Python, imaginez un framework de test):

def test_abs_of_neg_number_returns_positive():
    assert abs(-3) == 3

Cette implémentation est correcte, mais elle n'obtient qu'une couverture de code de 60%:

def abs(x):
    if x < 0:
        return -x
    else:
        return x

Cette implémentation est fausse, mais elle obtient une couverture de code à 100%:

def abs(x):
    return -x
RemcoGerlich
la source
2
Voici une autre implémentation qui réussit le test (veuillez excuser le Python non tronqué): def abs(x): if x == -3: return 3 else: return 0Vous pouvez éventuellement élider la else: return 0pièce et obtenir une couverture à 100%, mais la fonction serait essentiellement inutile même si elle réussit le test unitaire.
un CVn
7

Autre ajout à la réponse de Mason , le comportement d'un programme peut dépendre de l'environnement d'exécution.

Le code suivant contient un Use-After-Free:

int main(void)
{
    int* a = malloc(sizeof(a));
    int* b = a;
    *a = 0;
    free(a);
    *b = 12; /* UAF */
    return 0;
}

Ce code est un comportement non défini. En fonction de la configuration (version | débogage), du système d'exploitation et du compilateur, il génère différents comportements. Non seulement la couverture de chemin ne garantit pas que vous trouverez le fichier UAF, mais votre suite de tests ne couvre généralement pas les divers comportements possibles du fichier UAF qui dépendent de la configuration.

Sur une autre note, même si la couverture de chemin devait garantir la recherche de tous les bogues, il est peu probable que cela puisse être réalisé dans la pratique quel que soit le programme. Considérez le suivant:

int main(int a, int b)
{
    if (a != b) {
        if (cryptohash(a) == cryptohash(b)) {
            return ERROR;
        }
    }
    return 0;
} 

Si votre suite de tests peut générer tous les chemins pour cela, alors félicitations, vous êtes un cryptographe.

dureuill
la source
Facile pour des nombres entiers suffisamment petits :)
CodesInChaos
Sans rien savoir cryptohash, il est un peu difficile de dire ce qu'est "suffisamment petit". Peut-être que cela prend deux jours pour terminer sur un supercalculateur. Mais oui, ça intpourrait être un peu short.
dureuill
Avec des entiers de 32 bits et des hachages cryptographiques typiques (SHA2, SHA3, etc.), le calcul devrait être relativement économique. Quelques secondes ou plus.
CodesInChaos
7

Il ressort clairement des autres réponses que la couverture de code à 100% dans les tests ne signifie pas une exactitude de code à 100%, ni même que tous les bogues détectés par les tests seront détectés (peu importe les bogues qu'aucun test ne pourrait détecter).

Une autre façon de répondre à cette question est une pratique:

Il existe dans le monde réel, et même sur votre propre ordinateur, de nombreux logiciels développés à l’aide d’un ensemble de tests couvrant 100% des cas, mais qui présentent encore des bogues, notamment des bogues que de meilleurs tests permettraient d’identifier.

Une question impliquée est donc:

Quel est l'intérêt des outils de couverture de code?

Les outils de couverture de code aident à identifier les zones que l'on a négligé de tester. Cela peut être correct (le code est manifestement correct même sans test), il peut être impossible à résoudre (pour une raison quelconque, un chemin ne peut pas être atteint), ou bien il peut être l'emplacement d'un grand bogue puant, maintenant ou suite à des modifications futures.

À certains égards, la vérification orthographique est comparable: quelque chose peut "passer" la vérification orthographique et être mal orthographié de manière à correspondre à un mot du dictionnaire. Ou cela peut "échouer" car les mots corrects ne sont pas dans le dictionnaire. Ou cela peut passer et être un non-sens total. La vérification orthographique est un outil qui vous aide à identifier les endroits que vous avez peut-être manqués dans votre relecture, mais comme elle ne peut pas garantir une relecture correcte et complète, la couverture par code ne peut pas garantir un test complet et correct.

Et bien sûr, la mauvaise façon d’utiliser le correcteur orthographique est bien connue: il est préférable d’adopter toutes les suggestions suggérées pour que la situation de la cane s’aggrave s’aggravant par la suite, si elle laisse un prêt.

Avec la couverture de code, il peut être tentant, surtout si vous avez un 98% presque parfait, de remplir des cas pour que les chemins restants soient atteints.

Cela équivaut à redresser avec une correction orthographique corrigée selon laquelle tous les mots sont météo ou noués, il s'agit de tous les mots appropriés. Le résultat est un fouillis de canards.

Cependant, si vous considérez quels tests les chemins non couverts ont vraiment besoin, l'outil de couverture de code aura fait son travail; pas en vous promettant l'exactitude, mais en soulignant une partie du travail à faire.

Jon Hanna
la source
+1 J'aime cette réponse car elle est constructive et mentionne certains des avantages de la couverture.
Andres F.
4

La couverture de chemin ne peut pas vous dire si toutes les fonctionnalités requises ont été implémentées. Laisser une fonctionnalité est un bogue, mais la couverture de chemin ne la détectera pas.

Pete Becker
la source
1
Je pense que cela dépend de la définition d'un bug. Je ne pense pas que les fonctionnalités ou fonctionnalités manquantes devraient être considérées comme des bugs.
eis
@eis - vous ne voyez pas de problème avec un produit dont la documentation indique qu'il fait X alors qu'en fait il ne le fait pas? C'est une définition assez étroite de "bug". Lorsque j'ai géré l'assurance qualité pour la gamme de produits C ++ de Borland, nous n'étions pas si généreux.
Pete Becker
Je ne vois pas pourquoi la documentation dire qu'il ne X si cela n'a jamais été mis en œuvre
eis
@ eis - si la conception d'origine demandait la fonctionnalité X, la documentation pourrait décrire celle-ci. Si personne ne l'implémentait, il s'agissait d'un bogue, et la couverture de chemin (ou tout autre type de test de boîte noire) ne le trouverait pas.
Pete Becker
Oops, la couverture de chemin est un test de boîte blanche , pas de boîte noire . Les tests de boîte blanche ne permettent pas de détecter les fonctionnalités manquantes.
Pete Becker
4

Une partie du problème est que la couverture à 100% ne garantit que le code fonctionnera correctement après une seule exécution . Certains bugs, tels que les fuites de mémoire, peuvent ne pas être apparents ou causer un problème après une seule exécution, mais au fil du temps, cela causera des problèmes à l'application.

Par exemple, supposons que vous ayez une application qui se connecte à une base de données. Peut-être que, dans une méthode, le programmeur oublie de fermer la connexion à la base de données une fois la requête terminée. Vous pouvez exécuter plusieurs tests avec cette méthode sans trouver d'erreur dans ses fonctionnalités, mais votre serveur de base de données risque de rencontrer un scénario de rupture des connexions disponibles, car cette méthode particulière n'a pas fermé la connexion lorsqu'elle a été effectuée et les connexions ouvertes doivent maintenant timeout.

Derek W
la source
Convenu que cela fait partie du problème, mais le véritable problème est plus fondamental que cela. Même avec un ordinateur théorique avec une mémoire infinie et sans concurrence, une couverture de test à 100% n'implique pas l'absence de bugs. Des exemples triviaux de cela abondent dans les réponses ici, mais en voici un autre: si mon programme est times_two(x) = x + 2, cela sera entièrement couvert par la suite de tests assert(times_two(2) == 4), mais cela reste évidemment du code buggy! Pas besoin de fuites de mémoire :)
Andres F.
2
C’est un bon point et je reconnais que c’est un clou plus grand et plus fondamental dans la perspective de la possibilité d’applications exemptes de bogues, mais comme vous le dites, il a déjà été ajouté ici et je voulais ajouter quelque chose qui n’était pas tout à fait couvert. réponses existantes. J'ai entendu parler d'applications qui se sont bloquées parce que les connexions de base de données n'étaient pas relâchées dans le pool de connexions lorsqu'elles n'étaient plus nécessaires - Une fuite de mémoire est un exemple canonique de mauvaise gestion des ressources. Mon propos était d’ajouter que la bonne gestion des ressources en général ne peut être entièrement testée.
Derek W
Bon point. D'accord.
Andres F.
3

Si chaque chemin dans un programme est testé, est-ce que cela garantit de trouver tous les bogues?

Comme déjà dit, la réponse est NON.

Si non pourquoi pas

Outre ce qui est dit, des bogues apparaissent à différents niveaux et ne peuvent pas être testés avec des tests unitaires. Juste pour en mentionner quelques-uns:

  • bogues détectés avec les tests d'intégration (les tests unitaires ne devraient pas utiliser de vraies ressources)
  • bugs dans les exigences
  • bugs dans le design et l'architecture
BЈовић
la source
2

Qu'est-ce que cela signifie pour chaque chemin à tester?

Les autres réponses sont excellentes, mais je veux juste ajouter que la condition "chaque chemin dans un programme est testé" est elle-même vague.

Considérez cette méthode:

def add(num1, num2)
  foo = "bar"  # useless statement
  $global += 1 # side effect
  num1 + num2  # actual work
end

Si vous écrivez un test qui confirme add(1, 2) == 3, un outil de couverture de code vous indiquera que chaque ligne est exercée. Mais vous n'avez en réalité rien affirmé à propos de l'effet secondaire global ou de la tâche inutile. Ces lignes exécutées, mais n'ont pas vraiment été testées.

Le test de mutation aiderait à trouver des problèmes comme celui-ci. Un outil de test de mutation aurait une liste de moyens prédéterminés pour "muter" le code et voir si les tests réussissent toujours. Par exemple:

  • Une mutation pourrait changer le +=à -=. Cette mutation n'entraînera pas d'échec du test. Cela prouverait donc que votre test n'affirme rien de significatif concernant l'effet secondaire global.
  • Une autre mutation pourrait supprimer la première ligne. Cette mutation n'entraînera pas d'échec du test. Cela prouverait donc que votre test n'affirme rien de significatif pour la tâche.
  • Encore une autre mutation pourrait supprimer la troisième ligne. Cela provoquerait un échec de test, ce qui dans ce cas montre que votre test affirme quelque chose à propos de cette ligne.

Essentiellement, les tests de mutation sont un moyen de tester vos tests . Mais comme vous ne testerez jamais la fonction réelle avec tous les jeux d'entrées possibles, vous n'exécuterez jamais toutes les mutations possibles, ce qui est à nouveau limité.

Chaque test que nous pouvons faire est une heuristique pour passer à des programmes sans bug. Rien n'est parfait.

Nathan Long
la source
0

Eh bien ... oui en fait, si chaque chemin "à travers" le programme est testé. Mais cela signifie que chaque chemin possible à travers tout l'espace de tous les états possibles du programme peut avoir, y compris toutes les variables. Même pour un programme très simple compilé statiquement - par exemple, un ancien correcteur de nombres Fortran - ce n’est pas faisable, bien que cela puisse au moins être imaginable: si vous n’avez que deux variables entières, vous avez en gros la possibilité de relier des points entre eux. une grille bidimensionnelle; cela ressemble beaucoup à Travelling Salesman. Pour n telles variables, vous traitez avec un espace n- dimensionnel, de sorte que pour tout programme réel, la tâche est totalement indisponible.

Pire: pour les choses sérieuses, vous n’avez pas seulement un nombre fixe de variables primitives, mais vous créez des variables à la volée dans des appels de fonction, ou vous avez des variables de taille variable ... ou quelque chose du genre, autant que possible dans un langage complet de Turing. Cela donne à l'espace d'états une dimension infinie, brisant tous les espoirs d'une couverture totale, même avec un équipement de test absurdement puissant.


Cela dit ... en réalité, les choses ne sont pas si sombres. Il est possible de prouver que des programmes entiers sont corrects, mais vous devrez renoncer à quelques idées.

Premièrement: il est vivement conseillé de passer à une langue déclarative. Langues Impératif, pour une raison quelconque, ont toujours été de loin le plus populaire, mais la façon dont ils mélangent des algorithmes avec des interactions du monde réel, il est extrêmement difficile de dire même ce que vous entendez par « correct ».

Beaucoup plus facile dans les langages de programmation purement fonctionnels : ceux-ci établissent une distinction claire entre les propriétés réellement intéressantes des fonctions mathématiques et les interactions floues du monde réel sur lesquelles on ne peut vraiment rien dire. Pour les fonctions, il est très facile de spécifier le «comportement correct»: si, pour toutes les entrées possibles (à partir des types d'argument), le résultat souhaité correspondant sort, alors la fonction se comporte correctement.

Maintenant, vous dites que c'est toujours insoluble ... après tout, l'espace de tous les arguments possibles est en général aussi d'une dimension infinie. C'est vrai - bien que pour une seule fonction, même des tests de couverture naïfs vous mènent bien plus loin que vous ne pourriez l'espérer dans un programme impératif! Cependant, il existe un outil puissant incroyable qui change le jeu: la quantification universelle / polymorphisme paramétrique . En gros, cela vous permet d'écrire des fonctions sur des types de données très généraux, avec la garantie que si cela fonctionne pour un exemple simple de données, cela fonctionnera pour toute entrée possible.

Au moins théoriquement. Il n'est pas facile de trouver les bons types qui sont vraiment si généraux que vous pouvez tout à fait le prouver - vous avez généralement besoin d'un langage typé en fonction de la dépendance , ce qui est plutôt difficile à utiliser. Mais écrire dans un style fonctionnel avec un polymorphisme paramétrique augmente déjà énormément votre «niveau de sécurité» - vous ne trouverez pas nécessairement tous les bogues, mais vous devrez les cacher assez bien pour que le compilateur ne les repère pas!

à gauche autour de
la source
Je ne suis pas d'accord avec votre première phrase. Passer en revue tous les états du programme ne détecte en soi aucun bogue. Même si vous recherchez des blocages et des erreurs explicites, vous n'avez toujours pas vérifié la fonctionnalité réelle, vous n'avez donc couvert qu'une petite partie de l'espace d'erreur.
Matthew Lu
@MatthewRead: si vous appliquez cela en conséquence, alors "l'espace d'erreur" est un sous-espace propre de l'espace de tous les états. Bien sûr, c'est hypothétique car même les états «corrects» constituent un espace beaucoup trop grand pour permettre des tests exhaustifs.
gauche du