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

Ошибка отклонения на единицу или ошибка отклонения на единицу (известная под аббревиатурами 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  ++  )  
 { 
     /* Тело цикла */ 
 }

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

Другая такая ошибка может возникнуть, если цикла вместо while используется цикл do- 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  ));    // Конечный параметр должен быть: 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]