В 1985 году вышла книга Орсона Скотта Карда «Игра Эндера», позднее отмеченная престижными в мире научной фантастики наградами Hugo и Nebula. Главный герой, Эндер Уиггин, обучаясь в военной школе, тренируется на симуляторе для подготовки к военным действиям в масштабе Вселенной. Однако в реальности на протяжении нескольких месяцев он, не осознавая этого, руководит космическими войсками, которые разрушают чужую планету, чтобы ее армада не сумела уничтожить Землю. Таким образом Эндер, не желая этого, вел войну и безрассудно рисковал жизнями людей без осознания реальных последствий своих действий. А могут ли в действительности опытные игроки в военные компьютерные игры, не осознавая этого, контролировать реальные летательные аппараты? Не пытались ли взломщики сети PS3 на самом деле создать ботнет или собрать побочные продукты уже существующей зомби-сети? Другими словами, могут ли хакеры в злонамеренных целях использовать сети решения задач — либо путем создания игровых сайтов для приманки, либо посредством вторжения в уже существующие игровые сети, организованные на социальных игровых сайтах или независимых игровых серверах?

Ботнет на PlayStation 3?

Спустя всего несколько дней после событий с PS3 анонимный блогер опубликовал на форуме The Register рассуждения о том, что хакеры могли создать клиентскую программу для ботнета, работающую на шести незадействованных операционной системой процессорных модулях PS3: «Если бы некто разослал вредоносный код на 10 млн экземпляров PS3 (а всего их продано около 77 млн), он получил бы в свое распоряжение вычислительную мощность в 1,536 EFLOPS. Даже если операции ввода-вывода затормозят общее быстродействие всего до 1% этой мощности, то в руках злоумышленников по-прежнему останется мощный суперкомпьютер. Если бы им удалось удержать над ним контроль какое-то время, они сумели бы взломать шифр RSA-1024, очень возможно, что и RSA-2048 и, вероятно, даже RSA-3072». Действительно, еще в 2008 году европейские исследователи продемонстрировали, что с помощью сети из консолей PS3 можно клонировать SSL-сертификат сайта, если он полагается на хэш-алгоритм MD5.

Нет ничего нового в том, чтобы решать трудоемкие задачи с помощью grid, основанных на принципе добровольного жертвования пользователями ресурсов своих компьютеров. Как, например, в SETI, проекте поиска внеземного разума Калифорнийского университета в Беркли, в котором компьютеры добровольцев в периоды простоя ищут повторяющиеся последовательности в радиосигналах, полученных из космоса. Этот проект базируется на системе BOINC (Berkeley Open Infrastructure for Network Computing), позволяющей задействовать свободное время компьютеров на платформах Windows, Mac OS и Linux для решения задач большой размерности (поиск методов лечения болезней, исследование глобального потепления, поиск пульсаров, совершение новых научных открытий). К сегодняшнему дню на исследовательские проекты пожертвовано уже около 7 млрд часов работы процессорных ядер. По данным на апрель 2011 года, у BOINC было свыше 300 тыс. добровольных участников и более 500 тыс. компьютеров, ежедневно создающих среднюю мощность 5,6 PFLOPS. Сейчас проекты BOINC и SETI приостановлены на неопределенное время ввиду недостатка финансирования, однако архитектуру BOINC вполне можно было бы взять за образец для создания основанной на игре зомби-сети, которая способна охватить миллионы компьютеров или игровых консолей.

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

Пиратское решение задач

Идея скрытого решения задач с помощью краудсорсинга (то есть делегирования решения своей задачи распределенному сообществу) не нова; например, в 2007 году художники Аарон Коблин и Такаши Кавашима с помощью сервиса Amazon Mechanical Turk организовали проект с участием нескольких тысяч человек по коллективному созданию изображения стодолларовой купюры в высоком разрешении. Каждый должен был по шаблону нарисовать свой фрагмент, но в чем состояла общая задача проекта, участники не знали.

Известны примеры криминального краудсорсинга — троянская программа Captcha Busting Trojan замаскирована под компьютерный «стриптиз»: чтобы заставить экранную девушку раздеться, нужно решать CAPTCHA-тесты. Такие тесты применяются, в частности, для предотвращения автоматизированного создания ящиков электронной почты. С помощью данного троянца хакеры создали более 0,5 млн спамерских акаунтов в сервисах Hotmail, Yahoo и Gmail.

 

NP-сложные и NP-полные задачи

NP-сложные и NP-полные задачи – это вычислительные задачи, которые можно решить методом перебора. Многие игры содержат элементы комбинаторных или графовых задач, являющихся NP-сложными или NP-полными.

Задачи из класса NP-сложных обладают следующими свойствами:

  • не существует известного алгоритма полиномиального (p в некоторой степени) времени (время решения задачи зависит от ее сложности), который решает любую отдельно взятую задачу из этого класса;
  • из существования алгоритма полиномиального времени для решения любой конкретной задачи в классе следует, что всякую NP-полную задачу можно решить с помощью алгоритма полиномиального времени.

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

 

С помощью пиратского краудсорсинга, осуществляемого посредством игр, правительства могли бы исполнять сложные алгоритмы для нужд создания новых лекарств или решения задач распределения ресурсов. Все задачи последнего типа содержат в себе либо NP-сложные, либо NP-полные задачи (см. врезку).

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

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

Трансформация игрового процесса

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

Некоторые из приведенных игр доступны на нескольких платформах. Например, Mafia Wars имеется на MySpace, Facebook и других сайтах социальных сетей. Эта игра даже существует в виде приложения для iPhone. С помощью распространенных iPhone-игр вроде «Эрудита» или судоку хакеры потенциально могут решать задачи распределения ресурсов, взлома шифров или проведения разного рода испытаний на проникновение.

 

Онлайн-игры с «двойным дном»
Таблица. Популярные многопользовательские игры для Facebook и их потенциал в деле пиратского решения задач

 

Игры для браузеров вроде Runescape и FIFA Online могли бы быть замаскированными системами управления войсками и армадами летательных аппаратов. Даже онлайн-викторины, как на сайте Sporcle.com, могли бы содержать скрытые внедренные задачи для решения силами ее участников. Более того, любую из этих игр можно использовать для исследования динамики развития социальных сетей или для поиска подходящих социальных сетей определенной специализации (например, объединяющих коллекционеров автомобилей или ресторанных завсегдатаев). Эти сведения можно было бы коррелировать с иной доступной в Web информацией, чтобы проводить фишинговые атаки или выполнять отвлекающие маневры для иных злонамеренных целей. Самая безобидная задача здесь — создание неплохого генератора случайных чисел, который хакеры могли бы использовать для нужд шифрования или получения случайных пробных ключей при взломе шифров (вспомним теорему о бесконечных обезьянах).

***

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

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

Филип Лапланте (plaplante@psu.edu) — профессор программной инженерии Пенсильванского университета

Philip Laplante, Ender Wiggin. Played Mafia Wars Too. IT Pro, July/August 2011, IEEE Computer Society. All rights reserved. Reprinted with permission.

Поделитесь материалом с коллегами и друзьями

Купить номер с этой статьей в PDF