/* Chrysalide - Outil d'analyse de fichiers binaires
* loop.c - détection des boucles dans du code machine
*
* Copyright (C) 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 "loop.h"
#include
#include
#include
/* Suivi du flot d'exécution */
typedef struct _exec_flow
{
vmpa2t *steps; /* Jalons dans l'exécution */
size_t count; /* Quantité de ces points */
} exec_flow;
/* Initialise un flot d'exécution. */
static exec_flow *create_exec_flow(void);
/* Réalise la copie d'un flot d'exécution. */
static exec_flow *dup_exec_flow(const exec_flow *);
/* Efface de la mémoire un flot d'exécution. */
static void delete_exec_flow(exec_flow *);
/* Recherche si le chemin d'exécution a déjà mené à une adresse. */
static bool is_new_exec_flow(const exec_flow *, const vmpa2t *);
/* Ajoute une adresse jalon dans un flot d'exécution. */
static void add_step_into_exec_flow(exec_flow *, const vmpa2t *);
/* Suit un flot d'exécution à la recherche de boucles. */
static void track_loops_in_code(const GArchProcessor *, const mrange_t *, const vmpa2t *, exec_flow *);
/******************************************************************************
* *
* Paramètres : - *
* *
* Description : Initialise un flot d'exécution. *
* *
* Retour : Flot d'exécution nouveau. *
* *
* Remarques : - *
* *
******************************************************************************/
static exec_flow *create_exec_flow(void)
{
exec_flow *result; /* Flot vierge à retourner */
result = (exec_flow *)calloc(1, sizeof(exec_flow));
return result;
}
/******************************************************************************
* *
* Paramètres : src = jalons de l'exécution à dupliquer. *
* *
* Description : Réalise la copie d'un flot d'exécution. *
* *
* Retour : Flot d'exécution copié. *
* *
* Remarques : - *
* *
******************************************************************************/
static exec_flow *dup_exec_flow(const exec_flow *src)
{
exec_flow *result; /* Copie à retourner */
result = (exec_flow *)calloc(1, sizeof(exec_flow));
result->steps = (vmpa2t *)malloc(src->count * sizeof(vmpa2t));
memcpy(result->steps, src->steps, src->count * sizeof(vmpa2t));
result->count = src->count;
return result;
}
/******************************************************************************
* *
* Paramètres : flow = jalons de l'exécution à supprimer. *
* *
* Description : Efface de la mémoire un flot d'exécution. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void delete_exec_flow(exec_flow *flow)
{
if (flow->steps != NULL)
free(flow->steps);
free(flow);
}
/******************************************************************************
* *
* Paramètres : flow = ensemble des jalons de l'exécution du code. *
* addr = adresse d'un nouvel embranchement. *
* *
* Description : Recherche si le chemin d'exécution a déjà mené à une adresse.*
* *
* Retour : true si l'instruction est visitée pour la première fois. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool is_new_exec_flow(const exec_flow *flow, const vmpa2t *addr)
{
void *ret; /* Conclusion d'une recherche */
ret = bsearch(addr, flow->steps, flow->count,
sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa);
return (ret == NULL);
}
/******************************************************************************
* *
* Paramètres : flow = jalons de l'exécution du code à compléter. *
* addr = adresse d'un nouvel embranchement. *
* *
* Description : Ajoute une adresse jalon dans un flot d'exécution. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void add_step_into_exec_flow(exec_flow *flow, const vmpa2t *addr)
{
flow->steps = (vmpa2t *)realloc(flow->steps, ++flow->count * sizeof(vmpa2t));
copy_vmpa(&flow->steps[flow->count - 1], addr);
qsort(flow->steps, flow->count, sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa);
}
/******************************************************************************
* *
* Paramètres : proc = ensemble d'instructions à parcourir. *
* start = adresse du début de l'analyse. *
* end = adresse de fin de la routine traitée. *
* flow = ensemble des jalons de l'exécution du code. *
* *
* Description : Suit un flot d'exécution à la recherche de boucles. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void track_loops_in_code(const GArchProcessor *proc, const mrange_t *range, const vmpa2t *start, exec_flow *flow)
{
bool exit_track; /* Détermine la fin du parcours*/
GArchInstruction *iter; /* Boucle de parcours */
const mrange_t *irange; /* 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 */
const vmpa2t *addr; /* Prochaine adresse de saut */
exec_flow *next_flow; /* Suite de l'exécution */
add_step_into_exec_flow(flow, start);
exit_track = false;
for (iter = g_arch_processor_find_instr_by_address(proc, start);
iter != NULL && !exit_track;
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;
/* Fin de parcours ? */
if (g_arch_instruction_get_flags(iter) & AIF_RETURN_POINT)
break;
/**
* Afin de détecter les boucles le plus en aval possible,
* on marque toutes les arrivées potentielles de boucles comme jalons.
* Ainsi la détection se réalise sur l'ultime saut qui boucle effectivement.
*/
if (g_arch_instruction_has_sources(iter))
{
addr = get_mrange_addr(irange);
if (is_new_exec_flow(flow, addr))
add_step_into_exec_flow(flow, addr);
}
/* Analyse des destinations */
dcount = g_arch_instruction_get_destinations(iter, &dests, &types, NULL);
if (dcount == 0) continue;
for (i = 0; i < dcount; i++)
switch (types[i])
{
case ILT_LOOP:
/**
* On est déjà passé par là, donc on peut arrêter le parcours courant.
*/
exit_track = true;
break;
case ILT_CATCH_EXCEPTION:
irange = g_arch_instruction_get_range(dests[i]);
addr = get_mrange_addr(irange);
next_flow = create_exec_flow();
track_loops_in_code(proc, range, addr, next_flow);
delete_exec_flow(next_flow);
break;
case ILT_EXEC_FLOW:
case ILT_JUMP:
case ILT_CASE_JUMP:
case ILT_JUMP_IF_TRUE:
case ILT_JUMP_IF_FALSE:
/**
* On se lance dans d'autres suivis qui vont parcourir le reste des
* instructions, donc on peut arrêter le parcours courant ici.
*/
exit_track = true;
irange = g_arch_instruction_get_range(dests[i]);
addr = get_mrange_addr(irange);
if (!is_new_exec_flow(flow, addr))
/* status = */g_arch_instruction_change_link(iter, dests[i], types[i], ILT_LOOP);
else
{
next_flow = dup_exec_flow(flow);
track_loops_in_code(proc, range, addr, next_flow);
delete_exec_flow(next_flow);
}
break;
default:
break;
}
}
}
/******************************************************************************
* *
* Paramètres : proc = 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 : Détecte les boucles dans du code machine. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void detect_loops_in_code(const GArchProcessor *proc, GBinRoutine **routines, size_t count, GtkExtStatusBar *statusbar, bstatus_id_t id)
{
size_t i; /* Boucle de parcours */
const mrange_t *range; /* Couverture d'une routine */
exec_flow *flow; /* Flot d'exécution à suivre */
for (i = 0; i < count; i++)
{
range = g_binary_routine_get_range(routines[i]);
flow = create_exec_flow();
track_loops_in_code(proc, range, get_mrange_addr(range), flow);
delete_exec_flow(flow);
gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count);
}
}