Поочередная ошибка - Off-by-one error

Ошибка вне по одному или офф-за одной ошибку (известного под акронимами гобоя , ОВ , OB1 и OBOB ) является логической ошибкой с участием дискретного эквивалента граничного условия . Это часто происходит в компьютерном программировании, когда итерационный цикл повторяется один раз слишком много или слишком мало. Эта проблема может возникнуть, когда программист делает ошибки, такие как использование «меньше или равно», где «меньше, чем» должно было использоваться при сравнении, или не принимает во внимание, что последовательность начинается с нуля, а не с единицы ( как с индексами массивов на многих языках). Это также может происходить в математическом контексте.

Цикл по массивам

Рассмотрим массив элементов, и элементы с m по n (включительно) должны быть обработаны. Сколько там предметов? Интуитивно понятный ответ может быть n  -  m , но он отличается на единицу, показывая ошибку столбика забора ; правильный ответ ( n  -  m ) + 1.

По этой причине диапазоны в вычислениях часто представлены полуоткрытыми интервалами ; диапазон от m до n (включительно) представлен диапазоном от m (включительно) до n  + 1 (исключая), чтобы избежать ошибок в столбах ограды. Например, цикл , повторяющийся пять раз (от 0 до 4 включительно), можно записать как полуоткрытый интервал от 0 до 5: 

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

Тело цикла выполняется в первую очередь с индексом 0; затем index становится 1, 2, 3 и, наконец, 4 на последовательных итерациях. В этот момент index становится 5, поэтому index <5 ложно, и цикл заканчивается. Однако, если бы использованное сравнение было < or = (меньше или равно), цикл был бы выполнен шесть раз: index принимает значения 0, 1, 2, 3, 4 и 5. Аналогично, если index был инициализирован равным 1, скорее чем 0, то будет только четыре итерации: index принимает значения 1, 2, 3 и 4. Обе эти альтернативы могут вызывать погрешности, не равные единице.

Другая такая ошибка может возникнуть, если цикл do-while используется вместо цикла while (или наоборот). Цикл do-while гарантированно запускается хотя бы один раз.

Путаница, связанная с массивами, также может быть результатом различий в языках программирования. Чаще всего используется нумерация с 0, но в некоторых языках нумерация массивов начинается с 1. В Паскале есть массивы с определяемыми пользователем индексами. Это позволяет моделировать индексы массива после проблемной области.

Ошибка Fencepost

Прямой забор с n секциями имеет n +1 столб.

Ошибка столбика забора (иногда называемая ошибкой телеграфного столба, фонарного столба или забора из штакетника ) - это особый тип погрешности смещения на единицу. Раннее описание этой ошибки появляется в трудах Витрувия . Следующая проблема иллюстрирует ошибку:

Если вы построите прямой забор длиной 30 футов со столбами на расстоянии 3 футов друг от друга, сколько столбов вам понадобится?

Обычный ответ 10 сообщений неверен. Этот ответ возникает из-за деления длины забора на расстояние между столбами, при этом коэффициент ошибочно классифицируется как количество столбов. Фактически забор состоит из 10 секций и 11 столбов.

В этом сценарии забор с n секциями будет иметь n + 1 столб. И наоборот, если забор содержит n столбов, он будет содержать n - 1 секцию. Это соотношение важно учитывать при работе с обратной ошибкой. Обратная ошибка возникает, когда известно количество постов и предполагается, что количество разделов одинаково. В зависимости от конструкции забора это предположение может быть верным или неверным.

Следующая проблема демонстрирует обратную ошибку:

Если у вас n сообщений, сколько разделов между ними?

Интерпретация конструкции забора меняет ответ на эту проблему. Правильное количество секций для забора - n - 1, если забор представляет собой отдельно стоящий отрезок линии, ограниченный столбиком на каждом из его концов (например, забор между двумя проходами), n если забор образует единое целое, отдельно стоящая петля (например, ограждение, доступное для преодоления, такое как боксерский ринг), или n + 1, если столбики не встречаются на концах линейно-сегментного забора (например, забор между стеной и анкерным креплением к два корпуса). Необходимо тщательно продумать точное определение проблемы, поскольку установка для одной ситуации может дать неправильный ответ для других ситуаций. Ошибки Fencepost возникают из-за подсчета предметов, а не из-за пробелов между ними, или наоборот, или из-за того, что не учитывается, следует ли считать один или оба конца ряда.

Ошибки в столбах Fencepost могут также возникать в единицах измерения, отличных от длины. Например, Пирамида Времени , состоящая из 120 блоков, размещенных с 10-летними интервалами между блоками, по графику займет 1190 лет, чтобы построить (а не 1200), от установки первого блока до последнего блока. Одна из самых ранних ошибок в столбах забора связана с временем, когда юлианский календарь изначально неправильно рассчитывал високосные годы из-за того, что високосный год исчислялся не исключительно, а включительно, что давало високосный год каждые три года, а не каждые четыре.

«Ошибка Fencepost» в редких случаях может относиться к ошибке, вызванной неожиданными закономерностями во входных значениях, которые могут (например) полностью помешать теоретически эффективному двоичному дереву или реализации хеш-функции . Эта ошибка связана с различием между ожидаемым и наихудшим поведением алгоритма .

В больших количествах отсутствие одного часто не является серьезной проблемой. Однако в меньших количествах и в конкретных случаях, когда точность имеет первостепенное значение, единичная ошибка может иметь катастрофические последствия. Иногда такая проблема также повторяется и, следовательно, усугубляется тем, что кто-то передает неверный расчет, если следующий человек снова совершает такую ​​же ошибку (конечно, ошибку также можно исправить).

Пример этой ошибки может возникать в вычислительном языке MATLAB с функцией linspace() линейной интерполяции , параметры которой есть и нет . Программист, который неправильно понимает третий параметр как количество приращений, может надеяться, что достигнет последовательности, но вместо этого получит . (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]

Последствия для безопасности

Распространенная индивидуальная ошибка, которая приводит к ошибке, связанной с безопасностью, вызвана неправильным использованием стандартной библиотечной strncat процедуры C. Распространенное заблуждение strncatсостоит в том, что гарантированное завершение нуля не будет записывать сверх максимальной длины. На самом деле он запишет завершающий нулевой символ на один байт сверх указанной максимальной длины. Следующий код содержит такую ​​ошибку: 

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

Ошибки поочередности распространены при использовании библиотеки C, потому что это несовместимо с тем, нужно ли вычитать 1 байт - такие функции, как fgets()и strncpyникогда не будут записывать сверх заданной им длины ( fgets()вычитают 1 и только извлекают (длина - 1) байты), тогда как другие, подобные, strncatбудут записывать больше заданной им длины. Таким образом, программист должен помнить, для каких функций ему нужно вычесть 1.

В некоторых системах ( в частности, в архитектурах с прямым порядком байтов ) это может привести к перезаписи младшего байта указателя кадра . Это может вызвать эксплуатируемую ситуацию, когда злоумышленник может захватить локальные переменные для вызывающей процедуры.

Один из подходов, который часто помогает избежать таких проблем, заключается в использовании вариантов этих функций, которые вычисляют, сколько нужно записать, исходя из общей длины буфера, а не максимального количества записываемых символов. Такие функции включают strlcatи strlcpy, и часто считаются «более безопасными», потому что они позволяют избежать случайной записи после конца буфера. (В приведенном выше примере кода вызов strlcat(buf, s, sizeof(buf))вместо этого устранит ошибку.)

Смотрите также

дальнейшее чтение

  • Мэтт Паркер (2021). Humble Pi: Когда математика идет не так в реальном мире . Книги Риверхеда. ISBN 978-0593084694.

Примечания и ссылки

Примечания

использованная литература