/* 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 .
*/
#include "macro.h"
#include
#include "../blocks/flow.h"
#include "../blocks/virtual.h"
/**
* 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)
/* Détermine la couverture d'un ensemble de chemins. */
static bitfield_t *compute_other_paths_mask(const dragon_knight *, GArchInstruction **, InstructionLinkType *, size_t, size_t);
/* Procède à la définition de bloc regroupant des instructions. */
static GInstrBlock *build_instruction_blocks(GArchProcessor *, const dragon_knight *, dragon_node *, const bitfield_t *, bitfield_t *, size_t *);
/******************************************************************************
* *
* Paramètres : knight = représentation de la complexité du code. *
* dests = instructions pointées à consulter. *
* types = types associés aux destinations. *
* dcount = nombre de destinations. *
* current = indice de la destionation courante. *
* *
* Description : Détermine la couverture d'un ensemble de chemins. *
* *
* Retour : Champ de bits mis en place. *
* *
* Remarques : - *
* *
******************************************************************************/
static bitfield_t *compute_other_paths_mask(const dragon_knight *knight, GArchInstruction **dests, InstructionLinkType *types, size_t dcount, size_t current)
{
bitfield_t *result; /* Couverture à retourner */
size_t length; /* Taille du champ de bits */
InstructionLinkType target; /* Type de noeud à cibler */
size_t i; /* Boucle de parcours */
dragon_node *node; /* Noeud à considérer */
get_dragon_knight_content(knight, NULL, &length);
result = create_bit_field(length, false);
target = types[current];
if (target == ILT_JUMP_IF_TRUE)
target = ILT_JUMP_IF_FALSE;
else if (target == ILT_JUMP_IF_FALSE)
target = ILT_JUMP_IF_TRUE;
assert(target == ILT_CASE_JUMP || target == ILT_JUMP_IF_TRUE || target == ILT_JUMP_IF_FALSE);
for (i = 0; i < dcount; i++)
{
if (i == current)
continue;
if (types[i] == target)
{
node = find_knight_node_for_instruction(knight, false, dests[i]);
if (node == NULL) continue;
or_bit_field(result, get_paths_bits(node));
}
}
return result;
}
/******************************************************************************
* *
* Paramètres : proc = 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_blocks(GArchProcessor *proc, const dragon_knight *knight, dragon_node *node, const bitfield_t *stop, bitfield_t *converted, size_t *next)
{
GInstrBlock *result; /* Regroupement à retourner */
GInstrBlock *result_cached; /* Temporisation pour unicité */
size_t id; /* Indice du bit associé */
GArchInstruction *first; /* Première instruction de bloc*/
GArchInstruction *last; /* Dernière instruction de bloc*/
GInstrBlock *block; /* Nouveau bloc mis en place */
bitfield_t *local_stop; /* Arrêts pour les sous-blocs */
bitfield_t *others; /* Couvertures des autres */
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 */
dragon_node *target; /* Noeud suivant à traiter */
GInstrBlock *group; /* Regroupement à retourner */
GInstrBlock *group_cached ; /* Temporisation pour unicité */
result = NULL;
result_cached = NULL;
while (1)
{
id = get_dragon_knight_node_index(knight, node);
/**
* Si on traite une des branches Vrai/Faux et que cette branche est vide,
* on doit s'arrêter.
*/
//printf("=== [%d] PROCESSING NODE %u (0x%x) in 0x%08x\n", fff, id, 1 << id, gfw(stop));
if (test_in_bit_field(stop, id, 1))
{
//printf(" -- STOP\n");
*next = id;
break;
}
/**
* Si le bloc a déjà été converti, on arrête la conversion pour la branche courante.
*
* Cela peut correspondre à la situation suivante quand on revient sur le bloc
* inférieur droit :
*
* ======
* / \
* === |
* / \ |
* | `.|
* | ||
* === ===
*/
if (test_in_bit_field(converted, id, 1))
{
//printf(" HALT\n");
*next = 0;
break;
}
/* Constitution et ajout d'un bloc */
get_dragon_node_bounding_instructions(node, &first, &last);
/*
printf(" -- [%d] process block %u @ 0x%08x <-> 0x%08x\n",
fff, (unsigned int)id,
(unsigned int)first->range.addr.virtual,
(unsigned int)last->range.addr.virtual);
*/
block = g_flow_block_new(proc, first, last);
DELAYED_BLOCK_ADDING(result, result_cached, block);
set_in_bit_field(converted, id, 1);
/* Détermination du prochain arrêt */
local_stop = create_bit_field_from(stop, true);
others = NULL;
g_arch_instruction_rlock_dest(last);
dcount = g_arch_instruction_get_destinations(last, &dests, &types);
for (i = 0; i < dcount && others == NULL; i++)
switch (types[i])
{
case ILT_EXEC_FLOW:
case ILT_JUMP:
break;
case ILT_LOOP:
break;
case ILT_CASE_JUMP:
case ILT_JUMP_IF_TRUE:
case ILT_JUMP_IF_FALSE:
target = find_knight_node_for_instruction(knight, false, dests[i]);
if (target == NULL) break;
id = get_dragon_knight_node_index(knight, target);
others = compute_other_paths_mask(knight, dests, types, dcount, i);
/**
* Si une patte est contenue dans une autre, on place la branche
* incluse comme borne de fin.
*/
if (test_in_bit_field(others, id, 1))
{
reset_all_in_bit_field(others);
set_in_bit_field(others, id, 1);
}
/**
* Sinon la borne de fin est la sortie commune.
*/
else
{
delete_bit_field(others);
others = NULL;
and_bit_field(local_stop, get_paths_bits(target));
}
break;
case ILT_CATCH_EXCEPTION:
break;
default:
//assert(false);
break;
}
g_arch_instruction_runlock_dest(last);
if (others != NULL)
{
//printf(" HO \n");
delete_bit_field(local_stop);
local_stop = others;
}
//printf(" -- [%d] common :: 0x%08x\n", fff, gfw(local_stop));
//or_bit_field(local_stop, stop);
//printf(" -- [%d] common :: 0x%08x\n", fff, gfw(local_stop));
/* Récupération des sous-blocs */
*next = 0;
group = NULL;
group_cached = NULL;
for (i = 0; i < dcount; i++)
switch (types[i])
{
case ILT_EXEC_FLOW:
case ILT_JUMP:
/* Il ne peut y en avoir qu'un ! */
assert(*next == 0);
target = find_knight_node_for_instruction(knight, false, dests[i]);
if (target == NULL) break;
*next = get_dragon_knight_node_index(knight, target);
break;
case ILT_LOOP:
break;
case ILT_CASE_JUMP:
case ILT_JUMP_IF_TRUE:
case ILT_JUMP_IF_FALSE:
target = find_knight_node_for_instruction(knight, false, dests[i]);
if (target == NULL) break;
/*
printf(" -- call %d -> %zu -> %zu\n",
fff,
get_dragon_knight_node_index(knight, node),
get_dragon_knight_node_index(knight, target));
*/
block = build_instruction_blocks(proc, knight, target, local_stop, converted, &id);
//printf(" -> next id = %zu\n", id);
/* Le premier passage crée la référence */
if (*next == 0)
*next = id;
/**
* Une patte, première ou nom, peut se terminer alors que
* ses voisines continuent.
*
* Il y a donc plusieurs valeurs pour l'indice suivant :
* un nul et un strictement positif.
*
* Le cas typique est le suivant :
*
* ======
* / \
* | |
* ret |
* |
* ===
*/
else if (id > 0)
{
//printf(" NEXT :: %u vs %u\n", *next, id);
assert(*next == id);
}
if (block != NULL)
DELAYED_BLOCK_ADDING(group, group_cached, block);
break;
case ILT_CATCH_EXCEPTION:
break;
default:
//assert(false);
break;
}
if (/*group != NULL || */group_cached != NULL)
DELAYED_BLOCK_ADDING(result, result_cached, group != NULL ? group : group_cached);
delete_bit_field(local_stop);
/* On passe au noeud suivant */
if (*next == 0)
break;
node = get_dragon_knight_node(knight, *next);
}
return (result != NULL ? result : result_cached);
}
/******************************************************************************
* *
* Paramètres : routine = routine en code exécutable à traiter. *
* knight = rassemblement des complexités de code. *
* *
* Description : Procède à la définition de blocs regroupant des instructions.*
* *
* Retour : Blocs créés et enregistrés, ou NULL si erreur. *
* *
* Remarques : - *
* *
******************************************************************************/
void group_routine_instructions(GBinRoutine *routine, const dragon_knight *knight)
{
dragon_node *nodes; /* Liste des noeuds détectés */
size_t count; /* Taille de cette liste */
dragon_node *node; /* Noeud à traiter */
bitfield_t *stop; /* Bloc d'arrêt de l'analyse */
bitfield_t *converted; /* Cartographie des traitements*/
GInstrBlock *blocks; /* Blocs basiques construits */
get_dragon_knight_content(knight, &nodes, &count);
compute_all_paths(nodes, count);
#if 0
size_t k;
for (k = 0; k < count; k++)
{
GArchInstruction *first;
GArchInstruction *last;
const bitfield_t *paths;
node = get_dragon_node(nodes, k);
paths = get_paths_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(paths));
}
#endif
node = get_dragon_node(nodes, 0);
stop = create_bit_field(count, false);
converted = create_bit_field(count, false);
blocks = build_instruction_blocks(NULL, knight, node, stop, converted, (size_t []) { 0 });
delete_bit_field(stop);
#if 0
bool visit_block(GInstrBlock *blk, BlockVisitOrder order, int *indent)
{
int i;
switch (order)
{
case BVO_IN:
case BVO_PENDING:
for (i = 0; i < *indent; i++)
printf(" ");
printf("%p '%s'", blk, G_OBJECT_TYPE_NAME(blk));
if (G_IS_FLOW_BLOCK(blk))
{
vmpa2t start;
vmpa2t end;
g_flow_block_get_boundary_addresses(G_FLOW_BLOCK(blk), &start, &end);
printf(" 0x%08x -> 0x%08x",
(unsigned int)start.virtual,
(unsigned int)end.virtual);
}
printf("\n");
if (order == BVO_IN) (*indent)++;
break;
case BVO_OUT:
(*indent)--;
break;
}
return true;
}
g_instr_block_visit(blocks, (instr_block_visitor_cb)visit_block, (int []){ 0 });
printf("\n");
#endif
//if (blocks != NULL)
g_binary_routine_set_basic_blocks(routine, blocks);
}