From 1aac673d39180b661f6a2dc5ff6335a1cfa0b0a7 Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Sat, 15 Oct 2016 17:13:52 +0200 Subject: Avoided many infinite loops when computing ranks in Dalvik basic blocks. --- ChangeLog | 9 +++++ src/analysis/disass/dragon.c | 80 ++++++++++++++++++++++++++------------- src/analysis/disass/rank.c | 12 ++++++ src/arch/dalvik/opdefs/throw_27.d | 6 +++ 4 files changed, 81 insertions(+), 26 deletions(-) diff --git a/ChangeLog b/ChangeLog index 4f75240..82e3f2b 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,14 @@ 16-10-15 Cyrille Bagard + * src/analysis/disass/dragon.c: + * src/analysis/disass/rank.c: + Avoid many infinite loops when computing ranks in Dalvik basic blocks. + + * src/arch/dalvik/opdefs/throw_27.d: + Consider exception throws as return points. + +16-10-15 Cyrille Bagard + * src/analysis/db/item.c: * src/analysis/db/item.h: Ensure all items have their label when it is requested. diff --git a/src/analysis/disass/dragon.c b/src/analysis/disass/dragon.c index 24c24dc..58c293e 100644 --- a/src/analysis/disass/dragon.c +++ b/src/analysis/disass/dragon.c @@ -92,7 +92,7 @@ struct _dragon_knight * Remarques : - * * * ******************************************************************************/ -#include "../../arch/instruction-int.h" + 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 */ @@ -102,9 +102,11 @@ static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_ 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 scount; /* Nombre de liens de source */ + bool cut; /* Un découpage a été réalisé ?*/ size_t i; /* Boucle de parcours */ dragon_node *new; /* Nouvel élément à créer */ + size_t dcount; /* Nombre de liens de dest. */ result = NULL; *count = 0; @@ -123,7 +125,7 @@ static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_ if (!mrange_contains_mrange(range, irange)) break; - /* Analyse des sources */ + /* Découpage en blocs */ if (need_alloc) { @@ -143,13 +145,31 @@ static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_ } + /** + * Il y a plusieurs raisons à la création d'un nouveau bloc : + * + * - une instruction définit un saut vers une autre, + * et cette seconde instruction démarre donc un nouveau bloc. + * + * Pour traiter ce cas, il suffit d'analyser toutes les arrivées. + * + * - une instruction réalise un saut inconditionnel vers une autre. + * Cela se matérialise par un lien de type ILT_JUMP, ou de façon + * plus abstraite par un point de retour. + * + * Pour traiter ce cas, on s'attache à regarder les destinations. + */ else { + /* Analyse des sources */ + g_arch_instruction_rlock_src(iter); scount = g_arch_instruction_get_sources(iter, NULL, &types); - for (i = 0; i < scount; i++) + cut = false; + + for (i = 0; i < scount && !cut; i++) switch (types[i]) { case ILT_EXEC_FLOW: @@ -158,17 +178,7 @@ static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_ case ILT_JUMP_IF_TRUE: case ILT_JUMP_IF_FALSE: - if (*count > 0) - result[*count - 1].last = last; - - - /* - printf(" %% ?jmp? %% cut @ %zu ; last = 0x%08x ; iter = 0x%08x\n", *count - 1, - (unsigned int)last->range.addr.virtual, - (unsigned int)iter->range.addr.virtual); - fflush(NULL); - */ - + result[*count - 1].last = last; (*count)++; i = scount; @@ -183,6 +193,8 @@ static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_ new->first = iter; + cut = true; + break; default: @@ -194,24 +206,40 @@ static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_ } + /* Analyse des destinations */ + g_arch_instruction_rlock_dest(iter); + dcount = g_arch_instruction_get_destinations(iter, NULL, &types, NULL); - if (g_arch_instruction_get_flags(iter) & AIF_RETURN_POINT) - { - if (*count > 0) - result[*count - 1].last = iter; + cut = false; + + for (i = 0; i < dcount && !cut; i++) + switch (types[i]) + { + case ILT_JUMP: - /* - printf(" %% return %% cut @ %zu ; addr = 0x%08x\n", *count - 1, - (unsigned int)iter->range.addr.virtual); - fflush(NULL); - */ + result[*count - 1].last = iter; - need_alloc = true; + cut = true; - } + need_alloc = true; + + break; + default: + break; + } + + g_arch_instruction_runlock_dest(iter); + + if (!need_alloc && g_arch_instruction_get_flags(iter) & AIF_RETURN_POINT) + { + result[*count - 1].last = iter; + + need_alloc = true; + + } } diff --git a/src/analysis/disass/rank.c b/src/analysis/disass/rank.c index 0b9068b..7504231 100644 --- a/src/analysis/disass/rank.c +++ b/src/analysis/disass/rank.c @@ -324,6 +324,18 @@ void rank_routine_block(const GBlockList *list, GBasicBlock *block) /* La boucle de remontée n'abaisse pas les rangs */ if (types[i] == ILT_LOOP) continue; + /** + * On se doit de suivre le même cheminement que celui emprunté lors + * du parcours de create_dragon_nodes(). + * Sinon, les chemins divergent et une récursion infinie peut survenir. + */ + if (types[i] != ILT_EXEC_FLOW + && types[i] != ILT_JUMP + && types[i] != ILT_CASE_JUMP + && types[i] != ILT_JUMP_IF_TRUE + && types[i] != ILT_JUMP_IF_FALSE) + continue; + target = g_block_list_find_by_starting_instr(list, dests[i]); /** diff --git a/src/arch/dalvik/opdefs/throw_27.d b/src/arch/dalvik/opdefs/throw_27.d index 28a8348..79c71dd 100644 --- a/src/arch/dalvik/opdefs/throw_27.d +++ b/src/arch/dalvik/opdefs/throw_27.d @@ -27,4 +27,10 @@ @format 11x + @rules { + + call SetInsFlag(AIF_RETURN_POINT) + + } + } -- cgit v0.11.2-87-g4458