Одна из главных идей, связанных с «большими данными», заключается в том, что когда информации действительно много, она переходит в новое качество. Изучая её, можно обнаружить закономерности, которые в противном случае останутся незамеченными.
Возьмём, к примеру, поиск спама. Можно ли определить, является письмо спамом или нет, анализируя только одно письмо? Можно — например, сличая адрес отправителя с чёрным списком спамеров. Правда, этот способ работает так себе. Во-первых, он не спасёт от рассылок с адресов, которые ещё не успели попасть в чёрный список. Во-вторых, эту проверку довольно просто обмануть.
Чем больше данных, тем лучше. Статистические алгоритмы поиска спама, обучающиеся новым трюкам с каждым пойманным рекламным письмом, действуют куда эффективнее, причём чем больше база писем, с которой они работают, тем лучше. У крупных почтовых сервисов в распоряжении есть ещё один мощный метод: они замечают массовые рассылки, когда в тысячи ящиков, принадлежащие их пользователям, начинают падать одинаковые письма.
Похожую эволюцию переживают средства обнаружения вредоносного программного обеспечения. Двадцать лет назад антивирусы искали вредоносные файлы по сигнатурам — характерным фрагментам, которые содержат известные вирусы. Разработчики регулярно обновляли базы сигнатур, добавляя туда признаки новых вредоносных программ.
Со временем в арсенале антивирусов появлялись всё более замысловатые способы обнаружения вирусов. Вирусы, впрочем, тоже не стояли на месте, но что ещё хуже — они плодились всё быстрее и быстрее. Вдобавок, всё чаще встречались вредоносные программы, специально разработанные или автоматически сгенерированные для небольшого числа жертв. У них куда больше шансов ускользнуть от внимания антивирусных компаний и, соответственно, антивирусов.
Следующий шаг: замечать вирусы, сравнивая программы, которые установлены на миллионах персональных компьютеров. Если у незначительного количества пользователей вдруг появляется новый исполняемый файл, распространяемый неизвестно кем — это по меньшей мере подозрительно. Подобный метод может служить дополнительным уровнем обороны против вирусов, о которых ещё не знают антивирусные программы.
Компания Symantec, разработчик одного из наиболее популярных антивирусных пакетов в мире, изучала такую возможность с 2007 года. В период с 2007 по 2010 год она накопила десятки терабайт анонимизированных сведений о приложениях, которые устанавливают её пользователи. Специалисты из Symantec Research Labs и исследователи из университета Карнеги-Меллона несколько лет корпели над этим гигантским массивом информации.
Этот объём и сейчас неплохо укладывается в определение «больших данных», а уж три года назад — и подавно. Изучению подлежали 900 миллионов исполняемых файлов, занимающие в сумме около 60 терабайт* (это чуть больше половины всего массива, накопленного Symantec к тому времени). Файлы были переданы с 47,8 миллионов различных компьютеров.
Лишь 50 миллионов из этих файлов встречались на нескольких машинах. Остальные 850 миллионов присутствовали в единственном экземпляре. Часть из них представляла собой уникальную модификацию нормального приложения — например, скомпилированное «на лету» приложение .NET. Однако многие были редкими мутациями вредоносных программ.
Редкость — это одна из эвристик, помогающих отличить подозрительные файлы. «Приличные» приложения, как правило, встречаются на множестве компьютеров, принадлежат известному разработчику и обладают другими характерными чертами. Далеко не всякое приложение, не соответствующее этому описанию, окажется вирусом, но вероятность этого довольно высока. Есть и другие эвристики: например, очевидно, что на «грязных» компьютерах шансы встретить заражённый файл выше, чем на машине, за которой не замечено ничего странного.
Специалисты предложили построить гигантский граф, вершинами которого являются компьютеры и отдельные исполняемые файлы. Файлы будут связаны дугами с каждым компьютером, на котором они замечены. Когда есть граф, можно использовать алгоритм распространения доверия, чтобы оценить репутацию каждого файла. Если репутация недостаточно велика, система признает файл вредоносным.
Идея логично вытекала из прошлой работы исследователей из университета Карнеги-Меллона: они успешно применили аналогичный метод для того, чтобы искать мошенников, обманывающих посетителей интернет-аукционов. Тогда они использовали граф, где вершинами были продавцы и покупатели, а дугами — сделки между ними. «Компьютерра» описывала это в статье «Как анализ данных раскрывает преступные схемы»:
«Пользователи аукциона могут находиться в одном из трёх состояний: мошенник, пособник и честный пользователь. Чтобы прояснить, кто есть кто, служит алгоритм распространения доверия. Он действует так: вершины вычисляют своё состояние на основании сообщений, полученных от соседей, а затем переводят его в новые сообщения для соседей при помощи матрицы распространения. Матрица распространения — это самое важное. В ней указано, какова вероятность связи между вершинами с разными состояниями. По сути дела, получается нечто отдалённо напоминающее игру «Сапёр», где нужно угадывать клетки с бомбами по цифрам на соседних клетках.
Впрочем, чтобы добиться результата при поиске вирусов, понадобилось заметно усложнить алгоритм. Это связано с тем, что и сам граф уже не так прост, как в случае с интернет-аукционом. Вместо единственного типа вершины («пользователь интернет-аукциона») тут приходится работать с двумя — «компьютер» и «файл. Их репутацию нужно оценивать по-разному. По той же причине эвристики, описывающие влияние вершин друг на друга, не получается уложить в единственную матрицу.
Во-первых, для каждой машины рассчитывается исходная репутация. Для этого изобретена фирменная формула, учитывающая множество разнообразных факторов. Во-вторых, исходная репутация каждого файла вычисляется на основании количества компьютеров, где он встречается. Это позволяет учесть эвристику, согласно которой редкие файлы чаще бывают вредоносными. В-третьих, если файл находится в базе уже известных Symantec вредоносных файлов, его репутация выставляется в 0,01, а репутация известных незаражённых файлов — в 0,99. Наконец, для того, чтобы «хорошие» файлы повышали репутацию своих компьютеров, сообщения от них вызывают пересчёт репутации компьютера по специальной формуле.
Испытания показали, что после первой же итерации алгоритм верно вычисляет репутацию 84,9 процента файлов при всего лишь одном проценте ложных срабатываний. Правда, это верно лишь для файлов, встречающихся на четырёх компьютерах и более. Если файл встречается реже, точность резко падает. Это отчасти связано с тем, что сведения об отдельных файлах далеко не всегда точны. Когда источников информации мало, ошибки нечем компенсировать, и они начинают влиять на результат.
При сомнительности репутационной оценки из-за недостаточности информации о файле, срабатывают другие встроенные в продукт механизмы. Таким образом, комплекс технологий защиты позволяет эффективно использовать анализ больших объёмов данных, а если этого недостаточно, обеспечивать безопасность другими механизмами.
Каждая итерация несколько улучшает результат. Во время испытаний за шесть итераций точность выросла примерно на 2,2 процента. Итерации можно повторять до тех пор, пока точность не достигнет нужного уровня или не прекратит расти. Если же репутационной оценки недостаточно для принятия окончательного решения, срабатывают другие встроенные в продукт механизмы.
Интересно, что хотя в опубликованной работе исследователи отмечают возможность параллелизации вычислений при помощи Hadoop и других методов, во время испытаний использовался единственный сервер с четырьмя четырёхъядерными процессорами Opteron 8378 2,4 ГГЦ, 266 гигабайтами оперативной памяти, локальным накопителем ёмкостью один терабайт и сетевым хранилищем ёмкостью более 60 терабайт. Просчёт каждой итерации на такой машине занимал 185 минут, но она справлялась.
Исследование не пропало втуне. Технология, основанная на этом алгоритме, получила название Polonium. В августе 2010 года Symantec внедрила её. В течение следующих восьми месяцев количество данных, которые обработала компания, удвоилось.
* Polonium: Tera-Scale Graph Mining and Inference for Malware Detection. Duen Horng (Polo) Chau, Carey Nachenberg, Jeffrey Wilhelm, Adam Wright, Christos Faloutsos. Proceedings of SIAM International Conference on Data Mining (SDM) 2011.