Error de uno por uno - Off-by-one error

Un error de uno por uno o un error de uno por uno (conocido por las siglas OBOE , OBO , OB1 y OBOB ) es un error lógico que involucra el equivalente discreto de una condición de límite . A menudo ocurre en la programación de computadoras cuando un ciclo iterativo itera una vez demasiadas o muy pocas. Este problema podría surgir cuando un programador comete errores tales como usar "es menor o igual que" donde "es menor que" debería haberse usado en una comparación, o no toma en cuenta que una secuencia comienza en cero en lugar de uno ( como con los índices de matriz en muchos idiomas). Esto también puede ocurrir en un contexto matemático .

Bucle sobre matrices

Considere una matriz de elementos, y los elementos m hasta n (inclusive) deben procesarse. ¿Cuántos artículos hay? Una respuesta intuitiva puede ser n  -  m , pero está desviada en uno, mostrando un error en el poste de la cerca ; la respuesta correcta es ( n  -  m ) + 1.

Por esta razón, los rangos en computación a menudo se representan mediante intervalos semiabiertos ; el rango de m a n (inclusive) está representado por el rango de m (inclusive) a n  + 1 (exclusivo) para evitar errores en los postes de la cerca. Por ejemplo, un bucle que se repite cinco veces (de 0 a 4 inclusive) se puede escribir como un intervalo semiabierto de 0 a 5: 

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

El cuerpo del bucle se ejecuta en primer lugar con un índice igual a 0; el índice luego se convierte en 1, 2, 3 y finalmente 4 en iteraciones sucesivas. En ese punto, el índice se convierte en 5, por lo que el índice <5 es falso y el ciclo termina. Sin embargo, si la comparación utilizada fuera < or = (menor o igual a), el ciclo se realizaría seis veces: el índice toma los valores 0, 1, 2, 3, 4 y 5. Asimismo, si el índice se inicializara a 1 en lugar de que 0, solo habría cuatro iteraciones: el índice toma los valores 1, 2, 3 y 4. Ambas alternativas pueden causar errores uno por uno.

Otro error de este tipo puede ocurrir si se usa un bucle do-while en lugar de un bucle while (o viceversa). Se garantiza que un bucle do-while se ejecutará al menos una vez.

La confusión relacionada con las matrices también puede deberse a diferencias en los lenguajes de programación. La numeración desde 0 es más común, pero algunos lenguajes comienzan la numeración de matrices con 1. Pascal tiene matrices con índices definidos por el usuario. Esto hace posible modelar los índices de la matriz después del dominio del problema.

Error de poste de valla

Una cerca recta con n secciones tiene n +1 postes.

Un error de poste de cerca (en ocasiones llamado error de poste de telégrafo, poste de luz o cerca de estacas ) es un tipo específico de error de uno por uno. Una descripción temprana de este error aparece en las obras de Vitruvio . El siguiente problema ilustra el error:

Si construye una cerca recta de 30 pies de largo con postes espaciados a 3 pies de distancia, ¿cuántos postes necesita?

La respuesta común de 10 publicaciones es incorrecta. Esta respuesta proviene de dividir la longitud de la cerca por el espacio entre cada poste, clasificándose erróneamente el cociente como el número de postes. En realidad, la cerca tiene 10 secciones y 11 postes.

En este escenario, una cerca con n secciones tendrá n + 1 postes. Por el contrario, si la cerca contiene n postes, contendrá n - 1 secciones. Es importante tener en cuenta esta relación cuando se trata del error inverso. El error inverso ocurre cuando se conoce el número de publicaciones y se supone que el número de secciones es el mismo. Dependiendo del diseño de la cerca, esta suposición puede ser correcta o incorrecta.

El siguiente problema demuestra el error inverso:

Si tiene n publicaciones, ¿cuántas secciones hay entre ellas?

La interpretación del diseño de la cerca cambia la respuesta a este problema. El número correcto de secciones para una cerca es n - 1 si la cerca es un segmento de línea independiente delimitado por un poste en cada uno de sus extremos (por ejemplo, una cerca entre dos espacios de paso), n si la cerca forma uno completo, bucle independiente (p. ej., recinto accesible mediante una superación, como un ring de boxeo), o n + 1 si los postes no se encuentran en los extremos de una cerca similar a un segmento de línea (p. ej., una cerca entre y anclada a la pared a dos edificios). La definición precisa del problema debe considerarse cuidadosamente, ya que la configuración para una situación puede dar una respuesta incorrecta para otras situaciones. Los errores de los postes de cerca provienen de contar cosas en lugar de los espacios entre ellas, o viceversa, o de no considerar si uno debe contar uno o ambos extremos de una fila.

Los errores de los postes de cerca también pueden ocurrir en unidades distintas de la longitud. Por ejemplo, la Pirámide del Tiempo , que consta de 120 bloques colocados a intervalos de 10 años entre bloques, está programado para construir 1,190 años (no 1,200), desde la instalación del primer bloque hasta el último bloque. Uno de los primeros errores en el poste de la cerca involucró el tiempo, donde el calendario juliano originalmente calculó los años bisiestos de manera incorrecta , debido a que contaba de manera inclusiva en lugar de exclusivamente, lo que arroja un año bisiesto cada tres años en lugar de cada cuatro.

"Fencepost error" puede, en raras ocasiones, referirse a un error inducido por regularidades inesperadas en los valores de entrada, que pueden (por ejemplo) frustrar completamente una implementación de función hash o árbol binario teóricamente eficiente . Este error implica la diferencia entre el comportamiento esperado y el peor de los casos de un algoritmo .

En grandes cantidades, el hecho de estar fuera de uno a menudo no es un problema importante. Sin embargo, en cantidades más pequeñas y en casos específicos donde la precisión es primordial, cometer un error de uno por uno puede ser desastroso. A veces, un problema de este tipo también se repetirá y, por lo tanto, se agravará si alguien pasa un cálculo incorrecto si la siguiente persona comete el mismo tipo de error nuevamente (por supuesto, el error también podría revertirse).

Un ejemplo de este error puede ocurrir en el lenguaje computacional MATLAB con la función de linspace() interpolación lineal , cuyos parámetros son y no . Un programador que malinterprete el tercer parámetro como el número de incrementos puede esperar que logre una secuencia, pero en su lugar obtendrá . (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]

Implicaciones de seguridad

Un error común de uno en uno que da como resultado un error relacionado con la seguridad es causado por el mal uso de la rutina de la biblioteca estándar de C. strncatUn error común strncates que la terminación nula garantizada no escribirá más allá de la longitud máxima. En realidad, escribirá un carácter nulo de terminación un byte más allá de la longitud máxima especificada. El siguiente código contiene un error de este tipo: 

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

Los errores uno por uno son comunes en el uso de la biblioteca C porque no es consistente con respecto a si uno necesita restar 1 byte; funciones como fgets()y strncpynunca escribirán más allá de la longitud dada ( fgets()resta 1 en sí, y solo recupera (longitud - 1) bytes), mientras que otros, como strncatescribirán más allá de la longitud dada. Entonces, el programador debe recordar para qué funciones necesita restar 1.

En algunos sistemas ( arquitecturas little endian en particular), esto puede resultar en la sobrescritura del byte menos significativo del puntero de la trama . Esto puede causar una condición de explotación en la que un atacante puede secuestrar las variables locales para la rutina de llamada.

Un enfoque que a menudo ayuda a evitar estos problemas es utilizar variantes de estas funciones que calculan cuánto escribir en función de la longitud total del búfer, en lugar del número máximo de caracteres a escribir. Estas funciones incluyen strlcaty strlcpy, y a menudo se consideran "más seguras" porque facilitan la escritura accidental más allá del final de un búfer. (En el ejemplo de código anterior, llamar en su strlcat(buf, s, sizeof(buf))lugar eliminaría el error).

Ver también

Otras lecturas

  • Matt Parker (2021). Humble Pi: Cuando las matemáticas van mal en el mundo real . Libros de Riverhead. ISBN 978-0593084694.

notas y referencias

Notas

Referencias