Arithmetischer Überlauf

Der Arithmetische Überlauf (englisch arithmetic overflow) oder Zählerüberlauf (engl. counter overflow) tritt beim Rechnen in einem begrenzten Zahlenbereich immer dann auf, wenn das Ergebnis den Zahlenbereich nach oben oder unten überschreitet.

Begrenzte Zahlenbereiche kommen hauptsächlich in Computern vor, aber auch in Taschenrechnern und Kilometerzählern. Die Auswirkungen eines Überlaufs sind situationsabhängig.

Ganze Zahlen ohne Vorzeichen

Die einfachsten Datentypen in Computern sind Ganzzahlen ohne Vorzeichen. Der Datentyp Byte kann 256 unterschiedliche Werte darstellen, und diese Werte können als Zahlen im Bereich von 0 bis 255 interpretiert werden. Wenn in diesem Zahlenbereich beispielsweise die Zahlen 200 und 100 addiert werden, ist das Ergebnis 300 und damit größer als der Maximalwert 255. Bei dieser Addition passiert ein arithmetischer Überlauf, das Ergebnis und das weitere Verhalten sind situationsabhängig.

Bereits vor einer Addition $a+b$ lässt sich erkennen, ob ein Überlauf passieren wird. Ein Überlauf passiert dann, wenn die Ungleichung $a+b>{\textit {max}}$ erfüllt ist. Formt man diese Ungleichung so um, dass es in keinem der Rechenschritte zu einem Überlauf kommen kann, ergibt sich die Ungleichung $a>{\textit {max}}-b$. Beim Beispiel der Addition $200+100$ im Zahlenbereich von 0 bis 255 ergibt sich die Ungleichung $200>255-100$, umgeformt $200>155$, die Gleichung ist erfüllt, daher passiert ein Überlauf.

Für die Rechenarten Subtraktion, Multiplikation und Division ergeben sich die Prüfbedingungen durch analoge Überlegungen.

Überlauf bei ganzen Zahlen ohne Vorzeichen

Rechnung	Bedingung für Überlauf
$a+b$	$a>{\textit {max}}-b$
$a-b$	$a<b$
$a\cdot b$	$a>{\textit {max}}/b$
$a/b$	$b=0$

Bei der Addition und der Multiplikation muss nur die obere Grenze des Zahlenbereichs geprüft werden, da die untere Grenze rein mathematisch schon nicht unterschritten werden kann. Es ist zum Beispiel nicht möglich, zwei positive Zahlen zu addieren und als Ergebnis eine negative Zahl zu erhalten.

Ganze Zahlen mit Vorzeichen

Bei ganzen Zahlen mit Vorzeichen gelten analoge Überlegungen wie bei ganzen Zahlen ohne Vorzeichen. In Computern werden ganze Zahlen mit Vorzeichen im Zweierkomplement dargestellt. Dadurch liegt die Hälfte der darstellbaren Zahlen im negativen Bereich, und die 0 teilt sich mit den positiven Zahlen die andere Hälfte. Dadurch gibt es eine negative Zahl mehr als positive Zahlen.

Die Prüfbedingungen für den Überlauf müssen so ergänzt werden, dass sie beide Bereichsgrenzen abdecken. Dadurch, dass bei den Prüfbedingungen kein Überlauf passieren darf, benötigen die Ungleichungen Fallunterscheidungen und werden etwas aufwendiger als bei den Zahlen ohne Vorzeichen.

Überlauf bei ganzen Zahlen mit Vorzeichen

Rechnung	Bedingungen für Überlauf
$a+b$	$a>0\land b>0\land a>{\textit {max}}-b$ $a<0\land b<0\land a<{\textit {min}}-b$
$a-b$	$a>0\land b<0\land a>{\textit {max}}+b$ $a<0\land b>0\land a<{\textit {min}}+b$
$a\cdot b$	$a>0\land b>0\land |a|>|{\textit {max}}|/|b|$ $a>0\land b<0\land |a|>|{\textit {min}}|/|b|$ $a<0\land b>0\land |a|>|{\textit {min}}|/|b|$ $a<0\land b<0\land |a|>|{\textit {max}}|/|b|$
$a/b$	$b=0$ $a={\textit {min}}\land b=-1$

Die Betragsfunktion, die beim Prüfen der Multiplikation verwendet wird, muss einen Wertebereich haben, der groß genug ist, dass beim Berechnen von $|{\textit {min}}|$ kein Überlauf auftritt. Im Zweierkomplement erfüllt der entsprechende vorzeichenlose Datentyp diese Bedingung.

Gleitkommazahlen

Der Wertebereich von Gleitkommazahlen ist deutlich umfangreicher als der von Ganzzahlen, auf Kosten der Genauigkeit. Bei einem Überlauf wird in IEEE 754 mit ±∞ weitergerechnet.

Auswirkungen

Die Auswirkungen eines Überlaufs sind situationsabhängig und reichen von einem Weiterrechnen mit falschen Zahlen über Programmabstürze bis zu Sicherheitslücken in Computern.

Modulo-Rechnung

Die überzähligen Stellen des Ergebnisses werden verworfen, alle weiteren Berechnungen finden auf den verbleibenden Stellen statt. Eine mögliche Folge ist, dass zwei positive Zahlen addiert werden und das Ergebnis eine negative Zahl ist.

Beispiele:

• Kilometerzähler im Auto
• Die Programmiersprache C bei vorzeichenlosen Datentypen
• Die Programmiersprache Java bei allen ganzzahligen Datentypen

Sättigung

Wenn das Ergebnis größer als der maximal darstellbare Wert ist, wird der maximal darstellbare Wert übernommen. Wenn das Ergebnis kleiner als der minimal darstellbare Wert ist, wird der minimal darstellbare Wert übernommen.

Beispiele:

• Signalverarbeitung im Audio-Bereich, um Knackgeräusche zu vermeiden.

Fehlermarker

Wenn das Ergebnis nicht im darstellbaren Bereich liegt, wird es als fehlerhaft markiert. Nachfolgende Rechenschritte leiten den Fehlermarker weiter, so dass auch das Endergebnis ein Fehlermarker ist.

Ausnahmebehandlung

Der normale Programmablauf wird unterbrochen und stattdessen bei einer Routine zur Fehlerbehandlung fortgesetzt, siehe Laufzeitfehler, Ausnahmebehandlung.

Undefiniertes Verhalten

Die Programmiersprachen C und C++ definieren Überläufe bei vorzeichenbehafteten Zahlen als Undefiniertes Verhalten, jede weitere Aussage über einen möglichen Programmablauf ist damit hinfällig.

Sicherheitslücken

Ganzzahlüberläufe (englisch integer overflow) können 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.

Programmierschnittstelle

Beim Programmieren in Assemblersprachen hat der Programmierer direkten Zugriff auf den Prozessor, insbesondere die Arithmetisch-logische Einheit und deren Statusregister, in dem festgehalten wird, ob im letzten Rechenschritt ein Überlauf auftrat. In höheren Programmiersprachen ist dieser direkte Zugriff nicht möglich, dort muss eine Überlauferkennung entweder von der Laufzeitumgebung bereits abgefangen werden oder selbst programmiert werden.

Addition zweier positiver Zahlen	Addition negativer Zahlen mit Überlauf	Addition negativer Zahlen ohne Überlauf
${\begin{array}{cllllllr}&&0&1&0&1&&5_{10}\\+&&0_{\color {Red}1}&1&0_{\color {Red}1}&1&&5_{10}\\\hline =&(0)&1&0&1&0&&-6_{10}\\\end{array}}$	${\begin{array}{crlllllr}&&1&0&1&1&&-5_{10}\\+&{}_{\color {Red}1}&1&0_{\color {Red}1}&1_{\color {Red}1}&1&&-5_{10}\\\hline =&(1)&0&1&1&0&&6_{10}\\\end{array}}$	${\begin{array}{crlllllr}&&1&1&1&1&&-1_{10}\\+&{}_{\color {Red}1}&1_{\color {Red}1}&1_{\color {Red}1}&0_{\color {Red}1}&1&&-3_{10}\\\hline =&(1)&1&1&0&0&&-4_{10}\\\end{array}}$

Alle in 4 Bit darstellbaren Zahlen als Kreis; addiert man z. B. 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.

Siehe auch

• Überlaufbit
• Der Übertrag (engl. carry) entsteht beim Rechnen mit einzelnen Ziffern, er zeigt keinen Fehlerzustand an.
• Der Unterlauf tritt auf, wenn das Ergebnis eines Rechenschritts zwar innerhalb des Gültigkeitsbereichs liegt, aber betragsmäßig so klein (nah bei 0) ist, dass er aufgrund zu geringer Genauigkeit des verwendeten Datentyps fälschlicherweise zu 0 wird.
• Langzahlarithmetik, um die Begrenzung auf eine feste Anzahl von Ziffern zu umgehen.
• Bei Computern, die vom Jahr-2038-Problem betroffen sind, springen Datum und Uhrzeit auf 1901 zurück.
• Arithmetischer Unterlauf
• Pufferüberlauf

Literatur

• Blexim: Basic Integer Overflows. In: Phrack-Magazin. 11, Nr. 60, Februar 2002