Вход
Регистрация
Тема закрыта
Часть 1: Технические подробности
Часть 2: Рынок материалов
Часть 3: Рынок Т2
Часть 4: Преступление и наказание
Часть 1. Технические подробности
"Война порождает воров, а мир их убивает."
CCP Lilith
"Война порождает воров, а мир их убивает." - George Herbert
Игрокам приходится преодолевать множество трудностей и заниматься сложным планированием, чтобы победить в масштабных войнах EVE. Некоторые заходят слишком далеко и, в конце концов, платят за это исключением из игры. Так произошло и в истории с недавним багом, связанным с POS. Хотя его использовало относительно небольшое количество игроков, масштабы эксплуатации были промышленными.
Уязвимость была тщательно расследована как с технической перспективы, так и с точки зрения того, как она повлияла на экономику EVE Online. Мы исследовали абсолютно всё для того, чтобы понять как эта проблема возникла в нашем коде и почему её не обнаружили раньше, и извлекли из этого уроки, которые помогут нам предотвратить подобное в будущем.
Мы также абсолютно уверены, что вы, пилоты EVE, должны тоже узнать результаты, так что мы решили предоставить детальную информацию о проблеме с реакторами, известную также как "the POS exploit".
Предварительные результаты расследования были представлены в CSM в середине января. Члены CSM дали о них положительные отзывы и помогли нам уточнить некоторые детали и формулировки.
Как вы увидите в последующем отчете, подобная работа требует сотрудничества между многими отделами внутри CCP. Команда программистов представлена CCP Pleognost, который рассказал о коде, истории возникновения бага и что мы сделали для его исправления. CCP Diagoras и CCP DrEyjoG провели экономическои исследование и оценили общее воздействие уязвимости на экономику EVE, а CCP Grimmi описал действия, которые мы предприняли против тем, кто использовал баг для собственного обогащения. Многие другие были вовлечены в различные стадии расследования, и мы хотим поблагодарить их за их вклад.
Отчет получился довольно большой, но мы надеемся, что вы найдёте время прочесть его и высказать своё мнение в соответствующем обсуждении на форуме.
POSы: как они должны работать, и что происходило на самом деле.
CCP Pleognost
Понять причину появления уязвимости с технической точки зрения не так уж трудно. Проблема в том, что вам для этого нужно знать, что происходит внутри игры.
В нашем случае мы рассматриваем три игровых объекта: контрольные башни (POS Control Towers), силосы (POS Silos) и реакторы (POS Reactor Arrays). С нашей точки зрения, Coupling Arrays можно считать просто маленькими силосами. Точно так же, Moon Mining Arrays представляют собой просто простые реакторы - они просто выдают постоянный поток "бесплатных" веществ, и при этом ничего не потребляют.
Чем занимаются структуры ПОСов
Основние значение имеет то, как связаны эти объекты.
Контрольные башни - это большие начальники ПОСов, состоящие из полукилометровой простыни кода, которые занимается всем, начиная от определения момента включение реинфорса, до посылки надоедливых сообщений вашим противникам в тот момент, когда башня устанавливается в захваченном (claimed) космосе. Интересующий нас элемент - система управления производством, достаточно большой кусок гигантского файла, описывающего поведение башни.
Удобно думать о контрольной башне как о начальнике завода, который контролирует абсолютно всё; он говорит рабочим, когда им надо работать, и очень придирчив к порядку выполнения работ.
Силосы - это, попросту говоря, огромные склады в космосе. Они умеют хранить всякие штуки - и это их единственное занятие. Отметим, что мы добавили кое-какие ограничения. Силос может хранить только один вид товара, и, более того, этот товар может храниться только в одной куче (stack). Размер этой кучи кэшируется, так что мы можем работать с этим значением во время обработки производства, не обращаясь к базе данных.
Это хорошо, потому что лаги при обращении в базе данных - отстой. (Мы еще не раз вернёмся к теме "Лаги - отстой" позже).
Реакторы - сложные устройства, но не до такой степени, как контрольные башни. Если не углубляться в подробности, всё кажется простым; реакторы получают материалы из силосов, преобразуют их в более ценные материалы в соответствии с чертежами реакций, лежащими в них, и надеются, что полученные материалы кто-нибудь заберёт до того момента, как надо будет произвести что-нибудь ещё.
На самом деле, мы не делаем все эти манипуляции. Перемещение материалов с места на место - дорогая операция, так как она использует систему, которая следит за местонахождением всех вещей в EVE. Чрезмерное использование этой системы приводит к тому, что она отнимает бесценные ресурсы процессора и базы данных у всего остального в EVE. По возможности, мы должны избегать этого.
Как всё работает
Предположим, что у нас есть простой ПОС с простой реакцией: силоc A содержит ресурс A, силом B содержит ресурс B. Реактор X потребляет ресурс A и производит ресурс B.
Обратите внимание на последовательность действий вверху картинку: реактор проводит большую часть времени пустым; внутри него что-то находится только когда реактор ожидает, чтобы силос B забрал результат реакции. Нам не нужно следить за кучами ресурсов внутри реактора; достаточно знать, есть ли достаточно ресурса A для реакции, выдающей единицу ресурса B. После этого мы можем оповестить силос B, что он может добавить единицу ресурса B. Фактически, мы это и делаем.
Еще пара хитрых приемов
Перед тем, как мы перейдем к самой проблеме, вы должны узнать еще две вещи. Обе связаны с контрольными башнями.
Во первых, реакции состоят из двух больших фаз. В первой фазе мы проверяем, что цепочка может работать в её текущем состоянии: реакторы имеют доступ к ресурсам и могут/должны их потреблять. На этой фазе - если всё прошло хорошо - реакторы забирают ресурсы. Кроме этого, они устанавливают маленький внутренний флажок, напоминающий о том, что они еще не выдали результат в этом производственном цикле.
Во второй фазе мы фактически производим материалы - т.е. силосы забирают результаты из Moon Mining Arrays, других силосов и реакторов. В конце этой фазы мы сохраняем состояние ПОСа на тот случай, если что-то Плохое (например, даунтайм) случится перед следующим циклом производства.
Наконец, так как предполагается, что реакторы весь цикл "трудятся над производством", необходимо сделать еще кое-что. В самом начале первой фазы, они сохраняют текущее значение флажка, которого говорит нам о том, что они занимались произодством в предыдущем цикле. Если флаг был установлен, то силосы могут забирать результаты. Если нет - силосы должны подождать успешного завершения цикла, которое займёт 1 час при условии, что реактор имеет доступ к сырью.
Во-вторых, вспомним, что контрольные башни управляют абсолютно всем. Они говорят силосам, когда забирать произведённые материалы из присоединённых структур, они же говорят реакторам, когда потреблять и производить материалы, основываясь на их реакциях. Если контрольная башня просто приказала материалам переместиться в случайном порядке, силос может попытаться получить материалы из ниоткуда или ректор может запуститься до того, как отработает шахта, с которой он связан. Проще говоря - возникнет хаос и структуры будут случайным образом выключаться. Мы должны быть очень точны, указывая порядок, в котором работает ПОС.
Предупреждение: математика!
Если вы настоящий спец в ПОСах, и пробовали проектировать их на бумаге, то вы могли обнаружить, что ПОСы могут быть представлены тем, что математики называют направленным ациклическим графом. У нас есть структуры (с точки зрения математики - вершины), соединённые связями (ребрами). Правильный порядок, в котором должен обрабатываться ПОС, соответствует обходу графа в ширину, что означает что мы хотим для начала посетить вершины, в которые нет входящих ребер, потом - вершины, с которыми связаны те, с которые мы только что посетили, и так далее, до тех пор, пока мы не обойдём всё. Этот алгоритм похож на алгоритм поиск в ширину, хотя и не полностью совпадает с ним - мы на самом деле ничего не ищем, и у нас может быть несколько исходных вершин.
Определение вершин, с которых надо начинать обход, главный вопрос работы с ПОСами. На самом деле, найти места "входа" относительно просто: мы проходим через список связей ПОСа и отмечаем сколько связей входит в каждую структуру. Те структуры, для которых это число будет равно нулю, должны быть посещены первыми, так как именно они будут "головой" вашей производственной цепочки.
Мы такие умные!
В EVE много ПОСов, и было бы неплохо, если бы мы могли сэкономить намного тактов процессора или базы данных, пропустив некоторые структуры. Для этого, мы рассмотрели типы объектов, которые могли стоять в начале цепочки.
Логично, что силосы и Moon Mining Arrays будут находится в начале цепочки. Обе структуры могут поставлять материалы, или из "пустоты" (Moon Mining Arrays) или из собственных запасов (силосы). Мы обрабатываем их в соответствии с алгоритмом.
Однако, реакторы.... в них ведь всегда будут входить связи, правильно, парни? Точно! Давайте сэкономим время и просто пропустим эти реакторы! Ведь если его не обрабатывать, он не запустится, правильно?
... Правильно?
Ой
Предположим, что ваш ПОС отработал несколько циклов. Реактор ровно гудит. В этом цикле он произвёл новые материалы, точно так же, как и в прошлом. Контрольная башня управляет всеми структурами в правильном порядку. Всё спокойно... пока не происходит неожиданное.
Игрок отключает все связи, ведущие к реактору.
Контрольная башня, безумная из-за этой оптимизации, несется через код обработки производства. Сначала она подходит к реактору и своими мутными газами видит, что к нему не подсоединена ни одна связь.
Она говорит:
- Мы не можем начать здесь! Это глюк!
И продолжает свой путь дальше по направлению у силосу, присоединённому к реактору.
Реактор не был обработан. Он не знает, что прошел очередной цикл и - наивный! - помнит о предыдущем нормальном цикле, позволяя присоединённому силосу добавить в кучу новый, якобы произведённый им, материал.
Халява пришла.
Последствия
После того, как мы обнаружили эту проблемы, её было легко исправить: мы стали обрабатывать реакторы даже в том случае, если в них ничего не поступало.
Вся информация о состоянии производства и связях работающих ПОСов была в базе данные. После того, как мы сделали правку, мы сляпали запрос, который пробежался по всем реакторам Транквилити, проверяя, каких из них имеют входящие связи и проверяя их состояние. Мы получили список всех включенных реакторов без входящих связей, которые "считали", что в последний цикл они что-то произвели.
Мы исследовали всё структуры, производящие товары из ничего. С помощью дополнительной информации из базы данных, мы определили, какие ресурсы создавались ими, и когда они были запущены.
Вот, в общем-то, и всё. Теперь мы должны разобраться, сколько исков было создано с помощью этой уязвимости, и как это повлияло на рынок EVE. Вперед, к экономике!
продолжение следует
Сообщение отредактировал Cptn Z: 11 February 2009 - 16:22
Наверх
