/* 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 <http://www.gnu.org/licenses/>.
*/
#include "macro.h"
#include <malloc.h>
#include <string.h>
#include "../blocks/flow.h"
#include "../blocks/virtual.h"
/* ------------------------ COUVERTURE D'UNE ZONE A DECOUPER ------------------------ */
/* Bornes d'une zone à couvrir */
typedef struct _code_coverage
{
vmpa_t start; /* Adresse de départ */
vmpa_t *ends; /* Adresses butoir de fin */
size_t ends_count; /* Quantité de fins possibles */
} code_coverage;
/* Met en place les délimitations d'une zone de code. */
static code_coverage *create_code_coverage(vmpa_t, vmpa_t);
/* Crée une copie d'une couverture de zone de code. */
static code_coverage *dup_code_coverage(vmpa_t, const code_coverage *);
/* Détruit des délimitations d'une zone de code. */
static void delete_code_coverage(code_coverage *);
/* Indique si une adresse est hors zone ou non. */
static bool code_coverage_stop_here(const code_coverage *, const vmpa_t *);
/* Ajoute une adresse butoir pour la zone à couvrir. */
static void add_ending_address_code_coverage(code_coverage *, const vmpa_t *);
/* ------------------------- SUIVI DES FLOTS D'INSTRUCTIONS ------------------------- */
/* Indications sur une branche */
typedef struct _branch_info
{
vmpa_t *jumps; /* Jalons de la branche */
size_t count; /* Quantité de ces jalons */
} branch_info;
/* Indique si une adresse est retenue comme point de passage. */
static bool is_addr_in_branch(const branch_info *, const vmpa_t *);
/* Identifie les différents points de passage d'une branche. */
static void find_next_jumps(GArchInstruction *, vmpa_t, const code_coverage *, branch_info *);
/* Retrouve le point de ralliement entre deux branches. */
static vmpa_t compute_first_common_addr(branch_info *, branch_info *);
/* Retrouve le point de ralliement entre un groupe de branches. */
static vmpa_t compute_first_common_addr_in_group(const branch_info *, size_t);
/* --------------------------- DECOUPAGE EN BLOCS DE CODE --------------------------- */
/**
* Macros pour le marquage des instructions traitées.
* Dans un soucis d'optimisation, on ne traite que les instructions
* démarrant un bloc.
*/
#define MACRO_MARK_AS_PROCESSED(_instr) g_object_set_data(G_OBJECT(_instr), "macro_done", _instr)
#define MACRO_IS_PROCESSED(_instr) (g_object_get_data(G_OBJECT(_instr), "macro_done") != NULL)
#define MACRO_CLEAR_PROCESSED(_instr) g_object_set_data(G_OBJECT(_instr), "macro_done", NULL)
/* Procède à la définition de bloc regroupant des instructions. */
static GInstrBlock *build_instruction_block(GArchInstruction *, const code_coverage *);
/* ---------------------------------------------------------------------------------- */
/* COUVERTURE D'UNE ZONE A DECOUPER */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : start = adresse du début de la zone à couvrir. *
* end = adresse de fin de la zone à couvrir (exclusive). *
* *
* 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(vmpa_t start, vmpa_t end)
{
code_coverage *result; /* Couverture à retourner */
result = (code_coverage *)calloc(1, sizeof(code_coverage));
result->start = start;
result->ends = (vmpa_t *)calloc(1, sizeof(vmpa_t));
result->ends_count = 1;
result->ends[0] = end;
return result;
}
/******************************************************************************
* *
* Paramètres : start = nouvelle adresse de début, plus profonde. *
* src = informations de couverture à consulter. *
* *
* 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(vmpa_t start, const code_coverage *src)
{
code_coverage *result; /* Couverture à retourner */
size_t i; /* Boucle de parcours */
result = (code_coverage *)calloc(1, sizeof(code_coverage));
result->start = start;
result->ends = (vmpa_t *)calloc(src->ends_count, sizeof(vmpa_t));
result->ends_count = src->ends_count;
for (i = 0; i < result->ends_count; i++)
result->ends[i] = src->ends[i];
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);
free(coverage);
}
/******************************************************************************
* *
* Paramètres : coverage = informations de couverture à consulter. *
* addr = adresse à 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 vmpa_t *addr)
{
void *ptr; /* Résultat des recherches */
ptr = bsearch(addr, coverage->ends, coverage->ends_count,
sizeof(vmpa_t), (__compar_fn_t)compare_vmpa);
return (ptr != NULL);
}
/******************************************************************************
* *
* Paramètres : coverage = informations de couverture à compléter. *
* addr = adresse à ajouter. *
* *
* Description : Ajoute une adresse butoir pour la zone à couvrir. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void add_ending_address_code_coverage(code_coverage *coverage, const vmpa_t *addr)
{
coverage->ends = (vmpa_t *)realloc(coverage->ends, ++coverage->ends_count * sizeof(vmpa_t));
coverage->ends[coverage->ends_count - 1] = *addr;
qsort(coverage->ends, coverage->ends_count, sizeof(vmpa_t), (__compar_fn_t)compare_vmpa);
}
/* ---------------------------------------------------------------------------------- */
/* SUIVI DES FLOTS D'INSTRUCTIONS */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : info = informations à consulter. *
* addr = adresse à 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 vmpa_t *addr)
{
bool result; /* Bilan à retourner */
size_t i; /* Boucle de parcours */
result = false;
for (i = 0; i < info->count && !result; i++)
result = (info->jumps[i] == *addr);
return result;
}
/******************************************************************************
* *
* Paramètres : instrs = ensemble des instructions d'assemblage. *
* start = adresse de début du 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_jumps(GArchInstruction *instrs, vmpa_t start, const code_coverage *coverage, branch_info *info)
{
GArchInstruction *iter; /* Boucle de parcours #1 */
vmpa_t addr; /* Adresse d'une 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 */
vmpa_t daddr; /* Adresse de destination */
/* On évite de boucler... */
if (is_addr_in_branch(info, &start))
return;
info->jumps = (vmpa_t *)realloc(info->jumps, ++(info->count) * sizeof(vmpa_t));
info->jumps[info->count - 1] = start;
/* 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))
{
g_arch_instruction_get_location(iter, NULL, NULL, &addr);
if (code_coverage_stop_here(coverage, &addr))
break;
if (g_arch_instruction_is_return(iter))
{
iter = NULL;
break;
}
if (!g_arch_instruction_has_destinations(iter))
continue;
dcount = g_arch_instruction_get_destinations(iter, &dests, &types, NULL);
for (i = 0; i < dcount; 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:
g_arch_instruction_get_location(dests[i], NULL, NULL, &daddr);
find_next_jumps(instrs, daddr, coverage, info);
break;
case ILT_LOOP:
g_arch_instruction_get_location(dests[i], NULL, NULL, &daddr);
info->jumps = (vmpa_t *)realloc(info->jumps, ++(info->count) * sizeof(vmpa_t));
info->jumps[info->count - 1] = daddr;
break;
default:
break;
}
break;
}
/* Si on termine... */
if (iter != NULL && !is_addr_in_branch(info, &addr))
{
info->jumps = (vmpa_t *)realloc(info->jumps, ++(info->count) * sizeof(vmpa_t));
info->jumps[info->count - 1] = addr;
}
}
/******************************************************************************
* *
* Paramètres : a = premier ensemble de jalons à parcourir. *
* b = second ensemble de jalons à parcourir. *
* *
* Description : Retrouve le point de ralliement entre deux branches. *
* *
* Retour : Adresse commune à deux branches. *
* *
* Remarques : - *
* *
******************************************************************************/
static vmpa_t compute_first_common_addr(branch_info *a, branch_info *b)
{
vmpa_t result; /* Adresse trouvée à retourner */
size_t i; /* Boucle de parcours */
/* Valeur conceptuellement impossible à renvoyer */
result = VMPA_MAX;
for (i = 0; i < a->count && result == VMPA_MAX; i++)
if (is_addr_in_branch(b, &a->jumps[i]))
result = a->jumps[i];
return result;
}
/******************************************************************************
* *
* Paramètres : list = liste d'ensembles de jalons à parcourir. *
* count = taille de cette liste. *
* *
* Description : Retrouve le point de ralliement entre un groupe de branches. *
* *
* Retour : Adresse commune aux branches. *
* *
* Remarques : - *
* *
******************************************************************************/
static vmpa_t compute_first_common_addr_in_group(const branch_info *list, size_t count)
{
vmpa_t result; /* Adresse trouvée à retourner */
size_t i; /* Boucle de parcours #1 */
bool keep; /* Candidate à garder ? */
size_t j; /* Boucle de parcours #2 */
/* Valeur conceptuellement impossible à renvoyer */
result = VMPA_MAX;
for (i = 0; i < list[0].count && result == VMPA_MAX; i++)
{
keep = true;
for (j = 1; j < count && keep; j++)
keep = is_addr_in_branch(&list[j], &list[0].jumps[i]);
if (keep)
result = list[0].jumps[i];
}
return result;
}
/* ---------------------------------------------------------------------------------- */
/* DECOUPAGE EN BLOCS DE CODE */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* 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 : - *
* *
******************************************************************************/
static GInstrBlock *build_instruction_block(GArchInstruction *instrs, const 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 */
vmpa_t 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 *parent; /* Mémorisation pour les liens */
GInstrBlock *group; /* Regroupement de blocs */
size_t not_handled; /* Quantité de liens non gérés */
vmpa_t next_addr; /* Prochaine instruction visée */
branch_info *cases_branches; /* Branches d'un aiguillage */
size_t cases_count; /* Nombre d'aiguillages */
branch_info true_branch; /* Branche 'condition vraie' */
branch_info false_branch; /* Branche 'condition fausse' */
branch_info *excep_branches; /* Branches d'exceptions */
size_t excep_count; /* Nombre d'exceptions */
code_coverage *sub_coverage; /* Couverture pour les suivants*/
size_t j; /* Boucle de parcours #2 */
vmpa_t stop_addr; /* Adresse de fin de bloc */
result = NULL;
result_cached = NULL;
/**
* 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)
first = NULL;
last = NULL;
memset(&main_branch, 0, sizeof(branch_info));
find_next_jumps(instrs, coverage->start, coverage, &main_branch);
for (iter = g_arch_instruction_find_by_address(instrs, coverage->start, true);
iter != NULL;
)
{
g_arch_instruction_get_location(iter, NULL, NULL, &addr);
if (code_coverage_stop_here(coverage, &addr)) break;
/* On s'arrêter si l'instruction est déjà décompilée */
if (MACRO_IS_PROCESSED(iter)) break;
if (first == NULL)
first = iter;
last = iter;
/* 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;
next_addr = VMPA_MAX;
cases_branches = NULL;
cases_count = 0;
memset(&true_branch, 0, sizeof(branch_info));
memset(&false_branch, 0, sizeof(branch_info));
excep_branches = NULL;
excep_count = 0;
for (i = 0; i < dcount; i++)
switch (types[i])
{
case ILT_EXEC_FLOW:
case ILT_JUMP:
block = g_flow_block_new(instrs, first, iter);
MACRO_MARK_AS_PROCESSED(first);
first = NULL;
DELAYED_BLOCK_ADDING(result, result_cached, block);
g_arch_instruction_get_location(dests[i], NULL, NULL, &next_addr);
break;
case ILT_CASE_JUMP:
g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
cases_branches = (branch_info *)realloc(cases_branches,
++cases_count * sizeof(branch_info));
memset(&cases_branches[cases_count - 1], 0, sizeof(branch_info));
find_next_jumps(instrs, addr, coverage, &cases_branches[cases_count - 1]);
break;
case ILT_JUMP_IF_TRUE:
g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
find_next_jumps(instrs, addr, coverage, &true_branch);
break;
case ILT_JUMP_IF_FALSE:
g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
find_next_jumps(instrs, addr, coverage, &false_branch);
break;
case ILT_CATCH_EXCEPTION:
g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
excep_branches = (branch_info *)realloc(excep_branches,
++excep_count * sizeof(branch_info));
memset(&excep_branches[excep_count - 1], 0, sizeof(branch_info));
find_next_jumps(instrs, addr, coverage, &excep_branches[excep_count - 1]);
/**
* 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;
}
/* Post-traitements de ILT_CASE_JUMP */
if (cases_count > 0)
{
/**
* On doit clôturer le bloc renvoyant vers les branches de cas ici.
* Les sauts conditionnels sont normalement présents de façon exclusive,
* sauf pour les exceptions, qui sont traitées après.
*/
block = g_flow_block_new(instrs, first, iter);
MACRO_MARK_AS_PROCESSED(first);
first = NULL;
DELAYED_BLOCK_ADDING(result, result_cached, block);
next_addr = compute_first_common_addr_in_group(cases_branches, cases_count);
parent = block;
group = g_virtual_block_new();
for (i = 0; i < cases_count; i++)
{
sub_coverage = dup_code_coverage(cases_branches[i].jumps[0], coverage);
add_ending_address_code_coverage(sub_coverage, &next_addr);
for (j = 0; j < cases_count; j++)
if (cases_branches[j].jumps[0] != cases_branches[i].jumps[0])
add_ending_address_code_coverage(sub_coverage, &cases_branches[j].jumps[0]);
block = build_instruction_block(instrs, sub_coverage);
delete_code_coverage(sub_coverage);
if (block != NULL)
g_virtual_block_add_child(G_VIRTUAL_BLOCK(group), block);
free(cases_branches[i].jumps);
}
if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(group)) > 0)
{
DELAYED_BLOCK_ADDING(result, result_cached, group);
g_instr_block_set_links_block(parent, group);
}
else
g_object_unref(G_OBJECT(group));
free(cases_branches);
}
else if (true_branch.count > 0 || false_branch.count > 0)
{
next_addr = compute_first_common_addr(&true_branch, &false_branch);
/**
* On doit clôturer le bloc renvoyant vers les branches 'true' et 'false' ici.
* Les sauts conditionnels sont normalement présents de façon exclusive,
* sauf pour les exceptions, qui sont traitées après.
*/
block = g_flow_block_new(instrs, first, iter);
MACRO_MARK_AS_PROCESSED(first);
first = NULL;
DELAYED_BLOCK_ADDING(result, result_cached, block);
parent = block;
group = g_virtual_block_new();
/* Branche 'true' */
if (true_branch.count > 0)
{
sub_coverage = dup_code_coverage(true_branch.jumps[0], coverage);
add_ending_address_code_coverage(sub_coverage, &next_addr);
if (false_branch.count > 0)
add_ending_address_code_coverage(sub_coverage, &false_branch.jumps[0]);
block = build_instruction_block(instrs, sub_coverage);
if (block != NULL)
g_virtual_block_add_child(G_VIRTUAL_BLOCK(group), block);
delete_code_coverage(sub_coverage);
}
/* Branche 'false' */
if (false_branch.count > 0)
{
sub_coverage = dup_code_coverage(false_branch.jumps[0], coverage);
add_ending_address_code_coverage(sub_coverage, &next_addr);
if (true_branch.count > 0)
add_ending_address_code_coverage(sub_coverage, &true_branch.jumps[0]);
block = build_instruction_block(instrs, sub_coverage);
if (block != NULL)
g_virtual_block_add_child(G_VIRTUAL_BLOCK(group), block);
delete_code_coverage(sub_coverage);
}
/* Conclusion */
if (true_branch.count > 0) free(true_branch.jumps);
if (false_branch.count > 0) free(false_branch.jumps);
if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(group)) > 0)
{
DELAYED_BLOCK_ADDING(result, result_cached, group);
g_instr_block_set_links_block(parent, group);
}
else
g_object_unref(G_OBJECT(group));
}
/* Post-traitements de ILT_CATCH_EXCEPTION */
if (excep_count > 0)
{
if (first != NULL)
{
block = g_flow_block_new(instrs, first, iter);
MACRO_MARK_AS_PROCESSED(first);
first = NULL;
DELAYED_BLOCK_ADDING(result, result_cached, block);
}
for (j = 0; j < excep_count; j++)
{
stop_addr = compute_first_common_addr(&main_branch, &excep_branches[j]);
sub_coverage = dup_code_coverage(excep_branches[j].jumps[0], coverage);
add_ending_address_code_coverage(sub_coverage, &stop_addr);
block = build_instruction_block(instrs, sub_coverage);
delete_code_coverage(sub_coverage);
if (block != NULL)
DELAYED_BLOCK_ADDING(result, result_cached, block);
free(excep_branches[j].jumps);
}
free(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)
{
if (!MACRO_IS_PROCESSED(first))
{
block = g_flow_block_new(instrs, first, last);
MACRO_MARK_AS_PROCESSED(first);
DELAYED_BLOCK_ADDING(result, result_cached, block);
}
}
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 */
vmpa_t start; /* Adresse de départ */
vmpa_t end; /* Adresse de fin */
code_coverage *coverage; /* Couverture de zone de code */
GInstrBlock *block; /* Regroupement d'instructions */
for (i = 0; i < count; i++)
{
start = g_binary_routine_get_address(routines[i]);
end = start + g_binary_routine_get_size(routines[i]);
coverage = create_code_coverage(start, end);
block = build_instruction_block(list, coverage);
g_binary_routine_set_basic_blocks(routines[i], block);
delete_code_coverage(coverage);
gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count);
}
}