/* 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 "../../common/bits.h"
/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */
typedef 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 */
} dragon_node;
/* 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 *);
/* Termine l'initialisation de noeuds trouvés dans une routine. */
static void define_mask_for_nodes(dragon_node *, size_t);
/* Supprime de la mémoire tous les noeuds détectés. */
static void delete_dragon_nodes(dragon_node *, size_t);
/* Recherche un noeud selon son intruction de départ. */
static dragon_node *find_node_for_instruction(dragon_node *, size_t, bool, const GArchInstruction *);
/* Détermine toute la chaîne hiérarchique de domination. */
static void compute_all_dominators(dragon_node *, size_t);
/* Matérialise les liens de retour arrière en tant que boucles. */
static void detect_back_edges(dragon_node *, size_t);
/* Suit un flot d'exécution à la recherche de boucles. */
static void track_loops_in_code(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, memfield_t *);
/******************************************************************************
* *
* 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 : Termine l'initialisation de noeuds trouvés dans une routine. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void define_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 : 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 à 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 : - *
* *
******************************************************************************/
static 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 : - *
* *
******************************************************************************/
static 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 : nodes = liste de noeuds détectés dans une routine. *
* count = taille de cette liste de noeuds à traiter. *
* *
* Description : Matérialise les liens de retour arrière en tant que boucles. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void detect_back_edges(dragon_node *nodes, size_t count)
{
size_t k; /* Boucle de parcours #1 */
dragon_node *node; /* Noeud à traiter */
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 */
dragon_node *target; /* Noeud référencé à tester */
size_t id; /* Indice du bit associé */
printf("-----------------------------------------------------------------\n");
for (k = 0; k < count; k++)
{
node = &nodes[k];
printf("#[ node %zu ]# @ 0x%08x / 0x%08x - mask = 0x%08lx\n", k,
(unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual,
(unsigned int)g_arch_instruction_get_range(node->last)->addr.virtual,
gfw(node->bits));
}
printf("\n");
for (k = 1; k < count; k++)
{
node = &nodes[k];
dcount = g_arch_instruction_get_destinations(node->last, &dests, &types, NULL);
if (dcount == 0) continue;
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:
target = find_node_for_instruction(nodes, count, false, dests[i]);
if (target == NULL) break;
id = (target - nodes);
if (test_in_bit_field(node->bits, id, 1))
{
printf("BACKEDGE :: 0x%08lx -> 0x%08lx\n",
(unsigned int)g_arch_instruction_get_range(node->last)->addr.virtual,
(unsigned int)g_arch_instruction_get_range(dests[i])->addr.virtual);
/* status = */g_arch_instruction_change_link(node->last, dests[i], types[i], ILT_LOOP);
}
break;
default:
break;
}
}
}
/******************************************************************************
* *
* 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. *
* 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 instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, memfield_t *flow)
{
dragon_node *nodes; /* Liste des noeuds détectés */
size_t count; /* Taille de cette liste */
nodes = create_dragon_nodes(proc, coverage, range, start, &count);
assert(nodes != NULL);
printf("nodes count :: %d\n", (int)count);
define_mask_for_nodes(nodes, count);
compute_all_dominators(nodes, count);
detect_back_edges(nodes, count);
delete_dragon_nodes(nodes, count);
}
/******************************************************************************
* *
* 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 */
const vmpa2t *start; /* Adresse de départ */
const instr_coverage *coverage; /* Instructions couvertes */
memfield_t *flow; /* Flot d'exécution à suivre */
//for (i = 286; i == 286; i++)
for (i = 0; i < count; i++)
{
range = g_binary_routine_get_range(routines[i]);
start = get_mrange_addr(range);
printf("====== '%s' @ 0x%08x\n",
g_binary_routine_get_name(routines[i]),
start->virtual);
coverage = g_arch_processor_find_coverage_by_address(proc, start);
flow = NULL;//create_mem_field(range);
track_loops_in_code(proc, coverage, range, start, flow);
//delete_mem_field(flow);
gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count);
}
printf("done\n\n");
//exit(0);
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////
#if 0
#include
#include
#include
#include "../../common/bits.h"
/* Suit un flot d'exécution à la recherche de boucles. */
static void track_loops_in_code(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, memfield_t *);
/******************************************************************************
* *
* 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. *
* 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 instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, memfield_t *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 */
memfield_t *next_flow; /* Suite de l'exécution */
set_in_mem_field(flow, start);
exit_track = false;
for (iter = g_arch_processor_find_covered_instr_by_address(proc, coverage, 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 (!test_in_mem_field(flow, addr))
set_in_mem_field(flow, start);
}
/* 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_mem_field_from(flow);
track_loops_in_code(proc, coverage, range, addr, next_flow);
delete_mem_field(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]);
if (!mrange_contains_mrange(range, irange))
break;
addr = get_mrange_addr(irange);
if (test_in_mem_field(flow, addr))
/* status = */g_arch_instruction_change_link(iter, dests[i], types[i], ILT_LOOP);
else
{
next_flow = dup_mem_field(flow);
track_loops_in_code(proc, coverage, range, addr, next_flow);
delete_mem_field(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 */
const vmpa2t *start; /* Adresse de départ */
const instr_coverage *coverage; /* Instructions couvertes */
memfield_t *flow; /* Flot d'exécution à suivre */
for (i = 0; i < count; i++)
{
range = g_binary_routine_get_range(routines[i]);
start = get_mrange_addr(range);
coverage = g_arch_processor_find_coverage_by_address(proc, start);
flow = create_mem_field(range);
track_loops_in_code(proc, coverage, range, start, flow);
delete_mem_field(flow);
gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count);
}
}
#endif