/* Chrysalide - Outil d'analyse de fichiers binaires
* macro.c - vue macroscopique des liens entre blocs d'instructions
*
* Copyright (C) 2012-2013 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 .
*/
#include "macro.h"
#include
#include
#include
#include "../blocks/flow.h"
#include "../blocks/virtual.h"
/* ------------------------ COUVERTURE D'UNE ZONE A DECOUPER ------------------------ */
/* Bornes d'une zone à couvrir */
typedef struct _code_coverage
{
bool initial; /* Couverture racine ? */
mrange_t range; /* Couverture totale */
vmpa2t start; /* Position butoir de début */
vmpa2t *ends; /* Positions butoir de fin */
size_t ends_count; /* Quantité de fins possibles */
unsigned long *processed; /* Octets traités dans la zone */
size_t allocated; /* Taille de la cartographie */
} code_coverage;
/* Met en place les délimitations d'une zone de code. */
static code_coverage *create_code_coverage(const mrange_t *);
/* Crée une copie d'une couverture de zone de code. */
static code_coverage *dup_code_coverage(const code_coverage *, const vmpa2t *);
/* Détruit des délimitations d'une zone de code. */
static void delete_code_coverage(code_coverage *);
/* Précise la position de départ courante pour une analyse. */
static const vmpa2t *get_code_coverage_start_addr(const code_coverage *);
/* Indique si une adresse est hors zone ou non. */
static bool code_coverage_stop_here(const code_coverage *coverage, const vmpa2t *);
/* Ajoute une adresse butoir pour la zone à couvrir. */
static bool add_ending_address_code_coverage(code_coverage *, const vmpa2t *);
/* Indique si une zone donnée n'a jamais été traitée ou non. */
static bool is_range_processed_in_coverage(const code_coverage *, const mrange_t *);
/* Marque une série d'octets comme ayant été traités. */
static void mark_range_as_processed_in_coverage(code_coverage *, const GArchInstruction *);
/* ------------------------- SUIVI DES FLOTS D'INSTRUCTIONS ------------------------- */
/* Indications sur une branche */
typedef struct _branch_info
{
vmpa2t *hops; /* Jalons de la branche */
size_t count; /* Quantité de ces jalons */
vmpa2t entry; /* Valeur du jalon d'entrée */
} branch_info;
/* Initialise le suivi d'une branche de flot d'exécution. */
static void init_branch_info(branch_info *);
/* Acte la fin d'un suivi d'une branche de flot d'exécution. */
static void clean_branch_info(branch_info *);
/* Indique si une adresse est retenue comme point de passage. */
static bool is_addr_in_branch(const branch_info *, const vmpa2t *);
/* Ajoute un nouveau jalon dans l'exécution d'une branche. */
static bool add_hop_into_branch(branch_info *, const vmpa2t *);
/* Retourne le premier point d'exécution d'une branche donnée. */
static const vmpa2t *get_entry_to_branch(const branch_info *);
/* Identifie les différents points de passage d'une branche. */
static void find_next_hops(GArchInstruction *, const vmpa2t *, const code_coverage *, branch_info *);
/* Retrouve le point de ralliement entre deux branches. */
static bool compute_first_common_addr(const branch_info *, const branch_info *, vmpa2t *);
/* Groupement de branches et d'indications */
typedef struct _branch_group
{
branch_info *branches; /* Liste des branches */
size_t count; /* Taille de cette liste */
} branch_group;
/* Initialise le suivi d'un ensemble de branches. */
static void init_branch_group(branch_group *);
/* Acte la fin d'un suivi d'un ensemble de branches. */
static void clean_branch_group(branch_group *);
/* Ajoute une branche à un ensemble de branches en place. */
static branch_info *extend_branch_group(branch_group *);
/* Retrouve le point de ralliement entre un groupe de branches. */
static bool compute_first_common_addr_in_group(const branch_group *, vmpa2t *);
/* --------------------------- DECOUPAGE EN BLOCS DE CODE --------------------------- */
/**
* Procédure d'ajout de blocs : pour le premier, on conserve le bloc en mémoire
* et on attend. Si rien ne suit, il constitura l'unique retour. Sinon, on
* l'ajoute à partir de la sauvegarde, et le reste suit.
*/
#define DELAYED_BLOCK_ADDING(res, cache, blk) \
do \
{ \
if (res == NULL) \
{ \
if (cache == NULL) \
cache = blk; \
else \
{ \
res = g_virtual_block_new(); \
g_virtual_block_add_child(G_VIRTUAL_BLOCK(res), cache); \
} \
} \
\
if (res != NULL) \
g_virtual_block_add_child(G_VIRTUAL_BLOCK(res), blk); \
\
} \
while (0)
/* Procède à la création d'un bloc d'instructions simple. */
static GInstrBlock *build_instruction_block_simple(GArchInstruction *, code_coverage *, GArchInstruction **, GArchInstruction *);
/* Procède à la définition d'un bloc d'instructions selectif. */
static GInstrBlock *build_instruction_blocks_case(GArchInstruction *, code_coverage *, const branch_group *, vmpa2t *);
/* Procède à la définition d'un bloc d'instruction if/then/else. */
static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *, code_coverage *, const branch_info *, const branch_info *, vmpa2t *);
/* Procède à la définition d'un bloc d'instructions d'exception. */
static void add_instruction_blocks_except(GInstrBlock **, GInstrBlock **, GArchInstruction *, code_coverage *, const branch_group *, const branch_info *);
/* Procède à la définition de bloc regroupant des instructions. */
static GInstrBlock *build_instruction_blocks(GArchInstruction *, code_coverage *);
/* ---------------------------------------------------------------------------------- */
/* COUVERTURE D'UNE ZONE A DECOUPER */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : range = définition de la zone à couvrir. *
* *
* Description : Met en place les délimitations d'une zone de code. *
* *
* Retour : Couverture d'une zone de code. *
* *
* Remarques : - *
* *
******************************************************************************/
static code_coverage *create_code_coverage(const mrange_t *range)
{
code_coverage *result; /* Couverture à retourner */
phys_t length; /* Taille de la zone couverte */
size_t requested; /* Nombre de mots à allouer */
result = (code_coverage *)calloc(1, sizeof(code_coverage));
result->initial = true;
copy_mrange(&result->range, range);
copy_vmpa(&result->start, get_mrange_addr(range));
result->ends = (vmpa2t *)calloc(1, sizeof(vmpa2t));
result->ends_count = 1;
compute_mrange_end_addr(range, &result->ends[0]);
length = get_mrange_length(range);
requested = length / sizeof(unsigned long);
if (length % sizeof(unsigned long) != 0) requested++;
result->processed = (unsigned long *)calloc(requested, sizeof(unsigned long));
result->allocated = requested;
return result;
}
/******************************************************************************
* *
* Paramètres : src = informations de couverture à consulter. *
* new = nouvelle position de début, plus profonde. *
* *
* Description : Crée une copie d'une couverture de zone de code. *
* *
* Retour : Couverture d'une zone de code copiée. *
* *
* Remarques : - *
* *
******************************************************************************/
static code_coverage *dup_code_coverage(const code_coverage *src, const vmpa2t *new)
{
code_coverage *result; /* Couverture à retourner */
size_t i; /* Boucle de parcours */
result = (code_coverage *)calloc(1, sizeof(code_coverage));
result->initial = false;
copy_mrange(&result->range, &src->range);
copy_vmpa(&result->start, new);
result->ends = (vmpa2t *)calloc(src->ends_count, sizeof(vmpa2t));
result->ends_count = src->ends_count;
for (i = 0; i < result->ends_count; i++)
copy_vmpa(&result->ends[i], &src->ends[i]);
/**
* Les blocs produits par le découpage sont à accès global, et ne sont donc pas
* la propriété d'une branche particulière.
* Il ne faut donc pas créer deux blocs identiques à partir de deux chemins
* différents ; aussi on partage la couverture de code plutôt que la copier.
* Et, par ailleurs, c'est plus simple & efficace.
*/
result->processed = src->processed;
return result;
}
/******************************************************************************
* *
* Paramètres : coverage = structure à libérer de la mémoire. *
* *
* Description : Détruit des délimitations d'une zone de code. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void delete_code_coverage(code_coverage *coverage)
{
free(coverage->ends);
if (coverage->initial)
free(coverage->processed);
free(coverage);
}
/******************************************************************************
* *
* Paramètres : coverage = informations de couverture à consulter. *
* *
* Description : Précise la position de départ courante pour une analyse. *
* *
* Retour : Position de départ pour une analyse d'une portion de zone. *
* *
* Remarques : - *
* *
******************************************************************************/
static const vmpa2t *get_code_coverage_start_addr(const code_coverage *coverage)
{
return &coverage->start;
}
/******************************************************************************
* *
* Paramètres : coverage = informations de couverture à consulter. *
* addr = localisation à tester. *
* *
* Description : Indique si une adresse est hors zone ou non. *
* *
* Retour : true si l'adresse ne doit pas être couverte, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool code_coverage_stop_here(const code_coverage *coverage, const vmpa2t *addr)
{
void *ptr; /* Résultat des recherches */
if (!mrange_contains_addr(&coverage->range, addr))
return true;
ptr = bsearch(addr, coverage->ends, coverage->ends_count,
sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa);
return (ptr != NULL);
}
/******************************************************************************
* *
* Paramètres : coverage = informations de couverture à compléter. *
* addr = localisation à ajouter. *
* *
* Description : Ajoute une adresse butoir pour la zone à couvrir. *
* *
* Retour : true si une insertion a été effectuée, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool add_ending_address_code_coverage(code_coverage *coverage, const vmpa2t *addr)
{
bool result; /* Bilan à retourner */
result = !code_coverage_stop_here(coverage, addr);
if (result)
{
coverage->ends = (vmpa2t *)realloc(coverage->ends, ++coverage->ends_count * sizeof(vmpa2t));
copy_vmpa(&coverage->ends[coverage->ends_count - 1], addr);
qsort(coverage->ends, coverage->ends_count, sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa);
}
return result;
}
/******************************************************************************
* *
* Paramètres : coverage = informations de couverture à consulter. *
* range = zone à interroger. *
* *
* Description : Indique si une zone donnée n'a jamais été traitée ou non. *
* *
* Retour : true si l'aire visée est vierge, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool is_range_processed_in_coverage(const code_coverage *coverage, const mrange_t *range)
{
bool result; /* Bilan à renvoyer */
phys_t diff; /* Décalage à appliquer */
size_t index; /* Cellule de tableau visée */
unsigned int remaining; /* Nombre de bits restants */
diff = compute_vmpa_diff(get_mrange_addr(&coverage->range), get_mrange_addr(range));
assert(diff < get_mrange_length(&coverage->range));
index = diff / (sizeof(unsigned long) * 8);
remaining = diff % (sizeof(unsigned long) * 8);
result = ((coverage->processed[index] & (1ul << remaining)) != 0);
return result;
}
/******************************************************************************
* *
* Paramètres : coverage = informations de couverture à consulter. *
* instr = instruction couvrant la zone à interroger. *
* *
* Description : Marque une série d'octets comme ayant été traités. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void mark_range_as_processed_in_coverage(code_coverage *coverage, const GArchInstruction *instr)
{
const mrange_t *range; /* Emplacement d'instruction */
phys_t diff; /* Décalage à appliquer */
size_t index; /* Cellule de tableau visée */
unsigned int remaining; /* Nombre de bits restants */
range = g_arch_instruction_get_range(instr);
diff = compute_vmpa_diff(get_mrange_addr(&coverage->range), get_mrange_addr(range));
assert(diff < get_mrange_length(&coverage->range));
index = diff / (sizeof(unsigned long) * 8);
remaining = diff % (sizeof(unsigned long) * 8);
coverage->processed[index] |= (1ul << remaining);
}
/* ---------------------------------------------------------------------------------- */
/* SUIVI DES FLOTS D'INSTRUCTIONS */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : info = informations à initialiser. *
* *
* Description : Initialise le suivi d'une branche de flot d'exécution. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void init_branch_info(branch_info *info)
{
memset(info, 0, sizeof(branch_info));
}
/******************************************************************************
* *
* Paramètres : info = informations à nettoyer. *
* *
* Description : Acte la fin d'un suivi d'une branche de flot d'exécution. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void clean_branch_info(branch_info *info)
{
if (info->hops != NULL)
free(info->hops);
}
/******************************************************************************
* *
* Paramètres : info = informations à consulter. *
* addr = position à rechercher. *
* *
* Description : Indique si une adresse est retenue comme point de passage. *
* *
* Retour : true si le jalon est déjà dans la liste, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool is_addr_in_branch(const branch_info *info, const vmpa2t *addr)
{
void *ptr; /* Résultat des recherches */
ptr = bsearch(addr, info->hops, info->count,
sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa);
return (ptr != NULL);
}
/******************************************************************************
* *
* Paramètres : info = informations de flot à compléter. *
* addr = localisation à ajouter. *
* *
* Description : Ajoute un nouveau jalon dans l'exécution d'une branche. *
* *
* Retour : true si une insertion a été effectuée, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool add_hop_into_branch(branch_info *info, const vmpa2t *addr)
{
bool result; /* Bilan à retourner */
result = !is_addr_in_branch(info, addr);
if (result)
{
if (info->count == 0)
copy_vmpa(&info->entry, addr);
info->hops = (vmpa2t *)realloc(info->hops, ++info->count * sizeof(vmpa2t));
copy_vmpa(&info->hops[info->count - 1], addr);
qsort(info->hops, info->count, sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa);
}
return result;
}
/******************************************************************************
* *
* Paramètres : info = informations de flot à consulter. *
* *
* Description : Retourne le premier point d'exécution d'une branche donnée. *
* *
* Retour : Point de départ d'une branche. *
* *
* Remarques : - *
* *
******************************************************************************/
static const vmpa2t *get_entry_to_branch(const branch_info *info)
{
return &info->entry;
}
/******************************************************************************
* *
* Paramètres : instrs = ensemble des instructions d'assemblage. *
* start = position du début de bloc. *
* coverage = liste des adresses de fin butoir. *
* count = nombre de sauts détectés. [OUT] *
* *
* Description : Identifie les différents points de passage d'une branche. *
* *
* Retour : Jalons dans le flot d'exécution. *
* *
* Remarques : - *
* *
******************************************************************************/
static void find_next_hops(GArchInstruction *instrs, const vmpa2t *start, const code_coverage *coverage, branch_info *info)
{
GArchInstruction *iter; /* Boucle de parcours #1 */
const mrange_t *range; /* Emplacement d'instruction */
GArchInstruction **dests; /* Instr. visée par une autre */
InstructionLinkType *types; /* Type de lien entre lignes */
size_t dcount; /* Nombre de liens de dest. */
size_t i; /* Boucle de parcours #2 */
size_t not_handled; /* Nombre d'éléments écartés */
printf(" ---- FN [ %p ] ---------------------------\n", info);
printf("CONTAINS ? %d\n", mrange_contains_addr(&coverage->range, start));
/* Si la position est déjà présente, on évite de boucler... */
if (!add_hop_into_branch(info, start))
{
printf(" ++ !add 0x%08x\n", (unsigned int)start->virtual);
return;
}
else
printf(" ++ add 0x%08x\n", (unsigned int)start->virtual);
/* On suit le flot jusqu'à la prochaine bifurcation */
for (iter = g_arch_instruction_find_by_address(instrs, start, true);
iter != NULL;
iter = g_arch_instruction_get_next_iter(instrs, iter, VMPA_MAX))
{
range = g_arch_instruction_get_range(iter);
if (code_coverage_stop_here(coverage, get_mrange_addr(range)))
printf(" ++ stop here 0x%08x\n", (unsigned int)range->addr.virtual);
if (code_coverage_stop_here(coverage, get_mrange_addr(range)))
break;
if (g_arch_instruction_has_sources(iter))
add_hop_into_branch(info, get_mrange_addr(range));
if (g_arch_instruction_is_return(iter))
printf(" ++ return 0x%08x\n", (unsigned int)range->addr.virtual);
if (g_arch_instruction_is_return(iter))
{
iter = NULL;
break;
}
/*
if (!g_arch_instruction_has_destinations(iter))
printf(" ++ no dest 0x%08x\n", (unsigned int)range->addr.virtual);
*/
if (!g_arch_instruction_has_destinations(iter))
continue;
printf(" ++ dcount 0x%08x\n", (unsigned int)range->addr.virtual);
dcount = g_arch_instruction_get_destinations(iter, &dests, &types, NULL);
not_handled = 0;
for (i = 0; i < dcount; i++)
{
range = g_arch_instruction_get_range(dests[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:
find_next_hops(instrs, get_mrange_addr(range), coverage, info);
break;
case ILT_LOOP:
add_hop_into_branch(info, get_mrange_addr(range));
break;
default:
not_handled++;
break;
}
}
if (not_handled < dcount)
break;
}
/* Si on termine... */
if (iter != NULL) add_hop_into_branch(info, get_mrange_addr(range));
printf(" ------- [ %p ] ---\n", info);
}
/******************************************************************************
* *
* Paramètres : a = premier ensemble de jalons à parcourir. *
* b = second ensemble de jalons à parcourir. *
* c = éventuelle adresse commune à deux branches. *
* *
* Description : Retrouve le point de ralliement entre deux branches. *
* *
* Retour : true si une position commune a pu être trouvée, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool compute_first_common_addr(const branch_info *a, const branch_info *b, vmpa2t *c)
{
bool result; /* Bilan à retourner */
size_t i; /* Boucle de parcours */
result = false;
printf("....................\n");
printf(" A :: ");
for (i = 0; i < a->count; i++)
printf("0x%08x ", a->hops[i].virtual);
printf("\n");
printf(" B :: ");
for (i = 0; i < b->count; i++)
printf("0x%08x ", b->hops[i].virtual);
printf("\n");
for (i = 0; i < a->count && !result; i++)
if (is_addr_in_branch(b, &a->hops[i]))
{
result = true;
copy_vmpa(c, &a->hops[i]);
}
if (result)
printf(" N :: 0x%08x\n", (unsigned int)c->virtual);
else
printf(" N :: ----\n");
printf("....................\n");
return result;
}
/******************************************************************************
* *
* Paramètres : group = informations à initialiser. *
* *
* Description : Initialise le suivi d'un ensemble de branches. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void init_branch_group(branch_group *group)
{
memset(group, 0, sizeof(branch_group));
}
/******************************************************************************
* *
* Paramètres : group = informations à nettoyer. *
* *
* Description : Acte la fin d'un suivi d'un ensemble de branches. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void clean_branch_group(branch_group *group)
{
size_t i; /* Boucle de parcours */
for (i = 0; i < group->count; i++)
clean_branch_info(&group->branches[i]);
if (group->branches != NULL)
free(group->branches);
}
/******************************************************************************
* *
* Paramètres : group = liste d'ensembles de jalons à agrandir. *
* *
* Description : Ajoute une branche à un ensemble de branches en place. *
* *
* Retour : Nouvel élément rajouté et initialisé. *
* *
* Remarques : - *
* *
******************************************************************************/
static branch_info *extend_branch_group(branch_group *group)
{
branch_info *result; /* Nouveauté à retourner */
group->branches = (branch_info *)realloc(group->branches,
++group->count * sizeof(branch_info));
result = &group->branches[group->count];
init_branch_info(result);
return result;
}
/******************************************************************************
* *
* Paramètres : group = liste d'ensembles de jalons à parcourir. *
* common = éventuelle adresse commune à branches. *
* *
* Description : Retrouve le point de ralliement entre un groupe de branches. *
* *
* Retour : true si une position commune a pu être trouvée, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool compute_first_common_addr_in_group(const branch_group *group, vmpa2t *common)
{
vmpa_t result; /* Adresse trouvée à retourner */
branch_info *list; /* Raccourci de confort */
size_t i; /* Boucle de parcours #1 */
bool keep; /* Candidate à garder ? */
size_t j; /* Boucle de parcours #2 */
result = false;
list = group->branches;
for (i = 0; i < list[0].count && !result; i++)
{
keep = true;
for (j = 1; j < group->count && keep; j++)
keep = is_addr_in_branch(&list[j], &list[0].hops[i]);
if (keep)
copy_vmpa(common, &list[0].hops[i]);
}
return result;
}
/* ---------------------------------------------------------------------------------- */
/* DECOUPAGE EN BLOCS DE CODE */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : instrs = ensemble des instructions d'assemblage. *
* coverage = délimitations de la zone à couvrir. *
* first = première instruction d'un bloc préliminaire. *
* cur = instruction courante dans le traitement. *
* *
* Description : Procède à la création d'un bloc d'instructions simple. *
* *
* Retour : Bloc créé ou NULL. *
* *
* Remarques : - *
* *
******************************************************************************/
#include "../../arch/instruction-int.h"
static GInstrBlock *build_instruction_block_simple(GArchInstruction *instrs, code_coverage *coverage, GArchInstruction **first, GArchInstruction *cur)
{
GInstrBlock *result; /* Regroupement à retourner */
if (*first != NULL)
{
result = g_flow_block_new(instrs, *first, cur);
mark_range_as_processed_in_coverage(coverage, *first);
*first = NULL;
}
else result = NULL;
return result;
}
/******************************************************************************
* *
* Paramètres : instrs = ensemble des instructions d'assemblage. *
* coverage = délimitations de la zone à couvrir. *
* cases = branches conditionnelles des situations. *
* next = localisation de l'instruction de reprise. *
* *
* Description : Procède à la définition d'un bloc d'instructions selectif. *
* *
* Retour : Bloc créé et enregistré, ou NULL si erreur. *
* *
* Remarques : - *
* *
******************************************************************************/
static GInstrBlock *build_instruction_blocks_case(GArchInstruction *instrs, code_coverage *coverage, const branch_group *cases, vmpa2t *next)
{
GInstrBlock *result; /* Regroupement à retourner */
bool has_common; /* Fin commune ? */
size_t i; /* Boucle de parcours #1 */
code_coverage *sub_coverage; /* Couverture pour les suivants*/
size_t j; /* Boucle de parcours #2 */
GInstrBlock *block; /* Nouveau bloc mis en place */
has_common = compute_first_common_addr_in_group(cases, next);
if (!has_common) return NULL;
result = g_virtual_block_new();
for (i = 0; i < cases->count; i++)
{
sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(&cases->branches[i]));
add_ending_address_code_coverage(sub_coverage, next);
for (j = 0; j < cases->count; j++)
add_ending_address_code_coverage(sub_coverage, get_entry_to_branch(&cases->branches[j]));
block = build_instruction_blocks(instrs, sub_coverage);
if (block != NULL)
g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);
delete_code_coverage(sub_coverage);
}
if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(result)) == 0)
{
g_object_unref(G_OBJECT(result));
result = NULL;
}
return result;
}
/******************************************************************************
* *
* Paramètres : instrs = ensemble des instructions d'assemblage. *
* coverage = délimitations de la zone à couvrir. *
* true_branch = branche conditionnelle correspondant à true. *
* false_branch = branche conditionnelle correspondant à false. *
* next = localisation de l'instruction de reprise. *
* *
* Description : Procède à la définition d'un bloc d'instruction if/then/else.*
* *
* Retour : Bloc créé et enregistré, ou NULL si erreur. *
* *
* Remarques : - *
* *
******************************************************************************/
static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *instrs, code_coverage *coverage, const branch_info *true_branch, const branch_info *false_branch, vmpa2t *next)
{
GInstrBlock *result; /* Regroupement à retourner */
bool has_common; /* Fin commune ? */
GInstrBlock *block; /* Nouveau bloc mis en place */
has_common = compute_first_common_addr(true_branch, false_branch, next);
if (!has_common)
{
code_coverage *_sub_coverage; /* Couverture pour les suivants*/
result = g_virtual_block_new();
/* Branche 'true' */
_sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(true_branch));
block = build_instruction_blocks(instrs, _sub_coverage);
delete_code_coverage(_sub_coverage);
printf("===> !TRUE_BRANCH = %p\n", block);
if (block != NULL)
g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);
/* Branche 'false' */
_sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(false_branch));
block = build_instruction_blocks(instrs, _sub_coverage);
delete_code_coverage(_sub_coverage);
printf("===> !FALSE_BRANCH = %p\n", block);
if (block != NULL)
g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);
/* Conclusion */
if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(result)) == 0)
{
g_object_unref(G_OBJECT(result));
result = NULL;
}
return result;
}
assert(has_common);
if (!has_common) printf(" === nothing in common\n");
if (!has_common) return NULL;
result = g_virtual_block_new();
/**
* Encapsulation des branches conditionnelles.
*/
GInstrBlock *build_instr_block_bi(GArchInstruction *instrs, const code_coverage *coverage, const branch_info *br0, const branch_info *br1, const vmpa2t *next)
{
GInstrBlock *result; /* Bloc construit à renvoyer */
code_coverage *sub_coverage; /* Couverture pour les suivants*/
result = NULL;
if (br0->count > 0)
{
sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(br0));
add_ending_address_code_coverage(sub_coverage, next);
if (br1->count > 0)
add_ending_address_code_coverage(sub_coverage, get_entry_to_branch(br1));
result = build_instruction_blocks(instrs, sub_coverage);
delete_code_coverage(sub_coverage);
}
return result;
}
/* Branche 'true' */
block = build_instr_block_bi(instrs, coverage, true_branch, false_branch, next);
printf("===> TRUE_BRANCH = %p\n", block);
if (block != NULL)
g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);
/* Branche 'false' */
block = build_instr_block_bi(instrs, coverage, false_branch, true_branch, next);
printf("===> FALSE_BRANCH = %p\n", block);
if (block != NULL)
g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block);
/* Conclusion */
if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(result)) == 0)
{
g_object_unref(G_OBJECT(result));
result = NULL;
}
return result;
}
/******************************************************************************
* *
* Paramètres : result = liste générale résultante du découpage. [OUT] *
* cached = emplacement pour le cache des résultats. [OUT] *
* instrs = ensemble des instructions d'assemblage. *
* coverage = délimitations de la zone à couvrir. *
* exceptions = branche conditionnelle correspondant à true. *
* main_branch = branche principale avec son flot d'exécution. *
* *
* Description : Procède à la définition d'un bloc d'instructions d'exception.*
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void add_instruction_blocks_except(GInstrBlock **result, GInstrBlock **cached, GArchInstruction *instrs, code_coverage *coverage, const branch_group *exceptions, const branch_info *main_branch)
{
size_t i; /* Boucle de parcours */
vmpa2t stop_addr; /* Adresse de fin de bloc */
bool has_stop; /* Fin commune ? */
code_coverage *sub_coverage; /* Couverture pour les suivants*/
GInstrBlock *block; /* Nouveau bloc mis en place */
for (i = 0; i < exceptions->count; i++)
{
has_stop = compute_first_common_addr(main_branch, &exceptions->branches[i], &stop_addr);
if (!has_stop) continue;
sub_coverage = dup_code_coverage(coverage, get_entry_to_branch(&exceptions->branches[i]));
add_ending_address_code_coverage(sub_coverage, &stop_addr);
block = build_instruction_blocks(instrs, sub_coverage);
if (block != NULL)
DELAYED_BLOCK_ADDING(*result, *cached, block);
delete_code_coverage(sub_coverage);
}
}
/******************************************************************************
* *
* Paramètres : instrs = ensemble des instructions d'assemblage. *
* coverage = délimitations de la zone à couvrir. *
* *
* Description : Procède à la définition de bloc regroupant des instructions. *
* *
* Retour : Bloc créé et enregistré, ou NULL si erreur. *
* *
* Remarques : - *
* *
******************************************************************************/
#include "../../arch/instruction-int.h"
static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_coverage *coverage)
{
GInstrBlock *result; /* Regroupement à retourner */
GInstrBlock *result_cached; /* Temporisation pour unicité */
branch_info main_branch; /* Flot d'exécution complet */
GArchInstruction *first; /* Première instruction */
GArchInstruction *last; /* Dernière instruction */
GArchInstruction *iter; /* Boucle de parcours */
const mrange_t *range; /* Emplacement d'instruction */
const vmpa2t *addr; /* Adresse de la destination */
GArchInstruction **dests; /* Instr. visée par une autre */
InstructionLinkType *types; /* Type de lien entre lignes */
size_t dcount; /* Nombre de liens de dest. */
size_t i; /* Boucle de parcours #1 */
GInstrBlock *block; /* Nouveau bloc mis en place */
GInstrBlock *group; /* Regroupement de blocs */
size_t not_handled; /* Quantité de liens non gérés */
vmpa2t next_addr; /* Prochaine instruction visée */
branch_group cases_branches; /* Branches d'un aiguillage */
branch_info true_branch; /* Branche 'condition vraie' */
branch_info false_branch; /* Branche 'condition fausse' */
branch_group excep_branches; /* Branches d'exceptions */
branch_info *branch; /* Branche à suivre */
result = NULL;
result_cached = NULL;
first = NULL;
last = NULL;
init_branch_info(&main_branch);
find_next_hops(instrs, get_code_coverage_start_addr(coverage), coverage, &main_branch);
printf("//////////////////////////\n");
printf("/// Cutting for 0x%08x -> %p\n",
get_code_coverage_start_addr(coverage)->virtual,
g_arch_instruction_find_by_address(instrs, get_code_coverage_start_addr(coverage), true));
printf("//////////////////////////\n");
for (iter = g_arch_instruction_find_by_address(instrs, get_code_coverage_start_addr(coverage), true);
iter != NULL;
)
{
range = g_arch_instruction_get_range(iter);
addr = get_mrange_addr(range);
if (code_coverage_stop_here(coverage, addr)) break;
/* On s'arrête si l'instruction est déjà décompilée */
if (is_range_processed_in_coverage(coverage, range)) break;
if (first == NULL)
first = iter;
last = iter;
/**
* On s'arrête également en fin de procédure.
* L'expérience montre qu'il peut y avoir plusieurs fins dans une routine,
* et donc des fins en milieu de couverture de cette même routine.
*/
if (g_arch_instruction_is_return(iter)) break;
/* On n'approfondit que les chemins qui se séparent */
if (!g_arch_instruction_has_destinations(iter))
{
iter = g_arch_instruction_get_next_iter(instrs, iter, VMPA_MAX);
continue;
}
/* Adaptations en fonction du type de bifurcation */
dcount = g_arch_instruction_get_destinations(iter, &dests, &types, NULL);
not_handled = 0;
init_vmpa(&next_addr, VMPA_NO_PHYSICAL, VMPA_NO_VIRTUAL);
init_branch_group(&cases_branches);
init_branch_info(&true_branch);
init_branch_info(&false_branch);
init_branch_group(&excep_branches);
for (i = 0; i < dcount; i++)
{
branch = NULL;
switch (types[i])
{
case ILT_EXEC_FLOW:
case ILT_JUMP:
//break;
{
GArchInstruction *_saved0;
_saved0 = first;
block = build_instruction_block_simple(instrs, coverage, &first, iter);
printf(" -- simple block JMP -- @ 0x%08x <-> 0x%08x\n",
(unsigned int)(_saved0 ? _saved0->range.addr.virtual : ~0),
(unsigned int)iter->range.addr.virtual);
fflush(NULL);
}
DELAYED_BLOCK_ADDING(result, result_cached, block);
/**
* La prochaine adresse d'analyse est celle visée par l'instruction !
* Pour les sauts naturels, ça ne change rien ; ce n'est pas le cas
* pour les sauts explicites.
*/
range = g_arch_instruction_get_range(dests[i]);
copy_vmpa(&next_addr, get_mrange_addr(range));
first = NULL;
break;
case ILT_LOOP:
/**
* Lorsque l'on désassemble un flot d'instructions et que l'on rencontre
* une amorce de boucle, il y a deux cas de figure :
*
* - soit il s'agit d'un ancien JUMP, et la reprise du désassemblage
* se fera à partir de l'adresse ciblée.
*
* - soit il s'agit d'un branchement conditionnel dont une des branches
* conduit à un rebouclage. Le désassemblage s'arrête alors pour la
* partie en boucle car il n'y a plus d'adresse commune pour la suite.
*
* Il reste donc à forcer une coupure dans le cas suivant :
*
* ...
* jmp xxxx
* loc:
* ...
*
* Il suffit de ne pas initialiser 'next_addr' et de laisser la main à d'éventuelles
* autres destinations voisines.
*/
break;
case ILT_CASE_JUMP:
branch = extend_branch_group(&cases_branches);
break;
case ILT_JUMP_IF_TRUE:
printf("FIND TRUE BRANCH @ 0x%08x\n", (unsigned int)iter->range.addr.virtual);
branch = &true_branch;
break;
case ILT_JUMP_IF_FALSE:
printf("FIND FALSE BRANCH @ 0x%08x\n", (unsigned int)iter->range.addr.virtual);
branch = &false_branch;
break;
case ILT_CATCH_EXCEPTION:
branch = extend_branch_group(&excep_branches);
/**
* Les deux cas sont les seuls à ne pas conduire à une définition de
* next_addr, donc on les comptabilise sur un pied d'égalité !
*/
/* break; */
default:
not_handled++;
break;
}
/* Si on a une branche à compléter... */
if (branch != NULL)
{
range = g_arch_instruction_get_range(dests[i]);
addr = get_mrange_addr(range);
printf("\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
printf("BUILD @ 0x%08x\n", (unsigned int)addr->virtual);
find_next_hops(instrs, addr, coverage, branch);
printf("<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n\n");
}
}
/* Post-traitements de ILT_CASE_JUMP */
if (cases_branches.count > 0)
{
block = build_instruction_block_simple(instrs, coverage, &first, iter);
DELAYED_BLOCK_ADDING(result, result_cached, block);
group = build_instruction_blocks_case(instrs, coverage, &cases_branches, &next_addr);
if (group != NULL)
{
DELAYED_BLOCK_ADDING(result, result_cached, group);
g_instr_block_set_links_block(block, group);
}
}
/* Post-traitements de ILT_JUMP_IF_TRUE / ILT_JUMP_IF_FALSE */
else if (true_branch.count > 0 || false_branch.count > 0)
{
block = build_instruction_block_simple(instrs, coverage, &first, iter);
GArchInstruction *_saved1;
_saved1 = first;
printf(" -- branches -- %d vs %d\n", (int)true_branch.count, (int)false_branch.count);
printf(" -- simple block ITE -- @ 0x%08x <-> 0x%08x\n",
(unsigned int)(_saved1 ? _saved1->range.addr.virtual : ~0),
(unsigned int)iter->range.addr.virtual);
fflush(NULL);
DELAYED_BLOCK_ADDING(result, result_cached, block);
group = build_instruction_blocks_ite(instrs, coverage, &true_branch, &false_branch, &next_addr);
printf(" --> group = %p - next = 0x%08x\n", group, next_addr.virtual);
if (group != NULL)
{
DELAYED_BLOCK_ADDING(result, result_cached, group);
g_instr_block_set_links_block(block, group);
}
}
/* Post-traitements de ILT_CATCH_EXCEPTION */
if (excep_branches.count > 0)
{
block = build_instruction_block_simple(instrs, coverage, &first, iter);
if (block != NULL) DELAYED_BLOCK_ADDING(result, result_cached, block);
add_instruction_blocks_except(&result, &result_cached, instrs, coverage,
&excep_branches, &main_branch);
}
clean_branch_group(&cases_branches);
clean_branch_info(&true_branch);
clean_branch_info(&false_branch);
clean_branch_group(&excep_branches);
/* Détermination du prochain point de chute */
if (not_handled == dcount)
iter = g_arch_instruction_get_next_iter(instrs, iter, VMPA_MAX);
else
iter = g_arch_instruction_find_by_address(instrs, &next_addr, true);
}
if (first != NULL && last != NULL)
{
range = g_arch_instruction_get_range(first);
if (!is_range_processed_in_coverage(coverage, range))
{
block = build_instruction_block_simple(instrs, coverage, &first, last);
DELAYED_BLOCK_ADDING(result, result_cached, block);
}
}
clean_branch_info(&main_branch);
return (result != NULL ? result : result_cached);
}
/******************************************************************************
* *
* Paramètres : list = ensemble d'instructions à relier. *
* routines = prototypes existants à insérer. *
* count = quantité de ces prototypes. *
* statusbar = barre de statut avec progression à mettre à jour.*
* id = identifiant du message affiché à l'utilisateur. *
* *
* Description : Regroupe les instructions par blocs. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void group_routines_instructions(GArchInstruction *list, GBinRoutine **routines, size_t count, GtkExtStatusBar *statusbar, bstatus_id_t id)
{
size_t i; /* Boucle de parcours */
const mrange_t *range; /* Emplacement de routine */
code_coverage *coverage; /* Couverture de zone de code */
GInstrBlock *block; /* Regroupement d'instructions */
for (i = 0; i < count; i++)
{
range = g_binary_routine_get_range(routines[i]);
printf("===== BLOCK(S) for 0x%08x ======\n", range->addr.virtual);
coverage = create_code_coverage(range);
block = build_instruction_blocks(list, coverage);
g_binary_routine_set_basic_blocks(routines[i], block);
bool visit_block(GInstrBlock *blk, BlockVisitOrder order, int *indent)
{
int i;
switch (order)
{
case BVO_IN:
case BVO_PENDING:
for (i = 0; i < *indent; i++)
printf(" ");
printf("%p '%s'", blk, G_OBJECT_TYPE_NAME(blk));
if (G_IS_FLOW_BLOCK(blk))
{
vmpa2t start;
vmpa2t end;
g_flow_block_get_boundary_addresses(G_FLOW_BLOCK(blk), &start, &end);
printf(" 0x%08x -> 0x%08x",
(unsigned int)start.virtual,
(unsigned int)end.virtual);
}
printf("\n");
if (order == BVO_IN) (*indent)++;
break;
case BVO_OUT:
(*indent)--;
break;
}
return true;
}
g_instr_block_visit(block, (instr_block_visitor_cb)visit_block, (int []){ 0 });
printf("\n");
delete_code_coverage(coverage);
gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count);
}
}