Brevet FR2700031A1 — publié le 19940701

PROCEDE DE DETECTION DES ERREURS D'EXECUTION D'UN LOGICIEL La présente invention concerne un procédé de détection des erreurs d'exécution d'un logiciel et s'applique notamment, mais de manière non limitative, à la détection en cours de fonctionnement des erreurs d'exécution de logiciels industriels de gestion ou de contrôle de réseaux, tels que des réseaux ferroviaires, des réseaux de télécommunications, ou de logiciels d'aide au pilotage dans des avions par10 exemple. De manière schématique, un logiciel peut être représenté par un ensemble d'instructions élémentaires constituant les sommets d'un graphe et reliées entre elles par des branchements constituant les arcs du graphe Ces15 instructions peuvent être: des opérations (addition, soustraction, multiplication, division, ET logique, noté A, OU logique, noté v, OU exclusif noté O, etc) mettant en jeu un opérateur, noté T, et plusieurs opérandes, deux par exemple notés x et y,20 les opérandes étant constitués soit de données d'entrée du logiciel considéré, soit de résultats obtenus par exécution d'autres instructions du logiciel; l'opérateur T appliqué aux opérandes x et y met à jour le contenu d'une variable, notée r, en lui affectant la valeur x Ty,25 des tests conditionnels du type "if EXPR then else ", o EXPR est de manière générale une condition du type "x > O ?" ou "x = constante ?", des instructions de branchements inconditionnels appelées instructions de destination, du type "goto" ou "stop". Le modèle précédent permet de représenter schématiquement tous les types de logiciels écrits au moyen de langages séquentiels courants. Selon le schéma de représentation précédent, chaque exécution d'un logiciel correspond à un parcours ou chemin particulier dans le graphe représentant le logiciel, ce chemin dépendant des résultats des opérations et de ceux des tests conditionnels en fonction des valeurs particulières prises par les variables au cours de l'exécution concernée. En outre, chaque parcours autorisé dans le graphe, c'est-à- dire correspondant à une suite possible d'instructions reliées entre elles par des branchements, est appelé chemin licite. En généralisant la présentation précédente, on peut remplacer chaque instruction d'opération par une suite d'instructions d'opération, cette suite étant dénommée bloc10 et présentant un unique point d'entrée et un unique point de sortie. Pour qu'un chemin exécuté soit considéré comme sans erreurs, c'est-à- dire pour que son résultat soit considéré comme exact, il faut que les conditions suivantes soient15 réunies: la suite des instructions exécutées (chemin exécuté) correspond à un chemin licite dans le graphe, c'est-à-dire qu'aucune instruction n'a été ajoutée ou supprimée par rapport à ce qui était prévu à la compilation,20 pour les instructions de test, le choix de l'instruction suivante est correct en fonction du résultat du test exécuté, et pour les instructions de destination, l'instruction suivante est bien celle prévue (on dit alors que le chemin exécuté est correct),25 chaque instruction d'opération est effectuée en utilisant l'opérateur prévu (dans le cas contraire, on dit qu'il y a une erreur opératoire), les opérandes utilisés au sein des instructions d'opérations et de test sont ceux attendus (dans le cas contraire, on dit qu'il y a une erreur de dépendance). Si le chemin exécuté n'est pas licite ou n'est pas correct, on dit qu'il y a une erreur de flot d'exécution. Dans de nombreux cas pratiques, étant donné que la probabilité d'occurrence d'erreurs d'exécution n'est pas négligeable, on utilise une méthode dite de réplication, faisant appel au principe de la redondance Au lieu d'implanter un seul logiciel au sein d'un système, on en implante R exemplaires identiques appelés répliques Le résultat final d'une exécution des R répliques, auxquelles ont été fournies les mêmes données d'entrée, est sélectionné5 comme étant le résultat obtenu par un nombre prédéterminé de ces répliques, en général la majorité Cette méthode de sélection est alors appelée vote majoritaire, et le résultat sélectionné par le vote est considéré comme exact. La réplication peut également consister à exécuter R fois séquentiellement le logiciel, et à sélectionner le résultat considéré comme exact de la même manière que précédemment, une fois les R exécutions terminées. La méthode qui vient d'être exposée, appelée réplication, est fiable, c'est-à-dire qu'elle permet de poursuivre l'exécution même si une ou plusieurs répliques sont défaillantes, à condition que la majorité des répliques ne soit pas affectée d'une même erreur. Si la majorité des répliques est affectée d'une même erreur (on est alors en présence d'une erreur dite générique), cette erreur n'est pas détectable On dit pour cela que la réplication n'est pas une méthode sécuritaire. Les erreurs génériques peuvent être dues par exemple à un défaut du matériel utilisé, à une erreur du compilateur lors de la réplication, à l'influence d'un rayonnement25 électromagnétique, etc On comprend bien que le fait qu'une telle erreur soit indétectable est préjudiciable au bon fonctionnement de l'installation et peut même s'avérer dangereux lorsque le logiciel considéré est un logiciel de contrôle du trafic ferroviaire ou d'aide au pilotage par30 exemple. On connaît par ailleurs une méthode sécuritaire, appelée méthode par processeur codé ou plus simplement processeur codé, qui consiste à coder, au sein du logiciel à contrôler lui-même, les variables intervenant dans chaque35 instruction par une transformation prédéterminée Si l'instruction est exécutée correctement, le résultat obtenu après exécution présente une cohérence attendue, c'est-à-dire qu'il peut être décodé au moyen d'une fonction prédéterminée et prévisible De plus, le codage effectué est tel que seule l'instruction prévue pour être la suivante est5 capable de décoder le résultat obtenu et par conséquent de permettre la poursuite de l'exécution. En pratique, le codage des variables effectué permet d'obtenir après exécution de chaque instruction un code numérique d'o l'on peut extraire notamment:10 le résultat correspondant à l'exécution de l'instruction sur les variables non codées, une valeur numérique représentant l'opération qui a été effectuée par l'instruction concernée ainsi que le numéro d'ordre de cette instruction dans la suite des instructions15 exécutées, une valeur numérique destinée à vérifier la cohérence du résultat obtenu. Le processeur codé est donc complexe et surtout coûteux en temps de calcul, car le codage qui y est effectué allonge sensiblement la durée d'exécution de chaque instruction, ce qui pénalise l'exécution du logiciel à contrôler. De plus, le processeur codé n'est pas une méthode fiable, puisqu'il n'est pas possible de poursuivre l'exécution une fois qu'une erreur a été détectée. Le but de la présente invention est donc de mettre au point un procédé de détection des erreurs d'exécution d'un logiciel à la fois fiable et sécuritaire. La présente invention propose à cet effet un procédé de détection des erreurs d'exécution d'un logiciel répliqué, c'est-à-dire dont plusieurs répliques identiques, auxquelles sont fournies les mêmes données d'entrée, sont exécutées en parallèle ou séquentiellement, ledit logiciel comprenant des instructions reliées entre elles par des branchements et35 constituées: soit d'opérations mettant en jeu un opérateur, dit simple, agissant sur des opérandes, dits simples, afin de mettre à jour le contenu d'une variable, lesdits opérandes étant constitués soit de données d'entrée, soit de résultats obtenus par exécution d'autres instructions,5 soit de tests conditionnels dont le résultat sert à déterminer l'instruction suivante à exécuter, soit d'indications de destination donnant directement l'instruction suivante à exécuter, ledit procédé étant caractérisé en ce que chacune desdites10 instructions d'opération, au sein de chaque réplique, est remplacée par plusieurs instructions dites de détection d'erreur permettant d'effectuer successivement: le codage préalable des opérandes mis en jeu dans ladite instruction d'opération et constitués de données d'entrée, au moyen d'une injection dite de codage spécifique de ladite instruction d'opération, pour obtenir des données d'entrée dites codées images desdites données d'entrée simples par ladite injection, chaque injection de codage, associée à l'une desdites répliques et à une instruction d'opération20 donnée au sein de cette réplique, étant distincte des injections de codage associées à toutes les autres instructions d'opération au sein de toutes les autres répliques, la transformation dudit opérateur simple associé à ladite instruction d'opération, de sorte que l'opérateur appliqué aux opérandes, codés, de ladite instruction résulte de la transformation dudit opérateur simple, les transformations correspondant à des opérateurs identiques au sein des différentes répliques étant deux à deux distinctes,30 le transcodage du résultat obtenu par application dudit opérateur transformé auxdits opérandes codés, pour obtenir un résultat dit transcodé sous la forme d'un opérande codé au moyen du codage spécifique de l'instruction d'opération destinée à utiliser ledit résultat, ledit transcodage étant35 effectué au moyen d'une transformation dite de transcodage, chaque transformation de transcodage, associée à l'une desdites répliques et à une instruction d'opération donnée au sein de cette réplique étant distincte des transformations de transcodage associées à toutes les autres instructions d'opération au sein de toutes les autres 5 répliques, ledit procédé étant en outre caractérisé en ce qu'il comprend une opération finale de décodage du résultat, dit final, obtenu en fin d'exécution de chaque réplique, au moyen de l'inverse d'une injection dite de décodage, chaque10 injection de décodage, spécifique de l'une desdites répliques, étant distincte des injections de décodage des autres répliques, et en ce qu'il indique qu'une erreur d'exécution s'est produite si, pour certaines desdites répliques, ledit résultat final ne peut être décodé au moyen15 de ladite injection inverse correspondante, et si, parmi les résultats finaux décodés des autres répliques, il n'en existe pas un, éventuellement appelé alors résultat final sélectionné, qui est obtenu par un nombre minimum prédéterminé desdites autres répliques.20 Grâce à l'invention, les différentes répliques sont dotées de comportements différents lors de l'activation d'une même erreur, ce qui permet de détecter l'occurrence d'une erreur générique En effet, une même information est élaborée plusieurs fois sous des formes différentes ou approchées Ainsi, une incohérence entre les différentes formes d'une même information révèle une erreur dans son processus d'élaboration. Le procédé selon l'invention est à la fois sécuritaire et fiable, puisqu'il utilise un principe de codage permettant de vérifier la cohérence de tout résultat obtenu, et donc de tenir compte des erreurs génériques éventuelles, et puisque même si une majorité des répliques est affectée d'une erreur générique, ces dernières ne sont pas prises en compte pour sélectionner le résultat final considéré comme35 exact. La fonction de transformation de chaque opérateur peut être composée avec la fonction de transcodage de l'opération précédente pour constituer une seule fonction Ceci permet de diminuer la durée d'exécution de ces deux5 transformations. De manière avantageuse, le procédé selon l'invention peut consister en outre à: déterminer, lors de la compilation de chaque réplique, une donnée de référence, appelée signature de référence, pour chaque parcours autorisé au sein de cette réplique, par combinaison de constantes numériques appelées identifiants élémentaires prédéterminés et associés à chaque instruction de test et à chaque instruction de destination, les signatures de référence étant mises en mémoire,15 calculer, au moyen d'instructions supplémentaires insérées au sein de chaque réplique, la valeur d'une variable, appelée signature courante, représentative de la suite des instructions de test et de destination effectuées lors de l'exécution, par combinaison de valeurs numériques appelées20 identifiants élémentaires d'exécution et associées à chacune des instructions de destination et de test exécutées, les combinaisons effectuées au sein d'une même réplique pour la détermination et pour le calcul respectivement des signatures de référence et courante étant identiques, et25 distinctes deux à deux d'une réplique à l'autre au moyen d'un paramétrage adapté. Lorsqu'il existe un résultat final sélectionné comme étant obtenu par un nombre prédéterminé des répliques restantes, les signatures courantes des répliques ayant fourni ce résultat sont comparées aux signatures de référence correspondantes, et si elles ne sont pas toutes égales à une signature de référence de la réplique correspondante, le procédé selon l'invention consiste à indiquer qu'une erreur d'exécution s'est produite. 35 Le perfectionnement précédent offre une sécurité supplémentaire qui permet d'accroître la détectabilité d'une erreur générique En effet, l'utilisation d'un paramétrage différent pour le calcul de signature de chaque réplique permet de détecter la présence d'une erreur générique qui n'aurait pu être détectée par un simple codage-décodage.5 De manière très avantageuse, pour une instruction d'opération suivant une instruction de test, la transformation associée à l'opérateur correspondant est fonction de la différence entre les signatures courante et de référence partielles du parcours exécuté jusqu'à cette10 instruction de test. Selon un mode de mise en oeuvre possible, les injections de codage sont des fonctions affines dont l'ordonnée à l'origine et la pente sont différentes d'une réplique à l'autre Ce mode de mise en oeuvre présente15 l'avantage d'être particulièrement simple, et notamment d'être beaucoup plus simple que la méthode de codage utilisée dans les processeurs codés. Il n'est en effet pas nécessaire, selon l'invention, d'avoir recours à un codage aussi complexe que celui du processeur codé, puisque l'on utilise en parallèle la réplication Ainsi l'on peut se servir d'un codage qui à lui seul serait insuffisant pour permettre la détection d'erreur au sein d'un processeur codé, mais qui en combinaison avec la réplication permet d'obtenir une probabilité de détection25 d'erreurs voisine de celle obtenue avec les processeurs codés connus. Lorsque l'opération est une addition ou une soustraction, l'opérateur transformé correspondant est respectivement une addition ou une soustraction,30 c'est-à-dire que la transformation utilisée pour transformer l'opérateur est l'identité Ici encore, le mode de codage est particulièrement simple. Le procédé selon l'invention est donc moins complexe et moins coûteux en temps de calcul que le processeur codé. Pour déterminer ou calculer les signatures de référence ou courantes, on additionne les représentations binaires des identifiants élémentaires en les ayant préalablement multipliées chacune par une puissance de deux choisie arbitrairement, cette puissance de deux étant fonction du numéro d'ordre de l'instruction correspondante5 et les ensembles de puissances de deux utilisés au sein de chaque réplique étant deux à deux distincts. L'identifiant élémentaire d'exécution d'une instruction de test est fonction de la variable faisant l'objet de la condition de cette instruction de test et de10 constantes prédéterminées, de sorte que, si l'instruction à laquelle correspond l'identifiant est exécutée correctement, il est égal à l'identifiant élémentaire prédéterminé affecté à cette instruction. La variable faisant l'objet de la condition de l'instruction de test peut être codée au moyen d'un codage spécifique fonction de la variable prévue pour le test avant d'être utilisée pour calculer l'identifiant élémentaire d'exécution de l'instruction correspondante de sorte que, si la variable effectivement utilisée lors du test n'est pas20 celle attendue, l'identifiant élémentaire d'exécution de l'instruction de test correspondante est altéré et l'erreur est donc détectable. Enfin, les identifiants élémentaires d'exécution des instructions de destination sont calculés par une instruction supplémentaire suivant chaque instruction de destination et affectant à l'identifiant élémentaire d'exécution une constante prédéterminée égale à l'identifiant élémentaire prédéterminé correspondant. D'autres caractéristiques et avantages du procédé selon la présente invention apparaîtront dans la description suivante d'un mode de mise en oeuvre particulier de ce procédé, donné à titre illustratif et nullement limitatif. Dans tout ce qui suit, on prendra l'exemple d'un logiciel simple écrit ci- dessous Ce logiciel comprend tous les types d'instructions mentionnés plus haut. r 1 = xj Tjyj 1 label ri = xi Tiyi i rj = xj Tjyj i if xk > O then k goto label else rl = xj Tjyl 1 endif stop Les variables notées r sont les résultats des instructions d'opération, numérotées 1, i, j et 1 Les opérandes de ces opérations sont notés x et y, et les opérateurs, supposés binaires pour des raisons de clarté, sont notés T Les indices représentent le numéro de20 l'opération ou de l'instruction considérée. Le logiciel écrit ci-dessus est répliqué au sein du système dans lequel il est implanté, de sorte que ce système comporte R répliques qui sont exécutées en parallèle par R processeurs, et auxquelles sont fournies les mêmes données25 d'entrée Selon un autre modèle d'implantation, la réplication peut prendre la forme de R exécutions séquentielles du logiciel concerné. En général, du fait de la fiabilité apportée par la réplication du logiciel, seule une détection des erreurs opératoires ou de dépendance suffit On commencera donc par présenter le procédé permettant de détecter les erreurs d'exécution en contrôlant les opérations effectuées et les opérandes utilisés au cours de ces opérations. On décrira ensuite un perfectionnement du procédé selon l'invention dans lequel on contrôle en outre le flot d'exécution afin de détecter les erreurs d'exécution. il Le procédé selon l'invention repose en premier lieu sur le principe du codage des opérateurs et des opérandes intervenant dans l'exécution du logiciel à contrôler (et de ses répliques) Selon l'invention, des instructions dites de5 détection d'erreur remplacent les instructions d'opération. Ces instructions sont de plusieurs types des instructions de codage des opérandes constitués de données d'entrée et mis en jeu au sein de chaque instruction d'opération, ce codage étant spécifique à l'instruction10 d'opération considérée, des instructions de transformation des opérateurs utilisés dans chaque instruction d'opération, des instructions dites de transcodage, pour coder le résultat obtenu par application d'un opérateur transformé à des opérandes codés au moyen du codage spécifique à une autre instruction d'opération ultérieure devant utiliser ce résultat, une instruction finale de décodage du résultat final codé de l'exécution. Les instructions précédentes font intervenir des fonctions permettant d'effectuer les codages, transcodages, transformations, et décodage final nécessaires. Ainsi par exemple, les instructions de codage utilisent des injections, afin qu'il soit possible, en appliquant l'injection inverse, de retrouver l'opérande initial. Les instructions de transformation appliquent aux opérandes modifiés un opérateur transformé, fonction de l'opérateur prévu au sein du logiciel initial.30 Les fonctions de transcodage sont en pratique obtenues par composition d'une fonction de décodage dépendant du codage spécifique de l'opération ayant produit le résultat considéré, et d'une fonction de codage spécifique à l'opération destinée à utiliser ce résultat.35 Enfin, l'instruction de décodage applique au résultat final de l'exécution ainsi effectuée l'inverse d'une injection qui doit permettre de retrouver, si aucune erreur ne s'est produite, le résultat qui aurait été obtenu en appliquant les opérateurs initiaux aux opérandes initiaux. Ainsi, l'injection inverse de décodage utilisée dépend des5 opérateurs prévus, de sorte que si un opérateur erroné est transformé puis appliqué aux opérandes codés (erreur opératoire), le décodage du résultat final n'est pas possible, ce qui permet de déduire que ce résultat n'est pas exact.10 Le schéma général du codage-transcodage-décodage est alors le suivant, pour un logiciel très simplifié constitué de deux instructions d'opération dont les opérateurs sont respectivement gl puis g 2, dont l'entrée est x et la sortie (résultat final) y tel que y = g 2 og 1 (x), o o représente la composition des opérateurs: x y L'injection u apporte à x dans X 1 = u(x) une cohérence informationnelle (appartenance à un code), et v-1, inverse de l'injection v, peut extraire y de Y 2 si Y 2 possède la cohérence attendue G 1 et G 2 sont des fonctions des opérateurs g 1 et g 2 respectivement, et T 1 est une transformation de transcodage permettant de transformer Y 1,25 possédant la cohérence correspondant à gl, c'est-à-dire codé au moyen du codage spécifique à l'opération dont l'opérateur est gl, en X 2, possédant la cohérence correspondant à g 2. G 1, G 2 et T 1 sont telles que l'on peut extraire de Y 2 le résultat y = g 2 og 1 (x) Si aucune erreur opératoire ou de30 dépendance ne s'est produite, G 1 transforme la cohérence de X 1 en une cohérence pour Y 1, T 1 la cohérence de Y 1 en une cohérence pour X 2 et G 2 la cohérence de X 2 en une cohérence pour Y 2. On peut comparer le codage-transcodage-décodage précédent à un processus de traduction: u traduit x d'une langue 1 à une langue L, parlée par G 1, T 1 traduit Y 1 de Ll à une langue L 2 parlée par G 2, et v-1 traduit Y 2 de L 2 à la langue 1 qui est celle du résultat final décodé Si une erreur de dépendance ou une erreur opératoire se produit, on5 effectue une traduction dans une langue 1 ' qui n'est pas celle attendue Le résultat final ne sera donc pas dans la langue attendue, c'est-à-dire n'aura pas la cohérence attendue,ce qui permettra de signaler une erreur au niveau de la réplique concernée.10 En pratique, il est possible d'effectuer en même temps les opérations de transformation de l'opérateur et de transcodage en remplaçant les deux instructions de détection d'erreur correspondantes par une seule, cette instruction unique étant constituée d'une fonction égale à la composée15 de la fonction de transcodage par celle de transformation de l'opérateur Ainsi, par exemple, la fonction de transformation de l'opérateur d'une instruction effectue également et simultanément le transcodage du résultat d'une instruction précédente, soit le transcodage associé à l'instruction précédente, si l'un de ses opérandes est égal à ce résultat On a donc ainsi une succession d'instructions d'opérations (bloc) transformant automatiquement le résultat de l'opération précédente dans un langage compréhensible par l'opération suivante, et l'on procède au décodage uniquement25 à la fin de l'exécution, lorsque l'on souhaite connaître le résultat final de cette dernière. Par conséquent, dans ce dernier cas, tout opérateur transformé maintient par son exécution correcte une cohérence, de sorte que la variable qu'il produit est30 consommable par son "successeur". Pour prendre un exemple de mise en oeuvre concret, une instruction de la forme z = x + y est remplacée par les instructions suivantes (l'indice r représente le paramétrage en fonction de la réplique considérée)35 Xr = Xr X + gr Yr = Xrx + Pr Zr = Xr + Yr z = (Zr gr Pr)/Xr, O Xr, gr, et Pr sont des constantes choisies arbitrairement Dans l'exemple précédent, les injections de 5 codage sont des fonctions affines des opérandes, la transformation de l'opérateur est l'identité, puisque l'on fait la somme des opérandes codés, et le décodage est effectué simplement par résolution de l'équation faisant intervenir z et Zr Le transcodage permet de faire passer10 directement de Zr à Z'r compréhensible par l'instruction d'opération ultérieure devant en principe utiliser z. Le tableau cidessous montre un exemple possible des codages (ur), transformations des opérateurs (Gr), et enfin décodages (vr) utilisés en relation avec les opérations15 d'addition, de soustraction, de multiplication et de division (l'indice r correspond au numéro de la réplique considérée). On comprend bien d'après le tableau précédent que les codages, transformations et décodages effectués selon le procédé de l'invention sont très simples, et donc peu coûteux en temps de calcul Ils pénalisent donc peu l'exécution du logiciel à contrôler.25 Cette grande simplicité est rendue possible par le fait que le codage- transcodage-décodage des opérations est couplé avec la méthode de réplication qui permet d'utiliser Opération ur Gr vr Z = x+y Xr = Xr X + gr Zr = rxr + Yr -+ rr r Zr r Z+r z I r 8 rIr sr Zr = Olr Z+ar Yr = Dr Y + Pr z = x-y Xr = Xr X + Fr Z Xr =r Yr crgr + rr + r = ar Z+r Yr = br Y + Pr z = x y Xr = Xr X + r Yr Zr"_r X Yr rr r+ lrv&r+ rr rr Xrr rr Zr = ar Z+Ir Yr = Zr Y + Or z = xy Xrrr Yr= rx +r Vr r Xrryrarsrr + r z = x/y Xr = a/r + Pr Z rvr = r Vr r rvr Zr = ar Z+ar Yr = _r Y + _r pour chaque réplique et pour chaque instruction des fonctions (injections de codage et de décodage, transformations) distinctes. En effet, puisque l'on se trouve dans un contexte répliqué, il faut effectuer une détection d'erreur qui n'est pas sensible au point faible de la réplication, c'est-à-dire les erreurs génériques Ceci est possible en définissant, pour chaque instruction d'opération, un ensemble de fonctions ur, Gr et Vr paramétré en fonction de la réplique10 concernée. Chaque fonction de codage, de transcodage et de transformation d'opérateur est distincte des fonctions associées aux instructions correspondantes et à toutes les autres instructions au sein de toute les autres répliques.15 Ainsi, lorsqu'une même faute affecte les différentes répliques, ces dernières présentent des comportements erronés distincts, ce qui permet d'éviter de considérer comme exact un résultat qui ne l'est pas. Grâce à l'invention, même si une même erreur affecte la majorité des répliques (ou un nombre prédéterminé d'entre elles lorsque le vote ne se fait pas à la majorité), elle a une probabilité très faible de produire un résultat final cohérent (c'est-à-dire qui peut être décodé par une injection inverse préétablie) pour chacune de ces répliques.25 En éliminant les résultats fournis par les répliques pour lesquelles une incohérence a été détectée, et en sélectionnant comme résultat "exact" celui qui est obtenu par la majorité ou par un nombre prédéterminé des répliques restantes, on a donc mis au point un procédé fiable et30 sécuritaire qui permet d'indiquer qu'une erreur d'exécution s'est produite lorsque, une fois les répliques ayant fourni un résultat incohérent éliminées, aucun résultat n'est obtenu par un nombre prédéterminé des répliques restantes. Selon un perfectionnement important de la présente invention, on effectue, en plusdu codage-transcodage- décodage présenté ci-dessus, un calcul de signature pour vérifier que le chemin emprunté dans le graphe est un chemin correct, c'est-à-dire que le chemin emprunté après chaque instruction de test est cohérent avec le résultat du test effectué.5 Pour cela, dans un premier temps, on insère dans le logiciel tel que présenté ci-dessus des instructions spécifiques, dites supplémentaires, permettant de calculer une variable numérique, appelée identifiant élémentaire d'exécution, représentant chaque instruction de test ou de10 destination effectivement exécutée, après exécution de cette dernière Cette méthode n'introduit pas de branchement supplémentaire au sein du logiciel. Plus précisément, lors de la compilation du logiciel précédent, chaque instruction de test ou de destination est associée à une donnée numérique (un nombre entier par exemple) appelée identifiant élémentaire prédéterminé. Ainsi, l'instruction k du logiciel précédemment décrit est associée à deux identifiants notés Ithen,p et Ielsepi le premier de ces identifiants correspondant à une réponse20 positive au test "Ixk > O ?", et le second à une réponse négative. En outre, les instructions de destination "goto"l et "stop" sont également associées à des identifiants notés respectivement Igoto et 1stop. Les valeurs de tous les identifiants élémentaires prédéterminés sont en général choisies arbitrairement, chaque type d'instruction étant associé à un identifiant élémentaire distinct. Pour détecter d'éventuelles erreurs, il faut pouvoir effectuer une comparaison entre des données de référence et des variables calculées lors de l'exécution Les identifiants élémentaires d'exécution doivent donc être identiques, s'il n'y a pas d'erreur d'exécution, à ceux définis lors de la compilation.35 Les identifiants élémentaires d'exécution des instructions de destination sont déterminés arbitrairement: on leur affecte, dans une instruction supplémentaire suivant l'instruction de destination considérée, la valeur de l'identifiant élémentaire prédéterminé de la compilation pour l'instruction correspondante.5 Pour ce qui est du calcul des identifiants élémentaires d'exécution des instructions de test, le procédé selon l'invention propose une méthode simple que l'on va exposer à présent. N'importe quel test peut se ramener à une ou plusieurs conditions de la forme "x > O ?" ou "x = c ?", o c est une constante et x la variable à tester Le raisonnement est identique pour les entiers ou pour les décimaux flottants. On présentera donc la méthode sur des entiers, par souci de clarté.15 Dans le cas o la condition est " x > O ?", si l'on pose Xr = arx + br, en choisissant ar > br ' 0, Xr est toujours du même signe que x. On sait par ailleurs que si x X > O (unsgd)Xr = ( 2 m + br) mod ar <> x Si l'on pose à la compilation Ithen,p égal à A et Ielse,p égal à B, A et B étant des constantes arbitrairement choisies, et si l'on calcule les identifiants correspondants à l'exécution (notés respectivement Ithen,ex et Ielse,ex) selon les formules: Ithen,ex = ((unsgd)Xr mod ar) O (br mod ar) O A Ielse,ex = ((unsgd)Xr mod ar) (( 2 m + br) mod ar) O B, les identifiants élémentaires d'exécution sont bien égaux aux identifiants élémentaires prédéterminés si le chemin exécuté est correct et si l'on a pris soin de respecter la35 condition: ( 2 m + br) mod ar t br mod ar. En effet, dans le cas du logiciel pris comme exemple, si la réponse au test l"xk > O ?" est positive (c'est-à-dire que xk est positif ou nul) et que le logiciel exécute ensuite l'instruction 1, l'identifiant calculé et pris en5 compte dans la signature courante n'est pas celui attendu. On détecte ainsi une erreur de branchement, c'est-à-dire que le chemin exécuté, bien que licite, n'est pas correct. Par ailleurs, dans le cas o la condition à vérifier est "x = c ?", on pose Cr = circ + c 2 r On suppose par ailleurs que Xr-Cr est codé au moyen de constantes a'r et b'r telles que a'r > b'r _> O, de sorte que Xr-Cr est du même signe que x-c. De même que précédemment, on pose à la compilation Ithenp égal à A et Ielsep égal à B, et l'on calcule Ithen,ex et Ielseex selon les formules suivantes Ithenex = Xr e Cr e A Ielse,ex = (((unsgd)(Xr-Cr) mod a'r) O ((unsgd)(Cr-Xr) mod a'r)) O ((b'r mod a'r) + " 2 m + b'r) mod a'r)) O B. Dans tous les cas, si la condition: Cr t (b'r mod a'r) + (( 2 m + b'r) mod a'r) est vérifiée, l'expression utilisée pour calculer l'identifiant élémentaire d'exécution de l'instruction de test donne un résultat qui indique si la branche suivie lors de l'exécution est cohérente avec le résultat du test de25 l'instruction. La méthode précédente de détermination des identifiants élémentaires d'exécution, utilisant des variables codées, permet de détecter non seulement des erreurs de branchement, mais également des erreurs sur la30 variable de test effectivement utilisée Ainsi, l'utilisation d'une variable qui n'est pas codée au moyen d'un codage attendu altère de manière détectable l'identifiant élémentaire d'exécution correspondant. Toujours selon l'invention, on procède, dans un deuxième temps, à l'aide des identifiants élémentaires d'exécution calculés comme indiqué précédemment, au calcul d'une variable, appelée signature courante du chemin exécuté La signature courante est un nombre entier représentatif du chemin exécuté Cette signature courante, notée Scr, est obtenue, selon l'invention, en faisant la 5 somme bit à bit et modulo 2 des représentations binaires des identifiants élémentaires d'exécution calculés. Toutefois, une simple somme entraîne une perte d'informations importante, puisqu'elle compacte l'information Par conséquent, de nombreux chemins exécutés10 risquent d'avoir la même signature courante, ce qui ne permet pas de détecter les erreurs d'exécution de manière fiable. La présente invention propose donc en outre de multiplier préalablement la représentation binaire de chaque identifiant élémentaire d'exécution par une puissance de deux, ce qui revient à effectuer un décalage des bits de cette dernière On choisit donc une suite arbitraire d'entiers naturels paramétrée en fonction de la réplique considérée (drlil)i=l,N (r représente la réplique), et si20 l'on note Ii (i variant de 1 à N) les identifiants élémentaires d'exécution des instructions de destination ou de test d'un chemin exécuté, ce chemin comptant N instructions, on a: N dr E l Scr = 2 I i 1 = 1 En pratique, on peut éventuellement munir la signature courante d'un "compteur" incrémenté de 1 après chaque instruction exécutée Ceci permet de connaître le numéro d'ordre de chaque instruction exécutée afin d'affecter à l'identifiant élémentaire d'exécution de cette instruction30 le décalage correspondant Après chaque instruction exécutée, la valeur de Sc est modifiée en lui ajoutant l'identifiant de cette instruction multiplié par la puissance de deux correspondante et par une puissance de deux constante, notée 2 D, qui permet de séparer dans la35 représentation binaire de la signature courante calculée la partie correspondant à la signature courante de la partie compteur On a donc en fait, à la fin de l'exécution: Scr = N 2 rl I i i= 1 Il n'est toutefois pas essentiel d'insérer le compteur au sein de la signature courante Toute autre méthode de comptage des instructions exécutées peut être employée. On va maintenant décrire en détail un exemple d'instructions supplémentaires permettant la mise en oeuvre selon le procédé de l'invention, du calcul de signature.10 Une instruction de destination est simplement suivie de l'instruction: Scr = ( 1 + S Cr) $ 2 drlScr A Mcptl+D Idest o Mcpt est tel que combiné par un ET logique à Scr, il permet d'extraire seulement la partie compteur de Scr, et o15 Idest est l'identifiant élémentaire prédéterminé de l'instruction de destination correspondante. Dans le cas d'une instruction de test du type "x > O ?", l'instruction "then" est suivie de l'instruction: Scr = ( 1 + Scr) $ 2 drlScr A Mcptl+D Ithen,ex, et l'instruction "else" est suivie de l'instruction: Scr = ( 1 + Scr) $ 2 drlscr A Mcptl+D Ielse,ex. Les deux instructions supplémentaires précédentes sont adaptées simplement en remplaçant les identifiants par ceux décrits plus haut dans le cas o le test est du type x = c ?" D'après ce qui précède, le logiciel pris comme exemple peut être modifié de la manière suivante pour permettre le calcul de la signature: S Cr = O r 1 = Xltly 1 label ri =xiti Yi rj =xjtjyj if xk > O then Scr = ( 1 + S Cr) e 2 drlScr A Mcptl+D Ithen,ex goto label Scr = ( 1 + S Cr) @ 2 drlScr A Mcptl+D Igoto else S Cr = ( 1 + S Cr) O 2 drlScr A Mcptl+D Ielse,ex r 1 = Xltl Y 1 endif stop Lors de la compilation, on effectue exactement de la même manière le calcul des signatures de référence de chaque chemin licite dans le logiciel à contrôler en remplaçant les instructions de calcul des identifiants élémentaires d'exécution par des instructions d'affectation des identifiants élémentaires prédéterminés.25 Si le chemin suivi dans le graphe lors de l'exécution est correct, la signature courante Scr est égale à l'une des signatures de référence déterminées lors de la compilation. Sinon, Scr n'est égale à aucune des signatures de référence. En choisissant une suite (drlil)i=l,N distincte pour chaque réplique, on paramètre le calcul de signature On profite ainsi du contexte répliqué en utilisant un mode de calcul différent sur chaque réplique Ceci a pour effet de changer d'une réplique à l'autre l'ensemble des parcours possédant une même signature Une erreur générique ne35 devient donc indétectable que si, quelle que soit la réplique, la signature courante correspondante Scr appartient à l'ensemble des signatures de référence pour cette réplique. Afin de détecter une erreur après l'exécution des R répliques et selon le procédé de l'invention perfectionné par le calcul de signature exposé précédemment, on compare les signatures courantes des répliques ayant fourni le résultat final sélectionné (c'est-à-dire obtenu par un nombre prédéterminé des répliques ayant fourni un résultat cohérent) aux signatures de référence correspondantes pour10 chaque réplique Si toutes ces signatures courantes sont égales à l'une des signatures de référence pour la réplique correspondante, le résultat final sélectionné est considéré comme exact Dans le cas contraire, une erreur est indiquée. Bien que le calcul de signature tel que décrit ci- dessus, associé au codage-transcodage-décodage selon l'invention, soit suffisant dans la plupart des cas pour détecter les erreurs d'exécution, il peut arriver que, au niveau d'un branchement conditionnel (en sortie d'une instruction de test), la signature courante soit20 correctement mise à jour en fonction de l'identifiant correspondant au résultat du test effectué, mais qu'en pratique, l'autre branche soit exécutée C'est pourquoi, selon l'invention, on peut en outre faire dépendre la transformation de l'opérateur de l'instruction suivant25 immédiatement un branchement conditionnel de la signature courante et partielle du chemin exécuté jusque là Ceci permet de contrôler la concordance de la signature représentative d'un chemin avec le chemin effectivement parcouru.30 D'après ce qui a été décrit précédemment, toute instruction d'opération produit, si l'on utilise des fonctions ur, vr et Gr du type de celles indiquées dans le tableau précédent, un résultat codé Zr de la forme Zr = ar Z + flr- L'instruction d'opération devant utiliser z l'utilise, comme on l'a vu, sous la forme codée Z'r suivante (le passage de Zr à Z'r est le transcodage): Z'r = a'r Z + O'r. On a donc: Z r Zr + I 1 r r"r Si l'on note Sc,pr et Sréfpr respectivement les signatures partielles courante et de référence du chemin effectivement exécuté et du chemin prévu (Sréfpr est connue10 au moment de la compilation), on modifie la fonction permettant d'obtenir Z'r de sorte que l'on a Z f =Cc Ir S"IZ I alr r P 3 r r r réf,pr -Sc Pr Zr + 1 ra r Ainsi, une différence entre Scpr et Sréfpr induit une erreur (mauvaise traduction) dans l'évaluation de Z'r, et Z'r n'est donc pas compréhensible par l'instruction suivante On peut donc détecter une erreur de branchement même si la signature a été évaluée avec l'identifiant correct correspondant au branchement cohérent avec le résultat du test effectué lors de l'instruction de test20 correspondante. Selon un autre perfectionnement important du procédé selon l'invention, étant donné que l'ensemble des signatures de référence de chaque réplique peut avoir une taille prohibitive, on peut recourir à une technique de25 justification de signature Ceci a pour effet de transformer l'ensemble des signatures de référence pour une réplique donnée en un singleton Une technique classique de justification est décrite par exemple dans l'article intitulé "Concurrent Error Detection Using Watchdog30 Processors A Survey" paru dans IEEE Transactions on Computers, Vol 37, N 02, Février 1988, pages 160 à 174 On ne décrira donc pas cette technique plus en détails ici. La justification de signature peut en outre s'appliquer au cas des boucles, c'est-à-dire au cas des ensembles d'instructions réitérés plusieurs fois de suite. Puisque l'on connaît en général à la compilation le nombre maximal possible imax d'itérations de chaque boucle, on peut transformer chaque boucle en une boucle qui possède 5 exactement imax itérations, et ce en rajoutant au corps initial de la boucle une dérivation qui fonctionnellement n'a pas d'effet Grâce à la justification, les différents chemins possibles dans le corps de la boucle ont alors même signature partielle.10 Bien entendu, pour le calcul des signatures, lorsque le nombre de bits nécessaire à la représentation binaire des identifiants élémentaires n'est pas suffisant pour effectuer le décalage souhaité, les bits de rang le plus élevé (ou de rang le plus faible) qui se trouveraient éventuellement en15 dehors de la zone disponible, sont replacés au niveau des bits de rang le plus faible (ou de rang le plus élevé), ce qui revient à effectuer une permutation circulaire sur les représentations binaires des identifiants élémentaires. Enfin, on pourra remplacer tout moyen par un moyen équivalent, et en particulier toute méthode de codage par une méthode équivalente, sans sortir du cadre de l'invention. REVENDICATIONS 1/ Procédé de détection des erreurs d'exécution d'un logiciel répliqué, c'est-à-dire dont plusieurs répliques identiques, auxquelles sont fournies les mêmes données d'entrée, sont exécutées en parallèle ou séquentiellement, ledit logiciel comprenant des instructions reliées entre elles par des branchements et constituées: soit d'opérations mettant en jeu un opérateur, dit simple, agissant sur des opérandes, dits simples, afin de mettre à jour le contenu d'une variable, lesdits opérandes étant constitués soit de données d'entrée, soit de résultats obtenus par exécution d'autres instructions, soit de tests conditionnels dont le résultat sert à déterminer l'instruction suivante à exécuter, soit d'indications de destination donnant directement l'instruction suivante à exécuter, ledit procédé étant caractérisé en ce que chacune desdites instructions d'opération, au sein de chaque réplique, est20 remplacée par plusieurs instructions dites de détection d'erreur permettant d'effectuer successivement: le codage préalable des opérandes mis en jeu dans ladite instruction d'opération et constitués de données d'entrée, au moyen d'une injection dite de codage spécifique de ladite25 instruction d'opération, pour obtenir des données d'entrée dites codées images desdites données d'entrée simples par ladite injection, chaque injection de codage, associée à l'une desdites répliques et à une instruction d'opération donnée au sein de cette réplique, étant distincte des30 injections de codage associées à toutes les autres instructions d'opération au sein de toutes les autres répliques, la transformation dudit opérateur simple associé à ladite instruction d'opération, de sorte que l'opérateur appliqué aux opérandes, codés, de ladite instruction résulte de la transformation dudit opérateur simple, les transformations correspondant à des opérateurs identiques au sein des différentes répliques étant deux à deux distinctes, le transcodage du résultat obtenu par application dudit opérateur transformé auxdites opérandes codés, pour obtenir un résultat dit transcodé sous la forme d'un opérande codé au moyen du codage spécifique de l'instruction d'opération destinée à utiliser ledit résultat, ledit transcodage étant effectué au moyen d'une transformation dite de transcodage, chaque transformation de transcodage, associée à l'une10 desdites répliques et à une instruction d'opération donnée au sein de cette réplique étant distincte des transformations de transcodage associées à toutes les autres instructions d'opération au sein de toutes les autres répliques,15 ledit procédé étant en outre caractérisé en ce qu'il comprend une opération finale de décodage du résultat, dit final, obtenu en fin d'exécution de chaque réplique, au moyen de l'inverse d'une injection dite de décodage, chaque injection de décodage, spécifique de l'une desdites20 répliques, étant distincte des injections de décodage des autres répliques, et en ce qu'il indique qu'une erreur d'exécution s'est produite si, pour certaines desdites répliques, ledit résultat final ne peut être décodé au moyen de ladite injection inverse correspondante, et si, parmi les25 résultats finaux décodés des autres répliques, il n'en existe pas un, éventuellement appelé alors résultat final sélectionné, qui est obtenu par un nombre minimum prédéterminé desdites autres répliques. 2/ Procédé selon la revendication 1 caractérisé en ce qu'il consiste en outre à: déterminer, lors de la compilation de chacune desdites répliques, une donnée de référence, appelée signature de référence, pour chaque parcours autorisé au sein de ladite réplique, par combinaison de constantes numériques appelées35 identifiants élémentaires prédéterminés et associés à chaque instruction de test et à chaque instruction de destination, lesdites signatures de référence étant mises en mémoire, calculer, au moyen d'instructions supplémentaires insérées au sein de chacune desdites répliques, la valeur d'une variable, appelée signature courante, représentative de la5 suite des instructions de test et de destination effectuées lors de l'exécution, par combinaison de valeurs numériques appelées identifiants élémentaires d'exécution et associées à chacune des instructions de destination et de test exécutées, les combinaisons effectuées au sein d'une même réplique pour la détermination et pour le calcul respectivement desdites signatures de référence et courante étant identiques, et distinctes deux à deux d'une réplique à l'autre au moyen d'un paramétrage adapté,15 ledit procédé étant en outre caractérisé en ce que, lorsqu'il existe un résultat final sélectionné, les signatures courantes des répliques ayant fourni ledit résultat final sélectionné sont comparées aux signatures de référence correspondantes, et si chacune desdites signatures20 courantes n'est pas égale à l'une desdites signatures de référence de la réplique correspondante, ledit procédé consiste alors à indiquer qu'une erreur s'est produite. 3/ Procédé selon la revendication 2 caractérisé en ce que, pour une instruction d'opération suivant une instruction de test, ladite transformation associée à l'opérateur correspondant est fonction de la différence entre les signatures courante et de référence partielles du parcours exécuté jusqu'à ladite instruction de test. 4/ Procédé selon l'une des revendications 1 ou 2 caractérisé en ce que la fonction de transformation de chacun desdits opérateurs est composée avec la transformation de transcodage de l'instruction d'opération précédente pour constituer une seule fonction. 5/ Procédé selon l'une des revendications 1 à 4 caractérisé en ce que lesdites injections de codage sont des fonctions affines dont l'ordonnée à l'origine et la pente sont différentes d'une réplique à l'autre. 6/ Procédé selon l'une des revendications 1 à 5 caractérisé en ce que, lorsque l'opération est une addition ou une soustraction, l'opérateur transformé correspondant est respectivement une addition ou une soustraction, c'est-à-dire que la transformation utilisée pour transformer l'opérateur est l'identité. 7/ Procédé selon l'une des revendications 2 à 6 caractérisé en ce que, pour déterminer ou calculer lesdites signatures de référence ou courantes, on additionne les représentations binaires desdits identifiants élémentaires en les ayant préalablement multipliées chacune par une puissance de deux choisie arbitrairement, ladite puissance de deux étant15 fonction du numéro d'ordre de l'instruction correspondante et les ensembles de puissances de deux utilisés au sein de chaque réplique étant deux à deux distincts. 8/ Procédé selon l'une des revendications 2 à 7 caractérisé en ce que l'identifiant élémentaire d'exécution d'une instruction de test est calculé en fonction de la variable faisant l'objet de la condition de ladite instruction de test, et de constantes prédéterminées, de sorte que, si l'instruction à laquelle correspond ledit identifiant est exécutée correctement, il est égal à l'identifiant25 élémentaire prédéterminé affecté à cette instruction. 9/ Procédé selon la revendication 8 caractérisé en ce que ladite variable faisant l'objet de ladite condition de ladite instruction de test est codée au moyen d'un codage spécifique fonction de la variable prévue pour ledit test,30 avant d'être utilisée pour le calcul dudit identifiant élémentaire d'exécution. / Procédé selon l'une des revendications 2 à 9 caractérisé en ce que les identifiants élémentaires d'exécution desdites instructions de destination sont calculés par une35 instruction supplémentaire suivant chaque instruction de destination et affectant à l'identifiant élémentaire d'exécution une constante prédéterminée égale à l 'identifiant élémentaire prédéterminé correspondant.