diff options
author | Cyrille Bagard <nocbos@gmail.com> | 2024-01-21 22:36:47 (GMT) |
---|---|---|
committer | Cyrille Bagard <nocbos@gmail.com> | 2024-01-21 22:36:47 (GMT) |
commit | 0ff1e52622828663d01f98c97f2cd8eccb8facf8 (patch) | |
tree | 88b5fcf2412f863276876d0b8ad8db91903f3758 /src/analysis/scan/patterns | |
parent | 0fac40d5a5752e8d7b92f57ea3cfa089f13a2d1f (diff) |
Refactor the scan match storage.
Diffstat (limited to 'src/analysis/scan/patterns')
25 files changed, 2816 insertions, 867 deletions
diff --git a/src/analysis/scan/patterns/Makefile.am b/src/analysis/scan/patterns/Makefile.am index c520321..989a562 100644 --- a/src/analysis/scan/patterns/Makefile.am +++ b/src/analysis/scan/patterns/Makefile.am @@ -10,6 +10,7 @@ libanalysisscanpatterns_la_SOURCES = \ modarg.h \ modifier-int.h \ modifier.h modifier.c \ + patid.h \ token-int.h \ token.h token.c diff --git a/src/analysis/scan/patterns/backend-int.h b/src/analysis/scan/patterns/backend-int.h index b2587df..90daec9 100644 --- a/src/analysis/scan/patterns/backend-int.h +++ b/src/analysis/scan/patterns/backend-int.h @@ -33,11 +33,17 @@ typedef size_t (* get_backend_atom_max_size_fc) (const GEngineBackend *); /* Inscrit dans le moteur une chaîne de caractères à rechercher. */ -typedef patid_t (* enroll_plain_into_backend_fc) (GEngineBackend *, GScanContext *, const uint8_t *, size_t); +typedef patid_t (* enroll_plain_into_backend_fc) (GEngineBackend *, const uint8_t *, size_t, uint32_t [2]); /* Met en ordre les derniers détails avant un premier scan. */ typedef void (* warm_up_backend_fc) (GEngineBackend *); +/* Récupère les identifiants finaux pour un motif recherché. */ +typedef patid_t (* build_backend_plain_pattern_id_fc) (const GEngineBackend *, const uint32_t [2]); + +/* Détermine le nombre d'identifiants constitués. */ +typedef size_t (* count_backend_plain_pattern_ids_fc) (const GEngineBackend *); + /* Parcours un contenu binaire à la recherche de motifs. */ typedef void (* run_backend_scan_fc) (const GEngineBackend *, GScanContext *); @@ -57,9 +63,11 @@ struct _GEngineBackendClass { GObjectClass parent; /* A laisser en premier */ - get_backend_atom_max_size_fc get_max_size; /* Taille maximale d'atome */ - enroll_plain_into_backend_fc enroll_plain; /* Inscription simple */ + get_backend_atom_max_size_fc get_max_size; /* Taille maximale d'atome */ + enroll_plain_into_backend_fc enroll_plain; /* Inscription simpl e */ warm_up_backend_fc warm_up; /* Préchauffage avant analyse */ + build_backend_plain_pattern_id_fc build_id; /* Définition d'identifiant*/ + count_backend_plain_pattern_ids_fc count_ids; /* Décompte des id. */ run_backend_scan_fc run_scan; /* Lancement d'une analyse */ output_backend_stats_fc output; /* Impression de statistiques */ diff --git a/src/analysis/scan/patterns/backend.c b/src/analysis/scan/patterns/backend.c index 0ecc7fe..50cc889 100644 --- a/src/analysis/scan/patterns/backend.c +++ b/src/analysis/scan/patterns/backend.c @@ -155,9 +155,9 @@ size_t g_engine_backend_get_atom_max_size(const GEngineBackend *backend) /****************************************************************************** * * * Paramètres : backend = moteur de recherche à manipuler. * -* context = contexte de l'analyse à mener. * * plain = chaîne de caractères classique à intégrer. * * len = taille de cette chaîne. * +* tmp_id = identifiants temporaires vers le motif. [OUT] * * * * Description : Inscrit dans le moteur une chaîne de caractères à rechercher.* * * @@ -167,14 +167,14 @@ size_t g_engine_backend_get_atom_max_size(const GEngineBackend *backend) * * ******************************************************************************/ -patid_t g_engine_backend_enroll_plain_pattern(GEngineBackend *backend, GScanContext *context, const uint8_t *plain, size_t len) +bool g_engine_backend_enroll_plain_pattern(GEngineBackend *backend, const uint8_t *plain, size_t len, uint32_t tmp_id[2]) { - patid_t result; /* Identifiant à retourner */ + bool result; /* Bilan à retourner */ GEngineBackendClass *class; /* Classe à activer */ class = G_ENGINE_BACKEND_GET_CLASS(backend); - result = class->enroll_plain(backend, context, plain, len); + result = class->enroll_plain(backend, plain, len, tmp_id); return result; @@ -208,6 +208,59 @@ void g_engine_backend_warm_up(GEngineBackend *backend) /****************************************************************************** * * * Paramètres : backend = moteur de recherche à manipuler. * +* tmp_id = identifiants temporaires vers le motif. [OUT] * +* * +* Description : Récupère les identifiants finaux pour un motif recherché. * +* * +* Retour : Identifiant constitué ou INVALID_PATTERN_ID en cas d'échec. * +* * +* Remarques : - * +* * +******************************************************************************/ + +patid_t g_engine_backend_build_plain_pattern_id(const GEngineBackend *backend, const uint32_t tmp_id[2]) +{ + patid_t result; /* Identifiant à retourner */ + GEngineBackendClass *class; /* Classe à activer */ + + class = G_ENGINE_BACKEND_GET_CLASS(backend); + + result = class->build_id(backend, tmp_id); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* * +* Description : Détermine le nombre d'identifiants constitués. * +* * +* Retour : Quantité de gestionnaires de suivi à prévoir. * +* * +* Remarques : - * +* * +******************************************************************************/ + +size_t g_engine_backend_count_plain_pattern_ids(const GEngineBackend *backend) +{ + size_t result; /* Quantité à retourner */ + GEngineBackendClass *class; /* Classe à activer */ + + class = G_ENGINE_BACKEND_GET_CLASS(backend); + + result = class->count_ids(backend); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * * context = lieu d'enregistrement des résultats. * * * * Description : Parcours un contenu binaire à la recherche de motifs. * diff --git a/src/analysis/scan/patterns/backend.h b/src/analysis/scan/patterns/backend.h index 8f6b929..71c97d1 100644 --- a/src/analysis/scan/patterns/backend.h +++ b/src/analysis/scan/patterns/backend.h @@ -57,11 +57,17 @@ GType g_engine_backend_get_type(void); size_t g_engine_backend_get_atom_max_size(const GEngineBackend *); /* Inscrit dans le moteur une chaîne de caractères à rechercher. */ -patid_t g_engine_backend_enroll_plain_pattern(GEngineBackend *, GScanContext *, const uint8_t *, size_t); +bool g_engine_backend_enroll_plain_pattern(GEngineBackend *, const uint8_t *, size_t, uint32_t [2]); /* Met en ordre les derniers détails avant un premier scan. */ void g_engine_backend_warm_up(GEngineBackend *); +/* Récupère les identifiants finaux pour un motif recherché. */ +patid_t g_engine_backend_build_plain_pattern_id(const GEngineBackend *, const uint32_t [2]); + +/* Détermine le nombre d'identifiants constitués. */ +size_t g_engine_backend_count_plain_pattern_ids(const GEngineBackend *); + /* Parcours un contenu binaire à la recherche de motifs. */ void g_engine_backend_run_scan(const GEngineBackend *, GScanContext *); diff --git a/src/analysis/scan/patterns/backends/acism-int.h b/src/analysis/scan/patterns/backends/acism-int.h index a8cfd59..af8080f 100644 --- a/src/analysis/scan/patterns/backends/acism-int.h +++ b/src/analysis/scan/patterns/backends/acism-int.h @@ -36,7 +36,7 @@ -#define __USE_BYTE_FREQ +//#define __USE_BYTE_FREQ //#define __SORT_BEFORE_BITMASK @@ -50,10 +50,14 @@ typedef struct _acism_source_t const uint8_t *atoms; /* Motif remarquable */ size_t len; /* Nombre d'octets considérés */ - patid_t pid; /* Identifiant de suivi */ + uint32_t coverage[2]; /* Départ et quantité de suivis*/ } acism_source_t; +#define SOURCE_COVERAGE_START 0 +#define SOURCE_COVERAGE_COUNT 1 +#define SOURCE_COVERAGE_END 1 + /* Etude de la fréquence des octets pour attribution des codes */ typedef struct _acism_freq_rank_t { @@ -81,8 +85,6 @@ typedef struct _acism_trie_node_t bin_t data; /* Donnée brute représentée */ acism_code_t code; /* Identifiant du noeud */ - patid_t pid; /* Identifiant de suivi */ - acism_code_t min_child_code; /* Plus petit code suivant */ acism_code_t max_child_code; /* Plus grand code suivant */ size_t children_count; /* Nombre de codes suivants */ @@ -127,6 +129,7 @@ typedef union _acism_state_t struct { uint8_t match : 1; /* Correspondance ici */ + uint8_t single_source : 1; /* Unique source à notifier */ uint8_t atom_size; /* Indice de saut */ uint8_t suffix : 1; /* Correspondance ailleurs */ }; @@ -169,7 +172,7 @@ struct _GAcismBackend bitfield_t *bitmap_usage; /* Localisation des usages */ acism_state_t *states; /* Tableau de transitions */ - patid_t *pids; /* Identifiants de motifs */ + uint32_t *coverages; /* Bornes de suivi de positions*/ }; diff --git a/src/analysis/scan/patterns/backends/acism.c b/src/analysis/scan/patterns/backends/acism.c index bceca09..a36e4b7 100644 --- a/src/analysis/scan/patterns/backends/acism.c +++ b/src/analysis/scan/patterns/backends/acism.c @@ -58,10 +58,10 @@ static void g_acism_backend_finalize(GAcismBackend *); size_t g_acism_backend_get_atom_max_size(const GAcismBackend *); /* Intègre un motif limité de contenu à rechercher. */ -static patid_t g_acism_backend_setup_for(GAcismBackend *, GScanContext *, const uint8_t *, size_t); +static void g_acism_backend_setup_for(GAcismBackend *, const uint8_t *, size_t, uint32_t [2]); /* Inscrit dans le moteur une chaîne de caractères à rechercher. */ -static patid_t g_acism_backend_enroll_plain_pattern(GAcismBackend *, GScanContext *, const uint8_t *, size_t); +static bool g_acism_backend_enroll_plain_pattern(GAcismBackend *, const uint8_t *, size_t, uint32_t [2]); #ifdef __USE_BYTE_FREQ @@ -92,9 +92,15 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *); /* Compresse l'arborescence dans un tableau de position. */ static void g_acism_backend_build_interleave_array(GAcismBackend *); +/* Détermine le nombre d'identifiants constitués. */ +static size_t g_acism_backend_count_plain_pattern_ids(const GAcismBackend *); + /* Met en ordre les derniers détails avant un premier scan. */ static void g_acism_backend_warm_up(GAcismBackend *); +/* Récupère les identifiants finaux pour un motif recherché. */ +static patid_t g_acism_backend_build_plain_pattern_id(const GAcismBackend *, const uint32_t [2]); + /* Parcours un contenu binaire à la recherche de motifs. */ static void g_acism_backend_run_scan(const GAcismBackend *, GScanContext *); @@ -142,6 +148,8 @@ static void g_acism_backend_class_init(GAcismBackendClass *klass) backend->get_max_size = (get_backend_atom_max_size_fc)g_acism_backend_get_atom_max_size; backend->enroll_plain = (enroll_plain_into_backend_fc)g_acism_backend_enroll_plain_pattern; backend->warm_up = (warm_up_backend_fc)g_acism_backend_warm_up; + backend->build_id = (build_backend_plain_pattern_id_fc)g_acism_backend_build_plain_pattern_id; + backend->count_ids = (count_backend_plain_pattern_ids_fc)g_acism_backend_count_plain_pattern_ids; backend->run_scan = (run_backend_scan_fc)g_acism_backend_run_scan; backend->output = (output_backend_stats_fc)g_acism_backend_output_stats; @@ -229,8 +237,8 @@ static void g_acism_backend_finalize(GAcismBackend *backend) if (backend->states != NULL) free(backend->states); - if (backend->pids != NULL) - free(backend->pids); + if (backend->coverages != NULL) + free(backend->coverages); G_OBJECT_CLASS(g_acism_backend_parent_class)->finalize(G_OBJECT(backend)); @@ -292,9 +300,9 @@ size_t g_acism_backend_get_atom_max_size(const GAcismBackend *backend) /****************************************************************************** * * * Paramètres : backend = moteur de recherche à préparer. * -* context = contexte de l'analyse à mener. * -* plain = chaîne de caractères classique à intégrer. * +* pattern = chaîne de caractères classique à intégrer. * * len = taille de cette chaîne. * +* tmp_id = identifiants temporaires vers le motif. [OUT] * * * * Description : Intègre un motif limité de contenu à rechercher. * * * @@ -304,15 +312,12 @@ size_t g_acism_backend_get_atom_max_size(const GAcismBackend *backend) * * ******************************************************************************/ -static patid_t g_acism_backend_setup_for(GAcismBackend *backend, GScanContext *context, const uint8_t *pattern, size_t len) +static void g_acism_backend_setup_for(GAcismBackend *backend, const uint8_t *pattern, size_t len, uint32_t tmp_id[2]) { - patid_t result; /* Identifiant à retourner */ size_t i; /* Boucle de parcours */ int ret; /* Bilan d'une comparaison */ acism_source_t *source; /* Définition à mémoriser */ - result = INVALID_PATTERN_ID; - /*Recherche d'un motif déjà sollicité */ /** @@ -332,15 +337,19 @@ static patid_t g_acism_backend_setup_for(GAcismBackend *backend, GScanContext *c if (ret == 0) { - result = source->pid; + tmp_id[0] = i; + tmp_id[1] = source->coverage[SOURCE_COVERAGE_COUNT]; + + source->coverage[SOURCE_COVERAGE_COUNT]++; break; + } } /* Introduction d'un nouveau motif au besoin */ - if (result == INVALID_PATTERN_ID) + if (i == backend->sources_count) { backend->sources = realloc(backend->sources, ++backend->sources_count * sizeof(acism_source_t)); @@ -349,8 +358,10 @@ static patid_t g_acism_backend_setup_for(GAcismBackend *backend, GScanContext *c source->atoms = pattern; source->len = len; - result = g_scan_context_get_new_pattern_id(context); - source->pid = result; + source->coverage[SOURCE_COVERAGE_COUNT] = 1; + + tmp_id[0] = i; + tmp_id[1] = 0; backend->nchars += len; @@ -361,17 +372,15 @@ static patid_t g_acism_backend_setup_for(GAcismBackend *backend, GScanContext *c } - return result; - } /****************************************************************************** * * * Paramètres : backend = moteur de recherche à manipuler. * -* context = contexte de l'analyse à mener. * * plain = chaîne de caractères classique à intégrer. * * len = taille de cette chaîne. * +* tmp_id = identifiants temporaires vers le motif. [OUT] * * * * Description : Inscrit dans le moteur une chaîne de caractères à rechercher.* * * @@ -381,12 +390,14 @@ static patid_t g_acism_backend_setup_for(GAcismBackend *backend, GScanContext *c * * ******************************************************************************/ -static patid_t g_acism_backend_enroll_plain_pattern(GAcismBackend *backend, GScanContext *context, const uint8_t *plain, size_t len) +static bool g_acism_backend_enroll_plain_pattern(GAcismBackend *backend, const uint8_t *plain, size_t len, uint32_t tmp_id[2]) { - patid_t result; /* Identifiant à retourner */ + bool result; /* Bilan à retourner */ assert(len <= ACSIM_ATOM_SIZE); + result = true; + /** * Le traitement différé des chaînes à rechercher permet deux choses : * - la construction d'une table de permutation ; @@ -405,7 +416,7 @@ static patid_t g_acism_backend_enroll_plain_pattern(GAcismBackend *backend, GSca * moindre coût un jour. */ - result = g_acism_backend_setup_for(backend, context, plain, len); + g_acism_backend_setup_for(backend, plain, len, tmp_id); return result; @@ -505,6 +516,7 @@ static void g_acism_backend_define_codes(GAcismBackend *backend) static void g_acism_backend_build_trie(GAcismBackend *backend) { size_t i; /* Boucle de parcours #1 */ + uint32_t current_start; /* Indice de gestionnaire */ acism_trie_node_t *next; /* Prochain noeud disponible */ acism_trie_node_t *node; /* Tête de parcours */ acism_source_t *source; /* Définition à mémoriser */ @@ -520,6 +532,8 @@ static void g_acism_backend_build_trie(GAcismBackend *backend) backend->nodes[i].max_child_code = MIN_ACISM_CODE; } + current_start = 0; + next = backend->nodes + 1; for (i = 0; i < backend->sources_count; i++) @@ -528,6 +542,15 @@ static void g_acism_backend_build_trie(GAcismBackend *backend) source = &backend->sources[i]; + /* Mise à jour de la couverture des gestionnaires de suivi */ + + source->coverage[SOURCE_COVERAGE_START] = current_start; + source->coverage[SOURCE_COVERAGE_END] += current_start; + + current_start = source->coverage[SOURCE_COVERAGE_END]; + + /* Parcours des noeuds contenus */ + for (k = 0; k < source->len && node->child != NULL; k++) { #ifdef __USE_BYTE_FREQ @@ -1026,6 +1049,8 @@ static void g_acism_backend_build_interleave_array(GAcismBackend *backend) size_t i; /* Boucle de parcours #1 */ acism_trie_node_t *node; /* Noeud à transcrire */ acism_state_t *base; /* Base d'une série de cellules*/ + uint32_t *coverage; /* Couverture des inscriptions */ + acism_source_t *source; /* Définition originelle */ acism_trie_node_t *iter; /* Sous-noeud à inscrire #2 */ acism_trie_node_t *child; /* Sous-noeud à inscrire #3 */ uint16_t offset; /* Décalage local */ @@ -1033,7 +1058,7 @@ static void g_acism_backend_build_interleave_array(GAcismBackend *backend) maxsize = get_bit_field_size(backend->bitmap_usage); backend->states = calloc(maxsize, sizeof(acism_state_t)); - backend->pids = calloc(maxsize, sizeof(patid_t)); + backend->coverages = calloc(maxsize, 2 * sizeof(uint32_t)); for (i = 0; i < backend->nodes_used; i++) { @@ -1045,10 +1070,15 @@ static void g_acism_backend_build_interleave_array(GAcismBackend *backend) if (node->matched_atom > 0) { + source = &backend->sources[node->matched_atom - 1]; + base[0].match = 1; + base[0].single_source = source->coverage[SOURCE_COVERAGE_COUNT] == 1 ? 1 : 0; base[0].atom_size = backend->sources[node->matched_atom - 1].len - 1; + coverage = &backend->coverages[node->state_index * 2]; - backend->pids[node->state_index] = backend->sources[node->matched_atom - 1].pid; + coverage[SOURCE_COVERAGE_START] = source->coverage[SOURCE_COVERAGE_START]; + coverage[SOURCE_COVERAGE_COUNT] = source->coverage[SOURCE_COVERAGE_COUNT]; for (iter = node->parent->suffix_link; iter != NULL; iter = iter->suffix_link) { @@ -1065,6 +1095,7 @@ static void g_acism_backend_build_interleave_array(GAcismBackend *backend) } } + base[0].index = i == 0 ? 0 : node->suffix_link->state_index; for (child = node->child; child != NULL; child = child->sibling) @@ -1111,6 +1142,10 @@ static void g_acism_backend_warm_up(GAcismBackend *backend) /** * Construit une arborescence de lecture à partir des différents * octets présents dans les motifs. + * + * Les couvertures des futurs tableaux de correspondances sont + * établies au passage, ouvrant la voie aux définitions d'identifiant + * pour les motifs enregistrés. */ g_acism_backend_build_trie(backend); @@ -1134,6 +1169,58 @@ static void g_acism_backend_warm_up(GAcismBackend *backend) /****************************************************************************** * * * Paramètres : backend = moteur de recherche à manipuler. * +* tmp_id = identifiants temporaires vers le motif. [OUT] * +* * +* Description : Récupère les identifiants finaux pour un motif recherché. * +* * +* Retour : Identifiant constitué ou INVALID_PATTERN_ID en cas d'échec. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static patid_t g_acism_backend_build_plain_pattern_id(const GAcismBackend *backend, const uint32_t tmp_id[2]) +{ + patid_t result; /* Identifiant à retourner */ + acism_source_t *source; /* Motif d'origine concerné */ + + source = backend->sources + tmp_id[0]; + + result = source->coverage[SOURCE_COVERAGE_START] + tmp_id[1]; + + assert(result < source->coverage[SOURCE_COVERAGE_END]); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * +* * +* Description : Détermine le nombre d'identifiants constitués. * +* * +* Retour : Quantité de gestionnaires de suivi à prévoir. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static size_t g_acism_backend_count_plain_pattern_ids(const GAcismBackend *backend) +{ + size_t result; /* Quantité à retourner */ + + result = backend->sources[backend->sources_count -1].coverage[SOURCE_COVERAGE_END]; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : backend = moteur de recherche à manipuler. * * context = lieu d'enregistrement des résultats. * * * * Description : Parcours un contenu binaire à la recherche de motifs. * @@ -1150,17 +1237,20 @@ static void g_acism_backend_run_scan(const GAcismBackend *backend, GScanContext phys_t dlen; /* Quantité de données */ vmpa2t pos; /* Point de départ ciblé */ const bin_t *data; /* Données à analyser */ + GUMemSlice **matches; /* Zones d'enregistrements */ #ifdef __USE_BYTE_FREQ acism_code_t codes_for_bytes[256]; /* Copie des codes d'accès */ #endif acism_state_t *root; /* Racine de l'arborescence */ - patid_t *pids; /* Identifiants de motifs */ + uint32_t *coverages; /* Bornes de suivi de positions*/ unsigned int state; /* Tête de lecture courante */ phys_t i; /* Boucle de parcours #1 */ acism_code_t code; /* Code du caractère courant */ unsigned int next; /* Prochaine tête à valider */ acism_state_t next_state; /* Prochaine tête à valider */ - unsigned int iter; /* Boucle de parcours #2 */ + uint32_t final_k; /* Dernier indice à traiter */ + uint32_t k; /* Boucle de parcours #2 */ + unsigned int iter; /* Boucle de parcours #3 */ acism_state_t test_state; /* Test de validité alternative*/ acism_state_t sub_state; /* Test de validité alternative*/ @@ -1171,6 +1261,8 @@ static void g_acism_backend_run_scan(const GAcismBackend *backend, GScanContext g_binary_content_compute_start_pos(content, &pos); data = g_binary_content_get_raw_access(content, &pos, dlen); + matches = g_scan_context_get_match_storages(context, (size_t []){ 0 }); + /* Suivi via l'arborescence aplatie */ #ifdef __USE_BYTE_FREQ @@ -1180,7 +1272,7 @@ static void g_acism_backend_run_scan(const GAcismBackend *backend, GScanContext root = backend->states; if (root == NULL) goto done; - pids = backend->pids; + coverages = backend->coverages; state = ROOT_STATE_INDEX; @@ -1217,9 +1309,19 @@ static void g_acism_backend_run_scan(const GAcismBackend *backend, GScanContext if (next_state.match) { - g_scan_context_register_atom_match(context, - pids[next], - i - next_state.atom_size); + k = coverages[next * 2 + SOURCE_COVERAGE_START]; + + if (next_state.single_source) + g_umem_slice_put_uint64(matches[k], i - next_state.atom_size); + + else + { + final_k = coverages[next * 2 + SOURCE_COVERAGE_END]; + + for (; k < final_k; k++) + g_umem_slice_put_uint64(matches[k], i - next_state.atom_size); + + } if (next_state.suffix) { @@ -1235,9 +1337,19 @@ static void g_acism_backend_run_scan(const GAcismBackend *backend, GScanContext { assert(sub_state.atom_size < next_state.atom_size); - g_scan_context_register_atom_match(context, - pids[test_state.index], - i - sub_state.atom_size); + k = coverages[test_state.index * 2 + SOURCE_COVERAGE_START]; + + if (sub_state.single_source) + g_umem_slice_put_uint64(matches[k], i - sub_state.atom_size); + + else + { + final_k = coverages[test_state.index * 2 + SOURCE_COVERAGE_END]; + + for (; k < final_k; k++) + g_umem_slice_put_uint64(matches[k], i - sub_state.atom_size); + + } } diff --git a/src/analysis/scan/patterns/backends/bitap.c b/src/analysis/scan/patterns/backends/bitap.c index 99e16e5..af50c6d 100644 --- a/src/analysis/scan/patterns/backends/bitap.c +++ b/src/analysis/scan/patterns/backends/bitap.c @@ -517,7 +517,7 @@ static patid_t enroll_plain_pattern_avx2(GBitapBackend *backend, GScanContext *c last->m[n] = plen; - result = g_scan_context_get_new_pattern_id(context); + result = 0; // FIXME g_scan_context_get_new_pattern_id(context); last->found_id[n] = result; @@ -934,9 +934,11 @@ static void run_scan_avx2(const GBitapBackend *backend, GScanContext *context, c { //assert((i + 1) >= group.m[j]); + /** TODO : update call g_scan_context_register_atom_match(context, group.found_id[j], (iter - data) + 1 - group.m[j]); + **/ } @@ -1108,9 +1110,11 @@ static void run_scan_avx2(const GBitapBackend *backend, GScanContext *context, c { //assert((i + 1) >= group.m[j]); + /** TODO : update call g_scan_context_register_atom_match(context, group.found_id[j], (iter - data) + 1 - group.m[j]); + **/ } @@ -1617,7 +1621,7 @@ static patid_t enroll_plain_pattern_avx512(GBitapBackend *backend, GScanContext last->m[n] = plen; - result = g_scan_context_get_new_pattern_id(context); + result = 0; // FIXME g_scan_context_get_new_pattern_id(context); last->found_id[n] = result; @@ -1925,9 +1929,11 @@ static void run_scan_avx512(const GBitapBackend *backend, GScanContext *context, { //assert((i + 1) >= group.m[j]); + /** TODO : update call g_scan_context_register_atom_match(context, group.found_id[j], (iter - data) + 1 - group.m[j]); + **/ } @@ -1946,9 +1952,11 @@ static void run_scan_avx512(const GBitapBackend *backend, GScanContext *context, { //assert((i + 1) >= group.m[j]); + /** TODO : update call g_scan_context_register_atom_match(context, _group->found_id[j], (iter - data) + 1 - _group->m[j]); + **/ } diff --git a/src/analysis/scan/patterns/patid.h b/src/analysis/scan/patterns/patid.h new file mode 100644 index 0000000..e8b7eee --- /dev/null +++ b/src/analysis/scan/patterns/patid.h @@ -0,0 +1,36 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * patid.h - prototypes pour la définition d'un identifiant de motif partiel + * + * Copyright (C) 2023 Cyrille Bagard + * + * This file is part of Chrysalide. + * + * Chrysalide is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3 of the License, or + * (at your option) any later version. + * + * Chrysalide is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Foobar. If not, see <http://www.gnu.org/licenses/>. + */ + + +#ifndef _ANALYSIS_SCAN_PATTERNS_PATID_H +#define _ANALYSIS_SCAN_PATTERNS_PATID_H + + + +/* Identifiant de motif intégré */ +typedef uint32_t patid_t; + +#define INVALID_PATTERN_ID 0xffffffff + + + +#endif /* _ANALYSIS_SCAN_PATTERNS_PATID_H */ diff --git a/src/analysis/scan/patterns/token.c b/src/analysis/scan/patterns/token.c index e5eb287..76a5e66 100644 --- a/src/analysis/scan/patterns/token.c +++ b/src/analysis/scan/patterns/token.c @@ -248,7 +248,6 @@ bool g_bytes_token_is_private(const GBytesToken *token) /****************************************************************************** * * * Paramètres : token = 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). * * * @@ -260,13 +259,37 @@ bool g_bytes_token_is_private(const GBytesToken *token) * * ******************************************************************************/ -bool g_bytes_token_enroll(GBytesToken *token, GScanContext *context, GEngineBackend *backend, size_t maxsize) +bool g_bytes_token_enroll(GBytesToken *token, GEngineBackend *backend, size_t maxsize) { bool result; /* Statut à retourner */ token->need_backward = g_scan_token_node_setup_tree(token->root); - result = g_scan_token_node_enroll(token->root, context, backend, maxsize, &token->slow); + result = g_scan_token_node_enroll(token->root, backend, maxsize, &token->slow); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : token = définition de la bribe à peaufiner. * +* backend = moteur de recherche à préchauffer. * +* * +* Description : Récupère les identifiants finaux pour un motif recherché. * +* * +* Retour : Bilan de l'opération à renvoyer. * +* * +* Remarques : - * +* * +******************************************************************************/ + +bool g_bytes_token_build_id(GBytesToken *token, GEngineBackend *backend) +{ + bool result; /* Statut à retourner */ + + result = g_scan_token_node_build_id(token->root, backend); return result; @@ -276,8 +299,6 @@ bool g_bytes_token_enroll(GBytesToken *token, GScanContext *context, GEngineBack /****************************************************************************** * * * Paramètres : token = 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. * * * * Description : Transforme les correspondances locales en trouvailles. * @@ -288,60 +309,98 @@ bool g_bytes_token_enroll(GBytesToken *token, GScanContext *context, GEngineBack * * ******************************************************************************/ -void g_bytes_token_check(const GBytesToken *token, GScanContext *context, GBinContent *content, pending_matches_t *matches) +void g_bytes_token_check(const GBytesToken *token, GScanBytesMatches *matches) { - size_t p; /* Boucle de parcours #3 */ - match_area_t *pending; /* Correspondance à traiter */ + scan_node_check_params_t params; /* Rassemblement de paramètres */ + vmpa2t start; /* Point de début du contenu */ + vmpa2t end; /* Point de fin du contenu */ + match_area_t *area; /* Correspondance à valider */ + match_area_t *next; /* Correspondance suivante */ vmpa2t pos; /* Tête de lecture */ const bin_t *byte; /* Octet à valider */ - g_scan_token_node_check_forward(token->root, context, content, matches); + /* Définition d'un contexte */ + + params.context = g_scan_bytes_matches_get_context(matches); + params.content = g_scan_context_get_content(params.context); + params.allocator = g_umem_slice_new(sizeof(match_area_t)); + + g_binary_content_compute_start_pos(params.content, &start); + g_binary_content_compute_end_pos(params.content, &end); + + params.content_start = start.physical; + params.content_end = end.physical; + + // offset + + params.initialized = false; + + params.main_areas = NULL; + params.main_count = 0; + + params.created_areas = NULL; + params.created_count = 0; + + params.kept_areas = NULL; + params.kept_count = 0; + + /* Lancement des analyses */ + + g_scan_token_node_check_forward(token->root, ¶ms); if (token->need_backward) - g_scan_token_node_check_backward(token->root, context, content, matches); + g_scan_token_node_check_backward(token->root, ¶ms); - sort_and_filter_pending_matches(matches); + // REMME ? sort_and_filter_pending_matches(matches); if (token->fullword) { - reset_pending_matches_ttl(matches); - - for (p = 0; p < matches->used; p++) + for_each_match_area_safe(area, ¶ms.main_areas, next) { - pending = &matches->areas[p]; - /* Validation de l'octet précédent, s'il existe */ - if (pending->start > matches->content_start) + if (area->start > params.content_start) { - init_vmpa(&pos, pending->start - 1, VMPA_NO_VIRTUAL); + init_vmpa(&pos, area->start - 1, VMPA_NO_VIRTUAL); - byte = g_binary_content_get_raw_access(content, &pos, 1); + byte = g_binary_content_get_raw_access(params.content, &pos, 1); if (isalnum(*byte)) + { + del_match_area(area, ¶ms.main_areas); + assert(¶ms.main_count > 0); + params.main_count--; continue; + } } /* Validation de l'octet suivant, s'il existe */ - if (pending->end < matches->content_end) + if (area->end < params.content_end) { - init_vmpa(&pos, pending->end, VMPA_NO_VIRTUAL); + init_vmpa(&pos, area->end, VMPA_NO_VIRTUAL); - byte = g_binary_content_get_raw_access(content, &pos, 1); + byte = g_binary_content_get_raw_access(params.content, &pos, 1); if (isalnum(*byte)) + { + del_match_area(area, ¶ms.main_areas); + assert(¶ms.main_count > 0); + params.main_count--; continue; + } } - keep_pending_match(pending); - } - purge_pending_matches(matches); - } + g_scan_bytes_matches_set_list(matches, params.main_areas, params.main_count); + + g_object_unref(G_OBJECT(params.context)); + g_object_unref(G_OBJECT(params.content)); + //g_object_unref(G_OBJECT(params.allocator)); + } @@ -394,17 +453,20 @@ char *g_bytes_token_get_modifier_path(const GBytesToken *token, size_t index) static void g_bytes_token_output_to_text(const GBytesToken *pattern, GScanContext *context, int fd) { - const GScanMatch **matches; /* Correspondances établies */ - size_t count; /* Quantité de cette liste */ - size_t i; /* Boucle de parcours */ + GScanMatches *matches; /* Correspondances établies */ if (g_bytes_token_is_private(pattern)) return; - matches = g_scan_context_get_full_matches(context, G_SEARCH_PATTERN(pattern), &count); + matches = g_scan_context_get_full_matches(context, G_SEARCH_PATTERN(pattern)); - for (i = 0; i < count; i++) - g_scan_match_output_to_text(matches[i], fd); + if (matches != NULL) + { + g_scan_matches_output_to_text(matches, fd); + + g_object_unref(G_OBJECT(matches)); + + } } @@ -427,57 +489,19 @@ static void g_bytes_token_output_to_text(const GBytesToken *pattern, GScanContex static void g_bytes_token_output_to_json(const GBytesToken *pattern, GScanContext *context, const sized_string_t *padding, unsigned int level, int fd) { - unsigned int i; /* Boucle de parcours #1 */ - const GScanMatch **matches; /* Correspondances établies */ - size_t count; /* Quantité de cette liste */ - char value[ULLONG_MAXLEN]; /* Impression de la position */ - int ret; /* Bilan d'une conversion */ - size_t k; /* Boucle de parcours #2 */ - bool trailing; /* Virgule finale */ + GScanMatches *matches; /* Correspondances établies */ if (g_bytes_token_is_private(pattern)) return; - matches = g_scan_context_get_full_matches(context, G_SEARCH_PATTERN(pattern), &count); - - /* Nombre de correspondances */ - - for (i = 0; i < level; i++) - write(fd, padding->data, padding->len); + matches = g_scan_context_get_full_matches(context, G_SEARCH_PATTERN(pattern)); - write(fd, "\"match_count\": ", 15); - - ret = snprintf(value, ULLONG_MAXLEN, "%zu", count); - - if (ret > 0) - write(fd, value, ret); - - else - { - log_simple_message(LMT_EXT_ERROR, "Error while converting value!"); - write(fd, "null", 4); - } - - write(fd, ",\n", 2); - - /* Détail des correspondances */ - - for (i = 0; i < level; i++) - write(fd, padding->data, padding->len); - - write(fd, "\"matches\": [\n", 13); - - for (k = 0; k < count; k++) + if (matches != NULL) { - trailing = ((k + 1) < count); - - g_scan_match_output_to_json(matches[k], padding, level + 1, fd, trailing); + g_scan_matches_output_to_json(matches, padding, level, fd); + + g_object_unref(G_OBJECT(matches)); } - for (i = 0; i < level; i++) - write(fd, padding->data, padding->len); - - write(fd, "]\n", 2); - } diff --git a/src/analysis/scan/patterns/token.h b/src/analysis/scan/patterns/token.h index 2816bf8..3bc5cb7 100644 --- a/src/analysis/scan/patterns/token.h +++ b/src/analysis/scan/patterns/token.h @@ -30,7 +30,7 @@ #include "backend.h" #include "tokens/node.h" -#include "../matches/pending.h" +#include "../matches/bytes.h" @@ -59,10 +59,13 @@ bool g_bytes_token_target_fullword(const GBytesToken *); bool g_bytes_token_is_private(const GBytesToken *); /* Inscrit la définition d'un motif dans un moteur de recherche. */ -bool g_bytes_token_enroll(GBytesToken *, GScanContext *, GEngineBackend *, size_t); +bool g_bytes_token_enroll(GBytesToken *, GEngineBackend *, size_t); + +/* Récupère les identifiants finaux pour un motif recherché. */ +bool g_bytes_token_build_id(GBytesToken *, GEngineBackend *); /* Transforme les correspondances locales en trouvailles. */ -void g_bytes_token_check(const GBytesToken *, GScanContext *, GBinContent *, pending_matches_t *); +void g_bytes_token_check(const GBytesToken *, GScanBytesMatches *); /* Retrouve l'origine d'une correspondance à partir d'un indice. */ char *g_bytes_token_get_modifier_path(const GBytesToken *, size_t); diff --git a/src/analysis/scan/patterns/tokens/atom.c b/src/analysis/scan/patterns/tokens/atom.c index 01da28d..580ad30 100644 --- a/src/analysis/scan/patterns/tokens/atom.c +++ b/src/analysis/scan/patterns/tokens/atom.c @@ -26,6 +26,7 @@ #include <assert.h> #include <malloc.h> +#include <math.h> @@ -168,6 +169,8 @@ void find_best_atom(const sized_binary_t *raw, size_t maxsize, tracked_scan_atom atom->len = raw->len; atom->rem = 0; + atom->fast_check = true; + if (letters != NULL) { *letters = 0; @@ -240,11 +243,16 @@ void find_best_atom(const sized_binary_t *raw, size_t maxsize, tracked_scan_atom atom->rem = raw->len - atom->pos - maxsize; + atom->fast_check = false; + if (letters != NULL) *letters = best_letters; } + assert((atom->fast_check && atom->pos == 0 && atom->rem == 0) + || (!atom->fast_check && (atom->pos != 0 || atom->rem != 0))); + } @@ -340,11 +348,11 @@ sized_binary_t *make_atoms_case_insensitive(const sized_binary_t *src, const tra /****************************************************************************** * * -* Paramètres : byte = octet partiel à interpréter. * -* mask = valeur du masque à appliquer. * +* Paramètres : bytes = octets partiels avec leur masque à interpréter. * +* len = quantité d'octets à interpréter. * * produced = nombre de contenus générés. [OUT] * * * -* Description : Etablit la liste des cas de figures avec un octet partiel. * +* Description : Etablit la liste des cas de figures avec des octets partiels.* * * * Retour : Liste de toutes les combinaisons possibles. * * * @@ -352,28 +360,66 @@ sized_binary_t *make_atoms_case_insensitive(const sized_binary_t *src, const tra * * ******************************************************************************/ -sized_binary_t *make_atoms_from_masked_byte(bin_t value, bin_t mask, size_t *produced) +sized_binary_t *make_atoms_from_masked_bytes(const masked_byte_t *bytes, size_t len, size_t *produced) { sized_binary_t *result; /* Liste à retourner */ + size_t seq_len; /* Taille de séquence retenue */ + size_t repeat_times; /* Répétitions pour remplissage*/ + sized_binary_t *maxiter; /* Borne de fin de parcours */ size_t i; /* Boucle de parcours #1 */ + sized_binary_t *iter; /* Boucle de parcours #2 */ + size_t j; /* Boucle de parcours #3 */ + size_t k; /* Boucle de parcours #4 */ + + seq_len = (len > MASK_MAX_LEN_FOR_ATOMS ? MASK_MAX_LEN_FOR_ATOMS : len); + + /** + * Si l'usage de la fonction pow() disparaît, la bibliothèque m + * peut être retirée de libchrysacore_la_LDFLAGS dans le Makefile + * principal. + */ + repeat_times = pow(16, seq_len - 1); - *produced = 16; + *produced = 16 * repeat_times; /* Création du réceptacle */ - result = malloc(16 * sizeof(tracked_scan_atom_t)); + result = malloc(*produced * sizeof(tracked_scan_atom_t)); + + maxiter = result + *produced; /* Remplissage */ - for (i = 0; i < 16; i++) + for (i = 0; i < seq_len; i++) { - result[i].data = malloc(1); - result[i].len = 1; + for (iter = result; iter < maxiter; ) + { + for (j = 0; j < 16; j++) + { + assert(bytes[i].mask == 0x0f || bytes[i].mask == 0xf0); - if (mask == 0x0f) - result[i].data[0] = value | (i << 4); - else - result[i].data[0] = value | i; + for (k = 0; k < repeat_times; k++) + { + if (i == 0) + { + iter->data = malloc(seq_len); + iter->len = seq_len; + } + + if (bytes[i].mask == 0x0f) + iter->data[i] = bytes[i].value | (j << 4); + else + iter->data[i] = bytes[i].value | j; + + iter++; + + } + + } + + } + + repeat_times /= 16; } @@ -385,11 +431,10 @@ sized_binary_t *make_atoms_from_masked_byte(bin_t value, bin_t mask, size_t *pro /****************************************************************************** * * * Paramètres : raw = définition de la bribe à enregistrer. * -* context = contexte de l'analyse à mener. * * backend = moteur de recherche à préchauffer. * * atom = informations de suivi constituées. [OUT] * * * -* Description : Enregistre l'atome déterminé d'une série d'octets. * +* Description : Amorce l'insertion de l'atome déterminé d'une série d'octets.* * * * Retour : Bilan de l'opération à renvoyer. * * * @@ -397,14 +442,38 @@ sized_binary_t *make_atoms_from_masked_byte(bin_t value, bin_t mask, size_t *pro * * ******************************************************************************/ -bool enroll_prepared_atom(const sized_binary_t *raw, GScanContext *context, GEngineBackend *backend, tracked_scan_atom_t *atom) +bool enroll_prepared_atom(const sized_binary_t *raw, GEngineBackend *backend, tracked_scan_atom_t *atom) { bool result; /* Statut à retourner */ const bin_t *data; /* Données à rechercher */ data = raw->data + atom->pos; - atom->pid = g_engine_backend_enroll_plain_pattern(backend, context, data, atom->len); + result = g_engine_backend_enroll_plain_pattern(backend, data, atom->len, atom->tmp_id); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : atom = informations de suivi constituées. [OUT] * +* 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 : - * +* * +******************************************************************************/ + +bool build_atom_pattern_id(tracked_scan_atom_t *atom, GEngineBackend *backend) +{ + bool result; /* Statut à retourner */ + + atom->pid = g_engine_backend_build_plain_pattern_id(backend, atom->tmp_id); result = (atom->pid != INVALID_PATTERN_ID); diff --git a/src/analysis/scan/patterns/tokens/atom.h b/src/analysis/scan/patterns/tokens/atom.h index 2fbc19e..1d912d7 100644 --- a/src/analysis/scan/patterns/tokens/atom.h +++ b/src/analysis/scan/patterns/tokens/atom.h @@ -29,7 +29,6 @@ #include "../backend.h" -#include "../../context.h" #include "../../../../arch/vmpa.h" #include "../../../../common/bits.h" #include "../../../../common/szstr.h" @@ -43,11 +42,14 @@ typedef struct _tracked_scan_atom_t phys_t len; /* Taille de ladite sélection */ phys_t rem; /* Reste après l'atome */ + bool fast_check; /* Besoin de vérifications ? */ + + uint32_t tmp_id[2]; /* Couple d'identifiants temp. */ + patid_t pid; /* Identifiant de la bribe */ } tracked_scan_atom_t; - /* Note l'intêret de rechercher un octet particulier. */ int rate_byte_quality(bin_t, bitfield_t *, size_t *); @@ -60,11 +62,24 @@ void find_best_atom(const sized_binary_t *, size_t , tracked_scan_atom_t *, size /* Etablit la liste des cas de figures ignorant la casse. */ sized_binary_t *make_atoms_case_insensitive(const sized_binary_t *, const tracked_scan_atom_t *, size_t); -/* Etablit la liste des cas de figures avec un octet partiel. */ -sized_binary_t *make_atoms_from_masked_byte(bin_t, bin_t, size_t *); +/* 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; + +#define MASK_MAX_LEN_FOR_ATOMS 2 + +/* Etablit la liste des cas de figures avec des octets partiels. */ +sized_binary_t *make_atoms_from_masked_bytes(const masked_byte_t *, size_t, size_t *); + +/* Amorce l'insertion de l'atome déterminé d'une série d'octets. */ +bool enroll_prepared_atom(const sized_binary_t *, GEngineBackend *, tracked_scan_atom_t *); -/* Enregistre l'atome déterminé d'une série d'octets. */ -bool enroll_prepared_atom(const sized_binary_t *, GScanContext *, GEngineBackend *, tracked_scan_atom_t *); +/* Récupère un identifiant final pour un atome d'octets. */ +bool build_atom_pattern_id(tracked_scan_atom_t *, GEngineBackend *); diff --git a/src/analysis/scan/patterns/tokens/node-int.h b/src/analysis/scan/patterns/tokens/node-int.h index 091a5be..520e2a4 100644 --- a/src/analysis/scan/patterns/tokens/node-int.h +++ b/src/analysis/scan/patterns/tokens/node-int.h @@ -28,9 +28,9 @@ #include "node.h" -#include "offset.h" - +/* Communique l'intérêt d'un noeud au sein d'une analyse. */ +typedef float (* compute_scan_token_node_weight_fc) (const GScanTokenNode *); /* Prend acte d'une nouvelle propriété pour le noeud. */ typedef void (* apply_scan_token_node_flags_fc) (GScanTokenNode *, ScanTokenNodeFlags); @@ -38,23 +38,30 @@ typedef void (* apply_scan_token_node_flags_fc) (GScanTokenNode *, ScanTokenNode /* Noeuds clefs de l'arborescence mise en place */ typedef struct _scan_tree_points_t { - GScanTokenNode *first_node; /* Premier noeud de traitement */ - GScanTokenNode *last_node; /* Dernier noeud de traitement */ - GScanTokenNode *first_plain; /* Premier noeud textuel */ GScanTokenNode *best_masked; /* Noeud masqué le plus long */ } scan_tree_points_t; - /* Parcourt une arborescence de noeuds et y relève des éléments. */ typedef void (* visit_scan_token_node_fc) (GScanTokenNode *, scan_tree_points_t *); /* Inscrit la définition d'un motif dans un moteur de recherche. */ -typedef bool (* enroll_scan_token_node_fc) (GScanTokenNode *, GScanContext *, GEngineBackend *, size_t, size_t *); +typedef bool (* enroll_scan_token_node_fc) (GScanTokenNode *, GEngineBackend *, size_t, size_t *); + +/* Récupère un identifiant final pour un atome d'octets. */ +typedef bool (* build_scan_token_node_id_fc) (GScanTokenNode *, GEngineBackend *); + +typedef enum _TokenNodeCheckFlags +{ + TNCF_UPDATE_IN_PLACE = (1 << 0), /* Actualisation de l'entrée */ + TNCF_CREATE_NEW = (1 << 1), /* Allocation de positions */ + TNCF_KEEP_DISCARDED = (1 << 2), /* Inversion des résultats */ + +} TokenNodeCheckFlags; /* Transforme les correspondances locales en trouvailles. */ -typedef void (* check_scan_token_node_fc) (const GScanTokenNode *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +typedef void (* check_scan_token_node_fc) (const GScanTokenNode *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); /* Décomposition d'un motif de recherche en atomes (instance) */ @@ -71,10 +78,12 @@ struct _GScanTokenNodeClass { GObjectClass parent; /* A laisser en premier */ + compute_scan_token_node_weight_fc compute_weight; /* Evaluation */ + visit_scan_token_node_fc visit; /* Phase de répérage initial */ apply_scan_token_node_flags_fc apply; /* Prise en compte de fanions */ - visit_scan_token_node_fc visit; /* Phase de répérage initial */ enroll_scan_token_node_fc enroll; /* Inscription d'un motif */ + build_scan_token_node_id_fc build_id; /* Récupération d'identifiant */ check_scan_token_node_fc check_forward; /* Conversion en trouvailles */ check_scan_token_node_fc check_backward;/* Conversion en trouvailles */ @@ -86,13 +95,13 @@ struct _GScanTokenNodeClass void g_scan_token_node_visit(GScanTokenNode *, scan_tree_points_t *); /* Inscrit la définition d'un motif dans un moteur de recherche. */ -bool _g_scan_token_node_enroll(GScanTokenNode *, GScanContext *, GEngineBackend *, size_t, size_t *); +bool _g_scan_token_node_enroll(GScanTokenNode *, GEngineBackend *, size_t, size_t *); /* Transforme les correspondances locales en trouvailles. */ -void _g_scan_token_node_check_forward(const GScanTokenNode *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +void _g_scan_token_node_check_forward(const GScanTokenNode *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); /* Transforme les correspondances locales en trouvailles. */ -void _g_scan_token_node_check_backward(const GScanTokenNode *, GScanContext *, GBinContent *, pending_matches_t *, node_search_offset_t *, bool, bool *); +void _g_scan_token_node_check_backward(const GScanTokenNode *, scan_node_check_params_t *, TokenNodeCheckFlags, bool *); diff --git a/src/analysis/scan/patterns/tokens/node.c b/src/analysis/scan/patterns/tokens/node.c index 71fcf05..767cc6d 100644 --- a/src/analysis/scan/patterns/tokens/node.c +++ b/src/analysis/scan/patterns/tokens/node.c @@ -143,6 +143,38 @@ static void g_scan_token_node_finalize(GScanTokenNode *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 : - * +* * +******************************************************************************/ + +float g_scan_token_node_compute_weight_for_scan(const GScanTokenNode *node) +{ + float result; /* Valeur à retourner */ + GScanTokenNodeClass *class; /* Classe de l'instance */ + + class = G_SCAN_TOKEN_NODE_GET_CLASS(node); + + if (class->compute_weight != NULL) + result = class->compute_weight(node); + else + result = 0; + + return result; + +} + + + + + +/****************************************************************************** +* * +* Paramètres : node = noeud de motif à consulter. * +* * * Description : Indique les propriétés particulières d'un noeud d'analyse. * * * * Retour : Propriétés particulières associées au noeud. * @@ -206,15 +238,6 @@ void g_scan_token_node_visit(GScanTokenNode *node, scan_tree_points_t *points) { GScanTokenNodeClass *class; /* Classe de l'instance */ - if (node->flags & STNF_PROD) - { - if (points->first_node == NULL) - points->first_node = node; - - points->last_node = node; - - } - class = G_SCAN_TOKEN_NODE_GET_CLASS(node); if (class->visit != NULL) @@ -243,9 +266,6 @@ bool g_scan_token_node_setup_tree(GScanTokenNode *node) /* Phase de localisation */ - points.first_node = NULL; - points.last_node = NULL; - points.first_plain = NULL; points.best_masked = NULL; @@ -253,9 +273,8 @@ bool g_scan_token_node_setup_tree(GScanTokenNode *node) /* Phase d'application */ - // TODO : REMME - //g_scan_token_node_set_flags(points.first_node, STNF_FIRST); - //g_scan_token_node_set_flags(points.last_node, STNF_LAST); + g_scan_token_node_set_flags(node, STNF_FIRST); + g_scan_token_node_set_flags(node, STNF_LAST); if (points.first_plain != NULL) main = points.first_plain; @@ -264,11 +283,11 @@ bool g_scan_token_node_setup_tree(GScanTokenNode *node) main = points.best_masked; else - main = node;//points.first_node; + main = node; g_scan_token_node_set_flags(main, STNF_MAIN); - result = (main != node/*points.first_node*/); + result = (main != node); return result; @@ -278,7 +297,6 @@ bool g_scan_token_node_setup_tree(GScanTokenNode *node) /****************************************************************************** * * * 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] * @@ -291,14 +309,14 @@ bool g_scan_token_node_setup_tree(GScanTokenNode *node) * * ******************************************************************************/ -bool _g_scan_token_node_enroll(GScanTokenNode *node, GScanContext *context, GEngineBackend *backend, size_t maxsize, size_t *slow) +bool _g_scan_token_node_enroll(GScanTokenNode *node, GEngineBackend *backend, size_t maxsize, size_t *slow) { bool result; /* Statut à retourner */ GScanTokenNodeClass *class; /* Classe de l'instance */ class = G_SCAN_TOKEN_NODE_GET_CLASS(node); - result = class->enroll(node, context, backend, maxsize, slow); + result = class->enroll(node, backend, maxsize, slow); return result; @@ -308,7 +326,6 @@ bool _g_scan_token_node_enroll(GScanTokenNode *node, GScanContext *context, GEng /****************************************************************************** * * * 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] * @@ -321,7 +338,7 @@ bool _g_scan_token_node_enroll(GScanTokenNode *node, GScanContext *context, GEng * * ******************************************************************************/ -bool g_scan_token_node_enroll(GScanTokenNode *node, GScanContext *context, GEngineBackend *backend, size_t maxsize, size_t *slow) +bool g_scan_token_node_enroll(GScanTokenNode *node, GEngineBackend *backend, size_t maxsize, size_t *slow) { bool result; /* Statut à retourner */ @@ -329,7 +346,37 @@ bool g_scan_token_node_enroll(GScanTokenNode *node, GScanContext *context, GEngi *slow = 0; - result = _g_scan_token_node_enroll(node, context, backend, maxsize, slow); + result = _g_scan_token_node_enroll(node, 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 : - * +* * +******************************************************************************/ + +bool g_scan_token_node_build_id(GScanTokenNode *node, GEngineBackend *backend) +{ + bool result; /* Statut à retourner */ + GScanTokenNodeClass *class; /* Classe de l'instance */ + + class = G_SCAN_TOKEN_NODE_GET_CLASS(node); + + if (class->build_id == NULL) + result = true; + else + result = class->build_id(node, backend); return result; @@ -338,13 +385,10 @@ bool g_scan_token_node_enroll(GScanTokenNode *node, GScanContext *context, GEngi /****************************************************************************** * * -* 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. * * * @@ -354,7 +398,7 @@ bool g_scan_token_node_enroll(GScanTokenNode *node, GScanContext *context, GEngi * * ******************************************************************************/ -void _g_scan_token_node_check_forward(const GScanTokenNode *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +void _g_scan_token_node_check_forward(const GScanTokenNode *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { GScanTokenNodeClass *class; /* Classe de l'instance */ @@ -366,17 +410,15 @@ void _g_scan_token_node_check_forward(const GScanTokenNode *node, GScanContext * class = G_SCAN_TOKEN_NODE_GET_CLASS(node); - class->check_forward(node, context, content, matches, offset, not, skip); + class->check_forward(node, 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. * +* Paramètres : node = définition de la bribe à manipuler. * +* params = accès direct aux éléments utiles aux validations. * * * * Description : Transforme les correspondances locales en trouvailles. * * * @@ -386,9 +428,9 @@ void _g_scan_token_node_check_forward(const GScanTokenNode *node, GScanContext * * * ******************************************************************************/ -void g_scan_token_node_check_forward(const GScanTokenNode *node, GScanContext *context, GBinContent *content, pending_matches_t *matches) +void g_scan_token_node_check_forward(const GScanTokenNode *node, scan_node_check_params_t *params) { - node_search_offset_t offset; /* Espace des correspondances */ + node_search_offset_t offset; /* Espace des correspondances */ bool skip; /* Mise en attente des analyses*/ size_t ocount; /* Quantité de bornes présentes*/ node_offset_range_t * const *ranges_ptr;/* Bornes d'espace à parcourir */ @@ -401,11 +443,14 @@ void g_scan_token_node_check_forward(const GScanTokenNode *node, GScanContext *c const node_offset_range_t *range; /* Bornes d'espace à parcourir */ phys_t new_end; /* Nouveau point d'arrivée */ - init_node_search_offset(&offset); + init_node_search_offset(¶ms->offset); skip = true; - _g_scan_token_node_check_forward(node, context, content, matches, &offset, false, &skip); + _g_scan_token_node_check_forward(node, params, TNCF_UPDATE_IN_PLACE, &skip); + + +#if 0 // FIXME /** * Si un décalage entre octets n'a pas été consommé, @@ -425,8 +470,41 @@ void g_scan_token_node_check_forward(const GScanTokenNode *node, GScanContext *c * phase d'extension des résultats inexistants est ainsi sautée. */ if (count_pending_matches(matches) == 0) + { + + + for (o = 0; o < ocount; o++) + { + range = (*ranges_ptr) + o; + + + printf("range: %u - %u\n", + (unsigned int)range->min, + (unsigned int)range->max); + + + /* + new_end = old_end + range->min; + + if (new_end > matches->content_end) + new_end = matches->content_end; + + add_pending_match(pending_matches_t *, phys_t, phys_t); + + extend_pending_match_ending(matches, p, new_end); + */ + + } + + + + + + goto offset_done; + } + reset_pending_matches_ttl(matches); pending_ptr = get_all_pending_matches(matches, &pcount); @@ -466,20 +544,19 @@ void g_scan_token_node_check_forward(const GScanTokenNode *node, GScanContext *c assert(offset.used == 0); - exit_node_search_offset(&offset); +#endif + + exit_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. * * * @@ -489,13 +566,13 @@ void g_scan_token_node_check_forward(const GScanTokenNode *node, GScanContext *c * * ******************************************************************************/ -void _g_scan_token_node_check_backward(const GScanTokenNode *node, GScanContext *context, GBinContent *content, pending_matches_t *matches, node_search_offset_t *offset, bool not, bool *skip) +void _g_scan_token_node_check_backward(const GScanTokenNode *node, scan_node_check_params_t *params, TokenNodeCheckFlags cflags, bool *skip) { GScanTokenNodeClass *class; /* Classe de l'instance */ class = G_SCAN_TOKEN_NODE_GET_CLASS(node); - class->check_backward(node, context, content, matches, offset, not, skip); + class->check_backward(node, params, cflags, skip); if (node->flags & STNF_MAIN) { @@ -508,10 +585,8 @@ void _g_scan_token_node_check_backward(const GScanTokenNode *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. * +* Paramètres : node = définition de la bribe à manipuler. * +* params = accès direct aux éléments utiles aux validations. * * * * Description : Transforme les correspondances locales en trouvailles. * * * @@ -521,7 +596,7 @@ void _g_scan_token_node_check_backward(const GScanTokenNode *node, GScanContext * * ******************************************************************************/ -void g_scan_token_node_check_backward(const GScanTokenNode *node, GScanContext *context, GBinContent *content, pending_matches_t *matches) +void g_scan_token_node_check_backward(const GScanTokenNode *node, scan_node_check_params_t *params) { node_search_offset_t offset; /* Espace des correspondances */ bool skip; /* Mise en attente des analyses*/ @@ -536,11 +611,13 @@ void g_scan_token_node_check_backward(const GScanTokenNode *node, GScanContext * const node_offset_range_t *range; /* Bornes d'espace à parcourir */ phys_t new_start; /* Nouveau point d'arrivée */ - init_node_search_offset(&offset); + init_node_search_offset(¶ms->offset); skip = true; - _g_scan_token_node_check_backward(node, context, content, matches, &offset, false, &skip); + _g_scan_token_node_check_backward(node, params, TNCF_UPDATE_IN_PLACE, &skip); + +#if 0 // FIXME /** * Si un décalage entre octets n'a pas été consommé, @@ -591,6 +668,8 @@ void g_scan_token_node_check_backward(const GScanTokenNode *node, GScanContext * assert(offset.used == 0); - exit_node_search_offset(&offset); +#endif + + exit_node_search_offset(¶ms->offset); } diff --git a/src/analysis/scan/patterns/tokens/node.h b/src/analysis/scan/patterns/tokens/node.h index a2e3b0d..55bf0a8 100644 --- a/src/analysis/scan/patterns/tokens/node.h +++ b/src/analysis/scan/patterns/tokens/node.h @@ -29,9 +29,10 @@ #include <stdbool.h> +#include "offset.h" #include "../backend.h" #include "../../context.h" -#include "../../matches/pending.h" +#include "../../matches/bytes.h" #define G_TYPE_SCAN_TOKEN_NODE g_scan_token_node_get_type() @@ -53,10 +54,9 @@ typedef struct _GScanTokenNodeClass GScanTokenNodeClass; typedef enum _ScanTokenNodeFlags { STNF_NONE = (0 << 0), /* Absence de singularité */ - STNF_PROD = (1 << 0), /* Absence de singularité */ - STNF_FIRST = (1 << 1), /* Premier noeud de traitement */ /* REMME ? */ - STNF_LAST = (1 << 2), /* Dernier noeud de traitement */ /* REMME ? */ - STNF_MAIN = (1 << 3), /* Point de départ d'analyse */ + STNF_FIRST = (1 << 0), /* Premier noeud de traitement */ + STNF_LAST = (1 << 1), /* Dernier noeud de traitement */ + STNF_MAIN = (1 << 2), /* Point de départ d'analyse */ } ScanTokenNodeFlags; @@ -64,6 +64,11 @@ typedef enum _ScanTokenNodeFlags /* Indique le type défini pour un élément décomposant un motif d'octets à rechercher. */ GType g_scan_token_node_get_type(void); +/* Communique l'intérêt d'un noeud au sein d'une analyse. */ +float g_scan_token_node_compute_weight_for_scan(const GScanTokenNode *); + + + /* Indique les propriétés particulières d'un noeud d'analyse. */ ScanTokenNodeFlags g_scan_token_node_get_flags(const GScanTokenNode *); @@ -74,13 +79,47 @@ void g_scan_token_node_set_flags(GScanTokenNode *, ScanTokenNodeFlags); bool g_scan_token_node_setup_tree(GScanTokenNode *); /* Inscrit la définition d'un motif dans un moteur de recherche. */ -bool g_scan_token_node_enroll(GScanTokenNode *, GScanContext *, GEngineBackend *, size_t, size_t *); +bool g_scan_token_node_enroll(GScanTokenNode *, GEngineBackend *, size_t, size_t *); + +/* Récupère un identifiant final pour un atome d'octets. */ +bool g_scan_token_node_build_id(GScanTokenNode *, GEngineBackend *); + +/* Accès direct aux éléments utiles aux contrôles */ +typedef struct _scan_node_check_params_t +{ + GScanContext *context; /* Contexte de scan en cours */ + GBinContent *content; /* Contenu binaire associé */ + GUMemSlice *allocator; /* Allocateur pour zones */ + + phys_t content_start; /* Point de début du contenu */ + phys_t content_end; /* Point de fin du contenu */ + + node_search_offset_t offset; /* Décalages à respecter */ + + bool initialized; /* Etat du suivi */ + + /* TNCF_UPDATE_IN_PLACE */ + + match_area_t *main_areas; /* Zones principales à analyser*/ + size_t main_count; /* Taille de cette liste */ + + /* TNCF_CREATE_NEW */ + + match_area_t *created_areas; /* Zones principales à analyser*/ + size_t created_count; /* Taille de cette liste */ + + /* TNCF_KEEP_DISCARDED */ + + match_area_t *kept_areas; /* Zones principales à analyser*/ + size_t kept_count; /* Taille de cette liste */ + +} scan_node_check_params_t; /* Transforme les correspondances locales en trouvailles. */ -void g_scan_token_node_check_forward(const GScanTokenNode *, GScanContext *, GBinContent *, pending_matches_t *); +void g_scan_token_node_check_forward(const GScanTokenNode *, scan_node_check_params_t *); /* Transforme les correspondances locales en trouvailles. */ -void g_scan_token_node_check_backward(const GScanTokenNode *, GScanContext *, GBinContent *, pending_matches_t *); +void g_scan_token_node_check_backward(const GScanTokenNode *, scan_node_check_params_t *); 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); } diff --git a/src/analysis/scan/patterns/tokens/offset.c b/src/analysis/scan/patterns/tokens/offset.c index 010ec67..0a4fd91 100644 --- a/src/analysis/scan/patterns/tokens/offset.c +++ b/src/analysis/scan/patterns/tokens/offset.c @@ -229,6 +229,32 @@ node_offset_range_t * const *get_node_search_offset_ranges(const node_search_off /****************************************************************************** * * +* Paramètres : offset = suivi de tolérances bornées à consulter. * +* count = nombre de bornes enregistrées. [OUT] * +* * +* Description : Fournit la liste des tolérances bornées établies à présent. * +* * +* Retour : Liste d'intervales en lecture seule. * +* * +* Remarques : - * +* * +******************************************************************************/ + +const node_offset_range_t * const get_node_search_offset_ranges_2(const node_search_offset_t *offset, size_t *count) +{ + node_offset_range_t *result; /* Série à renvoyer */ + + result = offset->gen_ptr; + + *count = offset->used; + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : offset = suivi de tolérances bornées à consulter. * * min = point de départ pour parcourir une zone. * * max = point d'arrivée pour parcourir une zone. * @@ -318,6 +344,66 @@ void add_range_to_node_search_offset(node_search_offset_t *offset, phys_t min, p /****************************************************************************** * * +* Paramètres : offset = suivi de tolérances bornées à consulter. * +* min = point de départ pour parcourir une zone. * +* max = point d'arrivée pour parcourir une zone. * +* has_max = validité de la valeur maximale transmise. * +* * +* Description : Etend les décalages tolérés avec un nouvel espace. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void extend_node_search_offset(node_search_offset_t *offset, phys_t min, phys_t max, bool has_max) +{ + size_t i; /* Boucle de parcours */ + + switch (offset->used) + { + /* Si le réceptacle unique peut être employé... */ + case 0: + + offset->range.min = min; + offset->range.max = max; + offset->range.has_max = has_max; + + offset->used = 1; + + offset->gen_ptr = &offset->range; + + break; + + /* Si un espace unique est enregistré */ + case 1: + + offset->range.min += min; + offset->range.max += max; + offset->range.has_max &= has_max; + + break; + + /* Sinon le groupe dynamique est sollicité */ + default: + + for (i = 0; i < offset->used; i++) + { + offset->ranges[i].min += min; + offset->ranges[i].max += max; + offset->ranges[i].has_max &= has_max; + } + + break; + + } + +} + + +/****************************************************************************** +* * * Paramètres : offset = suivi de tolérances bornées à consulter. * * last = dernière position validée. * * pos = nouvelle position potentielle. * diff --git a/src/analysis/scan/patterns/tokens/offset.h b/src/analysis/scan/patterns/tokens/offset.h index b458717..130aaea 100644 --- a/src/analysis/scan/patterns/tokens/offset.h +++ b/src/analysis/scan/patterns/tokens/offset.h @@ -36,7 +36,7 @@ typedef struct _node_offset_range_t { /** * Les deux champs ci-après font bien référence à des positions absolues, - * et non à des bornes d'espace, lors que les résultats de correspondances + * et non à des bornes d'espace, lorsque les résultats de correspondances * sont encore non initialisés. * * Ensuite ces bornes représentent bien un espace séparant les résultats @@ -44,6 +44,7 @@ typedef struct _node_offset_range_t */ phys_t min; /* Position minimale */ phys_t max; /* Position maximale */ + bool has_max; /* Quantité définie ? */ } node_offset_range_t; @@ -53,6 +54,7 @@ bool get_node_offset_range(const node_offset_range_t *, phys_t, phys_t, phys_t * +#define MAX_RANGE_FOR_MANUAL_CHECK 5 @@ -83,13 +85,21 @@ void merge_node_search_offset(node_search_offset_t *, const node_search_offset_t /* Met fin à une mémorisation d'intervales de tolérance. */ void exit_node_search_offset(node_search_offset_t *); +#define offsets_exist(off) \ + ((off)->used > 0) + + /* Fournit la liste des tolérances bornées établies à présent. */ /* TODO : supprimer un niveau d'indirection */ node_offset_range_t * const *get_node_search_offset_ranges(const node_search_offset_t *, size_t *); +const node_offset_range_t * const get_node_search_offset_ranges_2(const node_search_offset_t *, size_t *); /* Ajoute un nouvel espace borné aux décalages tolérés. */ void add_range_to_node_search_offset(node_search_offset_t *, phys_t, phys_t, const phys_t *); +/* Etend les décalages tolérés avec un nouvel espace. */ +void extend_node_search_offset(node_search_offset_t *, phys_t, phys_t, bool); + #define disable_all_ranges_in_node_search_offset(off) \ (off)->used = 0 |