Ошибка на единицу

Ошибка на единицу или ошибка неучтённой единицы (англ. 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. В языке Паскаль можно определять индексы. Это позволяет настроить модель массива на предметную область.

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

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

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

Если вы ставите прямой забор длиной тридцать метров и ставите столбы через три метра, то сколько столбов вам необходимо?

«Очевидный» на первый взгляд ответ — 10, ошибочен. Забор имеет 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 (char *s) 
{
    char buf[15];
    memset(buf, 0, sizeof(buf));
    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)) устраняет ошибку безопасности)

См. также

1. Массив (программирование)
2. Си (язык программирования)
3. Ошибка (программирование)
4. Отладка программы
5. Стандартная библиотека языка Си
6. Список функций стандартной библиотеки Си
7. Переполнение стека

Ссылки

1. Массивы в C++
2. Ошибка заборных столбов
3. Ошибки программирования
4. Заметки по языкам C и C++