Nezodpovězené otázky a jiné problémy

Látka probíraná v některých předmětech (Analýza hašovacích funkcí, Analýza programů a verifikace kódu, principy překladačů) ve mi někdy vnuká různé otázky, na které neznám odpověď, nebo témata, která by bylo zajímavé prozkoumat blíže (zvláště po praktické stránce). Aktuální seznam problémů vypadá takto:

• Pozadí: Existuje třída tzv. NP-úplných problémů. Tyto rozhodovací problémy jsou charakteristické tím, že pro ně neznáme deterministický polynomiální algoritmus, který je vyřeší (nedeterministikcy je to lehké). Asymptotická složitost se pohybuje v nehezých exponenciálních výšinách. Zajímavostí ovšem je, že NP-úplné problémy lze na sebe polynomiálními algoritmy převádět. Mezi takové problémy patří například SAT, hledání maximální kliky či nezávislé množiny v grafu či jeho barvení pro čtyři a více barev (aspoň doufám).

  Problém: Samozřejmě existují různé heuristiky, jak NP-úplné problémy řešit (například pro SAT to je DPLL). Nedávno jsem dospěl k myšlence, že když jsou tyto problémy na sebe převoditelné, tak by totéž mohlo platit o heuristikách. Dále si myslím, že je celkem pravděpodobné, že u každého NP-úplného problému známe jiné heuristiky - takové, které se při převodu problému na jiný zobrazí na heuristiky, které třeba ještě neznáme.

  Je to pravda?
  Zkusit s tím něco udělat, nějak otestovat

• Pozadí: Generování náhody mi přijde jako docela zajímavá oblast. Dostat opravdovou náhodu v našem determnistickém světě může být relativně obtížné, obzvláště pokud potřebujeme třeba čistě softwarové řešení. Von Neumann kdysi přišel s nápadem, že bychom si měli zadefinovat, co od náhody požadujeme, a podle toho sestrojit algoritmus na míru.

  Úkol: Porovnat některé náhodné generátory (čistě softwarové). Zatím připadají v úvahu tyto: Delphi generátor, Windows API, Cčko, generátory založené na nějaké kryptografické hašovací funkci (SHA-1, BMW), generátory založené na nějaké blokové šifře (AES, RC4) - to je obdoba předchozích. Pokusit se změřit různé statistické vlastnosti (střední hodnota, rozptyl, četnost N-tic bitů, rozdělení pravděpodobnosti, četnost různých N-tic bitů (pro N od 1 do nějakého rozumného čísla) atd. atd.).

• Pozadí: Antivirové programy při detekci virů často spoléhají na tzv. databázi signatur, kde jsou obsažené jedinečné bytové řetězce, které se vyskytují v souborech různých rodin škodlivé havěti. Tvůrci malware se proti této technice mohou bránit například polymorfním (generování mnoha souborů viru, které dělají to samé, ale jejich obsah je odlišný) či metamorfním (kód viru se dynamicky mění za běhu, takže nikdy nezůstane dlouho v určité podobě) kódem. Při takové činnosti mohou (aspoň si to myslím) využít i teorii formálních jazyků (automatů a gramatik).

  Úkol: Vytvořit gramatiku (min. bezkontextovou s množstvím nedeterministických pravidel) pro generování polymorfních věciček a napsat k tomu program, který bude z kódu na vstupu generovat kód ekvivalentního významu, leč jinak vypadající.

• Úkol: Pohrát si s kryptografickou hašovací funkcí Blue Midnight Wish (tady pozadí není potřeba). Zvláště s funkcí F0, která při jistém nahlédnutí vypadá až podivně jednoduše.