Ошибка на единицу (KonQtg ug y;nuner)

Ошибка на единицу или ошибка неучтённой единицы (англ. off-by-one error) — логическая ошибка в алгоритме (или в математических вычислениях), включающая в частности дискретный вариант нарушения граничных условий.

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

Перебор элементов массива

Рассмотрим массив элементов, в котором обрабатываются элементы с m-го по n-й включительно. Сколько членов массива будет обработано? Ответ n-m является ошибкой на единицу и примером «ошибки заборного столба». Правильный ответ — n-m+1.

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

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

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

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

Ошибки, связанные с массивами, могут также являться результатом различия в языках программирования. Отсчёт с нуля традиционен, но некоторые языки ведут отсчёт с 1. В языках Паскаль и Фортран можно определять индексы. Это позволяет настроить модель массива на предметную область.

Количество элементов q в массиве можно подсчитать следующим образом:

q = n-m-1 в открытом интервале (A, B) где начальный и конечный элемент не включены в массив.

q= n-m+1 в закрытом интервале [A, B] где начальный и конечный элемент включены в массив.

q = n-m в полузакрытом (полуоткрытом) интервале (A, B] или [A,B) где включён в массив только один из граничных элементов.

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

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

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

Вы ставите прямой забор длиной 30 метров и ставите столбы каждые 3 метра. Сколько столбов вам необходимо?

«Очевидный» на первый взгляд ответ — 10, ошибочен.
Забор имеет 30 : 3 = 10 секций. Но столбов требуется 11, на один больше.

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

В более общем виде задача может быть сформулирована следующим образом: если есть n телеграфных столбов, сколько имеется промежутков между ними?

Корректный ответ может быть n-1, если линия столбов открыта с обоих концов; n если столбы образуют круг; n+1 — если свободные пространства с обоих концов считать промежутками. Точное определение проблемы должно быть тщательно изучено, поскольку решение, верное в одной ситуации, может дать ошибочный результат в другой. Ошибка заборного столба возникает из-за того, что считаются столбы вместо промежутков между ними или наоборот, а также пренебрежения вопросом, нужно ли рассматривать один или два конца ряда.

Ошибка заборного столба может также проявить себя при счёте других элементов, а не только длин. Примером может служить пирамида времени, которая должна состоять из 120 блоков, каждый из которых помещается на своё место с интервалом в 10 лет. Для её строительства с начала установки первого блока и до последнего блока требуется 1190 лет, а не 1200. Одним из самых ранних примеров ошибки заборного столба, касающихся времени, был Юлианский календарь, где изначально неправильно рассчитывались високосные годы по причине расчёта с включением, а не с исключением. Из-за этого в расчёте високосный год повторялся через 3 года, а не через 4.

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

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

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

Проблемы безопасности

Обычная ошибка на единицу, которая приводит к проблеме безопасности — это некорректное использование функции strncat() из стандартной библиотеки C. Обычное недоразумение, связанное с strncat(), заключается в том, что null-байт не может быть записан дальше, чем длина строки. В действительности функция пишет null-байт за указанной длиной строки, если третий параметр равен или превышает эту длину. Следующий код содержит именно такую ошибку:

void foo (const char *s) 
{
    char buf[15];
    buf[0] = '\0';

    strncat(buf, s, sizeof(buf)); // ОШИБКА - последний параметр должен быть равен sizeof(buf)-1
}

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

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

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

См. также

• Массив (программирование)
• Си (язык программирования)
• Ошибка (программирование)
• Отладка программы
• Стандартная библиотека языка Си
• Список функций стандартной библиотеки Си
• Переполнение стека

Ссылки

• Массивы в C++ Архивная копия от 21 апреля 2015 на Wayback Machine
• Ошибка заборных столбов Архивная копия от 4 февраля 2015 на Wayback Machine
• Ошибки программирования Архивная копия от 5 марта 2016 на Wayback Machine
• Заметки по языкам C и C++ Архивная копия от 14 апреля 2016 на Wayback Machine