Ошибка на единицу: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Содержимое удалено Содержимое добавлено
Проблемы безопасности: некорректное пишется слитно
Нет описания правки
 
(не показаны 34 промежуточные версии 16 участников)
Строка 1: Строка 1:
'''Ошибка на единицу''' или '''ошибка неучтённой единицы''' ({{lang-en|off-by-one error}}) — логическая ошибка в алгоритме, включающая в частности дискретный вариант нарушения граничных условий. Ошибка часто встречается в программировании, когда количество итераций пошагового [[Цикл (программирование)|цикла]] оказывается на единицу меньше или больше необходимого. Например, программист при сравнении указывает «меньше или равно», вместо «меньше», или ошибается, отсчитывая начало последовательности не с нуля, а с единицы ([[Индекс (массив)|индексация]] [[Массив (программирование)|массивов]] во многих [[Язык программирования|языках программирования]] начинается с нуля).
'''Ошибка на единицу''' или '''ошибка неучтённой единицы''' ({{lang-en|off-by-one error}}) — логическая ошибка в алгоритме (или в математических вычислениях), включающая в частности дискретный вариант нарушения граничных условий.
Ошибка часто встречается в программировании, когда количество итераций пошагового [[Цикл (программирование)|цикла]] оказывается на единицу меньше или больше необходимого. Например, программист при сравнении указывает «меньше или равно» вместо «меньше», или ошибается, отсчитывая начало последовательности не с нуля, а с единицы ([[Индекс (массив)|индексация]] [[Массив (программирование)|массивов]] во многих [[Язык программирования|языках программирования]] начинается с нуля).


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


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


<source lang="c">
<source lang="c">
for (i = 0; i < 5; i++)
for (i = 0; i < 5; ++i)
{
{
/* тело цикла */
/* тело цикла */
Строка 13: Строка 15:
</source>
</source>


[[Цикл (программирование)|Тело цикла]] выполняется, начиная с 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. Обе эти альтернативы ведут к ошибке на единицу.
[[Цикл (программирование)|Тело цикла]] выполняется начиная с 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 гарантирует выполнение по крайней мере одной итерации, поскольку проверка условия осуществляется после выполнения тела цикла.
Подобная же ошибка может возникнуть, если цикл [[цикл с постусловием|do-while]] используется вместо цикла [[Цикл с предусловием|while]] (или наоборот). Цикл do-while гарантирует выполнение по крайней мере одной итерации, поскольку проверка условия осуществляется после выполнения тела цикла.


Ошибки, связанные с массивами, могут также являться результатом различия в языках программирования. Отсчёт с нуля традиционен, но некоторые языки ведут отчет с 1. В языке [[Паскаль (язык программирования)|Паскаль]] можно определять индексы<ref>Традиционно в языке Паскаль отсчет принято начинать с единицы.</ref>. Это позволяет настроить модель массива на предметную область.
Ошибки, связанные с массивами, могут также являться результатом различия в языках программирования. Отсчёт с нуля традиционен, но некоторые языки ведут отсчёт с 1. В языках [[Паскаль (язык программирования)|Паскаль]] и [[Фортран]] можно определять индексы<ref>Традиционно в языке Паскаль отсчёт принято начинать с единицы.</ref>. Это позволяет настроить модель массива на предметную область.

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

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

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

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


== Ошибка заборного столба ==
== Ошибка заборного столба ==
[[Файл:Fencepost error.svg|thumb|250px|Прямой забор с ''n'' секциями имеет ''n+1'' столбов.]]
[[Файл:Fencepost error.svg|thumb|250px|Прямой забор с ''n'' секциями имеет ''n+1'' столбов]]
Ошибка заборного столбов (иногда её называют ошибкой телеграфного столба или фонарного столба) является частным случаем ошибки на единицу. Следующая задача иллюстрирует эту ошибку:
Ошибка заборного столба (иногда её называют ошибкой телеграфного столба или фонарного столба) является частным случаем ошибки на единицу. Следующая задача иллюстрирует эту ошибку:


<blockquote>
Если вы ставите прямой забор длиной тридцать метров и ставите столбы через три метра, то сколько столбов вам необходимо?
Вы ставите прямой забор длиной 30 метров и ставите столбы каждые 3 метра. Сколько столбов вам необходимо?
</blockquote>


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


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


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


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


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


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


В качестве примера такой ошибки можно взять функцию linspace()<ref>[http://help.scilab.org/docs/5.4.1/ru_RU/linspace.html] вектор с равномерными интервалами между элементами</ref> из вычислительного языка [[MATLAB|Matlab]], параметрами которой являются: наименьшая величина, наибольшая величина и количество величин, а не: наименьшая величина, наибольшая величина и количество шагов. Программист, который неправильно поймет, что из себя представляет третий параметр, будет считать, что linspace(0,10,5) сгенерирует последовательность [0,2,4,6,8,10], но вместо этого получит [0, 2.5,5, 7.5,10].
В качестве примера такой ошибки можно взять функцию linspace()<ref>{{Cite web |url=http://help.scilab.org/docs/5.4.1/ru_RU/linspace.html |title=вектор с равномерными интервалами между элементами |access-date=2015-02-04 |archive-date=2015-02-04 |archive-url=https://web.archive.org/web/20150204142651/http://help.scilab.org/docs/5.4.1/ru_RU/linspace.html |deadlink=no }}</ref> из вычислительного языка [[MATLAB|Matlab]], параметрами которой являются: наименьшая величина, наибольшая величина и количество величин, а не: наименьшая величина, наибольшая величина и количество шагов. Программист, который неправильно поймёт, что из себя представляет третий параметр, будет считать, что linspace(0,10,5) сгенерирует последовательность [0,2,4,6,8,10], но вместо этого получит [0, 2.5, 5, 7.5, 10].


== Проблемы безопасности ==
== Проблемы безопасности ==
{{Переписать раздел}}
Обычная ошибка на единицу, которая приводит к проблеме безопасности — это некорректное использование функции [[strncat|strncat()]] из [[Стандартная библиотека языка Си|стандартной библиотеки]] [[ANSI C|C]]. Обычное недоразумение, связанное с [[strncat|strncat()]], заключается в том, что null-байт<ref>Символ, однобайтовый код которого равен нулю. Библиотека C поддерживает правило, по которому такой байт обозначает конец строки</ref> не может быть записан дальше, чем длина строки. В действительности функция пишет null-байт за указанной длиной строки, если третий параметр равен или превышает эту длину. Следующий код содержит именно такую ошибку:
Обычная ошибка на единицу, которая приводит к проблеме безопасности — это некорректное использование функции [[strncat|strncat()]] из [[Стандартная библиотека языка Си|стандартной библиотеки]] [[ANSI C|C]]. Обычное недоразумение, связанное с [[strncat|strncat()]], заключается в том, что null-байт<ref>Символ, однобайтовый код которого равен нулю. Библиотека C поддерживает правило, по которому такой байт обозначает конец строки</ref> не может быть записан дальше, чем длина строки. В действительности функция пишет null-байт за указанной длиной строки, если третий параметр равен или превышает эту длину. Следующий код содержит именно такую ошибку:


<source lang="c">
<syntaxhighlight lang="c">
void foo (char *s)
void foo (const char *s)
{
{
char buf[15];
char buf[15];
memset(buf, 0, sizeof(buf));
buf[0] = '\0';

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


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


В некоторых системах (особенно в архитектуре с порядком байтов от младшего к старшему) это может привести к переписыванию значимых байтов в стеке процесса, что может создать условие, когда злоумышленник получает данные, позволяющие ему вызывать процедуру процесса<ref>Запись данных за границу буфера называется [[Переполнение буфера|'''ошибкой переполнения буфера''']].</ref>.
В некоторых системах (особенно в архитектуре с порядком байтов от младшего к старшему) это может привести к переписыванию значимых байтов в стеке процесса, что может создать условие, когда злоумышленник получает данные, позволяющие ему вызывать процедуру процесса<ref>Запись данных за границу буфера называется [[Переполнение буфера|'''ошибкой переполнения буфера''']].</ref>.


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


== См. также ==
== См. также ==
# [[Массив (программирование)]]
*[[Массив (программирование)]]
# [[Си (язык программирования)]]
*[[Си (язык программирования)]]
# [[Ошибка (программирование)]]
*[[Ошибка (программирование)]]
# [[Отладка программы]]
*[[Отладка программы]]
# [[Стандартная библиотека языка Си]]
*[[Стандартная библиотека языка Си]]
# [[Список функций стандартной библиотеки Си]]
*[[Список функций стандартной библиотеки Си]]
# [[Переполнение стека]]
*[[Переполнение стека]]


== Примечания ==
== Примечания ==
Строка 73: Строка 87:


== Ссылки ==
== Ссылки ==
# [https://code-live.ru/post/cpp-arrays/ Массивы в C++ ]
*[https://code-live.ru/post/cpp-arrays/ Массивы в C++ ] {{Wayback|url=https://code-live.ru/post/cpp-arrays/ |date=20150421225353 }}
# [http://dolphinsbay.narod.ru/Reefs.html#1 Ошибка заборных столбов]
*[http://dolphinsbay.narod.ru/Reefs.html#1 Ошибка заборных столбов] {{Wayback|url=http://dolphinsbay.narod.ru/Reefs.html#1 |date=20150204142650 }}
# [http://wiki.mvtom.ru/index.php/%D0%9E%D1%82%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D1%8B Ошибки программирования]
*[http://wiki.mvtom.ru/index.php/%D0%9E%D1%82%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D1%8B Ошибки программирования] {{Wayback|url=http://wiki.mvtom.ru/index.php/%D0%9E%D1%82%D0%BB%D0%B0%D0%B4%D0%BA%D0%B0_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D1%8B |date=20160305112245 }}
# [http://shgpi.edu.ru/pirogov/cpp/ Заметки по языкам C и C++]
*[http://shgpi.edu.ru/pirogov/cpp/ Заметки по языкам C и C++] {{Wayback|url=http://shgpi.edu.ru/pirogov/cpp/ |date=20160414212247 }}
{{rq|wikify|style|sources}}
{{rq|wikify|style|sources}}



Текущая версия от 03:52, 6 мая 2024

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

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

[править | править код]

Обычная ошибка на единицу, которая приводит к проблеме безопасности — это некорректное использование функции strncat() из стандартной библиотеки C. Обычное недоразумение, связанное с strncat(), заключается в том, что null-байт[3] не может быть записан дальше, чем длина строки. В действительности функция пишет 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.

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

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

Примечания

[править | править код]
  1. Традиционно в языке Паскаль отсчёт принято начинать с единицы.
  2. вектор с равномерными интервалами между элементами. Дата обращения: 4 февраля 2015. Архивировано 4 февраля 2015 года.
  3. Символ, однобайтовый код которого равен нулю. Библиотека C поддерживает правило, по которому такой байт обозначает конец строки
  4. Запись данных за границу буфера называется ошибкой переполнения буфера.