Hlavní navigace

Bezpečné programování v C++ II

18. 3. 2009 0:59 (aktualizováno) inkvizitor

V dnešním díle bych chtěl blíže pohovořit o tom, proč považuji používání naší funkce filter() za bezpečné a rozebrat ji z pohledu jednoho z kritérií správnosti kódu. Předpokládejme, že tzv. Murphyho zákony platí a tudíž není obecně možné projít zdrojový kód celé aplikace, dokonale mu porozumět ve všech souvislostech a odhalit všechny potenciální chyby. Pokud tedy za takovýchto podmínek chceme provádět audit kódu, ať už pomocí „zkušeného oka“ nebo pomocí nějakého nástroje pro statickou analýzu, musíme si stanovit kritéria správnosti.

Správný kód

1. Dělá všechno, co dělat má a přesně tak, jak má. Například kalkulačka umí správně sčítat, odčítat, násobit a dělit.

2. Nedělá nic, co dělat nemá

Zatímco ke zhodnocení správnosti provádění výpočtu slouží různé metody testování, otestování toho, že program za žádných okolnosttí nedělá, co nemá, není snadné. Příkladem může být například „trojský kůň“, který za normálních okolností funguje jako kalkulačka, ale 29. února ve 13:00 zaplní celý disk, sežere celý výpočetní výkon procesoru nebo pošle obsah souborů /etc/passwd a /etc/shadow na nějaký FTP server.

Příklady nežádoucího chování programu mohou být:

1. Program zapisuje, kam nemá (disk, paměť, TCP/IP…)

2. Program zneužívá nějaký známý exploit a získává přístup na úrovni uživatele root

3. Výpočet se dostane do nekonečného cyklu

4. Program za nějakých okolností vyvolá výjimku

5. Výpočet trvá v některých případech neúnosně dlouho

Jak si poradit s hrozbou nekonečného cyklu

V tomto díle bych se chtěl zaměřit na tzv. halting problem (česky problém zastavení), což je statická analýza programového kódu, která má rozhodnout, zda se celý program nebo jeho část (procedura nebo funkce) někdy zastaví. Alan Turing už v roce 1936 dokázal, že obecný algoritmus, který toto umí pro každý program, nelze sestrojit.

Rozhodně ale lze sestavit algoritmus, který toto dokáže rozhodnout pro některé programy. Existují operace, o kterých víme (resp. předpokládáme na základě znalosti výstupu kompilátoru nebo funkce interpretu), že skončí. Např. sčítání dvou celých čísel. Následující kód zcela jistě skončí a není nutné to dále dokazovat:

int i = 1;
int j = 2;
i = j + i;

Pokud si vystačíme s takovýmto jednoduchým programem, není co řešit. Pokud ale potřebujeme rozhodnout o zastavení výpočtu obecné procedury nebo funkce, dostáváme se zpátky k algoritmicky neřešitelnému problému. Pokud si nepomůžeme jinak. Problém představují cykly (které obecně nemusí skončit nikdy) a rekurze (které skončí až tenkrát, když vyčerpají prostředky programu přidělené, typicky maximální velikost zásobníku). Problém je, že bez cyklů nebo rekurzí se ve složitějších programech těžko obejdeme, ale cykly používat nesmíme, protože jinak nedokážeme obecně zjistit, zda se program zastaví.

Funkce typu filter() tento náš problém řeší. U těchto funkcí dokážeme relativně snadno rozhodnout, za jakých okolností se jejich výpočet zastaví. Šabloně funkce filter() prohlédneme a vystavíme certifikát, který prohlásí, za jakých okolností se funkce zastaví. A statický analyzátor na základě takového certifikátu snadno zjistí, zda se volání takové funkce někdy zastaví. Představme si následující kód:

HALTS("halts(func)")
template<typename T>
list<T> filter(const list<T> &originalList, bool (* func)(const T &))
{
    list<T> newList;
    typename list<T>::const_iterator it;

    for (it = originalList.begin(); it != originalList.end(); it++)
    {
        if (func(*it))
            newList.push_back(*it);
    }

    return newList;

}

Naše stará dobrá šablona funkce filter() dostala certifikát, který říká, že se výpočet zastaví v případě, že se zastaví callback funkce, kterou do funkce filter() posíláme jako parametr. Pokud tedy analyzátor dokáže analyzovat volání funkce s takovýmto certifikátem a dokáže ověřit, zda se funkce func zastaví, dokáže také určit, zda se zastaví kterékoliv konkrétní volání funkce filter().

Naše volání v minulém díle vypadalo následovně:

filter(l, isEven)

takže zbývá analyzovat funkci isEven(), která vypadala takto:

bool isEven(const int &i)
{
    return ((i % 2) == 0);
}

Jak je vidět, funkce provádí triviální operaci modulo, porovnání dvou celých čísel a vrací výsledek tohoto porovnání. S takovou funkcí si i velmi primitivní statický analyzátor poradí. Pokud analyzátor nezná zdrojový kód funkce isEven(), například proto, že je umístěna v nějaké knihovně, můžeme mu opět napovědět:

HALTS("true")
extern bool isEven(const int &i);

Statický analyzátor rozumí deklaraci certifikátu, takže teď zbývá pouze vytvořit makro, které zařídí, že takovýto certifikát bude kompilátor jazyka C++ ignorovat. Makro může vypadat následovně:

#define HALTS(x)

Používání funkce filter() je bezpečný programátorský idiom, který zajistí, že program nebude dělat, co nemá (minimálně z hlediska hrozby nekonečného zacyklení). O této funkci můžeme ale prohlásit i to, že nezapisuje nikam jinam, než do svých lokálních proměnných, nezneužívá žádný exploit, nemá tendenci k vyvolání výjimky (v úvahu připadá vyčerpání volné paměti) a dobu výpočtu lze předvídat, protože je funkcí délky seznamu a výpočetní náročnosti callback funkce. Podobným způsobem, jakým jsme udělili certifikát garance zastavení výpočtu funkce, můžeme vydat certifikát paměťové náročnosti, výpočetní složitosti, absence vedlejších efektů funkce (tedy že funkce nezapisuje, kam nemá) atd. Důsledné používání podobných idiomů nám zajistí velmi dobrou předvidatelnost chování programu, která je srovnatelná s kódem ve funkcionálních jazycích a nesrovnatelně lepší, než je předvídatelnost obecného programu v C# nebo v Javě, tedy jazycích, které pan LO stavěl na vyšší úroveň než C++.