/* 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 "dragon.h"
/* 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 : 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 */
const bitfield_t *dominators; /* Liste de dominateurs */
GArchInstruction *last; /* Instruction finale de noeud */
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++)
{
GArchInstruction *first;
node = get_dragon_node(nodes, k);
dominators = get_domination_bits(node);
get_dragon_node_bounding_instructions(node, &first, &last);
printf("#[ node %zu ]# @ 0x%08x / 0x%08x - mask = 0x%08lx\n", k,
(unsigned int)g_arch_instruction_get_range(first)->addr.virtual,
(unsigned int)g_arch_instruction_get_range(last)->addr.virtual,
gfw(dominators));
}
printf("\n");
for (k = 1; k < count; k++)
{
node = get_dragon_node(nodes, k);
dominators = get_domination_bits(node);
get_dragon_node_bounding_instructions(node, NULL, &last);
dcount = g_arch_instruction_get_destinations(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 = get_dragon_node_index(nodes, target);
if (test_in_bit_field(dominators, id, 1))
{
printf("BACKEDGE :: 0x%08lx -> 0x%08lx\n",
(unsigned int)g_arch_instruction_get_range(last)->addr.virtual,
(unsigned int)g_arch_instruction_get_range(dests[i])->addr.virtual);
/* status = */g_arch_instruction_change_link(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_knight *knight; /* Complexité de code posée */
dragon_node *nodes; /* Liste des noeuds détectés */
size_t count; /* Taille de cette liste */
knight = begin_dragon_knight(proc, coverage, range, start);
if (knight == NULL) return;
assert(knight != NULL);
get_dragon_knight_content(knight, &nodes, &count);
printf("nodes count :: %d\n", (int)count);
compute_all_dominators(nodes, count);
detect_back_edges(nodes, count);
end_dragon_knight(knight);
}
/******************************************************************************
* *
* 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