Apresentação SIC 2016

Título do capítulo Autor: Levindo Gabriel Taschetto NetoOrientador: Alberto Egon Schaeffer-Filho 15/09/2016

Verificação Formal em Redes Definidas por Software

Introdução

Atualmente a necessidade por mais programabilidade e flexibilidade encoraja a utilização de abstrações de software.Isso serve para realizar atividades relacionadas à operação da rede. Exemplos • Algoritmos de roteamento• Balanceadores de carga

Software fechado rodando em um

hardware proprietário

Manipulação de fluxos de dados usando software

independentemente do hardware

Objetivo do Trabalho

O objetivo do presente trabalho é investigar métodos, e desenvolver aplicações para verificar formalmente as seguintes propriedades em redes definidas por software• Conflitos• Redundâncias• Reachability

Propriedades Exploradas em SDN

ConflitosRegras com mesmo match (dados de reconhecimento de pacote), mas ações diferentes.

Propriedades Exploradas em SDN

ConflitosRegras com mesmo match (dados de reconhecimento de pacote), mas ações diferentes.RedundânciasRegras com mesmo match (dados de reconhecimento de pacote) e ações iguais.

Propriedades Exploradas em SDN

ConflitosRegras com mesmo match (dados de reconhecimento de pacote), mas ações diferentes.RedundânciasRegras com mesmo match (dados de reconhecimento de pacote) e ações iguais.ReachabilityDeterminado pacote que sai de um switch A chega em um switch B de maneira certa.

Placidus: A Platform for Formal Verification in Software Defined Networks

O Placidus é uma plataforma de verificação formal para redes definidas por software.

A plataforma conta com dois módulos que verificam as seguintes propriedades

• Conflitos e Redundâncias de regras lógicas formados a partir de uma topologia.

• Reachability dentro de uma rede.

Placidus: Localização na rede

ControladorSDN

Dispositivomal configurado

Fluxos

Placidus: Coleta de Dados

Placidus: Coleta de Dados

Placidus: Coleta de Dados

Placidus: Módulos

Verificador de Conflitos e

Redundâncias

Verificador de Reachability

Placidus: Verificador de Conflitos e Redundâncias

Estrutura de Dados

SW1

SW2

SW3

Switches Lista de regras de cada switchMatch Ação

Placidus: Verificador de Conflitos e Redundâncias

Match 0

Match 1

Match 2

Match 3

Match 4

AlgoritmoCompara dados de reconhecimento

Placidus: Verificador de Conflitos e Redundâncias

Algoritmo

Match 0

Match 1

Match 2

Match 3

Match 4

Compara dados de reconhecimento

Placidus: Verificador de Conflitos e Redundâncias

Algoritmo

Match 0

Match 1

Match 2

Match 3

Match 4

Compara dados de reconhecimento

Placidus: Verificador de Conflitos e Redundâncias

Algoritmo

Match 0

Match 1

Match 2

Match 3

Match 4

Compara dados de reconhecimento

Placidus: Verificador de Conflitos e Redundâncias

Algoritmo

Match 0

Match 1

Match 2

Match 3

Match 4

Remove a primeira regra

Placidus: Verificador de Conflitos e Redundâncias

Algoritmo

Match 1

Match 2

Match 3

Match 4

Segue com as comparações até encontrar regras com mesmo match

Placidus: Verificador de Conflitos e Redundâncias

Match 1

Match 2

Match 3

Match 4

Iguais

AlgoritmoSegue com as comparações até encontrar regras com mesmo match

Placidus: Verificador de Conflitos e Redundâncias

Ação 1

Ação 2

AlgoritmoCompara as ações das regras com iguais dados de reconhecimento

Placidus: Verificador de Conflitos e Redundâncias

Ação 1

Ação 2

Diferentes

AlgoritmoCompara as ações das regras com iguais dados de reconhecimento

Placidus: Verificador de Conflitos e Redundâncias

Ação 1

Ação 2

DiferentesConflito

AlgoritmoCompara as ações das regras com iguais dados de reconhecimento

Placidus: Verificador de Conflitos e Redundâncias

Ação 1

Ação 2

Iguais

AlgoritmoCompara as ações das regras com iguais dados de reconhecimento

Placidus: Verificador de Conflitos e Redundâncias

Ação 1

Ação 2

IguaisRedundância

AlgoritmoCompara as ações das regras com iguais dados de reconhecimento

Placidus: Verificador de Conflitos e Redundâncias

Comparações a cada iteração

Desempenho

Comparações

Placidus: Verificador de Conflitos e Redundâncias

Execução

Switches contidos na topologia

Placidus: Verificador de Conflitos e Redundâncias

SaídaSão gerados três arquivos após a execução● Regras conflitantes● Regras redundantes● Todas as regras da topologia

No seguinte formato... 00:04 ^00:02 ^0x0x806 -> output=1

Match Ação

Placidus: Verificador de Reachability

Estrutura de DadosLista com listas de vetores de bits

Match Ação

SW1

SW2

SW3

Placidus: Verificador de Reachability

AlgoritmoConverte a tabela de dados geradas na coleta para uma tabela de bits

“2” “5” “5” “1”

“5” “7” “3” “0”

“6” “6” “1” “1”

“7” “5” “6” “1”

“2” “1” “5” “0”

“6” “4” “7” “0”

Placidus: Verificador de Reachability

AlgoritmoConverte a tabela de dados geradas na coleta para uma tabela de bits

“2” “5” “5” “1”

“5” “7” “3” “0”

“6” “6” “1” “1”

“7” “5” “6” “1”

“2” “1” “5” “0”

“6” “4” “7” “0”

010 101 101 1

101 111 011 0

110 110 001 1

111 101 110 1

010 001 101 0

110 100 111 0

Placidus: Verificador de Reachability

AlgoritmoA tabela de bits é convertida em listas de vetores de bits

010101101 1

101111011 0

110110001 1

111101110 0

010001101 1

110100111 0

Placidus: Verificador de Reachability

AlgoritmoO pacote de entrada é procurado nos n-1 bits das listas, por meio de um XNOR bit a bit

010101101 1

101111011 0

110110001 1

111101110 0

010001101 1

110100111 0

110110001

0

Placidus: Verificador de Reachability

AlgoritmoO pacote de entrada é procurado nos n-1 bits das listas, por meio de um XNOR bit a bit

010101101 1

101111011 0

110110001 1

111101110 0

010001101 1

110100111 0

110110001

0

Placidus: Verificador de Reachability

AlgoritmoO pacote de entrada é procurado nos n-1 bits das listas, por meio de um XNOR bit a bit

010101101 1

101111011 0

110110001 1

111101110 0

010001101 1

110100111 0

110110001

0

Placidus: Verificador de Reachability

AlgoritmoO pacote é encontrado nos n-1 bits de uma das listas

010101101 1

101111011 0

110110001 1

111101110 0

010001101 1

110100111 0

110110001

1

Placidus: Verificador de Reachability

AlgoritmoÉ feito um AND entre a ação da regra encontrada com o bit 1

110110001 1

1

1

Placidus: Verificador de Reachability

AlgoritmoÉ feito um AND entre a ação da regra encontrada com o bit 1

110110001 1

1

1

Pacote pode passar

Placidus: Verificação de Reachability

Execução

Placidus: Resultados Experimentais

Configurações da máquina utilizada

ProcessadorIntel Core I7-4790 3.6GhZ de 8 núcleos

Memória RAM15.6 GB

Resultados Experimentais: Conflitos e Redundâncias

nº de regras

tempo (s)

Resultados Experimentais: Reachability

tempo (s)

nº de regras

Trabalhos em andamento

Atualmente tem se trabalhado em uma solução para a verificação de Reachability com a utilização de grafos aliados aos vetores de bits.

Trabalhos relacionados

Alguns trabalhos que foram utilizados como inspiração para os algoritmos desenvolvidos para a plataforma Placidus

• Formal Correctness of Conflict Detection for Firewalls Caprett, V; Stepien, B; Felty, A; Matwin, S.

• Header Space Analysis: Static Checking For Networks Kazemian,P; Varghese,G; McKeown,N.

Conclusão e Trabalhos Futuros

Nossa pesquisa na área de verificação formal de redes SDN tem o propósito de tornar a rede mais robusta e confiável.

Trabalhos futuros incluem• Uniformização das Estruturas de Dados• Detecção de loops• Detecção de black holes• Aprimoramento dos algoritmos para

verificação das propriedades já verificadas

Título do capítuloObrigado!

Salão de Iniciação Científica UFRGS 2016

Autor: Levindo Gabriel Taschetto NetoOrientador: Alberto Egon Schaeffer-Filho 15/09/2016