Проблема SETI@home

Перспективы В 1999 году группа астрофизиков из Беркли поняла, что безопасность - первоочередная цель при организации распределённых вычислений. В рамках программы поиска внеземного разума (SETI) исследователи собрали гигабайты сырых данных с радиотелескопов по всему миру. Не в силах обработать все данные, они пришли к идее распределить эти вычисления. Машина в Беркли работает как сервер и посылает данные на компьютеры-клиенты, которые проверяют данные на наличие сигналов и посылают назад. Этот проект был назван SETI@Home. Как скоро обнаружили исследователи, проект SETI@Home принёс им проблему SETI@Home: как ты можешь убедиться в том, что клиентские машины делают "right thing"? [(Примечание Коммандера: right thing - устоявшееся программистское выражение. Переводится как "правильная вещь". Означает истинно верный способ решения проблемы, обычно - применение правильного алгоритма, дающего единственно верный результат.)] Проблема SETI@Home - интересный пример распределённых компьютерных проблем, которые затаились за горизонтом и пока не видны, но по мере движения вперед готовы встать на нашем пути. Сегодня только исследователи-астрофизики и взломщики криптографических алгоритмов распределяют свои вычисления. [(Примечание Коммандера: первые программы для распределённых вычислений предназначались для проверки надёжности криптографических алгоритмов.)] Завтра "продажа лишних циклов" может стать источником дохода для компьютерных пользователей и жизненным ресурсом для компаний, заинтересованных в крупномасштабных вычислениях. Перед тем, как эта революция в компьютерных ресурсах случится, некоторые проблемы (и прежде всего проблема SETI@Home) должны быть решены. Это также важно для создания механизма оплаты работы клиентов и для защиты секретности и целостности данных. Проблема Проект SETI@Home достиг большего, чем было в самых диких мечтах его создателей. На данный момент более миллиона машин запускают клиентскую программу SETI@Home. [(Примечание Коммандера. Эта статья написана в октябре 2000 года. Сейчас - больше трёх миллионов. Но только треть участников просчитала хотя бы один блок данных.)] Каждая клиентская машина загружает из штаб-квартиры в Беркли рабочий юнит (Work Unit, WU), содержащий блок данных с радиотелескопа, пропускает рабочий юнит через алгоритмы обработки сигнала, а потом сообщает результаты. В SETI@Home это не только позволяет исследователям на лету, по мере поступления, обрабатывать новые данные, - им просто не хватает данных для того, чтобы загрузить все машины! С этим успехом пришла слава; со славой пришли "олли". Приход Олли. Olli - псевдо одного из подписчиков конференции SCI.ASTRO.SETI, который решил, что клиентская программа SETI@Home слишком медленная и нуждается в усовершенствовании. Olli выпустил патч к исходной программе из Беркли, добавляющий эти "усовершенствования". Тогда как Olli заявлял, что патч делает клиент быстрее, исследователи SETI@Home утверждали, что патч служит причиной тому, что клиент возвращает ответы, которые могут непредсказуемо отличаться от вычисленных с помощью оригинального непропатченного клиента. От результатов эксперимента чуть не остались одни руины. Проблема заключалась в том, что пропатченные и непропатченные клиенты отправляли свои результаты на один и тот же сервер SETI@Home, причем не было никакой возможности отличить одни от других. [(Комментарий Коммандера. Основная часть вычислений, делаемых программой - быстрое преобразование Фурье. Чтобы понять, как оно работает, у меня в Политехе ушло полгода, и теперь на то, чтобы вспомнить, уйдёт, видимо, столько же. Так что каким бы хорошим программистом не был Olli, лучше профессиональных математиков написать программу, осуществляющую БПФ, он не мог.)] SETI@Home встречает Microsoft. Olli был не единственным, кто пытался "усовершенствовать" клиент SETI@Home. FAQ конференции SCI.ASTRO.SETI рассказывает о другом неверном патче. Microsoft сообщил о своей собственной версии SETI, заточенной под аппаратуру с установленным Windows. Они хотели быстрее всех просчитывать рабочие юниты, чтобы доказать, насколько хорошо Windows работает. Персонал SETI обнаружил жульничество Microsoft и указал, что надо использовать оригинальное программное обеспечение SETI. Люди пригрозили распустить команду Microsoft и сказали, что все результаты, полученные от обработки WU на неофициальных SETI-клиентах, будут отклонены. [(Примечание Коммандера: на сайте SETI@Home устроено своеобразное социалистическое соревнование - кто сосчитает больше юнитов, чей юнит просчитается быстрее и т.д., причём участвовать можно как поодиночке, так и группами; есть даже несколько команд из России.)] Учёные SETI явно беспокоятся, что их алгоритмы могут быть запрограммированы некорректно. [(Особенно если за дело берется Микрософт. - СХ)] Инциденты, подобные тем, что произошли с Olli и Microsoft, создали проблему SETI@Home: могут ли исследователи найти разницу между рабочими юнитами, просчитанными на одном из их клиентов и просчитанными на пропатченном клиенте? Как серверу узнать, что клиент играет по правилам? Пока ведутся попытки сделать запуск пропатченного клиента социально неприемлемым (напимер, на страничке "Patch-Free Processing" ), но никто не уверен, что эти попытки сработают. Гораздо предпочтительнее найти способ, позволяющий исключить пропатченные клиенты и их испорченные рабочие юниты из вычислений SETI@Home. Проверка распределённых вычислений Думая над проблемой SETI@Home, понимаешь, что это только частный случай более общей проблемы проверки распределённых вычислений: "Дано огромное количество вычислений, разделённых на множество компьютеров. Как делать так, чтобы злостно обманывающие нас компьютеры не смогли нанести ущерб?" Это не новая проблема. Распределённые вычисления - почтенная тема разработок, а идея "продажи лишних циклов процессора" обмусоливается в научной фантастике многие годы. В жизни распределённые вычисления используются с начала 1980-х годов при создании машинных ферм для обработки трёхмерных изображений. Фермы позволяют художникам создавать огромные изображения без покупки суперкомпьютера. Позднее необходимость в научных вычислениях положила начало созданию таких структур, как Parallel Virtual Machine (PVM) и Beowulf, которые облегчают распределённые вычисления между многими машинами. Используемые компьютеры обычно принадлежали к одной сущности - были одинаковы. И каждая из машин считалась "хорошей" или "плохой", если она функционировала или глючила. Не было машин, выдающих неверный результат умышленно. Internet сделал возможным распределить вычисления на гораздо большее число машин. Однако, распределение вычислений по Сети потребовало от производителей предусмотреть возможность клиентов-злодеев. Первым крупномасштабным проектом, лицом к лицу столкнувшимся с этой проблемой, был основанный на грубой силе взлом криптографических алгоритмов. В 1995 году сообщество киберпанков организовало несколько соревнований взломщиков, нацеленных на взлом (простым перебором паролей) алгоритма RC-4 с 40-битным ключом (это максимально возможная длина ключа для программ на экспорт по американским законам). Во время соревнований народ начал поднимать такие вопросы, как "а что если машина скажет, что она этот код уже проверила, не сделав этого?" и "что случится, если машина, разделяющая работу, временно недоступна?" Сегодня те, кто участвует в соревновании взломщиков на сайте distributed.net, ищут решение тех же проблем. Позднее стартапы entropia.com и centrata.com также стремились продать свободные циклы. [(Стартап - новый проект, возникший на голом месте, в Сети - просто реализация какой-то новой идеи, коммерческий сайт, не имеющий ничего, кроме доменного имени. В середине 2000 года многие стартапы стоили дороже старых фирм с солидным капиталом, а к апрелю 2001 - практически все разорились. В общем, сетевой аналог АО МММ, но один из тысячи стартапов становится-таки прибыльной солидной фирмой. СХ)] Детали выложены на сайте centrata.com. Компания позже стала второй в конкурсе MIT 50K Entrepreneurship Competition с планом использования свободного места на дисках огромного числа компьютеров, подключенных к Сети. Методы защиты SETI@Home Сегодняшняя стратегия На данный момент сервер SETI@Home смотрит на "подозрительно" просчитанные рабочие юниты и потом перенаправляет их на те машины, которым доверяет. Система работает, но всё зависит от сложности определения "подозрительных" ответов. К тому же, если слишком много блоков будут выглядеть подозрительно, то машины, которым сервер доверяет, станут чем-то вроде бутылочного горлышка. Это худшая из исследовательских стратегий. Убрать желание жульничать Проект SETI@Home собирает и публикует рейтинги вычислений, показывающие, какие машины сделали больше работы. Соревнование вычислителей нацелено на то, чтобы поощрять клиентов для увеличения своего рейтинга подключать к решению проблемы больше машин. К несчастью, народ вместо этого переходит к пропатченным клиентам (как Olli), чтобы поднять своё положение. В некотором роде проекту SETI@Home повезло, поскольку люди, запускающие пропатченные клиенты (например, от Microsoft), на самом деле не пытаются разрушить вычисления SETI@Home. Тем не менее, более быстрый пропатченный клиент - путь к повышению рейтинга. Уберите рейтинг и стимул к жульничеству исчезнет прочь. Преимущества такого подхода - в простоте, его легко понять и легко внедрить. Но есть как минимум три недостатка: Нельзя определить или остановить клиента, который уже установил патч. Если у клиента есть и другие мотивы установить патч, этот метод не работает. Уничтожение рейтингов также уберёт и стимул, из-за которого некоторые пользователи приняли участие в проекте. Другой вариант этого метода - оставить рейтинги, но в качестве штрафной санкции немедленно удалять из них пропатченных клиентов. Это решение не коснется тех, кому рейтинги безразличны. Зато тем недобросовестным клиентам, кому рейтинги небезразличны, будет предложено встать на путь соревнования в дружбе со всеми, кто вовлечён в SETI@Home. К несчастью, взломанные клиенты сначала должны быть обнаружены. Нижеизложенные методы описывают пути обнаружения и взаимодействия с пропатченными клиентами. Использование клиентов для проверки других клиентов. Проекту SETI@Home повезло ещё и в том, что людей имеется гораздо больше, чем рабочих юнитов. Миллионы людей, вовлеченных в проект, дают возможность многократно просчитать каждый блок данных. Фактически, каждый "подозрительный" рабочий юнит уже дважды проверен на сервере SETI@Home. Огромное число клиентов позволяет организовать подсчёт так, что один и тот же просчитанный блок данных, принятый от нескольких клиентов, формирует блок голосования. Результаты клиентов сравниваются друг с другом и в конце вычислений принимается тот, что набрал большинство голосов. Клиенты, получившие в блоке меньшинство, считаются пропатченными в том случае, когда результат большинства будет корректным, т.е. говорить о том, что такой результат вычислений мог получиться на этом самом рабочем юните. Получится ли? Для того, чтобы стратегия оправдалась, надо придерживаться следующего: Пропатченные клиенты в каждом блоке должны быть в меньшинстве. Это зависит от того, как сконструированы блоки голосования. Самый честный путь - определять клиентов в блок голосования случайным образом; в этом случае успех зависит от того, сколько из клиентов, включённых в это случайное распределение, пропатчены. Другой метод использует "постоянные учетные карточки клиентов" (persistent client identities). Если сервер может определить настоящих клиентов, он помещает их в один голосующий блок с незнакомыми или вызывающими недоверие серверами для проверки результатов этих серверов. Доверенными клиентами могут быть те, что находятся под непосредственным контролем сервера или клиенты, которые до этого выдавали только хорошие результаты, совпадающие с теми, что получены на машинах под непосредственным контролем сервера. Ответы от пропатченного клиента и ответы от настоящего клиента могут быть разными, когда оба просчитывают одинаковые данные. Например, если единственным ответом, посылаемым назад в SETI@Home будут сообщения "Да, Чужие найдены!" или "Нет, Чужие здесь не ходят!", тогда ответы от двух типов клиентов будут неразличимыми практически постоянно. С другой стороны, если ответ содержит отчёт обо всем проделанном на клиенте процессе вычислений, включая выполненные инструкции и содержание регистров на каждом шаге, то любая несогласованность будет быстро обнаружена после простого построчного сравнения отчётов. Для достаточно детального отчёта полное тождество записей означает, что оба клиента работали по одному алгоритму. Этот подход хорошо работает в SETI@Home как минимум по двум причинам. Во-первых, он требует избытка клиентов, который наличествует в SETI@Home. Во-вторых, пропатченные клиенты отличны друго от друга и нет злого гения, определяющего, какие из клиентов пропатчены. Если бы нашёлся противник, способный наблюдать за сервером и потом разрушать ответы клиентов, помещённые в один голосующий блок, то шансы на успех у этого подхода будут ничтожными. Установка ловушек и тестирование клиентов Предположим, что точные различия между пропатченным и настоящим клиентами на конкретном рабочем юните могут быть идентифицированы и засечены. В случае с патчем Olli, исходники патча недоступны. Зато доступны сами клиенты. Можно в пошаговом режиме сравнить два клиента и найти их первое отличие. Например, на промежуточном шаге вычислений T настоящий клиент присвоит переменной "x" значение "4.243", а пропатченный клиент присвоит "x" значение "4.200". Теперь у нас есть метод для определения, пропачтен клиент или нет. Установите ловушку! Просто дайте ему тестовый рабочий юнит и попросите сообщить значение "x" на шаге T. Если клиент сообщит "4.200", то он пропатчен. Преимущество этого подхода - он даёт доказательство, что клиент был подправлен. Недостаток - если пропатченный клиент предполагает, что его тестируют, он может запустить настоящий клиент, определить, каким должен быть "x" и потом сообщать "4.243" при запуске пропатченного клиента в будущем. Более серьёзный недостаток - требуется, чтобы сервер SETI@Home знал, какой именно тип патча клиент может запустить, или получал отчёт, устанавливающий факт использования корректного алгоритма. Записываемые отчеты и случайное моделирование В октябре 1999г. на конференции SCI.CRYPT David Wagner, Paul Crowley и другие предложили метод, который решает некоторые проблемы с клиентами, знающими, что их тестируют. Вместо того, чтобы сначала собирать с клиентов, а затем рассылать тестовые блоки информации, надо требовать от клиентов посылки защищённой от коллизий хеш-функции отчёта о вычислениях (collision-resistant hashed transcript of computation) с каждым ответом. Фраза "collision-resistant hashed transcript of computation" вызывает зевоту, попробуем прояснить её шаг за шагом. На отчёт о вычислениях (transcript of computation) мы уже ссылались в описании метода, использующего одних клиентов для тестирования других; в отчёт выводятся такие вещи, как промежуточные шаги, внутреннее состояние, содержимое регистров и т.п., предназначенные для определения того, запускает ли клиент корректный алгоритм без патчей. Так как подобные отчеты достаточно велики, клиенты посылают только защищённую от коллизий хеш-функцию отчёта. Хеш функция в данном случае - это функция, которая получает строки произвольной длины, а возвращает строки фиксированной (обычно - достаточно короткой) длины - 128 или 160 бит. Защищённая от коллизий хеш-функция должна быть построена так, чтобы было достаточно трудно найти две строчки, которые дают одинаковый результат на выходе. Это свойство необходимо, потому что иначе клиент в состоянии найти два отчёта, которые выдают одинаковые результаты на этой хеш-функции. Идея заключается в том, что хеш отчёта - это сжатая замена самого отчёта. [(Комментарий Коммандера: Возьмите любой словарь. Сверху у каждой колонки вы найдёте хеш-функцию слов этой колонки. Например, в словаре, с которым я перевожу эту статью, на с.547 есть 2 колонки. Одна начинается словом "substantiation", а другая - "subvention". Хеш-функция будет "SUB" и "SUC" (потому что вторая колонка заканчивается словом "succumb"). Но это не будет хеш-функция, защищённая от коллизий, т.к. с букв "SUB" и "SUC" начинаются много слов в этом словаре. А вот если я пронумерую все слова, то хеш-функция станет защищённой от коллизий - для "succumb" в моём словаре она будет выглядеть так: "SUC007".)] Теперь после того, как клиенты просчитали данные и послали их хеши, сервер получает набор различных хешированных отчётов для проверки. Сервер случайным образом выбирает один рабочий юнит, результаты работы над которым похожи на истинные, сам вычисляет правильный ответ и затем сравнивает с ним пришедшие от клиентов хеш-функции этого рабочего юнита. Так как сервер выбирает, какой из отчётов следует проверить, уже после того, как вычисления завершены, клиент не знает, тестируют его в данный момент или нет! Теперь для того, чтобы предотвратить разоблачение в течение долгого времени, пропатченный клиент должен генерировать "хороший" отчёт для каждого ответа и получать хеш этого хорошего отчёта для своего ответа. Если генерация этого отчёта займёт хотя бы столько же времени, сколько и работа настоящего клиента SETI@Home, то пропатченный клиент теряет преимущество по эффективности по сравнению с настоящим клиентом. Быстро проверяемые доказательства корректности Случайная природа предыдущего метода оставляет некоторое место для ошибки. Даже можно точно подсчитать эту погрешность. Но могут быть ситуации, когда ошибка нежелательна. Добавим, что рассмотренные ранее методы не предполагают, что кто-то пытается просто разрушить вычисления SETI@Home, совершенно не заботясь о рейтингах. Другие подходы должны иметь клиентов, предоставляющих доказательства корректности (proofs of correctness) вместе с каждым ответом. Тогда сервер сервер может действовать, как средство проверки (verifier) этих доказательств и в каждом конкретном случае решать - принять ответ или нет. Отчёты о вычислениях, используемые в предыдущем методе, могут быть рассмотрены, как доказательство корректности клиентских вычислений. Это влечёт за собой вопрос: "есть ли пути построения коротких и быстропроверяемых отчётов?" В конце концов, если проверка вычислений занимает столько же времени, сколько сами вычисления, этот подход ничего не даст. Для специфического случая SETI@Home такие быстропроверяемые доказательства пока неизвестны. Их изучение близко относится к таким областям исследований, как проверка программ, самопроверка и самокоррекция. Эти области изучают программы, которые глючат, т.е. сбоят на некоторых отрезках входных данных (так же, как пропатченные клиенты возвращают "сбойные" результаты для "программы", состоящей из совокупности всех клиентов SETI@Home). Идея заключается в том, чтобы разработать структуру, позволяющую глючной программе определять, где она делает ошибки или даже корректировать свои собственные ошибки. Разработки в этой области начал Manuel Blum. Их обзор можно найти на странице Hal'а Wasserman'а. Ко всему этому относится и понятие о вероятностно проверяемом доказательстве, где проверяющему необходимо только посмотреть на несколько небольших, случайно выбранных участков в доказательстве, чтобы сказать, верно оно или нет. Вероятностно проверяемые доказательства, если их удастся сконструировать, послужат поддержкой для любой проблемы, при решении которой можно или хочется прибегнуть к распределённым вычислениям. Но обычно они совершенно неприменимы - хотя бы из-за своей непомерной длины (несмотря на то, что для проверки достаточно только посмотреть несколько бит). Silvio Micali представил ещё одно направление, названное звуком вычислений (computationally sound) или CS-доказательство (CS-Proof), которое легче проверить из-за некоторых предположений в конструкции доказательства. Исследования в этих областях только ведутся. Представление о состоянии дел в области секретных военных вычислений можно найти в Тезисе Канетти (Canetti's thesis). Какие стратегии будут работать в SETI@Home? Метод "клиент проверяет клиента" может быть использован с использованием машин, которым сервер доверяет. Будут по порядку строиться "уровни доверия" из клиентов, которые потом будут использованы для определения того, какие клиенты подключатся к блокам голосования. Например, клиент может быть выбран и его результат сравнён с результатом машины, которой сервер SETI@Home полностью доверяет. Если результат проверки чаще всего положителен, то вероятнее всего, проверяемая машина работает под настоящей версией клиента. А значит, она может быть включена в блок голосования совместно с другими - частично проверенными и неизвестными клиентами. Всё это происходит без какой-либо модификации клиентских программ и эффективно разгружает ресурсы полностью проверенных машин SETI@Home. Случайная проверка хешированных отчётов и установка ловушек, конечно же, будет работать в проекте SETI@Home. Проблема только в том, что до сих пор не установлен формат отчёта. Вдобавок, для применения этого метода должны быть переписаны как клиентские, так и серверные программы, а это значит, что народу придётся скачивать новую версию клиентской программы. Пока старые клиенты апгрейдятся, выполнение проекта будет тормозиться. Метод быстропроверяемых доказательств на текущий момент не выглядит работоспособным, т.к. нет очевидного пути для создания такого доказательства корректности и никто в данный момент не ищет неочевидные пути, чтобы сделать его. Этот вопрос встанет в отдалённом будущем или когда исчерпают себя другие методы. Критической точкой здесь является поиск злонамеренных клиентов и выяснение их количества. Похоже, что в SETI@Home немного таких клиентов и все они хотят только лучшего рейтинга. Другие распределённые вычисления могут и не быть настолько удачливыми. Заключение Изучение основных направлений секретных военных вычислений дало нам много интересных работ в последние две декады. Менее изучены, к несчастью, инструменты и технологии для продвижения теоретических результатов в реальный мир. Старая мечта больших распределённых вычислений наконец-то становится правдой, но наши инструменты для создания и анализа реальных систем всё ещё остаются примитивными. Исследования нескольких следующих лет перекроют эту брешь мостом. Благодарности. Guy Macon поднял проблему в конференции SCI.CRYPT. David Wagner дал разрешение описать метод записываемых отчётов. Этой статье положила начало дискуссия в MIT Applied Security Reading Group; автор благодарит Kevin'а Fu за предоставленную возможность высказаться, и слушателей, включая David'a Andersen'a, Trevor'a Schroeder'a и William'a Ricker'a за их комментарии. David'a Alpert'a, Joev Dubach'a, Andy Oram'a, и William'a Josephson'a за предоставленные комментарии и моральную поддержку. И наконец, автор в долгу перед анонимными обозревателями и редакторами "Crossroad", которые сделали возможным появление этой колонки. Биография David Molnar начал использовать PGP в 1993. Он заинтересовался криптографией, разбираясь, "почему это работает" и с тех пор продолжает ее изучать . Сейчас, после окончания аспирантуры Гарвардского Университета, он продолжает работать в области безопасности и криптографии, посещая курсы, читая конференции, ньюсгруппы и листы рассылки и участвуя в DEF CON в своём родном Лас-Вегасе. Дэвид - член-корреспондент ACM и член International Association for Cryptologic Research