Warum das Portieren über einen Ganzzahlüberlauf keine gute Idee ist

Dieser Artikel konzentriert sich auf undefiniertes Verhalten und Compileroptimierungen, insbesondere im Zusammenhang mit einem vorzeichenbehafteten Ganzzahlüberlauf.

Anmerkung des Übersetzers: Auf Russisch gibt es keine eindeutige Entsprechung im verwendeten Kontext des Wortes „Wrap“ / „Wrapping“. Es gibt einen mathematischen Begriff " Übertragung ", der dem beschriebenen Phänomen nahe kommt, und der Begriff "Übertragsflag" ist ein Mechanismus zum Setzen eines Flags in Prozessoren während eines Ganzzahlüberlaufs. Eine andere Übersetzungsoption kann der Ausdruck "Drehung / Umdrehen / Umdrehen um Null" sein. Es spiegelt die Bedeutung von "Wrap" besser wider als "Carry", weil zeigt den Übergang von Zahlen beim Überlaufen vom positiven zum negativen Bereich. Wie sich jedoch herausstellte, sehen diese Wörter im Text für Testleser ungewöhnlich aus. Der Einfachheit halber werden wir in Zukunft das Wort "Übertragung" als Übersetzung des Begriffs "Wrap" verwenden.

Compiler der C-Sprache (und C ++) orientieren sich in ihrer Arbeit zunehmend am Konzept des unbestimmten Verhaltens - der Vorstellung, dass das Verhalten eines Programms für einige Operationen nicht durch den Standard geregelt wird und dass der Compiler beim Generieren von Objektcode das Recht hat, von der Annahme auszugehen, dass das Programm solche Operationen nicht ausführt. Viele Programmierer haben gegen diesen Ansatz Einwände erhoben, da sich der generierte Code in diesem Fall möglicherweise nicht als Autor des beabsichtigten Programms verhält. Dieses Problem wird immer akuter, da Compiler ausgefeiltere Optimierungsmethoden verwenden, die wahrscheinlich auf dem Konzept des unbestimmten Verhaltens basieren werden.

In diesem Zusammenhang ist ein Beispiel mit einem vorzeichenbehafteten Ganzzahlüberlauf indikativ. Die meisten C-Entwickler schreiben Code für Maschinen, die zusätzlichen Code zur Darstellung von Ganzzahlen verwenden, und die Addition und Subtraktion in dieser Darstellung wird auf genau dieselbe Weise in vorzeichenloser Arithmetik implementiert. Wenn die Summe von zwei positiven Ganzzahlen mit einem Vorzeichen überläuft - das heißt, sie wird größer als der Typ -, gibt der Prozessor einen Wert zurück, der als binäres Komplement der vorzeichenbehafteten Zahl interpretiert wird und als negativ betrachtet wird. Dieses Phänomen wird als "Übertragung" bezeichnet, da das Ergebnis, das die Obergrenze des Wertebereichs erreicht, "übertragen" wird und an der unteren Grenze beginnt.

Aus diesem Grund können Sie diesen Code manchmal in C sehen:

int b = a + 1000; if (b < a) { //  puts("input too large!"); return; } 

Die Aufgabe der if-Anweisung besteht darin, eine Überlaufbedingung zu erkennen (in diesem Fall nach dem Hinzufügen von 1000 zum Wert der Variablen a ) und einen Fehler zu melden. Das Problem ist, dass in C ein vorzeichenbehafteter Ganzzahlüberlauf einer der Fälle von undefiniertem Verhalten ist. Seit einiger Zeit betrachten Compiler solche Bedingungen immer als falsch: Wenn Sie einer anderen Zahl 1000 (oder eine andere positive Zahl) hinzufügen, kann das Ergebnis nicht unter dem Anfangswert liegen. Wenn ein Überlauf auftritt, liegt ein undefiniertes Verhalten vor, und dies nicht zuzulassen, ist (anscheinend) bereits das Anliegen des Programmierers. Daher kann der Compiler entscheiden, dass der bedingte Operator zu Optimierungszwecken vollständig entfernt werden kann (schließlich ist die Bedingung immer falsch, sie wirkt sich auf nichts aus, sodass Sie darauf verzichten können).

Das Problem ist, dass der Compiler bei dieser Optimierung die vom Programmierer speziell hinzugefügte Prüfung entfernt hat, um undefiniertes Verhalten zu erkennen und zu verarbeiten. Hier können Sie sehen, wie dies in der Praxis geschieht. (Hinweis: Die Website godbolt.org, auf der das Beispiel gehostet wird, ist sehr cool! Sie können den Code bearbeiten und sofort sehen, wie verschiedene Compiler ihn verarbeiten, und es gibt viele davon. Experimentieren Sie!). Beachten Sie, dass der Compiler die Prüfung auf Überlauf nicht entfernt, wenn Sie den Typ in vorzeichenlos ändern, da das Verhalten mit vorzeichenlosem Überlauf in C definiert ist (genauer gesagt, bei vorzeichenloser Arithmetik wird das Ergebnis übertragen, sodass ein Überlauf tatsächlich nicht auftritt).

Also ist das falsch? Jemand sagt ja, obwohl es offensichtlich ist, dass viele Compiler-Entwickler diese Entscheidung für legal halten. Wenn ich das richtig verstehe, lauten die Hauptargumente der Unterstützer (edit: implementierungsabhängig) der Übertragung während des Überlaufs wie folgt:

• Überlaufen ist ein nützliches Verhalten.
• Migration ist das Verhalten, das Programmierer erwarten.
• Die Semantik des unbestimmten Überlaufverhaltens bietet keinen spürbaren Vorteil.
• Der C-Sprachstandard für undefiniertes Verhalten ermöglicht es der Implementierung, "die Situation vollständig zu ignorieren und das Ergebnis ist unvorhersehbar". Dies gibt dem Compiler jedoch nicht das Recht, den Code unter der Annahme zu optimieren, dass die Situation mit undefiniertem Verhalten überhaupt nicht auftritt.

Lassen Sie uns nacheinander jeden Punkt analysieren:

Überlaufmigration - Nützliches Verhalten?

Die Migration ist vor allem dann nützlich, wenn Sie einen bereits aufgetretenen Überlauf verfolgen müssen. (Wenn es andere Probleme gibt, die durch Übertragung gelöst werden können und nicht mit vorzeichenlosen Ganzzahlvariablen gelöst werden können, kann ich mich nicht sofort an solche Beispiele erinnern, und ich vermute, dass es nur wenige davon gibt). Während die Übertragung das Problem der Verwendung falsch übergelaufener Variablen wirklich vereinfacht, ist sie definitiv kein Allheilmittel (denken Sie an die Multiplikation oder Addition von zwei unbekannten Größen mit einem unbekannten Vorzeichen).

In trivialen Fällen, in denen Sie mit der Übertragung lediglich den aufgetretenen Überlauf verfolgen können, ist es auch nicht schwierig, im Voraus zu wissen, ob er überhaupt auftreten wird. Unser Beispiel kann wie folgt umgeschrieben werden:

 if (a > INT_MAX - 1000) { //    puts("input too large!"); return; } int b = a + 1000; 

Das heißt, anstatt die Summe zu berechnen und dann herauszufinden, ob ein Überlauf aufgetreten ist oder nicht, und das Ergebnis auf mathematische Konsistenz zu überprüfen, können Sie überprüfen, ob die Summe die maximale Anzahl überschreitet, zu der der Typ passt. (Wenn das Vorzeichen beider Operanden unbekannt ist, muss die Überprüfung sehr kompliziert sein, dies gilt jedoch auch für die Überprüfung während der Übertragung.)

Angesichts all dessen finde ich das Argument nicht überzeugend, dass die Übertragung in den meisten Fällen nützlich ist.

Ist Migration das Verhalten, das Programmierer erwarten?

Es ist schwieriger, mit diesem Argument zu argumentieren, da es offensichtlich ist, dass der Code von mindestens einigen C-Programmierern eine Übertragungssemantik mit einem vorzeichenbehafteten Ganzzahlüberlauf voraussetzt. Diese Tatsache allein reicht jedoch nicht aus, um eine solche Semantik als vorzuziehen zu betrachten (beachten Sie, dass Sie bei einigen Compilern diese bei Bedarf aktivieren können).

Eine offensichtliche Lösung für das Problem (Programmierer erwarten dieses Verhalten) besteht darin, den Compiler zu warnen, wenn er den Code optimiert, vorausgesetzt, es gibt kein undefiniertes Verhalten. Wie wir im Beispiel auf godbolt.org über den obigen Link gesehen haben, tun Compiler dies leider nicht immer (Gcc-Version 7.3 - ja, aber Version 8.1 - nein, es gibt also einen Schritt zurück).

Gibt die Semantik des unbestimmten Überlaufverhaltens keinen spürbaren Vorteil?

Wenn diese Bemerkung in allen Fällen zutrifft, würde sie als starkes Argument für die Tatsache dienen, dass Compiler standardmäßig die Übertragungssemantik einhalten sollten, da es wahrscheinlich besser wäre, Überlaufprüfungen zuzulassen, auch wenn dieser Mechanismus aus technischer Sicht falsch ist - obwohl wäre, weil es in möglicherweise defektem Code verwendet werden kann.

Ich gehe davon aus, dass diese Optimierung (Entfernen von Überprüfungen mathematisch widersprüchlicher Bedingungen) in normalen C-Programmen oft vernachlässigt werden kann, da ihre Autoren die beste Leistung anstreben und den Code dennoch manuell optimieren: Das heißt, wenn es offensichtlich ist, dass diese if-Anweisung eine Bedingung enthält , was niemals wahr sein wird, wird der Programmierer es wahrscheinlich selbst entfernen. Tatsächlich fand ich heraus, dass in mehreren Studien die Wirksamkeit einer solchen Optimierung in Frage gestellt, getestet und im Rahmen von Kontrolltests als praktisch unbedeutend befunden wurde. Obwohl diese Optimierung in der Sprache C fast nie einen Vorteil bringt, sind Codegeneratoren und Compileroptimierungen größtenteils universell und können in anderen Sprachen verwendet werden - und für sie ist diese Schlussfolgerung möglicherweise falsch. Nehmen wir die C ++ - Sprache mit ihrer Tradition, sich auf den Optimierer zu verlassen, um redundante Konstruktionen im Vorlagencode zu entfernen, anstatt sie manuell auszuführen. Es gibt jedoch Sprachen, die vom Transporter in C konvertiert werden, und der redundante Code in ihnen wird auch von C-Compilern optimiert.

Selbst wenn Sie ständig nach Überläufen suchen, ist es keineswegs eine Tatsache, dass die direkten Kosten für die Übertragung ganzzahliger Variablen selbst auf Computern mit zusätzlichem Code minimal sind. Die Mips-Architektur kann beispielsweise nur arithmetische Operationen in Registern fester Größe (32 Bit) ausführen. Der Typ short int hat in der Regel eine Größe von 16 Bit und char - 8 Bit; Wenn eine Variable eines dieser Typen im Register gespeichert ist, vergrößert sich ihre Größe. Um sie korrekt zu übertragen, muss mindestens eine zusätzliche Operation ausgeführt und möglicherweise ein zusätzliches Register verwendet werden (um die entsprechende Bitmaske aufzunehmen). Ich muss zugeben, dass ich mich lange nicht mehr mit dem Code für Mips befasst habe, daher bin ich mir nicht sicher, welche Kosten diese Vorgänge genau verursachen, aber ich bin mir sicher, dass er nicht Null ist und dass bei anderen RISC-Architekturen dieselben Probleme auftreten können.

Verbietet ein Sprachstandard die Vermeidung von Variablenumbruch, wenn dies von der Architektur beabsichtigt ist?

Wenn Sie schauen, ist dieses Argument besonders schwach. Sein Kern ist, dass der Standard der Implementierung (dem Compiler) angeblich erlaubt, "unbestimmtes Verhalten" nur in begrenztem Umfang zu interpretieren. Im Text der Norm selbst - in dem Fragment, auf das sich die Befürworter der Übertragung berufen - wird Folgendes gesagt (dies ist Teil der Definition des Begriffs „unbestimmtes Verhalten“):

HINWEIS: Undefiniertes Verhalten kann darin bestehen, die Situation vollständig zu ignorieren, während das Ergebnis unvorhersehbar ist.

Die Idee ist, dass die Worte „die Situation vollständig ignorieren“ nicht darauf hindeuten, dass ein Ereignis, das zu undefiniertem Verhalten führt - beispielsweise ein Überlauf während des Hinzufügens -, nicht auftreten kann, sondern dass der Compiler in diesem Fall weiterhin wie in arbeiten sollte als nie passiert, aber berücksichtigen Sie auch das Ergebnis, das sich herausstellt, wenn er dem Prozessor eine Anfrage zur Durchführung einer solchen Operation sendet (mit anderen Worten, als ob der Quellcode auf einfache und naive Weise in Maschinencode übersetzt worden wäre).

Zunächst ist zu beachten, dass dieser Text als „Anmerkung“ angegeben wird und daher gemäß der in der Einleitung zur Norm genannten ISO-Richtlinie nicht normativ ist (dh nichts vorschreiben kann):

In Übereinstimmung mit Teil 3 der ISO / IEC-Richtlinien dienen dieses Vorwort, die Einführung in den Text, die Anmerkungen, Fußnoten und Beispiele auch nur zu Informationszwecken.

Da diese Passage „unbestimmtes Verhalten“ eine Notiz ist, schreibt sie nichts vor. Bitte beachten Sie, dass die aktuelle Definition von „unbestimmtem Verhalten“ lautet:

Verhalten aufgrund der Verwendung eines unerträglichen oder falschen Software-Designs oder falscher Daten, für die diese Internationale Norm keine Anforderungen stellt .

Ich habe die Hauptidee hervorgehoben: Es werden keine Anforderungen an unbestimmtes Verhalten gestellt. Die Liste der „möglichen Arten von undefiniertem Verhalten“ in der Notiz enthält nur Beispiele und kann nicht die endgültige Vorschrift sein. Der Ausdruck „stellt keine Anforderungen“ kann nicht anders interpretiert werden.

Einige, die dieses Argument entwickeln, argumentieren, dass das Sprachkomitee bei der Formulierung dieser Wörter unabhängig vom Text bedeutete, dass das Verhalten als Ganzes so weit wie möglich der Architektur der Hardware entsprechen sollte, auf der das Programm ausgeführt wird, was eine naive Übersetzung impliziert in Maschinencode. Dies mag zutreffen, obwohl ich keine Beweise (zum Beispiel historische Dokumente) für dieses Argument gesehen habe. Selbst wenn dies so wäre, ist es keine Tatsache, dass diese Aussage für die aktuelle Version des Textes gilt.

Letzte Gedanken

Die Argumente für die Übertragung sind weitgehend unhaltbar. Das vielleicht stärkste Argument ergibt sich, wenn wir sie kombinieren: Weniger erfahrene Programmierer (die die Feinheiten der C-Sprache und das unbestimmte Verhalten darin nicht kennen) zählen manchmal auf die Portierung und verringern die Leistung nicht - obwohl letzteres nicht in allen Fällen zutrifft und der erste Teil nicht schlüssig ist wenn Sie es separat betrachten.

Persönlich würde ich es vorziehen, Überläufe zu blockieren (Einfangen) anstatt zu wickeln. Das heißt, das Programm stürzt ab und funktioniert nicht weiter - mit unsicherem Verhalten oder möglicherweise falschen Ergebnissen, da in beiden Fällen eine Sicherheitsanfälligkeit auftritt. Eine solche Lösung wird natürlich die Leistung auf den meisten (?) Architekturen, insbesondere auf x86, geringfügig verringern, andererseits werden Überlauffehler sofort erkannt und sie können auf diesem Weg keine falschen Ergebnisse nutzen oder falsche Ergebnisse erzielen Programme. Darüber hinaus könnten Compiler mit diesem Ansatz theoretisch redundante Überlaufprüfungen sicher entfernen, da dies sicherlich nicht passieren wird, obwohl, wie ich sehe, weder Clang noch GCC diese Gelegenheit nutzen.

Glücklicherweise sind sowohl Unterbrechung als auch Portierung in dem Compiler implementiert, den ich am häufigsten verwende, nämlich GCC. Um zwischen den Modi zu wechseln, werden die Befehlszeilenargumente -ftrapv und -fwrapv verwendet.

Natürlich gibt es viele Aktionen, die zu undefiniertem Verhalten führen - ein ganzzahliger Überlauf ist nur eine davon. Ich halte es überhaupt nicht für sinnvoll, all diese Fälle als unbestimmtes Verhalten zu interpretieren, und ich bin sicher, dass es viele spezifische Situationen gibt, in denen die Semantik durch die Sprache bestimmt oder zumindest dem Ermessen der Implementierungen überlassen werden sollte. Und ich habe Angst vor zu freien Interpretationen dieses Konzepts durch Compilerhersteller: Wenn das Verhalten des Compilers nicht den intuitiven Vorstellungen der Entwickler entspricht, insbesondere derjenigen, die den Text des Standards persönlich lesen, kann dies zu echten Fehlern führen. Wenn der Leistungsgewinn in diesem Fall vernachlässigbar ist, ist es besser, solche Interpretationen aufzugeben. In einem der folgenden Beiträge werde ich mich wahrscheinlich mit einigen dieser Probleme befassen.

Nachtrag (vom 24. August 2018)

Mir wurde klar, dass vieles davon besser geschrieben werden könnte. Im Folgenden fasse ich meine Worte kurz zusammen, erkläre sie und füge ein paar kleinere Bemerkungen hinzu:

• Ich habe nicht argumentiert, dass unbestimmtes Verhalten dem Überlauf vorzuziehen ist - vielmehr ist die Übertragung in der Praxis nicht viel besser als unbestimmtes Verhalten. Insbesondere können Sicherheitsprobleme im ersten und im zweiten Fall auftreten - und ich wette, dass viele der Schwachstellen, die durch nicht rechtzeitig abgefangene Überläufe verursacht wurden (mit Ausnahme derjenigen, für die der Compiler für das Löschen fehlerhafter Überprüfungen verantwortlich ist), tatsächlich entstanden sind - aufgrund der Übertragung des Ergebnisses, jedoch nicht aufgrund eines undefinierten Verhaltens im Zusammenhang mit dem Überlauf.
• Der einzige wirkliche Vorteil der Übertragung besteht darin, dass Überlaufprüfungen nicht gelöscht werden. Obwohl Sie auf diese Weise den Code vor einigen Angriffsszenarien schützen können, ist es wahrscheinlich, dass einige der Überläufe überhaupt nicht überprüft werden (d. H. Der Programmierer vergisst, eine solche Überprüfung hinzuzufügen) und unbemerkt bleiben.
• Wenn das Sicherheitsproblem nicht so wichtig ist und die hohe Geschwindigkeit des Programms in den Vordergrund tritt, führt undefiniertes Verhalten zumindest in einigen Fällen zu einer rentableren Optimierung und einer höheren Produktivitätssteigerung. Wenn die Sicherheit an erster Stelle steht, ist die Portierung mit Sicherheitslücken behaftet.
• Wenn Sie also zwischen Unterbrechung, Übertragung und undefiniertem Verhalten wählen, gibt es nur sehr wenige Aufgaben, bei denen die Übertragung hilfreich sein kann.
• Was die Überprüfung des aufgetretenen Überlaufs betrifft, glaube ich, dass das Verlassen schädlich ist, da dadurch der falsche Eindruck entsteht, dass sie funktionieren und immer funktionieren werden. Durch das Unterbrechen von Überläufen wird dieses Problem vermieden. angemessene Warnungen - mildern Sie es.
• Ich denke, dass jeder Entwickler, der sicherheitskritischen Code schreibt, im Idealfall die Semantik der Sprache, in der er schreibt, gut beherrschen und sich ihrer Fallstricke bewusst sein sollte. Für C bedeutet dies, dass Sie die Semantik des Überlaufs und die Feinheiten des undefinierten Verhaltens kennen müssen. Es ist traurig, dass einige Programmierer nicht auf dieses Niveau angewachsen sind.
• Ich bin auf die Behauptung gestoßen, dass "die meisten C-Programmierer Migration als Standardverhalten erwarten", aber ich kenne die Beweise dafür nicht. (In dem Artikel habe ich "einige Programmierer" geschrieben, weil ich einige Beispiele aus dem wirklichen Leben kenne, und im Allgemeinen bezweifle ich, dass irgendjemand damit streiten wird).
• Es gibt zwei verschiedene Probleme: Was der C-Sprachstandard erfordert und welche Compiler implementieren sollten. Mir gefällt (allgemein), wie der Standard undefiniertes Überlaufverhalten definiert. In diesem Beitrag spreche ich darüber, was Compiler tun sollten.
• Wenn der Überlauf unterbrochen wird, muss nicht jeder Vorgang überprüft werden. Im Idealfall verhält sich das Programm mit diesem Ansatz entweder konsistent in Bezug auf mathematische Regeln oder funktioniert nicht mehr. In diesem Fall wird das Vorhandensein eines „vorübergehenden Überlaufs“ möglich, der nicht zum Auftreten eines falschen Ergebnisses führt. Dann können sowohl der Ausdruck a + b - b als auch der Ausdruck (a * b) / b auf a optimiert werden (ersterer ist auch während der Übertragung möglich, letzterer ist jedoch nicht mehr vorhanden).

Hinweis Die Übersetzung des Artikels wird mit Genehmigung des Autors im Blog veröffentlicht. Originaltext: Davin McCall " Wrap on Integer Overflow ist keine gute Idee ".

Zusätzliche verwandte Links vom PVS-Studio-Team:

1. Andrey Karpov. Undefiniertes Verhalten ist näher als Sie denken .
2. Will Dietz, Peng Li, John Regehr und Vikram Adve. Grundlegendes zum Integer-Überlauf in C / C ++ .
3. V1026. Die Variable wird in der Schleife inkrementiert. Bei einem vorzeichenbehafteten Ganzzahlüberlauf tritt ein undefiniertes Verhalten auf .
4. Stapelüberlauf Ist der vorzeichenbehaftete Ganzzahlüberlauf in C ++ immer noch undefiniertes Verhalten?