tyomitch Jul 16 2014 at 03:48

Неопределённое поведение и теорема Ферма

4 min

55K

В соответствии со стандартами C и C++, если выполнение программы приводит к переполнению знаковой целой переменной, или к любому из сотен других «неопределённых действий» (undefined behaviour, UB), то результат выполнения программы может быть любым: она может запостить на Твиттер непристойности, может отформатировать вам диск…
Увы, в действительности «пасхальные яйца», которые бы заставляли программу в случае UB делать что-то из ряда вон выходящее, не встречались со времён GCC 1.17 — та запускала nethack, когда встречала в коде программы неизвестные #pragma. Обычно же результат UB намного скучнее: компилятор просто оптимизирует код для тех случаев, когда UB не происходит, не придавая ни малейшего значения тому, что этот код будет делать в случае UB — ведь стандарт разрешает сделать в этом случае что угодно!
В качестве иллюстрации того, как изобилие UB в стандарте позволяет компилятору выполнять неочевидные оптимизации, Реймонд Чен приводит такой пример кода:

int table[4];
bool exists_in_table(int v)
{
    for (int i = 0; i <= 4; i++) {
        if (table[i] == v) return true;
    }
    return false;
}

В условии цикла мы ошиблись на единицу, поставив <= вместо <. В итоге exists_in_table() либо должна вернуть true на одной из первых четырёх итераций, либо она прочтёт table[4], что является UB, и в этом случае exists_in_table() может сделать всё что угодно — в том числе, вернуть true! В полном соответствии со стандартом, компилятор может соптимизировать код exists_in_table() до

int table[4];
bool exists_in_table(int v)
{
    return true;
}

Такие оптимизации иногда застают программистов врасплох. Джон Регер приводит подборку примеров, когда UB приводило к значительным последствиям:

UB при знаковом сдвиге влево позволило компилятору удалить из NaCl проверку адреса возврата, важную для безопасности.
В ядре Linux, разыменование указателя перед его проверкой на NULL позволило компилятору удалить эту проверку, создав уязвимость в системе.
В Debian, использование неинициализированного массива в качестве источника случайных данных для инициализации RNG seed привело к тому, что всё вычисление seed было удалено компилятором.
Когда переменная p не инициализирована, программа может выполнить и код внутри if (p) { ... }, и код внутри if (!p) { ... }.
Когда знаковая переменная x равна INT_MAX, выражение (x+1)>x в разных местах одной программы может трактоваться и как истинное, и как ложное.
Бесконечный цикл, например поиск несуществующего значения, может быть удалён компилятором. Например, так компилятор может «опровергнуть» Великую теорему Ферма. (Этот пример мы ещё разберём подробно.)
Компилятор может сделать программу «ясновидящей», переставив операцию, потенциально способную обрушить процесс (деление на ноль, чтение по нулевому указателю и т.п.), вперёд операции вывода. Например, вот этот код:
```
int a;

void bar (void)
{
  setlinebuf(stdout);
  printf ("hello!\n");
}

void foo3 (unsigned y, unsigned z)
{
  bar();
  a = y%z;
}

int main (void)
{
  foo3(1,0);
  return 0;
}
```
— успеет напечатать сообщение перед SIGFPE, если его скомпилировать без оптимизаций; и рухнет сразу при старте, если включить оптимизацию. Программа «заранее знает», что ей суждено упасть с SIGFPE, и поэтому даже не заморачивается печатью сообщения. Похожий пример, только с SIGSEGV, приводит и Чен.

В 2012 Регер объявил конкурс на «самый причудливый результат UB». Один из победителей воспользовался тем, что использование указателя после того, как он передан параметром в realloc(), является UB. Его программа печатает разные значения по одному и тому же указателю:

#include <stdio.h>
#include <stdlib.h>
 
int main() {
  int *p = (int*)malloc(sizeof(int));
  int *q = (int*)realloc(p, sizeof(int));
  *p = 1;
  *q = 2;
  if (p == q)
    printf("%d %d\n", *p, *q);
}

$ clang -O realloc.c ; ./a.out 
1 2

Программы остальных победителей конкурса, на мой взгляд, скучнее и частично перекрываются с ранее приведёнными примерами.
Но ничто не сравнится с примером самого Регера — «опровержением» компилятором теоремы Ферма.

Он объясняет, что для какого-то встроенного приложения ему нужно было написать на C++ бесконечный цикл так, чтобы оптимизирующий компилятор не смог удалить из программы весь код, следующий за циклом. Современные компиляторы достаточно умны, чтобы узнавать «идиомы» навроде while (1) { } или for (;;) { } — они понимают, что код, следующий за таким циклом, никогда не выполнится, а значит, его и компилировать незачем. Например, функцию

  void foo (void)
  {
    for (;;) { }
    open_pod_bay_doors();
  }

— большинство компиляторов «укоротят» до единственной инструкции:

  foo:
    L2: jmp L2

Clang оказывается ещё умнее, он способен распознавать (и удалять) даже такие замаскированные бесконечные циклы:

  unsigned int i = 0;
  do {
    i+=2;
  } while (0==(i&1));

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

Регер решил: уж теорему Ферма-то компиляторы вряд ли смогут доказать во время компиляции?

int fermat (void)
{
  const int MAX = 1000;
  int a=1,b=1,c=1;
  while (1) {
    if (((a*a*a) == ((b*b*b)+(c*c*c)))) return 1;
    a++;
    if (a>MAX) {
      a=1;
      b++;
    }
    if (b>MAX) {
      b=1;
      c++;
    }      
    if (c>MAX) {
      c=1;
    }
  }
  return 0;
}

#include <stdio.h>

int main (void)
{
  if (fermat()) {
    printf ("Fermat's Last Theorem has been disproved.\n");
  } else {
    printf ("Fermat's Last Theorem has not been disproved.\n");
  }
  return 0;
}

regehr@john-home:~$ icc fermat2.c -o fermat2
regehr@john-home:~$ ./fermat2
Fermat's Last Theorem has been disproved.
regehr@john-home:~$ suncc -O fermat2.c -o fermat2
"fermat2.c", line 20: warning: statement not reached
regehr@john-home:~$ ./fermat2
Fermat's Last Theorem has been disproved.

Как так? Цикл завершится по return 1; — компилятор смог доказать, что теорема Ферма неверна?!

Интересно, какие же значения a,b,c он «нашёл»?

Регер добавил печать «найденных значений» перед return 1; — вот тогда компилятор признал бессилие и честно скомпилировал бесконечный цикл. (Ничего, естественно, не напечаталось.)

Несмотря на то, что эта программа не содержит никаких арифметических переполнений (множители изменяются в пределах 1..1000, сумма их кубов не превосходит 2³¹), стандарт C++ объявляет «неопределённым действием» бесконечный цикл без изменения внешнего состояния — поэтому компиляторы C++ вправе считать любой такой цикл конечным.
Компилятор легко видит, что единственный выход из цикла while(1) — это оператор return 1;, а оператор return 0; в конце fermat() недостижим; поэтому он оптимизирует эту функцию до

int fermat (void)
{
  return 1;
}

Иначе говоря, единственная возможность написать на C++ такой бесконечный цикл, который компилятор не смог бы удалить — это добавить внутрь цикла изменение внешнего состояния. Самый простой (и стандартный!) способ сделать это — изменять переменную, объявленную как volatile.

Tags:

Hubs: