diff options
Diffstat (limited to 'src/analysis/scan/matches/pending.c')
-rw-r--r-- | src/analysis/scan/matches/pending.c | 677 |
1 files changed, 677 insertions, 0 deletions
diff --git a/src/analysis/scan/matches/pending.c b/src/analysis/scan/matches/pending.c new file mode 100644 index 0000000..c653257 --- /dev/null +++ b/src/analysis/scan/matches/pending.c @@ -0,0 +1,677 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * pending.c - consolidation de correspondances partielles + * + * Copyright (C) 2023 Cyrille Bagard + * + * This file is part of Chrysalide. + * + * Chrysalide 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. + * + * Chrysalide 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 "pending.h" + + +#include <malloc.h> +#include <stdlib.h> +#include <string.h> + + +#include "../../../common/sort.h" + + + + + +/* ------------------------- MEMORISATION D'UNE ZONE BORNEE ------------------------- */ + + +/* Compare deux couvertures bornées de correspondances. */ +static int compare_match_area(const match_area_t *, const match_area_t *); + + + +/* -------------------- CONSERVATION DE CORRESPONDANCES ETABLIES -------------------- */ + + +#define PENDING_ALLOC_SIZE 10 + + + + + +/* ---------------------------------------------------------------------------------- */ +/* MEMORISATION D'UNE ZONE BORNEE */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : allocator = allocateur dédié à l'ensemble de zones. * +* start = point de départ d'une nouvelle correspondance. * +* length = taille de la zone couverte. * +* * +* Description : Crée une nouvelle structure de suivi de correspondance. * +* * +* Retour : Structure initialisée mise en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static match_area_t *create_match_area(GUMemCache *allocator, phys_t start, phys_t length) +{ + match_area_t *result; /* Zone à retourner */ + + result = g_umem_cache_alloc(allocator); + + DL_LIST_ITEM_INIT(&result->link); + + result->start = start; + result->end = start + length; + + assert(matches->content_start <= result->start); + assert(result->end <= matches->content_end); + + result->ttl = 1; + + result->has_mod_path = false; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : allocator = allocateur dédié à l'ensemble de zones. * +* start = point de départ d'une nouvelle correspondance. * +* length = taille de la zone couverte. * +* index = indice de construction pour le motif concerné. * +* * +* Description : Crée une nouvelle structure de suivi de correspondance. * +* * +* Retour : Structure initialisée mise en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static match_area_t *create_match_area_with_path(GUMemCache *allocator, phys_t start, phys_t length, size_t index) +{ + match_area_t *result; /* Zone à retourner */ + + result = g_umem_cache_alloc(allocator); + + DL_LIST_ITEM_INIT(&result->link); + + result->start = start; + result->end = start + length; + + assert(matches->content_start <= result->start); + assert(result->end <= matches->content_end); + + result->ttl = 1; + + result->mod_path_index = index; + result->has_mod_path = true; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : area = zone de suivi à supprimer. * +* allocator = allocateur dédié à l'ensemble de zones. * +* * +* Description : Supprime une structure de suivi de correspondance. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void delete_match_area(match_area_t *area, GUMemCache *allocator) +{ + // TODO : assert(alone) + + g_umem_cache_free(allocator, area); + +} + + +/****************************************************************************** +* * +* Paramètres : a = pointeur vers la première zone à analyser. * +* b = pointeur vers la seconde zone à analyser. * +* * +* Description : Compare deux couvertures bornées de correspondances. * +* * +* Retour : Bilan de la comparaison. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static int compare_match_area(const match_area_t *a, const match_area_t *b) +{ + int result; /* Bilan à renvoyer */ + + result = sort_unsigned_long_long(a->start, b->start); + + if (result == 0) + result = sort_unsigned_long_long(a->end, b->end); + + if (result == 0) + result = sort_unsigned_long_long(a->ttl, b->ttl); + + if (result == 0) + result = sort_unsigned_long_long(a->has_mod_path, b->has_mod_path); + + if (result == 0) + result = sort_unsigned_long_long(a->mod_path_index, b->mod_path_index); + + return result; + +} + + + +/* ---------------------------------------------------------------------------------- */ +/* CONSERVATION DE CORRESPONDANCES ETABLIES */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : matches = suivi de correspondances à initialiser. * +* start = première position du contenu (souvent 0). * +* end = position de fin du contenu. * +* * +* Description : Initialise une structure de consolidation de correspondances.* +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void init_pending_matches(pending_matches_t *matches, const phys_t *start, const phys_t *end) +{ + matches->content_start = *start; + matches->content_end = *end; + + matches->allocator = NULL; + matches->areas = NULL; + matches->allocated = 0; + matches->used = 0; + + matches->initialized = false; + + matches->abort = false; + +} + + +/****************************************************************************** +* * +* Paramètres : dest = suivi de correspondances à initialiser. [OUT] * +* src = suivi de correspondances à copier. * +* * +* Description : Copie une structure de consolidation de correspondances. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void copy_pending_matches(pending_matches_t *dest, const pending_matches_t *src) +{ + dest->content_start = src->content_start; + dest->content_end = src->content_end; + + dest->areas = malloc(src->used * sizeof(match_area_t)); + dest->allocated = src->used; + dest->used = src->used; + + memcpy(dest->areas, src->areas, src->used * sizeof(match_area_t)); + + dest->initialized = src->initialized; + + dest->abort = src->abort; + +} + + +/****************************************************************************** +* * +* Paramètres : dest = suivi de correspondances à initialiser. [OUT] * +* src = suivi de correspondances à copier. * +* * +* Description : Fusionne une structure de consolidation avec une autre. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void merge_pending_matches(pending_matches_t *dest, const pending_matches_t *src) +{ + if ((dest->used + src->used) > dest->allocated) + { + dest->allocated += src->used; + + dest->areas = realloc(dest->areas, dest->allocated * sizeof(match_area_t)); + + } + + memcpy(&dest->areas[dest->used], src->areas, src->used * sizeof(match_area_t)); + + dest->used += src->used; + + dest->initialized |= src->initialized; + + dest->abort |= src->abort; + +} + + +/****************************************************************************** +* * +* Paramètres : matches = suivi de correspondances à purger. * +* * +* Description : Libère la mémoire utilisée par une consolidation. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void exit_pending_matches(pending_matches_t *matches) +{ + if (matches->areas != NULL) + free(matches->areas); + +} + + +/****************************************************************************** +* * +* Paramètres : matches = suivi de correspondances à consulter. * +* * +* Description : Dénombre les correspondances établies jusque là. * +* * +* Retour : Quantité de correspondances complètes jusqu'à présent. * +* * +* Remarques : - * +* * +******************************************************************************/ + +size_t count_pending_matches(const pending_matches_t *matches) +{ + size_t result; /* Quantité à renvoyer */ + + result = matches->used; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : matches = suivi de correspondances à consulter. * +* count = nombre de correspondances en attente. [OUT] * +* * +* Description : Fournit la liste des correspondances établies à présent. * +* * +* Retour : Liste de correspondances en lecture seule. * +* * +* Remarques : - * +* * +******************************************************************************/ + +match_area_t * const *get_all_pending_matches(const pending_matches_t *matches, size_t *count) +{ + match_area_t * const *result; /* Série à renvoyer */ + + result = &matches->areas; + + *count = matches->used; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : matches = suivi de correspondances à compléter. * +* start = point de départ d'une nouvelle correspondance. * +* length = taille de la zone couverte. * +* * +* Description : Ajoute au suivi la définition d'une nouvelle correspondance. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void add_pending_match(pending_matches_t *matches, phys_t start, phys_t length) +{ + match_area_t *area; /* Nouvelle zone à intégrer */ + + area = create_match_area(matches->allocator, start, length); + + dl_list_add_tail(area, &matches->areas, match_area_t, link); + matches->used++; + +} + + +/****************************************************************************** +* * +* Paramètres : matches = suivi de correspondances à compléter. * +* start = point de départ d'une nouvelle correspondance. * +* length = taille de la zone couverte. * +* index = indice de construction pour le motif concerné. * +* * +* Description : Ajoute au suivi la définition d'une nouvelle correspondance. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void add_pending_match_with_path(pending_matches_t *matches, phys_t start, phys_t length, size_t index) +{ + match_area_t *area; /* Nouvelle zone à intégrer */ + + area = create_match_area_with_path(matches->allocator, start, length, index); + + dl_list_add_tail(area, &matches->areas, match_area_t, link); + matches->used++; + +} + + +/****************************************************************************** +* * +* Paramètres : matches = suivi de correspondances à compléter. * +* target = indice de la zone de correspondance concernée. * +* start = nouvelle position initiale de la zone couverte. * +* * +* Description : Etend une zone couverte dans le suivi des correspondances. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void extend_pending_match_beginning(pending_matches_t *matches, size_t target, phys_t start) +{ + match_area_t *area; /* Zone à actualiser */ + + assert(target < matches->used); + + area = &matches->areas[target]; + + if (area->ttl == 0) + { + assert(matches->content_start <= start); + + area->start = start; + + area->ttl = 1; + + } + else + { + assert(area->ttl == 1); + + add_pending_match(matches, start, area->end - start); + + } + +} + + +/****************************************************************************** +* * +* Paramètres : matches = suivi de correspondances à compléter. * +* target = indice de la zone de correspondance concernée. * +* length = taille de la zone couverte supplémentaire. * +* * +* Description : Etend une zone couverte dans le suivi des correspondances. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void extend_pending_match_ending(pending_matches_t *matches, size_t target, phys_t end) +{ + match_area_t *area; /* Zone à actualiser */ + + assert(target < matches->used); + + area = &matches->areas[target]; + + if (area->ttl == 0) + { + assert(end <= matches->content_end); + + area->end = end; + + area->ttl = 1; + + } + else + { + assert(area->ttl == 1); + + add_pending_match(matches, area->start, end - area->start); + + } + +} + + +/****************************************************************************** +* * +* Paramètres : matches = suivi de correspondances à modifier. * +* * +* Description : Réinitialisation à 0 tous les TTL de correspondances. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void reset_pending_matches_ttl(pending_matches_t *matches) +{ + size_t i; /* Boucle de parcours */ + + assert(matches->initialized); + + for (i = 0; i < matches->used; i++) + matches->areas[i].ttl = 0; + +} + + +/****************************************************************************** +* * +* Paramètres : matches = suivi de correspondances à modifier. * +* * +* Description : Retire toutes les correspondances sans issue pour l'analyse. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void purge_pending_matches(pending_matches_t *matches) +{ + match_area_t *del_start; /* Départ d'une zone morte */ + match_area_t *del_end; /* Fin d'une zone morte */ + size_t del_remaining; /* Nombre de valides ensuite */ + size_t del_count; /* Nombre d'éléments à effacer */ + size_t i; /* Boucle de parcours */ + + assert(matches->initialized); + + /** + * Note : le code original était le suivant : + * + + * for (i = matches->used; i > 0; i--) + * if (matches->areas[i - 1].ttl == 0) + * { + * memmove(&matches->areas[i - 1], &matches->areas[i], (matches->used - i) * sizeof(match_area_t)); + * matches->used--; + * } + * + * Pour éviter les appels à memmove(), un déplacement par blocs est désormais visée. + */ + + del_start = NULL; + del_end = NULL; + del_count = 0; + del_remaining = 0; + + /* Suppression en bloc si possible */ + + for (i = matches->used; i > 0; i--) + { + if (matches->areas[i - 1].ttl == 0) + { + del_start = &matches->areas[i - 1]; + + if (del_end == NULL) + { + del_end = del_start; + del_remaining = matches->used - i; + } + + del_count++; + + } + else + { + if (del_start != NULL) + { + assert(&matches->areas[i] == del_start); + + if (del_remaining > 0) + memmove(del_start, del_end + 1, del_remaining * sizeof(match_area_t)); + + assert(matches->used > del_count); + matches->used -= del_count; + + del_start = NULL; + del_end = NULL; + del_count = 0; + del_remaining = 0; + + } + + } + + } + + /* Dernier traitement au besoin */ + + if (del_start != NULL) + { + assert(&matches->areas[0] == del_start); + + if (del_remaining > 0) + memmove(del_start, del_end + 1, del_remaining * sizeof(match_area_t)); + + assert(matches->used >= del_count); + matches->used -= del_count; + + } + + /* Bilan */ + + matches->abort = (matches->used == 0); + +} + + +/****************************************************************************** +* * +* Paramètres : matches = suivi de correspondances à finaliser. * +* * +* Description : Trie les correspondances et retire tous les doublons. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void sort_and_filter_pending_matches(pending_matches_t *matches) +{ + match_area_t *last; /* Dernière zone conservée */ + size_t i; /* Boucle de parcours */ + match_area_t *cur; /* Zone courante dans l'analyse*/ + + if (matches->used > 0) + { + qsort(matches->areas, matches->used, sizeof(match_area_t), (__compar_fn_t)compare_match_area); + + last = &matches->areas[0]; + + for (i = 1; i < matches->used; i++) + { + cur = &matches->areas[i]; + + if (last->start != cur->start || last->end != cur->end) + { + if ((cur - last) > 1) + { + memmove(last + 1, cur, (matches->used - i) * sizeof(match_area_t)); + matches->used -= (cur - last + 1); + } + + last = cur; + + } + + } + + cur = &matches->areas[matches->used - 1]; + + if (last != cur) + matches->used = last - matches->areas + 1; + + } + +} |