Uma Proposta de Marcação de Pacotes
para Rastreamento Robusto a Ataques
Marcelo D. D. Moreira1, Rafael P. Laufer2, Pedro B. Velloso3,
Otto Carlos M. B. Duarte1
1 Universidade
2 University
3 Université
Federal do Rio de Janeiro (UFRJ)
of California, Los Angeles (UCLA)
Pierre et Marie Curie – Paris VI (UPMC)
Introdução
• Protocolo IP (Internet Protocol )
– Sem autenticação da fonte
– Roteamento baseado unicamente no endereço de destino
Introdução
• Protocolo IP (Internet Protocol )
– Sem autenticação da fonte
– Roteamento baseado unicamente no endereço de destino
Origem Destino
X
B
B
Origem Destino
A
roteador
X
B
Pacotes forjados alcançam seus destinos
Introdução
• Protocolo IP (Internet Protocol )
– Sem autenticação da fonte
– Roteamento baseado unicamente no endereço de destino
– Ausência de estado nos roteadores
• Pacotes não podem ser rastreados
• Solução
– Inserir rastros
• Rastreamento baseado em auditoria
− Roteadores
• Rastreamento sem estado
− Pacote
Rastreamento sem Estado
• Marcação de pacotes
– Cada roteador insere seu rastro no pacote
R5
A
R2
R4
R7
R6
R1
V
R3
Vítima tem informações suficientes para reconstruir rota
Como fazer os rastros?
1. Cada roteador insere seu endereço
Rota completa
contida no pacote
Pacote inicial
Roteador 1
•
Roteador 2
Roteador 3
Problemas
– Usam-se muitos bits
– Lista de endereços cresce com o aumento da rota
• Processamento e fragmentação
Como fazer os rastros?
2. Filtro de Bloom integrado em cada pacote
– Roteadores inserem endereço IP no filtro
•
•
O que é Filtro de Bloom?
Por que ele pode ser utilizado no rastreamento?
Filtro de Bloom
• Estrutura de dados que representa um conjunto de forma
compacta
• Aplicações em redes de computadores
– Pequeno vetor de bits no lugar de lista explícita de elementos
• Grande economia de espaço
– Custo: introdução de falsos positivos
Filtro de Bloom
• Inserção de Elemento
Vetor agora
representa o
conjunto S
k funções hash
1
0
1
0
h1(•)
s21
S = {s1, s2}
h2(•)
.
.
.
hk(•)
0
1
0
0
0
0
1
0
1
Filtro de Bloom
m bits
Filtro de Bloom
• Teste de Pertinência
Já foram
inseridos s1 e s2
k funções hash
1
1
es21
es21 
S
h1(•)
0
h2(•)
.
.
.
hk(•)
1
0
0
1
1



m bits
Falso positivo
Rastreamento com Filtro de Bloom
• Vantagens
– Tamanho fixo evita fragmentação
– Compactação reduz espaço ocupado no pacote
– Pouco processamento adicional
• Desvantagem
– Introdução de falsos positivos
Rastreamento com Filtro de Bloom
• Reconstrução de rota
– Após a inserção dos rastros
– Vítima possui um filtro com os roteadores da rota de ataque
10010011

1 0 0 1 0 0 1
1
A
R5
R2
R4
R7
R6
10 0 1 0 0 1 1
10 0 1 0 0 1 1
R1
R3
V
Rastreamento com Filtro de Bloom
• Reconstrução de rota
– Após a inserção dos rastros
– Vítima possui um filtro com os roteadores da rota de ataque
R5
A
R2
R4
R7
R6
R1
R3
V
O Problema da Condição Inicial
• Nó de origem é quem inicializa o filtro
– Atacante detém o controle da condição inicial
• Atacante pode colocar todos os bits em 1
– Saturação do filtro
– Taxas de falso positivo de 100%
1
1
1
• Conseqüência
– Todas as rotas são rastreadas
Filtro saturado
1
1
1
1
1
Saturação do Filtro
A
R26
R27
R19
R20




R17

R18
R11


R9

R12


R13


R6
R14
R1
R16
R15



R3

V



R2

 R24
 R7
R5

R4

R21
R28
R23


R10


R22

R8

R29

R25


Mecanismos de Segurança
• Robustez à interferência da condição inicial
• Proposta pioneira
– Filtro de Bloom Generalizado
• Novidade: uso de funções hash que zeram os bits
• Torna o filtro menos dependente da condição inicial
Filtro de Bloom Generalizado
• Inserção de elemento
1
1
Condição inicial
qualquer
1
s1
g1(•)
.
. bits em 0
.
gk0(•)
h1(•)
.
. bits em 1
.
hk1(•)
1
1
1
1
1
1
1
1
1
m bits
Filtro de Bloom Generalizado
• Inserção de elemento
0
1
1
s1
g1(•)
.
. bits em 0
.
gk0(•)
h1(•)
.
. bits em 1
.
hk1(•)
1
1
1
1
1
0
1
1
1
m bits
Filtro de Bloom Generalizado
• Inserção de elemento
0
1
1
s2
g1(•)
.
.
.
gk0(•)
h1(•)
.
.
.
hk1(•)
bits em 0
1
1
1
1
bits em 1
1
0
1
1
1
m bits
Filtro de Bloom Generalizado
• Inserção de elemento
0
1
0
s2
g1(•)
.
.
.
gk0(•)
h1(•)
.
.
.
hk1(•)
bits em 0
0
1
1
1
bits em 1
1
0
1
1
1
m bits
Filtro de Bloom Generalizado
• Teste de Pertinência
0
s1 , s2  S
1
0
s2
g1(•)
.
.
.
gk0(•)
h1(•)
.
.
.
hk1(•)
bits em 0
0
1
1
1
bits em 1
1
0
1
1
1


m bits
Filtro de Bloom Generalizado
• Teste de Pertinência
0
s1 , s2  S
s1
1
g1(•)
.
. bits em 0
.
gk0(•)
h1(•)
.
. bits em 1
.
hk1(•)
Filtro se
“esqueceu” de s1
0
Falso negativo
0
Invertido por s2
1
1
1
1
0
1
1
1

m bits
Ataque do Ajuste da Condição Inicial
• Filtro de Bloom Generalizado vulnerável ao ataque
• Idéia
– Forjar a inserção de certos elementos
Ataque do Ajuste da Condição Inicial
• Filtro de Bloom Generalizado vulnerável ao ataque
• Idéia
– Forjar a inserção de certos elementos
Situação
normal
Representa
s1, s2,..., sn
Condição inicial
00100001
A
00001011
s1
s2
sn
Elementos legítimos
V
Ataque do Ajuste da Condição Inicial
• Filtro de Bloom Generalizado vulnerável ao ataque
• Idéia
– Forjar a inserção de certos elementos
Representa
s1, s2,..., sn
+
Elementos
forjados
Ataque
Nova condição inicial
10001101
Elementos
forjados
01001010
11101001
A
s1
s2
sn
Elementos legítimos
V
Ataque do Ajuste da Condição Inicial
• Reconstrução de rota
– Elementos forjados: R4 e R6
10010011

R5
1 0 0 1 0 0 1
1
A
R2
10 0 1 0 0 1 1
1 0 0 1 0 0 1
1
10 0 1 0 0 1 1
R4
R7
R1
10010011

R6
R3
V
Ataque do Ajuste da Condição Inicial
• Reconstrução de rota
– Elementos forjados: R4 e R6
R5
A
R2
R4
R7
R1
R6
R3
V
Robustez ao Ataque
• Ordem de inserção dos elementos no filtro:
ef
Elemento forjado
s1
s2
sn
Elementos legítimos
• Métrica de robustez:
– Probabilidade do filtro não reconhecer o elemento ef
Inversão de bits: as duas faces
da moeda
• Efeito benéfico
– Inversão de bits garante robustez
• Basta 1 bit invertido para a rejeição do elemento forjado
• Efeito maléfico
– Perda de informação (rastros)
• “Esquecimento” dos elementos antigos
Robustez do FBG
FBG (m = 128, k0 = k1 = 4)
Elemento forjado
não reconhecido
Elemento legítimo
não reconhecido
Proposta desse Trabalho
•
Objetivos
– Aumentar a robustez
– Diminuir perda de informação
•
Simultaneamente
Impossível no Filtro de Bloom Generalizado
Filtro de Bloom Concatenado
• Definição
– Concatenação de N subfiltros
de m/N bits cada
subfiltro 1
1
m/N bits
0
subfiltro 2
subfiltro 3
1
1
1
0
.
.
.
subfiltro N
0
1
m bits
Inserção de Elemento
contador = 1
s1
Esquema
de marcação
1
Condição inicial
qualquer
0
1
1
1
0
.
.
.
0
1
m bits
Inserção de Elemento
contador = 1
s1
Esquema
de marcação
0
1
1
1
1
0
.
.
.
0
1
m bits
Inserção de Elemento
contador = 2
0
1
s2
Esquema
de marcação
1
1
1
0
.
.
.
0
1
m bits
Inserção de Elemento
contador = 2
0
1
s2
Esquema
de marcação
0
1
1
0
.
.
.
0
1
m bits
Inserção de Elemento
contador = 3
0
1
0
1
s3
Esquema
de marcação
1
0
.
.
.
0
1
m bits
Inserção de Elemento
contador = 3
0
1
0
1
s3
Esquema
de marcação
0
0
.
.
.
0
1
m bits
Inserção de Elemento
contador = N
0
1
0
1
0
0
.
.
.
sN
Esquema
de marcação
0
1
m bits
Inserção de Elemento
contador = N
0
1
0
1
0
0
.
.
.
sN
Esquema
de marcação
1
0
m bits
Inserção de Elemento
Vantagens:
1) Não há perda de informação
– 1 elemento por subfiltro
2) Robustez
– Apagamento da condição inicial
0
Condição inicial
apagada
1
0
1
0
0
.
.
.
1
0
m bits
Esquema de Marcação
1) Subfiltro é inicialmente zerado
Condição inicial
qualquer
0
1
0
0
1
0
0
0
0
0
1
Subfiltro
m/N bits
Esquema de Marcação
1) Subfiltro é inicialmente zerado
Condição inicial
apagada
0
0
0
0
0
0
0
0
Subfiltro
m/N bits
Esquema de Marcação
1) Subfiltro é inicialmente zerado
2) Algoritmo do Filtro de Bloom original
k funções hash
0
0
si
h1(•)
0
h2(•)
.
.
.
hk(•)
0
0
0
0
0
Subfiltro
m/N bits
Esquema de Marcação
1) Subfiltro é inicialmente zerado
2) Algoritmo do Filtro de Bloom original
k funções hash
1
0
si
h1(•)
0
h2(•)
.
.
.
hk(•)
1
0
0
1
0
Subfiltro
m/N bits
Teste de Pertinência
contador = i
1
0
si
.
.
.
Esquema
de marcação
x1
1
x2
0
.
.
.
0
1
i-ésimo
subfiltro
m bits
Resultados Analíticos
• Falso negativo
– Elemento legítimo não é reconhecido pelo filtro
– Probabilidade nula
• 1 elemento por subfiltro  Não há perda de informação
• Falso positivo
– Elemento externo possui marcação idêntica à do elemento
legítimo
Resultados Analíticos
m/N = 1
m/N = 2
m/N = 4
Resultados Analíticos
p = 0.5
m/N = 1
m/N = 2
m/N = 4
pmin = 0.5
Resultados Analíticos
• Cálculo de p (probabilidade de um bit ser zerado)
• Probabilidade de nenhuma das k funções hash preencher um
bit com 1
fp vai ser mínima
quando p=0.5
p = 0.5
Resultados Analíticos
Resultados Analíticos
• Um outro esquema de marcação
Condição inicial
qualquer
si
H (•)
0
1
1
0
0
0
0
1
1
1
0
1
0
0
1
0
Subfiltro
m/N bits
Resultados Analíticos
• Um outro esquema de marcação
Condição inicial
sobrescrita
0
1
0
si
H (•)
0
1
0
0
1
Subfiltro
m/N bits
Resultados Analíticos
• Um outro esquema de marcação
• Cálculo de p (probabilidade de um bit ser zerado)
– Cada bit tem a mesma probabilidade de ser preenchido com 0
ou com 1. Logo,
p = 0.5
fp sempre mínima
Resultados Analíticos
• Probabilidade de sucesso do atacante pa
• Filtro de Bloom original
– Nenhum bit inserido pelo atacante é invertido
• Filtro de Bloom Concatenado
– Equivalente à probabilidade de falso positivo
Conclusões
• Filtro de Bloom Generalizado
– Alta robustez implica pequena capacidade de memória
• “Esquecimento” dos elementos antigos
• Filtro de Bloom Concatenado
– Alta robustez
• pa decresce exponencialmente
− 4 bits por subfiltro  pa = 6,25%
− 8 bits por subfiltro  pa = 0,39%
– Sem perda de informação
• Pouco processamento adicional
Conclusões
• Comparação numérica (1a parte)
Bits/elemento Prob. de falso
positivo
Robustez
Prob. de perda
de informação
Generalizado
25,6
0,002%
98,2%
96,5%
Concatenado
16
0,002%
99,998%
0%
Economia de espaço de 37,5%
Concatenado possui
mais memória
Conclusões
• Comparação numérica (2a parte)
Bits/elemento Prob. de falso
positivo
Robustez
Prob. de perda
de informação
Generalizado
25,6
6,25%
27%
22%
Concatenado
4
6,25%
93,8%
0%
Economia de espaço
de 84,4%
Concatenado possui
mais memória
3,5 vezes mais robusto
Uma Proposta de Marcação de Pacotes
para Rastreamento Robusto a Ataques
Marcelo D. D. Moreira1, Rafael P. Laufer2, Pedro B. Velloso3,
Otto Carlos M. B. Duarte1
1 Universidade
2 University
3 Université
Federal do Rio de Janeiro (UFRJ)
of California, Los Angeles (UCLA)
Pierre et Marie Curie – Paris VI (UPMC)
Trabalhos Futuros
• Simulações
– Validar expressões analíticas
– Resultados na aplicação ao rastreamento IP
Rastreamento sem Estado
• Marcação de pacotes
– Cada roteador insere seu rastro no pacote
R5
A
R2
R4
R7
R6
R1
V
R3
Vítima tem informações suficientes para reconstruir rota
Filtro de Bloom: Aplicações
• Redes P2P e localização de recursos
– Cada nó envia para seus vizinhos um Filtro de Bloom
• Filtro contém os objetos que podem ser alcançados através do nó
– Economia de espaço
• Identificador: 64 bits por objeto
• Filtro de Bloom: 8 ou 16 bits por objeto
• Distribuição de Web cache
– Servidores proxy trocam Filtros de Bloom
• Filtros representam o conteúdo do cache de cada proxy
• Rastreamento IP
Filtro de Bloom
• Deseja-se representar um conjunto S de n elementos
S = {s1, s2,..., sn}
• São utilizados:
a) Vetor de m bits, inicialmente todos zerados
b) Uma família de k funções hash independentes e uniformes
h1, h2,..., hk
c) Dois algoritmos
• Inserção de Elemento
• Teste de Pertinência
Inserção de Elemento
• Preenchimento com 1 de alguns bits
• As posições dos bits a serem preenchidos são dadas pelas
saídas das k funções hash
Teste de Pertinência
• Objetivo:
– Verificar se os bits indicados pelas saídas das k funções hash
estão todos em 1
O Problema da Condição Inicial
• Nó de origem é quem inicializa o filtro
– Atacante detém o controle da condição inicial
• Condição inicial pode ser cuidadosamente ajustada
– Maximizar a probabilidade de falso positivo dos elementos
desejados
– Saturar o filtro
• Colocar todos os bits em 1
• Taxas de falso positivo de 100%
• Conseqüência
– Comprometimento das aplicações
O Problema da Condição Inicial
• Conseqüências
– Redes P2P e distribuição de Web cache
• Demais nós acreditarão que atacante possui todas as páginas
ou objetos procurados
• Atacante pode substituir objetos procurados por outros
– Rastreamento IP
• Além da verdadeira rota de ataque, outras rotas serão
rastreadas
Ataque do Ajuste da Condição Inicial
• Definições:
a) U é o conjunto de todos os roteadores da Internet
b) S = {s1, s2,..., sn} é o conjunto dos roteadores integrantes da
rota de ataque
c) A ⊂ (U\S) é um conjunto de roteadores que não
pertencem à rota de ataque
• Objetivo do ataque:
– Maximizar a probabilidade de falso positivo dos elementos
de A, somente ajustando a condição inicial
Ataque do Ajuste da Condição Inicial
• Implementação do ataque
– Antes de enviar o pacote pela rede, o atacante:
• Insere no filtro os elementos de um conjunto B ⊂ U
• Caso a marcação de pacotes não seja robusta
– Elementos de B serão reconhecidos pelo filtro
– Falsos positivos “forçados”
• Ocorrem quando B ⊂ A
– Saturação do filtro
• Ocorre quando B = U
Inversão de bits: as duas faces
da moeda
FBG de 128 bits
Proposta desse Trabalho
•
Idéia central
– Desacoplar a robustez da perda de informação
1) Falsos negativos são eliminados
•
Não há mais “esquecimento” dos elementos antigos
•
Não se perde mais informação legítima
2) Robustez não mais garantida pela inversão de bits
•
Passa a ser garantida pelo apagamento das informações
iniciais
Filtro de Bloom Concatenado
• Definição
– Concatenação de N subfiltros de m/N bits cada
• Inserção de Elemento
– Feita seqüencialmente de acordo com o índice de cada
elemento
• O elemento si é inserido no i-ésimo subfiltro
– Somente um elemento inserido em cada subfiltro
– São admitidos, no máximo, N elementos
Filtro de Bloom Concatenado
• Definição
– Concatenação de N subfiltros
de m/N bits cada
m/N bits
m bits
.
.
.
Filtro de Bloom Concatenado
• Inserção de elemento
m/N bits
s1
s2
s3
.
.
.
sn
Esquema
de marcação
m bits
.
.
.
Resultados Analíticos
m/N = 1
m/N = 2
m/N = 4
Contribuições
• Ataque do ajuste da condição inicial
• Análise da robustez do Filtro de Bloom Generalizado
– Acoplamento entre robustez e perda de informação legítima
• Proposta do Filtro de Bloom Concatenado
– Concatenação de N subfiltros
– 1 elemento por subfiltro
– Desacoplamento entre robustez e perda de informação
• Apagamento das informações iniciais
• Probabilidade nula de falso negativo
Filtro de Bloom Generalizado
• Conjunto de n elementos S = {s1, s2,..., sn}
• Vetor de m bits, com probabilidades iniciais p0(0) e p1(0)
• Conjunto de k0 + k1 funções hash
– H = {g1, g2,..., gk , h1, h2,..., hk }
0
1
– Independentes e uniformes
• Para cada elemento si  S,
– Os bits g1(si), g2(si),..., gk (si) são colocados em 0
0
– Os bits h1(si), h2(si),..., hk (si) são colocados em 1
1
– Em uma colisão entre gi e hj, o bit é zerado, i,j
• Os bits podem ser colocados em 0 ou 1 diversas vezes
Filtro de Bloom Generalizado
• Verificando se um elemento x  S
– Verifica-se se todos os bits gi(x) estão em 0, 1  i  k0
– Verifica-se se todos os bits hj(x) estão em 1, 1  j  k1
– Se pelo menos um bit está invertido, é assumido que x  S
• Possibilidade de um falso negativo
– Se nenhum bit está invertido, é assumido que x  S
• Possibilidade de um falso positivo
• Condição inicial do vetor ou subconjunto de elementos de S
Filtro de Bloom Generalizado
• Cálculo da probabilidade de falso positivo
– Probabilidade de um bit ser colocado em 0 por um elemento



k
/
m
0
q

1

1

1
m

1

e


0
k
0
– Probabilidade de um bit ser colocado em 1 por um elemento
k
k

k
/
m

k
/
m
1
0
0
1


q

1

1

1
m
1

1
mee
1





 
1


– Número médio de bits colocados em 0 e em 1 por inserção
b0  mq
. 0
b1  mq
.1
Filtro de Bloom Generalizado
• Cálculo da probabilidade de falso positivo
– Probabilidade de um bit estar em 0 depois das n inserções
n

1
n
01
0
i

0
p
(
n
)

p
(
0
)
1

q

q

q
1

q

q





0
0
i
01
1

1

q

q



p
(
0
)
1

q

qq



0
1

1

q

q


0
1
n q
n
0


p
(
0
)
1

q

q
 1

1

q

q




0
01
01


q

q
01
n
0 1
0
n
0 1
– Probabilidade de um bit estar em 1 depois das n inserções
q
n


p
(
n
)(

p
0
)
1

q

q
1

1

q

q




1
1
0
1


q

q
n 1
01
01
Filtro de Bloom Generalizado
• Cálculo da probabilidade de falso positivo
() pn
()
– Probabilidade de falso positivo fppn
0
1
– No filtro convencional, k0 = 0, p0(0) = 1, p1(0) = 0

k
nm
/
1
b
0
p
(
n
)

e
0
0
b
0

k
nm
/
1
pn
(
)

1

e


1
b
1

k
1/m
b

m
1

e


1
– Usando a simplificação usada no filtro convencional
2




k
k
1

k
/
m
1
1
1
b

m
1

e
1

1


.
.
.

k

m



1
1
2 
m
2
!
m




– Probabilidade de falso positivo no filtro convencional
fp1

e

1

k
nm
/ k
1
Filtro de Bloom Generalizado
• Cálculo da probabilidade de falso negativo
– Elemento inserido não ser reconhecido pelo filtro
– Probabilidade muda de acordo com a ordem de inserção
• Probabilidade do último elemento é zero
• Probabilidade do primeiro elemento é a mais alta
– Probabilidade de um bit do (n - i)-ésimo elemento não ser
invertido pelos i elementos seguintes
Filtro de Bloom Generalizado
• Cálculo da probabilidade de falso negativo
– Probabilidade de um bit zerado pelo (n - i)-ésimo elemento
permanecer em 0 depois das i inserções seguintes
i

1
p
(
n

i
)

1

q

q

qq
1


q





0
0
0
i
01
j

0
j
01
q
i
0


1

q

q
 1

1

q

q




0
1


q

q
0
1
i
01
– Probabilidade de um bit preenchido pelo (n - i)-ésimo
elemento permanecer em 1 depois das i inserções seguintes
q
i
1


p
()
n

i

1

q

q
 1

1

q

q




1
1
01


q

q
01
i
01
Filtro de Bloom Generalizado
• Cálculo da probabilidade de falso negativo
– Probabilidade de falso negativo
b
b
0
1
fn

i

1

p
(
n

i
)
p
(
n

i
)


n
0
0
1
1