Improved the disassembling process by handling loops in code.

git-svn-id: svn://svn.gna.org/svn/chrysalide/trunk@339 abbe820e-26c8-41b2-8c08-b7b2b41f8b0a

11 files changed, 407 insertions, 21 deletions

diff --git a/ChangeLog b/ChangeLog
index d830550..918e55a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,25 @@
+13-02-10  Cyrille Bagard <nocbos@gmail.com>
+
+	* src/analysis/disass/disassembler.c:
+	Update the number of steps when disassembling code.
+
+	* src/analysis/disass/loop.c:
+	* src/analysis/disass/loop.h:
+	New entries: detect loops in code.
+
+	* src/analysis/disass/macro.c:
+	Improve the disassembling process by handling loops in code.
+
+	* src/analysis/disass/Makefile.am:
+	Add the 'loop.[ch]' files to libanalysisdisass_la_SOURCES.
+
+	* src/arch/instruction.h:
+	* src/gtkext/graph/dot.c:
+	* src/gtkext/graph/layout.c:
+	* src/gtkext/gtklinkrenderer.c:
+	* src/gtkext/gtklinkrenderer.h:
+	Introduce and handle loop links.
+
 13-02-05  Cyrille Bagard <nocbos@gmail.com>
 
 	* src/analysis/decomp/reduce.c:
diff --git a/src/analysis/disass/Makefile.am b/src/analysis/disass/Makefile.am
index 854c726..45fc3fd 100644
--- a/src/analysis/disass/Makefile.am
+++ b/src/analysis/disass/Makefile.am
@@ -6,6 +6,7 @@ libanalysisdisass_la_SOURCES =			\
 	fetch.h fetch.c						\
 	limit.h limit.c						\
 	links.h links.c						\
+	loop.h loop.c						\
 	macro.h macro.c						\
 	output.h output.c
 
diff --git a/src/analysis/disass/disassembler.c b/src/analysis/disass/disassembler.c
index 8f1d3f1..8c816f6 100644
--- a/src/analysis/disass/disassembler.c
+++ b/src/analysis/disass/disassembler.c
@@ -35,6 +35,7 @@
 #include "fetch.h"
 #include "limit.h"
 #include "links.h"
+#include "loop.h"
 #include "macro.h"
 #include "output.h"
 #include "../../decomp/lang/asm.h"
@@ -258,6 +259,14 @@ static void g_delayed_disassembly_process(GDelayedDisassembly *disass, GtkExtSta
 
     /* Quatrième étape */
 
+    id = gtk_extended_status_bar_push(statusbar, _("Detecting loops..."), true);
+
+    detect_loops_in_code(*disass->instrs, routines, routines_count, statusbar, id);
+
+    gtk_extended_status_bar_remove(statusbar, id);
+
+    /* Cinquième étape */
+
     id = gtk_extended_status_bar_push(statusbar, _("Grouping routines instructions..."), true);
 
     qsort(routines, routines_count, sizeof(GBinRoutine *), (__compar_fn_t)g_binary_routine_rcompare);
@@ -268,7 +277,7 @@ static void g_delayed_disassembly_process(GDelayedDisassembly *disass, GtkExtSta
 
     run_plugins_on_binary(disass->binary, PGA_BINARY_GROUPED, true);
 
-    /* Cinquième étape */
+    /* Sixième étape */
 
     id = gtk_extended_status_bar_push(statusbar, _("Printing disassembled code..."), true);
 
diff --git a/src/analysis/disass/loop.c b/src/analysis/disass/loop.c
new file mode 100644
index 0000000..301f084
--- /dev/null
+++ b/src/analysis/disass/loop.c
@@ -0,0 +1,283 @@
+
+/* OpenIDA - 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 OpenIDA.
+ *
+ *  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 <http://www.gnu.org/licenses/>.
+ */
+
+
+#include "loop.h"
+
+
+#include <malloc.h>
+#include <stdlib.h>
+#include <string.h>
+
+
+
+/* Suivi du flot d'exécution */
+typedef struct _exec_flow
+{
+    vmpa_t *steps;                          /* Jalons dans l'exécution     */
+    size_t count;                           /* Quantité de ces points      */
+
+} exec_flow;
+
+
+/* Initialise un flot d'exécution. */
+static exec_flow *create_exec_flow(void);
+
+/* Réalise la copie d'un flot d'exécution. */
+static exec_flow *dup_exec_flow(const exec_flow *);
+
+/* Efface de la mémoire un flot d'exécution. */
+static void delete_exec_flow(exec_flow *);
+
+/* Recherche si le chemin d'exécution a déjà mené à une adresse. */
+static bool is_new_exec_flow(const exec_flow *, vmpa_t);
+
+/* Ajoute une adresse jalon dans un flot d'exécution. */
+static void add_step_into_exec_flow(exec_flow *, vmpa_t);
+
+/* Suit un flot d'exécution à la recherche de boucles. */
+static void track_loops_in_code(GArchInstruction *, vmpa_t, vmpa_t, exec_flow *);
+
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : -                                                            *
+*                                                                             *
+*  Description : Initialise un flot d'exécution.                              *
+*                                                                             *
+*  Retour      : Flot d'exécution nouveau.                                    *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static exec_flow *create_exec_flow(void)
+{
+    exec_flow *result;                      /* Flot vierge à retourner     */
+
+    result = (exec_flow *)calloc(1, sizeof(exec_flow));
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : src = jalons de l'exécution à dupliquer.                     *
+*                                                                             *
+*  Description : Réalise la copie d'un flot d'exécution.                      *
+*                                                                             *
+*  Retour      : Flot d'exécution copié.                                      *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static exec_flow *dup_exec_flow(const exec_flow *src)
+{
+    exec_flow *result;                      /* Copie à retourner           */
+
+    result = (exec_flow *)calloc(1, sizeof(exec_flow));
+
+    result->steps = (vmpa_t *)malloc(src->count * sizeof(vmpa_t));
+    memcpy(result->steps, src->steps, src->count * sizeof(vmpa_t));
+
+    result->count = src->count;
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : flow = jalons de l'exécution à supprimer.                    *
+*                                                                             *
+*  Description : Efface de la mémoire un flot d'exécution.                    *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void delete_exec_flow(exec_flow *flow)
+{
+    free(flow->steps);
+
+    free(flow);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : flow = ensemble des jalons de l'exécution du code.           *
+*                addr = adresse d'un nouvel embranchement.                    *
+*                                                                             *
+*  Description : Recherche si le chemin d'exécution a déjà mené à une adresse.*
+*                                                                             *
+*  Retour      : true si l'instruction est visitée pour la première fois.     *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static bool is_new_exec_flow(const exec_flow *flow, vmpa_t addr)
+{
+    void *ret;                              /* Conclusion d'une recherche  */
+
+    ret = bsearch(&addr, flow->steps, flow->count,
+                  sizeof(vmpa_t), (__compar_fn_t)compare_vmpa);
+
+    return (ret == NULL);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : flow = jalons de l'exécution du code à compléter.            *
+*                addr = adresse d'un nouvel embranchement.                    *
+*                                                                             *
+*  Description : Ajoute une adresse jalon dans un flot d'exécution.           *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void add_step_into_exec_flow(exec_flow *flow, vmpa_t addr)
+{
+    flow->steps = (vmpa_t *)realloc(flow->steps, ++flow->count * sizeof(vmpa_t));
+    flow->steps[flow->count - 1] = addr;
+
+    qsort(flow->steps, flow->count, sizeof(vmpa_t), (__compar_fn_t)compare_vmpa);
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : list  = ensemble d'instructions à parcourir.                 *
+*                start = adresse du début de l'analyse.                       *
+*                end   = adresse de fin de la routine traitée.                *
+*                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(GArchInstruction *list, vmpa_t start, vmpa_t end, exec_flow *flow)
+{
+    GArchInstruction *iter;                 /* Boucle de parcours          */
+    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          */
+    vmpa_t addr;                            /* Prochaine adresse de saut   */
+    exec_flow *next_flow;                   /* Suite de l'exécution        */
+
+    add_step_into_exec_flow(flow, start);
+
+    for (iter = g_arch_instruction_find_by_address(list, start, true);
+         iter != NULL;
+         iter = g_arch_instruction_get_next_iter(list, iter, end))
+    {
+        dcount = g_arch_instruction_get_destinations(iter, &dests, &types, NULL);
+
+        for (i = 0; i < dcount; i++)
+            switch (types[i])
+            {
+                case ILT_LOOP:
+                    break;
+
+                case ILT_CALL:
+                case ILT_CATCH_EXCEPTION:
+                    break;
+
+                default:
+                    g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
+
+                    if (!is_new_exec_flow(flow, addr))
+                        types[i] = ILT_LOOP;
+
+                    else
+                    {
+                        next_flow = dup_exec_flow(flow);
+                        track_loops_in_code(list, addr, end, next_flow);
+                        delete_exec_flow(next_flow);
+                    }
+
+                    break;
+
+            }
+
+    }
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : list      = 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(GArchInstruction *list, GBinRoutine **routines, size_t count, GtkExtStatusBar *statusbar, guint id)
+{
+    size_t i;                               /* Boucle de parcours          */
+    vmpa_t start;                           /* Adresse de départ           */
+    vmpa_t end;                             /* Adresse de fin              */
+    exec_flow *flow;                        /* Flot d'exécution à suivre   */
+
+    for (i = 0; i < count; i++)
+    {
+        start = g_binary_routine_get_address(routines[i]);
+        end = start + g_binary_routine_get_size(routines[i]);
+
+        flow = create_exec_flow();
+        track_loops_in_code(list, start, end, flow);
+        delete_exec_flow(flow);
+
+        gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count);
+
+    }
+
+}
diff --git a/src/analysis/disass/loop.h b/src/analysis/disass/loop.h
new file mode 100644
index 0000000..8466405
--- /dev/null
+++ b/src/analysis/disass/loop.h
@@ -0,0 +1,38 @@
+
+/* OpenIDA - Outil d'analyse de fichiers binaires
+ * loop.h - prototypes pour la détection des boucles dans du code machine
+ *
+ * Copyright (C) 2013 Cyrille Bagard
+ *
+ *  This file is part of OpenIDA.
+ *
+ *  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 <http://www.gnu.org/licenses/>.
+ */
+
+
+#ifndef _ANALYSIS_DISASS_LOOP_H
+#define _ANALYSIS_DISASS_LOOP_H
+
+
+#include "../routine.h"
+#include "../../gtkext/gtkextstatusbar.h"
+
+
+
+/* Détecte les boucles dans du code machine. */
+void detect_loops_in_code(GArchInstruction *, GBinRoutine **, size_t, GtkExtStatusBar *, guint);
+
+
+
+#endif  /* _ANALYSIS_DISASS_LOOP_H */
diff --git a/src/analysis/disass/macro.c b/src/analysis/disass/macro.c
index 8766ed9..ebd236a 100644
--- a/src/analysis/disass/macro.c
+++ b/src/analysis/disass/macro.c
@@ -303,6 +303,7 @@ static void find_next_jumps(GArchInstruction *instrs, vmpa_t start, const code_c
     InstructionLinkType *types;             /* Type de lien entre lignes   */
     size_t dcount;                          /* Nombre de liens de dest.    */
     size_t i;                               /* Boucle de parcours #2       */
+    vmpa_t daddr;                           /* Adresse de destination      */
 
     /* On évite de boucler... */
     if (is_addr_in_branch(info, &start))
@@ -340,8 +341,14 @@ static void find_next_jumps(GArchInstruction *instrs, vmpa_t start, const code_c
                 case ILT_CASE_JUMP:
                 case ILT_JUMP_IF_TRUE:
                 case ILT_JUMP_IF_FALSE:
-                    g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
-                    find_next_jumps(instrs, addr, coverage, info);
+                    g_arch_instruction_get_location(dests[i], NULL, NULL, &daddr);
+                    find_next_jumps(instrs, daddr, coverage, info);
+                    break;
+
+                case ILT_LOOP:
+                    g_arch_instruction_get_location(dests[i], NULL, NULL, &daddr);
+                    info->jumps = (vmpa_t *)realloc(info->jumps, ++(info->count) * sizeof(vmpa_t));
+                    info->jumps[info->count - 1] = daddr;
                     break;
 
                 default:
@@ -681,30 +688,43 @@ static GInstrBlock *build_instruction_block(GArchInstruction *instrs, const code
 
             /* Branche 'true' */
 
-            sub_coverage = dup_code_coverage(true_branch.jumps[0], coverage);
-            add_ending_address_code_coverage(sub_coverage, &next_addr);
-            add_ending_address_code_coverage(sub_coverage, &false_branch.jumps[0]);
+            if (true_branch.count > 0)
+            {
+                sub_coverage = dup_code_coverage(true_branch.jumps[0], coverage);
+                add_ending_address_code_coverage(sub_coverage, &next_addr);
+                if (false_branch.count > 0)
+                    add_ending_address_code_coverage(sub_coverage, &false_branch.jumps[0]);
 
-            block = build_instruction_block(instrs, sub_coverage);
-            if (block != NULL)
-                g_virtual_block_add_child(G_VIRTUAL_BLOCK(group), block);
+                block = build_instruction_block(instrs, sub_coverage);
+                if (block != NULL)
+                    g_virtual_block_add_child(G_VIRTUAL_BLOCK(group), block);
 
-            delete_code_coverage(sub_coverage);
+                delete_code_coverage(sub_coverage);
+
+            }
 
             /* Branche 'false' */
 
-            sub_coverage = dup_code_coverage(false_branch.jumps[0], coverage);
-            add_ending_address_code_coverage(sub_coverage, &next_addr);
-            add_ending_address_code_coverage(sub_coverage, &true_branch.jumps[0]);
+            if (false_branch.count > 0)
+            {
+                sub_coverage = dup_code_coverage(false_branch.jumps[0], coverage);
+                add_ending_address_code_coverage(sub_coverage, &next_addr);
+                if (true_branch.count > 0)
+                    add_ending_address_code_coverage(sub_coverage, &true_branch.jumps[0]);
 
-            block = build_instruction_block(instrs, sub_coverage);
-            if (block != NULL)
-                g_virtual_block_add_child(G_VIRTUAL_BLOCK(group), block);
+                block = build_instruction_block(instrs, sub_coverage);
+                if (block != NULL)
+                    g_virtual_block_add_child(G_VIRTUAL_BLOCK(group), block);
 
-            delete_code_coverage(sub_coverage);
+                delete_code_coverage(sub_coverage);
+
+            }
 
             /* Conclusion */
 
+            if (true_branch.count > 0) free(true_branch.jumps);
+            if (false_branch.count > 0) free(false_branch.jumps);
+
             if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(group)) > 0)
             {
                 DELAYED_BLOCK_ADDING(result, result_cached, group);
@@ -713,9 +733,6 @@ static GInstrBlock *build_instruction_block(GArchInstruction *instrs, const code
             else
                 g_object_unref(G_OBJECT(group));
 
-            free(true_branch.jumps);
-            free(false_branch.jumps);
-
         }
 
         /* Post-traitements de ILT_CATCH_EXCEPTION */
diff --git a/src/arch/instruction.h b/src/arch/instruction.h
index ae53dbb..59577dc 100644
--- a/src/arch/instruction.h
+++ b/src/arch/instruction.h
@@ -91,6 +91,7 @@ typedef enum _InstructionLinkType
     ILT_CASE_JUMP,                          /* Saut suite à aiguillage     */
     ILT_JUMP_IF_TRUE,                       /* Saut conditionnel (si vrai) */
     ILT_JUMP_IF_FALSE,                      /* Saut conditionnel (si faux) */
+    ILT_LOOP,                               /* Retour en arrière (boucle)  */
     ILT_CALL,                               /* Appel d'une fonction        */
     ILT_CATCH_EXCEPTION                     /* Gestion d'une exception     */
 
diff --git a/src/gtkext/graph/dot.c b/src/gtkext/graph/dot.c
index 64ca2b5..18c4800 100644
--- a/src/gtkext/graph/dot.c
+++ b/src/gtkext/graph/dot.c
@@ -223,6 +223,8 @@ GtkLinkRenderer **create_links_from_graph_layout(const graph_layout *layout, siz
                     color = LKC_GREEN;
                 else if (strcmp("red", eiter->attr[attrib->index]) == 0)
                     color = LKC_RED;
+                else if (strcmp("blue", eiter->attr[attrib->index]) == 0)
+                    color = LKC_BLUE;
                 else if (strcmp("gray", eiter->attr[attrib->index]) == 0)
                     color = LKC_DASHED_GRAY;
             }
diff --git a/src/gtkext/graph/layout.c b/src/gtkext/graph/layout.c
index 87ae2ec..1748c40 100644
--- a/src/gtkext/graph/layout.c
+++ b/src/gtkext/graph/layout.c
@@ -282,6 +282,14 @@ static char *complete_graph_links(const GtkGraphView *view, GtkViewPanel **views
                             desc = stradd(desc, cmd);
                             break;
 
+                        case ILT_LOOP:
+                            snprintf(cmd, LINKS_DESC_LEN,
+                                     "_%p:s -> _%p:n  [ltail=cluster_%p, lhead=cluster_%p, " \
+                                     "color=blue];\n",
+                                     views[i], views[k], views[i], views[k]);
+                            desc = stradd(desc, cmd);
+                            break;
+
                         case ILT_CATCH_EXCEPTION:
                             snprintf(cmd, LINKS_DESC_LEN,
                                      "_%p:s -> _%p:n  [ltail=cluster_%p, lhead=cluster_%p, " \
diff --git a/src/gtkext/gtklinkrenderer.c b/src/gtkext/gtklinkrenderer.c
index 0dbdb25..1d4a86d 100644
--- a/src/gtkext/gtklinkrenderer.c
+++ b/src/gtkext/gtklinkrenderer.c
@@ -215,6 +215,9 @@ void _gtk_link_renderer_draw(const GtkLinkRenderer *renderer, cairo_t *cairo, bo
         case LKC_RED:
             cairo_set_source_rgb(cairo, 0.8, 0, 0);
             break;
+        case LKC_BLUE:
+            cairo_set_source_rgb(cairo, 0, 0, 0.8);
+            break;
         case LKC_DASHED_GRAY:
             cairo_set_source_rgb(cairo, 0.4, 0.4, 0.4);
             break;
@@ -226,6 +229,7 @@ void _gtk_link_renderer_draw(const GtkLinkRenderer *renderer, cairo_t *cairo, bo
         case LKC_DEFAULT:
         case LKC_GREEN:
         case LKC_RED:
+        case LKC_BLUE:
             cairo_set_dash(cairo, (double []) { 6.0 }, 0, 0.0);
             break;
         case LKC_DASHED_GRAY:
diff --git a/src/gtkext/gtklinkrenderer.h b/src/gtkext/gtklinkrenderer.h
index ed2699e..7b78e5e 100644
--- a/src/gtkext/gtklinkrenderer.h
+++ b/src/gtkext/gtklinkrenderer.h
@@ -2,7 +2,7 @@
 /* OpenIDA - Outil d'analyse de fichiers binaires
  * gtklinkrenderer.h - prototypes pour les liens graphiques entre différents morceaux de code
  *
- * Copyright (C) 2009 Cyrille Bagard
+ * Copyright (C) 2009-2013 Cyrille Bagard
  *
  *  This file is part of OpenIDA.
  *
@@ -52,6 +52,7 @@ typedef enum _LinkColor
     LKC_DEFAULT,                            /* Noir, par défaut            */
     LKC_GREEN,                              /* Condition vérifiée          */
     LKC_RED,                                /* Condition non vérifiée      */
+    LKC_BLUE,                               /* Boucle détectée             */
     LKC_DASHED_GRAY,                        /* Exception omniprésente      */
 
     LKC_COUNT