Обфускация баз данных

Обфускация баз данных

Алексей Миловидов

ClickHouse не тормозит?

ClickHouse работает быстро.

Это известный факт.

Все и так знают.

Как мы можем быть в этом уверены?

Нужны тесты производительности.

Мы добавили первые автоматизированные тесты в 2013 году.

За основу взят набор данных Яндекс.Метрики из 1 млрд просмотров страниц.

Запросы — те, которые предполагалось выполнять из интерфейса Яндекс.Метрики.

Добавили сравнение с другими системами: Vertica, MonetDB.

Часть функциональных тестов использует тот же набор данных.

Тесты на закрытых данных

В 2013 году ClickHouse только начинал использоваться внутри Яндекса.

В 2016 году ClickHouse стал open-source
и закрытые тесты стали серьёзной проблемой.

Тесты на закрытых данных

Тесты производительности невоспроизводимы снаружи
— для их запуска нужны закрытые данные, которые невозможно опубликовать.

Часть функциональных тестов также недоступна снаружи.

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

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

Решения

Выкинуть старые тесты?

— известные бенчмарки:
TPC-H, TPC-DS, Star Schema Benchmark, AMPLab Big Data Benchmark;

— открытые наборы данных:
Transportation Statistics "Ontime" data; NYC Taxi rides;

Но:

— нужно проверять регрессии производительности на наших запросах;
— нужно сохранить имеющиеся функциональные тесты;
— переписывать тесты — слишком затратно.

 

Производительность важно тестировать
на настоящих данных с продакшна!

Важны настоящие данные

Пример: если генерировать тестовые данные равномерно-случайно,
то данные не будут сжиматься.

Но сжатие данных — это важнейшая характеристика для аналитических СУБД.

Сжатие данных — это всегда компромисс между скоростью работы и коэффициентом сжатия, в котором нет единственно правильного решения.

Если не учитывать сжатие данных при тестировании производительности, то результаты не имеют смысла.

https://yandex.github.io/clickhouse-presentations/highload_siberia_2018/

Важны настоящие данные

Вывод:

Тестовые данные должны обладать
реалистичным коэффициентом сжатия.

Важны настоящие данные

Пример:

Пусть нас интересует скорость выполнения запроса:

SELECT RegionID, uniq(UserID) AS visitors FROM test.hits GROUP BY RegionID ORDER BY visitors DESC LIMIT 10

Такой запрос — типичный для Яндекс.Метрики

Что важно для скорости работы запроса?

— какая структура данных используется для расчёта агрегатной функции uniq;

— сколько есть разных RegionID;

— сколько оперативки будет требовать каждое состояние функции uniq;

— важно знать, что количество данных для разных регионов распределено неравномерно (по степенному закону);

— а если так — то нам важно, чтобы состояния агрегатной функции uniq с маленьким количеством значений, использовали мало памяти.

Что важно для скорости работы запроса?

Если просто использовать HyperLogLog
— получим потребление фиксированного количества памяти
для каждого RegionID — ключа агрегации.

— гарантированно низкая производительность.

Важны настоящие данные

Вывод:

Тестовые данные должны репрезентовать свойства
распределения значений в данных:

— кардинальности — количество различных значений в столбцах;

— взаимные кардинальности нескольких разных столбцов;

* но эти требования слегка противоречат анонимизации.

Важны настоящие данные

Пример:

Пусть мы тестируем производительность
не аналитической СУБД, а чего-нибудь попроще:
например, хэш-таблиц.

Скорость работы хэш-таблиц зависит от баланса
между качеством и скоростью работы хэш-функции.

Важны настоящие данные

um, it's just a trivial test ...
clickhouse hashmap takes 10GB
this only takes 2
and it's 60% faster
Alexey Milovidov
This test almost doesn't make sense...
Let me share a dataset with real strings...
[ File : data.tar ]
clickhouse hashmap is faster
from 2 times to 5 times

Задача

Получить данные для тестирования производительности.

Такой же структуры, как закрытые данные.

Анонимизированные, пригодные к публикации наружу.

Но с сохранением важных для тестирования свойств:

— коэффициентов сжатия;
— кардинальностей значений;
— свойств вероятностных распределений.

Задача-максимум

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

Чтобы мы отлаживали и тестировали производительность
на чужих данных, аналогичных продакшну.

И ещё: на анонимизированные данные
должно быть всё ещё интересно смотреть.

Попытки решения

Явные вероятностные модели

Wikipedia, public domain (2008)

Явные вероятностные модели

«На глаз» для каждого столбца выбрать
семейство вероятностных распределений.

По статистике оценить параметры распределения из этого семейства.

С помощью полученного распределения генерировать новые данные.

Явные вероятностные модели

Результат — скрипт на C++:

EventTime.day(std::discrete_distribution<>({ 0, 0, 13, 30, 0, 14, 42, 5, 6, 31, 17, 0, 0, 0, 0, 23, 10, ...})(random)); EventTime.hour(std::discrete_distribution<>({ 13, 7, 4, 3, 2, 3, 4, 6, 10, 16, 20, 23, 24, 23, 18, 19, 19, ...})(random)); EventTime.minute(std::uniform_int_distribution<UInt8>(0, 59)(random)); EventTime.second(std::uniform_int_distribution<UInt8>(0, 59)(random)); UInt64 UserID = hash(4, powerLaw(5000, 1.1)); UserID = UserID / 10000000000ULL * 10000000000ULL + static_cast<time_t>(EventTime) + UserID % 1000000; random_with_seed.seed(powerLaw(5000, 1.1)); auto get_random_with_seed = [&]{ return random_with_seed(); };

Явные вероятностные модели

Эвристики:

Для сохранения непрерывности временных рядов, моделируем не само значение, а разность с предыдущим.

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

Явные вероятностные модели

Достоинства:

— идейная простота;

Недостатки:

— трудоёмкость реализации;
— реализованное решение заточено для одного вида данных.

Таблица "hits" — более 100 столбцов по состоянию на 2013 год.
Для всех из них надо подобрать модель :(

Явные вероятностные модели

Модели можно подбирать автоматически
— best fit из набора моделей + регуляризация.

Зависимости между данными тоже можно искать автоматически
— считать relative entropy между каждой парой столбцов.

Всё равно слишком трудоёмко.

Нейронные сети

https://thiscatdoesnotexist.com/ (2019)

Нейронные сети

«The Unreasonable Effectiveness of Recurrent Neural Networks»

http://karpathy.github.io/2015/05/21/rnn-effectiveness/

Задачу взял случайный человек «с улицы»
— студент ВШЭ в качестве своего диплома.

(Для получения набора тестовых данных, подписано NDA).

Нейронные сети

Требуется генерировать структурированные данные, а не просто текст.

Два способа:

Можно оставить стуктуру данных фиксированной,
и генерировать только значения — «наполнители».
Но для этого надо адаптировать код.

Можно генерировать текстовый дамп. В нём будут невалидные строки, но их можно просто пропускать при загрузке.

Нейронные сети

Качество данных на первый взгляд Ок:

Шариф Ринатович Анвардинов, 2018

Нейронные сети (не работают)

Скорость генерации — примерно 100 строк в секунду
на одной машине с CPU.

— Не успеем сгенерировать дата-сет из 1 млрд строк
до защиты диплома.

Размер модели — около гигабайта
(после обучения на наборе данных в несколько гигабайт)

— Анонимизация данных становится под вопросом.

Сжатие нейронной сети и ускорение inference
— должно быть возможно, но никто ничего не сделал.

Нейронные сети

Решение полностью непрактично
...по крайней мере сейчас.

Человек защитил диплом с отличной оценкой :)

Код выкинули и больше не использовали.

Мутация сжатых данных

Мутация сжатых данных

Нужно сгенерировать данные

—у которых коэффициенты сжатия будут
точно такие же, как у исходных данных;

—и чтобы данные разжимались с точно такой же скоростью.

Как это сделать?

Мутация сжатых данных

Нужно редактировать байты сжатых данных напрямую!

Тогда размер сжатых данных не поменяется,
а сами данные поменяются.

Да ещё и всё быстро работать будет.

Мутация сжатых данных

Допустим, нас интересует только LZ4.

Данные, сжатые с помощью LZ4, состоят из команд двух видов:
— скопировать следующие N байт как есть (называется "literals");
— повторить N байт, которые были в файле на расстоянии M (называется "match", минимальная длина повторения равна 4).

В сжатом файле будем оставлять match как есть,
а в literals менять значения байтов.

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

Мутация сжатых данных

URL:

http://ljc.she/kdoqdqwpgafe/klwlpm&qw=962788775I0E7bs7OXeAyAx http://ljc.she/kdoqdqwdffhant.am/wcpoyodjit/cbytjgeoocvdtclac http://ljc.she/kdoqdqwpgafe/klwlpm&qw=962788775I0E7bs7OXe http://ljc.she/kdoqdqwdffhant.am/wcpoyodjit/cbytjgeoocvdtclac http://ljc.she/kdoqdqwdbknvj.s/hmqhpsavon.yf#aortxqdvjja http://ljc.she/kdoqdqw-bknvj.s/hmqhpsavon.yf#aortxqdvjja http://ljc.she/kdoqdqwpdtu-Unu-Rjanjna-bbcohu_qxht http://ljc.she/kdoqdqw-bknvj.s/hmqhpsavon.yf#aortxqdvjja http://ljc.she/kdoqdqwpdtu-Unu-Rjanjna-bbcohu_qxht http://ljc.she/kdoqdqw-bknvj.s/hmqhpsavon.yf#aortxqdvjja http://ljc.she/kdoqdqwpdtu-Unu-Rjanjna-bbcohu-702130

Мутация сжатых данных

Недостатки:

— не сохраняются зависимости между столбцами;

— в разных сжатых блоках данные преобразуются по-разному;

— данные недостаточно анонимизируются.

Случайные перестановки

и не только

Случайные перестановки

http://fabiensanglard.net/fizzlefade/

Wolfenstein 3D, Id Software, 1992; Fabien Sanglard, 2017

Случайные перестановки

Взаимнооднозначное преобразование множества значений,
которое выглядит случайным.

Пример: Linear-Feedback Shift Register

Wikipedia (KCAuXy4p - Own work), CC0, 2017

Случайные перестановки

Может быть составлено из более простых
взаимнооднозначных преобразований.

Примеры:

— умножение на нечётное число с переполнением;
— xor-shift: x ^= x >> N;
— CRC-N, где N — число бит аргумента;

https://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/

Feistel Network

http://antirez.com/news/113

Wikipedia (Amirki derivative work), CC BY-SA 3.0, 2011

Feistel Network (один раунд)

1. Биты аргумента разделяются на две половинки:

arg: xxxxyyyy arg_l: xxxx arg_r: yyyy

2. На место левой половинки ставится правая. А на место правой ставится xor от левой половинки и F(правой половинки):

res: yyyyzzzz res_l = yyyy = arg_r res_r = zzzz = arg_l ^ F(arg_r)

Это преобразование обратимо:
мы можем вычислить F(res_l) ^ res_r и получить arg_l.

Случайные перестановки

Будем использовать случайные перестановки
для преобразования числовых столбцов.

— полностью сохраняются кардинальности;

— полностью сохраняются взаимные кардинальности;

— повторяющиеся значения продолжают повторяться
на таком же расстоянии друг от друга;

Будем также сохранять порядок величин.

— перестановки в пределах одного size class.

Марковские модели

https://yandex.ru/referats/

Order-N марковская модель
— определяет вероятность следующего символа по N предыдущим.

P(мама | мам) = 0.9 P(мамб | мам) = 0.05 P(мамв | мам) = 0.01 ...

За счёт маленькой памяти генерируют смешные, бредовые тексты.

Зато работают быстро :)

Марковские модели

Title:

Модная Пышки — Информер.Ру - национальное ДТП в экспресс фиксика

призы, пробки в Новостинг. Триалы онлайн ногтях, но не пировод, электрошка кадры со скидкой или - Яндекс.Афиша@Mail.Ru - модные знакомств - интернет-магазин СТРИТБОЛКУ в интернет авто. Одесса) - AUTO.ria.ua Базар автомагнитомник фильмы онлайн бесплатно и видео

Марковские модели

Сохранение повторяющихся значений:

Генератор случайных чисел будем инициализировать
хэш-функцией исходного значения.

Одинаковые значения преобразуются в одинаковые.

Марковские модели

Сохранение повторяющихся фрагментов значений.

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

https://www.yandex.ru/images/cats/?id=12345 https://www.yandex.ru/images/cats/?id=67890 -> http://ftp.edu.co/cgi-bin/index.phtml#hello http://ftp.edu.co/cgi-bin/index.phtml#world

Марковские модели

Сохранение повторяющихся фрагментов значений.

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

https://www.yandex.ru/images/cats/?id=12345 ^^^^^^^^ distribution: [aaaa][b][cc][dddd][e][ff][ggggg][h]... hash("images/c") % total_count: ^ http://ftp.google.kz/cg...

Марковские модели

Проградар-детей беременны отправления или Дачна Невестика и МО | Холодеи. - Плакаты пустить в Аксессуаро Проградар-детей бережье — Яндекс.Деньги: Оплатного журнал пять велосипеды на Lore - dfghf — я.ру - недвижимость в Москва) по 473682 объявленов - Продаже Компром Проградар-детей бесплатно! в большом ассоте»в Москве - Вышивку — Омский Оплатно в Самые босоножка рост Проградар-детей бесплатно! в большом ассоте»в Москве, странспортал Проградар-детей бердянский Модов. Рецепт c фотогалерея и прикрыло громной футбола Московье@Mail.Ru - Поиск Проградар-детей бережнева продажа Смотрите лучшей цене, сообществе 2010 | Проектиролабор СНОВНЫЕ. Доста Проградар-детей бесплатно! в большом ассотруди Цена: 820 0000 км., Таганде квартиры в Санкт-Пет Проградар-детей бережный месяцам - DoramaTv.ru - Платья повсему мире. Интернет-продажа авто б.у. и на со скидкой Проградар-детей беремховой комн. в 2013 год, болисменной подержанны в Ставропавлины и коляски ->  Магнитаз 80 сотовим.РУ Проградар-детей бережена - Официальный форумы Калинин (Украины. Авториа Бакслера Кудрявцева поставка, вакансионны, продаже отеля Проградар-детей беременность подробная д. 5, 69, общения W*ойчивом - Яндекс.Карты, дома, какой цены эвакуатор форум игры World of Tanks Проградар-детей берец, отечестве и в розовый стр. 2 из кабинет поиск по доровье@Mail.Ru Проградар-детей беремени програда в Китая верты Баре, попогода Манику. Записи в Смоленское

Результат

Результат

— собрал всё вместе в утилиту clickhouse-obfuscator;

— устанавливается в пакете с clickhouse-client;

— внутри — случайные перестановки и марковские модели;

— работает детерминированно, результат параметризован ключом;

— подходит для любых табличных данных;

— не зависит от ClickHouse — можно применять для данных любой БД;

— работает быстро: на данных из ~ 100 столбцов
~ 10 000 строк в секунду на одном ядре;

Результат

clickhouse-obfuscator \ --seed "$(head -c16 /dev/urandom | base64)" \ --input-format TSV --output-format TSV \ --structure 'CounterID UInt32, URLDomain String, \ URL String, SearchPhrase String, Title String' \ < table.tsv > result.tsv clickhouse-obfuscator --help

Результат

Данные для функциональных тестов опубликованы:

https://clickhouse-datasets.s3.yandex.net/hits/tsv/hits_v1.tsv.xz
https://clickhouse-datasets.s3.yandex.net/visits/tsv/visits_v1.tsv.xz

https://clickhouse.yandex/docs/ru/getting_started/example_datasets/metrica/

Не всё так однозначно, но публикация этих данных одобрена.

Внешние разработчики используют эти данные
для настоящих тестов производительности.

.