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).

By the way...
On 22nd Nov'24 we're running a webinar called "CVEs of SSH" – it's free, but requires sign up: https://hexarcana.ch/workshops/cves-of-ssh (Dan from HexArcana is the speaker).

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 ;)