Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Цикл по массивам [ править ]

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

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

for  ( index  =  0 ;  index  <  5 ;  index ++ )  {  / * Тело цикла * / }

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

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

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

Наивный ответ 10 неверен. Ограда 10 секций, но 11 столбов.

Обратная ошибка возникает, когда известно количество постов и предполагается, что количество разделов одинаково. Фактическое количество разделов на единицу меньше количества сообщений.

В более общем виде проблему можно сформулировать следующим образом:

Если у вас 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 ));  // Конечный параметр должен быть: sizeof (buf) -1 }

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

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

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

См. Также [ править ]

  • Граничный анализ
  • Принцип голубятни
  • Ошибка округления
  • Нумерация с нуля

Ссылки [ править ]

  1. ^ Монио, Роберт К., Кто первым описал "ошибку столбика забора?" , Фордхемы университета , архивируется с оригинала на 2016-03-05 , извлекаться 2016-07-07.
  • Более ранняя версия этой статьи была основана на ошибке забора в FOLDOC , использованной с разрешения .
  • Дейкстра, Эдсгер Вайб (2 мая 2008 г.). «Почему нумерация должна начинаться с нуля (EWD 831)» . EW Dijkstra Archive . Техасский университет в Остине . Проверено 16 марта 2011 .
  • В системе Common Weakness Enumeration эта проблема обозначена как CWE-193: Off-by-one Error