татко Крокодил

Малко за гледаните лекции от 28c3 – ще бъдат в няколко post-а по ред причини.

Ще започна с една лекция, която описа в общи линии нов проблем в повечето web-facing езици/framework-ове в хеш реализациите, за който даже написах малко код.

Къде е проблемът – повечето такива езици (в случая – perl, php, python, java, ruby, asp.net) използват hash-ове (познати още като асоциативни масиви), за да подадат към програмиста параметрите, които са дошли от HTTP request-а (най-вече от POST-а). Почти всички го реализират, използвайки стандартни hash таблици с 32 или 64битов hash (не-криптографски, т.е. даже и CRC32 би свършил работа, повечето ползват нещо, писано от DJB, например DJBX33A).
По принцип insert-а на нов елемент в такава таблица е с ниска/константна сложност, но ако вмъкваме само елементи, които дават същия hash, сложността става максималната възможна, т.е. O(n) и съответно вмъкването на n елемента ще е от порядъка на O(n^2).
Накратко, ако подадем (например) през POST параметри, които се хешират към същата стойност, времето, което ще отнеме на езика/framwork-а да обработи заявката (преди да стигне до вашето приложение) ще е бая, като тестовете при мен показаха нещо от порядъка на 1 минута за заявка с 62000 параметъра и голяма около 400kb. В лекцията (има и запис, mirror-нат при мен) има повече подробности и тестове.

Реших да видя доколко мен ме лови тоя проблем. Като за начало трябваше да си напиша генератор на тия стрингове (ВНИМАНИЕ: грозен гаден код на C), което се оказа сравнително лесно – измъкнах от source на php от Zend/zend_hash.h тяхната функция, поразгледах кода и се оказа, че от hash функцията се взимат първите X бита, като X е в общи линии log2(N) (където N е броя елементи в стуктурата). Съответно ако ми трябват по-малко от 65536 collide-ващи стринга ми е достатъчно да търся колизии само в първите 16 бита. Моята некадърна програмка на машина със 192GB памет (трябваха и около 120GB) се справи за около 5 минути.
(пускам кода като пример, който може да го разбере би могъл да си го напише и сам сравнително лесно).

Имам да се поровя още малко, но в някои случаи debian-ската default-на конфигурация реже тия атаки (понеже не позволява повече от 1000 променливи в какъвто и да е request, което па от своя страна чупи малко (малоумен) софтуер), в някои не и повечето php-та, които човек може да намери по net-а ги лови тоя проблем. Реализирането на DoS-а за да направи реален проблем изисква прилично количество паралелни връзки и определено не е толкова опасно, колкото беше проблемът с Range request-ите от август, но пак не е приятно. Също така може да се атакува и през други места, например ако трябва да се сглоби json request или какъвто и да е hash, чиито ключове зависят от данни, подадени от потребителя.

Решението е да се random-изира hash-а на всяка заявка, за което си написах една тестова програмка, която да пробва в/у такива подбрани string-ове hash, който освен всичко XOR-ва всеки 8-байтов блок от входа с един random seed. Мисля ако скоро не изкарат някакво хубаво решение да си patch-на директно php-то, но още не съм имал време да намеря подходящия entry point, в който да вкарам инициализацията на seed-а, така че хем да е различен за всеки request, хем да не счупи нещо по много лош начин (ако някой е бърникал по кода на php и знае къде, много моля да пише).

Та, добри хора, прочетете оригиналното advisory и се patch-вайте, ако правите нещо свързано с web най-вероятно проблемът ви засяга.

И една отделна книжна равносметка за годината, понеже вероятно ще излезе по-голяма от предишната.
(всички книги по-долу и моите rewiew-та за тях може да се намерят в goodreads)

Една интересна тази година беше психиатрията. От нещата, които наистина ми харесаха ще спомена “The Psychopath Test” на Jon Ronson (наистина забавно четиво и много добре написана), “The Mask of Sanity” на Robert M. Cleckley (също хубаво четиво, но доста разпънато и може да доведе до странни сънища, например как си говорите с психопати), “Destroying the World to Save it: Aum Shinrikyo, Apocalyptic Violence, and the New Global Terrorism” на Robert Jay Lifton (който все още ми е от любимите автори, въпреки че “The Protean Self” беше много разочароваща), и “Inside the Criminal Mind” на Stanton E. Samenow (пак от книгите, дето влияят на съня).

По икономическата тема имаше няколко други интересни книги – “Liar’s Poker”, “The Big Short: Inside the Doomsday Machine” и “Boomerang: Travels in the New Third World” на Michael Lewis, който се оказа един наистина четим автор, който да опише кризата, последствията и причините (“Liar’s Poker” е писана преди 6-7 години с идеята да разкаже какво всъщност се случва на Wall Street и помага доста за разбиране на ситуацията). Внимание заслужава и “Currency Wars” на James Rickard.

От любимите ми автори имаше по една нова книга – “Reamde” на Нийл Стивънсън (трилър, много добър, но не може да настигне Cryptonomicon-а и Бароковия цикъл и всички са нещастни), “Snuff” на Тери Пратчет (много добра, но всички се надяваме да пише още книги), “12/22/63” на Стивън Кинг (пак много хубаво, въпреки елемента на пътуване във времето), “Diary” на Чък Паланюк (очаквах нещо повече), “Лудост” на Калин Терзийски (“Хората стават психиатри, за да си изписват сами халоперидол”), “Rule 34” на Чарли Строс (една от книгите, която четох с голямо удоволствие), “The Wise Man’s Fear” на Патрик Ротфус (ако и трета книга е толкова добра, спокойно може да го пишем за най-велик фентъзи автор) и “The Crippled God” на Стивън Ериксън (последната от “Малазанска книга на мъртвите”, не мисля, че има нужда да казвам повече).
Надявам се поне част от тях да се завърнат догодина с още нещо интересно (с изключение на Стивънсън, на който е ясно, че ще му трябват още 2-3 години за нова книга).

Имаше и разни неща, на които попаднах по разни други причини (препоръки, забелязани някъде и т.н.). Струва се да се отбележат:
“The Geeks Shall Inherit the Earth: Popularity, Quirk Theory and Why Outsiders Thrive After High School” на Alexandra Robbins – много интересни изследвания в/у училищата и груповата психология.
“1491: New Revelations of the Americas Before Columbus” на Charles C. Mann – много подробно разказани последните теории и открития за двете Америки преди пристигането на Колумб, чух я от едно интервю с Нийл Стивънсън (както и следващата, “1493…”) и определено си струва да се прочете.
“Rats Saw God” на Rob Thomas – рядко добра young adult книга, мен ме зариби заглавието.
Две книги на Atul Gawande – “Complications” и “Better” – хирург, пише много интересни неща за медицината и за как може да се подобри като цяло с мерки, приложими и в други области.
“Kingpin: How One Hacker Took Over the Billion-Dollar Cybercrime Underground” на Kevin Poulsen – много добре research-ната книга за хора, занимаващи се с credit card fraud и свързаните неща, попадна ми след като изчетох “Ghost in the Wiers” на Kevin Mitnick.
“The Organization Man” на William H. Whyte – може би една от най-добрите книги по темата за психологията на хората в корпорациите и проблемите там (мисля да я дам да я прочетат всичките ми познати, дето работят в големи фирми).
Отделно трябва да спомена Амели Нотомб, която пише кратки и все пак много добри книги. Успях да издъвча каквото намерих на български, скоро може да почна да търся и преводи на английски.

Препрочетох също така “То” (на Стивън Кинг), целия “Хари Потър” (Джоан Роулинг) и целите Хроники на Амбър (Роджър Зелазни). Има книги, които определено си струва да се четат пак и пак, да видим кои ще са в тоя списък догодина (може би пак Бароковия цикъл).

Най-препоръчаната от мен книга обаче за тая година е “Shooting an Elephant” на Джордж Оруел – събрани негови есета по различни теми, включително това за писането (което всички хора цитират), като цяло “стуктуро-определяща” книга. От там идва цитатът “During times of universal deceit, telling the truth becomes a revolutionary act”.
Втората също така силно препоръчвана книга е “Дзен и изкуството да поддържаш мотоциклет” на Робърт Пърсиг. Трудно ми е я да опиша, само ще отбележа, че ми помогна много да изясня някои мои идеи за преподаването.

И като препоръка за нещо по-скорошно и интересно – “Barefoot into Cyberspace: Adventures in search of techno-Utopia” на Becky Hogge, книгата може да се намери online и е доста добро описание на събитията в последните няколко години, свързани с wikileaks, copyright-а, internet и други такива забавни неща.

(но най-вече препоръчвам да четете. По-интересно е от почти всички филми (ок, според мен от всички, но пък не съм ги гледал всичките възможни, за да преценя), може да се чете по-бързо или по-бавно (с темпо, което ви харесва) и определено има много повече информация, отколкото в разните смлени бози, които може да се гледат)

И малко равносметка, преди да седнем да гледаме 28c3.

Като за начало, в началото на тая година съм забравил да напиша някакви планове. Замислям се какво съм правил и голяма част ми се губи, та ще се ползват външни памети.

Като за начало, станах на 30 и ми се размина стандартното проклятие да се оженя, да имам деца и т.н.. Е, не се е разминало съвсем, има още два-три месеца, но съм близо.

Отказах се да се занимавам повече с водене на курсове във ФМИ (като мрежовата сигурност). Направихме един хубав курс, записахме го по възможно най-добрия начин (няма пропуснати лекции) и на мен тотално ми писна от студентите (най-вече тези, които идват само за оценката), бюрокрацията и изобщо идиотията във факултета.
Понеже нямам намерение да се отказвам от идеята с преподаването, мисля да правя един не-курс по системна администрация, за който още си чакам хардуера.

Отказах се да се занимавам с OpenFest. Още не съм събрал желание да напиша защо в подробности (понеже основно псувни ми идват в главата), а и не е толкова важно, в крайна сметка хората могат да се справят и без мен. Може и да успея догодина да направя лекция там, вероятно ще имам време (за разлика от тая година).

Прочел съм горе-долу същия обем книги като миналата година (според статистиката в goodreads миналата година са 138 книги и 44388 страници, тая са 124 книги и 44122 страници), въпреки една голяма дупка в последните няколко месеца. Май рядко пиша в блога за това, което чета, трябва да се стегна и да пусна малко такива постове.

Започнах да ходя в initLab и да се забавлявам с всякакви странни неща там (тагнати са ми в блога).

Със свиренето напредвам бавно, но не особено мъчително. Взех си и китара (за която не съм блогвал), най-вече около слушането на Kyuss и от време на време сменям инструментите, но определено басът ми е по-приятен.

Прекарах месец-два в изпитване на програмисти за един проект и открих как около 90% от тези, които идват от обяви за работа за нищо не стават. Усещането беше сравнимо с това да изпитвам студенти (малко като вица за приликата между студента и кучето).

Като цяло – не умрях, не се ожених, не се пропих. Мога да броя 2011 за прилична година :)

Организираме прожектиране на лекциите от 28c3 в initLab, от 27ми до 30ти декември. Имаме предварителен списък какво мислим да гледаме и поне две стаи, в които да прожектираме (може да ползваме и третата).

(почти са ни одобрили регистрацията за гарантиран bandwidth, така че не трябва да има проблеми)

Нищо особено ново нямаше. Панаирът изглежда добре, имаше доста хора, може би малко по-малко издателства от миналата година.

Взех си 5 книги:
“Минало несвършващо”, съставител Евгения Иванова (исторически публикации);
“Лицето на водата”, Робърт Силвърбърг (фантастика);
“Министерство на болката”, Дубравка Угрешич (втора нейна книга, първата, която си взех нещо не ми хареса, да видим);
“Пространства на другостта”, издадена от БАН по темата за етносите и религиите в България;
“Окупаторът съюзник”, Бисер Петров (за колаборационизма в Албания, Сърбия и Гърция по време на втората световна).

В общи линии е добро място за откриване на странни книги, които трудно се намират по нормалните книжарници (като тези от БАН или от военното издателство).

Работи до неделя до 22:00, ако някой още не е успял да иде.

Странен сезон е. Сутринта валя, два дни подред пия, едвам намирам време да си свърша работата (не щото е много, а щото нещата се припокриват и има чакане) и съм пил вечерта, че да блогна.

Всички вероятно са чували какво е fizzbuzz, но пак да го кажа, накратко – задачка да се отпечатат числата от 1 до 100, като ако числото се дели на 3, вместо него се печата “Fizz”, ако се дели на 5 вместо него се печата “Buzz”, а ако се дели на 15 вместо него се печата “FizzBuzz”.
(това се дава на интервюта да се види дали човека изобщо може да програмира)

Оригиналното решение, което всеки може да напише на листче (говорим само за C) изглежда така:

for (i=1;i< =100;i++) {
	if (i%3==0) printf("Fizz");
	if (i%5==0) printf("Buzz");
	if (i%3!=0 && i%5!=0) printf("%d",i);
	printf("\n");
}

(което е почти същото на повечето езици за програмиране)

Оптимизираният вариант, който ми хрумна изглеждаше по следния начин:

int i,p;
char *s[4]= {"%d\n", "Fizz\n", "Buzz\n", "FizzBuzz\n"};
int s3[3]={1,0,0},s5[5]={2,0,0,0,0};

for (i=1;i<=100;i++) {
	p= s3[i%3] | s5[i%5]; 
	printf(s[p],i);
}

(накратко си избира максимално бързо format string-а, като се прави индекса му от два бита – единия за дали се дели на 3, другия на 5, след което се вика printf() с него и аргумента, а ако във format string-а няма “%”, то вторият аргумент изобщо не се гледа)

Методът с lookup таблиците е известен от зората на програмирането и е един от най-хубавите примери за time-memory trade-off.

Това решение няма branch-ове (т.е. if() и компания) в основния си код, но пък разчита на printf(), който не е особено бърз. На пиенето на Титов му хрумна, че може да се направи масив от функции, които да правят различните неща, но па на мен идеята за call и ret не ми хареса особено, за това се замислих и открих, че в C всъщност има масив от label-и. Съответно, ето извратено и максимално бързо решение:

int i,p;
static void *pos[4]= {&&digit, &&fizz, &&buzz, &&fizzbuzz};
int s3[3]={1,0,0},s5[5]={2,0,0,0,0};
char buff[2048];
char dgts[16]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
int buffpos=0;

for (i=1;i<=100;i++) {
	p= s3[i%3] | s5[i%5]; 
	goto *pos[p];

fizz:
	memcpy(&buff[buffpos],"Fizz", 4);
	buffpos+=4;
	goto end;
buzz:
	memcpy(&buff[buffpos],"Buzz", 4);
	buffpos+=4;
	goto end;
fizzbuzz:
	memcpy(&buff[buffpos],"FizzBuzz", 8);
	buffpos+=8;
	goto end;
digit:
	buff[buffpos++]=dgts[i/16];
	buff[buffpos++]=dgts[i%16];
end:
	buff[buffpos++]='\n';
}
write(1,buff, buffpos);

(т.е. както в предния пример имаме масив от format string-ове, тук имаме масив от позиции, на които директно можем да скочим. Също така не викаме никакви външни функции (memcpy се inline-ва и е от едни по-бързи инструкции) и единствения branch, който имаме е за for() (който също може да се избегне с една lookup таблица и едни goto-та, ама това вече ще е гадно)

Човек, способен да напише подобен код на интервю вероятно трябва да го пратят в Карлуково.

Ако на някой му хрумне нещо по-забавно, да пише :)

Update: Оптимизация – да се изместят p3, p5 и dgts като глобални променливи, понеже ако са във функцията, компилатора ги прави на много mov-ове.

Днес на ИББ изскочи една интересна тема, за която май пак е време да пиша.
(темата беше провокирана от това клипче и най-вече от музикалните инструменти в него)

Преди около 3 години си взех бас. В началото бях адски зле, после много зле, сега може би стигнах до нивото на адски много зле (има кило записи някъде, мислех си да направя един текущ на нещата, които горе-долу докарвам, но звуковата ми карта за записи е в initLab в момента, а аз съм достатъчно пиян да пропускам струни и прагчета). Двете оправдания защо го направих са “криза на средната възраст” (не минава, щото май не съм стигнал дотам) или че съм си взел голям инструмент да компенсирам за други неща (това успява да мине пред незапознатите :) ).

Всъщност, основната причина да си го взема беше звукът. Китарата (въпреки, че имам и такава) си остава за мен някакъв лек, детски инструмент – близки, тънки струни, никакво задържане на тона (колкото и да е добра) и липса на усещането, което баса докарва – като го държиш, вибрацията на струните се усеща в тялото, като цяло обратната връзка е пряка и доста силна.
За това имам и колебания дали някой искам да си взема контрабас или upright bass, да видя какво е.

Също така музиката, писана да звучи добре на бас просто звучи по-добре и усещането от това най-накрая да успееш да я изсвириш е невероятно. Два страхотни примера са “Orion” и “Anesthesia” на Metallica (второто съм го слушал и като малък, но май чак сега успявам донякъде да разбера колко е красиво). Други примери могат да се намерят в Tool (“Schism”, който още не мога да свиря, “46&2”, от което докарвам части), или в много простите неща на Offspring, например “Gotta get away” или “Change the world”. А ако на някой му се прииска нещо по-злобно, може да пробва “Killing in the name of” на Rage against the machine.

Изобщо, правенето на нещо със собствените ти ръце, особено нещо толкова лесно усещаемо като музика е нещо, което всеки трябва да пробва поне веднъж. Не е задължително да кара хората да го слушат, може просто да му се радва.

Чета “Spy Files”, последния release от WikiLeaks и се чудя как да се чувствам.

В началото си мислех да напиша нещо по темата за това каква отговорност трябва да се носи при правенето на тези неща, продаването им (особено като се погледне офертата на Amesys за Либия) и прилагането им. Никак не вървеше, та се зачетох в документите по-подробно и попаднах на набор каталози на Elaman (които mirror-нах при мен, че са 124MB).

Четенето им е почти като да четеш ужаси. От една страна те хваща параноята, че тия неща може да ти ги приложат на теб, от друга страна обаче има такива невероятни играчки, че чак ти потичат лигите. Комплекти за отваряне на ключалки и сейфове, детектори за радиоизлъчване, лазер и инфрачервени лъчи, заглушители за същите, дребни ръчки осцилоскопи и спектрални анализатори, системи за гледане през стени (да се проследят кабели и т.н.), подслушващи системи за сателити, разпознаване на глас, кой говори, на какъв език говори и т.н., и т.н.. Ако вярвах в Дядо Коледа, щях да му пратя тоя каталог…
Не съм фен на разните генерални подслушващи неща, анализирането на трафика и връзките между хората и ги намирам за гадни, но останалото всъщност е … готино.

Пиша това, за да отбележа, че всъщност съм ужасен човек и такива като мен ще унищожим света. Забавлявайки се.

Обичам CaCert.

Хората си дават сертификати просто ако domain-а си е твой, работят съвсем правилно, има ги в достатъчно дистрибуции (може би ги няма в IE, ама това си остава проблем на хората, които го ползват). Тия дни подкарах сертификати на cassie, най-вече за базата данни, която правихме вчера на hackaton-а, днес слагам на marla за няколко vhost-а и може някой хубав ден да мина всичко само на https.

Всичко трябва да се криптира. Защо – вижте “Spy Files” в wikileaks.

Update: Понеже съм забравил да го напиша – тези сертификати са само за УДОБСТВО, да не свети на повечето хора на browser-ите, че има проблем (или поне на тези, които признават cacert). Напълно осъзнявам, че целия модел на сертификатите в момента не струва и не може да се разчита на него и ползвам cacert защото 1) са удобни за ползване (вместо сам да си правя CA) и 2) защото поне на ubuntu-вските browser-и това си работи (т.е. има го root-а им в ca-certificates пакета).

Важната част е SSL-а, който също си има своите много проблеми, но е поне някакъв вариант за сигурност и за криптиране, т.е. стъпка в някаква хубава посока.