Неявни предикати
И така, измислихте супер алгоритъм за обфускация на програмния код. При декомпилиране кодът изглежда просто скандално и никой няма да го анализира със сигурност. Изглеждаше като победа! Но не. Естествено обфусцираният код няма да бъде анализиран от никого ... на ръка. Хакерът ще разбере как сте оплели кода и ще напише "unraveler". Ако вашият алгоритъм е достатъчно силен, тогава хакерът ще трябва да напише свой собствен емулатор, но това не е такъв проблем, както може да изглежда на пръв поглед - има емулатори, налични в мрежата и дори специално написани специално за хакерски цели.
От теорията на компютърните науки е известно, че няма и никога няма да има алгоритъм, който определя дали програмата ще спре или ще работи завинаги - така нареченият "проблем със спирането". Това гарантира, че емулаторът на хакер, разкриващ обфусцирана програма, ще го направи като че ли „локално“: той няма да може да знае състоянието и стойността на всички променливи, включени във всеки раздел на кода, и следователно, в условни точки на разклоняване, често ще приема, че всички варианти на програмата са възможни. Това е мястото, където решението идва на ум: объркващият код ще бъде изпълнен с условни изрази, които винаги ще бъдат верни, но ще бъде трудно да се емулира и разбере това. Приблизително така:
„Но това е само едно от онези обърквания, които хакерът ще заобиколи с помощта на емулатор“, ще кажете и ще сте прави. И каквоако измислите хиляди такива трикове? О, това е решение, ако имате легион от програмисти, всеки от които измисля трикове, които не са като триковете на другите. В действителност това не е така. В действителност вие мислите една седмица и измисляте тридесет трика, а един хакер разглежда кода един ден и намира всичките тридесет трика, защото тридесет не са толкова много.
Идеалният имплицитен генератор на предикати
Нека формулираме как трябва да изглежда един вид идеален супер генератор на неявни предикати. Той създава предикати P(x1,x2,…,xn) в зависимост от променливите x1,x2,…,xn и може да създава както идентично верни, така и не винаги верни предикати, в зависимост от желанието на потребителя на генератора. И генераторът има следните фантастични характеристики:
- предикатът се генерира в линейно време от дължината;
- предикатът е много подобен на нормално състояние от нормална програма (стелт);
- няма и не може да съществува (!) алгоритъм, който да определи, че предикатът е генериран от нашия генератор;
- не съществува и не може да съществува (!) алгоритъм, който по генерирания предикат винаги да определя дали той е верен или има входни параметри, на които той е неверен;
- няма вероятностен алгоритъм, който да определи правилно, средно, поне в 80% от случаите (цифрата е намерена чрез научно проучване), дали предикатът, създаден от генератора, е идентично верен.
Точка 4 изглежда възможна. Нека ви напомня, че диофантовото уравнение е уравнение от вида f(x1, x2, …, xn) = 0, където f е полином с цели коефициенти, а x са неотрицателни цели числа. Обръщайки се отново към теорията на компютърните науки, припомняме тованяма и не може да има алгоритъм, който да определи дали диофантово уравнение има решение или не. По-специално, според последната теорема на Ферма, диофантовото уравнение (x+1)*(x+1)*(x+1) + (y+1)*(y+1)*(y+1) - (z+1)*(z+1)*(z+1) = 0 няма решения. Изглеждаше: точно там трябва да копаете! Но не бързайте. Диофантовото уравнение изобщо не е набор от суми и произведения на числа със стойности от 0 до 4 милиарда, а набор от суми и произведения на цели числа със стойности от 0 до безкрайност. Ще трябва да ги напишете с помощта на така наречената "дълга аритметика" и те ще изглеждат много странно в кода.
Точка 2 пречи на всички. Ние наричаме интуитивно потаен предикат, който не се откроява в тълпата от реални, „неимплицитни“ предикати от реални програми. Умните хора вече са анализирали много типични приложения и са открили, че повечето от предикатите в тях са съвсем прости: x == 0, x == y, x > 0 и т.н., където x, y са int променливи (във втората от горните статии умните хора просто небрежно анализират условията на типичните java програми). Не отнема много време да се досетим, че условието за стелт е много важно за предикатите. Наистина, един хакер може просто да намери всички „странни“ предикати и по някакъв начин да ги изолира или да ги премахне напълно, което изобщо не ни трябва.
Елемент 4 не е възможен поради елемент 2... въпреки че. Така че, ако предикатът е аритметичен и е „скрит“, тогава той най-вероятно включва само аритметика с int, което означава, че има алгоритъм, който ще провери дали предикатът винаги е верен: достатъчно е просто да се изброят всички стойности на int-овете, включени в предиката. Но това не е лошо, защото в най-добрия случай, за да анализирате предиката, ще трябва да преминете през 4 милиарда стойности! И ако има две променливи в предиката? Така че ние с чиста съвест,приемайки P тагове:
- замъгляване
- обфускатор
- замъгляване
- контролен поток
- математика
Hardcore conf в C++. Каним само професионалисти.