summaryrefslogtreecommitdiff
path: root/src/analysis/scan/patterns/backends
diff options
context:
space:
mode:
authorCyrille Bagard <nocbos@gmail.com>2024-01-21 22:36:47 (GMT)
committerCyrille Bagard <nocbos@gmail.com>2024-01-21 22:36:47 (GMT)
commit0ff1e52622828663d01f98c97f2cd8eccb8facf8 (patch)
tree88b5fcf2412f863276876d0b8ad8db91903f3758 /src/analysis/scan/patterns/backends
parent0fac40d5a5752e8d7b92f57ea3cfa089f13a2d1f (diff)
Refactor the scan match storage.
Diffstat (limited to 'src/analysis/scan/patterns/backends')
-rw-r--r--src/analysis/scan/patterns/backends/acism-int.h13
-rw-r--r--src/analysis/scan/patterns/backends/acism.c174
-rw-r--r--src/analysis/scan/patterns/backends/bitap.c12
3 files changed, 161 insertions, 38 deletions
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]);
+ **/
}