Resumo Técnico: DP4SQL - SQL Diferencialmente Privado com Políticas de Privacidade Flexíveis

Declaração do Problema

A privacidade diferencial (DP) é bem estabelecida para conjuntos de dados de tabela única, mas sua aplicação a bancos de dados relacionais permanece desafiadora devido à complexidade de definir a "denegabilidade plausível" em múltiplas relações. Os sistemas de SQL diferencialmente privados existentes sofrem de modelos de privacidade rígidos e pré-programados que não conseguem acomodar os requisitos matizados de aplicações do mundo real.

As principais limitações dos sistemas atuais incluem:

1. Políticas Inflexíveis: Eles não conseguem lidar com cenários onde diferentes tabelas ou até mesmo diferentes colunas dentro da mesma tabela exigem níveis variados de proteção (por exemplo, protegendo a existência de registros em uma tabela enquanto apenas protege valores de atributos em outra).
2. Integração de Conhecimento Público: Eles têm dificuldade em incorporar informações públicas (por exemplo, tamanhos de tabela conhecidos, valores de colunas públicas como nomes de docentes) no cálculo de privacidade. Ignorar o conhecimento público frequentemente leva à proteção excessiva (injeção de ruído excessivo) ou à proteção insuficiente (falha em mascarar a existência de registros quando o tamanho da tabela é conhecido).
3. Interações Complexas de Entidades: Os modelos existentes frequentemente falham ao lidar corretamente com chaves estrangeiras e propriedade transitiva, particularmente quando entidades interagem (por exemplo, um membro do corpo docente atribuindo notas a um estudante). Isso leva a cálculos de sensibilidade incorretos, resultando em ruído insuficiente (violações de privacidade) ou ruído excessivo (perda de utilidade).

Metodologia

O artigo propõe o DP4SQL, um sistema que desacopla a especificação da política de privacidade de alto nível do raciocínio automatizado de baixo nível. A metodologia consiste em três componentes principais:

1. Estrutura de Rotulagem de Privacidade de Alto Nível

Os administradores de dados especificam políticas usando um sistema de rotulagem simples de alto nível para cada relação no esquema. Para uma relação de entidade distinta $R^\star$ (ex: Estudantes ou Docentes), cada relação $R_i$ recebe um dos três rótulos:

• DEL (Delete/Deletar): A existência de registros é privada. Mundos contrafatuais são criados deletando registros. Isso corresponde a vizinhos ilimitados (unbounded).
• REPA (Replace/Substituir): A existência de registros é pública, mas atributos específicos $A$ são privados. Mundos contrafatuais são criados substituindo valores em $A$. Isso corresponde a vizinhos limitados (bounded).
• PUB (Public/Público): A relação inteira é pública.

Esta estrutura permite políticas mistas, como proteger a existência de estudantes (DEL) enquanto mantém nomes de docentes públicos (PUB), mas salários de docentes privados (REPA).

2. Ações de Denegabilidade Plausível de Baixo Nível

Para automatizar o raciocínio, o sistema traduz rótulos de alto nível em um conjunto de ações de denegabilidade plausível que descrevem a mudança máxima que o resultado de uma consulta pode sofrer entre bancos de dados vizinhos. As ações são:

• Add$_a$ / Del$_d$: Adicionar ou deletar $a$ ou $d$ linhas.
• Rep$^A_k$: Substituir valores de atributos $A$ em $k$ linhas.

O sistema emprega um sistema de inferência com regras de produção para derivar essas ações para consultas SQL complexas envolvendo:

• Relações Base: Regras mapeiam rótulos de privacidade para ações iniciais, considerando a propriedade máxima ($\hat{\otimes}$) derivada de restrições de chave estrangeira.
• Transformações Unárias: Regras para Seleção ($\sigma$), Projeção ($\pi$) e Agrupamento ($\gamma$) propagam ações baseadas em se os predicados ou chaves de agrupamento interceptam atributos protegidos.
• Joins (Junções): O sistema distingue entre Key Joins (junções de chave, baseadas em pares de chave primária-estrangeira) e General Joins (junções gerais). As key joins aproveitam restrições de integridade para derivar limites mais estreitos sobre mudanças de registros, evitando a sobre-aproximação comum em regras de junção geral.

3. Cálculo de Sensibilidade e Injeção de Ruído

As ações inferidas são mapeadas para um limite superior de sensibilidade global ($\hat{\Delta}$). Este limite determina a escala de ruído adicionado via mecanismo de Laplace. O sistema calcula a sensibilidade para funções agregadas (COUNT, SUM) analisando como as ações inferidas (adições, deleções, substituições) afetam o vetor de saída.

Principais Contribuições

1. Especificação de Política Flexível: Uma estrutura de rotulagem de colunas de alto nível que suporta requisitos de privacidade mistos (tamanhos de tabela públicos, colunas públicas, atributos privados) através de esquemas relacionais com chaves estrangeiras.
2. Mecanismo de Raciocínio Automatizado: Um sistema de inferência formal que traduz rótulos de alto nível em ações de denegabilidade plausível de baixo nível, raciocinando de forma sólida sobre a estabilidade de consultas de álgebra relacional (junções, agregações, subconsultas).
3. Limites de Sensibilidade Mais Estreitos: Ao modelar explicitamente o conhecimento público (ex: tamanhos de tabela conhecidos) e usar regras específicas para key-joins, o DP4SQL deriva limites de sensibilidade mais estreitos do que os sistemas existentes, que frequentemente assumem cenários de pior caso para todos os atributos.
4. Implementação e Validação: O sistema é implementado como um middleware de banco de dados (DP4SQL) que intercepta consultas SQL, computa o ruído necessário e retorna respostas diferencialmente privadas.

Resultados

O artigo avalia o DP4SQL usando um estudo de caso de esquema universitário e o benchmark TPC-H, comparando-o com políticas de linha de base (vizinhos puramente ilimitados e puramente limitados) e o sistema Tumult Analytics (baseado no PrivateSQL).

• Corretude de Privacidade (Subproteção): Em cenários onde os tamanhos das tabelas são públicos (ex: o número de pedidos no TPC-H), modelos de vizinhos ilimitados (como o Tumult) incorretamente assumem que a existência do registro é privada. Isso leva à subproteção (ruído insuficiente) porque eles falham em considerar que substituir um registro (em vez de deletá-lo) é o contrafactual válido quando o tamanho é conhecido. O DP4SQL identifica corretamente esses casos e aplica o ruído apropriado.
• Melhoria de Utilidade (Sobreproteção): Modelos de linha de base frequentemente tratam todos os atributos como privados, levando à sobreproteção (ruído excessivo). Por exemplo, no estudo de caso universitário, consultas sobre pontuações de avaliação públicas ou nomes de docentes resultaram em zero sensibilidade sob a política flexível do DP4SQL, enquanto as linhas de base injetaram ruído significativo. No TPC-H, o DP4SQL alcançou zero sensibilidade para consultas que retornam informações públicas (ex: contagens de fornecedores), enquanto as linhas de base adicionaram ruído que tornou os resultados inutilizáveis (erro relativo > 100%).
• Precisão: Em casos onde as linhas de base sobreprotegeram, o DP4SQL demonstrou erro relativo significativamente menor (ex: 19,6% vs. erros muito maiores nas linhas de base para consultas específicas do TPC-H).

Significância e Alegações

O artigo alega que o DP4SQL aborda a limitação de "tamanho único" dos atuais sistemas de SQL com privacidade diferencial. Ao permitir que os curadores de dados personalizem os requisitos de denegabilidade plausível, o sistema evita o compromisso entre violações de privacidade (devido à subproteção) e perda de utilidade de dados (devido à sobreproteção).

Os autores enfatizam que sua abordagem é sólida (sound): eles fornecem provas formais de que o sistema de inferência deriva corretamente um limite superior para a sensibilidade global, garantindo que o mecanismo resultante satisfaça a privacidade diferencial $(PS, R^\star, \epsilon)$. O trabalho destaca que a modelagem correta da privacidade — especificamente a capacidade de raciocinar sobre tamanhos de tabela públicos, colunas públicas e proteção de atributos granulares — é essencial para implantar a privacidade diferencial em ambientes relacionais de múltiplas tabelas complexas.