Complexité du code

tbowan

13 Juillet 2017

Il est souvent nécessaire d'estimer la qualité d'un code source ou de pouvoir en extraire les parties à risques. Que ce soit pour maintenir le code ou l'auditer, cette information permet d'aiguiller le travail et d'accélérer la découverte de bogues ou de vulnérabilités.

Dans cet article, nous abordons trois métriques de la complexité du code : la complexité cyclomatique, la complexité NPath et la complexité cognitive.

Mesurer la qualité

Lorsque je travaille sur un logiciel, j'attache une certaine importance à la qualité du code source. La facilité à le comprendre, le tester et le maintenir conditionne le coût de correction des bogues et des vulnérabilités mais aussi leur fréquence.

Un code clair facilite le travail de l'auditeur mais aussi celui des développeurs. La découverte de vulnérabilité est plus facile mais aussi moins fréquente car les développeurs ont pu en éviter un grand nombre.

Pour se faire à l'idée de la qualité d'un code source, on peut commencer par en lire des portions au hasard. Avec l'expérience, on reconnait assez rapidement un travail soigné d'un bricolage sans nom. Bien que très utile, cette première impression reste personnelle et difficile à communiquer.

On peut alors utiliser des métriques logicielles qui donnent une certaine mesure de la qualité du code source. Leur objectivité et impartialité évitent les problèmes liés aux jugements personnels mais leur interprétation nécessite de bien les comprendre, ce qui ne facilite pas toujours leur communication...

Dans cet article, je vous propose d'aborder trois métriques qui tentent de mesurer la complexité d'un code source. C'est à dire le travail nécessaire pour comprendre, tester et modifier un code source.

Complexité Cyclomatique

Aussi appelée mesure de McCabe, cette première métrique a été inventée en 1976 par Thomas McCabe qui a appliqué la théorie des graphes aux programmes et en a tiré une mesure de complexité1 correspondant aux nombres de décisions d'un algorithme.

Pour comprendre cette mesure, il faut utiliser le graphe de flot de contrôle du programme. Les noeuds correspondent aux blocs d'instructions et les arcs aux enchainements. On peut alors se rendre compte visuellement de la complexité de la structure d'un programme.

Compter le nombre total de chemin dans le graphe est inutile. En effet, pour un graphe cyclique, correspondant à un programme avec des boucles, le nombre total de chemins est infini et ne permet donc plus de comparer les programmes entre eux.

Plutôt que de compter tous ces chemins, l'idée de McCabe est de ne compter que les chemins de base. Ces chemins permettent de générer tous les autres par combinaisons. Mathématiquement, on parle des chemins linéairement indépendant du graphe (G).

En connectant la sortie du programme à son entrée, il s'agit alors de calculer le nombre cyclomatique V(G) du graphe G contenant e arcs, n noeuds et p composantes connexes :

V(G) = e − n + p

Ce nombre correspond aux embranchements dans le graphe et donc aux points de décision du programme. On peut le calculer simplement en comptant les instructions conditionnelles plutôt qu'en construisant le graphe.

Voici donc un exemple de code source sur lequel appliquer les métriques de complexité. Ce code calcule la somme des diviseurs et vous dit si le nombre est parfait, abondant ou deficient. Le but est uniquement illustratif.

#include <iostream>
#include <string>
                                                  // Cyclomatic complexity :
int main(int argc, char * argv[]) //  - - - - - - - - - - - - +1
{
    if (argc != 2) { // - - - - - - - - - - - - - - - - - - - +1
        std::cerr << "un argument nécessaire" << std::endl ;
        return 1 ;
    }

    try {
        int a = std::stoi(argv[1]) ;

        int sum = 0 ;
        for (int i = 1; i < a ; ++i) { // - - - - - - - - - - +1
            if (a % i == 0) { //  - - - - - - - - - - - - - - +1
                sum += i ;
            }
        }

        if (sum == a) { //  - - - - - - - - - - - - - - - - - +1
            std::cout << "a est parfait" << std::endl ;
        } else if (sum < a) { //  - - - - - - - - - - - - - - +1
            std::cout << "a est déficient" << std::endl ;
        } else {
            std::cout << "a est abondant" << std::endl ;
        }

    } catch (std::invalid_argument const & e) { //  - - - - - +1
        std::cout << "Error : " << e.what() << std::endl ;
        return 1 ;
    }

    return 0 ;
} // Total  - - - - - - - - - - - - - - - - - - - - - - - - -  7

L'intérêt de la théorie des graphes est de fournir un cadre formel pour prouver ces équivalences et une réalité mathématique derrière le nombre calculé.

L'une de ces réalité est que la complexité cyclomatique correspond au nombre minimal de tests pour couvrir toutes les instructions d'un programme. Un nombre de tests inférieur à ce minima signifie soit qu'il manque des tests, soit que le code est trop complexe inutilement (i.e. contient des branches inutiles) et qu'on peut donc le simplifier.

Il est généralement admis qu'une complexité cyclomatique de 10 est un maximum pour une fonction. C'est le chiffre proposé initialement par McCabe après l'avoir appliquée sur des projets réels et est toujours utilisé par les outils de mesure automatique actuels.

Complexité NPath

La complexité cyclomatique ne prenant pas en compte les imbrications des instructions conditionnelles, Nejmeh a proposé en 1988 la notion de complexité NPath2, également issue de la théorie des graphes et qui donne le nombre de chemins acycliques dans le programme.

Là où McCabe garde les boucles et compte les chemins de base, Nejmeh préfère compter tous les chemins mais pour ça, il doit élimine les boucles. La complexité NPath est donc le nombre de chemins possibles dans un programme sans passer deux fois par la même suite d'instructions : les chemins acycliques.

Plutôt que de travailler sur le graphe, il est ici également possible et plus pertinent de faire un comptage en lisant le programme. En effet, réduire un graphe orienté quelconque en graphe acyclique est NP-Complet3 et donc bien trop coûteux sur de gros codes.

La complexité NPath se calcule en multipliant la complexité pour les séquences d'instructions et en additionnant celles des branches conditionnelles. Techniquement, chaque structure (if, for, ...) est traitée spécifiquement.

Je ne rentrerai pas dans les détails que vous pouvez trouver dans l'article original de Nejmeh ou dans la documentation de checkstyle.

Nous pouvons appliquer cette méthode sur le même code que précédement. Le calcul est plus difficile à illustrer car le coût d'une structure dépend de son contenu et il faut ensuite multiplier ces complexités pour les séquences.

#include <iostream>
#include <string>
                                                  // NPath complexity :
int main(int argc, char * argv[])
{
    if (argc != 2) {
        std::cerr << "un argument nécessaire" << std::endl ;
        return 1 ;
    } // if + 1  - - - - - - - - - - - - - - - - - - - - - => 2

    try {
        int a = std::stoi(argv[1]) ;

        int sum = 0 ;
        for (int i = 1; i < a ; ++i) {
            if (a % i == 0) {
                sum += i ; //  - - - - - - - - - - - - - - 1
            } // if + 1- - - - - - - - - - - - - - - - - - => 2
        } // for + 1 - - - - - - - - - - - - - - - - - - - => 3

        if (sum == a) {
            std::cout << "a est parfait" << std::endl ;
        } else if (sum < a) {
            std::cout << "a est déficient" << std::endl ;
        } else {
            std::cout << "a est abondant" << std::endl ;
        } // if + elif + else  - - - - - - - - - - - - - - => 3

    } catch (std::invalid_argument const & e) { //  - - - 1
        std::cout << "Error : " << e.what() << std::endl ;
        return 1 ;
    } // try (for x if) + catch  - - - - - - - - - - - - - => 10

    return 0 ;
} // Total : if x try  - - - - - - - - - - - - - - - - - - => 20

Ces deux complexité sont liées l'une à l'autre. Un programme ayant une complexité cyclomatique c a une complexité NPath au pire de 2c. Le minimum est atteint si les strucures conditionnelles sont uniquement imbriquées, le maximum si elles sont uniquement séquentielles. Les valeurs intermédiaires donnent une idée de l'agencement des structures du programme.

De même que la complexité cyclomatique permet de connaître le nombre minimal de tests pour couvrir tout le code, la complexité NPath donne le nombre minimal de tests pour couvrir toutes les combinaisons acycliques de chemins.

Le seuil généralement admis est ici de 200 et vient des premiers essais chez AT&T. Une valeur supérieure pour une fonction indique qu'il est pertinent de la vérifier pour pouvoir la simplifier.

Complexité Cognitive

La dernière complexité abordée a été proposée en 2016 par SonarSource4 pour proposer une mesure plus intuitive de la difficulté à comprendre un code source.

Cette mesure s'inspire de la complexité cyclomatique mais s'affranchi complètement de tout fondement mathématique et d'une interpretation en termes de tests.

Pour la calculer, on incrémente également un compteur mais en prenant en compte la difficulté de compréhension liée aux instructions et leur niveau d'imbrication.

Le but n'est pas de mesurer la complexité mathématique de l'algorithme mais de quantifier l'effort nécessaire pour la comprendre. Le choix des instruction qui incrémente suit cette logique en pénalisant les inscructions jugées complextes (i.e. goto, continue) et en avantageant les plus lisibles (la définition d'une fonction compte pour 0). La prise en compte de l'indentation suit ce but.

Par exemple, la complexité cognitive incrémente pour l'instruction switch et chacun des break mais ignore les case alors qu'à l'inverse, la complexité cyclomatique incrémente pour chaque case mais ignore le switch et les breaks.

Voici ce que donne cette métrique sur le code d'exemple :

#include <iostream>
#include <string>
                                                  // Cognitive complexity :
int main(int argc, char * argv[])
{
    if (argc != 2) { // - - - - - - - - - - - - - - - - - - - +1
        std::cerr << "un argument nécessaire" << std::endl ;
        return 1 ;
    }

    try {
        int a = std::stoi(argv[1]) ;

        int sum = 0 ;
        for (int i = 1; i < a ; ++i) { // - - - - - - - - - - +2 (nesting = 1)
            if (a % i == 0) { //  - - - - - - - - - - - - - - +3 (nesting = 2)
                sum += i ;
            }
        }

        if (sum == a) { //  - - - - - - - - - - - - - - - - - +2 (nesting = 1)
            std::cout << "a est parfait" << std::endl ;
        } else if (sum < a) { //  - - - - - - - - - - - - - - +1
            std::cout << "a est déficient" << std::endl ;
        } else { // - - - - - - - - - - - - - - - - - - - - - +1
            std::cout << "a est abondant" << std::endl ;
        }

    } catch (std::invalid_argument const & e) { //  - - - - - +1
        std::cout << "Error : " << e.what() << std::endl ;
        return 1 ;
    }

    return 0 ;
} // Total  - - - - - - - - - - - - - - - - - - - - - - - - -  11

L'absence de fondement mathématique, une qualité d'après les auteurs de cette métrique, empêche toute interprétation de la valeur obtenue. Dans l'exemple la valeur 11 n'a aucune réalité et ne peut servir qu'à comparer des codes entre eux pour savoir lequel utilise plus de structures ou d'indentation.

Le seuil proposé par l'outil est de 15 mais je n'ai trouvé aucune documentation qui explique l'origine de cette valeur, sans doute l'expérience des concepteurs dans la métrologie logicielle.

Critiques et Conclusion

Ces trois métriques ont en commun le but de mesurer la complexité du code mais ont une approche et une interprétation différente :

Les utiliser globalement sur un projet n'a pas de sens. Tout d'abord, aucune corrélation avec la qualité du produit n'a été démontrée (i.e. nombre de bogues) et on manque effectivement d'études sur cet aspect. Ensuite, il existe des cas où le dépassement des seuils est nécessaire et justifiable. Enfin, la complexité d'un projet est plus liée à sa couverture fonctionnelle qu'au code lui-même (le refactorer ne fera que redistribuer cette complexité entre les différents composants).

L'utilité de ces méthodes est plutôt de mesurer les portions du code pour les comparer et pointer, parmis la base de code, les endroits les plus pertinents en terme d'amélioration et d'audit. Ces métriques pointent ainsi les zones à risque les plus succeptibles de contenir des défauts voir des vulnérabilités.

Il s'agit donc avant tout d'un outil au service de l'auditeur qui, manié avec intelligence, permet d'orienter le travail avec efficience.


  1. A Complexity Measure, McCabe, IEEE transactions on software engineering, volume SE-2 issue 4, décembre 1976, (PDF).

  2. NPATH: a measure of execution path complexity and its applications, Brian A. Nejmeh, Communications of the ACM, volume 31, issue 2, février 1988.

  3. Coupe-cycles de sommets, wikipedia.

  4. Cognitive Complexity, G. Ann Campbell, SonarSource (PDF).