Avoided many infinite loops when computing ranks in Dalvik basic blocks.

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)
+
+    }
+
 }