.:: Marcos Alvares ::.

Inteligencia Computacional tem sido usada como ferramenta de apoio para outras áreas da computação. O objetivo desse Post é oferecer uma VISÃO GERAL a respeito de Computação evolucionária.  Vou tentar compartilhar um pouco do que estudei para usarmos como meio no desenvolvimento de melhores ferramentas de segurança da informação.

Uma das áreas mais fascinantes de Inteligencia Computacional certamente é a Computação Natural. A Computação Natural representa uma série de técnicas computacionais inspiradas em mecanismos encontrados na natureza. Esses mecanismos naturais vão desde o funcionamento de neurônios ao comportamento coletivo de organismos. As principais técnicas estudadas em computação natural são: Redes Neurais Artificiais, Algoritmos Evolucionários, Inteligência por Enxames e Sistemas Imunológicos Artificiais.

Nesse artigo vamos falar sobre Algoritmos Evolucionários, mais especificamente sobre algorítimos que usam mecanismos de Coevolução. Os algorítimos evolucionários são meta-heurísticas que imitam o mecanismo natural de evolução biológica proposto por Charles Darwin nas décadas de 60. Tal classe de algoritmos é geralmente usada para resolver problemas que não se conhece uma solução em tempo polinomial (NP-completos). Os Algoritmos Evolucionários são baseados em populações de indivíduos que evoluem ao decorrer do tempo. Cada indivíduo representa uma solução para o problema tratado.

Assim como na natureza, os Algorítimos Evolucionários possuem três operadores que trabalham sistematicamente:

• Seleção de indivíduos mais aptos para passar as suas características para as próximas gerações;
• Cruzamento de indivíduos aptos para formação de um novo indivíduo;
• Mutação dos novos indivíduos que garante diversidade na nova população.

Esses operadores são executados, repetidamente na população resultando em uma nova população que melhor se adapta ao ambiente. E assim o problema é resolvido iterativamente. Uma população de um algoritmo evolucionário qualquer e seus operadores podem ser observados na Figura 1.

Na Figura 1 mostramos três etapas de evolução numa população. Na primeira etapa os indivíduos mais e menos aptos selecionados, na segunda etapa o pior indivíduo é eliminado e os indivíduos mais aptos realizam um cruzamento retornando um novo indivíduo que corresponde a composição das duas melhores soluções e na terceira etapa o novo indivíduo sofre uma mutação gerando uma solução completamente diferente e garantindo uma diversidade na população. Nesse exemplo mostramos, de uma forma simplista, o funcionamento básico de uma técnica específica de Algoritmos Evolucionários que são os Algoritmos Genéticos.

Um exemplo de aplicação para Algoritmos Genéticos está em achar soluções para problemas de otimização de funções contínuas. Exemplo é a função Rosenbrock exibida na Figura 2.

É possível aplicar Algorítimos genéticos para achar o ponto mínimo dessa função que se encontra na coordenada (0,0). Cada indivíduo do algoritmo seria representado por um par ordenado (x,y) e a sua função de aptidão seria a função Rosenbrock. No inicio do problema os indivíduos seriam espalhados aleatoriamente pelo espaço de busca. Após o fim de uma determinada quantidade de gerações, perceberíamos que os indivíduos dessa nova geração estariam juntos próximo ao ponto (0,0), indicando qual a melhor solução para o problema de minimização da função Rosenbrock. Um exemplo da evolução do algoritmo é mostrado na Figura 3, onde os pontos pretos são os indivíduos do problema.

Algoritmo Genético é a técnica de Computação Evolucionária mais popular e possui diversas variações. Bom, o que foi mostrado é o BÁSICO de apenas uma técnica do mundo que é algorítimos evolucionários. Para mais detalhes sobre algorítimos genéticos ler os livros [1][2]. Esses fundamentos são essenciais para compreensão dos mecanismos de coevolução mostrados mais adiante.

Ao algorítimos evolucionários podemos adicionar características cooperativas e ai chegamos aos algoritmos co-evolucionários. Mas … o que é Coevolução ? É o processo que envolve a relação entre a evolução de duas ou mais entidades. Essa entidade pode ser uma população, um organismo vivo qualquer ou diferentes algoritmos computacionais inteligentes. Um exemplo de coevolução, encontrado na natureza da flor e do inseto, as flores precisam dos insetos para sua reprodução e os insetos precisam das flores para sua alimentação. Com isso surge um ciclo simbiótico que ambas espécimes são beneficiadas e evoluem em paralelo. No caso de uma coevolução cooperativa, ao decorrer dos anos essas especies se adaptam e evoluem para que o processo simbiótico seja fortalecido. Um exemplo disso são as orquídeas abelhas (Figura 4) que possuem o seu gineceu em forma de abelha fêmea, atraindo os machos e facilitando o processo de polinização.

Esse mecanismo de coevolução entre entidades pode ser de duas naturezas: competitiva e cooperativa. Para a coevolução competitiva, temos duas sub-classes:

• Competição: onde ambas as espécies são inibidas e a evolução emerge da competição;
• Amensalismo: onde apenas uma espécie é inibida e existe uma relação de espécie ameaçadora e espécie ameaçada;

Na evolução cooperativa (ou simbiótica) temos três sub-classes:

• Mutualismo: onde ambas as espécies são beneficiadas. A melhoria em uma das espécies serve como feedback positivo para a melhoria da outra espécie;
• Comensalismo: onde apenas uma das espécies é beneficiada e a outra não é afetada;
• Parasitismo: onde apenas uma das espécies é beneficiada e a outra é penalizada;

Nesse artigo vamos focar em coevolução por competição (CCE – Competitive Coevolution) mostrando o funcionamento de um algoritmo CCE genérico.

Diferentemente de abordagens evolucionárias como o algorítimo genético, o CCE avalia a aptidão através de uma função de aptidão relativa. Isso significa que a aptidão de cada indivíduo de uma população será avaliada em relação a população concorrente.

A avaliação dessa função de aptidão relativa significa uma complexidade a mais em relação a um algoritmo evolucionário convencional. Além da avaliação da função objetivo que está sendo otimizada é necessário uma comparação direta de cada indivíduo com os indivíduos da população concorrente. Para amenizar o impacto computacional de tal comparação, uma seleção dos indivíduos da população concorrente é realizada. Existem algumas estratégias de seleção que ajuda no calculo da aptidão relativa:

• Seleção todos versus todos: cada indivíduo em uma população é comparado com todos os indivíduos da população concorrente;
• Seleção aleatória: cada indivíduo de uma população é testado com um grupo selecionado aleatoriamente da população concorrente;
• Seleção por torneio: cada indivíduo de uma população é comparado com os indivíduos mais aptos relativamente de outra população;
• Seleção de todos versus os melhores: cada indivíduo de uma população é testado com os melhores indivíduos (função objetivo) na população concorrente;
• Seleção compartilhada: cada indivíduo de uma população é testado com os melhores indivíduos em relação a aptidão compartilhada máxima (será comentado mais na frente).

Existem também abordagens diferentes para o cálculo da aptidão relativa de cada indivíduo em uma população. As principais estratégias são:

• Aptidão Simples: para cada indivíduo da população, é realizado um somatório simples do número de indivíduos na população concorrente que são menos aptos;
• Aptidão Compartilhada: Essa aptidão é calculada levando em consideração similaridades entre os indivíduos da população. A aptidão simples de um indivíduo em uma população é dividido pela soma da aptidão dos indivíduos similares a ele. Isso causa um efeito de reforço para os indivíduos “diferentes” na população;
• Aptidão por Torneio: faz uso de uma estrutura de dados em forma de árvore para organizar um torneio entre os indivíduos, onde o indivíduo mais apto é colocado na raiz. Para cada nível da arvore dois indivíduos (escolhidos aleatoriamente) são posicionados e apenas o mais apto irá passar para o próximo nível. Após a formação da árvore um método de seleção qualquer é utilizado e uma aptidão simples é calculada.

Assim como a maioria dos algorítimos evolucionários o CCE possui problemas com elitismo. Uma das soluções mais eficazes é a chamada Hall da Fama, que consiste em criar uma área de tamanho limitado para proteger os indivíduos mais aptos da população (melhores soluções). Para cada geração o melhor indivíduo da iteração é armazenado no hall da fama da população. Caso o hall da fama esteja lotado o pior individuo é substituído.

Um pseudo-código do CCE com duas populações pode ser observado na Figura 5. Em cada iteração um algoritmo um algoritmo evolucionário qualquer como PSO ou algoritmo genético é usado para a fase de evolução de cada população.

Mas para que essa teoria toda ?! Tudo culpa dos meus amigos Julios (Fort e Auto) : ]. Eu havia lido na página do Júlio Auto sobre um de seus projetos chamado “On Code Normalization” [3]. Esse projeto consiste em levantar hipóteses para um dos desafios propostos em 2006 pelo Halvar Flake na Black Hat Vegas. O desafio consiste em basicamente conseguir produzir uma forma normal, de forma automática, para dois códigos sintaticamente diferentes mas com a mesma semântica. Fui catar o vídeo da apresentação e achei uma série de desafios interessantes [4], alguns parcialmente resolvidos e outros ainda sem solução. Um desses desafios me chamou muita atenção por o Halvar propor uma solução usando inteligencia computacional e eu achar que essa proposição realmente faz sentido e vale a pena experimentar. O desafio foi o seguinte: “Automating input craft for a path through the executable“. Esse desafio consiste em dado dois pontos “A” e “B” em um determinado programa determinar de forma automática uma configuração de entrada no ponto “A” que garanta a execução do código localizado no ponto “B”.

Vamos modelar esse problema em forma de um algorítimo evolucionário. Como seria modelado o indivíduo da nossa população? Esse indivíduo seria composto pela coleção de porções de memória modificáveis (variáveis, registradores, estruturas) pertencentes ao ambiente “A” e a combinação de todos os possíveis valores que essas podem assumir. Como seria medido a qualidade de uma solução? O fluxo do software pode ser representado por um grafo (ou múltiplos grafos), podemos medir a distancia do ponto B para um ponto C (alcançado por uma entrada qualquer) através de uma busca pelo menor caminho entre esses dois pontos. Com isso transformamos nosso problema de encontrar entradas que nos levam de um ponto a outro no software em um problema de otimização (minimização) em espaço discreto e que algorítimos evolucionários resolvem MUITO BEM.

Ai que entra o outro culpado, Júlio Fort, que me chamou para colaborar para uCon Security Conference III [5]. Apesar da necessidade de uma investigação rigorosa, estou otimista quanto aos possíveis resultados. Por isso, pensei em propor falar algo nessa linha e apresentar resultados que conseguir produzir daqui para o dia da conferência. A ideia é mostrar algo bem prático, com exemplos didáticos e provas de conceito. Em breve escreverei em mais detalhes a respeito dessa investigação por aqui.

Salve salve,

pois é pessoal, infelizmente o blog tem estado entregue as moscas … mas aqui estou eu de volta com as baterias renovadas e pronto para dar a luz a mais alguns artigos.

Retomando a linha de pesquisa, vamos fazer um planejamento de estudo para médio prazo. Primeiramente gostaria de terminar a série de artigos de vulndev. Estava concluindo o artigo sobre Heap Overflow (parte 2) quando foi lançada a Phrack #66 e tive que dar um “pause” na escrita para dar uma lida nos novos artigos. Nessa mesma série pretendo escrever artigos sobre escrita de shellcode, integer overflow, vulndev em outros SOs e um apenas de aplicação com uma coleção de exemplos reais comentados.

No inicio desse ano tive uma idéia envolvendo técnicas de sistemas multi-agentes inteligentes e fuzzy para teste automatizado de ambientes e mineração de vulnerabilidades, tentarei escrever até onde cheguei nessa investigação.

Nesse tempo sem postar, li dois livros bem interessantes: ‘Reversing: secrets of reverse engineering‘ e ‘The IDA Pro book‘ estou bastante entusiasmado em aplicar RE para análise de malwares (e eventualmente misturar algo de IA nisso tudo). Esses livros me despertaram para aspectos interessantes dos internals do Windows (NT based) e para estudos de análise estática de código.

Em paralelo estou, juntamente com meu grupo de pesquisa, ajudando na escrita de dois livros de Inteligencia Computacional (em português): o primeiro sobre inteligência por enxames e o segundo sobre computação evolucionaria. Aos poucos escreverei mini-artigos sobre essas duas sub-áreas de CI e postarei aqui no blog.

Minha linha de pesquisa de mestrado é Computação Social, que envolve diversas áreas divertidissimas como algoritmos culturais, semiótica, sistemas multi-agentes, coevolução, estratégias de evolução, etc. Ultimamente tenho tido insônias bem produtivas, pensando em como que as pessoas se comunicam e interagem com o mundo (objetos, outras pessoas, estruturas) e como ela armazena o conhecimento adquirido. Sempre tentarei postar algo que venho estudando desse escopo por aqui também.

Algumas áreas da segurança da informação tem uma ligação artística com o que estudo de I.A., isso dava um artigo filosófico bastante interessante também. O nível de maturidade que temos sobre determinada área de conhecimento tem um ciclo:

Filosofia -> Arte -> Ciência -> Engenharia

O que torna essas duas áreas de pesquisa tão interessantes é o fato de possuírem ramificações que, ao meu ver, ainda são expressões artísticas.

Pronto, agora elocumbrou de vez !! esquindô, esquindô!! e viva a ARTE! Sem mais delongas, é isso o que tenho feito ultimamente e agora que o contexto do processo de escritor foi carregado na CPU novamente vamos “colocar para moer“.

Adelante compañeros !

Caros, venho por meio deste anunciar mais uma edição do já tradicional Encontro de Software Livre da Universidade de Pernambuco [1]. O evento está em sua sexta edição e contará com palestras, mini-cursos e install fest oferecendo ao espectador um panorama da produção de Software Livre do estado de Pernambuco.

O encontro ocorrerá no próximo sábado dia 22 de Agosto das 10h às 17h no auditório da Escola Politécnica de Pernambuco (núcleo de engenharia da UPE) [2]. O evento é gratuito e para participar é só seguir os detalhes descritos no site [3].

A agenda do evento pode ser conferida em [4] e a grade de palestras em [5].

Estou na organização do evento e irei palestrar a respeito do meu projeto open-source: o Ruby Neuron [6]. Tenho como objetivo tentar eliminar o estigma que as técnicas de IA possuem de complexas e experimentais além de diminuir o gap entre a pesquisa e o uso prático da ciência produzida para melhoria de vida das pessoas. Em breve vou começar a escrever um artigo sobre o Ruby Neuron e como usa-lo como ferramenta para solução de problemas de classificação e regressão.

Referências:
[1] http://slpoli.dsc.upe.br/
[2] http://slpoli.dsc.upe.br/place/
[3] http://slpoli.dsc.upe.br/registration/
[4] http://slpoli.dsc.upe.br/schedule/
[5] http://slpoli.dsc.upe.br/speaker/
[6] http://rubyneuron.org/

O foco desse artigo é explicar a essência da técnica de exploração de overflows baseados na heap, para plataformas Intel x86 32 bits usando como sistema operacional o Linux. Esse artigo ficou muito grande para caber em um único post e resolvi dividi-lo em duas partes. A primeira irá descrever a fundamentação teórica necessária para o entendimento do ataque (meio frustrante, mas extremamente necessária) e a segunda irá descrever mecanismos de bypassing necessários para a exploração em ambientes atualizados. Os exemplos serão baseados na implementação de Doug Lea e Wolfram Gloger presente no pacote da glibc 2.9 [1].
A heap nada mais é do que uma região de memória reservada pelo sistema operacional para cada processo armazenar os dados referentes à variáveis alocadas dinamicamente usando as chamadas de sistema mmap(reserva uma nova área) ou brk(libera uma determinada área) através de funções da glibc como malloc(), calloc(), realloc() e free(). Cada processo mapeado em memória possui a sua região de heap privada. A seguir, podemos observar um exemplo de código que faz uso da heap:

#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *argv[]) {
        char *buffer;

        /*
            Cria uma porção de 200 bytes na heap e armazena o endereço
            para esta nova porção na variável buffer. Faz uma chamada de
            sistema mmap.Podemos acompanhar esse fluxo de chamadas
            de sistemas através do comando strace.
       */

        buffer = (char *) malloc (200 * sizeof(char));   

        /*
            Avisa ao sistema operacional que a porção armazenada no endereço
            "buffer" não é mais necessária, através da chamada de sistema brk.
        */
        free(buffer);
        return 0;
}

.
Na literatura e em diversos advisories, quando se fala de “heap overflow“, de uma forma geral, a intenção é se referir a buffer overflow em qualquer porção de memória diferente da pilha, que tenha permissão de escrita. Isso é algo a se levar em consideração já que muitas vezes iremos estudar códigos que atacam regiões diferentes da heap e serão classificados como “heap based vulnerabilities“.

A motivação para explorar essa categoria de vulnerabilidades consiste em dois argumentos:
.
- Linha do tempo: os ataques à heap são mais recentes em relação aos baseados na pilha, com isso, existem menos mecanismos de proteção internos aos sistemas operacionais (falo quantitativamente e não qualitativamente). A heap é usada por programas que necessitam de uso intensivo de memória, portanto projetar um mecanismo de proteção para essa área nos leva ao dilema de segurança versus performance, pois qualquer verificação de segurança adicionada nessa camada será executada inúmeras vezes, introduzindo um overhead em processos que fazem uso intensivo da heap (banco de dados, servidores web, servidores DNS …).

- Complexidade: com uma busca rápida em qualquer sistema de indexação de vulnerabilidades, percebemos que existem bem mais explorações bem sucedidas e publicadas, usando ataques baseados na pilha do que na heap. Isso acontece devido a complexidade envolvida no processo de busca e exploração de falhas no uso da heap. Essa complexidade é um fator decisivo no tempo de vida do 0-day.

Para iniciarmos nosso estudo é necessário uma visão geral do sistema de gerenciamento de memória alocada dinâmicamente projetado por Doug Lea e Wolfram Gloger, usado na maioria das distribuições de Linux. Esse estudo é necessário, pois as técnicas para exploração de problemas na heap se baseiam justamente na forma como as funções da glibc tratam as porções de memória alocadas.

O sistema de alocação de memória usado no Linux, através da glibc, não é o mais otimizado que existe, porém com certeza ele está entre um dos mais flexíveis, portáveis e aceitáveis em termos de conservação de espaço em memória. Balanceando consistentemente esses fatores, temos um bom alocador, em termos gerais, para uso em programas que requerem um uso intensivo do recurso de alocação dinâmica de memória.

As propriedades do algoritmo de alocação variam em quatro modos de acordo com a quantidade de memória solicitada:

- Para requisições menores que 64 bytes é usado um alocador baseado em cache, para ser possível uma rápida limpeza da memória quando essas não forem mais necessárias;
- Para requisições intermediárias entre 64 bytes e 512 bytes o algoritmo se adapta a situação do ambiente para escolha da melhor solução para a situação.
- Para requisições de porções maiores que 512 bytes é usado um algoritmo best-fit allocator [2] puro e tradicional (será explicado mais na frente).
- Para requisições maiores que 128 Kb, malloc delega a requisição para o gerenciador de memória do sistema (se esse suportar, no caso do Linux é suportado).

Para indexar certa quantidade de memória alocada, malloc adiciona um cabeçalho que contém a informação da quantidade de memória reservada para aquele segmento, esse cabeçalho será usado para identificação, localização e liberação dessa porção de memória.

Dependendo do estado da porção (livre ou em uso), o cabeçalho pode assumir dois formatos:
.
1) Cabeçalho para porções em uso:

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if not allocated        | |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                       |M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             User data starts here...                          .
            .                                                               .
            .             (malloc_usable_size() bytes)                      .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk                                     |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

.
2) Cabeçalho para porções livres:

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if not allocated        | |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                       |M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Forward Pointer                                   |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Backward Pointer                                  |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            .                                                               .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk                                     |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

.
Em comum, ambas as estruturas possuem o tamanho da porção alocada e a informação do tamanho da porção imediatamente anterior caso essa esteja livre. O cabeçalho de uma porção livre possui mais dois campos que são ponteiros para a porção livre anterior e posterior, formando uma lista duplamente encadeada. Os dois bits menos significativos do segundo byte do cabeçalho corresponde a uma indicação se a porção anterior estar livre (bit “P”) e se a gerencia da porção atual foi delegada ao sistema operacional (bit “M”).

A seguir é apresentada a estrutura de dados usada pela glibc para representar uma porção de memória, nela podemos visualizar os campos usados pelos quatro modos de alocação de memória (nós só iremos trabalhar com porções menores que 512 bytes).
.

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

.
Lembrando que dentro do campo “size” da estrutura existem os bits de controle da porção. (esses bits são retirados desse campo através de mascaras).

Um ponto chave é a forma como as porções livres são organizadas e re-aproveitadas na heap. Para otimizar a busca por porções livres de memória o sistema organiza essas em forma de lista duplamente encadeada como mostrado na figura 02.

.
A figura 2 mostra cinco porções alocadas na heap. As porções em azul estão em uso e as em cinza são as livres que possuem links em seus cabeçalhos, dando forma a lista encadeada. A porção de endereço 0x80c5090 é o elemento raiz da lista de porções livres, todo o processo ao iniciar a sua região de heap já cria esse elemento.

O processo de alocação é baseado no algoritmo “Best Fit Allocation” [2], através da pesquisa na lista encadeada de qual a menor porção de memória livre que comporta o tamanho solicitado.

O algoritmo de liberação de uma determinada porção de memória é parte fundamental dentro o sistema de gerencia da heap. Esse algoritmo é responsável pela reciclagem da memória de forma eficiente, observando o estado da heap no momento da liberação para realização de otimizações, garantindo um melhor aproveitamento do espaço em memória e preparando o espaço liberado para ser reaproveitado. O processo de liberação de memória é responsável pela execução de “merges“, evitando uma fragmentação desnecessária da heap. Quanto mais fragmentada a heap mais custoso será o processo de alocação de memória (uma lista maior para fazer busca).

Fiz um “artifício técnico” (a.k.a. gambiarra), para melhor visualização da organização da heap usando a própria estrutura da glibc (vou disponibilizar todo o código dos experimentos [aqui]). São basicamente duas funções:

- __pretty_print_chunk(): Recebe por parâmetro a estrutura da porção e imprime na tela o seu cabeçalho.

void __pretty_print_chunk (struct malloc_chunk *p, int chunk_id) {
  printf("::. Manipulando head do chunk_%02d: \n\n", chunk_id);
  printf("\t- Endereço do chunk:                       [%#x]\n", (uint) p);
  printf("\t- Tamanho do elemento anterior (se livre): [%d]\n" , p->prev_size);
  printf("\t- Tamanho do elemento atual:               [%d]\n" , chunksize(p));
  printf("\t- Foward link:                             [%#x]\n", (uint)p->fd);
  printf("\t- Backward link:                           [%#x]\n", (uint)p->bk);
  printf("\n");
}

- __malloc_char_chunk(): Cria uma nova porção na heap.

struct malloc_chunk *__malloc_char_chunk(uint size) {
  char *temp_buffer = (char *)malloc(size * sizeof(char));
  memset(temp_buffer, 'A', size/2);
  return (struct malloc_chunk *)(temp_buffer - 0x8);
}

.
Usando essas funções conseguimos ter uma interface para visualização das porções alocadas na heap. Vamos usar essa interface para criar quatro porções na memória e vamos liberar a primeira e a terceira porção.
.

int main (int argc, char *argv[]) {
  struct malloc_chunk *chunk_01, *chunk_02,*chunk_03,*chunk_04;
  chunk_01 = __malloc_char_chunk(BUFFER_SIZE);
  chunk_02 = __malloc_char_chunk(BUFFER_SIZE);
  chunk_03 = __malloc_char_chunk(BUFFER_SIZE);
  chunk_04 = __malloc_char_chunk(BUFFER_SIZE);
  free((char *)((uint)chunk_01 + 0x8)); // O free() recebe o endereço do inicio
  free((char *)((uint)chunk_03 + 0x8)); // região de dados da porção
  __pretty_print_chunk(chunk_01, 1);
  __pretty_print_chunk(chunk_02, 2);
  __pretty_print_chunk(chunk_03, 3);
  __pretty_print_chunk(chunk_04, 4);
}

.

::. Manipulando head do chunk_01:

        - Endereço do chunk:                       [0x8cd1680]
        - Tamanho do elemento anterior (se livre): [0]
        - Tamanho do elemento atual:               [208]
        - Foward link:                             [0x80c5090]
        - Backward link:                           [0x8cd1820]

::. Manipulando head do chunk_02:

        - Endereço do chunk:                       [0x8cd1750]
        - Tamanho do elemento anterior (se livre): [208]
        - Tamanho do elemento atual:               [208]
        - Foward link:                             [0x41414141]
        - Backward link:                           [0x41414141]

::. Manipulando head do chunk_03:

        - Endereço do chunk:                       [0x8cd1820]
        - Tamanho do elemento anterior (se livre): [0]
        - Tamanho do elemento atual:               [208]
        - Foward link:                             [0x8cd1680]
        - Backward link:                           [0x80c5090]

::. Manipulando head do chunk_04:

        - Endereço do chunk:                       [0x8cd18f0]
        - Tamanho do elemento anterior (se livre): [208]
        - Tamanho do elemento atual:               [208]
        - Foward link:                             [0x41414141]
        - Backward link:                           [0x41414141]

.
Observe a lista duplamente encadeada de porções livres na heap.
.

O que acontece se nós liberarmos a segunda porção de memória?
.
O algoritmo do free() irá detectar que as porções três e um também estão livre e criará uma única porção que corresponde a soma das três regiões (um, dois e três).

::. Manipulando head do chunk_01:

        - Endereço do chunk:                       [0x8cfe680]
        - Tamanho do elemento anterior (se livre): [0]
        - Tamanho do elemento atual:               [624]
        - Foward link:                             [0x80c5090]
        - Backward link:                           [0x80c5090]

::. Manipulando head do chunk_02:

        - Endereço do chunk:                       [0x8cfe750]
        - Tamanho do elemento anterior (se livre): [208]
        - Tamanho do elemento atual:               [208]
        - Foward link:                             [0x41414141]
        - Backward link:                           [0x41414141]

::. Manipulando head do chunk_03:

        - Endereço do chunk:                       [0x8cfe820]
        - Tamanho do elemento anterior (se livre): [416]
        - Tamanho do elemento atual:               [208]
        - Foward link:                             [0x41414141]
        - Backward link:                           [0x41414141]

::. Manipulando head do chunk_04:

        - Endereço do chunk:                       [0x8cfe8f0]
        - Tamanho do elemento anterior (se livre): [624]
        - Tamanho do elemento atual:               [208]
        - Foward link:                             [0x41414141]
        - Backward link:                           [0x41414141]

Reparem que na porção quatro diz que existe uma porção livre com 624 bytes (3 * 208) na porção imediatamente anterior. Se obsevarmos o cabeçalho dessa porção vamos verificar que o merge das porções foi realizado com sucesso.

.
Na Figura 04 mostramos a região em que será realizado o merge. Após a liberação da porção 2 será criada uma nova porção contendo a soma das porções 1, 2 e 3, como mostrado na figura abaixo.
.

.
Nesse tipo de merge, o algoritimo fez alterações na porção livre que estava imediatamente abaixo da porção três para apontar para a nova porção e fez alteração na nova porção para apontar para a porção que era apontada pela porção três.
.

(porção 3)->bd + 8    < -  (porção 3)->fd
(porçao 3)->fd + 12   < -  (porção 3)->bd

.
É justamente explorando essas heurísticas de merge, que conseguimos tirar proveito de falhas no uso da heap. E é ai que a brincadeira começa …

Imagine se pudéssemos manipular o cabeçalho da porção imediatamente após da que nós iríamos liberar (a porção 3 do exemplo anterior)… Isso significa que nós poderíamos manipular os valores dos links usados para ligar a lista de porções livres apos a operação de merge.

Quando é possível preencher uma porção na heap com mais dados do que essa foi inicialmente planejada para comportar, conseguimos sobrescrever regiões da porção de memória conseguinte, colocando um cabeçalho falso nessa seção e criando porções adjacentes falsas, de forma que quando a função free() for chamada recebendo como parâmetro o endereço para essa porção de memória, ela irá buscar informações no header falso e tentar realizar a operação de merge, com isso conseguimos realizar o ataque sobrescrevendo uma posição qualquer na memória que tenha permissão de escrita com um conteúdo especificado (Já que a “porção 3″ será injetada na “porção 2″ através da “porção 1″ que está vulnerável \O/).

É … não é simples de entender mesmo não … leia e releia o parágrafo acima. Desenhe no papel que talvez fique mais fácil. Tudo gira em torno do funcionamento do merge. Eu também pensei a mesma coisa: “O cara que fez isso pela primeira vez devia ter muitas drogas em mente.”

Agora, que já temos idéia na prática como o algoritmo de merge funciona, vamos montar um ambiente com dois buffers alocados na heap em que o primeiro está vulnerável e recebe dados direto da linha de comando sem nenhuma espécie de verificação.

Antes de tudo vamos desabilitar algumas proteções existentes no nosso Linux, fazer o bypass desses mecanismos de segurança não faz parte do escopo dessa primeira parte do artigo. Em breve irei escrever um artigo mostrando como funcionam esses mecanismos de proteção e se possível como fazer um bypass de forma eficiente e confiável (não tem quem goste dessas técnicas probabilísticas). Esse artigo sobre as técnicas usadas para proteção da memória, será útil para todos os posts de vulndev publicados aqui no blog.
.
Primeiro vamos desabilitar ASLR (Adress Space Layout Randomization):

root@envy:/# /bin/echo 0 > /proc/sys/kernel/randomize_va_space

.
Habilitar o modo de depuração do mecanismo de proteção em tempo de execução interno a glibc:

export MALLOC_CHECK_=1

.
O código usado como exemplo para todo o resto do artigo será o seguinte:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUFFER_SIZE 200

int main (int argc, char *argv[]) {
  char *buffer_01, *buffer_02;

  buffer_01 = (char *) malloc(BUFFER_SIZE*sizeof(char));
  buffer_02 = (char *) malloc(BUFFER_SIZE*sizeof(char));

  strcpy(buffer_01, argv[1]);

  free(buffer_02);

  return 1;
}

Podemos sobrescrever o “buffer_02” através da vulnerabilidade no “buffer_01“, com isso nós iremos criar duas porções de memória falsas ao redor de “buffer_02“, de forma que quando dermos um free() nessa porção possamos induzir o merge dessas três áreas (fake_01, buffer_02 e fake_02) e com isso explorarmos a falha. O layout do nosso exploit irá ficar como na figura a seguir.

Não se esquecer que devemos sobrescrever o cabeçalho da porção dois para sinalizarmos que essa possui uma porção anterior livre, através da flag “P” e ajustarmos o campo de tamanho para a porção terminar no inicio da segunda porção falsa (a que irá conter os endereços). Sem isso, o processo de merge não será iniciado.

Com uma pequena ajuda do interpretador Python podemos construir o nosso exploit.
.

./heap `python -c 'print "A"*184    +    "\xff"*8+"A"*8    +
  "\xf8\xff\xff\xff"+"\xf0\xff\xff\xff"    +    "\xff"*8 + "AAAA" + "BBBB"'`

.
Com o código acima nós conseguiríamos sobrescrever porções específicas do nosso interesse na memória (return pointer, locks, global offset table … ): *(AAAA + 12) = BBBB
.
Quando executamos ele temos:

mabj@envy:~/Documents/project/heap_based_overflow$ ./heap `python -c 'print "A"*188+"\xff"*4+"A"*8+"\xf8\xff\xff\xff"+"\xf0\xff\xff\xff"+"\xff"*8 + "AAAA" + "BBBB"'`
malloc: using debugging hooks
buffer_01 (0x80c8690) - size: [0x15] previous [0xffffffd1]
buffer_02 (0x80c8760)- size: [0xfffffff8] previous [0xfffffff0]

*** glibc detected *** ./heap: free(): invalid pointer: 0x080c8760 ***

.
Essa mensagem ocorre devido a seguinte verificação de segurança interna a glibc:
.

  /* Little security check which won't hurt performance: the
     allocator never wrapps around at the end of the address space.
     Therefore we can exclude some size values which might appear
     here by accident or by "design" from some intruder.  */
if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
    || __builtin_expect (misaligned_chunk (p), 0))
  {
    errstr = "free(): invalid pointer";
  errout:
    malloc_printerr (check_action, errstr, mem);
    return;
  }

.
Pronto. É aqui que chegamos ao fim da primeira etapa no nosso estudo a respeito de vulnerabilidades baseadas na heap. Já sabemos o que é a heap, como funciona os mecanismos de gerencia da heap e onde estão os pontos de exploração. No próximo passo, vamos focar no estudo dos mecanismos de proteção e na exploração.

<frustation mode=”on”>
Tudo que foi mostrado até agora foram os fundamento para exploração de vulnerabilidades baseadas na heap. Todos os exploit writers e heap lovers já passaram por tudo o que foi descrito acima até chegar no estado que vamos mostrar no segundo tempo do jogo (VD03.2). A quatro anos atrás o conhecimento acumulado até agora seria o suficiente para a nossa exploração. Hoje em dia, a glibc mais recente possui mecanismos de proteção, como o mostrado acima, que impede nosso ataque. Mas não desanimem! O ‘#’ já está mais perto do que vocês imaginam.
</frustation>
.
“Em balanço está a Força. A Escuridão e a Luz. Sem um, não há o outro. O Lado Negro tentador é. Rápido, fácil no início, mas uma armadilha é o Lado Negro. Mau, corrupto. Uma vez que se começa no Lado Negro, para sempre dominará seu destino. Para o caminho da Luz, paciência você precisa. Controle. Paz e harmonia ele é.”

.

TO BE CONTINUED …

Referências:

[1] http://www.gnu.org/software/libc/
[2] http://g.oswego.edu/dl/html/malloc.html
[3] The Shellcoder’s handbook, segunda edição, capitulo 5 (Gera, FX e Chris Anley)
[4] http://www.w00w00.org/files/articles/heaptut.txt
[5] http://www.phrack.org/issues.html?issue=61&id=6&mode=txt
[6] http://www.phrack.org/issues.html?issue=57&id=8&mode=txt
[7] http://www.phrack.org/issues.html?issue=57&id=9&mode=txt
[8] http://sourceware.org/glibc/

Em Abril iniciei um projeto open source chamado Ruby Neuron, esse projeto tem por objetivo fazer uma ligação entre as novas técnicas na área de Redes Neurais Artificiais (RNAs) e a aplicação destas para solução de problemas reais encontrados na sociedade. A inspiração inicial surgiu da observação que a ciência avança bem rápido, descobrindo novas técnicas e novas otimizações de algorítimos, e essas não são usadas nos frameworks tradicionais para melhoria de performances e resultados. Outro objetivo, não menos importante que o primeiro, é desfazer o estigma relacionado a complexidade relacionada ao uso das técnicas de inteligencia computacional.

O Ruby Neuron além de fornecer uma poderosa ferramenta para classificação e inferência ainda funciona como uma API flexível para simulação e testes de novos modelos de Redes Neurais Artificiais. Com isso teremos uma ferramenta para auxílio a pesquisa e desenvolvimento na área de inteligencia computacional.

O escopo do projeto será restrito a Redes Neurais Artificiais, não se estendendo a outras técnicas de computação inteligente (tenho experiências negativas de projetos generalistas). O mesmo tempo dedicado a desenvolvimento do código será dedicado a infra-estrutura, documentação e testes, de forma a construirmos uma boa base de exemplos e documentos disponibilizados para a comunidade.

O escopo e a infra-estrutura do projeto já estão formados, em breve será lançado o primeiro release e com isso espero receber novos usuários, desenvolvedores e pesquisadores.