Вызывает ли целочисленное переполнение неопределенное поведение из-за повреждения памяти?

Question

Я недавно прочитал, что целочисленное переполнение со знаком в C и C++ вызывает неопределенное поведение:

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

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

Поэтому я решил написать небольшую тестовую программу в Visual Studio 2015, чтобы проверить эту теорию с помощью следующего кода:

#include <stdio.h>
#include <limits.h>

struct TestStruct
{
    char pad1[50];
    int testVal;
    char pad2[50];
};

int main()
{
    TestStruct test;
    memset(&test, 0, sizeof(test));

    for (test.testVal = 0; ; test.testVal++)
    {
        if (test.testVal == INT_MAX)
            printf("Overflowing\r\n");
    }

    return 0;
}

Я использовал здесь структуру, чтобы предотвратить любые защитные проблемы Visual Studio в режиме отладки, такие как временное заполнение переменных стека и так далее. Бесконечный цикл должен вызывать несколько переполнений test.testValи это действительно так, хотя и без каких-либо последствий, кроме самого переполнения.

Я посмотрел на дамп памяти при выполнении тестов переполнения со следующим результатом (test.testVal имел адрес памяти 0x001CFAFC):

0x001CFAE5  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x001CFAFC  94 53 ca d8 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Как видите, память вокруг int, которая постоянно переполняется, осталась "неповрежденной". Я проверял это несколько раз с похожим результатом. Никогда не было никакой памяти вокруг переполненного int.

Что здесь происходит? Почему нет повреждения памяти вокруг переменной test.testVal? Как это может вызвать неопределенное поведение?

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

Answer 1

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

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

И как со всем неопределенным поведением, даже если ваше оборудование использует дополнение 2 для своей арифметики и имеет определенные правила для переполнения, компиляторы не связаны ими. Например, в течение долгого времени GCC оптимизировал любые проверки, которые выполнялись бы только в среде с двумя дополнительными компонентами. Например, if (x > x + 1) f() будет удален из оптимизированного кода, так как переполнение со знаком является неопределенным поведением, то есть никогда не происходит (с точки зрения компилятора, программы никогда не содержат код, производящий неопределенное поведение), то есть x никогда не может быть больше, чем x + 1,

Answer 2

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

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

int test(int x)
{
  int temp = (x==INT_MAX);
  if (x+1 <= 23) temp+=2;
  return temp;
}

100% надежно вернет 3, когда передаст значение INT_MAX, так как добавление 1 к INT_MAX приведет к INT_MIN, который, конечно, меньше 23.

В 1990-х годах компиляторы использовали тот факт, что целочисленное переполнение было неопределенным поведением, а не определялось как перенос двух дополнений, чтобы включить различные оптимизации, что означало, что точные результаты вычислений, которые были переполнены, не были бы предсказуемыми, но аспекты поведения, которые не учитывали не зависит от точных результатов, останется на рельсах. Компилятор 1990-х годов, учитывая приведенный выше код, вероятно, будет воспринимать его так, как если бы добавление 1 к INT_MAX давало значение, численно на единицу большее, чем INT_MAX, в результате чего функция возвращала бы 1, а не 3, или могла бы вести себя как старые компиляторы, приводя к 3. Примечание. что в приведенном выше коде такая обработка может сохранить инструкцию на многих платформах, поскольку (x+1 <= 23) будет эквивалентно (x <= 22). Компилятор может быть непоследовательным в выборе 1 или 3, но сгенерированный код не будет делать ничего, кроме как вывести одно из этих значений.

Однако с тех пор для компиляторов стало более модным использовать неспособность Стандарта навязывать какие-либо требования к поведению программы в случае целочисленного переполнения (сбой, вызванный наличием аппаратного обеспечения, когда последствия могут быть действительно непредсказуемыми), чтобы оправдать наличие компиляторов. запуск кода полностью с рельсов в случае переполнения. Современный компилятор может заметить, что программа вызовет Undefined Behavior, если x==INT_MAX, и, таким образом, заключить, что функции никогда не будет передано это значение. Если функции никогда не передается это значение, сравнение с INT_MAX может быть опущено. Если указанная выше функция была вызвана из другого модуля перевода с x==INT_MAX, она может вернуть 0 или 2; если вызывается из одной и той же единицы перевода, эффект может быть еще более странным, так как компилятор расширит свои выводы о x обратно до вызывающей стороны.

Что касается того, может ли переполнение вызвать повреждение памяти, на некоторых старых аппаратных средствах это может иметь место. На старых компиляторах, работающих на современном оборудовании, этого не произойдет. В гиперсовременных компиляторах переполнение сводит на нет структуру времени и причинности, поэтому все ставки отменены. Переполнение в оценке x + 1 может эффективно повредить значение x, которое было замечено при предыдущем сравнении с INT_MAX, и заставить его вести себя так, как будто значение x в памяти было повреждено. Кроме того, такое поведение компилятора часто удаляет условную логику, которая предотвратила бы другие виды повреждения памяти, таким образом позволяя произойти произвольному повреждению памяти.

Answer 3

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

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

Есть много ответов и сообщений в блоге о неопределенном поведении, но следующие мои любимые. Я предлагаю прочитать их, если вы хотите узнать больше о теме.

• Руководство по неопределенному поведению в C и C++, часть 1
• Что каждый программист C должен знать о неопределенном поведении #1/3

Answer 4

Поведение целочисленного переполнения не определяется стандартом C++. Это означает, что любая реализация C++ может делать все что угодно.

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

Есть аргумент, чтобы сказать, что целочисленное переполнение должно рассматриваться как ошибка, так же как целочисленное деление на ноль. Архитектура 86 года имеет даже INTO Инструкция по созданию исключения при переполнении. В какой-то момент этот аргумент может набрать достаточный вес для превращения его в основные компиляторы, после чего целочисленное переполнение может вызвать сбой. Это также соответствует стандарту C++, который позволяет реализации делать что угодно.

Вы можете представить себе архитектуру, в которой числа представлены в виде строк с нулевым символом в конце с прямым порядком байтов, причем нулевой байт говорит "конец числа". Добавление может быть сделано путем добавления байта к байту, пока не будет достигнут нулевой байт. В такой архитектуре целочисленное переполнение может перезаписать конечный ноль на единицу, что сделает результат намного длиннее и может привести к повреждению данных в будущем. Это также соответствует стандарту C++.

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

if (a+b>0) x=a+b;

может, если компилятор знает, что оба a а также b положительные, не удосужились выполнить тест, но безоговорочно добавить a в b и положить результат в x, На машине с двумя комплементами это может привести к отрицательному значению x, в явном нарушении намерений кода. Это будет полностью соответствовать стандарту.

Answer 5

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

• Даже если вы знаете, что архитектура дополняет два (или что-то еще), переполненная операция может не установить флаги, как ожидалось, поэтому оператор типа if(a + b < 0) может принять неправильную ветвь: при наличии двух больших положительных чисел, так что при сложении они переполняются, и результат, как утверждают пуристы из двух дополнений, отрицателен, но инструкция сложения может фактически не устанавливать отрицательный флаг)

• Многошаговая операция могла иметь место в более широком регистре, чем sizeof (int), без усечения на каждом шаге, и поэтому выражение вроде (x << 5) >> 5 может не отрезать левые пять битов, как вы предполагаете.

• Операции умножения и деления могут использовать вторичный регистр для дополнительных битов в произведении и деления. Если умножение переполнения "не может" переполнено, компилятор может предположить, что вторичный регистр равен нулю (или -1 для отрицательных продуктов), и не сбрасывать его до деления. Так что выражение как x * y / z может использовать более широкий промежуточный продукт, чем ожидалось.

Некоторые из них звучат как дополнительная точность, но это дополнительная точность, которая не ожидается, не может быть предсказана и на которую нельзя полагаться, и нарушает вашу ментальную модель: "каждая операция принимает N-битные операнды с двумя дополнениями и возвращает наименее значимое N биты результата для следующей операции

Answer 6

Не определено, какое значение представляет int, В памяти нет "переполнения", как вы думали.