Ошибка отклонения на единицу

Ошибка отклонения на единицу или ошибка отклонения на единицу (известная под аббревиатурами OBOE , OBO , OB1 и OBOB ) — это логическая ошибка , которая включает в себя число, которое отличается от его предполагаемого значения на +1 или -1. Ошибка отклонения на единицу иногда может появиться в математическом контексте. Это часто происходит в компьютерном программировании, когда цикл повторяется один раз слишком много или слишком мало, обычно это вызвано использованием нестрогого неравенства (≤) в качестве условия завершения там, где должно было использоваться строгое неравенство (<), или наоборот. Ошибки отклонения на единицу также возникают из-за путаницы с нумерацией, начинающейся с нуля .

Случаи

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

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

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

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

Ошибка столба забора

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

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

Для прямого забора из 10 секций требуется 11 столбов. В более общем смысле, для n разделов потребуется n + 1 сообщение.

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

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

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

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

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

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

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

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

Пример этой ошибки может возникнуть в вычислительном языке 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].

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

Распространенная ошибка отклонения на единицу, которая приводит к ошибке, связанной с безопасностью, вызвана неправильным использованием стандартной библиотеки C. strncat рутина. Распространенное заблуждение, связанное с 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)) вместо этого удалил бы ошибку.)

См. также

Ссылки

Цитаты

^ Монио, Роберт К., Кто первым описал «ошибку столба забора?» , Университет Фордхэма , заархивировано из оригинала 5 марта 2016 г. , получено 7 июля 2016 г.
^ Рэймонд, Эрик. «Жаргонный файл» . Проверено 17 мая 2021 г.

Источники

Более ранняя версия этой статьи была основана на ошибке в столбе забора в FOLDOC и использовалась с разрешения .
Дейкстра, Эдсгер Вайбе (2 мая 2008 г.). «Почему нумерация должна начинаться с нуля (EWD 831)» . Архив Э. В. Дейкстры . Техасский университет в Остине . Проверено 16 марта 2011 г.
В системе перечисления общих слабостей эта проблема указана как CWE-193: Ошибка отклонения на единицу.

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

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

[1] Монио, Роберт К., Кто первым описал «ошибку столба забора?» , Университет Фордхэма , заархивировано из оригинала 5 марта 2016 г. , получено 7 июля 2016 г.

[2] Рэймонд, Эрик. «Жаргонный файл» . Проверено 17 мая 2021 г.

[1]

[2]