Off-by-one-Error

Ein Off-by-one-Error oder Off-by-one-Fehler (abgekürzt OBOE; deutsch etwa Um-Eins-daneben-Fehler),^[1] oder Plus-minus-eins-Syndrom^[2] scherzhaft auch „Obi-Wan error“, da ähnlich klingend, oder ±1-Problem, bezeichnet in der Informatik einen Programmierfehler, bei dem eine Zahlenangabe oder eine Anzahl ausgeführter Schritte um 1 zu groß oder zu klein ist. Zum Beispiel ist die Größe eines Speicherblocks um 1 falsch oder es wird in einem Puffer um einen Schritt zu weit in den Speicher geschrieben, wobei der Speicher eines anderen Puffers bzw. einer Variable überschrieben wird.^[3]

Allgemeines

Off-by-one-Fehler ereignen sich oft im Umgang mit Datenfeldern, Arrays, Vektoren, Listen, Zeichenketten oder anderen indizierbaren Datentypen.

Off-by-one-Fehler können leicht unterlaufen und sind sehr schwer zu finden, vor allem, da sie sich sehr häufig nur unter ganz speziellen Bedingungen bemerkbar machen. Auch bei der Durchsicht des Quelltextes können sie sehr leicht übersehen werden. Erschwerend kommt hinzu, dass Indizes oder Offsets im Quelltext meist durch Variablen oder Formeln gebildet werden. Maßnahmen von Compiler/Interpreter oder ggf. Betriebssystemen, die ein Überschreiten einer Puffergrenze um jedes einzelne Byte registrieren, greifen auch nur in dem Spezialfall, dass der gesamte reservierte Puffer genutzt werden soll.

Wenn ein Off-by-one-Fehler gefunden und lokalisiert ist, ist er in der Regel sehr einfach zu beheben.

Häufige Ursachen (Auswahl)

Es gibt verschiedenste Fehlerursachen, die im Ergebnis zu einem Off-by-one-Fehler führen. Beispiele:

Eine häufige Fehlerquelle ist der Umstand, dass man bei der Programmierung das Indexieren häufig bei 0 beginnt und nicht mit 1 (zero-based numbering). Bei einem Array mit 10 Datenfeldern bedeutet das, dass die Datenfelder nicht die Indizes 1 bis 10 haben, sondern die Indizes 0 bis 9. In einer Schleife „von 0 bis Länge“ wird somit auf ein elftes Element (Index 10) zugegriffen.

Element nach umgangssprach- licher Zählung	Null- basierte Zählung	Speicheradresse
erstes Element	Element 0	Anfangsadresse + 0 × Größe des Elements
zweites Element	Element 1	Anfangsadresse + 1 × Größe des Elements
drittes Element	Element 2	Anfangsadresse + 2 × Größe des Elements
viertes Element	Element 3	Anfangsadresse + 3 × Größe des Elements
fünftes Element	Element 4	Anfangsadresse + 4 × Größe des Elements
sechstes Element	Element 5	Anfangsadresse + 5 × Größe des Elements
siebtes Element	Element 6	Anfangsadresse + 6 × Größe des Elements
achtes Element	Element 7	Anfangsadresse + 7 × Größe des Elements
neuntes Element	Element 8	Anfangsadresse + 8 × Größe des Elements
zehntes Element	Element 9	Anfangsadresse + 9 × Größe des Elements
		Anfangsadresse +10 × Größe des Elements gehört nicht mehr zum Array!

Die Verwirrung geht weiter durch unterschiedliche Handhabung in unterschiedlichen Programmiersprachen:

Basic: DIM A(10) legt ein Array mit den Indices 0, 1, ..., 9, 10 an.

C/C++/Java/...: a[10] legt ein Array mit den Indices 0, 1, ..., 9 an.

Matlab: Eine Standard-Vektor x = [10, 11, ... 19]mit 10 Elementen verwendet die Indices 1, ..., 9, 10.

Matlab: x = 0:10 verwendet die Indices 0, 1, ..., 9, 10.

Pascal: array [0..10] legt ein Array mit den Indices 0, 1, ..., 9, 10 an.

Pascal: array [1..10] legt ein Array mit den Indices 1, ..., 9, 10 an.

Eine weitere häufige Fehlerquelle ist die Verwendung von Nullbytes, vor allem bei Zeichenketten, also Text. Das Nullbyte ist ein in Text nicht vorkommendes Zeichen mit dem Wert 0 und markiert das Ende einer Zeichenkette, während der eigentliche Puffer für die Zeichenkette um ein Vielfaches größer sein kann. Dadurch muss man bei variablen Pufferinhalten die Puffergröße nicht ständig verändern und ebenso die Länge der Zeichenkette nicht separat angeben. Durch das Nullbyte ist eine Zeichenkette allerdings prinzipiell um ein Zeichen länger, als die Zeichenkette an sich lang ist. Beispielsweise ist die Zeichenkette „Hallo“ somit zwar 5 Zeichen lang, benötigt aber 6 Zeichen im Speicher. Funktionen, die die Länge einer Zeichenkette ermitteln und zurückgeben, zählen das Nullbyte nicht mit.
Off-by-one-Fehler treten auch häufig als Folge sogenannter Zaunpfahlfehler auf, also durch die Verwechslung von Distanzen und Anzahlen bei der Indizierung.
Falls gar nichts zu tun ist, z. B. bei Analyse einer leeren Zeichenkette, wird eine nachprüfende Schleife einmal (also einmal zu oft) ausgeführt.

Folgen

Im Falle eines Off-by-one-Errors wird typischerweise beim Schreiben der Schleife, die ein Feld verarbeiten soll, die Abbruch- bzw. Fortsetzungsbedingung falsch gewählt, sodass im Rumpf der Schleife eine Anweisung, die indexbasiert auf das Feld zugreift, genau einmal zu oft oder einmal zu wenig ausgeführt wird, wodurch entweder versucht wird, auf ein Element des Feldes zuzugreifen, das nicht existiert, oder das letzte (bzw. erste) Element des Feldes ausgelassen wird. Im erstgenannten Fall ist oft ein Index-out-of-upper-Range-Fehler (o. ä.) die auffällige Folge, im letztgenannten Fall wird mitunter gar kein Fehler sichtbar, solange nicht die gesamte Puffergröße genutzt werden soll oder ein Index-out-of-lower-Range-Fehler gemeldet wird.

Ein Off-by-one-Fehler kann durchaus zu einem Absturz des Programms führen, wenn im Speicher nach dem Puffer wichtige Daten liegen, die von der Schleife dann überschrieben werden (z. B. Zeiger auf eine Struktur). Grundsätzlich kann nach einem Puffer im Arbeitsspeicher auch Programmcode liegen, wobei in der Regel ein zufälliges Überschreiben ebenfalls einen Programmabsturz verursacht, da die Daten keinem gültigen Maschinenbefehl entsprechen.

Beispiele

Beispiel aus der Sprache C:

#define ANZAHL 10

double nettopreise [ANZAHL];
double bruttopreise[ANZAHL];

/* nettopreise initialisieren */
int i;
for (i = 0; i <= ANZAHL; i++)
    bruttopreise[i] = nettopreise[i] * 1.19; // MwSt aufschlagen.

In diesem Fall müsste es i < ANZAHL oder i+1 <= ANZAHL^[4] und nicht i <= ANZAHL heißen, da in der Deklaration zwar ANZAHL als Feldgröße angegeben wurde, aber der maximale Index ANZAHL-1 ist.

Häufig resultiert diese Art der Fehler aus der Verwirrung, die dadurch entsteht, dass Menschen von 1 bis N zählen, Feldindizes in vielen Programmiersprachen aber von 0 bis N−1 gehen.^[5] Dann gibt es auch noch das Größer-als-Zeichen und das Größer-gleich-Zeichen, die man verwechseln kann. Darüber hinaus kann die Abbruchbedingung komplizierter ausfallen, so dass sich an dieser Stelle häufig Off-by-one-Fehler ergeben.

Besonders tückisch ist der Fall einer Datenstruktur, die doch mit 1 beginnt, jedoch Schleifenzählungen über diese Datenstruktur mit 0 beginnen.

Ebenfalls kann leicht ein Off-by-one-Fehler unterlaufen, wenn bei Bereichsgrenzen nicht beachtet wird, ob die untere und obere Schranke einschließend oder ausschließend sind. So liefert die Funktion substring in Java den Teil eines Strings, der die untere Schranke mit einschließt, die obere aber nicht.

String wort = "Foobar";
String zweiteSilbe = wort.substring(3, 5); // schlägt fehl

Will man beispielsweise aus dem Wort „Foobar“ das Teilwort „bar“ herauslösen, indem man die Buchstaben durchzählt, so kann man sich bei der oberen Schranke leicht vertun, selbst wenn man korrekt bei 0 zu zählen beginnt. Da das Wort „bar“ die Buchstaben bei den Indizes 3, 4 und 5 umfasst, ist man versucht, substring(3, 5) aufzurufen. Als Ergebnis würde man aber nur „ba“ erhalten.

Um dieses Problem zu vermeiden, benutzen andere Programmiersprachen wie C/C++, JavaScript oder PHP anstelle der Parameter Start-Index und End-Index, die Parameter Start-Index und Länge der gewünschten Zeichenkette.

Weblinks

off-by-one error im Free On-line Dictionary of Computing (englisch)

Einzelnachweise

↑ userpage.fu-berlin.de
↑ Ägidius Plüss: Java – exemplarisch: learning by doing. Oldenbourg Wissenschaftsverlag, 2004, ISBN 3-486-20040-2, S. 51.
↑ foldoc.org
↑ Never ever ever use size_t i; i <= ANZAHL-1, diese Art von Code ist zwar extrem verbreitet, aber auch ein Geschenk für jeden, der in einen Computer einbrechen will. Man muss irgendwo ein leeres Array einschmuggeln.
↑ Dieter Masak: Legacysoftware: Das lange Leben der Altsysteme. Springer-Verlag, 2005, ISBN 3-540-25412-9, S. 161.

[1] userpage.fu-berlin.de

[2] Ägidius Plüss: Java – exemplarisch: learning by doing. Oldenbourg Wissenschaftsverlag, 2004, ISBN 3-486-20040-2, S. 51.

[3] .org

[4] Never ever ever use size_t i; i <= ANZAHL-1, diese Art von Code ist zwar extrem verbreitet, aber auch ein Geschenk für jeden, der in einen Computer einbrechen will. Man muss irgendwo ein leeres Array einschmuggeln.

[5] Dieter Masak: Legacysoftware: Das lange Leben der Altsysteme. Springer-Verlag, 2005, ISBN 3-540-25412-9, S. 161.

[1]

[2]

[3]

[4]

[5]