Arithmetischer Überlauf

Der Arithmetische Überlauf (englisch arithmetic overflow) oder Zählerüberlauf (engl. counter overflow) ist ein Begriff aus der Informatik. Solch ein Überlauf tritt auf, wenn das Ergebnis einer Berechnung für den gültigen Zahlenbereich zu groß ist, um noch richtig interpretiert werden zu können.

Zumeist wird man dem Überlauf beim Rechnen mit Zweierkomplementzahlen begegnen. So kann es passieren, dass bei der Addition zweier Zahlen mit gleichem Vorzeichen eine Zahl mit anderem Vorzeichen entsteht. In diesem Fall setzt der Prozessor das Überlaufbit. Mit einigen Prozessoren und Programmiersprachen kann ein Überlauf durch einen Laufzeitfehler oder eine Ausnahmebehandlung (Exception) aufgefangen werden.

Der Überlauf hängt immer von der verwendeten Zahlendarstellung ab. Er ist keinesfalls mit dem Übertrag (engl. carry) zu verwechseln.

Ganzzahlüberlauf

Ein Ganzzahlüberlauf (engl. integer overflow) tritt auf, wenn ein Computer Berechnungen mit begrenzter Stellenzahl durchführt und das Rechenergebnis zur Darstellung mehr Stellen erfordert.

Die Stellenanzahl und damit der Wertebereich ist durch das Rechenwerk begrenzt. Das Rechenwerk heutiger Computer ist meist für 32 oder 64 Binärstellen ausgelegt. Tritt hier ein Ganzzahlüberlauf auf, wird das im Statusregister des Prozessors registriert; dieser Fall kann vom Programmierer festgestellt werden.

Ein anderer Fall liegt vor, wenn ein Rechenergebnis in einer Variablen gespeichert wird, die weniger Stellen als das Rechenwerk aufweist. Dieser Fall wird vom Prozessor nicht automatisch erkannt, die Variable erhält einen falschen Wert.

Nur durch die Verwendung von Funktionsbibliotheken ist es möglich, Berechnungen mit Millionen von Stellen durchzuführen ohne einen Ganzzahlüberlauf zu erreichen.

Ein Beispiel aus der Programmiersprache C: Der Datentyp unsigned char umfasst in der Regel 8 Bit und hat einen Wertebereich von 0 bis 255.^[1]

unsigned char a = 255;
unsigned char b = 2;
unsigned char Ergebnis = a + b;

Die zugehörige duale Rechnung veranschaulicht den Ganzzahlüberlauf:

  11111111 (a)
+ 00000010 (b)
----------
 100000001 (Ergebnis)

Die vordere Eins, das neunte Bit, ist nicht in den 8 Bit des gewählten Datentyps enthalten. Betrachtet man nur diese letzten 8 Bit, so erhält man 00000001, also 1 und nicht 257. Selbst wenn die Zahlenwerte bei der Übersetzung des Programmcodes schon feststehen, ignorieren manche C-Compiler diese Überläufe, was zu falschen Ergebnissen führt. Daher sollte der Datentyp immer ausreichend groß gewählt werden.

Bei plattformunabhängiger Programmierung sollte der Ganzzahlüberlauf nicht absichtlich benutzt werden, da der Wertebereich der Datentypen und damit der Punkt des Überlaufs auf den Zielsystemen unterschiedlich sein kann.

Beispiel: 32 Bit Integer

Der auf 32-Bit-Prozessoren häufig verwendete Ganzzahl-Datentyp Integer kann im Zweierkomplement die Werte –2³¹ = –2.147.483.648 bis +(2³¹)–1 = +2.147.483.647 darstellen. Wird nun zu +2.147.483.647 (Binär 01111111 11111111 11111111 11111111) eins dazugezählt, erhält man nicht wie erwartet +2.147.483.648, sondern –2.147.483.648, da der Binärwert 10000000 00000000 00000000 00000000 als negative Zahl interpretiert wird. Ein solcher Überlauf ist auch die Ursache für das Jahr-2038-Problem.

Beispiel: 4 Bit im Zweierkomplement

Im Zweierkomplement sind positive und negative Zahlen darstellbar, sodass die Subtraktion auf die Addition zurückgeführt werden kann. Es sind 3 Fälle zu betrachten:

Addition zweier positiver Zahlen	Addition negativer Zahlen mit Überlauf	Addition negativer Zahlen ohne Überlauf
${\begin{matrix} \ &{\ }_{\ } &0_{\ } &1_{\ } &0_{\ } &1 &&& 5_{10} \\ + &{\ }_{\ } &0_{\color{Red}1} &1_{\ } &0_{\color{Red}1} &1 &&& 5_{10} \end{matrix}\over \begin{matrix} \quad &{(0)}_{\ } & 1_{\ } &0_{\ } &1_{\ } &0_{\ } &&& -6_{10} \end{matrix}}$	${\begin{matrix} \ &{\ }_{\ } &1_{\ } &0_{\ } & 1_{\ } &1 &&& -5_{10} \\ + &{\ }_{\color{Red}1} &1_{\ } & 0_{\color{Red}1} & 1_{\color{Red}1} & 1 &&& -5_{10} \end{matrix}\over \begin{matrix} \quad &{(1)}_{\ } & 0_{\ } & 1_{\ } & 1_{\ } & 0_{\ } &&& 6_{10} \end{matrix}}$	${{\begin{matrix}\ &{\ }_{\ }&1_{\ }&1_{\ }&1_{\ }&1&&&-1_{10}\\+&{\ }_{\color {Red}1}&1_{\color {Red}1}&1_{\color {Red}1}&0_{\color {Red}1}&1&&&-3_{10}\end{matrix}} \over {\begin{matrix}\quad &{(1)}_{\ }&1_{\ }&1_{\ }&0_{\ }&0_{\ }&&&-4_{10}\end{matrix}}}$

Alle in 4 Bit darstellbaren Zahlen als Kreis; addiert man zB. 5 und 5, sucht man sich die dargestellte 5 und geht im Uhrzeigersinn 5 Einheiten weiter, es kommt zum "Überlaufen" des Kreises und man landet bei −6.

Verallgemeinerung

Operation	richtiges Ergebnis	Überlauf
A + B	$c_n = 0 , c_{n-1} = 0$	$c_n = 0 , c_{n-1} = 1$
A - B	$c_n = c_{n-1}$	nicht möglich
-A - B	$c_n = 1 , c_{n-1} = 1$	$c_n = 1 , c_{n-1} = 0$

Man muss sich stets die letzten beiden Überträge anschauen, hier $c_{n}$ und $c_{n-1}$ genannt. Sind diese ungleich, dann ist das Ergebnis falsch, als Resultat eines Überlaufes. Bei der Addition einer positiven und einer negativen Zahl kann dies nie der Fall sein.

Folgerung

In einer 4-Bit-Architektur, die mit dem Zweierkomplement arbeitet, ist z.B. die Dezimalzahl 10 nicht dual abbildbar.

Manche Prozessoren können einen Überlauf durch ein Überlaufbit registrieren.

Gefahren

Ganzzahlüberläufe können indirekt ein sicherheitsrelevantes Problem darstellen, wenn sie Teil eines Programmfehlers sind. Insbesondere wenn die fehlerhafte Berechnung zur Bestimmung der Größe eines Puffers genutzt wird oder die Adressierung eines Feldes betrifft. Dann können daraus Pufferüberläufe resultieren oder es einem Angreifer ermöglichen den Stack zu überschreiben.

Einen Spezialfall stellt der sogenannte signedness bug dar. Er tritt auf, wenn eine vorzeichenbehaftete Ganzzahl (signed) als nichtnegative Zahl (unsigned) interpretiert wird.

Die Tragweite von Ganzzahlüberläufen liegt oft auch darin, dass sie nicht erkannt werden können, nachdem sie erfolgt sind. Derart fehlerbehaftete Stellen sind im Programmcode deshalb nur schwer zu finden.

Siehe auch

Pufferüberlauf

Anmerkungen

↑ Dies wird jedoch nicht vom C-Standard vorgeschrieben. Deshalb gibt es auch Systeme und zugehörige C-Compiler, bei denen ein char bzw. unsigned char eine abweichende Anzahl an Bit und demzufolge auch einen abweichenden Wertebereich hat.

Basierend auf einem Artikel in:

Wikipedia.de