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é correspondant aux nombres de décisions d’un algorithme.

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

Pour comprendre cette mesure, il faut utiliser le graphe de flot de contrôle du programme. Les nœuds 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$ nœuds et $p$ composantes connexes :

$$\begin{align} V(g) & = e - n + p \end{align}$$

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 déficient. Même si c’est sûrement très utile, le but est ici 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é NPath, également issue de la théorie des graphes et qui donne le nombre de chemins acycliques dans le programme.

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

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-Complet (cf. problème du coupe-cycle de sommets) 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édemment. 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 $2^c$. Le minimum est atteint si les structures 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 aujourd’hui ne cherche pas à mesurer la complexité informatique d’un algorithme mais cognitive, c’est à dire la facilité avec laquelle un être humain est capable de le comprendre. La notion n’étant pas formellement définie, elle fait l’objet de recherche actives, encore aujourd’hui.

La version la plus consensuelle (surtout parce qu’elle est intégrée à leur outil) est celle de SonarSource. Elle a été proposée en 2016 et se sert d’un compteur qui est incrémenté lorsque des instructions et structures de contrôles particuliers sont rencontrés.

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

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 instructions jugées complexes (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.

Si vous cherchez une variante de complexité cognitive qui tente d’obtenir une corrélation plus fiable entre la valeur calculée et la difficulté ressentie par les développeurs, vous pouvez vous tourner vers le module npm genese-complexity qui suit un principe similaire (mais avec d’autres valeurs pour les incréments).

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 :

• La complexité cyclomatique compte le nombre de point de décision dans le code et donne le nombre minimal de tests pour couvrir le code,
• La complexité NPath compte le nombre de chemin acycliques possibles et donne le nombre minimal de tests pour couvrir les combinaisons possibles,
• La complexité cognitive calcule un poids qui traduit une difficulté de lecture du code.

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, parmi 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 susceptibles 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.