Программа курса Урок 53 из 156 · Измеряйте приватность честно
Измеряйте приватность честно

Множества анонимности и энтропия

Почему это важно Заголовки говорят что-то вроде "ваш браузер уникален" или "этот признак даёт 10 бит". Этот урок показывает, как измеряют такие числа, и две ловушки, из-за которых многие из них больше правды. Тогда вы сможете судить об утверждениях о приватности, включая свои собственные.

Прятаться в толпе

Представьте вокзал, полный пассажиров в одинаковых чёрных пальто. Если вы тоже в чёрном пальто, вы прячетесь среди сотен. Если в ярко-жёлтом, толпа, в которой вы прячетесь, - это только вы.

Множество анонимности: группа людей, которые для наблюдателя выглядят точно как вы. Чем она больше, тем лучше вы прячетесь. Множество размера 1 значит, что вы уникальны.

В уроке 50 вы измеряли, насколько один человек, Сэм, выделялся в толпе. Здесь вы измеряете всю толпу из 5000 синтетических браузеров (их создаёт synthetic_browsers, никаких реальных людей), чтобы увидеть, насколько хорошо прячется каждый.

Сгруппируйте, затем посчитайте

Выберите несколько признаков, скажем ["timezone", "language"]. Отпечаток каждого браузера - кортеж этих значений, например ("Europe/London", "en-GB"). Кортеж работает как ключ словаря, поэтому collections.Counter может посчитать, сколько браузеров делят каждый:

from collections import Counter
Counter([("A", "x"), ("A", "x"), ("B", "x")])
# Counter({('A', 'x'): 2, ('B', 'x'): 1})

Каждый подсчёт - множество анонимности. Подсчёт 1 - уникальный браузер. Со всеми 13 признаками большинство из 5000 браузеров оказываются уникальными.

Энтропия: одно число для всей толпы

В уроке 48 вы использовали энтропию Шеннона, чтобы измерить, насколько перемешаны символы текста. Та же формула работает и на толпе: для каждого множества анонимности возьмите его долю p от всех и сложите -p * log2(p).

Энтропия (отпечатка): среднее число бит, которое трекер узнаёт о случайном посетителе по этим признакам. 0 бит: все выглядят одинаково. log2(N) бит: каждый в толпе из N уникален.

Пример: четыре браузера с часовыми поясами A, A, B, C. Доли - 1/2, 1/4 и 1/4, поэтому энтропия равна 0.5 × 1 + 0.25 × 2 + 0.25 × 2 = 1.5 бита.

Ловушка 1: потолок

Толпа из 5000 никогда не может показать больше log2(5000), около 12.3 бита, потому что в этот момент все уже уникальны. Поэтому исследование 5000 браузеров, которое находит "12 бит", может упираться в потолок, а не измерять признак. И уникальность среди 5000 - не уникальность среди миллиардов. Большие выборки дают большие и более честные числа.

Ловушка 2: складывать признаки

Часовой пояс и язык ходят вместе: большинство браузеров с Asia/Tokyo говорят ja-JP. Видеокарта и система тоже. Поэтому сложение энтропии каждого признака по отдельности считает одну и ту же информацию несколько раз. Ваш sum_of_parts окажется намного выше joint, энтропии всех признаков, измеренных вместе, и намного выше потолка в 12.3 бита. Честное число - совместное.

Распространённое заблуждение

"Высокая энтропия значит, что каждого можно отследить." Энтропия - среднее. У толпы может быть высокая энтропия, и при этом большая группа людей с очень распространёнными настройками по-прежнему хорошо прячется. Смотрите и на среднее, и на то, сколько людей находятся в маленьких множествах.

Попробуйте Когда пройдёте, выведите entropy_bits(crowd, [t]) для каждого признака (решение это делает). Какие три признака несут больше всего бит? Затем сравните значения этих признаков в своём браузере с сайтом-тестом отпечатков, например Cover Your Tracks от EFF.

На других языках

JavaScript:

function entropyBits(rows, traits) {
  const counts = new Map();
  for (const r of rows) {
    const key = JSON.stringify(traits.map(t => r[t]));
    counts.set(key, (counts.get(key) || 0) + 1);
  }
  let bits = 0;
  for (const c of counts.values()) {
    const p = c / rows.length;
    bits -= p * Math.log2(p);
  }
  return bits;
}

Go:

func entropyBits(keys []string) float64 {
    counts := map[string]int{}
    for _, k := range keys {
        counts[k]++
    }
    bits := 0.0
    for _, c := range counts {
        p := float64(c) / float64(len(keys))
        bits -= p * math.Log2(p)
    }
    return bits
}

Итоги

  • Множество анонимности - все, кто выглядит точно как вы; размер 1 значит уникальность.
  • Энтропия - среднее число бит, узнаваемых о посетителе: сгруппируйте, посчитайте, затем сложите -p log2(p).
  • Ни одна выборка из N не может показать больше log2(N) бит; маленькие выборки занижают толпу.
  • Измеряйте признаки вместе: сложение их по одному дважды считает связанные признаки.
Твоя очередь

Напишите fingerprint(row, traits) (кортеж значений), anonymity_sets(rows, traits) (словарь от отпечатка к числу), fraction_unique(rows, traits) (доля строк в множестве размера 1), entropy_bits(rows, traits) (энтропия Шеннона по множествам анонимности) и max_bits(n) (log2(n)). Затем задайте joint как энтропию crowd по всем TRAIT_NAMES, а sum_of_parts - как сумму энтропий каждого отдельного признака.

Заметили проблему в этом уроке? Сообщите о ней · Спросить об этом уроке

Это упражнение откроется скоро

Закончи предыдущий урок, чтобы открылся этот. Весь курс бесплатный, аккаунт не нужен, и ты можешь прочитать этот урок прямо сейчас.