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

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

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

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

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

за (индекс = 0; индекс < 5; индекс++) {    / * Тело цикла * /}

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

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

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

Ошибка Fencepost

Прямой забор с п разделы имеют п + 1 сообщения.

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

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

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

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

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

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

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

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

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

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

Пример этой ошибки может возникнуть на вычислительном языке. MATLAB с linspace () линейная интерполяция функция, параметры которой (меньшее значение, верхнее значение, количество значений) и нет (меньшее значение, верхнее значение, количество приращений). Программист, который неправильно понимает третий параметр как число приращений, может надеяться, что внутреннее пространство (0,10,5) достигнет последовательности [0, 2, 4, 6, 8, 10] но вместо этого получил бы [0, 2.5, 5, 7.5, 10].

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

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

пустота фу (char *s) {    char бух[15];    мемсет(бух, 0, размер(бух));    strncat(бух, s, размер(бух)); // Конечный параметр должен быть: 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.