Quelltext der Seite Off-by-one-Error

Ein '''Off-by-one-Error''' oder '''Off-by-one-Fehler''' (abgekürzt '''OBOE'''; deutsch etwa ''Eins-daneben-Fehler''),<ref>[http://userpage.fu-berlin.de/~ram/pub/pub_jf47ht81Ht/formal_bereich_de userpage.fu-berlin.de]</ref> oder ''Plus-minus-eins-Syndrom''<ref>Ägidius Plüss: [http://books.google.de/books?id=b-HMaUG1ct0C&pg=PA51 ''Java – exemplarisch: learning by doing''.] Oldenbourg Wissenschaftsverlag, 2004, ISBN 3-486-20040-2, S. 51.</ref> scherzhaft auch ''„[[Figuren aus Star Wars#Obi-Wan Kenobi|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 (Informatik)|Puffer]] um einen Schritt zu weit in den Speicher geschrieben, wobei der Speicher eines anderen Puffers bzw. einer Variable überschrieben wird.<ref>[http://foldoc.org/off-by-one+errors foldoc.org]</ref>

== Allgemeines ==
Off-by-one-Fehler ereignen sich oft im Umgang mit [[Datenfeld]]ern, [[Feld (Datentyp)|Arrays]], [[Vektor]]en, [[Liste (Datenstruktur)|Listen]], [[Zeichenkette]]n oder anderen indizierbaren [[Datentyp]]en.

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 [[Speicheradresse#Segmentierte Adressen|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 [[Null|0]] beginnt und nicht mit [[Eins|1]] ''(zero-based numbering)''. Bei einem Array mit 10 Datenfeldern bedeutet das, dass die Datenfelder nicht die [[Feld (Datentyp)#Indizes|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.
:{| class="wikitable" ; line-height:120%"
! Element nach<br>umgangssprach-<br>licher Zählung
! Null-<br>basierte<br>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<br>gehört nicht mehr zum Array!
|}
:Die Verwirrung geht weiter durch unterschiedliche Handhabung in unterschiedlichen Programmiersprachen:
:: Basic: <code>DIM A(10)</code> legt ein Array mit den Indices 0, 1, ..., 9, 10 an.
:: C/C++/Java/...: <code>a[10]</code> legt ein Array mit den Indices 0, 1, ..., 9 an.
:: Matlab: Eine Standard-Vektor <code>x = [10, 11, ... 19]</code>mit 10 Elementen verwendet die Indices 1, ..., 9, 10.
:: Matlab: <code>x = 0:10</code> verwendet die Indices 0, 1, ..., 9, 10.
:: Pascal: array <code>[0..10]</code> legt ein Array mit den Indices 0, 1, ..., 9, 10 an.
:: Pascal: array <code>[1..10]</code> legt ein Array mit den Indices 1, ..., 9, 10 an.

* Eine weitere häufige Fehlerquelle ist die Verwendung von [[Nullzeichen|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.&#8239;B. bei Analyse einer leeren Zeichenkette, wird eine [[Schleife (Programmierung)#Arten|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.&#8239;ä.) 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 (Computer)|Absturz]] des Programms führen, wenn im Speicher nach dem Puffer wichtige Daten liegen, die von der Schleife dann überschrieben werden (z.&#8239;B. [[Zeiger (Informatik)|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. <!-- Hingegen ist eine Speicherschutzverletzung sehr unwahrscheinlich, da Betriebssysteme Arbeitsspeicher in großen Blöcken reservieren. Eine Ausnutzung eines Off-By-One-Fehlers für [[Exploit]]s ist kaum denkbar, da hierzu zufälligerweise viele Bedingungen gleichzeitig erfüllt sein müssen.-->

== Beispiele ==
Beispiel aus der Sprache [[C (Programmiersprache)|C]]:
<syntaxhighlight lang="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.
</syntaxhighlight>

In diesem Fall müsste es <code>i < ANZAHL</code> oder <code>i+1 <= ANZAHL</code><ref>Never ever ever use <code>size_t i; i <= ANZAHL-1</code>, 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.</ref> und nicht <code>i <= ANZAHL</code> heißen, da in der Deklaration zwar <code>ANZAHL</code> als Feldgröße angegeben wurde, aber der maximale Index <code>ANZAHL-1</code> ist.

Häufig resultiert diese Art der Fehler aus der Verwirrung, die dadurch entsteht, dass Menschen von 1 bis&nbsp;N zählen, Feldindizes in vielen Programmiersprachen aber von 0 bis&nbsp;N−1 gehen.<ref>Dieter Masak: [http://books.google.de/books?id=_ADkwozCvegC&pg=PA161 ''Legacysoftware: Das lange Leben der Altsysteme''.] Springer-Verlag, 2005, ISBN 3-540-25412-9, S.&nbsp;161.</ref> 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 [[Infimum und Supremum|Bereichsgrenzen]] nicht beachtet wird, ob die untere und obere Schranke einschließend oder ausschließend sind. So liefert die Funktion <code>substring</code> in [[Java (Programmiersprache)|Java]] den Teil eines Strings, der die untere Schranke mit einschließt, die obere aber nicht.

<syntaxhighlight lang="Java">
String wort = "Foobar";
String zweiteSilbe = wort.substring(3, 5); // schlägt fehl
</syntaxhighlight>

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, <code>substring(3, 5)</code> 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 ==
* [http://foldoc.org/off-by-one+errors off-by-one error] im [[FOLDOC|Free On-line Dictionary of Computing]] (englisch)

== Einzelnachweise ==
<references />

[[Kategorie:Programmfehler]]