diff options
Diffstat (limited to 'src/analysis/scan/patterns/tokens/nodes')
| -rw-r--r-- | src/analysis/scan/patterns/tokens/nodes/any.c | 461 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/tokens/nodes/choice.c | 342 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/tokens/nodes/masked-int.h | 5 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/tokens/nodes/masked.c | 735 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/tokens/nodes/masked.h | 9 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/tokens/nodes/not.c | 98 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/tokens/nodes/plain.c | 902 | ||||
| -rw-r--r-- | src/analysis/scan/patterns/tokens/nodes/sequence.c | 116 |
8 files changed, 2028 insertions, 640 deletions
diff --git a/src/analysis/scan/patterns/tokens/nodes/any.c b/src/analysis/scan/patterns/tokens/nodes/any.c index 6233cb4..10a01cd 100644 --- a/src/analysis/scan/patterns/tokens/nodes/any.c +++ b/src/analysis/scan/patterns/tokens/nodes/any.c @@ -55,10 +55,10 @@ static void g_scan_token_node_any_finalize(GScanTokenNodeAny *); static bool g_scan_token_node_any_enroll(GScanTokenNodeAny *, GScanContext *, GEngineBackend *, size_t, size_t *); /* Transforme les correspondances locales en trouvailles. */ -static void g_scan_token_node_any_check_forward(const GScanTokenNodeAny *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_any_check_forward(const GScanTokenNodeAny *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); /* Transforme les correspondances locales en trouvailles. */ -static void g_scan_token_node_any_check_backward(const GScanTokenNodeAny *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_any_check_backward(const GScanTokenNodeAny *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); @@ -95,6 +95,7 @@ static void g_scan_token_node_any_class_init(GScanTokenNodeAnyClass *klass) node = G_SCAN_TOKEN_NODE_CLASS(klass); + node->apply = (apply_scan_token_node_flags_fc)NULL; node->visit = (visit_scan_token_node_fc)NULL; node->enroll = (enroll_scan_token_node_fc)g_scan_token_node_any_enroll; node->check_forward = (check_scan_token_node_fc)g_scan_token_node_any_check_forward; @@ -117,8 +118,6 @@ static void g_scan_token_node_any_class_init(GScanTokenNodeAnyClass *klass) static void g_scan_token_node_any_init(GScanTokenNodeAny *any) { - g_scan_token_node_set_flags(G_SCAN_TOKEN_NODE(any), STNF_PROD); - any->min = 0; any->has_max = false; @@ -297,13 +296,10 @@ static bool g_scan_token_node_any_enroll(GScanTokenNodeAny *node, GScanContext * /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offset = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* 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. * * * @@ -313,66 +309,250 @@ static bool g_scan_token_node_any_enroll(GScanTokenNodeAny *node, GScanContext * * * ******************************************************************************/ -static void g_scan_token_node_any_check_forward(const GScanTokenNodeAny *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_any_check_forward(const GScanTokenNodeAny *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { - bool initialized; /* Initialisation du suivi ? */ + ScanTokenNodeFlags flags; /* Particularités du noeud */ bool forced; /* Inclusion dans un scan ? */ phys_t size; /* Quantité d'octets considérés*/ - const phys_t *datasize; /* Taille max. à communiquer */ + phys_t match_size; /* Taille de correspondance */ + phys_t i; /* Boucle de parcours #1 */ + match_area_t *space; /* Nouvelle zone à intégrer */ + match_area_t *area; /* Correspondance à valider */ + match_area_t *next; /* Correspondance suivante */ + 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 #2 */ + phys_t updated_edge; /* Nouvelle bordure de motif */ + match_area_t *new_area; /* Copie de correspondance */ + + if (0x1) printf("=================== CHECK :: %s (skip? %d)\n", __FUNCTION__, *skip); if (*skip) return; + flags = g_scan_token_node_get_flags(G_SCAN_TOKEN_NODE(node)); - // $a = { [1-3] 6f } - // pas d'initialisation, construction de résultats avec une taille nulle + forced = (flags & STNF_MAIN); + assert((!params->initialized && forced) || (params->initialized & !forced)); + + /** + * La situation forcée correspond au cas particulier d'une définition + * complètement abstraite : ??, ?? ??, etc. + */ + if (forced) + { + size = params->content_end - params->content_start; + if (node->has_max && 0 /* greedy ? */) + { + match_size = node->max; - initialized = are_pending_matches_initialized(matches); + if (match_size > size) + match_size = node->min; - forced = (g_scan_token_node_get_flags(G_SCAN_TOKEN_NODE(node)) & STNF_MAIN); + } + else + match_size = node->min; + + /** + * Si le contenu binaire est trop petit pour contenir au moins un enregistrement, + * aucune correspondance n'est enregistrée. Comme le noeud est le principale, ie. + * seul et unique, l'analyse s'arrête ensuite d'elle même. + * + * Si le contenu binaire est suffisamment large, des espaces sont créés et l'analyse + * se termine ensuite. La conservation des espaces n'est donc pas utile, ni réalisée. + */ - size = matches->content_end - matches->content_start; + if (match_size <= size) + { + size -= match_size; - datasize = (not ? &size : NULL); + assert(cflags & TNCF_UPDATE_IN_PLACE); - if (forced) - { - assert(!initialized); + for (i = 0; i < size; i++) + { + space = g_umem_slice_alloc(params->allocator); - if (node->min > size) - /* TODO set abort in matches */; + space->start = params->content_start + i; + space->end = space->start + match_size; - else - add_range_to_node_search_offset(offset, - matches->content_start, - matches->content_end - matches->content_start, - datasize); + add_tail_match_area(space, ¶ms->main_areas); + params->main_count++; + + } + + } } + + /** + * Situation usuelle : des espaces séparent deux noeuds. + */ else { - assert(initialized); + assert(params->initialized); + + /** + * Les espaces existants sont à compléter. La présence de tels espaces + * restant à traiter peut provenir d'un aiguillage imposé par un motif + * tel que : + * + * ( aa ?? ?? | bb cc dd ) [0-5] ee ee + * + * Deux espaces sont à considérer avant de rechercher des octets ee : + * [2-7] et [0-5]. + * + * Note : ces espaces peuvent être disjoints. + * + * Si aucun espace n'est en place, un est créé. + */ + extend_node_search_offset(¶ms->offset, node->min, node->max, node->has_max); - // TODO : compléter les intervales éventuels déjà en place + /** + * Si un décalage enregistré ne peut être consommé par un noeud, les + * résultats sont étendus ici à minima ou maxima. + */ + if (flags & STNF_LAST) + { + assert(offsets_exist(¶ms->offset)); - /* - printf("[i] create hole: %llx <-> %llx\n", - (unsigned long long)node->min, - (unsigned long long)node->max); - */ + if (0x1) 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); - if (node->has_max) - add_range_to_node_search_offset(offset, node->min, node->max, datasize); - else - add_range_to_node_search_offset(offset, node->min, matches->content_end - node->min, datasize); + after = params->content_end - area->end; + + if (0x1) printf("---------- iter @ %u -> %u\n", (unsigned int)area->start, (unsigned int)area->end); - // TODO : si dernier, virer les correspondances qui n'ont plus l'espace de fin requis - // -> au niveau du noeud, en fonction du flag _LAST + min_end = params->content_end; + max_end = params->content_start; + + updated = false; + + ranges = get_node_search_offset_ranges_2(¶ms->offset, &rcount); + + for (r = 0; r < rcount; r++) + { + if (ranges[r].min > after) + continue; + + updated_edge = area->end + ranges[r].min; + + if (updated_edge < min_end) + min_end = updated_edge; + + if (ranges[r].has_max) + { + if (ranges[r].max > after) + updated_edge = params->content_end; + else + updated_edge = area->end + ranges[r].max; + + 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 + + } + + } + + } + + disable_all_ranges_in_node_search_offset(¶ms->offset); + + } } @@ -381,13 +561,10 @@ static void g_scan_token_node_any_check_forward(const GScanTokenNodeAny *node, G /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offset = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* 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. * * * @@ -397,55 +574,191 @@ static void g_scan_token_node_any_check_forward(const GScanTokenNodeAny *node, G * * ******************************************************************************/ -static void g_scan_token_node_any_check_backward(const GScanTokenNodeAny *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_any_check_backward(const GScanTokenNodeAny *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { + ScanTokenNodeFlags flags; /* Particularités du noeud */ #ifndef NDEBUG bool forced; /* Inclusion dans un scan ? */ #endif - phys_t size; /* Quantité d'octets considérés*/ - const phys_t *datasize; /* Taille max. à communiquer */ + 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 */ + phys_t updated_edge; /* Nouvelle bordure de motif */ + match_area_t *new_area; /* Copie de correspondance */ + + if (0x1) 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 lecteur normal). Donc l'initialisation a déjà dû avoir lieu. + * du sens de lecture normal). Donc l'initialisation a déjà dû avoir lieu. */ - assert(are_pending_matches_initialized(matches)); + + assert(params->initialized); + + flags = g_scan_token_node_get_flags(G_SCAN_TOKEN_NODE(node)); /** * Si les recherches associées au noeud ont été forcées, alors les traitements * liés ont déjà été effectués, et l'appel de cette fonction aurait dû être sauté. */ #ifndef NDEBUG - forced = (g_scan_token_node_get_flags(G_SCAN_TOKEN_NODE(node)) & STNF_MAIN); + forced = (flags & STNF_MAIN); assert(!forced); #endif - size = matches->content_end - matches->content_start; + /** + * Les considérations pour l'extension des espaces en place sont identiques + * à celles formulées dans la fonction g_scan_token_node_any_check_forward(). + */ - if (node->min > size) - /* TODO set abort in matches */; + extend_node_search_offset(¶ms->offset, node->min, node->max, node->has_max); - else + /** + * Si un décalage enregistré ne peut être consommé par un noeud, les + * résultats sont étendus ici à minima ou maxima. + */ + + if (flags & STNF_FIRST) { - datasize = (not ? &size : NULL); + assert(offsets_exist(¶ms->offset)); - /** - * Une tolérance basée sur des espaces (et non des positions) est déterminée - * ici. - * - * Charge au prochain noeud de traitement de filtrer les résultats courants - * avec, voire à la fonction _g_scan_token_node_check_backward() de - * réaliser une synthèse finale si le noeud courant est le dernier d'une - * lignée. - */ + if (0x1) printf(" LIST : %p (sz = %zu)\n", params->main_areas, params->main_count); - if (node->has_max) - add_range_to_node_search_offset(offset, node->min, node->max, datasize); - else - add_range_to_node_search_offset(offset, node->min, matches->content_end - node->min, datasize); + for_each_match_area_safe(area, ¶ms->main_areas, next) + { + assert(params->content_start <= area->start); + + before = area->start - params->content_start; + + if (0x1) printf("---------- iter @ %u -> %u\n", (unsigned int)area->start, (unsigned int)area->end); + + min_start = params->content_start; + max_start = params->content_end; + + updated = false; + + ranges = get_node_search_offset_ranges_2(¶ms->offset, &rcount); + + for (r = 0; r < rcount; r++) + { + if (ranges[r].min > before) + continue; + + updated_edge = area->start - ranges[r].min; + + if (updated_edge > min_start) + min_start = updated_edge; + + if (ranges[r].has_max) + { + if (ranges[r].max > before) + updated_edge = params->content_start; + else + updated_edge = area->start - ranges[r].max; + + 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); } diff --git a/src/analysis/scan/patterns/tokens/nodes/choice.c b/src/analysis/scan/patterns/tokens/nodes/choice.c index df6ae45..102c7de 100644 --- a/src/analysis/scan/patterns/tokens/nodes/choice.c +++ b/src/analysis/scan/patterns/tokens/nodes/choice.c @@ -24,6 +24,9 @@ #include "choice.h" +#include <assert.h> + + #include "choice-int.h" @@ -48,6 +51,9 @@ static void g_scan_token_node_choice_finalize(GScanTokenNodeChoice *); /* --------------------- IMPLEMENTATION DES FONCTIONS DE CLASSE --------------------- */ +/* Communique l'intérêt d'un noeud au sein d'une analyse. */ +static float g_scan_token_node_choice_compute_weight_for_scan(const GScanTokenNodeChoice *); + /* Prend acte d'une nouvelle propriété pour le noeud. */ static void g_scan_token_node_choice_apply_flags(GScanTokenNodeChoice *, ScanTokenNodeFlags); @@ -55,13 +61,16 @@ static void g_scan_token_node_choice_apply_flags(GScanTokenNodeChoice *, ScanTok static void g_scan_token_node_choice_visit(GScanTokenNodeChoice *, scan_tree_points_t *); /* Inscrit la définition d'un motif dans un moteur de recherche. */ -static bool g_scan_token_node_choice_enroll(GScanTokenNodeChoice *, GScanContext *, GEngineBackend *, size_t, size_t *); +static bool g_scan_token_node_choice_enroll(GScanTokenNodeChoice *, GEngineBackend *, size_t, size_t *); + +/* Récupère un identifiant final pour un atome d'octets. */ +static bool g_scan_token_node_choice_build_id(GScanTokenNodeChoice *, GEngineBackend *); /* Transforme les correspondances locales en trouvailles. */ -static void g_scan_token_node_choice_check_forward(const GScanTokenNodeChoice *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_choice_check_forward(const GScanTokenNodeChoice *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); /* Transforme les correspondances locales en trouvailles. */ -static void g_scan_token_node_choice_check_backward(const GScanTokenNodeChoice *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_choice_check_backward(const GScanTokenNodeChoice *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); @@ -98,9 +107,11 @@ static void g_scan_token_node_choice_class_init(GScanTokenNodeChoiceClass *klass node = G_SCAN_TOKEN_NODE_CLASS(klass); + node->compute_weight = (compute_scan_token_node_weight_fc)g_scan_token_node_choice_compute_weight_for_scan; node->apply = (apply_scan_token_node_flags_fc)g_scan_token_node_choice_apply_flags; node->visit = (visit_scan_token_node_fc)g_scan_token_node_choice_visit; node->enroll = (enroll_scan_token_node_fc)g_scan_token_node_choice_enroll; + node->build_id = (build_scan_token_node_id_fc)g_scan_token_node_choice_build_id; node->check_forward = (check_scan_token_node_fc)g_scan_token_node_choice_check_forward; node->check_backward = (check_scan_token_node_fc)g_scan_token_node_choice_check_backward; @@ -227,6 +238,51 @@ void g_scan_token_node_choice_add(GScanTokenNodeChoice *choice, GScanTokenNode * /****************************************************************************** * * +* 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_choice_compute_weight_for_scan(const GScanTokenNodeChoice *node) +{ + float result; /* Valeur à retourner */ + size_t weight_count; /* Nombre de comptabilisations */ + size_t i; /* Boucle de parcours */ + float weight; /* Nouveau poids à intégrer */ + + result = 0; + + weight_count = 0; + + for (i = 0; i < node->count; i++) + { + weight = g_scan_token_node_compute_weight_for_scan(node->children[i]); + + if (weight > 0) + { + result += weight; + weight_count++; + } + + } + + if (weight_count != node->count) + result = 0; + else + result /= weight_count; + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : node = noeud de motif à mettre à jour. * * flags = propriétés particulières à associer au noeud. * * * @@ -274,9 +330,6 @@ static void g_scan_token_node_choice_visit(GScanTokenNodeChoice *node, scan_tree for (i = 0; i < node->count; i++) { - tmp_points.first_node = NULL; - tmp_points.last_node = NULL; - tmp_points.first_plain = NULL; tmp_points.best_masked = NULL; @@ -296,7 +349,6 @@ static void g_scan_token_node_choice_visit(GScanTokenNodeChoice *node, scan_tree /****************************************************************************** * * * 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] * @@ -309,7 +361,7 @@ static void g_scan_token_node_choice_visit(GScanTokenNodeChoice *node, scan_tree * * ******************************************************************************/ -static bool g_scan_token_node_choice_enroll(GScanTokenNodeChoice *node, GScanContext *context, GEngineBackend *backend, size_t maxsize, size_t *slow) +static bool g_scan_token_node_choice_enroll(GScanTokenNodeChoice *node, GEngineBackend *backend, size_t maxsize, size_t *slow) { bool result; /* Statut à retourner */ size_t i; /* Boucle de parcours */ @@ -317,7 +369,7 @@ static bool g_scan_token_node_choice_enroll(GScanTokenNodeChoice *node, GScanCon result = true; for (i = 0; i < node->count && result; i++) - result = _g_scan_token_node_enroll(node->children[i], context, backend, maxsize, slow); + result = _g_scan_token_node_enroll(node->children[i], backend, maxsize, slow); return result; @@ -326,13 +378,38 @@ static bool g_scan_token_node_choice_enroll(GScanTokenNodeChoice *node, GScanCon /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offset = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* 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_choice_build_id(GScanTokenNodeChoice *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 = g_scan_token_node_build_id(node->children[i], backend); + + 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. * * * @@ -342,78 +419,117 @@ static bool g_scan_token_node_choice_enroll(GScanTokenNodeChoice *node, GScanCon * * ******************************************************************************/ -static void g_scan_token_node_choice_check_forward(const GScanTokenNodeChoice *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_choice_check_forward(const GScanTokenNodeChoice *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { - pending_matches_t init_matches; /* Correspondances initiales */ - node_search_offset_t init_offset; /* Intervales initiaux */ - size_t new_offset; /* Décompte d'intervales */ + bool initialized; /* Initialisation du suivi ? */ + match_area_t *collected_areas; /* Zones mises en place ici */ + size_t collected_count; /* Quantité de ces zones */ + TokenNodeCheckFlags local_cflags; /* Particularités nouvelles */ size_t i; /* Boucle de parcours */ - pending_matches_t tmp_matches; /* Copie locale de travail #1 */ - node_search_offset_t tmp_offset; /* Copie locale de travail #2 */ + scan_node_check_params_t local_params; /* Rassemblement de paramètres */ + + if (0x1) printf("=================== CHECK :: %s (skip? %d)\n", __FUNCTION__, *skip); if (*skip) return; - /* Copie des contextes de départ */ + /* Lancement des sous-traitements */ - copy_pending_matches(&init_matches, matches); + initialized = false; - exit_pending_matches(matches); - init_pending_matches(matches, &init_matches.content_start, &init_matches.content_end); + collected_areas = NULL; + collected_count = 0; - copy_node_search_offset(&init_offset, offset); + local_cflags = (cflags & ~TNCF_UPDATE_IN_PLACE) | TNCF_CREATE_NEW; - exit_node_search_offset(offset); - init_node_search_offset(offset); + for (i = 0; i < node->count; i++) + { + local_params = *params; - /* Lancement des sous-traitements */ + local_params.created_areas = NULL; + local_params.created_count = 0; - new_offset = 0; + local_params.kept_areas = NULL; + local_params.kept_count = 0; - for (i = 0; i < node->count; i++) - { - copy_pending_matches(&tmp_matches, &init_matches); - copy_node_search_offset(&tmp_offset, &init_offset); + if ((cflags & TNCF_CREATE_NEW) == 0 && (i + 1) == node->count) + local_cflags = cflags; + + _g_scan_token_node_check_forward(node->children[i], &local_params, local_cflags, skip); - _g_scan_token_node_check_forward(node->children[i], context, content, - &tmp_matches, &tmp_offset, not, skip); + initialized |= local_params.initialized; - merge_pending_matches(matches, &tmp_matches); - merge_node_search_offset(offset, &tmp_offset); + if (local_cflags & TNCF_KEEP_DISCARDED) + { + merge_match_areas(&collected_areas, &local_params.kept_areas); + collected_count += local_params.kept_count; + } - if (tmp_offset.used > 0) - new_offset++; + else if (local_cflags & TNCF_CREATE_NEW) + { + merge_match_areas(&collected_areas, &local_params.created_areas); + collected_count += local_params.created_count; + } - exit_pending_matches(&tmp_matches); - exit_node_search_offset(&tmp_offset); + else + { + assert(local_cflags & TNCF_UPDATE_IN_PLACE); + + merge_match_areas(&collected_areas, &local_params.main_areas); + collected_count += local_params.main_count; + + } } - /* Sortie propre */ + /* Enregistrement des résultats finaux */ - exit_pending_matches(&init_matches); - exit_node_search_offset(&init_offset); + if (collected_count > 1) + sort_match_areas_no_dup(&collected_areas, &collected_count, compare_match_area_as_dl_item, NULL); - /* "Alternative" directe en cas de motif(s) non terminé(s) par un intervale */ + if (0x1) printf("[%s] collected: #%zu (bis)\n", __FUNCTION__, collected_count); - if (new_offset != node->count) + params->initialized = initialized; + + if (cflags & TNCF_KEEP_DISCARDED) { - assert(node->count > 1); - add_range_to_node_search_offset(offset, 0, 0, NULL); + params->kept_areas = collected_areas; + params->kept_count = collected_count; } + else if (cflags & TNCF_CREATE_NEW) + { + params->created_areas = collected_areas; + params->created_count = collected_count; + } + + else + { + assert(cflags & TNCF_UPDATE_IN_PLACE); + + params->main_areas = collected_areas; + params->main_count = collected_count; + + } + + + + + + /// TODO : gestion des offets en sortie : ajout (+ ajout d'un test en Python) + + + + } /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offsets = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* 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. * * * @@ -423,64 +539,108 @@ static void g_scan_token_node_choice_check_forward(const GScanTokenNodeChoice *n * * ******************************************************************************/ -static void g_scan_token_node_choice_check_backward(const GScanTokenNodeChoice *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_choice_check_backward(const GScanTokenNodeChoice *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { - pending_matches_t init_matches; /* Correspondances initiales */ - node_search_offset_t init_offset; /* Intervales initiaux */ - size_t new_offset; /* Décompte d'intervales */ + match_area_t *collected_areas; /* Zones mises en place ici */ + size_t collected_count; /* Quantité de ces zones */ + TokenNodeCheckFlags local_cflags; /* Particularités nouvelles */ size_t i; /* Boucle de parcours */ - pending_matches_t tmp_matches; /* Copie locale de travail #1 */ - node_search_offset_t tmp_offset; /* Copie locale de travail #2 */ + scan_node_check_params_t local_params; /* Rassemblement de paramètres */ + + if (0x1) printf("=================== CHECK :: %s (skip? %d)\n", __FUNCTION__, *skip); if (*skip) return; - /* Copie des contextes de départ */ + /** + * 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. + */ - copy_pending_matches(&init_matches, matches); - - exit_pending_matches(matches); - init_pending_matches(matches, &init_matches.content_start, &init_matches.content_end); - - copy_node_search_offset(&init_offset, offset); - - exit_node_search_offset(offset); - init_node_search_offset(offset); + assert(params->initialized); /* Lancement des sous-traitements */ - new_offset = 0; + collected_areas = NULL; + collected_count = 0; + + local_cflags = (cflags & ~TNCF_UPDATE_IN_PLACE) | TNCF_CREATE_NEW; for (i = 0; i < node->count; i++) { - copy_pending_matches(&tmp_matches, &init_matches); - copy_node_search_offset(&tmp_offset, &init_offset); + local_params = *params; + + local_params.created_areas = NULL; + local_params.created_count = 0; + + local_params.kept_areas = NULL; + local_params.kept_count = 0; + + if ((cflags & TNCF_CREATE_NEW) == 0 && (i + 1) == node->count) + local_cflags = cflags; - _g_scan_token_node_check_backward(node->children[i], context, content, - &tmp_matches, &tmp_offset, not, skip); + _g_scan_token_node_check_backward(node->children[i], &local_params, local_cflags, skip); - merge_pending_matches(matches, &tmp_matches); - merge_node_search_offset(offset, &tmp_offset); + if (local_cflags & TNCF_KEEP_DISCARDED) + { + merge_match_areas(&collected_areas, &local_params.kept_areas); + collected_count += local_params.kept_count; + } - if (tmp_offset.used > 0) - new_offset++; + else if (local_cflags & TNCF_CREATE_NEW) + { + merge_match_areas(&collected_areas, &local_params.created_areas); + collected_count += local_params.created_count; + } - exit_pending_matches(&tmp_matches); - exit_node_search_offset(&tmp_offset); + else + { + assert(local_cflags & TNCF_UPDATE_IN_PLACE); + + merge_match_areas(&collected_areas, &local_params.main_areas); + collected_count += local_params.main_count; + + } } - /* Sortie propre */ + /* Enregistrement des résultats finaux */ - exit_pending_matches(&init_matches); - exit_node_search_offset(&init_offset); + if (collected_count > 1) + sort_match_areas_no_dup(&collected_areas, &collected_count, compare_match_area_as_dl_item, NULL); - /* "Alternative" directe en cas de motif(s) non terminé(s) par un intervale */ + if (0x1) printf("[%s] collected: #%zu (bis)\n", __FUNCTION__, collected_count); - if (new_offset != node->count) + if (cflags & TNCF_KEEP_DISCARDED) { - assert(node->count > 1); - add_range_to_node_search_offset(offset, 0, 0, NULL); + params->kept_areas = collected_areas; + params->kept_count = collected_count; } + else if (cflags & TNCF_CREATE_NEW) + { + params->created_areas = collected_areas; + params->created_count = collected_count; + } + + else + { + assert(cflags & TNCF_UPDATE_IN_PLACE); + + params->main_areas = collected_areas; + params->main_count = collected_count; + + } + + + + + + /// TODO : gestion des offets en sortie : ajout (+ ajout d'un test en Python) + + + + + + } diff --git a/src/analysis/scan/patterns/tokens/nodes/masked-int.h b/src/analysis/scan/patterns/tokens/nodes/masked-int.h index 9eb8712..5fcc330 100644 --- a/src/analysis/scan/patterns/tokens/nodes/masked-int.h +++ b/src/analysis/scan/patterns/tokens/nodes/masked-int.h @@ -41,8 +41,9 @@ struct _GScanTokenNodeMasked size_t len; /* Taille de cette série */ sized_binary_t *raw; /* Liste de motifs à couvrir */ - tracked_scan_atom_t *atoms; /* Atomes correspondants */ - size_t count; /* Taille de cette liste */ + size_t raw_count; /* Taille de cette liste */ + + tracked_scan_atom_t *enrolled_atoms; /* Atomes correspondants */ size_t enrolled_count; /* Quantité avec identifiant */ }; diff --git a/src/analysis/scan/patterns/tokens/nodes/masked.c b/src/analysis/scan/patterns/tokens/nodes/masked.c index 8765b1d..2dbdb08 100644 --- a/src/analysis/scan/patterns/tokens/nodes/masked.c +++ b/src/analysis/scan/patterns/tokens/nodes/masked.c @@ -56,16 +56,19 @@ static void g_scan_token_node_masked_finalize(GScanTokenNodeMasked *); static void g_scan_token_node_masked_visit(GScanTokenNodeMasked *, scan_tree_points_t *); /* Inscrit la définition d'un motif dans un moteur de recherche. */ -static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *, GScanContext *, GEngineBackend *, size_t, size_t *); +static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *, GEngineBackend *, size_t, size_t *); + +/* Récupère un identifiant final pour un atome d'octets. */ +static bool g_scan_token_node_masked_build_id(GScanTokenNodeMasked *, GEngineBackend *); /* Détermine si un contenu d'intérêt est présent à une position. */ static bool check_scan_token_node_masked_content(const masked_byte_t *, size_t, phys_t, GBinContent *); /* Transforme les correspondances locales en trouvailles. */ -static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); /* Transforme les correspondances locales en trouvailles. */ -static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); @@ -102,8 +105,10 @@ static void g_scan_token_node_masked_class_init(GScanTokenNodeMaskedClass *klass node = G_SCAN_TOKEN_NODE_CLASS(klass); + node->apply = (apply_scan_token_node_flags_fc)NULL; node->visit = (visit_scan_token_node_fc)g_scan_token_node_masked_visit; node->enroll = (enroll_scan_token_node_fc)g_scan_token_node_masked_enroll; + node->build_id = (build_scan_token_node_id_fc)g_scan_token_node_masked_build_id; node->check_forward = (check_scan_token_node_fc)g_scan_token_node_masked_check_forward; node->check_backward = (check_scan_token_node_fc)g_scan_token_node_masked_check_backward; @@ -124,14 +129,14 @@ static void g_scan_token_node_masked_class_init(GScanTokenNodeMaskedClass *klass static void g_scan_token_node_masked_init(GScanTokenNodeMasked *masked) { - g_scan_token_node_set_flags(G_SCAN_TOKEN_NODE(masked), STNF_PROD); - masked->bytes = NULL; masked->len = 0; masked->raw = NULL; - masked->atoms = NULL; - masked->count = 0; + masked->raw_count = 0; + + masked->enrolled_atoms = NULL; + masked->enrolled_count = 0; } @@ -174,14 +179,14 @@ static void g_scan_token_node_masked_finalize(GScanTokenNodeMasked *masked) if (masked->bytes != NULL) free(masked->bytes); - for (i = 0; i < masked->count; i++) + for (i = 0; i < masked->raw_count; i++) exit_szstr(&masked->raw[i]); if (masked->raw != NULL) free(masked->raw); - if (masked->atoms != NULL) - free(masked->atoms); + if (masked->enrolled_atoms != NULL) + free(masked->enrolled_atoms); G_OBJECT_CLASS(g_scan_token_node_masked_parent_class)->finalize(G_OBJECT(masked)); @@ -305,7 +310,6 @@ static void g_scan_token_node_masked_visit(GScanTokenNodeMasked *node, scan_tree /****************************************************************************** * * * 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] * @@ -318,7 +322,7 @@ static void g_scan_token_node_masked_visit(GScanTokenNodeMasked *node, scan_tree * * ******************************************************************************/ -static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *node, GScanContext *context, GEngineBackend *backend, size_t maxsize, size_t *slow) +static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *node, GEngineBackend *backend, size_t maxsize, size_t *slow) { bool result; /* Statut à retourner */ bool forced; /* Inclusion dans un scan ? */ @@ -333,6 +337,8 @@ static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *node, GScanCon { *slow += (maxsize * 2); + node->raw = make_atoms_from_masked_bytes(node->bytes, node->len, &node->raw_count); + /** * Dans le cas bien précis de l'usage de l'algorithme Bitap pour les recherches * dans le contenu binaire à analyser, on tire parti du coût nul des recherches @@ -353,19 +359,23 @@ static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *node, GScanCon else { - node->raw = make_atoms_from_masked_byte(node->bytes[0].value, node->bytes[0].mask, &node->count); + node->enrolled_atoms = malloc(node->raw_count * sizeof(tracked_scan_atom_t)); + node->enrolled_count = node->raw_count; - node->atoms = malloc(node->count * sizeof(tracked_scan_atom_t)); - - for (i = 0; i < node->count && result; i++) + for (i = 0; i < node->enrolled_count && result; i++) { - find_best_atom(&node->raw[i], maxsize, &node->atoms[i], NULL); + find_best_atom(&node->raw[i], maxsize, &node->enrolled_atoms[i], NULL); - result = enroll_prepared_atom(&node->raw[i], context, backend, &node->atoms[i]); + /** + * Correction : si l'atome ne représente qu'une vue partielle, + * la validation rapide ne peut s'appliquer. + */ + if (node->enrolled_atoms[i].fast_check) + node->enrolled_atoms[i].fast_check = (node->enrolled_atoms[i].len == node->len); - } + result = enroll_prepared_atom(&node->raw[i], backend, &node->enrolled_atoms[i]); - node->enrolled_count = node->count; + } } @@ -378,6 +388,34 @@ static bool g_scan_token_node_masked_enroll(GScanTokenNodeMasked *node, GScanCon /****************************************************************************** * * +* 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_masked_build_id(GScanTokenNodeMasked *node, GEngineBackend *backend) +{ + bool result; /* Statut à retourner */ + size_t i; /* Boucle de parcours #1 */ + + result = true; + + for (i = 0; i < node->enrolled_count && result; i++) + result = build_atom_pattern_id(&node->enrolled_atoms[i], backend); + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : bytes = octets partiels avec leur masque à interpréter. * * len = quantité d'octets à interpréter. * * start = point d'analyse à respecter. * @@ -419,13 +457,10 @@ static bool check_scan_token_node_masked_content(const masked_byte_t *bytes, siz /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offset = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* 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. * * * @@ -435,37 +470,36 @@ static bool check_scan_token_node_masked_content(const masked_byte_t *bytes, siz * * ******************************************************************************/ -static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { - bool initialized; /* Initialisation du suivi ? */ #ifndef NDEBUG bool forced; /* Inclusion dans un scan ? */ #endif - size_t ocount; /* Quantité de bornes présentes*/ - node_offset_range_t * const *ranges_ptr;/* Bornes d'espace à parcourir */ size_t i; /* Boucle de parcours #1 */ const tracked_scan_atom_t *atom; /* Atome correspondant */ - size_t count; /* Quantité de bribes trouvées */ - const phys_t *found; /* Localisations des bribes */ - size_t k; /* Boucle de parcours #2 */ - phys_t new_begin; /* Nouveau départ à tester */ - size_t o; /* Boucle de parcours #3 */ - const node_offset_range_t *range; /* Bornes d'espace à parcourir */ + GUMemSlice *atoms; /* Localisations des bribes */ + const umem_slice_iter_t *aiter; /* Boucle de parcours #2 */ + match_area_t *end; /* Borne de fin de parcours */ + match_area_t *pos; /* Position courante */ bool status; /* Bilan d'une correspondance */ - size_t pcount; /* Nombre de correspondances */ - match_area_t * const *pending_ptr; /* Correspondances actuelles */ - size_t p; /* Boucle de parcours #4 */ - match_area_t *pending; /* Correspondance à traiter */ + match_area_t *area; /* Correspondance à valider */ + match_area_t *next; /* Correspondance suivante */ phys_t after; /* Espace disposible après */ - phys_t min; /* Borne minimale déterminée */ - phys_t max; /* Borne maximale déterminée */ - phys_t j; /* Boucle de parcours #5 */ + 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 (0x1) printf("=================== CHECK :: %s (skip? %d)\n", __FUNCTION__, *skip); if (*skip) return; - initialized = are_pending_matches_initialized(matches); - /** * Si l'analyse arrive à un ou plusieurs octets masqués, soit il s'agit du * premier noeud, et la génération d'atomes a été forcée pour obtenir des @@ -475,61 +509,103 @@ static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *n */ #ifndef NDEBUG forced = (g_scan_token_node_get_flags(G_SCAN_TOKEN_NODE(node)) & STNF_MAIN); - assert((!initialized && forced) || (initialized && (!forced || not))); + assert((!params->initialized && forced) || (params->initialized && (!forced || cflags & TNCF_KEEP_DISCARDED))); #endif - ranges_ptr = get_node_search_offset_ranges(offset, &ocount); - - /* Si aucune correspondance n'a été établie */ - if (!initialized) + if (!params->initialized) { for (i = 0; i < node->enrolled_count; i++) { - atom = &node->atoms[i]; + atom = &node->enrolled_atoms[i]; - found = g_scan_context_get_atom_matches(context, atom->pid, &count); + atoms = g_scan_context_get_atom_matches(params->context, atom->pid); - for (k = 0; k < count; k++) + if (atom->fast_check) { - assert(atom->pos == 0); + for (aiter = g_umem_slice_get_iter(atoms); aiter != NULL; aiter = aiter->next) + { + end = aiter->data_end; - new_begin = found[k]; + for (pos = aiter->data; pos < end; pos++) + { + /** + * 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. + */ + pos->end = pos->start + atom->len; - /** - * Si des bornes sont spécifiées, la position de l'atome est testée. - * - * Dans la pratique, cette situation (non initialisée) ne peut provenir - * que d'un espace situé dans le vide, donc couvrant un large périmètre. - * La validation a ainsi de grandes chances de passer... - * - * Le motif pouvant amener à cette situation (pas d'initialisation, - * mais à décalage à considérer) est par exemple : - * - * ~( ?? ?1 ) - * - */ - if (ocount > 0) - { - if (!does_node_search_offset_include_pos_forward(offset, 0, new_begin)) - continue; - } + if (cflags & TNCF_KEEP_DISCARDED) + { + add_tail_match_area(pos, ¶ms->kept_areas); + params->kept_count++; + } - /** - * Existe-t-il assez de place pour faire tenir le motif masqué ? - */ - if ((new_begin + node->len) > matches->content_end) - continue; + else if (cflags & TNCF_CREATE_NEW) + { + add_tail_match_area(pos, ¶ms->created_areas); + params->created_count++; + } + + else + { + assert(cflags & TNCF_UPDATE_IN_PLACE); + + add_tail_match_area(pos, ¶ms->main_areas); + params->main_count++; - status = check_scan_token_node_masked_content(node->bytes, node->len, new_begin, content); + } + + } - if ((status && !not) || (!status && not)) + } + + } + + else + { + for (aiter = g_umem_slice_get_iter(atoms); aiter != NULL; aiter = aiter->next) { - /** - * Il ne peut y avoir qu'une seule séquence d'octets à un même - * emplacement, donc le couple (start, len) enregistré est - * unique. - */ - add_pending_match(matches, new_begin, node->len); + end = aiter->data_end; + + for (pos = aiter->data; pos < end; pos++) + { + status = check_scan_token_node_masked_content(node->bytes, node->len, + pos->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. + */ + pos->end = pos->start + node->len; + + if (cflags & TNCF_KEEP_DISCARDED) + { + add_tail_match_area(pos, ¶ms->kept_areas); + params->kept_count++; + } + + else if (cflags & TNCF_CREATE_NEW) + { + add_tail_match_area(pos, ¶ms->created_areas); + params->created_count++; + } + + else + { + assert(cflags & TNCF_UPDATE_IN_PLACE); + + add_tail_match_area(pos, ¶ms->main_areas); + params->main_count++; + + } + + } + + } } @@ -539,69 +615,77 @@ static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *n } - /* Si les correspondances en place sont à confirmer et compléter */ + /** + * Poursuite des traitements sur des correspondances déjà amorcées, impliquant + * des comparaisons entières de motifs. + */ else { - reset_pending_matches_ttl(matches); + if (0x1) printf(" LIST : %p (sz = %zu)\n", params->main_areas, params->main_count); - pending_ptr = get_all_pending_matches(matches, &pcount); - - for (p = 0; p < pcount; p++) + for_each_match_area_safe(area, ¶ms->main_areas, next) { - pending = (*pending_ptr) + p; + assert(area->end <= params->content_end); + + after = params->content_end - area->end; - assert(pending->end <= matches->content_end); + if (0x1) printf("---------- iter @ %u -> %u\n", (unsigned int)area->start, (unsigned int)area->end); + + /** + * S'il s'avère qu'il existe de multiples correspondances dans l'espace + * analysé, c'est la prise en compte d'une éventuelle avarice quant aux + * distances consommées qui va sélectionner la position d'une bribe de + * correspondance retenue. + * + * Par exemple, deux correspondances '?1 ?1 [1-3] ?2 ?2' peuvent être + * valides pour un même contenu : + * + * aa.bbb -> correspondance 'aa.bb' + * ^ + * + * aa.bbb -> correspondance 'aa..bb' + * ^ + */ - after = matches->content_end - pending->end; + min_end = params->content_end; + max_end = params->content_start; - new_begin = pending->end; + updated = false; - if (ocount > 0) + /* Souplesse dans les positions ? */ + if (offsets_exist(¶ms->offset)) { - for (o = 0; o < ocount; o++) + ranges = get_node_search_offset_ranges_2(¶ms->offset, &rcount); + + for (r = 0; r < rcount; r++) { - range = (*ranges_ptr) + o; - - /** - * Si bornes de tolérance il y a, l'espace restant est validé en - * tenant compte de ces bornes. - */ - if (!get_node_offset_range(range, node->len, after, &min, &max)) - continue; - - /** - * Une recherche des différentes correspondances amont est lancée. - */ - for (j = min; j <= max; j++) + 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 + node->len) > after) + break; + status = check_scan_token_node_masked_content(node->bytes, node->len, - new_begin + j, content); + area->end + p, params->content); - if ((status && !not) || (!status && not)) + if (status) { - /** - * S'il s'avère qu'il existe de multiples correspondances dans l'espace - * analysé, c'est la fonction extend_pending_match_ending() qui - * duplique cette correspondance, en s'appuyant sur le TTL pour - * repérer ce cas de figure. - * - * Par exemple, deux correspondances '?1 ?1 [1-3] ?2 ?2' - * sont valides pour un même contenu : - * - * aa.bbb -> correspondance 'aa.bb' - * ^ - * - * aa.bbb -> correspondance 'aa..bb' - * ^ - */ - extend_pending_match_ending(matches, p, new_begin + j + node->len); + updated_edge = area->end + p + node->len; - /** - * Comme l'extension a pu conduire à un ajout et donc à une - * réallocation de la liste, on recharge l'élément pour les - * itérations suivantes. - */ - pending = (*pending_ptr) + p; + if (updated_edge < min_end) + min_end = updated_edge; + + if (updated_edge > max_end) + max_end = updated_edge; + + updated = true; } @@ -611,55 +695,133 @@ static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *n } + /* 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. + * représenté, alors la corresponance est écartée sans appel. */ - if (node->len > after) - continue; + if (node->len <= after) + { + status = check_scan_token_node_masked_content(node->bytes, node->len, + area->end, params->content); + + if (status) + { + updated_edge = area->end + node->len; + + min_end = updated_edge; + max_end = updated_edge; + + updated = true; + + } + + } - new_begin = pending->end; + } - status = check_scan_token_node_masked_content(node->bytes, node->len, new_begin, content); + if (updated) + { + /** + * Si seuls les rejets sont d'intérêt, les correspondances établies + * ne se voient pas mises à jours ni retirées. + */ - if ((status && !not) || (!status && not)) + if ((cflags & TNCF_KEEP_DISCARDED) == 0) { - extend_pending_match_ending(matches, p, new_begin + node->len); + if (cflags & TNCF_UPDATE_IN_PLACE) + area->end = (1 /* greedy */ ? min_end : max_end); - /** - * Comme il n'y a qu'une seule itération par correspondance, - * nul besoin de recharcher l'élément. - */ + 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... + */ - purge_pending_matches(matches); + 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 + + } + + } + + } } - set_pending_matches_initialized(matches); + params->initialized = true; - disable_all_ranges_in_node_search_offset(offset); + disable_all_ranges_in_node_search_offset(¶ms->offset); } /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offsets = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* 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. * * * @@ -669,26 +831,32 @@ static void g_scan_token_node_masked_check_forward(const GScanTokenNodeMasked *n * * ******************************************************************************/ -static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { #ifndef NDEBUG bool forced; /* Inclusion dans un scan ? */ #endif - size_t pcount; /* Nombre de correspondances */ - match_area_t * const *pending_ptr; /* Correspondances actuelles */ - size_t ocount; /* Quantité de bornes présentes*/ - node_offset_range_t * const *ranges_ptr;/* Bornes d'espace à parcourir */ - size_t p; /* Boucle de parcours #1 */ - const match_area_t *pending; /* Correspondance à traiter */ - phys_t before; /* Espace disposible avant */ - phys_t new_begin; /* Nouveau départ à tester */ - size_t o; /* Boucle de parcours #2 */ - const node_offset_range_t *range; /* Bornes d'espace à parcourir */ - phys_t min; /* Borne minimale déterminée */ - phys_t max; /* Borne maximale déterminée */ - phys_t j; /* Boucle de parcours #3 */ + + + 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 (0x1) printf("=================== CHECK :: %s (skip? %d)\n", __FUNCTION__, *skip); + if (*skip) return; @@ -696,7 +864,7 @@ static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked * * En lecture à rebourd, au moins un noeud a été solicité pour analyse (lors * du sens de lecteur normal). Donc l'initialisation a déjà dû avoir lieu. */ - assert(are_pending_matches_initialized(matches)); + assert(params->initialized); /** * Si les recherches associées au noeud ont été forcées, alors les traitements @@ -707,65 +875,121 @@ static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked * assert(!forced); #endif - reset_pending_matches_ttl(matches); - pending_ptr = get_all_pending_matches(matches, &pcount); - ranges_ptr = get_node_search_offset_ranges(offset, &ocount); - for (p = 0; p < pcount; p++) + /** + * ............. + */ + if (0) { - pending = (*pending_ptr) + p; - assert(matches->content_start <= pending->start); - before = pending->start - matches->content_start; + ; + + - new_begin = pending->start - node->len; + } + + /** + * Poursuite des traitements sur des correspondances déjà amorcées, impliquant + * des comparaisons entières de motifs. + */ + else + { + if (0x1) printf(" LIST : %p (sz = %zu)\n", params->main_areas, params->main_count); - if (ocount > 0) + for_each_match_area_safe(area, ¶ms->main_areas, next) { - for (o = 0; o < ocount; o++) + assert(params->content_start <= area->start); + + before = area->start - params->content_start; + + if (0x1) 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; + + /* Souplesse dans les positions ? */ + if (offsets_exist(¶ms->offset)) { - range = (*ranges_ptr) + o; + ranges = get_node_search_offset_ranges_2(¶ms->offset, &rcount); - /** - * Si bornes de tolérance il y a, l'espace restant est validé en - * tenant compte de ces bornes. - */ - if (!get_node_offset_range(range, node->len, before, &min, &max)) + for (r = 0; r < rcount; r++) { - if (not) - extend_pending_match_beginning(matches, p, pending->start - node->len); + 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 + node->len) > before) + break; + + status = check_scan_token_node_masked_content(node->bytes, node->len, + area->start - node->len - p, + params->content); + + if (status) + { + updated_edge = area->start - node->len - p; + + if (updated_edge > min_start) + min_start = updated_edge; + + if (updated_edge < max_start) + max_start = updated_edge; + + updated = true; - continue; + } + + } } + } + + /* Position immédiatement attendue */ + else + { /** - * Une recherche des différentes correspondances amont est lancée. + * 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. */ - for (j = min; j <= max; j++) + if (node->len <= before) { status = check_scan_token_node_masked_content(node->bytes, node->len, - new_begin - j, content); + area->start - node->len, + params->content); - if ((status && !not) || (!status && not)) + if (status) { - /** - * S'il s'avère qu'il existe de multiples correspondances dans l'espace - * analysé, c'est la fonction extend_pending_match_beginning() qui - * duplique cette correspondance, en s'appuyant sur le TTL pour - * repérer ce cas de figure. - */ - extend_pending_match_beginning(matches, p, new_begin); + updated_edge = area->start - node->len; - /** - * Comme l'extension a pu conduire à un ajout et donc à une - * réallocation de la liste, on recharge l'élément pour les - * itérations suivantes. - */ - pending = (*pending_ptr) + p; + if (updated_edge > min_start) + min_start = updated_edge; + + if (updated_edge < max_start) + max_start = updated_edge; + + updated = true; } @@ -773,35 +997,92 @@ static void g_scan_token_node_masked_check_backward(const GScanTokenNodeMasked * } - } - - else - { - /** - * Si le début 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. - */ - if (node->len > before) + if (updated) { - if (not) - extend_pending_match_beginning(matches, p, new_begin); + /** + * 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 - continue; + } } - status = check_scan_token_node_masked_content(node->bytes, node->len, new_begin, content); + 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 ((status && !not) || (!status && not)) - extend_pending_match_beginning(matches, p, new_begin); + 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 + + } + + } } } - purge_pending_matches(matches); - - disable_all_ranges_in_node_search_offset(offset); + disable_all_ranges_in_node_search_offset(¶ms->offset); } diff --git a/src/analysis/scan/patterns/tokens/nodes/masked.h b/src/analysis/scan/patterns/tokens/nodes/masked.h index d1765fa..04a05bc 100644 --- a/src/analysis/scan/patterns/tokens/nodes/masked.h +++ b/src/analysis/scan/patterns/tokens/nodes/masked.h @@ -49,15 +49,6 @@ typedef struct _GScanTokenNodeMasked GScanTokenNodeMasked; typedef struct _GScanTokenNodeMaskedClass GScanTokenNodeMaskedClass; -/* Mémorisation d'un octet visé avec son masque */ -typedef struct _masked_byte_t -{ - bin_t value; /* Valeur de l'octet visé */ - bin_t mask; /* Masque à appliquer */ - -} masked_byte_t; - - /* Indique le type défini pour un noeud représentant une bribe partielle à retrouver. */ GType g_scan_token_node_masked_get_type(void); diff --git a/src/analysis/scan/patterns/tokens/nodes/not.c b/src/analysis/scan/patterns/tokens/nodes/not.c index 645a1c8..81fce28 100644 --- a/src/analysis/scan/patterns/tokens/nodes/not.c +++ b/src/analysis/scan/patterns/tokens/nodes/not.c @@ -24,6 +24,9 @@ #include "not.h" +#include <assert.h> + + #include "not-int.h" @@ -48,17 +51,23 @@ static void g_scan_token_node_not_finalize(GScanTokenNodeNot *); /* --------------------- IMPLEMENTATION DES FONCTIONS DE CLASSE --------------------- */ +/* Prend acte d'une nouvelle propriété pour le noeud. */ +static void g_scan_token_node_not_apply_flags(GScanTokenNodeNot *, ScanTokenNodeFlags); + /* Parcourt une arborescence de noeuds et y relève des éléments. */ static void g_scan_token_node_not_visit(GScanTokenNodeNot *, scan_tree_points_t *); /* Inscrit la définition d'un motif dans un moteur de recherche. */ -static bool g_scan_token_node_not_enroll(GScanTokenNodeNot *, GScanContext *, GEngineBackend *, size_t, size_t *); +static bool g_scan_token_node_not_enroll(GScanTokenNodeNot *, GEngineBackend *, size_t, size_t *); + +/* Récupère un identifiant final pour un atome d'octets. */ +static bool g_scan_token_node_not_build_id(GScanTokenNodeNot *, GEngineBackend *); /* Transforme les correspondances locales en trouvailles. */ -static void g_scan_token_node_not_check_forward(const GScanTokenNodeNot *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_not_check_forward(const GScanTokenNodeNot *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); /* Transforme les correspondances locales en trouvailles. */ -static void g_scan_token_node_not_check_backward(const GScanTokenNodeNot *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_not_check_backward(const GScanTokenNodeNot *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); @@ -95,8 +104,10 @@ static void g_scan_token_node_not_class_init(GScanTokenNodeNotClass *klass) node = G_SCAN_TOKEN_NODE_CLASS(klass); + node->apply = (apply_scan_token_node_flags_fc)g_scan_token_node_not_apply_flags; node->visit = (visit_scan_token_node_fc)g_scan_token_node_not_visit; node->enroll = (enroll_scan_token_node_fc)g_scan_token_node_not_enroll; + node->build_id = (build_scan_token_node_id_fc)g_scan_token_node_not_build_id; node->check_forward = (check_scan_token_node_fc)g_scan_token_node_not_check_forward; node->check_backward = (check_scan_token_node_fc)g_scan_token_node_not_check_backward; @@ -223,6 +234,26 @@ bool g_scan_token_node_not_create(GScanTokenNodeNot *not, GScanTokenNode *child) /****************************************************************************** * * +* Paramètres : node = noeud de motif à mettre à jour. * +* flags = propriétés particulières à associer au noeud. * +* * +* Description : Prend acte d'une nouvelle propriété pour le noeud. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_scan_token_node_not_apply_flags(GScanTokenNodeNot *node, ScanTokenNodeFlags flags) +{ + g_scan_token_node_set_flags(node->child, flags); + +} + + +/****************************************************************************** +* * * Paramètres : node = point de départ du parcours à effectuer. * * points = points capitaux de l'arborescence. [OUT] * * * @@ -244,7 +275,6 @@ static void g_scan_token_node_not_visit(GScanTokenNodeNot *node, scan_tree_point /****************************************************************************** * * * 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] * @@ -257,11 +287,11 @@ static void g_scan_token_node_not_visit(GScanTokenNodeNot *node, scan_tree_point * * ******************************************************************************/ -static bool g_scan_token_node_not_enroll(GScanTokenNodeNot *node, GScanContext *context, GEngineBackend *backend, size_t maxsize, size_t *slow) +static bool g_scan_token_node_not_enroll(GScanTokenNodeNot *node, GEngineBackend *backend, size_t maxsize, size_t *slow) { bool result; /* Statut à retourner */ - result = _g_scan_token_node_enroll(node->child, context, backend, maxsize, slow); + result = _g_scan_token_node_enroll(node->child, backend, maxsize, slow); return result; @@ -270,13 +300,34 @@ static bool g_scan_token_node_not_enroll(GScanTokenNodeNot *node, GScanContext * /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offset = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* 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_not_build_id(GScanTokenNodeNot *node, GEngineBackend *backend) +{ + bool result; /* Statut à retourner */ + + result = g_scan_token_node_build_id(node->child, backend); + + 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. * * * @@ -286,8 +337,12 @@ static bool g_scan_token_node_not_enroll(GScanTokenNodeNot *node, GScanContext * * * ******************************************************************************/ -static void g_scan_token_node_not_check_forward(const GScanTokenNodeNot *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_not_check_forward(const GScanTokenNodeNot *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { + +#if 0 + + bool initialized; /* Initialisation du suivi ? */ phys_t i; /* Boucle de parcours */ @@ -322,7 +377,7 @@ static void g_scan_token_node_not_check_forward(const GScanTokenNodeNot *node, G _g_scan_token_node_check_forward(node->child, context, content, matches, offset, !not, skip); - +#endif } @@ -330,13 +385,10 @@ static void g_scan_token_node_not_check_forward(const GScanTokenNodeNot *node, G /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offset = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* 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. * * * @@ -346,7 +398,7 @@ static void g_scan_token_node_not_check_forward(const GScanTokenNodeNot *node, G * * ******************************************************************************/ -static void g_scan_token_node_not_check_backward(const GScanTokenNodeNot *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_not_check_backward(const GScanTokenNodeNot *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { diff --git a/src/analysis/scan/patterns/tokens/nodes/plain.c b/src/analysis/scan/patterns/tokens/nodes/plain.c index 71f5f17..166ce74 100644 --- a/src/analysis/scan/patterns/tokens/nodes/plain.c +++ b/src/analysis/scan/patterns/tokens/nodes/plain.c @@ -52,20 +52,26 @@ 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 *, GScanContext *, GEngineBackend *, size_t, size_t *); +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 *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +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 *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_plain_check_backward(const GScanTokenNodePlain *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); @@ -102,8 +108,11 @@ static void g_scan_token_node_plain_class_init(GScanTokenNodePlainClass *klass) 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; @@ -124,8 +133,6 @@ static void g_scan_token_node_plain_class_init(GScanTokenNodePlainClass *klass) static void g_scan_token_node_plain_init(GScanTokenNodePlain *plain) { - g_scan_token_node_set_flags(G_SCAN_TOKEN_NODE(plain), STNF_PROD); - init_szstr(&plain->orig); plain->modifier = NULL; plain->flags = SPNF_NONE; @@ -314,6 +321,29 @@ char *g_scan_token_node_plain_get_modifier_path(const GScanTokenNodePlain *node, /****************************************************************************** * * +* 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] * * * @@ -327,9 +357,25 @@ char *g_scan_token_node_plain_get_modifier_path(const GScanTokenNodePlain *node, 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; + + } + } @@ -349,7 +395,7 @@ static void g_scan_token_node_plain_visit(GScanTokenNodePlain *node, scan_tree_p * * ******************************************************************************/ -static bool g_scan_token_node_plain_enroll(GScanTokenNodePlain *node, GScanContext *context, GEngineBackend *backend, size_t maxsize, size_t *slow) +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 */ @@ -442,7 +488,7 @@ static bool g_scan_token_node_plain_enroll(GScanTokenNodePlain *node, GScanConte /* Enregistrements en masse */ for (i = 0; i < node->count && result; i++) - result = enroll_prepared_atom(&node->raw[i], context, backend, &node->atoms[i]); + result = enroll_prepared_atom(&node->raw[i], backend, &node->atoms[i]); exit: @@ -453,6 +499,34 @@ static bool g_scan_token_node_plain_enroll(GScanTokenNodePlain *node, GScanConte /****************************************************************************** * * +* 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. * @@ -478,11 +552,11 @@ static bool check_scan_token_node_plain_content(const sized_binary_t *raw, const init_vmpa(&pos, start, VMPA_NO_VIRTUAL); - /* Validation du contenu avant l'atome */ + /* Validation du motif intégral */ - if (atom->pos > 0) + if (atom == NULL) { - ptr = g_binary_content_get_raw_access(content, &pos, atom->pos); + 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, @@ -492,39 +566,67 @@ static bool check_scan_token_node_plain_content(const sized_binary_t *raw, const if (ptr == NULL) goto done; if (nocase) - ret = memcasecmp(raw->data, ptr, atom->pos); + ret = memcasecmp(raw->data, ptr, raw->len); else - ret = memcmp(raw->data, ptr, atom->pos); + ret = memcmp(raw->data, ptr, raw->len); - if (ret != 0) goto done; + result = (ret == 0); } - /* Validation du contenu après l'atome */ + /* Validation des extrémités */ - if (atom->rem > 0) + else { - advance_vmpa(&pos, atom->len); + /* Validation du contenu avant l'atome */ - ptr = g_binary_content_get_raw_access(content, &pos, atom->rem); + 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 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; + /** + * 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 + atom->pos + atom->len, ptr, atom->rem); - else - ret = memcmp(raw->data + atom->pos + atom->len, ptr, atom->rem); + if (nocase) + ret = memcasecmp(raw->data, ptr, atom->pos); + else + ret = memcmp(raw->data, ptr, atom->pos); - if (ret != 0) goto done; + if (ret != 0) goto done; - } + } - result = true; + /* 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: @@ -535,13 +637,10 @@ static bool check_scan_token_node_plain_content(const sized_binary_t *raw, const /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offset = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* 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. * * * @@ -551,236 +650,408 @@ static bool check_scan_token_node_plain_content(const sized_binary_t *raw, const * * ******************************************************************************/ -static void g_scan_token_node_plain_check_forward(const GScanTokenNodePlain *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_plain_check_forward(const GScanTokenNodePlain *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { - bool initialized; /* Initialisation du suivi ? */ bool track_path; /* Conservation du chemin */ bool nocase; /* Pas d'intérêt pour la casse */ - size_t ocount; /* Quantité de bornes présentes*/ size_t i; /* Boucle de parcours #1 */ const sized_binary_t *raw; /* Données brutes d'origine */ const tracked_scan_atom_t *atom; /* Atome correspondant */ - size_t count; /* Quantité de bribes trouvées */ - const phys_t *found; /* Localisations des bribes */ - size_t k; /* Boucle de parcours #2 */ - phys_t new_begin; /* Nouveau départ à tester */ + GUMemSlice *atoms; /* Localisations des bribes */ + const umem_slice_iter_t *aiter; /* Boucle de parcours #2 */ + match_area_t *end; /* Borne de fin de parcours */ + match_area_t *pos; /* Position courante */ bool status; /* Bilan d'une correspondance */ - size_t pcount; /* Nombre de correspondances */ - match_area_t * const *pending_ptr; /* Correspondances actuelles */ - size_t p; /* Boucle de parcours #3 */ - const match_area_t *pending; /* Correspondance à traiter */ + match_area_t *area; /* Correspondance à valider */ + match_area_t *next; /* Correspondance suivante */ + 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 (0x1) printf("=================== CHECK :: %s (skip? %d)\n", __FUNCTION__, *skip); if (*skip) return; - initialized = are_pending_matches_initialized(matches); - track_path = (G_SCAN_TOKEN_NODE(node)->flags & STNF_MAIN); nocase = (node->flags & SPNF_CASE_INSENSITIVE); - get_node_search_offset_ranges(offset, &ocount); - - for (i = 0; i < node->count; i++) + /** + * Création de premières marques de correspondances. + */ + if (!params->initialized) { - raw = &node->raw[i]; - atom = &node->atoms[i]; + for (i = 0; i < node->count; i++) + { + raw = &node->raw[i]; + atom = &node->atoms[i]; - found = g_scan_context_get_atom_matches(context, atom->pid, &count); + atoms = g_scan_context_get_atom_matches(params->context, atom->pid); - if (!initialized) - { - for (k = 0; k < count; k++) + if (atom->fast_check) { - new_begin = found[k] - atom->pos; - - /** - * Si personne n'a manipulé les pré-résultats, mais qu'un décallage - * est spécifié par un noeud précédent, une validation sur la base - * d'une position 0 est menée. - */ - if (ocount > 0) + for (aiter = g_umem_slice_get_iter(atoms); aiter != NULL; aiter = aiter->next) { - if (!does_node_search_offset_include_pos_forward(offset, 0, new_begin)) + end = aiter->data_end; + + for (pos = aiter->data; pos < end; pos++) { - if (not) - add_pending_match(matches, new_begin, raw->len); + /** + * 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. + */ + pos->end = pos->start + atom->len; - continue; + if (cflags & TNCF_KEEP_DISCARDED) + { + add_tail_match_area(pos, ¶ms->kept_areas); + params->kept_count++; + } + + else if (cflags & TNCF_CREATE_NEW) + { + add_tail_match_area(pos, ¶ms->created_areas); + params->created_count++; + } + + else + { + assert(cflags & TNCF_UPDATE_IN_PLACE); + + add_tail_match_area(pos, ¶ms->main_areas); + params->main_count++; + + } } + } - status = check_scan_token_node_plain_content(raw, atom, nocase, new_begin, content); + } - if ((status && !not) || (!status && not)) + else + { + for (aiter = g_umem_slice_get_iter(atoms); aiter != NULL; aiter = aiter->next) { - /** - * Il ne peut y avoir qu'une seule séquence d'octets à un même - * emplacement, donc le couple (new_begin, len) enregistré est - * unique. - */ - if (track_path) - add_pending_match_with_path(matches, new_begin, raw->len, i); - else - add_pending_match(matches, new_begin, raw->len); + end = aiter->data_end; + + for (pos = aiter->data; pos < end; pos++) + { + status = check_scan_token_node_plain_content(raw, atom, nocase, + pos->start - atom->pos, 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. + */ + pos->start -= atom->pos; + pos->end = pos->start + raw->len; + + if (cflags & TNCF_KEEP_DISCARDED) + { + add_tail_match_area(pos, ¶ms->kept_areas); + params->kept_count++; + } + + else if (cflags & TNCF_CREATE_NEW) + { + add_tail_match_area(pos, ¶ms->created_areas); + params->created_count++; + } + + else + { + assert(cflags & TNCF_UPDATE_IN_PLACE); + + add_tail_match_area(pos, ¶ms->main_areas); + params->main_count++; + + } + + } + + } } + } } - else - { - reset_pending_matches_ttl(matches); + } - pending_ptr = get_all_pending_matches(matches, &pcount); + /** + * Poursuite des traitements sur des correspondances déjà amorcées, impliquant + * des comparaisons entières de motifs. + */ + else + { + if (0x1) printf(" LIST : %p (sz = %zu)\n", params->main_areas, params->main_count); - for (p = 0; p < pcount; p++) + for_each_match_area_safe(area, ¶ms->main_areas, next) + { + assert(area->end <= params->content_end); + + after = params->content_end - area->end; + + if (0x1) 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++) { - pending = (*pending_ptr) + p; + raw = &node->raw[i]; - assert(matches->content_start <= pending->start); - - for (k = 0; k < count; k++) + /* Souplesse dans les positions ? */ + if (offsets_exist(¶ms->offset)) { - new_begin = found[k] - atom->pos; + ranges = get_node_search_offset_ranges_2(¶ms->offset, &rcount); - /** - * Si bornes de tolérance il y a, on valide la position. - * - * Sinon les correspondances passées et actuelle doivent - * être jointes. - */ - if (ocount > 0) + for (r = 0; r < rcount; r++) { - if (!does_node_search_offset_include_pos_forward(offset, pending->end, new_begin)) + 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++) { - if (not) + /** + * 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) { - extend_pending_match_ending(matches, p, pending->end + raw->len); + updated_edge = area->end + p + raw->len; - /** - * Comme l'extension a pu conduire à un ajout et donc à une - * réallocation de la liste, on recharge l'élément pour les - * itérations suivantes. - */ - pending = (*pending_ptr) + p; + if (updated_edge < min_end) + min_end = updated_edge; - } + if (updated_edge > max_end) + max_end = updated_edge; - continue; + updated = true; + + } } + } - else + + } + + /* 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) { - if (pending->end != new_begin) - { - if (not) - { - extend_pending_match_ending(matches, p, pending->end + raw->len); + updated_edge = area->end + raw->len; - /** - * Comme l'extension a pu conduire à un ajout et donc à une - * réallocation de la liste, on recharge l'élément pour les - * itérations suivantes. - */ - pending = (*pending_ptr) + p; + if (updated_edge < min_end) + min_end = updated_edge; - } + if (updated_edge > max_end) + max_end = updated_edge; - continue; + updated = true; - } } - status = check_scan_token_node_plain_content(raw, atom, nocase, new_begin, content); + } - if ((status && !not) || (!status && not)) + } + + 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) { - /** - * 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. - * - * 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 zone 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) - * ^ - */ + new_area = g_umem_slice_alloc(params->allocator); - /** - * La seconde situation est prise en compte par la fonction - * extend_pending_match_ending() qui s'appuie sur le TTL pour - * dupliquer la correspondance pending[x] initiale. Le nouvel - * élément est placé en fin de liste, ce qui ne boulverse pas - * le parcours de liste courant, la valeur de pcount n'étant - * pas actualisée. - */ + *new_area = *area; - extend_pending_match_ending(matches, p, new_begin + raw->len); + new_area->end = (1 /* greedy */ ? min_end : max_end); - /** - * Comme l'extension a pu conduire à un ajout et donc à une - * réallocation de la liste, on recharge l'élément pour les - * itérations suivantes. - */ - pending = (*pending_ptr) + p; + add_tail_match_area(new_area, ¶ms->created_areas); + params->created_count++; } +#ifndef NDEBUG + else + assert(false); +#endif + } } - purge_pending_matches(matches); + 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 + + } + + } } } - set_pending_matches_initialized(matches); + params->initialized = true; - disable_all_ranges_in_node_search_offset(offset); + disable_all_ranges_in_node_search_offset(¶ms->offset); } /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offset = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* 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. * * * @@ -790,19 +1061,272 @@ static void g_scan_token_node_plain_check_forward(const GScanTokenNodePlain *nod * * ******************************************************************************/ -static void g_scan_token_node_plain_check_backward(const GScanTokenNodePlain *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +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 (0x1) 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); + - printf("TODO\n"); - assert(0); + /** + * ............. + */ + if (0) + { + + + ; + + + + } + + /** + * Poursuite des traitements sur des correspondances déjà amorcées, impliquant + * des comparaisons entières de motifs. + */ + else + { + if (0x1) 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 (0x1) 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); } diff --git a/src/analysis/scan/patterns/tokens/nodes/sequence.c b/src/analysis/scan/patterns/tokens/nodes/sequence.c index 91307bf..394c877 100644 --- a/src/analysis/scan/patterns/tokens/nodes/sequence.c +++ b/src/analysis/scan/patterns/tokens/nodes/sequence.c @@ -24,6 +24,9 @@ #include "sequence.h" +#include <assert.h> + + #include "any.h" #include "sequence-int.h" @@ -49,17 +52,23 @@ static void g_scan_token_node_sequence_finalize(GScanTokenNodeSequence *); /* --------------------- IMPLEMENTATION DES FONCTIONS DE CLASSE --------------------- */ +/* Prend acte d'une nouvelle propriété pour le noeud. */ +static void g_scan_token_node_sequence_apply_flags(GScanTokenNodeSequence *, ScanTokenNodeFlags); + /* Parcourt une arborescence de noeuds et y relève des éléments. */ static void g_scan_token_node_sequence_visit(GScanTokenNodeSequence *node, scan_tree_points_t *); /* Inscrit la définition d'un motif dans un moteur de recherche. */ -static bool g_scan_token_node_sequence_enroll(GScanTokenNodeSequence *, GScanContext *, GEngineBackend *, size_t, size_t *); +static bool g_scan_token_node_sequence_enroll(GScanTokenNodeSequence *, GEngineBackend *, size_t, size_t *); + +/* Récupère un identifiant final pour un atome d'octets. */ +static bool g_scan_token_node_sequence_build_id(GScanTokenNodeSequence *, GEngineBackend *); /* Transforme les correspondances locales en trouvailles. */ -static void g_scan_token_node_sequence_check_forward(const GScanTokenNodeSequence *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_sequence_check_forward(const GScanTokenNodeSequence *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); /* Transforme les correspondances locales en trouvailles. */ -static void g_scan_token_node_sequence_check_backward(const GScanTokenNodeSequence *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +static void g_scan_token_node_sequence_check_backward(const GScanTokenNodeSequence *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); @@ -76,7 +85,7 @@ G_DEFINE_TYPE(GScanTokenNodeSequence, g_scan_token_node_sequence, G_TYPE_SCAN_TO * * * Paramètres : klass = classe à initialiser. * * * -* Description : Initialise la classe des décompositions séquentielles. * +* Description : Initialise la classe des décompositions séquentielles. * * * * Retour : - * * * @@ -96,8 +105,10 @@ static void g_scan_token_node_sequence_class_init(GScanTokenNodeSequenceClass *k node = G_SCAN_TOKEN_NODE_CLASS(klass); + node->apply = (apply_scan_token_node_flags_fc)g_scan_token_node_sequence_apply_flags; node->visit = (visit_scan_token_node_fc)g_scan_token_node_sequence_visit; node->enroll = (enroll_scan_token_node_fc)g_scan_token_node_sequence_enroll; + node->build_id = (build_scan_token_node_id_fc)g_scan_token_node_sequence_build_id; node->check_forward = (check_scan_token_node_fc)g_scan_token_node_sequence_check_forward; node->check_backward = (check_scan_token_node_fc)g_scan_token_node_sequence_check_backward; @@ -330,6 +341,40 @@ GScanTokenNode *g_scan_token_node_sequence_get(const GScanTokenNodeSequence *seq /****************************************************************************** * * +* Paramètres : node = noeud de motif à mettre à jour. * +* flags = propriétés particulières à associer au noeud. * +* * +* Description : Prend acte d'une nouvelle propriété pour le noeud. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_scan_token_node_sequence_apply_flags(GScanTokenNodeSequence *node, ScanTokenNodeFlags flags) +{ + size_t i; /* Boucle de parcours */ + + if (node->count == 1) + g_scan_token_node_set_flags(node->children[0], flags); + + else if (node->count > 1) + { + g_scan_token_node_set_flags(node->children[0], flags & ~STNF_LAST); + + for (i = 1; i < (node->count - 1); i++) + g_scan_token_node_set_flags(node->children[i], flags & ~(STNF_FIRST | STNF_LAST)); + + g_scan_token_node_set_flags(node->children[node->count - 1], flags & ~STNF_FIRST); + + } + +} + + +/****************************************************************************** +* * * Paramètres : node = point de départ du parcours à effectuer. * * points = points capitaux de l'arborescence. [OUT] * * * @@ -354,7 +399,6 @@ static void g_scan_token_node_sequence_visit(GScanTokenNodeSequence *node, scan_ /****************************************************************************** * * * 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] * @@ -367,7 +411,7 @@ static void g_scan_token_node_sequence_visit(GScanTokenNodeSequence *node, scan_ * * ******************************************************************************/ -static bool g_scan_token_node_sequence_enroll(GScanTokenNodeSequence *node, GScanContext *context, GEngineBackend *backend, size_t maxsize, size_t *slow) +static bool g_scan_token_node_sequence_enroll(GScanTokenNodeSequence *node, GEngineBackend *backend, size_t maxsize, size_t *slow) { bool result; /* Statut à retourner */ size_t i; /* Boucle de parcours */ @@ -375,7 +419,35 @@ static bool g_scan_token_node_sequence_enroll(GScanTokenNodeSequence *node, GSca result = true; for (i = 0; i < node->count && result; i++) - result = _g_scan_token_node_enroll(node->children[i], context, backend, maxsize, slow); + result = _g_scan_token_node_enroll(node->children[i], backend, maxsize, slow); + + 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_sequence_build_id(GScanTokenNodeSequence *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 = g_scan_token_node_build_id(node->children[i], backend); return result; @@ -384,13 +456,10 @@ static bool g_scan_token_node_sequence_enroll(GScanTokenNodeSequence *node, GSca /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offset = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* 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. * * * @@ -400,25 +469,22 @@ static bool g_scan_token_node_sequence_enroll(GScanTokenNodeSequence *node, GSca * * ******************************************************************************/ -static void g_scan_token_node_sequence_check_forward(const GScanTokenNodeSequence *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_sequence_check_forward(const GScanTokenNodeSequence *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { size_t i; /* Boucle de parcours */ for (i = 0; i < node->count; i++) - _g_scan_token_node_check_forward(node->children[i], context, content, matches, offset, not, skip); + _g_scan_token_node_check_forward(node->children[i], params, cflags, skip); } /****************************************************************************** * * -* Paramètres : node = définition de la bribe à manipuler. * -* context = contexte de l'analyse à mener. * -* content = accès au contenu brut pour vérifications (optim.) * -* matches = suivi des correspondances à consolider. * -* offset = tolérance dans les positions à appliquer. * -* not = indique si les résultats doivent être inversés. * -* skip = détermine si l'analyse est différée. [OUT] * +* 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. * * * @@ -428,11 +494,11 @@ static void g_scan_token_node_sequence_check_forward(const GScanTokenNodeSequenc * * ******************************************************************************/ -static void g_scan_token_node_sequence_check_backward(const GScanTokenNodeSequence *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +static void g_scan_token_node_sequence_check_backward(const GScanTokenNodeSequence *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { size_t i; /* Boucle de parcours */ for (i = node->count; i > 0 ; i--) - _g_scan_token_node_check_backward(node->children[i - 1], context, content, matches, offset, not, skip); + _g_scan_token_node_check_backward(node->children[i - 1], params, cflags, skip); } |