Невизначене поведінку і теорема Ферма

    У відповідності зі стандартами 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 лютому
 
 
Програми інших переможців конкурсу, на мій погляд, нудніше і частково перекриваються з раніше наведеними прикладами.
Але ніщо не зрівняється з прикладом самого Регера — «спростуванням» компілятором теореми Ферма .
 
Він пояснює, що для якогось вбудованого програми йому потрібно було написати на 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 31 ), стандарт C + + оголошує «невизначеним дією» нескінченний цикл без зміни зовнішнього стану — тому компілятори C + + вправі вважати будь-який такий цикл кінцевим.
Компілятор легко бачить, що єдиний вихід з циклу
while(1)
— це оператор
return 1;
, а оператор
return 0;
наприкінці
fermat()
недосяжний; тому він оптимізує цю функцію до
 
int fermat (void)
{
  return 1;
}

 
Інакше кажучи, єдина можливість написати на C + + такий нескінченний цикл, який компілятор не зміг би видалити — це додати всередину циклу зміна зовнішнього стану. Найпростіший (і стандартний!) Спосіб зробити це — змінювати змінну, оголошену як
volatile
.
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.