Comment pouvons-nous être certains que les composants les plus bas de la programmation informatique tels que les compilateurs, les assembleurs, les instructions machine, etc. sont sans faille?

57

Étant donné que nous dépendons de plus en plus de l'informatique, y compris de tâches très critiques de la vie quotidienne, je me demandais simplement comment ces composants essentiels étaient testés.

Plus techniquement, comment sont testés les compilateurs et les assembleurs? (Je suppose que cela se rapporte au problème de halte !!)

Sudip Bhandari
la source
36
Vous voudrez peut-être commencer vos recherches avec "Ken Thompson Hack". Voir Réflexions sur Trusting Trust
Bryan Oakley
7
Voici un exemple de compilateur pour lequel il existe une preuve de correction: compcert.inria.fr/doc/index.html
Giorgio
8
La plupart des compilateurs / lieurs / assembleurs sont testés plus profondément en les utilisant beaucoup dans de nombreuses circonstances différentes. Pour trouver des erreurs, rien ne se résume au fait que des millions d'utilisateurs utilisent votre compilateur.
Bart van Ingen Schenau
3
et ajoutez également le système d'exploitation à la liste.
Erik Eidt

Réponses:

104

Vous ne pouvez pas en être certain, mais vous présumez qu'ils le sont jusqu'à ce que vous découvriez qu'ils ne le sont pas. Il y a eu beaucoup de bogues dans les compilateurs et le matériel au fil des ans.

La façon dont ils sont testés, par exemple un compilateur, c’est qu’ils sont définis de manière très étroite et rigide, soigneusement écrits, puis testés avec une énorme suite de tests pour vérifier leur exactitude. Ajoutez à cela la large base d'utilisateurs d'un compilateur, et davantage de bogues seront détectés et rapportés. Une application de planification de rendez-vous chez le dentiste a comparativement beaucoup moins d'utilisateurs et encore moins de personnes capables de détecter des défauts.

SQLite comprend environ 73 000 lignes de code, tandis que sa suite de tests comprend environ 91378 000 lignes de code, soit plus de 1250 fois celle de SQLite. Je m'attends à ce que les compilateurs et autres outils de base présentent des ratios similaires. Les processeurs actuels sont conçus essentiellement avec des logiciels, utilisant des langages de description matérielle tels que Verilog ou VHDL. Des tests logiciels sont également appliqués sur ces derniers, ainsi que des broches d'E / S spécialisées pour l'exécution d'autotests sur le lieu de fabrication.

En fin de compte, il s’agit d’un jeu de probabilités. Des tests répétés et largement couvrant vous permettent de réduire la probabilité de défauts à un niveau suffisamment bas, comme un projet de logiciel.

comment s'appelle-t-il
la source
7
Je me suis souvent posé la même question que le PO, mais en ce qui concerne les SGBD. Vous avez donné un excellent exemple qui y a répondu dans le contexte de SQLite. Je vous remercie!
Brandon
7
+1, mais je doute que "les compilateurs et autres outils principaux aient des ratios similaires".
Mehrdad
5
Notez que (1) SQLite a en fait deux suites de tests, avec une redondance non triviale entre les deux et (2) il y a toujours des bogues trouvés dans SQLite malgré cela.
Matthieu M.
7
J'ai eu l'impression que SQLite est l'un des logiciels les plus «largement testés» (en termes de lignes de code de test / lignes de code opérationnel) disponibles pour un usage général, plus que beaucoup de compilateurs. Si rien d'autre, un compilateur complet est un énorme logiciel, et je ne peux pas l'imaginer avec mille fois cette quantité de code de test. (GCC compterait jusqu'à 14,5 millions de lignes. Il semble peu probable que la collection du compilateur proprement dit ne représente que 14k LOC ou une base de code de test de 14 milliards de lignes reposant sur le côté! :-P)
David Z
2
@DavidZ: Oui, c’est certainement le seul projet que je connaisse à utiliser des tests approfondis de MOO par exemple (ils utilisent un injecteur de pannes pour le test et les rejouent encore et encore, échouant à la 1ère, puis à la 2e attribution ... jusqu’au test complet. est exécuté).
Matthieu M.
46

En termes simples:

  1. Vous ne pouvez pas.
  2. Les compilateurs et interprètes sont testés sur l'unité comme n'importe quel autre logiciel (professionnel).
  3. Un test réussi ne signifie pas qu'un programme est exempt de bogues, cela signifie simplement qu'aucun bogue n'a été détecté.
  4. Une large base d'utilisateurs utilisant le compilateur pendant une longue période est un joli indicateur du fait qu'il contient très peu de bogues, car les utilisateurs testent généralement des cas de test auxquels les concepteurs n'ont pas pensé.
  5. Être open source est également un bon indicateur. "Avec un nombre suffisant de globes oculaires, tous les bogues sont superficiels ... Avec une base de bêta-testeurs et de co-développeurs suffisamment importante, presque tous les problèmes seront caractérisés rapidement et le correctif sera évident pour quelqu'un." . Un compilateur à source fermée peut avoir des bogues qui surviennent à des moments très spécifiques ou qui génèrent un code machine non optimal et la société qui le sous-tend pourrait tout simplement ne pas révéler leur existence et ne pas lui accorder une très faible priorité dans la feuille de route du produit.

En bout de ligne:

Je dirais aller pour la POO ( O ld, O pen et P opular). Je viens de composer cet acronyme.

Tulains Córdova
la source
19
+1 Pour avoir inventé un autre TLA (acronyme de trois lettres) - le monde n’en a pas encore assez.
s1lv3r
34
En outre, la programmation orientée objet n'avait pas encore de sens en programmation informatique. Alors KTT (bravo à toi)!
Pierre Arlaud
15
Le commentaire de Pierre est une blague @Dannnno.
Yannis
19
Sinon, il pourrait P opular, O ld et O stylo. ;) En fait, c'est comme ça que je les classerais par ordre d'importance.
jpmc26
23
@ jpmc26 J'irais avec Pratique, Vieux, Ouvert et Populaire. En ce qui concerne l'acronyme ...
StupidOne
24

C'est des tortues tout en bas.

Rien est certain. Vous n'avez pas d'autre choix que de vous contenter des notes de confiance.

Vous pouvez le considérer comme une pile: Math> Physique> Matériel> Micrologiciel> Système d'exploitation> Assembler / Compiler / etc

A chaque niveau, vous avez des tests que vous pouvez effectuer pour améliorer votre indice de confiance. Certains de ces tests ont la qualité de preuves formelles, d'autres sont basés sur l'observation, la plupart combinant les deux.

La partie la plus délicate est de résoudre la récursion dans certains de ces tests car nous utilisons des programmes pour faire des preuves et des analyses d’observation où il est devenu trop difficile de le faire à la main.

En fin de compte, la réponse est que vous essayez tout ce que vous pouvez penser. Analyse statique, fuzzing, simulation, exécution avec des entrées extrêmes ou aléatoires sélectionnées intentionnellement, exécution / mappage de tous les chemins de contrôle, preuves formelles, etc. En principe, votre objectif de test doit toujours être de faire tout votre possible pour prouver que votre produit (par exemple puce / programme) ne fonctionne pas comme prévu. Si vous faites un effort sincère et que vous échouez toujours, vous êtes autorisé à améliorer votre indice de confiance dans l'exactitude de votre produit.

Le test est au mieux un processus de semi-décision, ce qui signifie qu’en présence d’un bogue, vous le trouverez éventuellement, mais vous ne pouvez jamais être sûr de les avoir tous trouvés. Même avec un logiciel formellement vérifié, vous vous basez toujours sur la physique, les outils utilisés pour faire les preuves formelles, et sur le fait que la preuve que vous avez prouvée est nécessaire et suffisante pour que votre programme fasse ce qui est (souvent subjectivement) "prévu". Sans parler de tous les autres composants que vous utilisez et qui n’ont pas de preuves formelles.

voutasaurus
la source
17

C'est une question "dangereuse" pour les nouveaux développeurs dans la mesure où ils vont commencer à blâmer leurs outils au lieu de leur code (ils en ont été, ont fait, trop vu le font). Bien qu'il y ait des bogues dans les compilateurs, les environnements d'exécution, les systèmes d'exploitation, etc., les développeurs doivent être réalistes et se rappeler que, jusqu'à ce qu'il y ait des preuves et des tests unitaires démontrant le contraire, le bogue se trouve dans votre code .

En plus de 25 ans de programmation principalement en C, C ++ et Java, j'ai trouvé:

  • deux bugs dus à un bug de compilation (gcc et SunOS C)
  • environ une fois par an ou tous les deux ans, un bogue dû à un problème JVM Java (généralement lié à la consommation de mémoire / au ramassage des ordures)
  • environ une fois par mois ou tous les deux mois, un bogue dans une bibliothèque, qui est fréquemment corrigé en utilisant la dernière version ou en revenant à la version précédente de la bibliothèque

Tous les autres bogues sont directement liés à un bogue ou, plus fréquemment, à un manque de compréhension du fonctionnement d'une bibliothèque. Parfois, ce qui semble être un bogue est dû à une incompatibilité, par exemple comment la structure de classes Java a changé, cassant certaines bibliothèques AOP.

Ed Griebel
la source
Je suis curieux - quelles années pour quelles langues? À l'époque de l'EGCS, avant que le langage C ++ ne soit correctement normalisé, les problèmes de compilateur n'étaient pas si difficiles à trouver ...
Charles Duffy
3
Plus le compilateur, le processeur ou la langue est obscur, plus il est facile, donc, de trouver un bogue dans les compilateurs (avant quelqu'un d'autre), donc trouver 2 dans GCC C est bien :)
Surt
1
En fait, je viens de perdre environ un mois en supposant que le problème que je rencontrais était dans mes scripts gdb ou que je comprenais bien ce que j’examinais. Finalement, j’ai eu des doutes, simplifié mon scénario de test et trouvé un défaut de conception dans une bibliothèque (libkvm), ce qui empêchait le débogueur du noyau d’accéder à certaines adresses à partir d’un vidage mémoire. C'est-à-dire YMMV - et je suis le plus heureux quand je trouve un nouveau bogue dans le code en amont de moi, surtout quelque chose que j'utilise plutôt que de développer.
Arlie Stephens
Bien sûr, ce n'était pas un bogue du compilateur , ni même l'une des bibliothèques les plus utilisées. Et à vrai dire, je ne trouve pas de bugs chez ceux qui ont une fréquence quelconque.
Arlie Stephens
@ArlieStephens Il y a une leçon à tirer: simplifier votre cas de test est quelque chose que vous devriez faire dès le début lorsque vous ne parvenez pas à trouver un problème. Que le problème soit le vôtre ou celui de l'autre code, cela vous aidera à le réduire. Souvent, si le problème provient de l’autre code, il en résulte "des preuves et des tests unitaires le prouvant".
Jpmc26
8

Je pense qu’un point intéressant ici est que la grande majorité des licences de logiciels commerciaux (et même de logiciels open source) spécifient spécifiquement que vous ne pouvez pas faire confiance au logiciel.

LE LOGICIEL EST FOURNI "EN L'ETAT", SANS AUCUNE GARANTIE, EXPRESSE OU IMPLICITE, Y COMPRIS DE MANIÈRE NON LIMITÉE À LA GARANTIE DE QUALITÉ MARCHANDE, D'ADÉQUATION À UN USAGE PARTICULIER ET D'INFRACTION.

À partir du contrat de licence Microsoft Word

. À l’exception de la garantie limitée et dans la limite permise par la loi en vigueur, Microsoft et ses fournisseurs fournissent le logiciel et les services de support (le cas échéant) EN l’ETAT ET AVEC TOUS LES PANNES, et déclinent par la présente toute autre garantie, expresse, implicite ou contraire. légaux, y compris, sans toutefois s'y limiter, les éventuelles garanties, obligations ou conditions implicites de qualité marchande, d'adéquation à un usage particulier, de fiabilité ou de disponibilité, d'exactitude ou de complétude des réponses, des résultats, de l'effort de fabrication, de absence de virus et absence de négligence, le tout concernant le logiciel, ainsi que la fourniture ou l'absence d'assistance, de services, d'informations, de logiciels et de contenus associés via le logiciel ou résultant de l'utilisation du logiciel .

En substance, cette phrase de la licence de presque tous les logiciels que vous utilisez spécifie spécifiquement que vous ne pouvez pas faire confiance au logiciel et encore moins au compilateur utilisé.

Le logiciel est comme une théorie scientifique, il est réputé fonctionner comme spécifié jusqu'à ce qu'il ne fonctionne plus.

Toby Allen
la source
+1 pour signaler que les licences mêmes indiquent qu'aucun logiciel n'est parfait.
Tulains Córdova
3
J'ai eu le plaisir de constater un écart par rapport à cette pratique dans le logiciel ViaVoice pour Mac d'IBM. Au lieu de l’habitude «si cela ne fonctionne pas, tant pis», ils ont en fait dit quelque chose du type «Le logiciel est garanti pour fonctionner comme prévu».
WGroleau
1
Voici une traduction en langage clair de ce type de garantie: "Il s’agit peut-être d’un logiciel, ou bien d’un logiciel. Cela pourrait fonctionner. Cela ne fonctionnerait peut-être pas. Même si cela fonctionnait, cela pourrait ne pas fonctionner." Faites ce que vous voulez. Oh, en passant, nous pourrions en avoir volé des morceaux à quelqu'un d'autre. Dommage, nous avons votre argent et l'avons utilisé pour engager beaucoup d'avocats. JEU! ON! Nyah-nyah -nyah-nyah-nyaaah-naah! ". :-)
Bob Jarvis
2
@BobJarvis: Mon énoncé de garantie préféré, utilisé sur certains logiciels open source (comme nmap IIRC), est le suivant: "Si ça casse, vous devez garder les deux pièces".
Peter Cordes
Cette affirmation est omniprésente dans les logiciels open source et dans de nombreux logiciels fermés gratuits. Il n'apparaît pas dans la plupart des licences de logiciel payantes commerciales.
Jwg
2

En tant que rédacteur de compilateur pour un langage mathématique *, de par mon expérience, je peux dire en théorie que vous ne pouvez pas. Et certains des bogues donnent simplement des résultats erronés, comme (de ma liste honteuse), calculer à 6/3*2partir de la droite 6/(3*2)et en afficher 1 sans planter ou donner des erreurs de compilation absurdes.

Mais à mon humble avis, de nombreux compilateurs n’ont pas autant de bogues que les autres logiciels pour les raisons suivantes:

  • Écrire des tests unitaires est facile. Chaque instruction est une unité et vous pouvez écrire des tests aussi simples que:test_unit("2+(-2)*(-2+1)*3+1",9);
  • Un programme est une combinaison d'instructions et pour que tout programme produise le résultat correct, chaque instruction individuelle doit donner le résultat correct (le plus souvent). Il est donc très peu probable qu’il y ait des bugs pendant que le programme donne le résultat correct.
  • À mesure que la taille et le nombre de programmes écrits augmentent, la probabilité d'attraper des bogues augmente considérablement.

Pour les assembleurs, les instructions de machine, etc., ce qui précède est également valable; d’autre part, la vérification et la validation dans la conception et la production de puces ont des processus beaucoup plus stricts, car c’est une activité très importante: l’ automatisation de la conception électronique .

Avant de commencer la production, chaque processeur doit être testé rigoureusement, car chaque bogue coûte près de deux millions de dollars: la production de puces entraîne d’énormes coûts de production non récurrents. Les entreprises dépensent donc beaucoup d'argent et écrivent beaucoup de code de simulation pour leur conception avant de commencer la production, bien que cela ne donne pas une garantie à 100% - par exemple: le bug Pentium FDIV.

En bref, il est très peu probable que les compilateurs, les codes de machine, etc.

Mon humble langage mathématique *

Gorkem
la source
Intel teste l’enfer de ses processeurs en exécutant des séquences d’instructions aléatoires et en les comparant à un modèle logiciel, entre autres choses: tweakers.net/reviews/740/4/… . C'est pourquoi vous voyez souvent des errata vraiment obscurs publiés, pour certaines combinaisons vraiment improbables d'instructions dans un mode inhabituel.
Peter Cordes
0

Sans défaut? Ils ne sont pas. J'ai récemment installé des "mises à jour", et plusieurs mois (et plusieurs sections de code reprogrammées) ont été nécessaires avant que mon site ASP.NET ne fonctionne à nouveau correctement, en raison de modifications inexpliquées du fonctionnement ou de l'échec de divers éléments de base.

Cependant, ils sont testés puis utilisés par de nombreuses personnes très intelligentes, qui ont tendance à remarquer, rapporter et réparer la plupart des choses. Stack Exchange est un excellent exemple (et une amélioration) de la façon dont toutes les personnes utilisant ces outils aident à tester et à analyser le fonctionnement de ces outils incroyablement complexes et de bas niveau, du moins en ce qui concerne l'utilisation pratique.

Mais sans faille, non. Bien que vous puissiez également voir des utilisateurs de Stack Exchange obtenir un aperçu impressionnant des détails de performances, de la conformité aux normes et des bizarreries, il y a toujours des failles et des imperfections, en particulier lorsque différentes personnes ont des opinions différentes sur ce qu'est une faille.

Dronz
la source
-1

Pour montrer que les systèmes sous-jacents sont sans faille, vous devez soit

a) Nécessité de prouver qu'ils sont sans faille

  1. Preuve mathématique
  2. Réellement possible uniquement pour des programmes triviaux

b) Faire un test exhaustif

  1. Possible uniquement pour les programmes triviaux et certains programmes simples
  2. Dès qu'un élément de chronométrage entre dans le test, il n'est pas possible de faire un test exhaustif car le temps peut être divisé indéfiniment.
  3. Au-delà des programmes triviaux, les options d'exécution possibles explosent de manière exponentielle.

Dans les tests de logiciels, le test exhaustif n’est utilisé que dans le test unitaire de certaines fonctions simples.

Exemple: vous voulez tester une entrée utf-8 de 8 caractères dans un champ, vous devez couper l’entrée de 8 fois la longueur maximale 6 d’utf-8 en octets, ce qui donne 8 * 6 = 48 octets pour avoir un quantités finies de possibilités.

Vous pouvez maintenant penser que vous devez uniquement tester les 1 112 064 points de code valides de chacun des 8 caractères, c.-à-d. 1 112 064 ^ 8 (disons 10 ^ 48) tests (ce qui est déjà peu probable), mais vous devez en réalité tester chaque valeur de chacun des 48 octets ou 256 ^ 48, ce qui correspond à environ 10 ^ 120, ce qui est la même complexité que les échecs par rapport au nombre total d'atomes dans l'univers d'environ 10 ^ 80.

Au lieu de cela, vous pouvez utiliser, par ordre croissant d’effort, et chaque test doit couvrir tous les précédents:

a) tester un bon et un mauvais échantillon.

b) couverture de code, c'est-à-dire. essayez de tester chaque ligne de code, ce qui est relativement simple pour la plupart des codes. Vous pouvez maintenant vous demander quel est le dernier 1% du code que vous ne pouvez pas tester: bugs, code mort, exceptions matérielles, etc.

c) couverture de cheminement, tous les résultats de toutes les branches de toutes les combinaisons sont testés. Vous savez maintenant pourquoi le département de test vous hait quand vos fonctions contiennent plus de 10 conditions. Aussi vous vous demandez pourquoi le dernier 1% ne peut pas être testé ... certaines branches sont dépendantes des branches précédentes.

d) test des données, testez un nombre d'échantillons avec une valeur de bordure, des valeurs problématiques communes et des nombres magiques, zéro, -1, 1, min +/- 1, max +/- 1, 42, rnd valeurs. Si cela ne vous donne pas une couverture de chemin, vous savez que vous n'avez pas capté toutes les valeurs de votre analyse.

Si vous le faites déjà, vous devriez être prêt pour l'examen de base ISTQB.

Surt
la source