diff options
Diffstat (limited to 'src/analysis/disass/dragon.c')
-rw-r--r-- | src/analysis/disass/dragon.c | 541 |
1 files changed, 541 insertions, 0 deletions
diff --git a/src/analysis/disass/dragon.c b/src/analysis/disass/dragon.c new file mode 100644 index 0000000..2fcf830 --- /dev/null +++ b/src/analysis/disass/dragon.c @@ -0,0 +1,541 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * dragon.c - capacités apportées par la lecture du livre du dragon + * + * Copyright (C) 2016 Cyrille Bagard + * + * This file is part of Chrysalide. + * + * OpenIDA is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3 of the License, or + * (at your option) any later version. + * + * OpenIDA is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Foobar. If not, see <http://www.gnu.org/licenses/>. + */ + + +#include "dragon.h" + + +#include <assert.h> +#include <malloc.h> + + + +/* ---------------------------- ENCAPSULATION DES NOEUDS ---------------------------- */ + + +/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */ +struct _dragon_node +{ + GArchInstruction *first; /* Arrivée d'un lien (début) */ + GArchInstruction *last; /* Départ d'un lien (fin) */ + + bitfield_t *bits; /* Représentation par masque */ + +}; + + +/* Définition des blocs d'allocation */ +#define NODE_ALLOC_SIZE 100 + + +/* Dénombre le nombre de noeuds présents dans une routine. */ +static dragon_node *create_dragon_nodes(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, size_t *); + +/* Supprime de la mémoire tous les noeuds détectés. */ +static void delete_dragon_nodes(dragon_node *, size_t); + +/* Termine l'initialisation de noeuds trouvés dans une routine. */ +static void init_mask_for_nodes(dragon_node *, size_t); + + + +/* ---------------------------- ENCAPSULATION DES NOEUDS ---------------------------- */ + + +/* Concentration de tous les efforts */ +struct _dragon_knight +{ + dragon_node *nodes; /* Noeuds mis en place */ + size_t count; /* Taille de la liste */ + +}; + + + +/* ---------------------------------------------------------------------------------- */ +/* DECOUPAGES DE CODE EN NOEUDS */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : proc = ensemble d'instructions à parcourir. * +* coverage = zone de couverture où rechercher des instructions.* +* range = zone de couverture de la routine analysée. * +* start = adresse du début de l'analyse. * +* count = taille de la liste de noeuds retournés. [OUT] * +* * +* Description : Dénombre le nombre de noeuds présents dans une routine. * +* * +* Retour : Liste de noeuds initialisés de façon incomplète. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, size_t *count) +{ + dragon_node *result; /* Liste à créer et renvoyer */ + size_t allocated; /* Dimensionnement en mémoire */ + GArchInstruction *last; /* Mémorisation du passé */ + GArchInstruction *iter; /* Boucle de parcours */ + const mrange_t *irange; /* Emplacement d'instruction */ + InstructionLinkType *types; /* Type de lien entre instr. */ + size_t scount; /* Nombre de liens de dest. */ + size_t i; /* Boucle de parcours */ + dragon_node *new; /* Nouvel élément à créer */ + + result = NULL; + *count = 0; + + allocated = 0; + + for (last = NULL, iter = g_arch_processor_find_covered_instr_by_address(proc, coverage, start); + iter != NULL; + last = iter, iter = g_arch_instruction_get_next_iter(iter /* FIXME : list*/, iter, ~0)) + { + /* L'instruction sort-elle des clous ? */ + + irange = g_arch_instruction_get_range(iter); + + if (!mrange_contains_mrange(range, irange)) + break; + + /* Analyse des sources */ + + if (result == NULL) + { + (*count)++; + + if (*count >= allocated) + { + allocated += NODE_ALLOC_SIZE; + result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node)); + } + + new = &result[*count - 1]; + + new->first = iter; + + } + else + { + scount = g_arch_instruction_get_sources(iter, NULL, &types); + if (scount == 0) continue; + + for (i = 0; i < scount; i++) + switch (types[i]) + { + case ILT_EXEC_FLOW: + case ILT_JUMP: + case ILT_CASE_JUMP: + case ILT_JUMP_IF_TRUE: + case ILT_JUMP_IF_FALSE: + + if (*count > 0) + result[*count - 1].last = last; + + (*count)++; + i = scount; + + if (*count >= allocated) + { + allocated += NODE_ALLOC_SIZE; + result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node)); + } + + new = &result[*count - 1]; + + new->first = iter; + + break; + + default: + break; + + } + + } + + } + + if (*count > 0) + result[*count - 1].last = last; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à traiter. * +* * +* Description : Supprime de la mémoire tous les noeuds détectés. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void delete_dragon_nodes(dragon_node *nodes, size_t count) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < count; i++) + delete_bit_field(nodes[i].bits); + + free(nodes); + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à traiter. * +* * +* Description : Termine l'initialisation de noeuds trouvés dans une routine. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void init_mask_for_nodes(dragon_node *nodes, size_t count) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < count; i++) + nodes[i].bits = create_bit_field(count, i > 0); + + set_in_bit_field(nodes[0].bits, 0, 1); + +} + + +/****************************************************************************** +* * +* Paramètres : node = noeud de code à considérer. * +* first = instruction de départ à renseigner ou NULL. [OUT] * +* last = instruction d'arrivée à renseigner ou NULL. [OUT] * +* * +* Description : Fournit les instructions bornant un noeud de code. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void get_dragon_node_bounding_instructions(dragon_node *node, GArchInstruction **first, GArchInstruction **last) +{ + if (first != NULL) + *first = node->first; + + if (last != NULL) + *last = node->last; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* * +* Description : Fournit un noeud particulier à partir d'une liste. * +* * +* Retour : Noeud ciblé. * +* * +* Remarques : - * +* * +******************************************************************************/ + +dragon_node *get_dragon_node(dragon_node *nodes, size_t index) +{ + return nodes + index; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* node = noeud ciblé au sein de cette liste. * +* * +* Description : Fournit l'indice d'un noeud particulier à partir d'une liste.* +* * +* Retour : Indice du noeud ciblé. * +* * +* Remarques : - * +* * +******************************************************************************/ + +size_t get_dragon_node_index(dragon_node *nodes, dragon_node *node) +{ + return node - nodes; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à parcourir. * +* final = précise si l'instruction visée est la première. * +* instr = instruction à retrouver en tant que début de noeud. * +* * +* Description : Recherche un noeud selon son intruction de départ. * +* * +* Retour : Noeud trouvé ou NULL si aucune trouvaille. * +* * +* Remarques : - * +* * +******************************************************************************/ + +dragon_node *find_node_for_instruction(dragon_node *nodes, size_t count, bool final, const GArchInstruction *instr) +{ + dragon_node *result; /* Résultat des recherches */ + const mrange_t *irange; /* Emplacement d'instruction */ + + int find_node_from_range(const mrange_t *range, const dragon_node *node) + { + int status; /* Bilan à retourner */ + const mrange_t *nrange; /* Emplacement de noeud */ + + nrange = g_arch_instruction_get_range(final ? node->last : node->first); + + status = cmp_mrange(range, nrange); + + return status; + + } + + irange = g_arch_instruction_get_range(instr); + + result = bsearch(irange, nodes, count, sizeof(dragon_node), (__compar_fn_t)find_node_from_range); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à traiter. * +* * +* Description : Détermine toute la chaîne hiérarchique de domination. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void compute_all_dominators(dragon_node *nodes, size_t count) +{ + bitfield_t *inter; /* Intersection de dominations */ + bool changed; /* Note un changement qq part */ + size_t k; /* Boucle de parcours #1 */ + dragon_node *node; /* Noeud à traiter */ + dragon_node *predecessor; /* Noeud prédécesseur direct */ + GArchInstruction **srcs; /* Instructions d'origine */ + InstructionLinkType *types; /* Type de lien entre instr. */ + size_t scount; /* Nombre de liens de source */ + size_t i; /* Boucle de parcours #2 */ + + inter = create_bit_field(count, false); + + do + { + changed = false; + + for (k = 1; k < count; k++) + { + node = &nodes[k]; + + set_all_in_bit_field(inter); + + scount = g_arch_instruction_get_sources(node->first, &srcs, &types); + assert(scount > 0); + + for (i = 0; i < scount; i++) + switch (types[i]) + { + case ILT_EXEC_FLOW: + case ILT_JUMP: + case ILT_CASE_JUMP: + case ILT_JUMP_IF_TRUE: + case ILT_JUMP_IF_FALSE: + + predecessor = find_node_for_instruction(nodes, count, true, srcs[i]); + + + printf(" -- finding pred @ 0x%08x -> 0x%08x :: %p\n", + (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual, + (unsigned int)g_arch_instruction_get_range(srcs[i])->addr.virtual, + predecessor); + + + + if (predecessor == NULL) break; + + and_bit_field(inter, predecessor->bits); + break; + + default: + break; + + } + + set_in_bit_field(inter, k, 1); + + if (!is_bit_field_equal_to(node->bits, inter)) + { + copy_bit_field(node->bits, inter); + changed = true; + } + + } + + } + while (changed); + + delete_bit_field(inter); + +} + + +/****************************************************************************** +* * +* Paramètres : node = noeud représentant une portion de code à consulter. * +* * +* Description : Fournit la liste des noeuds dominés par un noeud. * +* * +* Retour : Champ de bits en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +const bitfield_t *get_domination_bits(const dragon_node *node) +{ + return node->bits; + +} + + + + + + +/* ---------------------------------------------------------------------------------- */ +/* ENCAPSULATION DES NOEUDS */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : proc = ensemble d'instructions à parcourir. * +* coverage = zone de couverture où rechercher des instructions.* +* range = zone de couverture de la routine analysée. * +* start = adresse du début de l'analyse. * +* * +* Description : Attaque la complexité d'un code en créant des noeuds. * +* * +* Retour : Définition d'un complexe de noeuds établis. * +* * +* Remarques : - * +* * +******************************************************************************/ + +dragon_knight *begin_dragon_knight(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start) +{ + dragon_knight *result; /* Données à retourner */ + dragon_node *nodes; /* Noeuds mis en place */ + size_t count; /* Nombre de ces noeuds */ + + result = NULL; + + nodes = create_dragon_nodes(proc, coverage, range, start, &count); + + if (nodes != NULL) + { + init_mask_for_nodes(nodes, count); + + result = (dragon_knight *)calloc(1, sizeof(dragon_knight)); + + result->nodes = nodes; + result->count = count; + + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : knight = données représentant une complexité traitée. * +* * +* Description : Supprime de la mémoire les données d'une complexité de code. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void end_dragon_knight(dragon_knight *knight) +{ + delete_dragon_nodes(knight->nodes, knight->count); + + free(knight); + +} + + +/****************************************************************************** +* * +* Paramètres : knight = données représentant une complexité à considérer. * +* nodes = noeuds de code associés à récupérer. [OUT] * +* count = taille de cette liste de noeuds. [OUT] * +* * +* Description : Fournit les éléments utiles à un traitement de blocs de code.* +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void get_dragon_knight_content(dragon_knight *knight, dragon_node **nodes, size_t *count) +{ + *nodes = knight->nodes; + *count = knight->count; + +} |