diff options
Diffstat (limited to 'src/analysis/scan/patterns/tokens/nodes/plain.c')
-rw-r--r-- | src/analysis/scan/patterns/tokens/nodes/plain.c | 1377 |
1 files changed, 1377 insertions, 0 deletions
diff --git a/src/analysis/scan/patterns/tokens/nodes/plain.c b/src/analysis/scan/patterns/tokens/nodes/plain.c new file mode 100644 index 0000000..5dd45df --- /dev/null +++ b/src/analysis/scan/patterns/tokens/nodes/plain.c @@ -0,0 +1,1377 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * plain.c - gestion d'une recherche de motif textuel + * + * 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 "plain.h" + + +#include <assert.h> + + +#include "plain-int.h" +#include "../../../../../common/extstr.h" + + + +/* ------------------------ DECOMPOSITION DE MOTIF RECHERCHE ------------------------ */ + + +/* Initialise la classe des noeuds pour motif textuel. */ +static void g_scan_token_node_plain_class_init(GScanTokenNodePlainClass *); + +/* Initialise une instance de noeud pour motif textuel. */ +static void g_scan_token_node_plain_init(GScanTokenNodePlain *); + +/* Supprime toutes les références externes. */ +static void g_scan_token_node_plain_dispose(GScanTokenNodePlain *); + +/* Procède à la libération totale de la mémoire. */ +static void g_scan_token_node_plain_finalize(GScanTokenNodePlain *); + + + +/* --------------------- IMPLEMENTATION DES FONCTIONS DE CLASSE --------------------- */ + + +/* Communique l'intérêt d'un noeud au sein d'une analyse. */ +static float g_scan_token_node_plain_compute_weight_for_scan(const GScanTokenNodePlain *); + +/* Parcourt une arborescence de noeuds et y relève des éléments. */ +static void g_scan_token_node_plain_visit(GScanTokenNodePlain *, scan_tree_points_t *); + +/* Inscrit la définition d'un motif dans un moteur de recherche. */ +static bool g_scan_token_node_plain_enroll(GScanTokenNodePlain *, GEngineBackend *, size_t, size_t *); + +/* Récupère un identifiant final pour un atome d'octets. */ +static bool g_scan_token_node_plain_build_id(GScanTokenNodePlain *, GEngineBackend *); + +/* Détermine si un contenu d'intérêt est présent à une position. */ +static bool check_scan_token_node_plain_content(const sized_binary_t *, const tracked_scan_atom_t *, bool, phys_t, GBinContent *); + +/* Transforme les correspondances locales en trouvailles. */ +static void g_scan_token_node_plain_check_forward(const GScanTokenNodePlain *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); + +/* Transforme les correspondances locales en trouvailles. */ +static void g_scan_token_node_plain_check_backward(const GScanTokenNodePlain *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); + + + +/* ---------------------------------------------------------------------------------- */ +/* DECOMPOSITION DE MOTIF RECHERCHE */ +/* ---------------------------------------------------------------------------------- */ + + +/* Indique le type défini pour un noeud représentant une bribe de texte à retrouver. */ +G_DEFINE_TYPE(GScanTokenNodePlain, g_scan_token_node_plain, G_TYPE_SCAN_TOKEN_NODE); + + +/****************************************************************************** +* * +* Paramètres : klass = classe à initialiser. * +* * +* Description : Initialise la classe des noeuds pour motif textuel. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_scan_token_node_plain_class_init(GScanTokenNodePlainClass *klass) +{ + GObjectClass *object; /* Autre version de la classe */ + GScanTokenNodeClass *node; /* Version de classe parente */ + + object = G_OBJECT_CLASS(klass); + + object->dispose = (GObjectFinalizeFunc/* ! */)g_scan_token_node_plain_dispose; + object->finalize = (GObjectFinalizeFunc)g_scan_token_node_plain_finalize; + + node = G_SCAN_TOKEN_NODE_CLASS(klass); + + node->compute_weight = (compute_scan_token_node_weight_fc)g_scan_token_node_plain_compute_weight_for_scan; + node->apply = (apply_scan_token_node_flags_fc)NULL; + node->visit = (visit_scan_token_node_fc)g_scan_token_node_plain_visit; + node->enroll = (enroll_scan_token_node_fc)g_scan_token_node_plain_enroll; + node->build_id = (build_scan_token_node_id_fc)g_scan_token_node_plain_build_id; + node->check_forward = (check_scan_token_node_fc)g_scan_token_node_plain_check_forward; + node->check_backward = (check_scan_token_node_fc)g_scan_token_node_plain_check_backward; + +} + + +/****************************************************************************** +* * +* Paramètres : plain = instance à initialiser. * +* * +* Description : Initialise une instance de noeud pour motif textuel. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_scan_token_node_plain_init(GScanTokenNodePlain *plain) +{ + init_szstr(&plain->orig); + plain->modifier = NULL; + plain->flags = SPNF_NONE; + + plain->raw = NULL; + plain->atoms = NULL; + plain->count = 0; + +} + + +/****************************************************************************** +* * +* Paramètres : plain = instance d'objet GLib à traiter. * +* * +* Description : Supprime toutes les références externes. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_scan_token_node_plain_dispose(GScanTokenNodePlain *plain) +{ + g_clear_object(&plain->modifier); + + G_OBJECT_CLASS(g_scan_token_node_plain_parent_class)->dispose(G_OBJECT(plain)); + +} + + +/****************************************************************************** +* * +* Paramètres : plain = instance d'objet GLib à traiter. * +* * +* Description : Procède à la libération totale de la mémoire. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_scan_token_node_plain_finalize(GScanTokenNodePlain *plain) +{ + size_t i; /* Boucle de parcours */ + + exit_szstr(&plain->orig); + + for (i = 0; i < plain->count; i++) + exit_szstr(&plain->raw[i]); + + if (plain->raw != NULL) + free(plain->raw); + + if (plain->atoms != NULL) + free(plain->atoms); + + G_OBJECT_CLASS(g_scan_token_node_plain_parent_class)->finalize(G_OBJECT(plain)); + +} + + +/****************************************************************************** +* * +* Paramètres : text = texte brut à rechercher. * +* modifier = transformateur éventuel à solliciter. * +* flags = particularités à prendre en considération. * +* * +* Description : Construit un noeud représentant un motif textuel. * +* * +* Retour : Mécanismes mis en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +GScanTokenNode *g_scan_token_node_plain_new(const sized_binary_t *text, GScanTokenModifier *modifier, ScanPlainNodeFlags flags) +{ + GScanTokenNode *result; /* Structure à retourner */ + + result = g_object_new(G_TYPE_SCAN_TOKEN_NODE_PLAIN, NULL); + + if (!g_scan_token_node_plain_create(G_SCAN_TOKEN_NODE_PLAIN(result), text, modifier, flags)) + g_clear_object(&result); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : plain = encadrement de motif à initialiser pleinement. * +* text = texte brut à rechercher. * +* modifier = transformateur éventuel à solliciter. * +* flags = particularités à prendre en considération. * +* * +* Description : Met en place un noeud représentant un motif textuel. * +* * +* Retour : Bilan de l'opération. * +* * +* Remarques : - * +* * +******************************************************************************/ + +bool g_scan_token_node_plain_create(GScanTokenNodePlain *plain, const sized_binary_t *text, GScanTokenModifier *modifier, ScanPlainNodeFlags flags) +{ + bool result; /* Bilan à retourner */ + + result = true; + + szstrdup(&plain->orig, text); + + if (modifier != NULL) + { + plain->modifier = modifier; + g_object_ref(G_OBJECT(modifier)); + } + + plain->flags = flags; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : plain = noeud de motif textuel à consulter. * +* * +* Description : Indique les propriétés particulières d'un noeud de texte. * +* * +* Retour : Propriétés particulières associées au noeud. * +* * +* Remarques : - * +* * +******************************************************************************/ + +ScanPlainNodeFlags g_scan_token_node_plain_get_flags(const GScanTokenNodePlain *plain) +{ + ScanPlainNodeFlags result; /* Statut à retourner */ + + result = plain->flags; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : node = définition de la bribe à consulter. * +* index = indice de la combinaison de modificateurs ciblée. * +* * +* Description : Retrouve l'origine d'une correspondance à partir d'un indice.* +* * +* Retour : Version humainement lisible de la combinaison. * +* * +* Remarques : - * +* * +******************************************************************************/ + +char *g_scan_token_node_plain_get_modifier_path(const GScanTokenNodePlain *node, size_t index) +{ + char *result; /* Combinaison à retourner */ + + if (node->modifier == NULL) + result = strdup("plain"); + + else + result = g_scan_token_modifier_get_path(node->modifier, (size_t []){ index }); + + return result; + + +} + + + +/* ---------------------------------------------------------------------------------- */ +/* IMPLEMENTATION DES FONCTIONS DE CLASSE */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : node = noeud de motif à consulter. * +* * +* Description : Communique l'intérêt d'un noeud au sein d'une analyse. * +* * +* Retour : Poids de l'importance pour un départ de scan. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static float g_scan_token_node_plain_compute_weight_for_scan(const GScanTokenNodePlain *node) +{ + float result; /* Valeur à retourner */ + + result = node->orig.len; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : node = point de départ du parcours à effectuer. * +* points = points capitaux de l'arborescence. [OUT] * +* * +* Description : Parcourt une arborescence de noeuds et y relève des éléments.* +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_scan_token_node_plain_visit(GScanTokenNodePlain *node, scan_tree_points_t *points) +{ + GScanTokenNode *candidate; /* Autre version du noeud */ + float node_weight; /* Poids du noeud courant */ + float other_weight; /* Poids de l'autre noeud */ + + if (points->first_plain == NULL) + points->first_plain = G_SCAN_TOKEN_NODE(node); + + else + { + candidate = G_SCAN_TOKEN_NODE(node); + + node_weight = g_scan_token_node_compute_weight_for_scan(candidate); + other_weight = g_scan_token_node_compute_weight_for_scan(points->first_plain); + + if (node_weight >= other_weight) + points->first_plain = candidate; + + } + +} + + +/****************************************************************************** +* * +* Paramètres : node = définition de la bribe à enregistrer. * +* context = contexte de l'analyse à mener. * +* backend = moteur de recherche à préchauffer. * +* maxsize = taille max. des atomes (mise en commun optimisée). * +* slow = niveau de ralentissement induit (0 = idéal). [OUT] * +* * +* Description : Inscrit la définition d'un motif dans un moteur de recherche.* +* * +* Retour : Bilan de l'opération à renvoyer. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bool g_scan_token_node_plain_enroll(GScanTokenNodePlain *node, GEngineBackend *backend, size_t maxsize, size_t *slow) +{ + bool result; /* Statut à retourner */ + size_t i; /* Boucle de parcours #1 */ + tracked_scan_atom_t atom; /* Atome identifié */ + size_t letters; /* Nombre de lettres présentes */ + size_t k; /* Boucle de parcours #2 */ + size_t extra_count; /* Quantité pour l'exhaustivité*/ + sized_binary_t *extra; /* Couverture supplémntaire */ + size_t remaining; /* Quantité restant à traiter */ + + /* Génération d'une base de chaînes à couvrir */ + + if (node->modifier == NULL) + { + node->raw = malloc(sizeof(sized_binary_t)); + node->count = 1; + + szstrdup(&node->raw[0], &node->orig); + + result = true; + + } + else + result = g_scan_token_modifier_transform(node->modifier, &node->orig, 1, &node->raw, &node->count); + + if (!result) + goto exit; + + /* Préparation pour la mémorisation des atomes */ + + node->atoms = malloc(node->count * sizeof(tracked_scan_atom_t)); + + /* Validation du besoin effectif dans les cas extrèmes */ + + + + // TODO : if (orig.len < ...) + + + + /* Recherche des atomes */ + + for (i = 0; i < node->count; i++) + { + if (node->flags & SPNF_CASE_INSENSITIVE) + { + find_best_atom(&node->raw[i], maxsize, &atom, &letters); + + if (letters == 0) + node->atoms[i] = atom; + + /* Insertion des nouvelles combinaisons pour couvrir toutes les casses */ + else + { + /* extra_count = 2^letters */ + for (k = 1, extra_count = 2; k < letters; k++, extra_count *= 2) + ; + + extra = make_atoms_case_insensitive(&node->raw[i], &atom, extra_count); + + remaining = node->count - i - 1; + + node->count += (extra_count - 1); + + node->raw = realloc(node->raw, node->count * sizeof(sized_binary_t)); + + memmove(&node->raw[i + extra_count], &node->raw[i + 1], remaining * sizeof(sized_binary_t)); + + for (k = 0; k < extra_count; k++) + node->raw[i + k] = extra[k]; + + free(extra); + + node->atoms = realloc(node->atoms, node->count * sizeof(tracked_scan_atom_t)); + + for (k = 0; k < extra_count; k++) + node->atoms[i + k] = atom; + + i += extra_count - 1; + + } + + } + + else + find_best_atom(&node->raw[i], maxsize, &node->atoms[i], &letters); + + } + + /* Enregistrements en masse */ + + for (i = 0; i < node->count && result; i++) + result = enroll_prepared_atom(&node->raw[i], backend, &node->atoms[i]); + + exit: + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : node = définition de la bribe à peaufiner. * +* backend = moteur de recherche à préchauffer. * +* * +* Description : Récupère un identifiant final pour un atome d'octets. * +* * +* Retour : Bilan de l'opération à renvoyer. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bool g_scan_token_node_plain_build_id(GScanTokenNodePlain *node, GEngineBackend *backend) +{ + bool result; /* Statut à retourner */ + size_t i; /* Boucle de parcours #1 */ + + result = true; + + for (i = 0; i < node->count && result; i++) + result = build_atom_pattern_id(&node->atoms[i], backend); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : raw = contneu brut à retrouver idéalement. * +* atom = contenu brut représentatif ciblé. * +* nocase = marque un éventuel désintérêt pour la casse. * +* start = point d'analyse à respecter. * +* content = accès au contenu brut pour vérifications (optim.) * +* * +* Description : Détermine si un contenu d'intérêt est présent à une position.* +* * +* Retour : Bilan de l'analyse : true pour une correspondance. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bool check_scan_token_node_plain_content(const sized_binary_t *raw, const tracked_scan_atom_t *atom, bool nocase, phys_t start, GBinContent *content) +{ + bool result; /* Bilan à retourner */ + vmpa2t pos; /* Position dans les données */ + const bin_t *ptr; /* Accès aux données brutes */ + int ret; /* Bilan d'une comparaison */ + + result = false; + + init_vmpa(&pos, start, VMPA_NO_VIRTUAL); + + /* Validation du motif intégral */ + + if (atom == NULL) + { + ptr = g_binary_content_get_raw_access(content, &pos, raw->len); + + /** + * Si la partion atomique recherchée est trouvée en début de contenu, + * le reste du motif de recherche va déborder. L'accès correspondant + * est donc refusé, et cette situation est prise en compte ici. + */ + if (ptr == NULL) goto done; + + if (nocase) + ret = memcasecmp(raw->data, ptr, raw->len); + else + ret = memcmp(raw->data, ptr, raw->len); + + result = (ret == 0); + + } + + /* Validation des extrémités */ + + else + { + /* Validation du contenu avant l'atome */ + + if (atom->pos > 0) + { + ptr = g_binary_content_get_raw_access(content, &pos, atom->pos); + + /** + * Si la partion atomique recherchée est trouvée en début de contenu, + * le reste du motif de recherche va déborder. L'accès correspondant + * est donc refusé, et cette situation est prise en compte ici. + */ + if (ptr == NULL) goto done; + + if (nocase) + ret = memcasecmp(raw->data, ptr, atom->pos); + else + ret = memcmp(raw->data, ptr, atom->pos); + + if (ret != 0) goto done; + + } + + /* Validation du contenu après l'atome */ + + if (atom->rem > 0) + { + advance_vmpa(&pos, atom->len); + + ptr = g_binary_content_get_raw_access(content, &pos, atom->rem); + + /** + * Si la partion atomique recherchée est trouvée en fin de contenu, + * le reste du motif de recherche va déborder. L'accès correspondant + * est donc refusé, et cette situation est prise en compte ici. + */ + if (ptr == NULL) goto done; + + if (nocase) + ret = memcasecmp(raw->data + atom->pos + atom->len, ptr, atom->rem); + else + ret = memcmp(raw->data + atom->pos + atom->len, ptr, atom->rem); + + if (ret != 0) goto done; + + } + + result = true; + + } + + done: + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : node = définition de la bribe à manipuler. * +* params = accès direct aux éléments utiles aux validations. * +* cflags = altérations de traitement à respecter. * +* skip = détermine si l'analyse est différée. [OUT] * +* * +* Description : Transforme les correspondances locales en trouvailles. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_scan_token_node_plain_check_forward(const GScanTokenNodePlain *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) +{ + bool track_path; /* Conservation du chemin */ + bool nocase; /* Pas d'intérêt pour la casse */ + match_area_t **areas; /* Liste de zones à constituer */ + size_t *count; /* Taille de cette liste */ + bool copy; /* Besoin d'une copie ? */ + bool inverted; /* Inversion des bilans ? */ + size_t i; /* Boucle de parcours #1 */ + const tracked_scan_atom_t *atom; /* Atome correspondant */ + match_area_t *atoms; /* Localisations des bribes */ + bool first_round; /* Premier tour de traitement */ + match_area_t *area; /* Correspondance à valider */ + const sized_binary_t *raw; /* Données brutes d'origine */ + match_area_t *next; /* Correspondance suivante */ + phys_t start; /* Début potentiel de motif */ + bool status; /* Bilan d'une correspondance */ + phys_t after; /* Espace disposible après */ + phys_t min_end; /* Fin la plus proche possible */ + phys_t max_end; /* Fin la plus éloignée trouvée*/ + bool updated; /* Existence de correspondance */ + size_t rcount; /* Quantité de bornes présentes*/ + const node_offset_range_t *ranges; /* Bornes d'espace à parcourir */ + size_t r; /* Boucle de parcours #xxxxxxxxxxxx*/ + phys_t p; /* Boucle de parcours #xxxxxxxxxxxx*/ + phys_t updated_edge; /* Nouvelle bordure de motif */ + match_area_t *new_area; /* Copie de correspondance */ + + if (0x0) printf("=================== CHECK :: %s (skip? %d)\n", __FUNCTION__, *skip); + + if (*skip) + return; + + track_path = (G_SCAN_TOKEN_NODE(node)->flags & STNF_MAIN); + + nocase = (node->flags & SPNF_CASE_INSENSITIVE); + + /** + * Création de premières marques de correspondances. + */ + if (!params->initialized) + { + /* Destinations établies une fois pour toutes */ + + if (cflags & TNCF_KEEP_DISCARDED) + { + areas = ¶ms->kept_areas; + count = ¶ms->kept_count; + + copy = false; + inverted = true; + + } + + else if (cflags & TNCF_CREATE_NEW) + { + areas = ¶ms->created_areas; + count = ¶ms->created_count; + + copy = true; + inverted = false; + + } + + else + { + assert(cflags & TNCF_UPDATE_IN_PLACE); + + areas = ¶ms->main_areas; + count = ¶ms->main_count; + + copy = false; + inverted = false; + + } + + /* Parcours des combinaisons enregistrées */ + + for (i = 0; i < node->count; i++) + { + atom = &node->atoms[i]; + + atoms = g_scan_context_get_atom_matches(params->context, atom->pid); + + first_round = (*count == 0); + + if (atom->fast_check) + { + /** + * Toutes les correspondances sont validées d'office car le motif identifié + * correspondant au motif complet. + */ + + if (!inverted) + { + for_each_match_area(area, atoms) + { + /** + * La modification de la zone d'origine est possible dans tous les cas + * car cette zone a été allouée de façon dédiée à un type de correspondances + * et ne sera pas réutilisée comme autre source de correspondance ailleurs. + */ + + assert(area->end >= atom->len); + + area->start = area->end - atom->len; + + (*count)++; + + } + + } + + else + atoms = NULL; + + } + + else + { + raw = &node->raw[i]; + + for_each_match_area_safe(area, &atoms, next) + { + start = area->end - atom->len - atom->pos; + + status = check_scan_token_node_plain_content(raw, atom, nocase, start, params->content); + + if (status) + { + /** + * La modification de la zone d'origine est possible dans tous les cas + * car cette zone a été allouée de façon dédiée à un type de correspondances + * et ne sera pas réutilisée comme autre source de correspondance ailleurs. + */ + + if (!inverted) + { + area->start = start; + area->end += atom->rem; + + (*count)++; + + } + else + del_match_area(area, &atoms); + + } + + else + { + /** + * Les principes de modifications restent valables, même inversés. + */ + if (inverted) + { + area->start = start; + area->end += atom->rem; + + (*count)++; + + } + else + del_match_area(area, &atoms); + + } + + } + + + } + + /* Mise à jour de la liste */ + + if (atoms != NULL) + { + if (first_round) + *areas = atoms; + + else + merge_match_areas(areas, &atoms); + + } + + } + + } + + /** + * Poursuite des traitements sur des correspondances déjà amorcées, impliquant + * des comparaisons entières de motifs. + */ + else + { + if (0x0) printf(" LIST : %p (sz = %zu)\n", params->main_areas, params->main_count); + + for_each_match_area_safe(area, ¶ms->main_areas, next) + { + assert(area->end <= params->content_end); + + after = params->content_end - area->end; + + if (0x0) printf("---------- iter @ %u -> %u\n", (unsigned int)area->start, (unsigned int)area->end); + + /** + * Il ne peut y avoir qu'une seule séquence d'octets à un même + * emplacement. En revanche, des modificateurs peuvent construire + * possédant une même base, mais offrant des suffixes différents + * (par exemple, un marqueur nul UTF-16 final en complément). + * + * L'ensemble des combinaisons produites doit ainsi être exploré. + */ + + /** + * Par ailleurs, même si une base de couples uniques est assurée, + * la constitution d'un ensemble de noeuds peut amener une redondance + * dans les emplacements de correspondances ; ces doublons éventuels + * sont alors filtrés par un appel à sort_match_areas_no_dup(). + * + * Par exemple, pour la séquence d'octets analysés suivante : + * + * aaa....bbb + * + * La définition { (61 61 | 61 61 61) [4-5] 62 62 62 } peut établir + * les correspondances suivantes : + * + * aa.....bbb -> couple pending[x] (0;2) puis (0;10) + * ^ + * aa....bbb -> couple pending[y] (1;3) puis (1;10) + * ^ + * aaa....bbb -> couple pending[z] (0;3) puis (0;10) + * ^ + * + * Par ailleurs, une même base de départ peut conduire à plusieurs + * zones de correspondances. + * + * Par exemple, pour la séquence d'octets analysés suivante : + * + * aa..bb..bb + * + * La définition { 61 61 [2-6] 62 62 } peut établir + * les correspondances suivantes : + * + * aa..bb..bb -> couple pending[x] (0;2) puis (0;6) + * ^ + * aa..bb..bb -> couple pending[x] (0;2) puis (0;10) + * ^ + */ + + /** + * Dans la première situation, c'est la bribe 62 62 62 qui fait l'objet + * d'une recherche de motifs. Les autres bribes sont recherchées + * manuellement ici, car l'espace de séparation est léger (inférieur à + * MAX_RANGE_FOR_MANUAL_CHECK). + * + * La seconde situation bénéficie de recherches automatisées pour + * l'ensemble des motifs, du fait d'une valeur de séparation plus + * importante. + * + * Dans les deux cas, l'espace de séparation est entièrement considéré. + * La sélection de la correspondance à retour s'établit selon un + * paramètre de configuation : doit-on être avare sur les distances + * consommées ou non ? + */ + + min_end = params->content_end; + max_end = params->content_start; + + updated = false; + + for (i = 0; i < node->count; i++) + { + raw = &node->raw[i]; + + /* Souplesse dans les positions ? */ + if (offsets_exist(¶ms->offset)) + { + ranges = get_node_search_offset_ranges_2(¶ms->offset, &rcount); + + for (r = 0; r < rcount; r++) + { + assert(ranges[r].has_max); + assert((ranges[r].max - ranges[r].min) <= MAX_RANGE_FOR_MANUAL_CHECK); + + for (p = ranges[r].min; p <= ranges[r].max; p++) + { + /** + * Si la fin d'une correspondance potentielle est trop près de + * la fin du contenu binaire et ne peut contenir le motif + * représenté, alors la corresponance est écartée sans appel. + */ + if ((p + raw->len) > after) + break; + + status = check_scan_token_node_plain_content(raw, NULL, nocase, + area->end + p, params->content); + + if (status) + { + updated_edge = area->end + p + raw->len; + + if (updated_edge < min_end) + min_end = updated_edge; + + if (updated_edge > max_end) + max_end = updated_edge; + + updated = true; + + } + + } + + } + + } + + /* Position immédiatement attendue */ + else + { + /** + * Si la fin d'une correspondance potentielle est trop près de + * la fin du contenu binaire et ne peut contenir le motif + * représenté, alors la corresponance est écartée sans appel. + */ + if (raw->len > after) + continue; + + status = check_scan_token_node_plain_content(raw, NULL, nocase, area->end, params->content); + + if (status) + { + updated_edge = area->end + raw->len; + + if (updated_edge < min_end) + min_end = updated_edge; + + if (updated_edge > max_end) + max_end = updated_edge; + + updated = true; + + } + + } + + } + + if (updated) + { + /** + * Si seuls les rejets sont d'intérêt, les correspondances établies + * ne se voient pas mises à jours ni retirées. + */ + + if ((cflags & TNCF_KEEP_DISCARDED) == 0) + { + if (cflags & TNCF_UPDATE_IN_PLACE) + area->end = (1 /* greedy */ ? min_end : max_end); + + else if (cflags & TNCF_CREATE_NEW) + { + new_area = g_umem_slice_alloc(params->allocator); + + *new_area = *area; + + new_area->end = (1 /* greedy */ ? min_end : max_end); + + add_tail_match_area(new_area, ¶ms->created_areas); + params->created_count++; + + } + +#ifndef NDEBUG + else + assert(false); +#endif + + } + + } + + else + { + /** + * Si la liste principale doit être mise à jour... + */ + + if (cflags & TNCF_UPDATE_IN_PLACE) + { + del_match_area(area, ¶ms->main_areas); + assert(params->main_count > 0); + params->main_count--; + } + + /** + * Au cas où le rejet est d'intérêt, l'absence de correspondance + * est conservée dans une liste dédiée. + */ + + if (cflags & TNCF_KEEP_DISCARDED) + { + if (cflags & TNCF_UPDATE_IN_PLACE) + { + add_tail_match_area(area, ¶ms->kept_areas); + params->kept_count++; + } + + else if (cflags & TNCF_CREATE_NEW) + { + new_area = g_umem_slice_alloc(params->allocator); + + *new_area = *area; + + new_area->end = (1 /* greedy */ ? min_end : max_end); + + add_tail_match_area(new_area, ¶ms->kept_areas); + params->kept_count++; + + } + +#ifndef NDEBUG + else + assert(false); +#endif + + } + + } + + } + + } + + params->initialized = true; + + disable_all_ranges_in_node_search_offset(¶ms->offset); + +} + + +/****************************************************************************** +* * +* Paramètres : node = définition de la bribe à manipuler. * +* params = accès direct aux éléments utiles aux validations. * +* cflags = altérations de traitement à respecter. * +* skip = détermine si l'analyse est différée. [OUT] * +* * +* Description : Transforme les correspondances locales en trouvailles. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_scan_token_node_plain_check_backward(const GScanTokenNodePlain *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) +{ + + + + + + bool track_path; /* Conservation du chemin */ + bool nocase; /* Pas d'intérêt pour la casse */ + + + + + size_t i; /* Boucle de parcours #1 */ + + + const sized_binary_t *raw; /* Données brutes d'origine */ + + + bool status; /* Bilan d'une correspondance */ + + + + + + match_area_t *area; /* Correspondance à valider */ + match_area_t *next; /* Correspondance suivante */ + phys_t before; /* Espace disposible avant */ + phys_t min_start; /* Début le plus proche trouvé */ + phys_t max_start; /* Début le plus distant trouvé*/ + bool updated; /* Existence de correspondance */ + size_t rcount; /* Quantité de bornes présentes*/ + const node_offset_range_t *ranges; /* Bornes d'espace à parcourir */ + size_t r; /* Boucle de parcours #xxxxxxxxxxxx*/ + phys_t p; /* Boucle de parcours #xxxxxxxxxxxx*/ + phys_t updated_edge; /* Nouvelle bordure de motif */ + match_area_t *new_area; /* Copie de correspondance */ + + if (0x0) printf("=================== CHECK :: %s (skip? %d)\n", __FUNCTION__, *skip); + + if (*skip) + return; + + /** + * En lecture à rebourd, au moins un noeud a été solicité pour analyse (lors + * du sens de lecture normal). Donc l'initialisation a déjà dû avoir lieu. + */ + + assert(params->initialized); + + track_path = (G_SCAN_TOKEN_NODE(node)->flags & STNF_MAIN); + + nocase = (node->flags & SPNF_CASE_INSENSITIVE); + + + + /** + * ............. + */ + if (0) + { + + + ; + + + + } + + /** + * Poursuite des traitements sur des correspondances déjà amorcées, impliquant + * des comparaisons entières de motifs. + */ + else + { + if (0x0) printf(" LIST : %p (sz = %zu)\n", params->main_areas, params->main_count); + + for_each_match_area_safe(area, ¶ms->main_areas, next) + { + assert(params->content_start <= area->start); + + before = area->start - params->content_start; + + if (0x0) printf("---------- iter @ %u -> %u\n", (unsigned int)area->start, (unsigned int)area->end); + + /** + * Il ne peut y avoir qu'une seule séquence d'octets à un même + * emplacement. En revanche, des modificateurs peuvent construire + * possédant une même base, mais offrant des suffixes différents + * (par exemple, un marqueur nul UTF-16 final en complément). + * + * L'ensemble des combinaisons produites doit ainsi être exploré. + */ + + min_start = params->content_start; + max_start = params->content_end; + + updated = false; + + for (i = 0; i < node->count; i++) + { + raw = &node->raw[i]; + + /* Souplesse dans les positions ? */ + if (offsets_exist(¶ms->offset)) + { + ranges = get_node_search_offset_ranges_2(¶ms->offset, &rcount); + + for (r = 0; r < rcount; r++) + { + assert(ranges[r].has_max); + assert((ranges[r].max - ranges[r].min) <= MAX_RANGE_FOR_MANUAL_CHECK); + + for (p = ranges[r].min; p <= ranges[r].max; p++) + { + /** + * Si la fin d'une correspondance potentielle est trop près de + * la fin du contenu binaire et ne peut contenir le motif + * représenté, alors la corresponance est écartée sans appel. + */ + if ((p + raw->len) > before) + break; + + status = check_scan_token_node_plain_content(raw, NULL, nocase, + area->start - raw->len - p, + params->content); + + if (status) + { + updated_edge = area->start - raw->len - p; + + if (updated_edge > min_start) + min_start = updated_edge; + + if (updated_edge < max_start) + max_start = updated_edge; + + updated = true; + + } + + } + + } + + } + + /* Position immédiatement attendue */ + else + { + /** + * Si la fin d'une correspondance potentielle est trop près du + * début du contenu binaire et ne peut contenir le motif + * représenté, alors la corresponance est écartée sans appel. + */ + if (raw->len > before) + continue; + + status = check_scan_token_node_plain_content(raw, NULL, nocase, + area->start - raw->len, + params->content); + + if (status) + { + updated_edge = area->start - raw->len; + + if (updated_edge > min_start) + min_start = updated_edge; + + if (updated_edge < max_start) + max_start = updated_edge; + + updated = true; + + } + + } + + } + + if (updated) + { + /** + * Si seuls les rejets sont d'intérêt, les correspondances établies + * ne se voient pas mises à jours ni retirées. + */ + + if ((cflags & TNCF_KEEP_DISCARDED) == 0) + { + if (cflags & TNCF_UPDATE_IN_PLACE) + area->start = (1 /* greedy */ ? min_start : max_start); + + else if (cflags & TNCF_CREATE_NEW) + { + new_area = g_umem_slice_alloc(params->allocator); + + *new_area = *area; + + new_area->start = (1 /* greedy */ ? min_start : max_start); + + add_tail_match_area(new_area, ¶ms->created_areas); + params->created_count++; + + } + +#ifndef NDEBUG + else + assert(false); +#endif + + } + + } + + else + { + /** + * Si la liste principale doit être mise à jour... + */ + + if (cflags & TNCF_UPDATE_IN_PLACE) + { + del_match_area(area, ¶ms->main_areas); + assert(params->main_count > 0); + params->main_count--; + } + + /** + * Au cas où le rejet est d'intérêt, l'absence de correspondance + * est conservée dans une liste dédiée. + */ + + if (cflags & TNCF_KEEP_DISCARDED) + { + if (cflags & TNCF_UPDATE_IN_PLACE) + { + add_tail_match_area(area, ¶ms->kept_areas); + params->kept_count++; + } + + else if (cflags & TNCF_CREATE_NEW) + { + new_area = g_umem_slice_alloc(params->allocator); + + *new_area = *area; + + new_area->start = (1 /* greedy */ ? min_start : max_start); + + add_tail_match_area(new_area, ¶ms->kept_areas); + params->kept_count++; + + } + +#ifndef NDEBUG + else + assert(false); +#endif + + } + + } + + } + + } + + disable_all_ranges_in_node_search_offset(¶ms->offset); + +} |