Off-by-one error: differenze tra le versioni

Versione delle 00:09, 8 feb 2015

Versione attuale delle 17:25, 29 apr 2025

(30 versioni intermedie di 17 utenti non mostrate)

Riga 1:

Un errore '''off-by-one error''' ('''OBOE'''), detto anche '''OBOBoff-by-one bug''' ('''off-by-one bugOBOB'''), è un errore logico di [[Programmazione (informatica)|programmazione]] che avviene quando un [[Strutture ciclicheIterazione|ciclo iterativo]] viene iteratoeseguito una volta di troppopiù o una volta di meno di quanto desiderato, a causa di un errore nella specifica della condizione di verità:. Di solito solitamenteciò accade quando il programmatore mettesceglie erroneamenteper errore il simbolo di ''minore o uguale'' al posto del simbolo ''minore'' (o viceversa), o il simbolo ''maggiore o uguale'' al posto di ''maggiore'' (o viceversa), oppure quando commette un errore nell'inizializzazione della [[variabile (informatica)|variabile]] testatache controlla l'iterazione, settandolaponendone il valore iniziale a zerouno anziché a unozero: questo causaconfligge problemicol adfatto esempioche sein essamolti si[[Linguaggio riferiscedi programmazione|linguaggi di programmazione]] alll'indice di un [[array]] (ilinizia qualeda inzero. moltiIn linguaggiquesto dierrore programmazionesi cominciapuò daincorrere zero);anche oppure nelin casocontesti inmatematici, cuiper essaesempio poi siase usata come divisore in una divisione (nel qual caso è bene sia settataimpostata a valori diversi da zero, per evitare [[Eccezione (informatica)|eccezioni]] del tipo ''[[divisione per zero]]'').

{{W|informatica|gennaio 2015}}

{{S|informatica}}

Un errore '''off-by-one error''' ('''OBOE'''), detto anche '''OBOB''' ('''off-by-one bug'''), è un errore logico di [[programmazione]] che avviene quando un [[Strutture cicliche|ciclo iterativo]] viene iterato una volta di troppo o una volta di meno, a causa di un errore nella specifica della condizione di verità: solitamente accade quando il programmatore mette erroneamente il simbolo di ''minore o uguale'' al posto del simbolo ''minore'', o il simbolo ''maggiore o uguale'' al posto di ''maggiore'', oppure quando commette un errore nell'inizializzazione della [[variabile]] testata, settandola a zero anziché a uno: questo causa problemi ad esempio se essa si riferisce all'indice di un [[array]] (il quale in molti linguaggi di programmazione comincia da zero); oppure nel caso in cui essa poi sia usata in una divisione (nel qual caso è bene sia settata a valori diversi da zero, per evitare eccezioni del tipo ''divisione per zero'')

== Iterazioni oltre il termine dell'array ==

{{categorizzare|informatica}}

Consideriamo un [[array]] di oggetti, dei quali dobbiamo elaborare quelli da un certo valore ''m'' a uno ''n'' (estremi inclusi). Quanti elementi si trovano in questo intervallo? Una risposta irriflessa potrebbe essere ''n'' – ''m'', ma questo è proprio un errore di off-by-one, più precisamente del tipo ''fencepost''; la risposta corretta è infatti (''n'' – ''m'') + 1.

Proprio per via di questa contro-intuitività, i range nell'informatica sono spesso rappresentati da [[Intervallo (matematica)|intervalli]] semi-aperti; il range da ''m'' ad ''n'' inclusivo infatti, è rappresentato dagli elementi che vanno da ''m'' (incluso) a ''n'' + 1 (escluso), proprio per evitare errori di fancepost. Per esempio, un [[Iterazione|ciclo]] che itera cinque volte (da 0 a 4 incluso) può essere scritto in [[C (linguaggio)|C]] come un intervallo semi-aperto da 0 a 5:<syntaxhighlight lang="c">

for (i = 0; i < 5; i++)

{

//Corpo del ciclo

}

</syntaxhighlight>Il corpo del ciclo è eseguito prima di tutto quando i è uguale a 0; successivamente i assume i valori 1,2,3, sino a raggiungere il valore finale 4 nel corso delle iterazioni. A questo punto, i assumerà valore 5, e dato che i<5 è falso il loop termina. In ogni caso, se la comparazione usata fosse stata <= (minore o uguale a), il ciclo sarebbe stato ripetuto 6 volte: i assumerebbe infatti i valori 0,1,2,3,4, e 5 (con un'ultima ripetizione all'assunzione del valore 5). Analogamente, se i fosse stato inizializzato ad 1 invece che a 0, si sarebbero verificate soltanto quattro iterazioni, relative ai valori 1,2,3, e 4 assunti da i.

Entrambe queste situazioni causerebbero quindi errori di tipo off-by-one.

Un altro tipo di errore può verificarsi se un ciclo do-while viene utilizzato al posto di uno while (o vice versa), poiché quello di tipo do-while è per costruzione ripetuto per forza almeno una volta.

Errori relativi agli array possono inoltre essere risultato di differenze concettuali tra i vari linguaggi di programmazione. La numerazione che fa riferimento alla prima cella come la cella 0 è molto comune, ma alcuni linguaggi la numerano come la 1. [[Pascal (linguaggio di programmazione)|Pascal]] utilizza gli array con indici definiti dagli utenti, rendendone possibile la modellazione successivamente al problema del dominio.

== Errore fencepost ==

[[File:Fencepost error 01.svg|miniatura|upright=1.2|Una recinzione dritta con ''n'' sezioni ha {{Nowrap|''n'' + 1}} paletti]]

Un '''errore fencepost''' (letteralmente "staccionata", chiamato anche '''telegraph pole''', '''lamp-post''' o '''picket fence''') è un tipo specifico di errore di off-by-one. Una descrizione primitiva di questo errore apparve nei testi di [[Marco Vitruvio Pollione|Vitruvio]].<ref>{{Cita web|url=http://www.dsm.fordham.edu/~moniot/Opinions/fencepost-error-history.shtml|titolo=History of fence-post error|sito=dsm.fordham.edu|lingua=en|citazione=Here is what Vitruvius had to say about the fence-post error:

In araeostylis enim libertas est quantum cuique libet

constituendi. Sed ita columnae in peripteris conlocentur uti quot

intercolumnia sunt in fronte, totidem bis intercolumnia fiant in

lateribus. Ita enim erit duplex longitudo operis ad

latitudinem. Namque qui columnarum duplicationes fecerunt erravisse

videntur, quod unum intercolumnium in longitudine plus quam oportet

procurrere videtur.|accesso=2017-11-04|urlarchivio=https://web.archive.org/web/20171107003005/http://www.dsm.fordham.edu/~moniot/Opinions/fencepost-error-history.shtml|dataarchivio=7 novembre 2017|urlmorto=sì}}</ref> Il problema si può illustrare nel modo seguente:

{{Quote|Se costruisci una recinzione dritta lunga 30 metri, con paletti spaziati 3 metri l'uno dall'altro, di quanti paletti necessiti?}}

La risposta più immediata, ovvero 10, è sbagliata. La recinzione è composta infatti da 10 sezioni ed 11 paletti.

L’errore inverso si verifica quando il numero di paletti è noto e il numero di sezioni si assume essere lo stesso. Il numero di sezioni attuale deve sempre essere uno di meno rispetto al numero di paletti.

Più in generale, il problema può essere posto nel modo seguente:

{{Quote|Se hai ''n'' paletti, quante sezioni ci sono tra di essi?}}

La risposta corretta dovrebbe essere ''n'' – 1 se la sequenza di paletti è aperta alla fine, ''n'' se si chiudono a cerchio, o ''n'' + 1 se il lato aperto della sequenza di paletti è considerato come una sezione. Bisogna prestare molta attenzione alla definizione precisa del problema, perché il setup di una certa configurazione potrebbe dare la risposta sbagliata per altre. Errori di fencepost derivano in sostanza dal contare gli elementi piuttosto che gli spazi che li separano e viceversa, o trascurando di considerare se l’oggetto in esame dovrebbe essere contato soltanto in uno o in entrambi gli estremi della fila.

Errori di fencepost possono inoltre verificarsi in [[unità di misura]] diverse dalle lunghezze. Ad esempio, la “Time Pyramid” è una costruzione costituita da 120 blocchi da piazzarsi a distanza di 10 anni l’uno dall’altro. Saranno quindi necessari 1190 anni per la costruzione completa, dal piazzamento del primo blocco sino all’ultimo, e non 1200. Uno dei primi errori di tipo fencepost vide coinvolta l’unità di misura temporale, nel caso specifico del [[Calendario giuliano|calendario Giuliano]]. Esso originariamente calcolava gli [[Calendario giuliano#Anni bisestili|anni bisestili]] in maniera errata, considerandoli in maniera inclusiva invece che esclusiva, originandone quindi uno ogni 3 anni invece che quattro.

Un errore di fencepost può, in rari casi, essere collegato ad un errore introdotto da regolarità inaspettate in valori di input, che possono (per esempio) contrastare completamente con un’implementazione teoricamente efficiente di [[Albero binario|alberi binari]] o [[Funzione di hash|funzioni di hash]]. Questo errore può implicare il verificarsi dei casi peggiori di un [[algoritmo]], invece che quelli attesi.

In caso di utilizzo di numeri molto grandi, avere una ripetizione in più può non essere un problema così evidente. Avendo a che fare con numeri più piccoli invece, soprattutto in casi specifici nei quali la precisione è essenziale, commettere un errore off-by-one può essere disastroso. A volte l’errore potrà essere inoltre ripetuto e anche peggiorato, nel caso in cui un susseguirsi di persone utilizzino uno stesso calcolo errato portandoselo dietro di volta in volta (ovviamente l’errore potrebbe anche venire corretto).

Un esempio di quando un errore di questo tipo si può verificare coinvolge il linguaggio [[MATLAB]], durante l’utilizzo della funzione <code>linspace()</code>. I parametri di questa funzione sono (limite inferiore, limite superiore, numero di valori) e non (limite inferiore, limite superiore, numero di incrementi). Un programmatore che fraintende il terzo parametro, intendendolo come “numero di incrementi”, potrebbe pensare che <code>linspace(0,10,5)</code> genererebbe la sequenza <code>[0, 2, 4, 6, 8, 10]</code>, mentre in realtà l’output sarebbe <code>[0, 2.5, 5, 7.5, 10]</code>.

== Implementazioni di sicurezza ==

Un errore di tipo off-by-one che può minare la sicurezza di un sistema informatico può derivare dall'errato utilizzo della funzione <code>strncat</code> , della [[Libreria standard del C|libreria standard C]]. Fraintendimento comune con questo tipo di funzione riguarda il pensare che il terminatore di sicurezza non verrà scritto oltre la lunghezza massima di una stringa. In realtà ciò accade, e il terminatore verrà scritto esattamente un byte oltre la lunghezza massima consentita specificata. Il codice di seguito presenta un bug di questo tipo:<syntaxhighlight lang="c">

void foo (char *s)

{

char buf[15];

memset(buf, 0, sizeof(buf));

strncat(buf, s, sizeof(buf)); //Il parametro finale dovrebbe essere: sizeof(buf) - 1

}

</syntaxhighlight>Errori di tipo off-by-one sono comuni nell'utilizzo delle librerie C, perché non coerenti tra loro in situazioni nelle quali, come nell’esempio, ci si deve ricordare di sottrarre un byte: funzioni come <code>fgets()</code> e <code>strncpy</code> non scriveranno mai oltre la lunghezza della stringa a loro indicata (<code>fgets()</code> sottrae 1 e restituisce soltanto (length – 1) byte), mentre altre come la <code>strncat</code> lo fanno; per questo motivo chi programma deve ricordarsi per quali funzioni sarà necessario sottrarre un byte, e per quali no.

In alcuni sistemi (in particolare architetture di tipo [[Ordine dei byte|little endian]]) questa incoerenza può causare una sovrascrittura dell’ultimo byte significativo del frame pointer. Si crea così una condizione sfruttabile per un aggressore, che può dirottare le variabile locale per la routine di chiamata.

Un approccio utile per cercare di prevenire alcuni problemi è usare varianti di queste funzioni, che calcolino quanto scrivere basandosi sulla lunghezza totale del buffer, piuttosto che sul massimo numero di caratteri da scrivere. Queste possono essere funzioni come la <code>strlcat</code> e <code>strlcpy</code>, spesso considerate più sicure perché rendono più facile prevenire scritture accidentali oltre la fine del buffer (nell'esempio di codice riportato sopra, chiamare <code>strlcat(buf, s, sizeof(buf))</code> risolverebbe il problema)

== Note ==

<references />

== Voci correlate ==

*[[Semantica formale]]

* [[Asserzione (informatica)]]

* [[Ciclo for]]

{{S|* [[Sicurezza informatica}}]]

== Collegamenti esterni ==

* {{Cita web|url=http://foldoc.org/fencepost_error|titolo=Fencepost error}}

* {{Cita web|autore=Edsger Wybe Dijkstra|data=2 maggio 2008|url=https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html|titolo=Why numbering should start at zero (EWD 831)|sito=Archivi E. W. Dijkstra|editore=[[Università del Texas a Austin]]}}

{{WPortale|informatica|gennaio 2015}}

[[Categoria:Terminologia informatica]]

[[Categoria:Sicurezza informatica]]