Brevet FR2911971A1 — publié le 20080801

PROCEDE ET SYSTEME DE VERIFICATION DE PROPRIETES D'UN PROGRAMME INFORMATIQUE La présente invention concerne un procédé et un système de vérification de propriétés d'un programme informatique. Elle s'applique notamment à tous programmes informatiques sous forme de codes sources dont on veut vérifier des propriétés, notamment de sûreté, de sécurité et de bon fonctionnement. Elle s'applique en particulier pour des programmes informatiques critiques. Il existe des programmes informatiques critiques embarqués par exemple 1 o dans les transports aériens et terrestres et les centrales nucléaires. Il est nécessaire, voire impératif, de s'assurer que ces programmes respectent notamment des propriétés de sûreté, de sécurité et de bon fonctionnement. D'autres propriétés peuvent être vérifiées. Ces propriétés sont exprimées sur le code source du programme étudié. 15 Plusieurs méthodes peuvent être utilisées pour apporter des éléments de confiance dans les programmes critiques en vérifiant des propriétés sur leur code source. Deux types de méthodes sont particulièrement connus, les méthodes de test et les méthodes d'analyses statiques. Dans les méthodes de test, il s'agit d'exécuter le programme sur un grand 20 nombre d'entrées. Comme il existe un nombre trop important d'entrées différentes, on en sélectionne une partie en espérant que cette partie est représentative de tous les comportements du programme. Ces méthodes ne peuvent donc donner qu'une confiance partielle dans le programme. Dans les méthodes d'analyses statiques, il s'agit d'étudier le code source 25 sans l'exécuter. Différentes méthodes d'analyse statique existent et apportent des garanties sur le comportement du programme pour toutes ses entrées. Ce problème n'a en général pas de solution : il fait partie de la classe des problèmes indécidables. Les méthodes existantes doivent donc procéder par approximations. Ces approximations peuvent être de deux 30 natures : soit elles permettent de donner un sous-ensemble ne comportant que des erreurs certaines, soit elles permettent de donner un sur-ensemble des erreurs potentielles. Dans le premier cas l'approximation a pour effet que certaines erreurs peuvent être omises. Dans le second cas, l'analyse peut indiquer des erreurs que le code source ne présente pas réellement. Dans le cadre de l'analyse d'un code critique on se place généralement dans la seconde famille d'approximations pour avoir la possibilité d'être certain qu'aucune erreur ne reste dans le programme source étudié. Par ailleurs, l'analyse statique repose sur une modélisation formelle du langage utilisé dans le programme source étudié. Cette modélisation peut ne pas prendre en compte certains aspects du langage pour des raisons techniques. A cause de ces choix dans la modélisation, une méthode donnée d'analyse statique peut être incapable de traiter certaines parties du programme source à étudier. Un but de l'invention est notamment de pallier les inconvénients précités, en permettant en particulier d'améliorer les méthodes d'analyses statiques. A cet effet, l'invention a pour objet un procédé et un système tels que définis par les revendications. D'autres caractéristiques et avantages de l'invention apparaîtront à l'aide de la description qui suit faite en regard de dessins annexés qui représentent : - la figure 1, une illustration du principe de fonctionnement d'une méthode d'analyses statiques pour la vérification d'un programme ; la figure 2, une illustration d'une phase de fonctionnement d'un système selon l'invention correspondant à l'émission d'une hypothèse par un analyseur, l'hypothèse portant sur la validité d'une propriété ; - la figure 3, une illustration d'une phase fonctionnement d'un système selon l'invention correspondant à la vérification des hypothèses émises ; - la figure 4, une illustration d'un exemple d'application. La figure 1 illustre le principe de fonctionnement d'un système mettant en oeuvre une méthode d'analyses statiques. Un ensemble d'analyseurs F1, Fk, B1, BI est afffecté à l'analyse de propriétés d'un programme informatique, au niveau de son code source 1. Deux types d'analyseurs sont utilisés, au moins un analyseur en avant F1, Fk et au moins un analyseur en arrière B1, BI. Un analyseur en avant F1, Fk débute avec l'état initial du programme 1 35 analysé et, par propagation en avant dans le graphe de flot de contrôle en partant d'un point d'entrée, calcule en des points du programme les états qui peuvent avoir lieu. Ce calcul est effectué en tenant compte notamment des effets des instructions de chaque étape et en réduisant les états propagés en présence de tests conditionnels, du type if , then ou else par exemple, dans le programme source. Cette réduction peut aussi se faire pour des opérations interdites détectées dans le code source du programme analysé. Dans ce cas, les résultats de l'analyseur reposent sur l'hypothèse que ces opérations interdites n'ont effectivement pas lieu. On dit que l'analyseur en avant émet une hypothèse. Cette émission d'une hypothèse peut révèler la limite de l'analyseur. Il est en effet dans l'impossibilité d'indiquer si une propriété P est vérifiée ou non en un point de programme Li. Un analyseur en arrière B1, BI travaille en partant d'une propriété donnée P et du point de programme Li auquel elle doit être vérifiée. L'analyseur parcourt le graphe de flot de contrôle dans le sens arrière, en calculant successivement en chaque point des conditions qui garantissent que les conditions associées au point précédent, successeur dans le graphe, sont établies. L'analyseur termine soit en rencontrant des instructions qui assurent que la propriété P au point Li du programme est vérifiée, soit quand il a atteint le point d'entrée du graphe de flot de contrôle. Dans ce dernier cas, les conditions restantes forment une précondition de la fonction et doivent être vérifiées. Ces préconditions qui restent à vérifier peuvent encore mettre en évidence la limite de l'analyseur, arrière cette fois-ci. Un analyseur F1 émet une hypothèse car il est limité, c'est-à-dire qu'il ne sait pas indiquer si cette hypothèse est vraie. Selon l'invention, tous les autres analyseurs F1, Fk, B1, BI sont mis à contribution pour analyser une hypothèse émise par un analyseur, qu'il soit en avant F1, Fk ou en arrière B1, BI. Parmi tous ces autres analyseurs, au moins un peut être en mesure d'indiquer si l'hypothèse est vraie ou fausse. L'invention permet ainsi d'exploiter au mieux les performances et ressources des analyseurs en présence. La figure 2 illustre une phase de fonctionnement d'un système selon l'invention dans le cas d'une émission d'une hypothèse par un analyseur. A titre d'exemple l'hypothèse est émise par un analyseur en avant. Elle pourrait aussi être émise par un analyseur en arrière. Le système comporte, outre les analyseurs F1, Fk, B1, BI un module centralisateur 21 et une base des hypothèses 22. Pendant cette phase, l'analyseur en avant F1 émet vers le module centralisateur 21 des hypothèses nécessaires à son fonctionnement. Le module centralisateur 21 stocke ces hypothèses dans la base des hypothèses 22 avec un statut précisant que ces hypothèses sont à vérifier. Pour indiquer ce statut, l'attribut à faire peut être affecté à chacune de ces hypothèses. Après avoir émis une hypothèse, l'analyseur en avant F1 continue son travail 1 o en admettant que cette hypothèse qu'il a émise est vérifiée. La vérification de cette hypothèse se fera dans une phase suivante de vérification. L'analyseur F1 peut émettre d'autres hypothèses qui suivront le même chemin, vers la base 22 via le module centralisateur 21. Dans une première étape (a), le code source 1 du programme dont on veut 15 vérifier le fonctionnement est fourni par une entité extérieure qui a décidé par ailleurs d'utiliser l'analyseur F1. Cette entité extérieure peut être un utilisateur ou tout autre moyen de décision, automatique ou non. Le code source comporte des points de programme L1, L2, Li, Lj à vérifier. Plus particulièrement, un analyseur analyse une propriété P à un point de 20 programme Lj. Une propriété P à un point de programme Lj pourra être notée par la suite P@ Lj. Dans l'exemple de la figure 2, dans une deuxième étape (b), pour analyser le code source au-delà du point de programme L2, l'analyseur F1 a besoin que la propriété P soit vraie au point L1 du code source. C'est-à-dire que P@ L1 25 est vraie, le point de programme L1 étant accessible à partir du point L2 dans le graphe de flot de contrôle du programme source étudié. Les points L1 et L2 peuvent éventuellement être égaux. L'analyseur F1 émet donc vers le module centralisateur 21 une hypothèse codée par exemple sous la forme F1 : P@ L1, L2. L'analyseur F1 exige que la propriété P soit vraie au point L1 30 sans reposer sur une hypothèse accessible à partir du point L2, L1 étant accessible à partir de L2 dans le graphe de flot de contrôle. Dans une troisième étape (c) le module centralisateur 21 stocke l'hypothèse F1 : P@ L1, L2 dans la base des hypothèses avec le statut à faire . Le module centralisateur 21 pourra par la suite reconnaître, pour l'hypothèse 35 ainsi stockée, son origine, l'analyseur F1, la propriété à vérifier P et les points de programme concernés, L1 et L2. La base des hypothèses comporte ainsi un ensemble d'hypothèses Bj : Pj@ Lj, Lj' à vérifier, c'est-à-dire ayant le statut à faire . La figure 3 illustre une phase suivante correspondant à la vérification des hypothèses qui sont marquées comme à faire dans la base des hypothèses 22. Un analyseur a émis une hypothèse car il est limité, en d'autres termes il n'a pas les moyens d'indiquer si cette hypothèse est vraie. Selon l'invention, tous les autres analyseurs F1, Fk, B1, BI sont mis à io contribution, qu'ils soient en avant ou en arrière, pour vérifier l'hypothèse par un processus de coopération. Une hypothèse est d'abord émise vers le module centralisateur 21 qui peut la ré-émettre vers d'autres analyseurs pour la vérifier. A titre d'exemple, la figure 3 illustre la vérification d'une hypothèse par un 15 analyseur en arrière B1, mais cette hypothèse pourrait être vérifiée par les autres analyseurs Fk, B1, BI. L'analyseur B1 va donc tenter de vérifier une hypothèse à faire stockée dans la base 22. S'il parvient à vérifier que l'hypothèse est vraie, cette dernière est marquée comme valide. Elle peut alors ne plus être remise en question. Pour vérifier cette hypothèse, 20 l'analyseur B1 peut être amené à poser des questions à d'autres analyseurs. Une question concerne par exemple la propriété P au point L1. La question est alors la suivante : est-ce que la propriété P est vérifiée au point L1 sans reposer sur une hypothèse faite à un point accessible à partir du point P2. La réponse peut être vraie, c'est-à-dire une réponse positive à la question. La 25 réponse peut aussi être ne sait pas , c'est-à-dire que l'analyseur interrogé ne sait pas répondre à la question. Cette question pourra être notée par la suite P@ L1, L2. Dans une première étape (a') l'analyseur B1 est, par exemple, utilisé pour vérifier la propriété Pk@ Lk sur laquelle reposent les résultats d'une certaine 30 analyse effectuée par un analyseur Fk en des points du code source accessibles à partir du point L2 et ayant le statut à faire dans la base des hypothèses 22. Dans une deuxième étape (b'), l'analyseur B1 peut éventuellement poser des questions au module centralisateur 21 sous la forme P@ L1, L2, c'est-à-dire 35 est-ce que la propriété P au point de programme L1 est vérifiée sans que la réponse à cette question repose sur une hypothèse marquée à faire dans la base des hypothèses 22 et attachée à un point accessible à partir du point L2. Dans une troisième étape (c'), le module centralisateur 21 utilise la base des hypothèses 22 pour déterminer quels analyseurs peuvent répondre à la question, c'est-à-dire sans reposer sur une hypothèse marquée à faire et attachée à un point accessible à partir du point L2. Par cette dernière exigence, le module centralisateur 21 assure la cohérence du processus de vérification. Il permet ainsi d'éviter l'utilisation dans la chaîne de vérification d'une hypothèse pour vérifier cette hypothèse elle-même. Le module centralisateur 21 n'interroge que les analyseurs dont il peut vérifier qu'ils n'utilisent pas cette hypothèse. La base des hypothèses permet cette vérification car il y a un lien entre chaque hypothèse et son analyseur d'origine, comme indiqué précédemment. Dans une quatrième étape (d') la base des hypothèses 22 renvoie au module centralisateur 21 un ensemble d'analyseurs { Fi, ... Fj } répondant à sa requête émise dans l'étape précédente (c'). Dans l'exemple de la figure 3, la base des hypothèses répond par le singleton { F1 }. Dans une cinquième étape (e') le rnodule centralisateur pose la question 20 P@ L1, L2 à l'analyseur F1. Dans une sixième étape (f') l'analyseur répond vrai ou ne sait pas au centralisateur. Dans une septième étape (g') le module centralisateur transmet cette réponse, vrai ou ne sait pas , à l'analyseur B1 qui peut s'en servir pour 25 continuer la vérification de l'hypothèse Pk. L'analyseur peut reposer une autre question et recommencer à l'étape (b'). Dans une dernière étape (h'), une fois que l'analyseur a vérifié la validité de l'hypothèse transmise dans la première étape (a'), il modifie son statut dans la base des hypothèses en remplaçant le statut à faire par le statut 30 valide . Le processus décrit pour l'analyseur B1 est itéré le cas échéant pour d'autres analyseurs. Le processus est achevé lorsque toutes les hypothèses de la base 22 sont validées, c'est-à-dire qu'elles sont toutes affectées du statut valide . Dans ce cas, toutes les hypothèses peuvent être considérées comme correctes et par conséquent le code source 1 peut être considéré comme répondant aux conditions de sûreté par exemple. Si au moins une hypothèse n'a pas pu être vérifiée par un analyseur F1, Fk, B1, BI elle reste affectée du statut à faire . Le code source 1 ne peut pas être considéré comme répondant aux conditions de sûreté. En d'autres termes, le système ne permet pas d'indiquer si le programme est valide ou non. En comparaison avec un système selon l'art antérieur, il y a néanmoins une grande amélioration de la perforrnance. En effet, par la collaboration des analyseurs et du module centralisateur l'invention réduit fortement le nombre d'hypothèses non vérifiées. Il n'y a pas nécessaire un ordre privilégié pour sélectionner un analyseur en vue de vérifier une hypothèse donnée. Dès qu'un analyseur a pu vérifié cette hypothèse, le processus est terminé pour cette hypothèse. Si un analyseur sélectionné ne sait pas répondre, un autre analyseur est sélectionné. La figure 4 illustre un exemple d'application. Dans cet exemple le code source 1 est en langage C. Le système comporte un seul analyseur en avant F1 et un seul analyseur en arrière B1. L'analyseur en avant F1 utilise un calcul d'intervalles de valeurs par interprétation abstraite avant. Ce calcul est notamment décrit dans le document Abstract interprétation : a unified lattice model for static analysis of programs by construction or approximation of fix points de Patrick et Radhia Cousot, in Proc. 4th ACM Symposium on Principles of Programming Language, pp 238-252, 1977. Ce calcul réduit les états du code source en cas d'opérations en langage C invalides et émet des hypothèses de type pointeur valide et diviseur non nul. Dans ce cas, l'analyseur F1 doit notamment vérifier les deux propriétés P1, P2 suivantes en des points déterminés Li du code source du programme : P1 : vérifier que le pointeur est valide, c'est-à-dire qu'il pointe une zone de mémoire disponible, autorisée à l'écriture et à la lecture ; 30 - P2 : vérifier que les diviseurs sont non nuls. Ce qui revient à assurer que pour le programme analysé, il n'existe pas dans ce programme de diviseurs nuls et des accès à des zones mémoires interdites, susceptibles d'interrompre Ne programme. L'analyseur en arrière B1 utilise un calcul par la méthode de plus faible 35 précondition notamment décrit dans le document Assigning meaning to programs de Robert W. Floyd in Mathematical Aspects of Computer Science, pp 19-32, 1967 ainsi que dans le document An axiomatic basis for computer programming de C. Antony et R. Hoare in Communications of the ACM, 12 : 576-580, 1969. Ce calcul permet de prouver, le cas échéant, que les alarmes sont factices et utilise les résultats de l'analyseur en avant F1 pour résoudre les questions dites d'aliasing , c'est-à-dire les problèmes de code ayant des alias. Le phénomène d'aliasing correspond notamment au fait d'utiliser deux noms pour une même zone mémoire. Une limitation de l'analyseur en avant F1 est qu'il ne sait pas analyser un 1 o code qui a des alias, cela en contrepartie d'une rapidité et d'une simplicité d'analyse. L'invention permet de faire collaborer l'analyseur en avant F1 avec l'analyseur en arrière B1 augmentant ainsi les performances de l'ensemble. 15 REVENDICATIONS 1. Procédé d'analyse du code source d'un programme informatique, la vérification portant sur la validité d'un ensemble de propriétés (P, Pk) en des points de programme (L1, L2, Li) au moyen d'au moins un analyseur en avant (F1, Fk) et un analyseur en arrière (B1, BI), caractérisé en ce qu'il comporte, pour chaque propriété (P) : - une phase d'émission dans laquelle un analyseur (F1) émet vers un module centralisateur (21) une hypothèse sur la validité de la propriété (P) en un point (L1) du programme, le module centralisateur (21) stockant l'hypothèse dans une base de données (22) avec un attribut (F1 : P@ L1, L2) indiquant au moins son analyseur d'origine (F1) et un statut indiquant que l'hypothèse est à vérifier ; une phase de vérification de l'hypothèse (F1 : P@ L1, L2), stockée dans la base de données (22), dans laquelle un analyseur de test (B1) est sélectionné pour analyser l'hypothèse en coopération avec les autres analyseurs (F1, Fk, BI), le module centralisateur (21) déterminant les analyseurs aptes à coopérer ; la phase de vérification étant itérée jusqu'à ce que toutes les hypothèses stockées dans la base (22) aient été analysées par au moins un analyseur de test, une hypothèse vérifiée étant marquée comme valide. 2. Procédé selon la revendication 1, caractérisé en ce qu'un analyseur est apte à coopérer si sa coopération ne repose pas sur l'utilisation de l'hypothèse elle-même. 3. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que, lorsque la coopération avec un analyseur ne permet pas de vérifier l'hypothèse (F1 : P @ L1, L2), le module centralisateur (21) sélectionne un autre analyseur. 4. Procédé selon la revendication 3, caractérisé en ce que le processus de sélection par le module centralisateur (21) est itéré jusqu'à ce qu'un analyseur puisse coopérer avec l'analyseur de test (B1) ou jusqu'à ce que tous les analyseurs aptes à coopérer aient été sélectionnés par le module centralisateur (21). 5. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que, lorsqu'un analyseur de test (B1) ne parvient pas à vérifier l'hypothèse, un autre analyseur est sélectionné. 6. Procédé selon la revendication 5, caractérisé en ce que le processus de sélection de l'analyseur de test est itéré jusqu'à ce qu'un analyseur de test puisse vérifier l'hypothèse ou jusqu'à ce que tous les analyseurs disponibles aient été sélectionnés. 10 7. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que dans la phase de vérification, un analyseur coopère avec l'analyseur de test (B1) en répondant à une question (P@ L1, L2) relative à la propriété (P) au point de programme (L1), l'analyseur de test 15 posant la question au module centralisateur (21). 8. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que l'analyseur de test (B1) demande si la propriété (P) au point de programme (L1) est vérifiée sans que la réponse à cette question 20 repose sur une hypothèse à vérifier dans la base (22), cette hypothèse étant attachée à un point accessible à partir d'un autre point du programme (L2). 9. Procédé selon l'une quelconque des revendications 7 ou 8, caractérisé en ce que le module centralisateur (21) pose la question (P@ L1, L2) à un 25 analyseur (F1) apte à coopérer et transmet la réponse à l'analyseur de test (B1) qui utilise cette réponse pour vérifier l'hypothèse (P). 10. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'un programme est considéré comme valide lorsque 30 toutes les hypothèses stockées dans la base (22) sont marquées comme valides. 11. Système de vérification du code source d'un programme informatique, la vérification portant sur la validité d'un ensemble de propriétés (P, Pk) en des 35 points de programme (L1, L2, Li), ledit système comportant au moins un5analyseur en avant (F1, Fk) et un analyseur en arrière (B1, BI), caractérisé en ce que comportant un module centralisateur (21) et une base de données (22), pour chaque propriété (P) : dans une phase d'émission un analyseur (F1) émet vers le module centralisateur (21) une hypothèse sur la validité d'une propriété (P) en un point (L1) du programme, le module centralisateur (21) stockant l'hypothèse dans une base de données (22) avec un attribut (F1 : L1, L2) indiquant au moins son analyseur d'origine (F1) et un statut indiquant que l'hypothèse est à vérifier ; - dans une phase de vérification de l'hypothèse (F1 : P @ L1, L2), stockée dans la base de données (22), un analyseur de test (B1) est sélectionné pour analyser l'hypothèse en coopération avec les autres analyseurs (F1, Fk, BI), le module centralisateur (21) déterminant les analyseurs aptes à coopérer ; la phase de vérification étant itérée jusqu'à ce que toutes les hypothèses stockées dans la base (22) aient été analysées par au moins un analyseur de test, une hypothèse vérifiée étant marquée comme valide. 12. Système selon la revendication 11, caractérisé en ce que le module 20 centralisateur (21) détermine qu'un analyseur est apte à coopérer si sa coopération ne repose pas sur l'utilisation de l'hypothèse elle-même. 13. Système selon l'une quelconque des revendications 11 ou 12, caractérisé en ce que, lorsque la coopération avec un analyseur ne permet 25 pas de vérifier l'hypothèse (F1 : P@ L1, L2), le module centralisateur (21) sélectionne un autre analyseur. 14. Système selon la revendication 13, caractérisé en ce que le module centralisateur (21) répète le processus de sélection jusqu'à ce qu'un 30 analyseur puisse coopérer avec l'analyseur de test (B1) ou jusqu'à ce que tous les analyseurs disponibles aient été sélectionnés par le module centralisateur (21). 15. Système selon l'une quelconque des revendications 11 à 14, caractérisé en ce que, lorsqu'un analyseur de test (B1) ne parvient pas à vérifier l'hypothèse, un autre analyseur est sélectionné. 16. Système selon la revendication 15, caractérisé en ce que le processus de sélection de l'analyseur de test est itéré jusqu'à ce qu'un analyseur de test puisse vérifier l'hypothèse ou jusqu'à ce que tous les analyseurs disponibles aient été sélectionnés. io 17. Système selon l'une quelconque des revendications 11 à 16, caractérisé en ce qu'il comporte un analyseur en avant (F1) utilisant un calcul d'intervalles de valeurs par interprétation abstraite avant et un analyseur en arrière (B1) utilisant un calcul par la méthode de plus faible précondition. 15 18. Système selon la revendication 17, caractérisé en ce qu'il vérifie au moins les deux propriétés P1, P2 suivantes en des points déterminés du code source du programme : P1 : vérifier que le pointeur est valide, c'est-à-dire qu'il pointe une zone de mémoire disponible, autorisée à l'écriture et à la lecture ; 20 - P2 : vérifier que les diviseurs sont non nuls. 19. Système selon l'une quelconque des revendications précédentes, caractérisé en ce qu'un programme est considéré comme valide lorsque toutes les hypothèses stockées dans la base (22) sont marquées comme 25 valides. 30