diff options
Diffstat (limited to 'src/analysis/scan/patterns/backends/acism.c')
| -rw-r--r-- | src/analysis/scan/patterns/backends/acism.c | 174 |
1 files changed, 143 insertions, 31 deletions
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); + + } } |