dxdt.blog: занимательный интернет-журнал

Появился новый робот, быстро собирающий кубик Рубика – он справляется примерно за секунду (по ссылке с картинки – видео на Youtube.com):

Конкретно это решение можно, конечно, покритиковать: там четыре камеры; нужен специально подготовленный кубик (насадки на валах электродвигателей входят в механическое зацепление с центральными элементами сторон кубика); кубик устанавливается в заранее заданном положении (манипуляторы размечены по цветам) и так далее, и тому подобное. Однако интереснее подумать, насколько вообще можно улучшить результат. Вычислительные мощности доступны, поэтому механическая составляющая робота оказывается важным фактором, устанавливающим границы.

Если я не путаю, то сейчас известно, что из любой конфигурации кубик (3×3) собирается не более, чем за 26 ходов, если ходом называется поворот грани на 90 градусов. При этом большинство конфигураций лежат на два-три хода ближе к собранному кубику. Для оценки точное число ходов не так важно. Примем, что типичная сложная конфигурация – 25 ходов. То есть, если поворачивать грань за 10 миллисекунд на 90 градусов, то с преобразованиями конфигурации можно уложиться в 250 мс (плюс затраты на “переключение” граней – но не будем их учитывать). 10 мс – это 9000 градусов или 25 оборотов в секунду. Сама по себе, скорость вращения не очень большая, добротный кубик её наверняка выдержит. Заметные потери времени при “миллисекундном разрешении” будут связаны с разгоном грани – отсюда и идеи с механическим зацеплением. Для немодифицированного кубика быстрый разгон при начале вращения грани составит серьёзную техническую проблему.

Работа робота сводится к определению начальной конфигурации кубика, вычислению оптимального (или близкого к оптимальному) пути из этой конфигурации к собранному кубику, выполнению ходов. Интересно, что оптимальный путь здесь не обязательно кратчайший. Дело в том, что оптимизировать нужно с учётом исполнительного механизма, а он может какие-то ходы выполнять быстрее, а какие-то – медленнее. Например, очевидно, что все повороты должны осуществляться в одну сторону, что некоторые ходы поддаются механическому “распараллеливанию”, а некоторые – нет, и так далее. Изображение кубика требуется получить только один раз, для определения начальной позиции. Причём это изображение может быть низкого разрешения и известной геометрии, так что сколь-нибудь заметного времени на передачу и распознавание не потребуется. Основное вычислительное время – поиск оптимального пути сборки. После того, как получен список ходов – он отправляется в контроллер механизма, который максимально быстро выполняет их, передавая команды исполнительным механизмам. Логично использовать простейший контроллер, а максимум вычислений проводить на управляющем компьютере: результатом работы программы будет являться набор команд на поворот валов электродвигателей, который и передаётся в контроллер (алгоритм выполнения команд должен учитывать параллельное выполнение, так что контроллеру потребуется память и логика, позволяющая одновременно управлять несколькими двигателями).

В общем, тема эта весьма интересная, а особенное техническое развитие она получает после преодоления секундного барьера. (Человеческий рекорд, кстати, чуть менее 5 секунд.)

Как известно, “любая достаточно продвинутая технология неотличима от магии”. При этом “степень продвинутости” – оценочная величина, зависящая от системы отсчёта. Поэтому и порог достижения статуса магии – он разный для разных наблюдателей. Даже не для наблюдателей, а для пользователей.

Именно поэтому некоторые пользователи удивляются, как это содержание их сообщений электронной почты стало известно кому-то ещё. Нет, они вовсе не исключают, что кто-то, кроме получателя, может прочитать письмо. Но само понимание этого процесса чтения как раз сводится к степени вовлечения в магическую часть технологии. Так, пользователь уверен, что раз в момент написания письма никто не стоял у него за спиной, заглядывая на экран через плечо, то и содержание письма остаётся тайным. Понимание того, что есть некий “почтовый сервер”, где письмо присутствует в открытом виде – это следующий уровень, далеко не всем доступный, как ни странно.

Опытный пользователь знает о почтовом сервере. И догадывается, что его письмо может прочитать администрация сервера. Однако в администрации он уверен (что читать она не станет) и поэтому полагает переписку секретной, смело доверяя ей весьма скользкие моменты.

Но тут пользователя настигает следующий уровень – опять магия: электронные письма передаются по сетям связи, нередко – в открытом виде, поэтому читать их может и третья сторона, а не только “администрация сервера”. Понимание этого аспекта – уже прерогатива не обычного пользователя, а специалиста. Но магом данный понимающий специалист тоже не является.

Дело в том, что пока упомянутый специалист утверждает, что почта нынче ходит между продвинутыми серверами в зашифрованном виде, через TLS и прочие заклинания, настоящие техномаги (80 lvl) “кастуют” подмену DNS и заменяют интересующие их почтовые серверы на свои прокси. Эти прокси отменяют TLS (почтовые протоколы позволяют) и – хлоп! – опять читают “секретную” переписку пользователя, что грозит последнему проблемами, хоть он этого и не понимает.

Вывод и мораль: не используйте математических методов, если вы не понимаете их сути (из известного анекдота про математиков и физиков). Да. Лучше уж подсуньте записку под дверь.

Кстати, про фотографии. Нередко приходится видеть, как на фотографиях сетевого оборудования замазывают имена серверов и названия портов/линий. В принципе, это полезная практика: потому что также приходилось наблюдать и скандалы, когда на фотографиях из некоторого дата-центра, опубликованных в СМИ, специалисты узнали оборудование, которого в этом дата-центре (как бы) не должно было находиться. Так вот, на сайте ЦРУ есть статья, повествующая об одном рабочем эпизоде аналитика стратегической разведки, занимавшегося, в конце 50-х годов прошлого века, реконструкцией параметров советской электрической энергосистемы на Урале (некоторый перевод удалось найти готовый, но лучше, конечно, читать оригинал; зато страница с переводом очень дополняет оригинал важными картинками в высоком разрешении).

Если в двух словах, то история вертится вокруг фотографии, опубликованной в журнале “Огонёк” 1958 года. На этой фотографии запечатлена центральная диспетчерская “Уралэнерго”, находившаяся в Свердловске. Используя схему системы энергоснабжения, которая составляет основное содержание фотографии, аналитику ЦРУ Чарльзу В. Ривзу удалось составить план энергосистемы, на основе которого, используя теорию электросетей, он смог вычислить потребляемую мощность советских секретных атомных объектов, находившихся на Урале, а также подтвердить, что некоторые объекты – являются атомными. Ради этого, собственно, всё и затевалось. Фотография в “Огоньке”, конечно, была отретуширована перед печатью: на ней, как пишут, закрасили все названия и шкалы (или “индикаторы”) приборов. Зацепкой послужил состав схемы: обозначения, соответствовавшие генераторам, позволили сопоставить их с электростанциями – так как информация о числе генераторов на некоторых из них была известна из других источников. Новые станции, а также станции, о которых было мало информации (неизвестно число генераторов), оказалось возможным сопоставить со схемой методом исключения, анализируя взаимные подключения, на фотографии и на разведывательных аэрофотоснимках.

Занятно, что фотография из “Огонька” обозначена в статье как ключ, позволивший сопоставить имевшиеся данные и получить итоговую техническую схему энергосистемы (с указанием мощностей и прочих параметров). Схема, как пишут, являлась секретной. Правда, остаются вопросы. Раз схема энергосистемы являлась секретной, то для чего в “Огоньке” опубликовали фотографию пульта управления этой энергосистемой (пусть и отретушированную)? Понятно, что фотографии с режимного объекта, где присутствует секретная схема во всю стену – во всесоюзном журнале, отправляемом, фактически, прямо в ЦРУ, появиться не могли: фотокорреспондента просто не пустили бы на объект. То есть, настенная схема в диспетчерской, вероятно, всё же не считалась секретной. Либо её решили рассекретить. Возможен, конечно, и вариант, что специалист, просматривавший материал на предмет ретуширования, с одной стороны, не понимал, как работает служба стратегической разведки, а с другой – как работает энергосистема, поэтому оставил ключевые элементы нетронутыми.

Как можно было бы предотвратить утечку, опубликовав, вместе с тем, рискованную фотографию? Например, дорисовать примерно треть дополнительных обозначений, которых нет там в реальности. Попутно удалив примерно одну пятую обозначений подлинных. Но, конечно, дорисовка испортит документальную ценность фотографии, поэтому можно было бы ограничиться вырезанием больших кусков схемы и удалением изображений линий электропередач.

Кстати, в статье сообщается разумная вещь: выход продукта “атомного объекта” (например, оружейного плутония) коррелирует с потребляемой предприятием электрической мощностью. Но дело в том, что о таком побочном канале всем хорошо известно, поэтому вовсе не факт, что подводимая мощность соответствует мощности, потребляемой агрегатами и установками, занятыми в производстве. Методы и требования по маскировке информации в подобных каналах утечки никто не отменял: например, азы технической защиты информации – маскировка различных производственных отходов; это особенно касается атомной и химической промышленности. Впрочем, на сайте ЦРУ пишут, что выводы аналитика о схеме энергосистемы очень хорошо совпали с подоспевшими результатами аэрофотосъёмки U-2 – так что “Огонёк”, получается, помог, предоставив разведке дополнительный источник информации.

Вот.

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

В продолжение заметки про лазерную турель, перехватывающую подлетающие снаряды. Чисто “кинетическая” турель стреляет не лазером, а своим снарядом, который должен угодить прямо в снаряд подлетающий. Попасть снарядом в снаряд сложнее, чем лазером, но возможно. При столкновении на встречных курсах – мгновенный гарантированный результат: сумма скоростей будет такой, что оба снаряда разрушатся. Даже если перехватчик мал, относительно перехватываемого снаряда, например, составляет лишь десять процентов его массы, попадание всё равно приводит к разрушению цели.

В прошлом примере, про лазер, перехватываемый снаряд летит со скоростью 1300 м/сек (что является заведомо завышенным показателем – обычно скорость раза в два-три меньше). Путь, на котором требуется перехватить снаряд, – 900 метров: предполагаем, что снаряд обнаружен на расстоянии в километр, а если он не перехвачен до рубежа 100 метров от прикрываемого объекта, то перехвата, считаем, не состоялось (таковы условия задачи). Выходит, на всё про всё у перехватывающего комплекса 750 мс. Это как минимум.

Основной проблемой для кинетического перехватчика становится подлётное время до снаряда. Лазер тут действует мгновенно, а вот стальной болванке ещё нужно лететь. Пусть у нас столь же сверхмощная фантастическая пушка, как и у атакующих, поэтому снаряд на перехват вылетает со скоростью 1300 м/сек. Тогда, если пренебречь падением скорости, 100 метров он преодолеет за 76 мс. В реальности, конечно, несколько медленнее. Это означает, что нижний предел запаса времени на полёт перехватчика – примерно 100 мс. Осталось 650 мс. В предыдущем упражнении, на поворот лазерной турели мы отводили 300 мс. Это показатель, отражающий предел сверху: действительно, за 0,3 сек. можно повернуть на 180 градусов даже массивную турель, если заранее озаботиться электрическим или, на худой конец, паровым приводом. Итак, 300 + 100 = 400, а осталось 350 мс, но это только механическая часть. Кстати, интересная оптимизация состоит в том, что турель может всё время быстро вращаться: это, во-первых, позволяет экономить на разгоне (хотя, тут можно поспорить); во-вторых, снижает средний показатель угла доворота, необходимого для обстрела подлетающего снаряда – в некоторых случаях мы уже будем смотреть примерно на подлетающий снаряд, когда тот будет обнаружен (лучше всего, конечно, сразу развернуться в сторону вероятного противника). Для того, чтобы понять, куда же стрелять, как и в случае с лазером, придётся провести траекторные вычисления, пусть, как и в прошлый раз, это 50-100 мс. 350 – 100 = 250 мс, столько осталось времени на выстрел.

Кинетический перехватчик должен маневрировать, чтобы корректировать свой полёт и попадать в цель. Маневрирование, кроме того, позволяет сократить время поворота турели: оптимизированный вариант стреляет, развернув турель в некий сектор, захватывающий снаряд, а перехватчик дальше наводится дополнительно. Траектория полёта изменяется, расстояние несколько увеличивается, но это может оказаться оправданным. Особенно, если выпускать несколько перехватчиков. А для получения высокой вероятности перехвата – именно так и придётся поступать. Выстрелы могут происходить параллельно, поэтому 250 мс не нужно делить между десятью, как минимум, стволами. Естественно, 250 мс – более чем достаточно. Если начать раньше, то перехватчик получит шанс встретить снаряд на большем удалении от критического рубежа. Проблема в том, что обычный, не реактивный, перехватчик довольно быстро теряет скорость с расстоянием. Поэтому лучше всего стрелять кинетическим перехватчиком из электромагнитной пушки, разгоняющей снаряд хотя бы до 2500 м/сек. Сооружение громоздкое, но зато всепогодное и эффективное. Это вам не лазер.

(Скопирую из Facebook.com.) Интересно развивается наука. Много лет назад я отвечал на “детские вопросы” сайта “Элементы” (рубрика была замечательная, а вопросы – очень занятные.) Среди вопросов был и такой: видят ли микробы друг друга? Мой ответ, который я и сейчас считаю неплохо обоснованным, сводился к тому, что у видеть микробы не могут, так как, во-первых, размеры микробов сравнимы с минимальной разрешающей способностью световой оптической системы; во-вторых, глаз, как оптический прибор, является слишком сложной, по сравнению с микробом, структурой. А теперь вот микробиологи раз – и докопались до того, что обнаружили некую сложную структуру у одноклеточного планктона, которую уже называют “глазом”. Хорошо ещё, что в кавычках, условно. Очень интересно. Осталось обнаружить только “мозг”. Хотя, я всё равно не понимаю, как может что-то увидеть “глаз” такого размера. Ну, если только эти микробы настолько продвинутые, что развились до ближнепольной микроскопии. Впрочем, в таком случае микробы должны были бы изучать микробиологов, а не наоборот.

Про то, что биткоины появились с некоторой дополнительной, “неплатёжной”, целью, приходится слышать нередко. Чуть чаще говорят, что вычислительная мощность узлов, составляющих сеть этой распределённой платёжной системы, очень велика и может быть использована для криптологических задач. На правах технократического юмора (весьма занудного, конечно) процитирую свою заметку из Facebook:

Попробовал придумать, как всесильное АНБ могло бы использовать вычислительную мощность сети биткоин (которую, в таком случае, агентство само и продвигает, незаметно) в своих целях. Напомню, что майнеры биткоинов вычисляют SHA-256, подбирая аргумент под заданное значение. Результат SHA-256 от входного сообщения (заголовка блока транзакций) должен быть меньше заданного в сети числа. Подбор заголовка и составляет сложность. Казалось бы, какой от этого толк криптологии?

Сформулировал такой заговор: АНБ известна некоторая оптимизация, позволяющая находить произвольные коллизии SHA-256; но для практического использования этой оптимизации требуется знать некоторое число “особых точек” – блоков данных, для которых результат SHA-256 меньше порогового значения. Данная теория, кстати, не выглядит математически абсурдной. Множество найденных “особых точек” позволяет АНБ построить радужную таблицу, на которой и заработает их секретная оптимизация SHA-256. Так как денег в бюджете не хватило (мало ли – может, ушли на строительство), решено было запустить в эти интернеты криптовалюту, протокол которой привязан к вычислению “особых точек”, да ещё и устроен таким образом, что результаты автоматически публикуются через Сеть, с резервированием (удобно собирать). При этом нужное АНБ пороговое значение достаточно мало, но и протокол устроен так, что мощность сети наращивается постепенно, а на основе этого роста корректируется и цель сети (Target), которая всё ближе и ближе к полезному для АНБ результату.

Тут особенно занимательно, что в таком случае сеть сама постепенно выходит на нужную мощность – так устроен протокол: награда за майнинг мотивирует к увеличению мощности майнера, а такое увеличение сдвигает пороговое значение сложности.

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

Во-первых, производитель, опираясь на “груз ответственности”, запрещает ручное вождение, а также, ещё раз, запрещает вносить какие бы то ни было изменения в конструкцию и ПО, да и вообще – автомобиль они больше не продают, а лишь лицензируют “право проезда”;

Во-вторых, ответственность за ошибки конструкции и опасные “баги” в программном обеспечении будет сводиться к единичным миллионным выплатам (не так много для автогиганта) и отзыву автомобилей “на перепрошивку” (практика уже отработана, и с отзывами, и с выплатами);

В-третьих, и это самое интересное, наверняка появятся некие квоты на “травматизм и ДТП”, которыми страховые компании и автопроизводители будут обмениваться между собой – потому что в роботизированном мире подобная статистка хорошо формализуется.

Вопрос лишь в том, много ли окажется желающих за собственные деньги ездить в запертой (“а чтобы не выскочили на проезжую часть без команды”) коробочке, управляемой даже не локальным персональным автопилотом, а транспортной сетью (“потому что планирование, оптимизация потоков”), без единого шанса как-то повлиять на ситуацию в момент перемещения между точками А и Б. Особенно, если учитывать следующий тонкий момент. Автомобили-роботы, находящиеся в транспортном потоке, обмениваются между собой информацией и, в перспективе, принимают решения о безопасном “разруливании” каких-то критических ситуаций. Можно ожидать, что роботы и компьютеры, обычно, справятся с такой задачей хорошо и без потерь. Но возможны ситуации, – например, возникающие в результате стихийных событий, вроде падения дерева на трассу, – когда выхода без потерь просто нет. И вот, в случае транспортного потока ближайшего будущего, решение о том, кому из пассажиров и что терять, станут принимать роботы, управляющие коробочками-автомобилями. Многим ли это понравится?

Впрочем, роботы, конечно, безопаснее, это доказывает не только гражданская авиация. Безопаснее – до тех пор, пока под контролем.

В продолжение предыдущей записки о системе от Wolfram-а, распознающей образы на изображениях. Интересно, что ImageIdentify работает весьма хорошо даже с очень сложными сценами. Запутать систему, отогнав её на подобающую сторону теста принадлежности к роботам, конечно можно, особенно, если вы понимаете математические основы “компьютерного зрения”, но результаты всё равно впечатляют. Возьмём для примера разные картинки велосипедов и отправим их на сервис ImageIdentify.com. Опознать что-то общее (“велосипедное”) на этих картинках человеку несложно, у автомата – сложности возникают, капчу он бы не решил.

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

Есть такие “капчи”, где требуется узнать предметы или животных на фотографиях, выделив сходные изображения (например те, где есть кошки). Недавно появился сервис из проектов Стивена Вольфрама (Stephen Wolfram), который эффективность подобной капчи сводит практически к нулю: imageidentify.com – обученная группа машин успешно распознаёт и котов, и предметы быта. Правда, носорог на картинке ниже остался незамеченным. Но это не страшно, потому что откуда машине знать, что носорог может быть размером с кошку?

Сопроводительный текст рассказывает, что это демонстрация одной функции, встроенной в Wolfram Language – ImageIdentify. Полезная, надо сказать, функция.

Предположим, что некоторый пользователь онлайн-игры использует несколько аккаунтов (такое часто случается). Если администрации игры требуется сгруппировать такие аккаунты – а это просто необходимо для вычисления различных “маркетинговых” характеристик, – то для этого хорошо подходит механизм “профилирования” на основе активности пользователя в игре.

Понятно, что можно попробовать связать аккаунты на основе IP-адресов, но, при существующем распространении NAT, за одним адресом могут оказаться сотни различных пользователей. Если игра использует специальный клиент, идентификатором может послужить некий уникальный номер клиентской программы, но ведь и компьютер может быть общим, так что тоже возникает погрешность. А вот изменить поведение в игре – игроку крайне сложно, скорее, невозможно, если вести речь не о крупных чисто игровых действиях, а о базовых интерактивных элементах: о манере передвижения мышки, управления движением персонажа, использования меню и настроек в игре.

Для записи таких характеристик придётся вести подробные логи. Но дисковое пространство сейчас стоит недорого, да и сбор нужных параметров (которые неплохо “сжимаются” при использовании правильного кодирования) не отнимет заметной полосы пропускания канала доступа к Интернету. Зато можно быть уверенным, что уже на небольшом числе элементов идентифицирующей последовательности множество записей в логах расщепится на уникальные группы, соответствующие отдельным игрокам. Что может представлять собой идентифицирующая последовательность? Например, вот такой набор характеристик: средняя скорость перемещения курсора мыши; соотношение вертикальной и горизонтальной скорости курсора; частота следования сообщений в игровом чате; число уникальных слов, используемых в чате; частота нажатия кнопок управления персонажем (или игровым процессом, не важно) и т.д., и т.п. Чем больше параметров, тем точнее будет разделение пользователей.

Поведенческая идентификация несравнимо качественнее, чем идентификация по техническим параметрам (IP-адрес, скорость канала, тип оборудования и т.п.). Причина в том, что технические параметры характеризуют компьютер, а поведенческие – того, кто компьютер использует. Преимущество онлайн-игр перед другими системами (типа интернет-банков или веб-сайтов) в том, что пользователь здесь взаимодействует с системой гораздо более активно, совершая за малое время большое число измеримых действий.

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

Правда, злоумышленникам придётся весьма тщательно готовиться. Например, смартфон, предоставленный на замену, должен быть с SIM-картой внутри. Потому что владелец атакуемого аккаунта может достаточно быстро решить переставить карту в другой телефонный аппарат, чтобы, хотя бы, позвонить или иметь возможность принимать звонки. Обычная дефектная SIM-карта наведёт на подозрения. Поэтому нужна специальная карта, которая приводит к “зависанию” других аппаратов. К сожалению, из-за разнообразия оборудования такая карта вряд ли возможна.

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