La structure

Les types de mesures structurelles

• Les mesures de la structure sont souvent appelées mesures de complexité.
• La structure d'un logciel doit être examinée pour voir son impact sur l'objectif de la mesure.

Plusieurs aspects de la structure peuvent être considérés:

• Le flot de contrôle : le séquencement d'exécution des instructions.
• Le flot de données : l'evolution des données dans le programme.
• La structure des données.

La structure du flot de contrôle

• Si un programme A a une structure plus complexe qu'un programme B alors la mesure m doi être telle que : m(A) > m(B).
• Cette règle dépend de la définition de la bonne structure.
• Il nous faut une approche indépendante de la définition de la bonne structure d'un programme.
• Il existe une approche basée sur la décompostion du graphe en des composants primitfs.

Le graphe de contrôle

• Un graphe orienté : G =(N,E)
• L'ensemble N des noeuds représente les instructions du programme.
• L'ensemble E des arcs orientés (s,s') représentent le passage du contrôle de l'instruction s, source de l'arc, à l'instruction s', destination de l'arc.
• Chaque n ud est caractérisé par:
  • le degré interne : le nombres d'arcs aboutissant au n ud ou le nombre de prédecesseurs.
  • le degré externe : le nombre d'arcs sortant du n ud ou le nombre de successeurs.

• Un chemin est une suite d'arcs telle que la destination de est la source de .
• Un chemin simple est un chemin qui ne comporte pas d'arcs identiques.
• Deux n uds spéciaux le n ud début et le n ud fin.
• le n ud début a un degré interneégal à 0 et le n ud fin a un degré externe égal à 0. Chaque n ud existe sur un chemin du n ud début jusqu'au n ud fin.
• les n uds avec un degré externe égal à 1 sont des n uds procédures tous les autres (à part le n ud fin) sont des n uds prédicats.

Composition de graphes

Les représentent des graphes de flot de contrôle.

• Le séquencement de et : ; ou Seq(F1,F2) ou est la fusion du n ud fin de avec le n ud début de .
  nous avons F(A;A') = F(A) ; F(A').
• L'imbrication de dans au n ud x, notée ou s'il n'y a pas d'ambiguïté, est le graphe obtenu à partir de en remplaçant l'arc partant de x par tout . Le n ud x sera confondu avec le début de F2 et la fin de F2 sera fusionnée avec la destination de l'arc partant de x.
• L'imbrication est l'imbrication de , ..., dans F en les n uds respectivement.

Les graphes de contrôle premiers

• Les graphes de contrôle premiers sont des graphes qui ne sont pas trivialement décomposés par séquencement et imbrication.

La notion de structuration généralisée

• Un programme est dit structuré (ou bien structuré) ssi il est décomposable en un nombre réduit de constructions simples. En général ces constructions sont: la séquence, la sélection et l'itération.

Plus formellement, étant donné un ensemble S de graphes premiers, une famille de graphes est S-structurée si elle satisfait les conditions suivantes:

• Chaque membre de S est S-structuré.
• Si F et F' sont S-structurés alors :
  • F;F' est S-structuré.
  • F(F') est S-structuré, si l'imbrication est définie.

• Aucun graphe n'est S-structuré à moins de prouver qu'il peut être généré par un nombre fini d'applications des étapes précédentes.

La notion de structuration généralisée

• Exemple 1 : soit , alors la notion de -structuré correspond à la notion bien connue de structuration.
• Exemple 2 : une autre notion pourrait être basée sur l'ensemble ,

La décomposition en graphes premiers

• Chaque graphe de contrôle possède une décomposition unique en graphes premiers.
• Le résultat est l'arbre de décomposition.
• Chaque n ud de l'arbre de décomposition est premier et donc non décomposable.
• étant donné un ensemble S, si les n uds de l'arbre de décomposition n'appartiennent pas à S alors le programme correspondant au graphe n'est pas S-structuré.

Les mesures hiérarchiques

Plusieurs mesures structurelles peuvent être définis en utilisant la notion de graphes premiers et de composition de graphes par séquencement et imbrication.

Exemple la notion de profondeur d'imbrication peut être mesurée par . Soit F le graphe de contrôle associé à un programme.

Nous avons:

• Premiers: Si F est premier alors si et sinon.
• Séquencement : .
• Imbrication : .

De façon générale pour chaque ensemble de premiers S, une mesure m est une mesure hiérarchique sur les S-graphes ssi on peut définir:

• m(F) pour . C'est la règle .
• . La fonction ou fonctions de séquencement. C'est la règle .
• La ou les fonction(s) pour l'imbrication, pour chaque . C'est la règle .

Pour mesurer la longueur d'un programme on peut se baser sur la mesure v du nombre d'instructions d'un programme:

• et où n correspond au nombre de n uds procédure dans F.
• .
• .

Nombre de n uds: mesure n

 

• : n(F) = nombre de n uds pour chaque premier F.
• :
• : , pour chaque premier F.

Nombre d'arcs, mesure e

 

• : e(F) = nombre d'arcs dans F pour chaque premier F.
• :
• : , pour chaque premier F.

Le plus grand premier, mesure

 

• : = nombre de prédicats dans F pour chaque premier F.
• :
• : pour chaque premier F.

Nombre d'occurences d'un premier donné: p

 

• : p(F) = 1 si F est le premier en question et 0 sinon.
• :
• : .

mesure de D-structuration: d

 

(C'est une mesure nominale et vaut 1 si le graphe est D-structuré ou -structuré et 0 sinon.)

• : d(F) = 1 si et 0 sinon.
• :
• : .

Les mesures de la complexité

• Plusieurs mesures prétendant évaluer la complexité sont des mesures hiérarchiques.
• Il est facile dans le cadre qu'on vient de définir d'évaluer la subjectivité des mesures:
  • Quelle est la complexité de chacun des graphes premiers.
  • Quelle est la complexité du séquencement.
  • Quelle est la complexité de l'imbrication dans un premier donné.

La complexité cyclomatique de McCabe

• Le nombre cyclomatique d'un graphe de contrôle F correspondant à un programme P est v(F)= e-n+2.
• Le nombre cyclomatique représente le nombre de cycles linéairement indépendants dans F.
• On peut montrer que v(F)= d+1, où d est le nombre de n uds prédicat dans F.

Exemples d'utilisation du nombre cyclomatique:

• Grady a fait des études empiriques chez Hewlett-Packard sur 850 000 lignes de code. L'étude a montré une corrélation entre le nombre cyclomatique d'un module et le nombre de mises à jour nécessaires. Il a été décidé que le nombre cyclomatique ne devrait pas excéder 15.
• La procédure assurance qualité pour "Channel Tunnel rail system" exige qu'un module ayant un nombre cyclomatique plus grand que 20 soit rejeté.

McCabe a proposé une mesure appelée la complexité essentielle pour évaluer le degré de structuration.

• ev(F) = v(F) -m où m est le nombre de sous-graphes premiers D-structurés de F.
• Quand le graphe est D-structuré ev(F) = 1.
• Quand le graphe n'est pas structuré la mesure de la complexité essentielle peut être contre intuitive.

Couvertures de test

• Soit P un programme.
• S sa spécification.
• Un cas de test est une paire (i,S(i)) où i est une valeur d'entrée du programme et S(i) est le résultat attendu tel que défini dans la spécification S.
• Tester a pour objectif de s'assurer que P(i) le résultat effectif est le même que S(i).

Mesures de couverture de test

Exemple :

Les entrées d'un programme P sont les notes exprimées en pourcentage et les sorties sont des commentaires.

La spécification S du programme P est formulée par les règles suivantes.

• Si la note est inférieure à 45, P sort "échec".
• Si la note est entre 45 et 80 inclus, P sort "admission".
• Si la note est supérieure à 80, P sort "admission avec distinction".
• Toute entrée non comprise entre 0 et 100 inclus doit produire "donnée non valide".
• Un ensemble de 5 cas de test:
  (40, "échec") 
  (60,"admission") 
  (90,"admission avec distinction") 
  (110,"donnée invalide") 
  (fifty,"donnée invalide")

Il existe deux approches pour les stratégies de test:

• Les tests basés sur la boîte noire: seules les spécifications servent à dériver les cas de test.
• Les tests basés sur la boîte blanche: Le code du programme est considéré lors de la production de cas de test.

• La couverture d'instructions: les cas de test sont choisis de telle sorte qu'une instruction du programme soit exécutée au moins une fois.
• Il s'agit de trouver un ensemble de chemins d'exécution tel que chaque instruction appartienne au moins à un chemin.
• La couverture d'arcs.
• La couverture de chemins d'exécution. Impossible à couvrir à 100% dès qu'il y a des boucles.

Problèmes

• Il y a des chemins appartenant au graphe de contrôle et qui ne sont jamais exécutés.
• Aucune stratégie ne peut garantir que le programme est correct.
• La connaissance des chemins correspondant à une stratégie donnée ne donne pas une indication sur les cas de test.

Mesures de couvertures de test

• un cas de test correspond à un chemin dans le graphe de contrôle.
• il faut calculer le nombre minimum de chemins requis pour satisfaire une stratégie.
• est définie pour chaque stratégie de test.

Mesures de couvertures de test

Mesures pour les graphes premiers

Fonction de séquencement:

Fonctions d'imbrication:

Fonctions d'imbrication:

Le taux d'efficacité d'un test: Exemple le programme de commentaires des notes avec les cas de test 60 et 90.

• Les chemins parcourus : (A B D E G), ( A B D E F G).
• Couverture d'instructions 6 instructions de 7 : 86%.
• Couverture d'arcs 7 de 9 arcs : 78%.
• Couverture de chemins 2 de 4 : 50%.

Modularité et attributs du flot de contrôle

• Les mesures internes intra-modulaires ont des dérivés inter-modulaires. Pour un ensemble de modules (ou procedures):
  • La longueur moyenne en nombre de lignes de codes.
  • La médiane du niveau d'imbrication.
  • etc.

• Il existe des mesures spécifiques à la structure dépendance inter-modules.
• Ces mesures concenent la structure spécifiée lors de la conception ou la structure effective du code.

Modèles de modularité et information de flot

• Définition: Un module est une séquence d'instructions (contiguës) délimitée par des délimiteurs et possédant un identificateur.
• Un module est compilable de façon séparée.
• Un programme, une procédure, une fonction, un module( comme en modula2) peuvent être considérés comme des modules.
• Les mesures sont basés sur le graphe d'appels.

Modularité globale

• La taille moyenne des modules n'est significative que si on prend en compte la variance.
• Pour établir un modèle général de la modularité, il faut se focaliser sur des aspects spécifiques puis construire le modèle global.

Morphologie

• La morphologie est une notion qui tente de capter la forme globale du système.
• Elle est basée sur le graphe de dépendance entre modules.
• Les n uds du graphe sont les modules, les arcs non orientés expriment les dépendances entre modules: appel ou flot de données.

Mesures des attributs concernant la morphologie:

• Taille : nombre de n uds, nombre d'arcs (ou arêtes) ou une combinaison des deux.
• Profondeur : le plus long chemin (en nombre d'arcs) du n ud racine (le module représentant le programme principal, main) jusqu'à un n ud feuille (sans successeur).
• Largeur : le nombre maximum de n uds appartenant au même niveau. Le niveau étant le nombre minimum d'arcs entre un n ud et la racine.
• Le rapport nombre d'arcs/nombre de n uds.

Ces mesures ne sont pas spécifiques au graphe de dépendance. Elles peuvent être appliquées à la plupart des types de graphes.

Impureté d'arbre

• Une chaîne dans un graphe non-orienté est l'équivalent du chemin dans le graphe orienté. C'est une séquence de n uds telle que il existe une arête entre et , pour i =1, n-1.
• Un cycle est une chaîne dans laquelle le n ud début est le même que le n ud fin. = dans l'exemple précédent.
• Un graphe non-orienté est dit connexe ssi , dans l'ensemble des n uds, il existe une chaîne entre et .
• un arbre est un graphe connexe sans cycles.
• Un graphe complet est un graphe dans lequel chaque deux n uds sont liés par une arête.

• La structure d'arbre est un signe d'une bonne conception.
• La mesure d'impureté d'arbre devrait nous renseigner de combien le graphe est éloigné de la structure d'arbre.

• Un arbre ayant n n uds possède exactement n-1e arêtes.
• A chaque graphe connexe G, on peut associer un arbre de parcours tel que tous les n uds de G sont connectés sans qu'il y ait de cycles. Les n uds de cet arbre sont les mêmes que ceux de G et les arcs sont un sous-ensemble de l'ensemble d'arcs de G.

Toute mesure m d'Impureté d'arbre doit satisfaire au moins ces 4 propriétés:

1. m(G) = 0 ssi G est un arbre.
2. m(G) > m(G') si G diffère de G' par l'insertion d'un arc supplémentaire.
3. Soient A le nombre d'arcs dans G et N le nombre de n uds et A' et N' ceux de G' alors si N < N' et A - N +1 = A' - N' + 1 alors m(G) > m(G').
4. Soit le graphe complet ayant n n uds alors et un graphe de N n uds on a

Exemple d'une mesure:

• Le nombre d'arcs d'un graphe complet à n n uds est :
• Le nombre d'arcs d'un arbre à n n uds est : n -1.
• Le nombre maximum d'arcs excédent l'arbre de parcours d'un grahe à n n uds est :
• Le nombre d'arcs excédant l'arbre de parcours d'un graphe G de e arcs est exc = e - n +1.
• On peut choisir m(G) telle que

La réutilisation interne

• La réutilisation interne c'est le degré de réutilisation des mêmes modules dans un même produit.
• Le graphe d'appel est suffisant si on ne veut pas considérer les différents appels au même module M par le même module M'.
• Une mesure de la réutilisation interne devrait respecter les propriétés 1 et 2 de l'impureté d'arbre. La propriété 4 est également raisonnable à condition de ne pas considérer que .
• Une mesure pourrait être r(G) = e - n +1

Le couplage

• Le couplage est le degré d'inter-dépendance entre deux modules.
• C'est une mesure impliquant deux modules.
• Le couplage global pourrait être dérivé du couplage entre les différentes paires de modules poosibles.
• Le couplage est un des attributs les plus importants lié à la qualité de la conception.

Considérons les relations suivantes qui ont lien avec le couplage sur l'ensemble des paires de modules. Et soient x et y deux modules.

• Pas de couplage: ssi x et y sont complètement indépendants.
• Couplage de données : ssi x et y communiquent seulement au moyen de paramètres. Ces paramètres n'influent pas sur le contrôle.
• Couplage de signature: ssi x et y utilisent le même type d'enregistrement comme paramètre.
• Couplage de contrôle: ssi x passe un paramètre à y qui influence le contrôle.
• Couplage par variables globales communes: ssi x et y accèdent à la même donnée globale. Ce type de couplage est indésirable car il rend la maintenance difficile.
• Couplage de contenu: ssi x modifie des données ou des instructions à l'intérieur de y.

• La relation de dépendance de est plus forte que pour i = 1, 5.
• x et y sont lâchement couplés si i = 1 ou 2 et fortement couplés si .
• Le couplage entre modules est représenté par un graphe orienté.
• Les n uds du graphe sont les modules et les arcs représentent le couplage et sont étiquetés par (i,j) où i représente la relation et j le nombre de fois que les deux modules sont couplés par cette relation.

• Fenton et Melton ont défini une mesure à échelle ordinale du couplage :

  

  où i est le numéro de la relation de couplage la plus élevée et n est le nombre d'interconnexions entre x et y.

• Le couplage global d'un système S formé des modules peut être dérivée de c: C(S) est la médiane de l'ensemble

D'autres mesures sont appliquées à un seul module et évaluent le degré de dépendance aux autres.

• Le nombre maximum d'inter-connexions par module.
• Le nombre moyen d'inter-connexions par module.
• Le nombre total d'inter-connexions par module.
• Le nombre de modules ayant accès à des inter-connexions de contrôle.
• le nombre d'inter-connexions de données avec le module principal.

La cohésion

La cohésion d'un module est le degré de participation des composants à est un attribut qui représente la participation des composnats à la même tâche.

Yourdon et Constantine ont proposés des classes de cohésion ce qui offre une mesure à échelle ordinale:

• Fonctionnelle: le module effectue une seule fonction bien définie.
• Séquentielle: le module effectue plus d'une fonction, mais dans l'ordre défini par la spécification.
• Communicationnelle: le module effectue plusieurs fonctions toutes sur le même ensemble de données (non organisés comme une seule structure ou un seul type).
• Procédurale : le module effectue plusieurs fonctions appartenant à un processus donné.
• Temporelle: le module effectue plusieurs fonctions intervenant toutes dans le mêne laps de temps.
• Logique: le module effectue plusieurs fonctions liées logiquement.
• Cohésion par coïncidence: le module effectue plusieurs fonctions sans aucune liaison entre elles.

La cohésion

• Ces classes sont listées par degré d'indésirabilité croissant.
• Un module est caractérisé par son type de cohésion le pire.
• Une autre classe pourrait être définie : la cohésion abstraite pour représenter le fait que les fonctions s'appliquent à un type de données abstrait.
• La cohésion abstraite est une cohésion de donnée.
• Une mesure de la cohésion :

  

  

Le flot d'information

La quantification du flot d'information pourrait être effectuée en mesurant:

• Le niveau total du flot d'information dans le système.
• Le niveau total de flot d'information entre un module donné et le reste du système.

La mesure Henry et Kafura

• Un flot direct local existe ssi
  • un module appelle un autre et lui passe de l'information.
  • Le module appelé retourne des résultats à l'appelant.

• Un flot indirec local existe ssi:
  • le module appelé retourne un résultat qui sera utilisé par un autre module appelé.

• Un flot global existe ssi:
  • L'information passe d'un module à l'autre par l'intermédiare d'une structure de donnée globale.

• Deux attributs de flot d'information peuvent être définis:
  • Le fan-in d'un module M est le nombre de flots locaux terminant en M plus le nombre de structure de données à partir desquelles l'information est extraite par M.
  • Le fan-out d'un module M est le nombre de flots locaux sortant de M plus le nombre de structures de données mises à jour par M.

• La complexité du flot d'information d'un module M est :

  

  

Les raffinements de Shepperd:

• Les appels récursifs doivent être traités comme les autres appels.
• Une variable partagée entre deux modules ou plus devrait être traitée comme une variable globale.
• Les modules de librairie et du compilateur devraient être ignorés.
• Le flot indirect devrait être compté à travers un seul niveau hiérarchique.
• Le flot indirect devrait être ignoré à moins que la même variable soit importée et exportée par le module appelant.
• Il ne faut pas prendre en compte l'analyse dynamique des appels.
• Les flots dupliqués devraient être ignorés.
• La longueur du module ne doit pas intervenir. C'est un autre attribut.

• La complexité de Shepperd:

  

  

• La complexité de Shepperd est très fortement corrélée au temps de développement.
• Les estimateurs ont plus de chance d'être précis s'ils impliquent des mesures d'attributs spécifiques.

Flot d'information et couverture de test

• Les tests basés sur le flot de données utilisent la notion de chaîne def-use. C'est un chemin qui lie la définition d'une variable à son utilisation.
• Les c-uses sont les utilisations de variables dans le calcul.
• Les p-uses sont les utilisations de variables dans les conditions.
• Une mesure de complexité pourrait être le nombre minimum de chemins assurant la couverture de toutes les chaînes def-use.
• Empiriquement c'est une bonne mesure.

Les mesures orientées-objet

Le monde en orienté-objet est vu comme:

• Un ensemble d'individus.
• Un ensemble de propriétés associées aux individus.
• Un objet est un individu plus ses propriétés.
• Une classe est un ensemble d'objets.
• Une méthode est une opération sur l'objet définie dans la classe.

Les mesures orientées-objet

Les mesures de Chidamber et Kemerer:

• nombre de méthodes pondérées par classe:

  

  où est une pondération reflétant la complexité de la méthode .

• Profondeur de l'arbre d'héritage (DIT):
  • L'arbre d'héritage est un graphe dans lequel les n uds sont des calsses et les arcs représentent un lien d'héritage entre classes.
  • La mesure DIT est définie pour chaque classe. C'est la longueur du plus long chemin de la racine jusqu'à cette classe.
  • La mesure DIT est liée à la notion de portées des propriétés. Elle mesure le nombre de classes ancêtres pouvant affecter la classe.

• Le nombre de fils (NOC) : c'est le nombre de successeurs immédiats dans l'arbre d'héritage.
• Le couplage entre classes d'objets (CBO) : le nombre de classes avec lesquelles une classe donnée est couplée.
• Les réponses pour une calsse (RFC): c'est le nombre des méthodes de la calsse plus le nombre des méthodes appelées par les méthodes locales.
• La mesure de manque de cohésion (LCOM): c'est le nombre d'ensembles disjoints de méthodes locales.

Les structures de données

• Une mesure des structures de données devrait capturer la quantité de données d'un système.
• La mesure de Halstead est un exemple: c'est le nombre d'opérandes distincts dans un programme :

  nombre de variables + nombre de constantes + nombre de labels.

• Le rapport D/P = taille de la base de donnée en octets/ taille du programme en DSI (nombre d'instructions source livrées).

Les structures de données

• La contribution du rapport D/P au coût dans le modèle COCOMO:

  

• La complexité des structures de donées et de la structure du contrôle sont souvent en conflit.

Difficulté avec la mesure de complexité

• La mesure ne doit pas inclure plusieurs attributs.
• La mesure ne doit pas être conçue pour différents objectifs.
• Il ne faut pas utilser une seule mesure de comlexité.

Propriétés d'une mesure de complexité M

• Il existe deux programmes P et Q tels que .
• Si c est un nombre non négatif alors il existe un nombre fini de programmes tels que M(P) = c.
• Il existe deux programmes distincts tels que M(P) = M(Q)
• Il existe deux programmes équivalents tels que .
• Pour tout P et Q nous avons: et

• Il existe des programmes P et Q tels que Q est obtenu par permutation des instructions de P et
• Si P est un renommage de Q alors M(P) = M(Q)
• Il existe deux programmes P et Q tels que M(P) + M(Q) < M(P;Q)