[A] Integer

rüdiger

<!---
Den Artikel habe ich vor ungefähr einem Jahr angefangen zu schreiben und ungefähr seit der Zeit nicht mehr angefasst. Naja, ich poste einfach mal hier, was ich bisher habe. Ist natürlich noch voller Fehler und Ungenauigkeiten. Aber so bin ich vielleicht motiviert den Artikel fertig zu machen (fall ihr das Thema überhaupt interessant findet).

Hmm, einen vernünftigen Titel brauch das ganze natürlich auch noch.

Erklären:
* Vorzeichen
* Vorzeichenlos
* Andere Programmiersprachen?
* Sicherheitslücke durch Truncation
-->

Integer

Inhalt

Einleitung und Motivation
Was ist ein Integer und welche Integer-Datentypen gibt es?
Darstellung von Integern in Computern
Zweierkomplement
Einerkomplement
BCD
Weiter Darstellungen
Probleme mit Integern
Rundung (Truncation)
Überläufe (Overflows)/Unterläufe (Underflows)
Signed-Overflow
Vergleiche zwischen signed/unsigned
Der kleinste Wert und der Betrag (abs)
Probleme für die Sicherheit durch Integer
Allgemeine Tipps
Quellen und Links

1. Einleitung und Motivation

Integer-Datentypen sind in den meisten Programmiersprachen fundamental. Bei unserer täglichen Programmierarbeit hantieren wir oft mit ihnen, ohne uns wirklich Gedanken über die Typen oder die Darstellung im Computer zu machen. Dieser unbedachte Umgang mit Integern kann aber zu Problemen und sogar Sicherheitslücken führen.

In diesem Artikel soll Ihnen nun etwas Hintergrundwissen zu den Integern und auch den möglichen Probleme vermittelt werden. Dabei bezieht sich der Artikel zum größten Teil auf C und C++. Durch verweise auf andere Programmiersprachen, sollen aber auch alternative Konzepte oder Versuche gewisse Probleme zu vermeiden aufgezeigt werden.

In dem Artikel werde ich nicht auf BigInteger-Typen, also Datentypen die beliebig große Integer darstellen können, eingehen, auch wenn einige der hier besprochenen Probleme auch auf sie zutreffen.

2. Was ist ein Integer?

Integer ist das englische Wort für Ganzzahl. Mathematisch gesehen also alle Zahlen $\ldots , -3, -2, -1, 0, 1, 2, 3,\ldots$ . Die Menge der ganzen Zahlen wird in der Mathematik mit dem Symbol $\mathbb{Z}$ dargestellt.

Im Gegensatz zu den Fließkommazahlen existiert für die Integer-Datentypen keine Standardisierung. Damit ist die Darstellung und die Verfügbarkeit der Integer-Datentypen von der Programmiersprache oder gar der Implementierung abhängig.

In C++ gibt es vier (in C fünf) Datentypen zur Darstellung von Integern, jeweils in einer Variante mit Vorzeichen ( signed ) und eine Variante ohne Vorzeichen ( unsigned ). Bis auf char sind die Typen ohne explizite Angabe vorzeichenbehaftet. Ob char vorzeichenbehaftet ist, hängt von der Implementierung ab.

char
short
int
long
long long (derzeit nur in C99)

In C gibt es seit dem C99-Standard im Gegensatz zu C++ noch den Datentyp long long . Im TR1 zu C++ wird ein Typ _Longlong eingeführt, der über ein typedef implementiert werden kann. Dies ist eine Zwischenlösung, bis zum Erscheinen des C++0x-Standard, der long long auch für C++ definiert. Einige C++-Implementierungen, wie die GCC, unterstützen long long bereits.

Die Größe und Darstellung der Typen ist im C- und im C++-Standard nicht genormt. Es gibt nur Angaben über das Verhältnis der Größen zueinander:

sizeof(char) <= sizeof(short) <= sizeof(int) <= sizeof(long) <= sizeof(long long)

Die größten darstellbaren Zahlen für die Datentypen erhält man in C über Macros die im Header limits.h (oder für C++ auch climits ) enthalten sind:

SCHAR_MIN / SCHAR_MIN für signed char
UCHAR_MAX für unsigned char
CHAR_MIN / CHAR_MIN für char
SHRT_MIN / SHRT_MAX für signed short int
USHRT_MAX für unsigned short int
INT_MIN / INT_MAX für signed int
UINT_MAX für unsigned int
LONG_MIN / LONG_MAX für signed long int
ULONG_MAX für unsigned long int
LLONG_MIN / LLONG_MAX für signed long long int
ULLONG_MAX für unsigned long long int

Die Konstante CHAR_BIT gibt die Anzahl der Bits in einem char an und muss mindestens 8 Bit betragen. Mittels sizeof(x)*CHAR_BITS lässt sich so die Anzahl der Bits in einem beliebigen Typ oder Ausdrucks x ermitteln.

In C++ gibt es mit std::numeric_limits eine Template-Klasse für diesen Zweck, mit der man generisch die Limits der Datentypen erfragen kann.

#include <limits>
#include <iostream>

int main() {
  std::cout << "Größter int: "   << std::numeric_limits<int>::max() << '\n'
            << "Kleinster int: " << std::numeric_limits<int>::min() << '\n';
}

Im Verlaufe des Textes werde ich mich jedoch wegen der Kürze und Kompatibilität auf die Konstanten aus limits.h beziehen. In C++-Code ist jedoch die Verwendung von std::numeric_limits zu empfehlen.

C besitzt seit dem C99-Standard einen Header stdint.h der nützliche typedef s für Integer-Datentypen zur Verfügung stellt. Es gibt einmal Datentypen mit fester Breite. Wobei intN_t ein vorzeichenbehafteter Integer-Datentyp und intN_t ein vorzeichenloser Integer-Datentyp mit der Breite N Bits ist. Typen mit fester Breite sind jedoch optional, da zum Beispiel eine C-Implementierung auf einem System mit einer char Größe von 32 Bit keinen kleineren Typ zur Verfügung stellen kann. Dies trifft zum Beispiel auf Signalprozessoren zu. stdint.h enthält aber auch Typen, die eine Mindestgröße erfüllen int_leastN_t und uint_leastN_t .  Dieser Header ist bereits Bestandteil des TR1s zu C++. In der Boost-Library gibt es ebenfalls einen Header dieser Art unter boost/cstdint.hpp . Die GCC unterstützt stdint.h bereits für C++-Code.

Im Verlauf des Textes wird in Beispielen wo eine bestimmte Größe eines Integer-Datentyps erforderlich ist, auf die Typen aus stdint.h zurück gegriffen.

3. Darstellung von Integern in Computern

Zahlen werden bekanntlich in Computern mit dem Binärsystem, also dem System zur Basis 2, dargestellt. Bei vorzeichenlosen Integern kann man einfach die binäre Darstellung der Zahl in einen Integer schreiben. Für Integer mit Vorzeichen benötigt man eine Darstellung für das Vorzeichen und daher eine kompliziertere Kodierung. Außerdem gibt es noch weitere Darstellungen, um Rundungs- oder Transport-Fehler zu vermeiden, was für bestimmte Anwendungen (zum Beispiel im Finanzwesen) interessant sein kann.

Einerkomplement

Das Einerkomplement (im englischen One's Complement) ist die einfachste Darstellung für vorzeichenbehaftete Integer. Es wird aber kaum mehr verwendet, da die Darstellung der Zahl 0 nicht eindeutig ist (dazu gleich mehr). Auf alten Großrechnern wie dem PDP-1 findet man noch das Einerkomplement und die Checksumme des IPv4-Headers wird im Einerkomplement dargestellt.

Alle negativen Zahlen haben im Einerkomplement eine führende 1 und alle positiven Zahlen eine führende 0.

Beim Einerkomplement werden einfach alle Bits gekippt, also eine bitweise Verneinung (NOT) durchgeführt. In C und C++ gibt es dafür den unären operator~ . Um also -42 zu erhalten, nimmt man die Zahl 42 bzw. binär dargestellt als 00101010 und ändert jedes Bit in der binären Darstellung: 00101010 wird dann zu 11010101. Die beiden führenden 0en wurden angefügt um die Zahl auf 8 Bit zu alignen, was einem Octet oder Byte auf heutigen Computern entspricht.

Das rechnen mit dem Einerkomplement ist analog zur normalen Arithmetik auf Binärzahlen, wobei ein Übertrag (carry) wieder zum Ergebnis hinzu addiert werden muss.

Problematisch ist das Einerkomplement vor allem weil es zwei Darstellungen für die 0 gibt. Einmal 00000000 und das Komplement 11111111.

Es lassen sich Zahlen in dem Bereich $2^{n-1} \le Z \le 2^{n-1}$ darstellen.

Zweierkomplement

Das Zweierkomplement (Two's Complement) ist die verbreiteste Darstellung von vorzeichenbehafteten Integern in Computern. Die Negierung einer Zahl ist etwas umständlicher als beim Einerkomplement, aber dafür existiert eine eindeutige Darstellung für die Zahl 0. Außerdem erfolgt die Addition und Subtraktion exakt wie bei vorzeichenloser Darstellung, was die Implementierung in Hardware vereinfacht.

Die Darstelung für negative Zahlen erfolgt ähnlich wie beim Einerkomplement. Die binäre Darstellung wird negiert. Im Unterschied zum Einerkomplement, wird zu dem Ergebnis noch die Zahl 1 (also als Byte 00000001 addiert). Dies dient dazu das 0 immer eindeutig dargestellt wird, da $~00000000 + 00000001 = 11111111 + 00000001 = 00000000$ ist.

Wenn man also die Zahl 42 negieren will, geht man wie folgt vor:

00101010 (42)
11010101 (~42) negieren
11010110 (-42) 00000001 hinzuaddieren.

Die Darstellung im Zweierkomplement ist jedoch problematisch, weil die kleinste darstellbare negative Zahl keine Entsprechung als positive Zahl hat.

Es lassen sich Zahlen in dem Bereich $2^n \le Z \le 2^{n-1}$ darstellen.

BCD-Zahlen

BCD steht für Binary-Coded Decimal. Wie der Name schon sagt handelt es sich um eine Darstellung von Dezimal Zahlen als Binär-Kodierung. Dabei werden die einzelnen Stellen einer Dezimal Zahl in eine 4 Bit große binäre Darstellung umgewandelt.

Für Simple BCD (auch SBCD oder BCD 8 4 2 1 genannt), würden die Stellen wie folgt kodiert werden:
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001

Damit entspräche die Zahl 190 im BCD-System 0001 1001 0000.

Diese Darstellung wird besonders beim kaufmännischen Rechnen verwendet, da man Rundungsfehler bei der Fließkomma-Darstellung vermeiden kann. Außerdem lassen sich BCD-Zahlen schneller als Dezimal-Zahlen darstellen, weshalb einige LCD-Displays die Eingabe als BCD-Zahl erwarten oder das DCF77-Protokoll für Funkuhren mit dem BCD-System arbeitet. Viele Großrechner und selbst heutige Prozessoren verfügen über BCD-Arithmetik. In der Programmiersprache COBOL ist ein extra Datentyp für BCD-Zahlen enthalten. In C und C++ gibt es keine expliziten Typen für BCD-Zahlen.

Nachteile des BCD-Systems sind jedoch eine komplizierteres Darstellung in der Hardware, da die Rechenoperationen komplizierter werden. Außerdem verbrauchen BCD-Zahlen mehr platz. BCD-Codes sind nicht einheitlich standardisiert, so dass sich einige Systeme in der Darstellung unterscheiden.

Weitere Darstellungen

Es gibt weitere Darstellungen für Integer-Typen, die jedoch selten benutzt oder nur für Spezialfälle verwendet werden (z.B. den sicheren Transport von Daten oder Abwandlungen des BCD-Systems). Erwähnt sei hier nur kurz Gray-Code für den Transport von digitalen Signalen über analoge Übertragungswege. Bei der Gray-Code Codierung unterscheiden sich zwei benachbarte Zahlen höchstens um 1 Bit, um ablese Fehler beim Quantisieren zu vermeiden.

4. Probleme mit Integern

Obwohl der Umgang mit Integern zur alltäglichen Arbeit eines Programmierers gehört, ist die Verwendung nicht frei von Problemen. Viele Programme erhalten Fehler in der Benutzung von Integern. Dieser Abschnitt soll die Probleme aufzeigen.

4.1. Rundung (Truncation)

Die meisten Integer-Datentypen haben eine feste Größe. In der Regel gibt es 8 Bit, 16 Bit, 32 Bit, 64 Bit und seltener auch 128 Bit Datentypen. Diesen Typen haben in den meisten Fällen eine direkte Entsprechung in der Hardware und die Arithmetik erfolgt über einfache Maschinenbefehle. Wobei der größte Datentyp der direkt in der Hardware implementiert ist jedoch in der Regel der Architekturgröße entspricht, also den 32 oder 64 Bit die man bei Prozessoren immer erwähnt. Größere Integer werden vom Compiler im Maschinencode über mehrere Operationen dargestellt.

Die unterschiedliche Größe der Datentypen kann jedoch zu Problemen führen beim umwandeln (casten) von einen größeren in einen kleinen Datentyp. Dabei werden die überzähligen Bits einfach abgeschnitten und es kommt zu einem Informationsverlust.

Wenn man Beispielsweise die Zahl 241 (Binär 11110001) einer 4 Bit großen Variable zuweist, werden 4 Bit abgeschnitten. Wobei die es Implementierungsabhängig ist, welche 4 Bits abgeschnitten werden . Das Ergebnis kann also 00001 (Dezimal 1) oder 1111 (Dezimal 15) sein.

Fehler dieser Art lassen sich leicht bei statischer Code-Analyse zum Beispiel in einem Compiler erkennen.

4.2. Überläufe (Overflows)/Unterläufe (Underflows)

Überläufe (im Englischen Overflows) und Unterläufe (im Englischen Underflows) können durch arithmetische Operationen entstehen. Zum Beispiel bei der Multiplikation zweier 32 Bit Variablen kann das Ergebnis doppelt so groß werden, also bis zu 64 Bit. In vielen Programmiersprachen ist hat jedoch das Ergebnis einer Multiplikation die gleiche Größe wie die beiden Faktoren. Daher können die oberen  Bits verloren gehen. Dies führt zu dem Ergebnis das die Multiplikation und Addition zweier positiver Zahlen kleiner seien kann, als die ursprünglichen Zahlen.

Diese Fehler lassen sich nicht mehr mit statischer Code-Analyse ermitteln und müssen zur Laufzeit überprüft werden. Die wenigsten Programmiersprachen und Implementierungen besitzen die Fähigkeit Integer-Überläufe/Unterläufe zu erkennen und an das Programm zu melden. Ausnahmen stellen hier zum Beispiel Ada und Common Lisp dar. Einige Programmiersprachen wandeln das Ergebnis einer überlaufenden Operation automatisch in einen größeren Typ oder gar in einen BigNum-Typ um, also ein Datentyp der beliebig große Integer enthalten kann. Beispielsweise seien hier Common Lisp und Ruby erwähnt.

Beispiel für einen Überlauf durch eine arithmetische Operation wäre

uint8_t a = 0xFF;
++a;

0xFF ist Binär 11111111 (also alle Bits in einem Byte gesetzt). Wenn man nun 00000001 hinzuaddiert, kommt man zu 100000000 (256 im Dezimal System), was aber nicht mehr in ein Byte passt und die führende 1 wird abgeschnitten. Das Ergebnis ist also 0 (kein Bit im Byte gesetzt).

Ein derartiger Überlauf kann sehr problematische Folgen haben, da eine Zahl die eigentlich größer seien sollte auf einmal kleiner wird. Vorzeichenlose Integer verhalten sich dabei wie ein Ring. Bei einem Überlauf kommt nach dem größten möglichen Wert wieder die Null bzw. bei einem Unterlauf kommt nach der Null wieder der größte mögliche Wert.

Mit Überlauf/Unterlauf bei Vorzeichen behafteten Typen befasst sich der nächste Abschnitt.

4.3. Signed-Overflow in C und C++

In C und C++ ist der Überlauf/Unterlauf bei vorzeichenbehafteten Variablen nicht definiert. Eine Implementierung kann bei einem Überlauf oder Unterlauf einer vorzeichenbehafteten Variable im Grunde alles tun. Viele Implementierungen werden sich vermutlich ähnlich verhalten wie bei einem Überlauf einer vorzeichenlosen Variable. Also nach dem größten möglichen Wert kommt der kleines mögliche Wert.

Dennoch kann man sich darauf nicht verlassen. Zum Beispiel geht der GCC ab der Version 4.1 davon aus, das ein Überlauf/Unterlauf bei vorzeichenbehafteten Typen nicht statt findet. Dieses Verhalten erlaubt dem Compiler einige arithmetische Operationen zu optimieren, so kann man i*10/5 zum Beispiel durch i*2 ersetzen. Wenn ein Überlauf erlaubt wäre, könnte i*10/5 ein unterschiedliches Ergebnis liefern!

Der Überlauf/Unterlauf von Pointern, die auf den meisten Systemen als Ganzzahl dargestellt werden, ist ebenfalls nicht definiert.

4.4. Kombination von signed/unsigned

Die Kombination von vorzeichenlosen und vorzeichenbehafteten Integern kann zu unerwarteten Resultaten führen. Einige Programmiersprachen (besonders Script-Sprachen) verzichten daher gänzlich auf vorzeichenlose Integer-Datentypen. Aber in C und C++ muss man sich mit

4.5. Der Betrag (abs)

Wie bereits in dem Abschnitt über das Zweierkomplement erwähnt, gibt es bei der Darstellung von vorzeichenbehafteten Integern im Zweierkomplement eine Zahl (die kleinste mögliche Zahl), die sich nicht negieren lässt (für die also keine Entsprechung als positive Ganzzahl existiert).

Daher kann auf Systemen die das Zweierkomplement benutzen (was heutzutage auf fast alle Systeme zutrifft), der Betrag (also die Funktion man: abs in C und C++) und die Negierung einer negativen Zahl wieder negativ sein.

Dieses Verhalten ist dann wichtig, wenn man zum vorzeichenbehaftete und vorzeichenlose Integer kombiniert.

Ich will dies an einem Beispiel demonstrieren. Wir haben Längenangaben, die fälschlicherweise in einen vorzeichenbehafteten Typ gespeichert werden und wir wollen nun die gesammte Länge berechnen.

int laenge[N]; // Längenangaben, die fälschlicherweise vorzeichenbehaftet sind
// ...
size_t gesammte_laenge = 0;
for(size_t i = 0; i < N; ++i)
  gesammte_laenge += laenge;

Bei diesem einfachen Code könnte eine negative Länge (zum Beispiel das Resultat eines Überlaufs), die gesammte Länge verkleinern. Daher muss man vermeiden, dass die Zahl die hinzuaddiert wird negativ ist. Würde man nun einfach abs benutzen

int laenge[N]; // Längenangaben, die fälschlicherweise vorzeichenbehaftet sind
// ...
size_t gesammte_laenge = 0;
for(size_t i = 0; i < N; ++i)
  gesammte_laenge += abs(laenge[i]);

könnte die gesammte_laenge immer noch verkleinert werden, da abs eine negative Zahl zurück geben kann.

Dies ist übrigens einer der Gründe warum man für Längenangaben vorzeichenbehaftete Typen vermeiden sollte. Mehr dazu im nächsten und übernächsten Kapitel.

Ein ähnliches Problem tritt natürlich auch bei der Division auf. So darf man sich nicht darauf verlassen, dass die Division zweier negativer Ganzzahlen ein positives Ergebnis hat. Dieses Problem ist in den meisten Fällen wesentlich weniger kritisch.

5. Sicherheitsprobleme durch den falschen gebrauch von Integern

Buffer-Overflows sind eine bekannte Ursache für Sicherheitslücken. Besonders C-Funktionen wie man: gets, man: strcpy und man: sprintf haben dadurch einen nicht ganz unbegründeten schlechten Ruf erhalten. Doch wesentlich weniger bekannt und oft unterschätzt sind Sicherheitslücken die durch die falsche Verwendung von Integern entstehen. Sicherheitslücken durch Integer sind passive Sicherheitslücken. Die Möglichkeit eine Sicherheitslücke auszunutzen wird also erst ermöglicht und nicht direkt durchgeführt. In diesem Kapitel will ich Ihnen nun einige Beispiele und typische Fehler erläutern. Aber auch gewisse Strategien zeigen um solche Probleme zu vermeiden. Damit will ich besonders das Bewusstsein für derartige Sicherheitslücken steigern.

Jedes unerwartete Verhalten eines Integers kann zu einer Sicherheitslücke führen. Besonders die im vorherigen Kapitel aufgeführten Probleme. Ein Informationsverlust kann immer dazu führen, das ein Angreifer die Informationen so manipulieren kann, wie er sie für einen Angriff benötigt.

Folgende Sammlung von echten Sicherheitslücken durch den falschen gebrauch von Integern soll nicht nur typische Fehler aufzeigen, sondern auch das Bewusstsein dafür schärfen, das solche Sicherheitslücken ein reales Problem darstellen. Ich habe nur exemplarisch für unterschiedliche Fehlerarten einige Sicherheitslücken rausgesucht und mich dabei auf Open Source Projekte beschränkt, da ich den wirklichen Code auch vorführen wollte. Dies heißt natürlich nicht, dass die Projekte besonders schlecht oder unsicher sind.

Beispiel: Integeroverflow in SSH

Im SSH-Daemon gab es zum Beispiel eine Sicherheitslücke, weil die Portnummer als int eingelesen wurde. Die Socket-APIs benutzen für Portnummern jedoch ein short . Auf den meisten Systemen ist es einem unprivilegierten Programmen nicht erlaubt Sockets unterhalb eines bestimmten Ports zu öffnen (in der Regel Port 1024), damit ein Benutzer nicht einfach einen Dienst wie HTTP nachstellen kann. Der SSH-Daemon lief jedoch als privilegierter Prozess und um normalen Benutzern dennoch das binden eines privilegierten Ports zu ermöglichen, gab es eine Sicherheitsabfrage. Der Code sah also grob in etwas so aus:

<!-- vielleicht konkreter nachlesen -->
int port = port_aus_der_config();
if(unpriviligiert() && port <= 1024) {
  error("Portnummer kleiner als 1024 für unpriviligierte Nutzer nicht erlaubt!");
  exit(1);
}
struct sockaddr_in my_addr;
//...
my_addr.sin_port = htons(port); // Portnummer festlegen.
                                // htons erwartet ein short
//...
if( bind(socket, (struct sockaddr_in*)&my_addr, sizeof(my_addr)) == -1)
  //...

Vermutlich haben Sie es schon bemerkt. Hier lässt sich die Truncation, also die Verkürzung von int auf short ausnutzen, um dennoch einen Port kleiner als 1024 zu binden. Dazu reicht es einfach port auf SHRT_MAX + Portnummer zu setzen, was natürlich größer war als 1024. Bei der Umwandlung wurden dann alle höheren Bits abgeschnitten und nur noch die Portnummer verblieb.

Beispiel: Umwandlung von signed zu unsigned in Mac OS X

In Mac OS X 10.4.8 (8L2127) x86 existierte ein Bug durch die falsche Benutzung eines vorzeichenbehafteten Integers. Der Code existierte in einer Funktion zum umwandeln von Big in Litte-Endian, also eigentlich einem ziemlich trivialen Code. Die Funktion wurde beim Laden von UFS-Dateisystemen benutzt. Hier ist ein kleiner Ausschnitt

// aus der Datei bsd/ufs/ufs/ufs_byte_order.c
void
byte_swap_shorts(short *array, int count)
{
  register int    i;

  for (i = 0;  i < count;  i++)
    byte_swap_short(array[i]);
}

void
byte_swap_sbin(struct fs *sb)
{
  u_int16_t *usptr;
  unsigned long size;

  // ... 

  /* Got these magic numbers from mkfs.c in newfs */
  if (sb->fs_nrpos != 8 || sb->fs_cpc > 16) {
    usptr = (u_int16_t *)((u_int8_t *)(sb) + (sb)->fs_postbloff);
    size = sb->fs_cpc * sb->fs_nrpos;
    byte_swap_shorts(usptr,size);   /* fs_postbloff */
  }
}

der Inhalt der Daten in sb wurde durch das zu ladende Dateisystem initialisiert, war also für einen Angreifer mit einer Image-Datei ([i]DMG*) manipulierbar. Geeignet große Werte in fs_cpc und fs_nrpos konnten also size größer werden lassen als INT_MAX . Bei der Übergabe an byte_swap_shorts wurde der Wert dann mit Vorzeichen (im Zweierkomplement) betrachtet und count konnte so einen negativen Wert enthalten, was dazu führt dass die Schleife einen Buffer-Overflow erzeugte. Dieser Fehler konnte zumindest für einen Denial-of-Service (DOS) Angriff benutzt werden.

Beispiel: Integeroverflow in PHP

In PHP 4.4.5 konnte es in der Funktion zip_entry_read zu einem Überlauf kommen, mit dem es möglich war einen Heap-Überlauf zu erzeugen und Code auszuführen. Die Funktion wurde zum lesen von ZIP-Archiven benutzt und war durch manipulierte ZIP-Archive angreifbar.

// aus zip_entry_read ext/zip/zip.c
        long              len   = 1024;
// einlesen von len aus dem Archiv ...
        buf = emalloc(len + 1);
        ret = zzip_read(entry->fp, buf, len);
        buf[ret] = 0;

Wenn len nun auf den Wert LONG_MAX gesetzt wurde, erzeugte das len + 1 bei emalloc einen überlauf und es wurde Speicher mit der Länge Null angelegt. Da in zzip_read ohne weitere Überprüfung Daten in den buffer gelesen wurden, konnte man so den Heap überschreiben und eigenen Code einschleusen.

Beispiel: Verwendung von abs in GNUs libiberty

In GNUs libiberty, eine Library die einige häufig genutzte Unterfunktionen aus einigen GNU-Programmen (binutils, gdb und mehr) zusammen fasst, gibt es in der Funktion vasprintf ein Bug in der Verwendung von abs und einen potentiellen Integer-Überlauf. Die Funktion vasprinft verhält sich die wie die Funktion man: vsprintf nur wird der zurück gegebene Buffer dynamisch angelegt, um Buffer-Überläufe zu verhindern.

// aus binutils libiberty/vasprintf.c
static int
int_vasprintf (char **result, const char *format, va_list args)
{
  const char *p = format;
  // ...
  int total_width = strlen (format) + 1;
  // ...
  while (*p != '\0')
    {
      // ...
          if (*p == '*')
            {
              ++p;
              total_width += abs (va_arg (ap, int));
            }
       // ...
    }
  // ...
  *result = (char *) malloc (total_width);
  if (*result != NULL)
    return vsprintf (*result, format, args);
  else
    return -1;
}

Auf einem System mit Zweierkomplement Darstellung könnte ein Wert von MIN_INT als Längenangabe den Wert von total_width verkleinern und so einen zu kleinen Buffer für result bewirken, was zu einem Heap-Überlauf führt. Ebenso gibt es keine Überprüfung auf einen Überlauf von total_width und ein Überlauf könnte eine ähnliche Wirkung erzielen.

6. 7. Quellen und Links

Felix von Leitner: Catching Integer Overflows in C

<!--
Sicherheitslücken evaluieren: http://secunia.com/advisories/29668/ http://www.debian.org/security/2008/dsa-1545

... oh man, der rsync Quellcode ist voller Integerfehler
-->

sothis_

es würde sich teilweise mit dem inhalt meines artikels über zahlensysteme überschneiden

rüdiger

sothis_ schrieb:

es würde sich teilweise mit dem inhalt meines artikels über zahlensysteme überschneiden

oh, ich habe jetzt erst den 2. Teil entdeckt. Naja, das lässt sich ja vermutlich ziemlich gut vereinen. Dann verkürze ich den Bereich ein wenig in meinem Artikel. Passt dann ja eigentlich gut zusammen.

sothis_

yup

Wie gerade in #cpp-mag schon angesprochen, zur Erinnerung:

- long long (derzeit nur in C) -> schreib noch C99 dazu
- CHAR_BIT ohne S
- sizeof lässt sich auf Ausdrücke anwenden.
- bez. uint8_t: nicht gefordert da es Architekturen gibt wo CHAR_BIT > 8 ist

rüdiger

Tim schrieb:

Wie gerade in #cpp-mag schon angesprochen, zur Erinnerung:

- long long (derzeit nur in C) -> schreib noch C99 dazu
- CHAR_BIT ohne S
- sizeof lässt sich auf Ausdrücke anwenden.

done

Tim schrieb:

- bez. uint8_t: nicht gefordert da es Architekturen gibt wo CHAR_BIT > 8 ist

done

Wie weit sollte ich stdint.h erklären? Ich meine so etwas wie int_fastN_t etc. scheint ja eher wenig interessant zu sein.

Allerhöchsten erwähnen/aufzählen. Sonst würde es imho zu weit gehen.