private_heavy_hitters.ipynb

Kernel: Python 3

Copyright 2022 The TensorFlow Authors.

#@title Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

Heavy hitters privados

Ver em TensorFlow.org

Executar no Google Colab

Ver fonte no GitHub

Baixar notebook

OBSERVAÇÃO: foi verificado que este Colab funciona com a versão mais recente lançada do pacote pip tensorflow_federated. Talvez não seja possível atualizar este Colab para funcionar no main.

Este tutorial mostra como usar a API tff.analytics.heavy_hitters.iblt.build_iblt_computation para construir uma computação analítica federada para descobrir as strings mais frequentes (heavy hitters privados) na população.

Configuração do ambiente

Execute o código abaixo para que o ambiente seja configurado corretamente. Se não for exibida uma saudação, consulte as instruções de instalação.

#@test {"skip": true}

# tensorflow_federated_nightly also bring in tf_nightly, which
# can causes a duplicate tensorboard install, leading to errors.
!pip install --quiet tensorflow-text-nightly
!pip install --quiet --upgrade tensorflow-federated

import collections

import numpy as np
import tensorflow as tf
import tensorflow_federated as tff
import tensorflow_text as tf_text

np.random.seed(0)
tff.backends.test.set_sync_test_cpp_execution_context()

tff.federated_computation(lambda: 'Hello, World!')()

b'Hello, World!'

Histórico – Heavy hitters privados em análise federada

Considere o seguinte cenário: cada cliente tem uma lista de strings, e cada string é de um conjunto aberto, ou seja, pode ser arbitrário. O objetivo é descobrir as strings mais populares (heavy hitters) e suas contagens de forma privada em um ambiente federado. Este Colab demonstra uma solução para esse problema com as seguintes propriedades de privacidade:

• Agregação segura – Computa as contagens agregadas de strings de tal forma que não deve ser possível para o servidor aprender um valor individual de qualquer cliente. Confira mais informações em tff.federated_secure_sum.

• Privacidade diferencial (DP, na sigla em inglês) – Método amplamente usado para limitação e quantificação do vazamento de dados confidenciais em análises. Você pode aplicar a privacidade diferencial central em nível de usuário aos resultados de heavy hitter.

A API de agregação segura tff.federated_secure_sum tem suporte a somas lineares de vetores de inteiros. Se as strings forem de um conjunto fechado de tamanho n, então é fácil codificar as strings de cada cliente em um vetor de tamanho n – seja o valor no índice i do vetor a contagem da i^ésima string no conjunto fechado; então, é possível somar de forma segura os vetores de todos os clientes para obter as contagens de strings de toda a população. Entretanto, se as strings forem de um conjunto aberto, não é óbvio como codificá-los adequadamente para fazer a soma segura. Neste trabalho, você pode codificar as strings em Invertible Bloom Lookup Tables (IBLT), que são uma estrutura de dados probabilística que tem a capacidade de codificar itens em um domínio grande (ou aberto) de maneira eficiente. Os sketches de IBLT podem ser somados linearmente, então são compatíveis com a soma segura.

Você pode usar tff.analytics.heavy_hitters.iblt.build_iblt_computation para criar uma computação do TFF que codifique as strings locais de cada cliente em uma estrutura de IBLT. Essas estruturas são somadas de forma segura por meio de um protocolo de computação seguro criptográfico multiparte em uma estrutura de IBLT agregada que o servidor pode decodificar. O servidor pode então retornar os principais heavy hitters. As próximas seções mostram como usar essa API para criar uma computação do TFF e executar simulações com o dataset Shakespeare.

Carregue e pré-processe os dados de Shakespeare federados

O dataset Shakespeare contém falas de personagens das peças de Shakespeare. Neste exemplo, um subconjunto de personagens (isto é, clientes) são selecionados. Um pré-processador converte as falas de cada personagem em uma lista de strings, e qualquer string que é apenas um sinal de pontuação ou símbolos é descartada.

# Load the simulation data.
source, _ = tff.simulation.datasets.shakespeare.load_data()

# Preprocessing function to tokenize a line into words.
def tokenize(ds):
  """Tokenizes a line into words with alphanum characters."""
  def extract_strings(example):
    return tf.expand_dims(example['snippets'], 0)

  def tokenize_line(line):
    return tf.data.Dataset.from_tensor_slices(tokenizer.tokenize(line)[0])

  def mask_all_symbolic_words(word):
    return tf.math.logical_not(
        tf_text.wordshape(word, tf_text.WordShape.IS_PUNCT_OR_SYMBOL))

  tokenizer = tf_text.WhitespaceTokenizer()
  ds = ds.map(extract_strings)
  ds = ds.flat_map(tokenize_line)
  ds = ds.map(tf_text.case_fold_utf8)
  ds = ds.filter(mask_all_symbolic_words)
  return ds

batch_size = 5

def client_data(n: int) -> tf.data.Dataset:
  return tokenize(source.create_tf_dataset_for_client(
      source.client_ids[n])).batch(batch_size)

# Pick a subset of client devices to participate in the computation.
dataset = [client_data(n) for n in range(10)]

Simulações

Para executar simulações a fim de descobrir as palavras mais populares (heavy hitters) no dataset Shakespeare, primeiro você precisa criar uma computação do TFF usando a API tff.analytics.heavy_hitters.iblt.build_iblt_computation com os seguintes parâmetros:

• capacity: capacidade do sketch de IBLT. Este número deve ser aproximadamente o número total de strings únicas que podem aparecer em uma rodada de computação. O padrão é 1000. Se esse número for pequeno demais, poderá haver falha na codificação devido à colisão de valores em hash. Se for grande demais, o consumo de memória poderá ser maior do que o necessário.

• string_max_bytes: tamanho máximo de uma string na IBLT. O padrão é 10. Precisa ser positivo. Strings maiores do que string_max_bytes serão truncadas.

• max_words_per_user: número máximo de strings que cada cliente pode fornecer. Se não for igual a None, deve ser um inteiro positivo. O padrão é None, ou seja, todos os clientes fornecem todas as suas strings.

• max_heavy_hitters: número máximo de itens a retornar. Se os resultados decodificados tiverem mais do que esse número de itens, a lista será ordenada de forma decrescente pelas contagens estimadas, e serão retornados os primeiros max_heavy_hitters itens. O padrão é None, ou seja, todos os heavy hitters são retornados no resultado.

• secure_sum_bitwidth: comprimento de bits usado para a soma segura. O valor padrão é None, que desativa a soma segura. Se não for None, precisa estar no intervalo [1,62]. Confira tff.federated_secure_sum.

• multi_contribution: define se cada cliente pode fornecer diversas contagens ou somente uma para cada palavra única. O padrão é True. Esse argumento pode melhorar a utilidade quando for necessário ter privacidade diferencial.

• batch_size: número de elementos em cada lote do dataset. O padrão é 1, ou seja, o dataset de entrada é processado por tf.data.Dataset.batch(1). Deve ser um inteiro positivo.

max_words_per_user = 8
iblt_computation = tff.analytics.heavy_hitters.iblt.build_iblt_computation(
    capacity=100,
    string_max_bytes=20,
    max_words_per_user=max_words_per_user,
    max_heavy_hitters=10,
    secure_sum_bitwidth=32,
    multi_contribution=False,
    batch_size=batch_size)

Agora está tudo pronto para executar simulações com computação do TFF iblt_computation e o dataset de entrada pré-processado. A saída iblt_computation tem quatro atributos:

• clients: número escalar de clientes que participaram da computação.

• heavy_hitters: lista de heavy hitters agregados.

• heavy_hitters_counts: lista das contagens de heavy hitters agregados.

• num_not_decoded: número escalar de strings que não são decodificadas com êxito.

def run_simulation(one_round_computation: tff.Computation, dataset):
  output = one_round_computation(dataset)
  heavy_hitters = output.heavy_hitters
  heavy_hitters_counts = output.heavy_hitters_counts
  heavy_hitters = [word.decode('utf-8', 'ignore') for word in heavy_hitters]

  results = {}
  for index in range(len(heavy_hitters)):
    results[heavy_hitters[index]] = heavy_hitters_counts[index]
  return output.clients, dict(results)

clients, result = run_simulation(iblt_computation, dataset)
print(f'Number of clients participated: {clients}')
print('Discovered heavy hitters and counts:')
print(result)

Number of clients participated: 10
Discovered heavy hitters and counts:
{'to': 8, 'the': 8, 'and': 7, 'you': 4, 'i': 4, 'a': 3, 'he': 3, 'your': 3, 'is': 3, 'of': 2}

Heavy hitters privados com privacidade diferencial

Para obter heavy hitters privados com privacidade diferencial central, um mecanismo de privacidade diferencial é aplicado nos histogramas de datasets abertos. A ideia é adicionar ruído às contagens de strings no histograma agregado e apenas manter as strings com contagens acima de um determinado limiar. O ruído e o limiar dependem do budget (epsilon, delta)-DP (confira os detalhes do algoritmo e da prova neste documento). As contagens de ruído são arredondadas para inteiros como uma etapa de pré-processamento, o que não enfraquece a garantia de privacidade diferencial. Você descobrirá menos heavy hitters quando for necessário ter privacidade diferencial, pois a etapa de limiar filtra strings com baixas contagens.

iblt_computation = tff.analytics.heavy_hitters.iblt.build_iblt_computation(
    capacity=100,
    string_max_bytes=20,
    max_words_per_user=max_words_per_user,
    secure_sum_bitwidth=32,
    multi_contribution=False,
    batch_size=batch_size)

clients, result = run_simulation(iblt_computation, dataset)

# DP parameters
eps = 20
delta = 0.01

# Calculating scale for Laplace noise
scale = max_words_per_user / eps

# Calculating the threshold
tau = 1 + (max_words_per_user / eps) * np.log(max_words_per_user / (2 * delta))

result_with_dp = {}
for word in result:
  noised_count = result[word] + np.random.laplace(scale=scale)
  if noised_count >= tau:
    result_with_dp[word] = int(noised_count)
print(f'Discovered heavy hitters and counts with central DP:')
print(result_with_dp)

Discovered heavy hitters and counts with central DP:
{'the': 8, 'you': 4, 'to': 7, 'tear': 3, 'and': 7, 'i': 3}