From 1aac673d39180b661f6a2dc5ff6335a1cfa0b0a7 Mon Sep 17 00:00:00 2001
From: Cyrille Bagard <nocbos@gmail.com>
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 <nocbos@gmail.com>
+ * 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 <nocbos@gmail.com>
+
* 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