Блог об IT бизнесе

Эники Беники ели вареники
Эники Бэники клёц!
Вышел зеленый матрос.

Знакомо?

Пока я крапаю длинную статью на тему как научиться НЕ делать все самому, решил набросать коротенькую статейку/задачку. Задачка аналогично такой, которая дается на олимпиадах по программированию.

Слегка формализированные правила считалочки.

1) Пусть у нас есть N человек

2) И у нас есть считалка длинной в M слов.

3) Начинаем считать с первого человека, по одному слову на человека.

4) Человек на котором считалка закончилась выбывает.

5) Считалка продолжает считаться с следующего после выбывшего, повторяя пункт 4 и 5.

6) Оставшийся последним человек – выигрывает.

Задача:

Написать программу, которая считает порядковый номер человека который выигрывает. Входные данные N и M.

5 баллов – программа может рассчитать выигрывающего при N и M < 20.

10 баллов – программа может рассчитать при N < 20, а M порядка 1 триллиона (не фига себе считалочка), за разумное время.

25 баллов – программа может рассчитать при N порядка 1 миллиарда, M < 20, за разумное время.

50 баллов – программа может рассчитать при N и M порядка триллиона.

Если вы знаете/придумали решение на 50 баллов, прошу сразу его не бросать в комментарии, а просто написать что вы его знаете (чтобы дать остальным подумать).

Остальные решения вполне welcome в комментариях

Увы, приза по рукой нет, да и как я его доставлю в произвольную точку земли тоже непонятно. Но, всем решившим большое уважение и почет.

P.S.  Как оказалось, задача классическая (просто я с ней не сталкивался). На момент написания статьи, я знал решение на 5 и 10 баллов, примерно имел идею на 25 баллов и не знал, как решить на 50 баллов.

Как и подобает каждому приличному секуритяну, я задумываюсь иногда о большом, белом и добром – об абсолютной защите от уязвимостей. То есть, какая должна быть система, чтобы с математической точки зрения к ней нельзя было сделать exploit’ы. Сразу оговорюсь, мы говорим именно о технической стороне, а не о social engineering’е, когда человек сам отдает ключи от квартиры, где лежат деньги.

А кстати, навеяло это мне то, что блог взломали и поместили невидимые линки на какой-то сайт с рекламой всякого хлама. Забавно, что жил на старинном WordPress 2.3 больше года и не был взломан. Стоило перейти на распоследний 2.8.5 c Security updat’ами и не прошло и недели, как взломали. Но, это, так… к делу не относится.

Так вот. в своих раздумьях по поводу абсолютной защиты, все что я смог придумать это – полное разделение кода и данных. То есть не должно быть ни одного места, где они перемешаны. Один из самых распространенных видов уязвимостей – переполнение буфера как раз основан на том, что сначала путем переполнения мы гадим в стек и вызываем переход на тот адрес, который мы хотим, например на другой загаженный кусок. Соответственно, если адресация команд отделена от адресации данных, то данные никак не будут исполнены как команды.

Вероятнее всего, имеет смысл даже более жестко вводить разделение. Вообще, управление программой не должно быть возможно с помощью “сырых” данных. То есть, все методы условного и безусловного ветвления могут работают только на основе того, что храниться в флагах или коде. А уж только флаги в свою очередь могут быть выставлены какими-то операциями с обычными данными.

Так, что – долой архитектура фон Неймана и да здравствует архитектура Ронина (м… нужно какой-нибудь титул раздобыть).

Вторая идея, фактически продолжение первой – запрет всех интерпретируемых языков. Долой всякий SQL-injection. Увы, пока я не смог придумать, как с технической стороны можно ограничить возможность интерпретирования.

Увы, пока на этом мысль останавливаются.

Есть у кого-нибудь еще идеи и предложения по этому поводу?

P.S.1. Основная идея, не какой-то метод написания кода, который будет более стабильный, а система в которой потенциально нельзя написать код позволяющий сделать exploit. Понятно, что против SQL injection и buffer overflaw есть вполне четко описанные практики борьбы, весь вопрос, что программист должен об этом думать и может забыть/не знать и поэтому везде и есть куча дыр.

P.S.2. Отличная идея от Alex UK. Конечная state machine действительно хорошо справляется с поставленной задачей.