Context-Aware Metric Differential Privacy for Vehicle Trajectory Data

Resumo Técnico: Privacidade Diferencial Métrica Consciente de Contexto para Dados de Trajetória Veicular

Declaração do Problema
A Privacidade Diferencial Métrica (mDP) generaliza a Privacidade Diferencial (DP) padrão ao permitir que garantias de privacidade sejam definidas sobre métricas de distância arbitrárias, tornando-a adequada para dados de geolocalização onde registros "vizinhos" são definidos pela proximidade espacial e não pela distância de Hamming. No entanto, os mecanismos de mDP existentes tipicamente perturbam cada registro de localização de forma isolada. Essa abordagem falha em levar em conta informações contextuais, como o histórico recente de mobilidade de um veículo, o que influencia significativamente a utilidade dos dados divulgados.

Os autores identificam uma incompatibilidade crítica: a perda de utilidade incorrida ao perturbar uma localização depende fortemente do contexto (por exemplo, direção de viagem, velocidade e localizações anteriores). Por exemplo, perturbar a localização de um veículo para um ponto específico pode resultar em perda de utilidade negligenciável se o veículo estiver se movendo em direção a um destino, mas causar perda significativa se estiver se afastando. As estruturas atuais de mDP, frequentemente formuladas como Programas Lineares (PL) para minimizar a perda esperada de utilidade, não incorporam essas dependências contextuais, levando a uma utilidade subótima em cenários do mundo real como Serviços Baseados em Localização (LBS) e crowdsourcing espacial.

Metodologia: mDP Consciente de Contexto (C-mDP)
O artigo propõe o C-mDP (Context-aware mDP), uma estrutura que integra informações contextuais tanto no modelo de utilidade quanto na definição de privacidade.

1. Formulação do Problema:

   • Segredo Aumentado: O segredo protegido é tratado como um registro aumentado por contexto $(X, V_X)$, onde $X$ é a localização atual e $V_X$ representa variáveis contextuais (por exemplo, localizações históricas).
   • Definição de Privacidade: O C-mDP impõe indistinguibilidade métrica sobre este domínio aumentado. A restrição de privacidade limita o vazamento posterior entre quaisquer dois registros aumentados vizinhos $(x_i, v)$ e $(x_j, v')$ com base em uma métrica de distância consciente de contexto $d((x_i, v), (x_j, v'))$. Essa métrica estende a distância de Haversine base incorporando distâncias ponderadas de localizações históricas.
   • Modelo de Utilidade: A perda esperada de utilidade é minimizada otimizando a distribuição de probabilidade de perturbação $q((x_i, v), y_k)$, que depende tanto da localização atual quanto do contexto.

2. Redução de Complexidade via Manta de Markov:

   • Resolver diretamente a otimização do C-mDP como um PL resulta em um número proibitivo de variáveis de decisão e restrições ($O(|X||Y||V|)$), tornando-o intratável para aplicações em larga escala.
   • Para abordar isso, os autores introduzem uma política Dependente-Condicional (CD). Eles aproveitam o conceito de Manta de Markov ($B_X$) do espaço de contexto $V_X$. A política CD restringe o mecanismo de perturbação para depender apenas da Manta de Markov do registro secreto, em vez de todo o histórico de contexto.
   • Garantias Teóricas: Os autores provam que, sob suposições específicas (onde a perda de utilidade é determinada pela distribuição a priori, distribuição de perturbação e fatores independentes de contexto, como topologia de estradas), a formulação reduzida usando apenas a Manta de Markov preserva as garantias de privacidade e alcança a perda esperada de utilidade mínima.

3. Identificação de Manta de Markov (MBI):

   • Como o tamanho da Manta de Markov varia com base em fatores como velocidade, região e tempo, o artigo propõe uma estrutura de MBI em duas etapas:
     • Descoberta: Uma fase offline usando testes de Independência Condicional (IC) em conjuntos de dados de trajetórias do mundo real para determinar o tamanho da Manta de Markov para diferentes combinações de características.
     • Previsão: Uma fase de tempo de execução usando uma Rede Neural Profunda (DNN) pré-treinada para prever o status da Manta de Markov (ou seja, se incluir ou não a próxima localização histórica) com base em características atuais (tempo, velocidade, região). Isso evita o alto custo computacional de realizar testes de IC em tempo real.

Principais Contribuições

1. Estrutura C-mDP: Introdução de uma nova estrutura de perturbação de dados que modela explicitamente o impacto das informações contextuais na perda de utilidade e na privacidade, indo além do mDP agnóstico ao contexto.
2. Otimização Eficiente: Desenvolvimento de uma formulação de PL reduzida que utiliza a Manta de Markov para diminuir significativamente o número de variáveis de decisão e restrições, mantendo garantias teóricas de privacidade e optimalidade.
3. Sistema MBI: Projeto de um sistema prático combinando testes estatísticos de IC e aprendizado profundo para identificar dinamicamente o contexto relevante (Manta de Markov) para trajetórias veiculares.
4. Validação Empírica: Avaliação abrangente usando conjuntos de dados de táxis do mundo real de Roma, Itália, e Porto, Portugal.

Resultados Experimentais
Os autores avaliaram o C-mDP contra bases de comparação de mDP padrão (PL, ExpMech, ConstOPT) e variantes (LP+TrueMB, LP+Markov) usando dois conjuntos de dados do mundo real.

• Melhoria de Utilidade: O C-mDP alcançou consistentemente maior utilidade (menor perda esperada de utilidade) sob o mesmo orçamento de privacidade ($\epsilon$). Especificamente, reduziu a perda média de utilidade dos dados em 15,6% (Roma) e 4,9% (Porto) em comparação com a melhor base de comparação de PL sem contexto.
• Comparação com Oráculos: O C-mDP proposto (usando Mantas de Markov previstas) performou quase idênticamente a uma versão oráculo (LP+TrueMB) que usa Mantas de Markov de verdade derivadas de testes de IC, com uma diferença de apenas 1–2% na perda de utilidade.
• Limitações de Modelos Fixos: Uma base de comparação assumindo um processo de Markov de primeira ordem fixo (LP+Markov) incorreu em 3–8% de perda de utilidade adicional, demonstrando que os padrões de mobilidade veicular não são estritamente de primeira ordem e dependem de fatores dinâmicos.
• Eficiência: A otimização de PL offline leva aproximadamente 8–12 segundos, e a seleção de perturbação online (amostragem) leva menos de 1,2 milissegundos, tornando a abordagem viável para aplicações de LBS em tempo real.

Significado e Alegações
O artigo afirma que o C-mDP aborda uma limitação fundamental nos mecanismos de mDP existentes: a negligência das dependências contextuais que ditam a perda de utilidade. Ao incorporar contexto na definição de privacidade e no processo de otimização, o C-mDP fornece um modelo mais preciso da utilidade dos dados em cenários de mobilidade. Os autores enfatizam que sua abordagem não enfraquece as garantias de privacidade; pelo contrário, ela apertar o trade-off utilidade-privacidade permitindo que o mecanismo atribua probabilidades de perturbação mais altas a localizações que resultam em menor perda de utilidade dependente de contexto.

O trabalho destaca que a mobilidade veicular não é uniformemente de Markov de primeira ordem; o contexto efetivo (Manta de Markov) varia significativamente com velocidade, região e tempo. Ao identificar dinamicamente esse contexto, a estrutura adapta-se aos padrões de mobilidade do mundo real, oferecendo uma solução escalável e eficaz para proteger dados de trajetória veicular em crowdsourcing espacial e serviços de navegação.