Property-Preserving Hashing for $\ell_1$-Distance Predicates: Applications to Countering Adversarial Input Attacks

Este artigo propõe a primeira construção de hashing que preserva propriedades para predicados de distância $\ell_1$, oferecendo uma solução eficiente e robusta para detectar imagens similares sob ataques adversariais, forçando os atacantes a introduzir ruído significativo que degrada a qualidade da imagem.

O essencial

Imagine que você tem um cofre digital gigante cheio de fotos (um banco de dados) e você quer saber se uma nova foto que você acabou de tirar é "parecida" com alguma delas. O problema é que você não pode mostrar a foto original nem abrir o cofre para ninguém, por questões de privacidade.

Antigamente, usávamos uma espécie de "impressão digital visual" chamada Hash Perceptual. Era como tirar uma foto em preto e branco, borrada, para comparar. Mas os hackers descobriram um truque: eles podiam fazer pequenas alterações quase invisíveis na foto (como mudar a cor de um pixel aqui e ali) que enganavam o sistema. A foto parecia a mesma para um humano, mas o "impressão digital" mudava completamente, e o sistema dizia: "Não, essa não é a foto do cofre!".

Os autores deste artigo propuseram uma solução mais inteligente e segura, chamada Hash que Preserva Propriedades (PPH). Vamos explicar como funciona com uma analogia simples.

A Analogia da Receita de Bolo e o "Selo Mágico"

Imagine que cada imagem é um bolo feito com ingredientes específicos (os pixels).

• O Problema Antigo: O sistema antigo pegava uma amostra do bolo, esmagava e dizia "É bolo de chocolate". Mas um hacker podia trocar um grão de açúcar por um de sal (imperceptível) e o sistema dizia "Isso não é bolo de chocolate!".
• A Nova Solução (PPH): Em vez de apenas esmagar o bolo, os autores criaram uma receita matemática especial (um polinômio) para cada imagem.

Como funciona o novo sistema?

1. A Transformação (O Hash):
   Quando você envia uma foto, o sistema não a guarda. Ele transforma a foto em uma receita matemática complexa (chamada de polinômio $\sigma_x$). Pense nisso como transformar os ingredientes do bolo em uma lista de códigos secretos.

2. A Comparação (O Teste):
   Quando você quer saber se a sua foto é parecida com uma do banco de dados, você não compara as fotos. Você compara as receitas matemáticas.

   • O sistema usa uma ferramenta mágica (chamada Algoritmo de Euclides Estendido) para verificar se a diferença entre as duas receitas é pequena o suficiente.
   • Se a diferença for pequena (dentro de um limite $t$), o sistema diz: "Sim, são parecidas!".
   • Se a diferença for grande, diz: "Não, são diferentes".

3. Por que os hackers não conseguem enganar?
   Aqui está a mágica. Para enganar esse novo sistema, o hacker não pode apenas fazer uma pequena mudança "sutil". Ele precisa alterar a receita matemática de tal forma que ela pareça a mesma para o sistema, mas seja uma foto diferente.

   • Para fazer isso, o hacker teria que adicionar tanta ruído e distorção na imagem que a foto ficaria irreconhecível (como transformar um rosto humano em uma mancha de tinta).
   • Basicamente, o sistema força o hacker a escolher: ou a foto é parecida (e o sistema detecta), ou a foto é muito diferente (e o sistema rejeita). Não existe o "meio-termo" onde a foto parece igual para nós, mas diferente para o computador.

O "Pulo do Gato" Matemático

Os autores usaram um conceito de Códigos Corretores de Erros (algo usado em comunicações espaciais para corrigir falhas de transmissão). Eles adaptaram essa ideia para lidar com a distância $\ell_1$.

• Distância $\ell_1$: Imagine que você está em uma cidade com ruas em grade (como Manhattan). Para ir de um ponto A a um B, você só pode andar para frente, para trás, para a esquerda ou para a direita. A distância é a soma de todos os passos.
• O sistema verifica se a "soma dos passos" (a diferença entre os pixels) é pequena. Se for, as imagens são similares.

Por que isso é importante?

1. Segurança contra Ataques: Hoje em dia, existem ataques onde hackers tentam enganar sistemas de reconhecimento facial ou de detecção de conteúdo ilegal (como imagens de abuso infantil) fazendo pequenas alterações. Esse novo método torna esses ataques muito difíceis, porque qualquer tentativa de "enganar" o sistema destrói a qualidade da imagem.
2. Privacidade: O servidor nunca vê a imagem real. Ele só vê e compara as "receitas matemáticas" (os hashes).
3. Velocidade: O sistema é rápido. Para imagens grandes, eles dividem a foto em "blocos" (como um quebra-cabeça) e verificam cada peça separadamente, o que permite que tudo aconteça em segundos, mesmo em computadores comuns.

Resumo em uma frase

Os autores criaram um novo tipo de "impressão digital" para imagens que é matematicamente impossível de ser enganada com pequenas alterações, garantindo que, se o sistema disser que duas fotos são iguais, elas são realmente visualmente similares, e se disserem que são diferentes, qualquer tentativa de fingir que são iguais vai estragar a foto a ponto de ficar irreconhecível.

É como se o sistema tivesse um "olho de águia" que só vê a verdade matemática, ignorando qualquer truque visual que um hacker tente fazer.

Resumo técnico

Resumo Técnico: Hashing Preservador de Propriedades para Predicados de Distância ℓ1

1. O Problema

O hashing perceptual (ou sensível ao conteúdo) é amplamente utilizado para detectar imagens semelhantes em bancos de dados, com aplicações em reconhecimento facial, controle de fronteiras e filtragem de conteúdo ilegal na nuvem. No entanto, esses sistemas são vulneráveis a ataques de evasão adversarial. Nesses ataques, um adversário introduz pequenas perturbações imperceptíveis em uma imagem para que o algoritmo de hashing gere um resumo (hash) diferente do original, fazendo com que a imagem seja considerada "dissimilar" pelo sistema, mesmo sendo visualmente idêntica.

A raiz do problema reside na natureza probabilística do hashing perceptual: ele não garante uma correção negligenciável (ou seja, há uma probabilidade não desprezível de que imagens perceptualmente similares produzam hashes diferentes). Isso cria uma lacuna que os atacantes exploram para otimizar a perturbação da imagem, mantendo a similaridade visual mas alterando o hash.

O artigo propõe a aplicação de Hashing Preservador de Propriedades (PPH - Property-Preserving Hashing) para resolver essa vulnerabilidade. Diferente do hashing tradicional, o PPH garante que uma propriedade específica (neste caso, a distância entre imagens) seja preservada no domínio do hash com erro de correção negligenciável.

2. Metodologia

Os autores propõem a primeira construção de PPH para predicados de distância ℓ1 assimétrica. A metodologia baseia-se em conceitos de criptografia e teoria de códigos de correção de erros.

• Definição do Predicado: O sistema verifica se duas imagens $x$ e $y$ estão dentro de um limiar de distância $t$. A distância utilizada é a distância ℓ1 assimétrica, definida por:
  $$\|x \dot{-} y\|_1 = \sum \max(0, x_i - y_i)$$
  O predicado retorna 1 se ambas as distâncias unilaterais ($\|x \dot{-} y\|_1$ e $\|y \dot{-} x\|_1$) forem menores que um limiar $t$. Isso é crucial porque muitos ataques adversariais usam a norma ℓ2 (relacionada à ℓ1) como função objetivo; forçar um ataque a exceder o limiar ℓ1 degrada significativamente a qualidade visual da imagem.

• Construção Baseada em Polinômios:

  • A construção utiliza Códigos de Correção de Erros ℓ1 de Tallini e Rose.
  • Cada imagem $x$ (vetor de pixels) é mapeada para um polinômio $\sigma_x(z)$ sobre um corpo finito $\mathbb{Z}_p$:
    $$\sigma_x(z) = \prod_{i=1}^{n} (1 - a_i z)^{x_i}$$
    onde $a_i$ são elementos aleatórios distintos e $x_i$ são os valores dos pixels.
  • O hash da imagem é o polinômio $\sigma_x(z)$ reduzido módulo $z^{t+1}$.

• Algoritmo de Avaliação (Eval):

  • Para verificar a similaridade entre um hash de entrada $h(y)$ e um hash de banco de dados $h(x)$, o servidor utiliza o Algoritmo de Euclides Estendido (EEA).
  • O sistema calcula o inverso de $\sigma_x$ e verifica se o grau dos polinômios resultantes da divisão satisfaz as condições do limiar $t$.
  • Se as condições forem atendidas, o predicado retorna 1 (similar); caso contrário, 0.

• Otimização para Imagens Grandes:

  • Como a complexidade é $O(t^2)$, para imagens de alta resolução (ex: 224x224 RGB), o método divide a imagem em blocos menores. O predicado é avaliado por bloco, permitindo paralelização massiva.

3. Contribuições Principais

1. Primeira Construção PPH para Distância ℓ1: Os autores apresentam o primeiro esquema de hashing que preserva propriedades de distância ℓ1 assimétrica, superando as limitações anteriores focadas apenas em distância de Hamming.
2. Garantia de Robustez contra Evasão: O esquema oferece uma garantia de correção negligenciável. Para um atacante evadir a detecção, ele é forçado a adicionar ruído suficiente para exceder o limiar $t$, o que degrada drasticamente a qualidade perceptual da imagem (tornando o ataque inútil para fins de disfarce).
3. Limites Teóricos de Compressão: O artigo estabelece limites inferiores para o tamanho do digest (hash) necessário para preservar predicados de distância ℓ1. A proposta atinge uma compressão próxima a esses limites para pequenos valores de $t$.
4. Análise de Segurança:
   • Inversão: Demonstra-se que recuperar a imagem original a partir do hash é computacionalmente caro (complexidade exponencial em relação ao tamanho da imagem).
   • Colisões: A probabilidade de colisões (imagens diferentes gerando o mesmo hash) é extremamente baixa em configurações não robustas e controlada em configurações robustas.
5. Implementação Eficiente: O esquema foi implementado e testado, demonstrando tempos de execução viáveis para aplicações práticas.

4. Resultados Experimentais

Os autores testaram o esquema no conjunto de dados Imagenette (subconjunto do ImageNet) contra ataques de evasão conhecidos (FGSM e PGD) e transformações de imagem (brilho e contraste).

• Desempenho contra Ataques Adversariais:

  • Para imagens RGB 224x224, divididas em 1.000 blocos, a avaliação do predicado leva 0,0128 segundos por bloco (para uma mudança de 1% nos pixels).
  • O tempo total para processar uma imagem inteira é de aproximadamente 13 segundos (que pode ser reduzido significativamente com paralelização em GPUs).
  • O esquema impede ataques de evasão: para que um ataque FGSM ou PGD seja bem-sucedido (evite a detecção), ele precisa introduzir um ruído que resulta em uma distorção visual perceptível (LPIPS > 0.3), tornando a imagem inutilizável para o atacante.

• Comparação de Métricas:

  • O uso da métrica NAD (Normalized Asymmetric Distance) mostrou-se eficaz. Um limiar $t$ escolhido para garantir zero falsos positivos no banco de dados (imagens originais) também garante que ataques com ruído imperceptível sejam detectados.
  • Exemplo: Um ataque FGSM com $\epsilon=0.1$ resultou em uma degradação visual significativa (LPIPS ~0.56) para ser detectado, enquanto ataques com ruído menor (imperceptível) foram bloqueados.

• Eficiência Computacional:

  • Para imagens pequenas (28x28, estilo MNIST), a avaliação leva 0,0784 segundos.
  • O esquema é altamente paralelizável, permitindo escalabilidade para grandes bancos de dados.

5. Significado e Impacto

Este trabalho é significativo por várias razões:

• Segurança em Privacidade: Permite verificar similaridade de imagens (ex: para detectar CSAM ou roubo de identidade) sem revelar a imagem original ao servidor, mantendo a privacidade do usuário.
• Defesa contra Adversários: Oferece uma solução teórica e prática para o problema de ataques de evasão em hashing perceptual, que é uma vulnerabilidade crítica em sistemas de segurança baseados em visão computacional.
• Avanço Criptográfico: Estende a aplicação de PPHs, anteriormente restritos a distâncias de Hamming, para métricas de espaço contínuo (ℓ1/ℓ2), conectando teoria de códigos, álgebra polinomial e segurança cibernética.
• Viabilidade Prática: A demonstração de que é possível realizar essas verificações complexas em tempos aceitáveis (sub-segundos a segundos, dependendo do paralelismo) torna a adoção em cenários reais (como nuvem e borda) factível.

Em resumo, o artigo propõe uma mudança de paradigma: em vez de confiar na probabilidade de similaridade de hashes (como no hashing perceptual tradicional), utiliza garantias criptográficas rigorosas para garantir que qualquer tentativa de evasão resulte em uma alteração visível e indesejada na imagem, neutralizando assim a eficácia dos ataques adversariais.