Wie können wir sicher sein, dass die unteren Komponenten der Computerprogrammierung wie Compiler, Assembler, Maschinenanweisungen usw. fehlerfrei sind?

57

Da wir uns immer mehr auf das Rechnen verlassen, einschließlich sehr kritischer Aufgaben des täglichen Lebens, habe ich mich nur gefragt, wie diese wichtigen Komponenten getestet werden.

Wie werden die Compiler und Assembler technisch getestet? (Ich nehme an, das hängt mit dem Halteproblem zusammen !!)

Sudip Bhandari
quelle
36
Vielleicht möchten Sie Ihre Recherche mit dem "Ken Thompson Hack" beginnen. Siehe Überlegungen zu Trusting Trust
Bryan Oakley
7
Hier ist ein Beispiel eines Compilers, für den es einen Korrektheitsnachweis gibt: compcert.inria.fr/doc/index.html
Giorgio
8
Die meisten Compiler / Linker / Assembler werden am gründlichsten getestet, indem sie unter vielen verschiedenen Umständen verwendet werden. Um Fehler zu finden, müssen Millionen von Benutzern Ihren Compiler verwenden.
Bart van Ingen Schenau
3
und fügen Sie das Betriebssystem ebenfalls zur Liste hinzu.
Erik Eidt

Antworten:

104

Sie können sich nicht sicher sein, aber Sie gehen einfach davon aus, dass dies der Fall ist, bis Sie feststellen, dass dies nicht der Fall ist. Im Laufe der Jahre gab es viele Fehler in Compilern und in der Hardware.

Diese werden zum Beispiel als Compiler getestet, indem sie sehr eng und streng definiert, sorgfältig geschrieben und dann mit einer riesigen Testsuite getestet werden , um die Richtigkeit zu überprüfen. Fügen Sie dem die breite Benutzerbasis eines Compilers hinzu, und mehr Bugs werden erkannt und gemeldet. Eine Zahnarztterminplanungs-App hat vergleichsweise viel weniger Benutzer und immer noch weniger, die in der Lage sind, Fehler zu erkennen.

SQLite besteht aus ca. 73.000 Codezeilen, während die Testsuite aus ca. 91378.000 Codezeilen besteht, was mehr als dem 1250-fachen von SQLite selbst entspricht. Ich gehe davon aus, dass Compiler und andere Kerntools ähnliche Verhältnisse haben. Prozessoren werden heutzutage im Wesentlichen mit Software entwickelt, die Hardwarebeschreibungssprachen wie Verilog oder VHDL verwendet, und auf diesen werden auch Softwaretests ausgeführt sowie spezialisierte E / A-Pins zum Ausführen von Selbsttests am Herstellungsort.

Letztendlich handelt es sich um ein Wahrscheinlichkeitsspiel. Durch wiederholtes und umfassendes Testen können Sie die Wahrscheinlichkeit von Fehlern auf ein akzeptabel niedriges Niveau senken, genau wie bei einem anderen Softwareprojekt.

Whatsisname
quelle
7
Ich habe mich oft die gleiche Frage gestellt wie das OP, aber in Bezug auf DBMS. Sie gaben ein großartiges Beispiel, das es im Kontext von SQLite beantwortete. Danke!
Brandon
7
+1 aber irgendwie bezweifle ich, dass "Compiler und andere Kernwerkzeuge ähnliche Verhältnisse haben".
Mehrdad
5
Beachten Sie, dass (1) SQLite tatsächlich zwei Testsuiten hat, wobei zwischen den beiden Redundanzen keine Trivialität besteht und (2) in SQLite trotzdem noch Fehler gefunden werden.
Matthieu M.
7
Ich hatte den Eindruck, dass SQLite eine der am meisten "ausgiebig getesteten" Software-Komponenten (in Bezug auf Testcodezeilen / Operationscodezeilen) ist, die für den allgemeinen Gebrauch verfügbar sind, mehr noch als viele Compiler. Wenn überhaupt, ist ein Compiler mit vollem Funktionsumfang eine enorme Software, und ich kann mir nicht vorstellen, dass er die tausendfache Menge an Testcode enthält. (GCC hat Berichten zufolge bis zu 14,5 Millionen Zeilen. Es ist unwahrscheinlich, dass entweder die eigentliche Compiler-Sammlung nur 14 KByte groß ist oder dass eine 14-Milliarden-Zeilen-Testcodebasis auf der Seite herumsteht! :-P)
David Z
2
@DavidZ: Es ist sicherlich das einzige Projekt, von dem ich weiß, dass es umfangreiche OOM-Tests verwendet (sie verwenden einen Fehlerinjektor für den Test und spielen sie immer wieder ab, bis der gesamte Test fehlschlägt ausgeführt wird).
Matthieu M.
46

In den Begriffen des Laien:

  1. Du kannst nicht.
  2. Compiler und Interpreter sind wie jede andere (professionelle) Software Unit-getestet.
  3. Ein erfolgreicher Test bedeutet nicht, dass ein Programm fehlerfrei ist, sondern nur, dass keine Fehler erkannt wurden.
  4. Eine breite Anwenderbasis, die den Compiler über einen langen Zeitraum verwendet, ist ein hübscher Indikator dafür, dass er nur sehr wenige Fehler aufweist, da Anwender normalerweise Testfälle testen, an die die Designer nicht gedacht haben.
  5. Open Source ist auch ein guter Indikator. "Bei genügend Augäpfeln sind alle Bugs flach ... Bei einer ausreichend großen Beta-Tester- und Co-Entwickler-Basis wird fast jedes Problem schnell charakterisiert und die Behebung ist für jemanden offensichtlich." . Ein Closed-Source-Compiler kann Fehler aufweisen, die zu ganz bestimmten Zeiten auftreten oder einen nicht optimalen Maschinencode generieren, und das Unternehmen, das dahintersteckt, kann einfach nicht offenlegen, ob sie existieren, und ihm eine sehr niedrige Priorität in der Roadmap des Produkts einräumen.

Endeffekt:

Ich würde sagen, gehen Sie für OOP ( O ld, O Stift und P opular). Ich habe gerade dieses Akronym erfunden.

Tulains Córdova
quelle
19
+1 Für die Erfindung eines weiteren TLA (Drei-Buchstaben-Akronym) - die Welt hat noch nicht genug davon.
s1lv3r
34
Auch hatte OOP noch keine Bedeutung in der Computerprogrammierung. Also KTT (ein dickes Lob an dich)!
Pierre Arlaud
15
Pierres Kommentar ist ein Witz @Dannnno.
Yannis
19
Alternativ könnten es P opular, O ld und O pen sein. ;) Eigentlich würde ich sie so nach Wichtigkeit ordnen.
jpmc26
23
@ jpmc26 Ich würde mit Praktisch, Alt, Offen und Populär gehen. Wie für Akronym ...
StupidOne
24

Es ist Schildkröten den ganzen Weg nach unten.

Nichts ist sicher. Sie haben keine andere Wahl, als sich auf Vertrauensbewertungen zu einigen.

Sie können sich das als Stapel vorstellen: Mathematik> Physik> Hardware> Firmware> Betriebssystem> Assembler / Compiler / etc

Auf jeder Ebene haben Sie Tests, die Sie durchführen können, um Ihre Vertrauensbewertungen zu verbessern. Einige dieser Tests haben die Qualität formaler Beweise, einige basieren auf Beobachtungen, die meisten sind eine Kombination aus beiden.

Der knifflige Teil besteht darin, die Rekursion in einigen dieser Tests aufzudecken, da wir Programme verwenden, um Beweise und Beobachtungsanalysen durchzuführen, wo es zu schwierig geworden ist, dies von Hand zu tun.

Letztendlich ist die Antwort, dass Sie alles versuchen, was Sie sich vorstellen können. Statische Analyse, Fuzzing, Simulation, Laufen mit gezielt ausgewählten extremen Eingaben oder zufälligen Eingaben, Laufen / Abbilden aller Kontrollpfade, formale Beweise usw. Grundsätzlich sollte Ihr Ziel beim Testen immer sein, alles Mögliche zu tun, um zu beweisen, dass Ihr Produkt (z. B. Theorie / Chip / Programm) funktioniert nicht wie vorgesehen. Wenn Sie sich wirklich anstrengen und dennoch scheitern, können Sie Ihr Vertrauen in die Korrektheit Ihres Produkts verbessern.

Testen ist im besten Fall ein Semidecision-Prozess, was bedeutet, dass Sie einen Fehler finden, aber Sie können nie sicher sein, dass Sie alle gefunden haben. Selbst mit formal verifizierter Software verlassen Sie sich immer noch auf die Physik, die Werkzeuge, die für die formalen Beweise verwendet werden, und darauf, dass das, was Sie bewiesen haben, für Ihr Programm notwendig und ausreichend ist, um das zu tun, was (oftmals subjektiv) "beabsichtigt" ist. Das ist nicht zu erwähnen, dass alle anderen Komponenten, die Sie verwenden, keine formalen Beweise haben.

Voutasaurus
quelle
17

Dies ist eine "gefährliche" Frage für neue Entwickler, da sie anfangen, ihre Tools anstelle ihres Codes zu beschuldigen. Obwohl es Fehler in Compilern, Laufzeitumgebungen, Betriebssystemen usw. gibt, sollten Entwickler realistisch sein und sich daran erinnern, dass der Fehler in Ihrem Code enthalten ist , bis Beweise und Komponententests etwas anderes belegen .

In mehr als 25 Jahren Programmierung in C, C ++ und Java habe ich Folgendes gefunden:

  • zwei Fehler aufgrund eines Compiler-Fehlers (gcc und SunOS C)
  • Ungefähr ein bis zwei Mal im Jahr ein Fehler aufgrund eines Java-JVM-Problems (normalerweise im Zusammenhang mit Speicherverbrauch / Speicherbereinigung)
  • Ungefähr einmal im Monat oder zweimal ein Fehler in einer Bibliothek, der häufig durch Verwendung der neuesten Version oder Zurücksetzen auf die vorherige Version der Bibliothek behoben wird

Alle anderen Fehler haben einen direkten Bezug zu einem Fehler oder häufiger zu einem Mangel an Verständnis für die Funktionsweise einer Bibliothek. Manchmal scheint ein Fehler auf eine Inkompatibilität zurückzuführen zu sein, beispielsweise auf die Änderung der Java-Klassenstruktur, durch die einige AOP-Bibliotheken beschädigt wurden.

Ed Griebel
quelle
Ich bin gespannt - welche Jahre für welche Sprachen? In den EGCS-Tagen, bevor C ++ richtig standardisiert wurde, waren Compiler-Bugs nicht so schwer zu finden ...
Charles Duffy
3
Je dunkler der Compiler, die CPU oder die Sprache, desto einfacher ist es, Fehler in den Compilern zu finden (vor jemand anderem). Daher ist es schön, 2 in GCC C zu finden :)
Surt
1
Zufälligerweise verschwendete ich nur ungefähr einen Monat damit, anzunehmen, dass das Problem in meinen GDB-Skripten oder in meinem Verständnis dessen, was ich untersuchte, lag. Schließlich wurde ich misstrauisch, vereinfachte meinen Testfall und fand einen Konstruktionsfehler in einer Bibliothek (libkvm), der es einem Kernel-Debugger unmöglich machte, über einen Core-Dump auf bestimmte Adressen zuzugreifen. Dh YMMV - und ich bin am glücklichsten, wenn ich einen neuen Fehler im Code vor mir finde, insbesondere etwas, das ich eher benutze als zu entwickeln.
Arlie Stephens
Natürlich war es kein Compiler- Fehler oder eine der am häufigsten verwendeten Bibliotheken. Und um ehrlich zu sein, ich finde überhaupt keine Bugs in solchen mit irgendeiner Häufigkeit.
Arlie Stephens
@ArlieStephens Da gibt es eine Lektion: Den Testfall zu vereinfachen, sollten Sie frühzeitig tun, wenn Sie kein Problem finden. Unabhängig davon, ob das Problem bei Ihnen oder beim anderen Code liegt, können Sie es eingrenzen. Wenn das Problem im anderen Code liegt, führt dies häufig dazu, dass "Beweise und Komponententests dies belegen".
jpmc26
8

Ich denke, ein interessanter Punkt dabei ist, dass die überwiegende Mehrheit der kommerziellen Softwarelizenzen (und in der Tat Open-Source-Softwarelizenzen) ausdrücklich angibt, dass Sie der Software nicht vertrauen können.

DIE SOFTWARE WIRD "WIE BESEHEN" OHNE JEGLICHE AUSDRÜCKLICHE ODER STILLSCHWEIGENDE GEWÄHRLEISTUNG, EINSCHLIESSLICH DER GARANTIEN FÜR HANDELBARKEIT, EIGNUNG FÜR EINEN BESTIMMTEN ZWECK UND NICHTVERLETZUNG, ZUR VERFÜGUNG GESTELLT.

Aus der Microsoft Word-Lizenzvereinbarung

. Mit Ausnahme der eingeschränkten Garantie und im Rahmen des gesetzlich zulässigen Höchstmaßes stellen Microsoft und seine Lieferanten die Software und Support-Services (sofern vorhanden) wie besehen und mit allen Fehlern zur Verfügung und lehnen hiermit alle anderen Garantien und Bedingungen ab, ob ausdrücklich, stillschweigend oder stillschweigend gesetzlich vorgeschrieben, einschließlich, aber nicht beschränkt auf implizite Garantien, Pflichten oder Bedingungen der Marktgängigkeit, der Eignung für einen bestimmten Zweck, der Zuverlässigkeit oder Verfügbarkeit, der Richtigkeit oder Vollständigkeit von Antworten, der Ergebnisse, des fachmännischen Aufwands, von Fehlen von Viren und mangelnder Fahrlässigkeit in Bezug auf die Software sowie die Bereitstellung oder Nichterbringung von Support oder anderen Diensten, Informationen, Software und verwandten Inhalten durch die Software oder auf andere Weise aufgrund der Nutzung der Software .

Im Wesentlichen besagt dieser Satz in der Lizenz für fast jede Software, die Sie speziell verwenden, dass Sie der Software nicht vertrauen können, geschweige denn dem verwendeten Compiler.

Software ist wie eine wissenschaftliche Theorie, es wird angenommen, dass sie wie angegeben funktioniert, bis dies nicht mehr der Fall ist.

Toby Allen
quelle
+1 für den Hinweis, dass in den Lizenzen angegeben ist, dass keine Software perfekt ist.
Tulains Córdova
3
Ich war erfreut, eine Abweichung von dieser Vorgehensweise in IBMs ViaVoice für Mac festzustellen. Anstelle des üblichen "Wenn es nicht funktioniert, schade" sagten sie tatsächlich etwas wie "Die Software kann nur die angegebene Leistung erbringen."
WGroleau
1
Eine Klartextübersetzung dieses speziellen Teils der Garantie lautet: "Dies könnte eine Software sein, oder es könnte ein Teil von sh * t sein. Es könnte funktionieren. Es könnte nicht funktionieren. Auch wenn es funktioniert, könnte es nicht funktionieren Tun Sie, was Sie wollen. Übrigens, wir haben möglicherweise Teile davon von jemand anderem gestohlen. Schade. Wir haben Ihr Geld und haben damit viele Anwälte eingestellt. SPIEL! ON! Nyah-nyah -nyah-nyah-nyaaah-naah! " :-)
Bob Jarvis
2
@BobJarvis: Meine Lieblingsgarantieerklärung für Open Source-Software (wie nmap IIRC) lautet "Wenn sie kaputt geht, dürfen Sie beide Teile behalten".
Peter Cordes
Diese Aussage ist in Open-Source-Software und vielen kostenlosen Closed-Source-Software allgegenwärtig. Es erscheint nicht in den meisten kommerziellen kostenpflichtigen Softwarelizenzen.
Jwg
2

Als Compiler-Autor für eine Mathematik-Sprache * kann ich meiner Erfahrung nach theoretisch sagen, dass dies nicht möglich ist. Und einige der Fehler führen einfach zu falschen Ergebnissen, wie zum Beispiel (aus meiner Schamliste) 6/3*2von rechts zu rechnen 6/(3*2)und 1 auszugeben, ohne abzustürzen oder unsinnige Kompilierungsfehler zu verursachen.

Aber meiner Meinung nach haben viele Compiler nicht so viele Fehler wie andere Software, weil:

  • Unit Tests zu schreiben ist einfach. Jede Aussage ist eine Einheit und Sie können Tests so einfach schreiben wie:test_unit("2+(-2)*(-2+1)*3+1",9);
  • Ein Programm ist eine Kombination von Anweisungen. Damit ein Programm das richtige Ergebnis ausgibt, muss jede einzelne Anweisung (meistens) das richtige Ergebnis liefern. Daher ist es sehr unwahrscheinlich, dass Fehler auftreten, während das Programm das richtige Ergebnis liefert.
  • Mit zunehmender Größe und Anzahl der geschriebenen Programme steigt die Wahrscheinlichkeit, Fehler zu finden, dramatisch an.

Für Monteure, Maschinenanweisungen usw. gilt auch das oben Gesagte; Andererseits unterliegen Verifikation und Validierung bei Chip-Design und -Produktion viel strengeren Prozessen, da es sich um ein großes Geschäft handelt: Automatisierung des elektronischen Designs .

Vor der Serienreife sollte jede CPU rigoros getestet werden, da jeder Fehler fast ein paar Millionen Dollar kostet: In der Chipherstellung fallen enorme einmalige Produktionskosten an. Unternehmen geben also viel Geld aus und schreiben eine Menge Simulationscode für ihr Design, bevor sie in Produktion gehen, obwohl dies keine 100% ige Garantie bietet - zum Beispiel: der Pentium FDIV-Fehler.

Kurz gesagt, es ist sehr unwahrscheinlich, dass Compiler, Maschinencodes usw. schwerwiegende Fehler aufweisen.

Meine bescheidene Mathe Sprache *

Gorkem
quelle
Intel testet die Hölle aus ihren CPUs heraus, indem es Sequenzen von zufälligen Anweisungen ausführt und unter anderem mit einem Softwaremodell vergleicht: tweakers.net/reviews/740/4/… . Aus diesem Grund werden häufig sehr undurchsichtige Errata veröffentlicht, bei denen es sich um eine sehr unwahrscheinliche Kombination von Anweisungen in einem ungewöhnlichen Modus handelt.
Peter Cordes
0

Makellos? Sie sind nicht. Ich habe kürzlich einige "Updates" installiert und es dauerte Monate (und einige neu programmierte Codeabschnitte), bis meine ASP.NET-Site wieder ordnungsgemäß funktionierte, da sich die Funktionsweise verschiedener grundlegender Dinge ungeklärt hat oder ein Fehler aufgetreten ist.

Sie werden jedoch getestet und dann von vielen sehr intelligenten, detailorientierten Personen verwendet, die dazu neigen, die meisten Dinge zu bemerken, zu melden und zu beheben. Stack Exchange ist ein hervorragendes Beispiel (und eine Verbesserung) dafür, wie alle Benutzer dieser Tools testen und analysieren können, wie diese erstaunlich komplexen und einfachen Tools funktionieren, zumindest was die praktische Verwendung anbelangt.

Aber makellos, nein. Obwohl Sie auch sehen können, dass die Mitarbeiter von Stack Exchange einen beeindruckenden Einblick in die Leistungsdetails und die Einhaltung von Standards sowie in die Besonderheiten erhalten, gibt es immer Fehler und Unvollkommenheiten, insbesondere dann, wenn unterschiedliche Mitarbeiter unterschiedliche Meinungen darüber haben, was ein Fehler ist.

Dronz
quelle
-1

Um zu zeigen, dass die zugrunde liegenden Systeme fehlerfrei sind Sie auch

a) Sie müssen nachweisen, dass sie einwandfrei sind

  1. Mathematischer Beweis
  2. Nur für Trivialprogramme realistisch möglich

b) Machen Sie einen ausführlichen Test

  1. Nur für Trivialprogramme und einige einfache Programme möglich
  2. Sobald ein Zeitglied in den Test eintritt, kann kein vollständiger Test durchgeführt werden, da die Zeit unbegrenzt aufgeteilt werden kann.
  3. Jenseits der trivialen Programme explodieren die möglichen Ausführungsoptionen exponentiell.

Beim Softwaretest wird der ausführliche Test nur zum Testen einiger einfacher Funktionen verwendet.

Beispiel: Sie möchten eine 8-stellige utf-8-Eingabe in einem Feld testen. Sie haben die Wahl, die Eingabe auf das 8-fache der maximalen Länge von utf-8 in Bytes zu beschränken, was 8 * 6 = 48 Bytes ergibt, um tatsächlich ein zu haben endliche Mengen von Möglichkeiten.

Sie könnten jetzt denken, dass Sie nur die 1.112.064 gültigen Codepunkte jedes der 8 Zeichen testen müssen , d. H. 1.112.064 ^ 8 (sagen wir 10 ^ 48) Tests (was schon unwahrscheinlich ist), aber Sie müssen tatsächlich jeden Wert jedes der 48 Bytes oder 256 ^ 48 testen, was ungefähr 10 ^ 120 ist, was der gleichen Komplexität wie Schach entspricht verglichen mit der Gesamtzahl der Atome im Universum von ungefähr 10 ^ 80.

Stattdessen können Sie in zunehmender Reihenfolge des Aufwands verwenden und jeder Test sollte alle vorherigen abdecken:

a) Testen Sie eine gute und eine schlechte Probe.

b) Codeabdeckung, dh. Versuchen Sie, jede Codezeile zu testen, was für die meisten Codes relativ einfach ist. Jetzt können Sie sich fragen, was die letzten 1% des Codes sind, die Sie nicht testen können ... Fehler, toter Code, Hardware-Ausnahmen usw.

c) Pfadabdeckung, alle Ergebnisse aller Zweige in allen Kombinationen werden getestet. Jetzt wissen Sie, warum die Testabteilung Sie hasst, wenn Ihre Funktionen mehr als 10 Bedingungen enthalten. Sie fragen sich auch, warum die letzten 1% nicht getestet werden können ... einige Zweige hängen von den vorherigen Zweigen ab.

d) Datentest, teste eine Anzahl von Proben mit Grenzwerten, gemeinsamen problematischen Werten und magischen Zahlen, Null, -1, 1, min +/- 1, max +/- 1, 42, rnd Werten. Wenn Sie dadurch keine Pfadabdeckung erhalten, wissen Sie, dass Sie nicht alle Werte in Ihrer Analyse erfasst haben.

Wenn Sie dies bereits tun, sollten Sie für die ISTQB-Grundlagenprüfung bereit sein.

Surt
quelle