Einzelfehler - Off-by-one error

Ein Off-by-One-Fehler oder Off-by-One-Fehler (bekannt unter den Akronymen OBOE , OBO , OB1 und OBOB ) ist ein logischer Fehler , der das diskrete Äquivalent einer Randbedingung beinhaltet . Es tritt häufig in der Computerprogrammierung auf, wenn eine iterative Schleife einmal zu viele oder zu wenige Iterationen durchläuft. Dieses Problem kann auftreten, wenn ein Programmierer Fehler macht, wie z. wie bei Array-Indizes in vielen Sprachen). Dies kann auch in einem mathematischen Kontext vorkommen.

Schleifen über Arrays

Betrachten Sie ein Array von Elementen, und die Elemente m bis n (einschließlich) sollen verarbeitet werden. Wie viele Artikel gibt es? Eine intuitive Antwort kann n  −  m sein , aber das ist um eins daneben und weist einen Zaunpfostenfehler auf ; die richtige Antwort ist ( n  –  m ) + 1.

Aus diesem Grund werden Bereiche im Rechnen oft durch halboffene Intervalle dargestellt ; der Bereich von m bis n (einschließlich) wird durch den Bereich von m (einschließlich) bis n  + 1 (ausschließlich) dargestellt, um Zaunpfostenfehler zu vermeiden. Beispielsweise kann eine Schleife , die fünfmal (von 0 bis einschließlich 4) wiederholt wird , als halboffenes Intervall von 0 bis 5 geschrieben werden: 

for (index = 0; index < 5; index++) 
{
    /* Body of the loop */
}

Der Schleifenkörper wird zunächst mit Index gleich 0 ausgeführt; Index wird dann 1, 2, 3 und schließlich 4 bei aufeinanderfolgenden Iterationen. An diesem Punkt wird Index 5, also ist Index < 5 falsch und die Schleife endet. Wenn der verwendete Vergleich jedoch < or = (kleiner oder gleich) wäre, würde die Schleife sechsmal ausgeführt: index nimmt die Werte 0, 1, 2, 3, 4 und 5 an. Ebenso, wenn index eher auf 1 initialisiert würde als 0, gäbe es nur vier Iterationen: index nimmt die Werte 1, 2, 3 und 4 an. Beide Alternativen können Einzelfehler verursachen.

Ein weiterer solcher Fehler kann auftreten, wenn eine do-while-Schleife anstelle einer while-Schleife verwendet wird (oder umgekehrt). Eine do-while-Schleife wird garantiert mindestens einmal ausgeführt.

Array-bezogene Verwirrung kann auch aus Unterschieden in den Programmiersprachen resultieren. Die Nummerierung ab 0 ist am häufigsten, aber einige Sprachen beginnen die Array-Nummerierung mit 1. Pascal hat Arrays mit benutzerdefinierten Indizes. Dadurch ist es möglich, die Array-Indizes nach der Problemdomäne zu modellieren.

Zaunpfostenfehler

Ein gerader Zaun mit n Abschnitten hat n +1 Pfosten.

Ein Zaunpfostenfehler (gelegentlich als Telegrafenmast-, Laternenpfahl- oder Lattenzaunfehler bezeichnet ) ist eine bestimmte Art von Fehler, die nacheinander abweichen. Eine frühe Beschreibung dieses Fehlers erscheint in den Werken von Vitruv . Das folgende Problem veranschaulicht den Fehler:

Wenn Sie einen geraden Zaun mit einer Länge von 30 Fuß mit Pfosten im Abstand von 3 Fuß bauen, wie viele Pfosten benötigen Sie?

Die übliche Antwort von 10 Beiträgen ist falsch. Diese Reaktion ergibt sich aus der Division der Zaunlänge durch den Abstand von jedem Pfosten, wobei der Quotient fälschlicherweise als Anzahl der Pfosten klassifiziert wird. Tatsächlich hat der Zaun 10 Abschnitte und 11 Pfosten.

In diesem Szenario hat ein Zaun mit n Abschnitten n + 1 Pfosten. Umgekehrt, wenn der Zaun n Pfosten enthält , enthält er n − 1 Abschnitte. Diese Beziehung ist wichtig, wenn man mit dem Umkehrfehler umgeht. Der umgekehrte Fehler tritt auf, wenn die Anzahl der Pfosten bekannt ist und die Anzahl der Abschnitte als gleich angenommen wird. Je nach Ausführung des Zauns kann diese Annahme richtig oder falsch sein.

Das folgende Problem zeigt den umgekehrten Fehler:

Wenn Sie n Beiträge haben, wie viele Abschnitte gibt es dazwischen?

Die Interpretation des Zaundesigns ändert die Antwort auf dieses Problem. Die korrekte Anzahl von Abschnitten für einen Zaun ist n − 1, wenn der Zaun ein freistehendes Liniensegment ist, das an jedem seiner Enden von einem Pfosten begrenzt wird (z. B. ein Zaun zwischen zwei Durchgangslücken), n wenn der Zaun ein vollständiges bildet, freistehende Schleife (z. B. durch Überwindung zugängliche Einfriedung, z. B. ein Boxring) oder n + 1, wenn an den Enden eines liniensegmentartigen Zauns (z zwei Gebäude). Die genaue Problemdefinition muss sorgfältig überlegt werden, da der Aufbau für eine Situation für andere Situationen die falsche Antwort geben kann. Zaunpfostenfehler entstehen dadurch, dass man Dinge zählt und nicht die Abstände zwischen ihnen, oder umgekehrt, oder indem man vernachlässigt, zu überlegen, ob man ein oder beide Enden einer Reihe zählen sollte.

Zaunpfostenfehler können auch in anderen Einheiten als der Länge auftreten. Zum Beispiel soll die Zeitpyramide , die aus 120 Blöcken besteht, die in 10-Jahres-Intervallen zwischen den Blöcken platziert werden, 1190 Jahre (nicht 1200) dauern, von der Installation des ersten Blocks bis zum letzten Block. Einer der frühesten Zaunpfostenfehler betraf die Zeit, bei der der Julische Kalender ursprünglich Schaltjahre falsch berechnete , da er nicht ausschließlich, sondern alle drei Jahre ein Schaltjahr statt alle vier Jahre zählte.

"Zaunpfostenfehler" kann sich in seltenen Fällen auf einen Fehler beziehen, der durch unerwartete Regelmäßigkeiten in Eingabewerten verursacht wird und (zum Beispiel) eine theoretisch effiziente Implementierung eines Binärbaums oder einer Hashfunktion vollständig durchkreuzen kann . Dieser Fehler bezieht sich auf den Unterschied zwischen erwartetem und schlechtestmöglichem Verhalten eines Algorithmus .

Bei größeren Zahlen ist es oft kein großes Problem, von einem getrennt zu sein. In kleineren Zahlen jedoch und in bestimmten Fällen, in denen die Genauigkeit von größter Bedeutung ist, kann es katastrophal sein, einen Einzelfehler zu begehen. Manchmal wird ein solches Problem auch wiederholt und dadurch verschlimmert, dass jemand eine falsche Berechnung weitergibt, wenn die folgende Person den gleichen Fehler erneut macht (der Fehler kann natürlich auch rückgängig gemacht werden).

Ein Beispiel für diesen Fehler kann in der Rechensprache MATLAB mit der linspace() linearen Interpolationsfunktion auftreten , deren Parameter sind und nicht . Ein Programmierer, der den dritten Parameter als die Anzahl der Inkremente missversteht, könnte hoffen, dass damit eine Sequenz erreicht wird, aber stattdessen bekommt er . (lower value, upper value, number of values)(lower value, upper value, number of increments)linspace(0,10,5)[0, 2, 4, 6, 8, 10][0, 2.5, 5, 7.5, 10]

Auswirkungen auf die Sicherheit

Ein häufiger Fehler, der zu einem sicherheitsbezogenen Fehler führt, wird durch den Missbrauch der C-Standardbibliotheksroutine verursacht strncat. Ein häufiges Missverständnis strncatist, dass die garantierte Nullterminierung nicht über die maximale Länge hinaus schreibt. In Wirklichkeit schreibt es ein abschließendes Nullzeichen ein Byte über die angegebene maximale Länge hinaus. Der folgende Code enthält einen solchen Fehler: 

void foo (char *s) 
{
    char buf[15];
    memset(buf, 0, sizeof(buf));
    strncat(buf, s, sizeof(buf)); // Final parameter should be: sizeof(buf)-1
}

Off-by-One-Fehler sind bei der Verwendung der C-Bibliothek üblich, da sie nicht konsistent sind in Bezug darauf, ob 1 Byte subtrahiert werden muss – Funktionen mögen fgets()und strncpywerden niemals über die ihnen gegebene Länge hinaus schreiben ( fgets()subtrahiert 1 selbst und ruft nur (length − 1) Bytes), während andere wie strncatdie angegebene Länge überschreiben. Der Programmierer muss sich also merken, für welche Funktionen er 1 subtrahieren muss.

Auf einigen Systemen (insbesondere Little-Endian- Architekturen) kann dies dazu führen, dass das niederwertigste Byte des Rahmenzeigers überschrieben wird . Dies kann zu einer ausnutzbaren Bedingung führen, bei der ein Angreifer die lokalen Variablen für die aufrufende Routine kapern kann.

Ein Ansatz, der häufig hilft, solche Probleme zu vermeiden, besteht darin, Varianten dieser Funktionen zu verwenden, die berechnen, wie viel geschrieben werden soll, basierend auf der Gesamtlänge des Puffers und nicht auf der maximalen Anzahl zu schreibender Zeichen. Zu diesen Funktionen gehören strlcatund strlcpy, und werden oft als "sicherer" angesehen, da sie es einfacher machen, versehentlich über das Ende eines Puffers hinaus zu schreiben. (Im obigen Codebeispiel strlcat(buf, s, sizeof(buf))würde ein Aufruf stattdessen den Fehler beseitigen.)

Siehe auch

Weiterlesen

  • Matt Parker (2021). Humble Pi: Wenn Mathe geht falsch in der realen Welt . Riverhead-Bücher. ISBN 978-0593084694.

Hinweise und Referenzen

Anmerkungen

Verweise