2011-04-10:

Przemyślenia: int'y w programowaniu

int:x86:c:c++:code
Ostatnio trochę zajmowałem się trochę różnymi podejściami do problemu kodowania i operowaniu na liczbach całkowitych i naturalnych w programowaniu. Niniejszy post stanowi podsumowanie tego czego się dowiedziałem oraz dodatkowo, drobny rancik na temat C/C++ (innym językom dostanie się, być może, rykoszetem).

Post podzielony jest na dwie podczęści:
1. Część o trzech arytmetykach (modulo, saturacja i constraint + bonus w postaci resizable int) i ich podejściach do problemu integer overflow/underflow.
2. Część o kodowaniu U2 i problemach wynikającym z faktu, że liczb ujemnych jest więcej niż dodatnich.

Pod koniec części pierwszej jest pewne pytanie do czytelników - zachęcam do rzucenia okiem i odpowiedzenia na nie (w miarę możliwości) ;>

Osoby początkujące zachęcam również do rzucenia okiem na post o zmiennych.

Modulo, saturacja, sygnalizowanie przepełnień


Pierwszy problem (z dwóch) który omówię, dotyczy problemu przepełnienia zmiennej - zdefiniuje tutaj dwa pojęcia (zapewne znane większości moich czytelników):

Integer Overflow (dalej: int OF) - czyli próba zakodowania (np. w wyniku operacji arytmetycznej) większej wartości niż dany typ (całkowity/naturalny) na to pozwala, np. int x = INT_MAX; x++;
Integer Underflow (dalej: int UF) - czyli próba zakodowania mniejszej wartości niż dany typ na to pozwala, np. int x = INT_MIN; x--;

No i powstają dwa pytania: jaką wartość ma przyjąć zmienna w takim przypadku, oraz jak sprawdzić czy int OF/UF wystąpiło.

Podejścia są trzy (a w zasadzie cztery; omówię tylko przypadek int OF; int UF jest analogiczny; wady i zalety są IMHO):

Modulo / Truncate


Natywnym dla x86 podejściem jest wyliczenie pełnej wartości (binarnie) i obcięcie jej do dostępnej ilości bitów. Np.

uint8_t x = 0xff;
x += 2;
(bin)      1111 1111  wartość x
(bin)    + 0000 0010  "2" binarnie
     --------------  dodawanie
(bin)    1 0000 0001  pełen wynik
     --------------  truncate do 8 bitów
(bin)      0000 0001  wynik

W tym szczególnym przypadku obcięcie zmiennej nie jest oczywiście efektem celowej operacji modulo (reszta z dzielenia) czy bitwise AND (którym można zastąpić modulo w przypadku gdy dzielnik jest potęgą dwójki), a raczej efektem ubocznym wielkości rejestru.
Natomiast można spokojnie uogólnić to do:

wynik_końcowy = pełen_wynik % (max_możliwa_wartość + 1)

Dodam jeszcze, że w przypadku x86 rejestr flagowy EFLAGS zawiera dwie flagi, które sygnalizują czy nastąpiło przepełnienie:

flaga OF (Overflow Flag) - która dotyczy liczb całkowitych (np. int) i jest ustawiana jeśli nastąpi przekroczenie wartości maksymalnej lub minimalnej dla danego typu (np. INT_MAX+1 dla int32_t)
flaga CF (Carry Flag) - która dotyczy liczb naturalnych (np. unsigned int) i której działanie jest analogiczne do OF (np. UINT_MAX+1 dla uint32_t)
Oczywiście OF i CF są też odpowiednio ustawiane przy operacjach innych niż dodawanie (np. mnożenie MUL czy IMUL, etc).

Zalety:
* Operacje modulo bardzo ułatwiają "łączenie" kilku mniejszych uint'ów (np. 32-bitowych) w celu uzyskania np. 128-bitowego uint'a - np. zaprogramowanie dodawania dwóch 128-bitowych uint'ów (oczywiście niesupportowanych natywnie) jest trywialne i sprowadza się do serii 1*ADD i 3*ADC (add with carry). Wynika to z faktu, że "niższe bity" mają poprawne wartości, więc można je zachować i iść dalej liczyć wyższe bity (w przypadku np. arytmetyki ze staturacją było by to duuużo bardziej skomplikowane).
* Operacja modulo umożliwia optymalizacje dzielenia przez stałą liczbę via mnożenie, np. zamiast dzielić int32_t przez 7, można pomnożyć przez -1227133513 (sic!) (zresztą, kompilatory C/C++ korzystają z tego od pewnego czasu). Więcej info można znaleźć tutaj lub tutaj.

Wady:
* Problem integer overflow jest znany w bezpieczeństwie aż za bardzo. Przypuszczam, że każdy bug hunter ma uśmiech od ucha do ucha gdy widzi x = malloc(uint_from_user + 1); memcpy(x, data_from_user, uint_from_user);.
* Wymaga dodatkowych flag do przekazania informacji o wystąpieniu overflow/underflow.

Saturacja


Zapewne część z was pamięta saturację (nasycenie) z chemii (patrz roztwór nasycony). W przypadku chemii chodziło o roztwór do którego jest dosypywana pewna substancja która się w nim rozpuszcza - ale tylko do pewnego momentu, tj. do pełnego nasycenia. Od tego momentu roztwór nie może się już więcej nasycić, czyli de facto ilość substancji w roztworze się nie zmienia (tj. substancja gdzieś tam na dnie się osadza w postaci osadu, ale się już nie rozpuszcza).
W przypadku matematyczno-informatycznym jest podobnie, tj. możemy zwiększać wartość zmiennej tylko do osiągnięcia jej maksymalnej wartości. Kolejne próby zwiększenia wartości nie powodują jej zmiany, ponieważ zmienna się już nasyciła.
Przykładowo, gdyby operacje na int32_t w C/C++ były operacjami z saturacją, to INT_MAX + 1234 dałoby w rezultacie po prostu INT_MAX (analogicznie w drugą stronę, czyli INT_MIN - 1234 dałby i tak INT_MIN).

Jeśli chodzi o x86, to operacje z saturacją są natywne dla liczb zmiennoprzecinkowych (z poziomu C/C++: float, double, long double). Są także dostępne dla int'ów w rozszerzeniu MMX - patrz instrukcje typu PADDSx (Add Packed Signed Integers with Signed Saturation) czy PSUBUSx (Subtract Packed Unsigned Integers with Unsigned Saturation).
Również architektura ARM dysponuje int'ami z saturacją via instrukcje z prefixem Q, np. QADD czy QSUB.

Zalety:
* Rozwiązuje problem integer overflow w bezpieczeństwie (uint_from_user+1 nigdy nie da liczby mniejszej).
* Przydatne w grafice komputerowej.
* W zasadzie nie wymaga dodatkowych flag do stwierdzenia czy zmienna jest nasycona czy nie (chociaż takie flagi są przydatne).

Wady:
* Trudniejsza do zaimplementowania (na poziomie bramek logicznych), a software'owe implementacje są ofc. wolniejsze niż arytmetyka modulo.

Więzy integralności / Constraints


Oba powyższe podejścia, z pewnego punktu widzenia, starają się naprawić zmienną w której doszło do OF/UF. Oczywiście, jedna z zasad bezpiecznego programowania mówi "nigdy nie staraj się naprawiać uszkodzonych danych otrzymanych od usera".
I tak oto dochodzimy do constraintów, czyli założenia, że zmienna typu (np.) int spełnia constrainty jesli jest w przedziale INT_MIN do INT_MAX. Jeśli w wyniku danej operacji otrzymana wartość będzie spoza tego zakresu (czyli constrainty nie zostaną spełnione), powinno to zostać w jednoznaczny sposób zasygnalizowane, np. poprzez rzucenie wyjątku. Czyli INT_MAX+1 powoduje rzucenie exceptionu.

Właśnie w ten sposób zrealizowane jest to w języku ADA (thx dla mulandera za polecenie mi tego języka):

with Ada.Text_IO, Ada.Integer_Text_IO;

procedure Hello is
 X : Integer;
begin
 Ada.Integer_Text_IO.Get(Item => X);
 X := X + 1;
 Ada.Text_IO.Put("Res:" & Integer'Image(X));
end Hello;

>hello
16#7fffffff#

raised CONSTRAINT_ERROR : hello.adb:7 overflow check failed

Swoją drogą, ciekawy zapis hexadecymalny jest w Ada ;>

Zalety:
* Świetna sygnalizacja int OF/UF.
* Rzucony wyjątek powoduje, że (potencjalnie błędy) kod alokujący pamięć nigdy się nie wykona.

Wady:
* Software'owa implementacja jest ofc wolniejsza od natywnej.
* Nieobsłużony wyjątek crashuje program. Źle obsłużony wyjątek powoduje inne błędy. O ile nie jest to problem podejścia a programisty, to to zachowanie może być potencjalnie "błędogenne".

Bonus: Zwiększanie wielkości zmiennej "on demand"


Pewnym rozwiązaniem w którym problem overflow/underflow w ogóle nie występuje, jest stworzenie typu, który w momencie potencjalnego przekroczenia zakresu zmiennej po prostu dokłada kolejne bajty do wielkości zmiennej, sprawiając tym samym że dana wartość może być w niej zakodowana. Np. (w pseudokodzie ofc):

int x = INT_MAX; [sizeof(x) → 4]
x++;             [sizeof(x) → 8]

Rozwiązanie tego typu stosowane jest w niektórych językach skryptowych, np. w Pythonie:

>>> x=1234
>>> for i in range(1,10):
...   x=x*x
...   print "size:", x.__sizeof__(), "value:", x
...
size: 12 value: 1522756
size: 20 value: 2318785835536
size: 26 value: 5376767751082385640407296
size: 36 value: 28909631449079534909981650669567912283424770031616
size: 58 value: 8357667905216084894...[i 80 kolejnych cyfr]
size: 102 value: 698506128138790206...[i 180 kolejnych cyfr]
size: 190 value: 4879108110474440...[i 380 kolejnych cyfr]
size: 366 value: 2380569595369...[i 770 kolejnych cyfr]
479817216
size: 716 value: 5667111598398...[i 1570 kolejnych cyfr]

Zalety:
* Overflow? Jaki overflow?
* "Bignumy" gratis.

Wady:
* Niewątpliwie są to dużo bardziej złożone typy niż prosty natywny int, w związku z czym operacje na nich są dużo wolniejsze.
* Dochodzi problem potencjalnego wyczerpania pamięci i zwiększającej się ilości cykli potrzebnych do wykonywania operacji arytmetycznych wraz ze wzrostem wielkości zmiennej (od razu mi się nasuwa przypadek w którym atakujący może wywołać x *= x; wystarczającą ilość razy żeby "zjeść" całą dostępną pamięć).

Podsumowanie arytmetyk


Stare dobre chińskie przysłowie mówi "use the right tool for the right job". I tak, zazwyczaj arytmetyka modulo jest najlepszym wyjściem, z prostego powodu: jest najszybsza i natywna dla większości platform (a już na pewno dla x86). Natomiast arytmetyka z saturacją lub constraintami powinna być używana w miejscach gdzie overflow/underflow jest bardzo niemile widziany - np. w obliczaniu ilości pamięci do zaalokowania na podstawie danych otrzymanych od atakującego (ah, przepraszam, od usera ofc).

I tutaj pojawia się problem - np. C/C++ int OF/UF jest UB (Undefined Behavior), czyli de facto standard nie gwarantuje z którą arytmetyką będziemy mieli do czynienia:

3.4.3 unde?ned behavior
behavior,upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements
EXAMPLE  An example of unde?ned behavior is the behavior on integer over?ow.

Niestety, za tym idzie fakt, że nie mamy do wyboru z której arytmetyki chcielibyśmy dla danej zmiennej skorzystać (np. w Ada można wybrać między rozwiązaniami modulo a constraints).
Oczywiście, w C można sobie porobić funkcje do operacji ze saturacją, a w C++ można to nawet opakować w klasę z przeciążanymi operatorami (co niesamowicie zwiększa wygodę)... i to sprowadza nas do kolejnego problemu: o ile w assembly x86 wiemy czy nastąpił int OF/UF (patrz flagi OF i CF o których wspomniałem wcześniej), o tyle w C/C++ nie mamy jak tego sprawdzić (flagi nie są propagowane poziom wyżej). Ten problem rozwiązuje się na dwa (nieładne) sposoby:

1. Funkcje implementuje się w assembly (dzięki czemu jest to szybkie... i zupełnie nieprzenośne).
2. Stosuje się drobne heurystyki które mają sprawdzić czy overflow nastąpi/nastąpił (np. w operator++ można sprawdzić czy int jest MAX_INT, jeśli tak, to po ++ będzie overflow; ofc to się komplikuje np. dla mnożenia).

Czyli rozwiązania są, ale nie do końca są zgodne z zasadą KISS - powstaje więc pytanie: czy C/C++ naprawdę w pełni wspiera typy całkowite? Chyba nie, skoro żeby stwierdzić czy wystąpił edge-case trzeba się uciekać do hacków.

Oczywiście, inne języki tez nie są lepsze (chociaż np. wspomniane wcześniej Python i Ada wypadają nieźle pod tym względem).

I tutaj pytanie do czytelników - jak to wygląda w językach w których piszecie?

Na koniec tej części jeszcze link do jednego z poprzednich wpisów na moim blogu: Saturacja w scanf/atoi/strtol.

Two's complement (U2), czyli jedna wartość powodująca dwa problemy


Ostatnio doszedłem do wniosku, że kodowanie U2 (natywne dla intów na x86) ma jedną wadę (i wiele zalet; ale dzisiaj będzie o wadach). Mianowicie, fakt że liczb ujemnych jest o jedną więcej niż liczb dodatnich (np. -128 vs 127 dla char) sprawia, że powstały dwa błędogenne miejsca, czyli takie w których niedoświadczony programista może popełnić błąd, np. rzutujący na bezpieczeństwo (wspominałem zresztą o tym w mojej prelekcji na IGK oraz w poście o zmiennych).

Problem 1. Wartość bezwzględna


A propos wartości bezwzględnej na Wikipedii można przeczytać:

Z [...] definicji wynika, że wartość bezwzględna a jest zawsze liczbą nieujemną (dodatnią bądź zerem).
Tak więc programista pisząc np. abs(x) (gdzie x jest int'em) ma prawo się spodziewać, że wynikiem będzie liczba nieujemna.

Niestety, w kodowaniu U2 "that's not the case". Rozpatrzmy następujący przypadek:

int x = INT_MIN; // x = 0x80000000 = -2147483648
x = abs(x);      // x = 0x80000000 = -2147483648 (sic!)

Czyli wartość bezwzględna z -2147483648 wynosi nadal -2147483648, czyli nadal jest liczbą ujemną.

Wynika to z prostego faktu: operacja zmiany znaku x = -x realizowana w U2 jest jako x = (~x) + 1;, czyli w tym konkretnym przypadku:

int x = 0x80000000;
x = -x;
→ x = -0x80000000;
→ x = (~0x80000000) + 1;
→ x = 0x7fffffff +1;
x = 0x80000000;

Oczywiście, nie jest to wina funkcji abs(). Napisanie "ręcznie" wartości bezwzględnej np. jako x < 0 ? -x : x również jest podatne na ten błąd.

I teraz, jako ćwiczenie, poszukajcie błędu w popularnym kawałku kodu w dekoderach formatu BMP, formatu w którym wysokość bitmapy może być ujemna, co oznacza, że bitmapa jest zapisana od góry do dołu (normalnie jest od dołu do góry for some reason):
if(info_header.height < 0) {
 info_header.height = -info_header.height;
 top_bottom = true;
}

// sanity checks
if(info_header.width >= 4096 || info_header.height >= 4096)
 return false; // ignore malformed super-big bitmaps

// bitmap size is sane from this point, we can trust it
[...]

Zalecenie: Po abs() sprawdzaj czy wartość jest nadal ujemna; jeśli tak, odrzuć dane.

Problem 2. Dzielenie


Jednym z pierwszych programów które piszą początkujący programiści (np. na studiach w ramach ćwiczeń z programowania), jest tzw "kalkulator", czyli program który pobiera dwie liczby i operację od usera, a następnie wykonuje tą operację i zwraca wynik.

Przy oddawaniu takiego programu pierwszą rzeczą którą sprawdzają laboranci jest ofc przypadek 10 0 / (czyli podziel 10 przez 0). Oczywiście, brak odpowiedniego if'a przed dzieleniem spowoduje rzucenie wyjątku (#DE aka Division Error w terminologii x86).

Natomiast, jak się okazuje, jest jeszcze jeden przypadek w którym taki "kalkulator" rzuci #DE, mianowicie: -2147483648 -1 /. Wynikiem tej operacji powinna być wartość 2147483648, ale niestety, INT_MAX wynosi 2147483647, więc wartości 2147483648 nie można zapisać w 32-bitowym inc'ie. Ponieważ wynik dzielenia musi być prawidłowy (a w tym wypadku nie może być), to rzucany jest wyjątek.

No i powstaje pytanie - w ilu innych aplikacjach są takie "kalkulatory" z niesprawdzonym tym przypadkiem? (raczej w niedużej ilości, niemniej jednak niewątpliwie takie aplikacje istnieją).

Podsumowanie


Obu powyższych problemów możnaby uniknąć gdyby liczb ujemnych było dokładnie tyle samo co liczb dodatnich (tak jak jest np w kodowaniu U1 aka One's complement). Natomiast, w przypadku operacji na bitach, dużo wygodniej jest mieć liczbę zakodowaną w U2 (w którym dostaje się np. odejmowanie "gratis") niż walczyć z problemami typu "dwa zera" (0 i -0).
Tak więc wygląda na to, że trzeba o tych dwóch quirkach po prostu pamiętać.


I tyle na dzisiaj ;)

Comments:

2011-04-10 15:04:17 = MSM
{
Do wad `Więzów integralności` dodałbym jeszcze zdecydowanie sytuację w której spodziewamy się overflowa i jest jak najbardziej pożądany (np. z jakichś powodów robimy pętlę 32 razy mnożącą pewną zmienną przez 2.

Odpowiadając na pytanie `jak to wygląda w językach w których piszecie` - o oczywistych rzeczach nie ma co pisać, z ciekawszych rzeczy jakie mi przychodzą do głowy to konstrukcje checked/unchecked w C# - domyślnie jak w wielu językach można włączyć albo wyłączyć (bezpieczeństwo albo szybkość) `runtime-owe` sprawdzanie przepełnienia - czasami jednak wypada zaznaczyć że tutaj przepełnienie jest normalne/nie ma prawa wystąpić, niezależnie od domyślnych ustawień dla całego programu. całkiem wygodne.
O unchecked: http://msdn.microsoft.com/en-us/library/a569z7k8%28v=vs.71%29.aspx
}
2011-04-10 17:23:23 = mulander
{
> Mianowicie, fakt że liczb ujemnych jest o jedną więcej niż liczb dodatnich (np. -128 vs 127 dla char)

Z ciekawości zerknąłem do standardu Ada 95 (obecnie chyba najpopularniejszy pomimo rosnącego w popularności Ada 2005):

http://www.univ-orleans.fr/mapmo/systeme/Recup/systeme/logiciels/GRASP_Documentation/ada95lrm/rm9x-03-05-04.html

> Implementation Requirements
> (21)
> In an implementation, the range of Integer shall include the > range -2**15+1 .. +2**15-1.
> (22)
> If Long_Integer is predefined for an implementation, then > its range shall include the range -2**31+1 .. +2**31-1.

Zatem w przypadku Ada 95, przynajmniej na podstawie typów Integer oraz Long_Integer mamy pewność, że zakres liczb ujemnych dla typu jest taki sam jak dodatnich:

Integer - od -32767 do 32767
Long_Integer - od -2147483647L do 2147483647L
}
2011-04-10 19:58:32 = garbaty lamer
{
Ada? Pracujesz już dla US Army? Co będzie dalej? Delphi? Basic? ;-) Czytałem o renesansie COBOLa, ale żeby Ada?
}
2011-04-11 07:32:38 = Gynvael Coldwind
{
@MSM & mulander
Thx za komentarze ;>
Ciekawie to wygląda.

@garbaty lamer
BASIC już był, od BASICów różniastych zaczynałem zabawę ;)
COBOLa i Delphi nie planuje, ale who knows ;)
}
2011-04-11 10:15:39 = Reg
{
Pr0, dobry post! Oby więcej takich. To są rzeczy przydatne dla każdego programisty.
}
2011-04-12 00:42:26 = qyon
{
A tak robi php:
http://ideone.com/AXCbV
}
2011-04-15 15:30:26 = nobody
{
w Delphi taki kawałek kodu się nie skompiluje: błąd w lini podstawienia do x

var
x:integer;
begin
x:=-2147483648;
end;

ale funkcja Abs w Delphi jest również podatna na ten błąd

var
x:integer;
a:int64;
begin
x:=-2147483647;
dec(x);
a:=Abs(x);
ShowMessage(IntToStr(a))
end;

wyświetlony zostanie wynik z minusem
}
2011-04-15 15:56:42 = Gynvael Coldwind
{
@Reg
Thx ;)

@qyon
Ciekawe, thx ;)

@nobody
W C/C++ też są problemy z constem -2147483648, e.g.:
kod: int x = -2147483648;
c89: warning: this decimal constant is unsigned only in ISO C90
c99: OK
gnu99: OK
c++98: warning: this decimal constant is unsigned only in ISO C90
c++0x: warning: this decimal constant is unsigned only in ISO C90
gnu++0x: warning: this decimal constant is unsigned only in ISO C90
m.in. dlatego INT_MIN nie jest zdefiniowany bezpośrednio, tylko via odejmowanie i zmiana znaku:

#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX-1)

Ad abs w Delphi, mhm, thx ;)
}
2011-04-15 15:57:45 = mulander
{
Jeszcze raz Ada dla przykładu wartości absolutnej z Integer'First (plik test_abs.adb):


with Ada.Text_IO;


procedure Test_Abs is
I : Integer := Integer'First;
begin
Ada.Text_IO.Put_Line ( "Min = " & Integer'Image ( I ) );
Ada.Text_IO.Put_Line ( "Max = " & Integer'Image ( Integer'Last ) );
Ada.Text_IO.Put_Line ( "Abs(I) = " & Integer'Image ( abs(I) ) );
end Test_Abs;

Output z kompilacji:

mulander@bunkier_mysli:~/code/ada/gyn$ gnatmake test_abs.adb
gcc -c test_abs.adb
test_abs.adb:9:57: warning: value not in range of type "Standard.Integer"
test_abs.adb:9:57: warning: "Constraint_Error" will be raised at run time
gnatbind -x test_abs.ali
gnatlink test_abs.ali

I uruchomienie:

mulander@bunkier_mysli:~/code/ada/gyn$ ./test_abs
Min = -2147483648
Max = 2147483647

raised CONSTRAINT_ERROR : test_abs.adb:9 range check failed
}
2013-10-17 00:25:37 = SIRKOLPOL
{
W tym fragmencie:
"x = malloc(uint_from_user + 1); memcpy(x, data_from_user, uint_from_user);."
prosiłbym kogoś o objaśnienie czy dobrze rozumiem.
z czego wynika krasz programu po przepelnieniu inta? W moim przypadku crash nastapil podczas proby zapisu pod adres wskazany przez x. Jednak ja rozumuje w ten sposób:
1) Podajemy za dużą wartość, która przepełnia nam zmienną uint_from_user i daje tam jakieś bzdury.
2) Nie zależnie od tego co jest w uint_from_user to o ile jej wartość > data_from_user to wszystko będzie ok ? Sądze że tak, bo malloc zwróci nam poprawny adres .... chyba

Dobrze rozumuje??
}
2013-10-17 22:53:23 = Gynvael Coldwind
{
@SIRKOLPOL
Na współczesnych komputerach jest jak piszesz, tj. program się nie crashuje z uwagi na przepełnienie inta, a z uwagi na to memcpy które jest dalej.
Działa to tak (dla 32-bitowych maszyn), że dla uint_from_user == UINT_MAX (0xFFFFFFFF), wynik uint_from_user + 1 to 0, a więc zostaje zaalokowane 0 bajtów pamięci (czasami się około 16 bajtów zaalokuje i tak, np. pod Windowsem). Po tej alokacji następuje kopiowanie tych UINT_MAX, a skoro za mało pamięci zostało zaalokowane, to następuje crash.

Jeśli chodzi o to co napisałeś, to data_from_user jest nieistotne; istotne jest uint_from_user tutaj, ponieważ to ono mówi ile zaalokować (+1), oraz ile skopiować.
}

Add a comment:

Nick:
URL (optional):
Math captcha: 4 ∗ 6 + 5 =