Почему перенос при целочисленном переполнении — не очень хорошая идея

2018-10-25 в 8:26, admin, рубрики: C, c/c++, c++, undefined behavior, wrapping, Блог компании PVS-Studio, всё сложно, неопределённое поведение, переполнение int, Си

Эта статья посвящена неопределённому поведению и оптимизациям компилятора, особенно в контексте знакового целочисленного переполнения.

Примечание от переводчика: в русском языке нет четкого соответствия в употребляемом контексте слова «wrap»/«wrapping». Существует математический термин "перенос", который близок к описываемому явлению, а термин "флаг переноса" (carry flag) — механизм выставления флага в процессорах при целочисленном переполнении. Другим вариантом перевода может быть фраза «вращение/переворот/оборот вокруг нуля». Она лучше отображает смысл «wrap» по сравнению с «перенос», т.к. показывает переход чисел при переполнении из положительного в отрицательный диапазон. Однако, как оказалось, эти слова смотрятся в тексте непривычно для тестовых читателей. Для упрощения в дальнейшем примем в качестве перевода термина «wrap» слово «перенос».

Компиляторы языка C (и C++) в своей работе всё чаще руководствуются понятием неопределённого поведения — представлением о том, что поведение программы при некоторых операциях не регламентировано стандартом и что, генерируя объектный код, компилятор вправе исходить из предположения, что программа таких операций не производит. Немало программистов возражало против такого подхода, поскольку сгенерированный код в этом случае может вести себя не так, как задумывал автор программы. Эта проблема становится всё острее, так как компиляторы применяют всё более хитроумные методы оптимизации, которые наверняка будут опираться на понятие неопределённого поведения.

В этом контексте показателен пример со знаковым целочисленным переполнением. Большинство разработчиков на C пишут код для машин, в которых для представления целых чисел используется дополнительный код, а сложение и вычитание в таком представлении реализованы точно так же, в беззнаковой арифметике. Если сумма двух положительных целых чисел со знаком переполнится — то есть станет больше, чем вмещает тип, — процессор выдаст значение, которое, будучи интерпретировано как второе дополнение знакового числа, будет считаться отрицательным. Это явление называется «переносом», поскольку результат, дойдя до верхней границы диапазона значений, «переносится» и начинается с нижней границы.

По этой причине можно иногда увидеть вот такой код на C:

int b = a + 1000;
if (b < a) { // переполнение
    puts("input too large!"); return;
}

Задача оператора if — обнаружить состояние переполнения (в данном случае оно возникает после прибавления 1000 к значению переменной a) и сообщить об ошибке. Проблема в том, что в C знаковое целочисленное переполнение является одним из случаев неопределённого поведения. Компиляторы с некоторых пор считают такие условия всегда ложными: если прибавить 1000 (или любое другое положительное число) к другому числу, результат не может быть меньше начального значения. Если же происходит переполнение, значит, возникает неопределённое поведение, и не допускать этого — уже (по-видимому) забота самого программиста. Поэтому компилятор может решить, что условный оператор можно целиком удалить в целях оптимизации (ведь условие всегда ложно, оно ни на что не влияет, значит, можно обойтись без него).

Проблема в том, что этой оптимизацией компилятор убрал проверку, которую программист добавил специально, чтобы выявить неопределённое поведение и обработать его. Вот тут можно посмотреть, как это происходит на практике. (Примечание: сайт godbolt.org, на котором размещён пример, очень классный! Можно редактировать код и сразу же смотреть, как его обрабатывают разные компиляторы, а их там представлено множество. Поэкспериментируйте!). Обратите внимание, что компилятор не убирает проверку на переполнение, если изменить тип на беззнаковый, поскольку поведение при беззнаковом переполнении в языке С определено (точнее, при беззнаковой арифметике результат переносится, поэтому переполнения на самом деле не происходит).

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

Перенос при переполнении — полезное поведение.
Перенос — это поведение, которого ожидают программисты.
Семантика неопределённого поведения при переполнении не даёт заметного преимущества.
Стандарт языка C в отношении неопределённого поведения разрешает реализации «полностью игнорировать ситуацию, при этом результат будет непредсказуем», но это не даёт компилятору права оптимизировать код, исходя из предположения, будто ситуация с неопределённым поведением не случится вовсе.

Разберём каждый пункт по очереди:

Перенос при переполнении — полезное поведение?

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

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

if (a > INT_MAX - 1000) { // будет ли переполнение
    puts("input too large!");
    return;
}
int b = a + 1000;

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

Учитывая всё это, я нахожу неубедительным аргумент, будто перенос полезен в большинстве случаев.

Перенос — это поведение, которого ожидают программисты?

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

Очевидное решение проблемы (ожидание программистами именно этого поведения) — сделать так, чтобы компилятор выдавал предупреждение, когда он оптимизирует код, предполагая отсутствие неопределённого поведения. К сожалению, как мы видели в примере на сайте godbolt.org по ссылке выше, компиляторы не всегда поступают таким образом (Gcc версии 7.3 — да, а версии 8.1 — нет, так что налицо шаг назад).

Семантика неопределённого поведения при переполнении не даёт заметного преимущества?

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

Я допускаю, что конкретно этой оптимизацией (удаление проверок математически противоречивых условий) в обычных программах на C зачастую можно пренебречь, так как их авторы стремятся к наилучшей производительности и всё равно оптимизируют код вручную: то есть, если очевидно, что данный оператор if содержит условие, которое никогда не будет истинным, программист, скорее всего, уберёт его сам. В самом деле, я выяснил, что в нескольких исследованиях эффективность такой оптимизации была поставлена под вопрос, протестирована и признана практически несущественной в рамках контрольных тестов. Однако, хотя эта оптимизация почти никогда не даёт преимущества в языке C, генераторы кода и оптимизации компиляторов в большинстве своём универсальны и могут использоваться в других языках — и для них данный вывод может быть неверен. Возьмём язык C++ с его, скажем так, традицией полагаться на оптимизатор, чтобы тот убирал избыточные конструкции в коде шаблонов, а не делать это вручную. А ведь существуют и языки, которые преобразуются транспайлером в C, и при этом избыточный код в них также оптимизируется C-компиляторами.

Кроме того, даже если сохранить проверки на переполнение, вовсе не факт, что прямая стоимость переноса целочисленных переменных будет минимальной даже на машинах, использующих дополнительный код. Архитектура Mips, например, может выполнять арифметические операции только в регистрах фиксированного размера (32 бита). Тип short int, как правило, имеет размер 16 бит, а char — 8 бит; при хранении в регистре переменной одного из этих типов её размер расширится, и, чтобы корректно перенести её, потребуется выполнить по крайней мере одну дополнительную операцию и, возможно, задействовать дополнительный регистр (чтобы вместить соответствующую битовую маску). Должен признать, что я уже давно не имел дела с кодом для Mips, так что я не уверен насчёт точной стоимости этих операций, но я уверен, что она ненулевая и что на других архитектурах RISC могут возникнуть такие же проблемы.

Стандарт языка запрещает избегать переноса переменных, если оно предполагается архитектурой?

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

ПРИМЕЧАНИЕ: Неопределённое поведение может принимать вид от полного игнорирования ситуации, при этом результат будет непредсказуем, ...

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

Прежде всего, следует заметить, что этот текст дан как «примечание», а потому не является нормативным (т.е. не может что-то предписывать), согласно директиве ISO, упомянутой в предисловии к стандарту:

В соответствии с Частью 3 Директив ISO/IEC, данное предисловие, введение к тексту, примечания, сноски и примеры также носят исключительно информационный характер.

Поскольку этот фрагмент о «неопределённом поведении» является примечанием, он ничего не предписывает. Обратите внимание, что настоящее определение понятия «неопределённое поведение» звучит так:

поведение, возникающее при использовании непереносимой или некорректной программной конструкции или некорректных данных, к которому настоящий Международный Стандарт не предъявляет никаких требований.

Я выделил главную мысль: к неопределённому поведению не предъявляется никаких требований; список «возможных видов неопределённого поведения» в примечании содержит лишь примеры и не может быть окончательным предписанием. Фразу «не предъявляет никаких требований» невозможно истолковать как-то иначе.

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

Размышления напоследок

Доводы в защиту переноса по большей части несостоятельны. Пожалуй, самый сильный аргумент получается, если их объединить: на перенос иногда рассчитывают менее опытные программисты (которые не знают тонкостей языка C и неопределённого поведения в нем), и оно не снижает производительность — хотя последнее верно не во всех случаях, а первая часть неубедительна, если рассматривать её отдельно.

Лично я предпочёл бы, чтобы переполнения блокировались (trapping), а не переносились. То есть, чтобы программа падала, а не продолжала работать — с неопределённым ли поведением или потенциально некорректным результатом, ведь и в том, и в другом случае появляется уязвимость. Такое решение, конечно, немного снизит производительность на большинстве (?) архитектур, особенно на x86, но, с другой стороны, ошибки, связанные с переполнением, будут сразу выявлены и ими не получится воспользоваться или получить с их помощью некорректные результаты дальше по ходу выполнения программы. Кроме того, в теории компиляторы при таком подходе могли бы безопасно удалять избыточные проверки на переполнение, поскольку оно точно не случится, хотя, как я вижу, ни Clang, ни GСС этой возможностью не пользуются.

К счастью, и прерывание, и перенос реализованы в компиляторе, которым я пользуюсь чаще всего, — GCC. Для переключения между режимами используются аргументы командной строки -ftrapv и -fwrapv соответственно.

Действий, приводящих к неопределённому поведению, конечно же, много — целочисленное переполнение лишь одно из них. Я вовсе не считаю, что все эти случаи полезно трактовать как неопределённое поведение, и я уверен, что существует немало специфических ситуаций, когда семантика должна определяться языком или, по крайней мере, оставаться на усмотрение реализаций. И я опасаюсь излишне вольных трактовок этого понятия производителями компиляторов: если поведение компилятора не отвечает интуитивным представлениям разработчиков, особенно тех, кто лично читал текст стандарта, это может привести к реальным ошибкам; если прирост производительности в этом случае пренебрежимо мал, то лучше от таких трактовок отказаться. В одном из следующих постов я, возможно, разберу некоторые из этих проблем.

Дополнение (от 24 августа 2018 года)

Я понял, что многое из сказанного выше можно было бы написать лучше. Ниже я кратко резюмирую и поясню свои слова и добавлю несколько мелких замечаний:

Я не утверждал, что неопределённое поведение предпочтительнее переноса при переполнении — скорее, что на практике перенос ненамного лучше неопределённого поведения. В частности, проблемы с безопасностью можно получить что в первом случае, что во втором — и я готов поспорить, что многие из уязвимостей, спровоцированных неотловленными вовремя переполнениями (кроме тех, за которые ответственен компилятор, удаливший ошибочные проверки), на самом деле появились из-за переноса результата, а не из-за неопределённого поведения, связанного с переполнением.
Единственное реальное преимущество переноса состоит в том, что проверки на переполнение не удаляются. Хотя так можно обезопасить код от некоторых сценариев атак, остаётся вероятность, что часть переполнений не будет проверена совсем (т.е. программист забудет добавить такую проверку) и останется незамеченной.
Если вопрос безопасности не столь важен, и на первый план выходит высокая скорость работы программы, то неопределённое поведение даст более выгодную оптимизацию и больший прирост производительности, по крайней мере в некоторых случаях. С другой стороны, если безопасность превыше всего, перенос чреват уязвимостями.
Это значит, что, если выбирать между прерыванием, переносом и неопределённым поведением, то задач, в которых перенос может быть полезен, очень мало.
Что же касается проверок на возникшее переполнение, я считаю, что оставлять их вредно, потому что создаётся ложное впечатление, будто они работают и будут работать всегда. Прерывание переполнений позволяет избежать этой проблемы; адекватные предупреждения — смягчить её.
Думаю, любой разработчик, пишущий критичный с точки зрения безопасности код, в идеале должен хорошо владеть семантикой языка, на котором он пишет, а также знать о его подводных камнях. Применительно к C это означает, что необходимо знать семантику переполнения и тонкости неопределённого поведения. Печально, что некоторые программисты так и не доросли до этого уровня.
Мне встречалось утверждение, будто бы «большинство программистов на C ожидают переноса в качестве поведения по умолчанию», но свидетельств этого мне неизвестно. (В статье я написал «некоторые программисты», потому что знаю несколько примеров из реальной жизни, и вообще сомневаюсь, что кто-то будет с этим спорить).
Есть две разные проблемы: что требует стандарт языка C и что должны реализовывать компиляторы. Меня (в целом) устраивает то, как стандарт определяет неопределённое поведение при переполнении. В этом посте я говорю о том, что должны делать компиляторы.
При прерывании переполнения нет нужды проверять на него каждую операцию. В идеале программа при таком подходе либо ведёт себя непротиворечиво с точки зрения математических правил, либо прекращает работу. При этом становится возможным существование «временного переполнения», которое не приводит к появлению некорректного результата. Тогда и выражение a + b — b, и выражение (a * b) / b можно оптимизировать до a (первое возможно и при переносе, а вот второе — уже нет).

Примечание. Перевод статьи публикуется в блоге с разрешения автора. Оригинальный текст: Davin McCall "Wrap on integer overflow is not a good idea".

Дополнительные ссылки по теме от команды PVS-Studio: