/* OpenIDA - 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 OpenIDA.
*
* 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
{
vmpa_t *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 *, vmpa_t);
/* Ajoute une adresse jalon dans un flot d'exécution. */
static void add_step_into_exec_flow(exec_flow *, vmpa_t);
/* Suit un flot d'exécution à la recherche de boucles. */
static void track_loops_in_code(GArchInstruction *, vmpa_t, vmpa_t, 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 = (vmpa_t *)malloc(src->count * sizeof(vmpa_t));
memcpy(result->steps, src->steps, src->count * sizeof(vmpa_t));
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)
{
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, vmpa_t addr)
{
void *ret; /* Conclusion d'une recherche */
ret = bsearch(&addr, flow->steps, flow->count,
sizeof(vmpa_t), (__compar_fn_t)compare_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, vmpa_t addr)
{
flow->steps = (vmpa_t *)realloc(flow->steps, ++flow->count * sizeof(vmpa_t));
flow->steps[flow->count - 1] = addr;
qsort(flow->steps, flow->count, sizeof(vmpa_t), (__compar_fn_t)compare_vmpa);
}
/******************************************************************************
* *
* Paramètres : list = 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(GArchInstruction *list, vmpa_t start, vmpa_t end, exec_flow *flow)
{
bool exit_track; /* Détermine la fin du parcours*/
GArchInstruction *iter; /* Boucle de parcours */
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 */
vmpa_t 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_instruction_find_by_address(list, start, true);
iter != NULL && !exit_track;
iter = g_arch_instruction_get_next_iter(list, iter, end))
{
if (g_arch_instruction_is_return(iter))
break;
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_CALL:
case ILT_CATCH_EXCEPTION:
break;
default:
/**
* 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;
g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
if (!is_new_exec_flow(flow, addr))
types[i] = ILT_LOOP;
else
{
next_flow = dup_exec_flow(flow);
track_loops_in_code(list, addr, end, next_flow);
delete_exec_flow(next_flow);
}
break;
}
}
}
/******************************************************************************
* *
* 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 : Détecte les boucles dans du code machine. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void detect_loops_in_code(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 */
exec_flow *flow; /* Flot d'exécution à suivre */
for (i = 0; i < count; i++)
{
start = g_binary_routine_get_address(routines[i]);
end = start + g_binary_routine_get_size(routines[i]);
flow = create_exec_flow();
track_loops_in_code(list, start, end, flow);
delete_exec_flow(flow);
gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count);
}
}