diff options
Diffstat (limited to 'src/analysis/scan/patterns/tokens/atom.c')
-rw-r--r-- | src/analysis/scan/patterns/tokens/atom.c | 543 |
1 files changed, 543 insertions, 0 deletions
diff --git a/src/analysis/scan/patterns/tokens/atom.c b/src/analysis/scan/patterns/tokens/atom.c new file mode 100644 index 0000000..4f2ad67 --- /dev/null +++ b/src/analysis/scan/patterns/tokens/atom.c @@ -0,0 +1,543 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * atom.c - détermination d'atomes à partir de motifs + * + * Copyright (C) 2023 Cyrille Bagard + * + * This file is part of Chrysalide. + * + * Chrysalide is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3 of the License, or + * (at your option) any later version. + * + * Chrysalide is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Foobar. If not, see <http://www.gnu.org/licenses/>. + */ + + +#include "atom.h" + + +#include <assert.h> +#include <malloc.h> +#include <math.h> + + + +/** + * Remplacement des fonctions de <ctypes.h> dans support des locales. + */ + +#define IS_CH_LETTER(ch) (('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z')) + +#define MAKE_CH_UPPER(ch) (ch & 0xdf) +#define MAKE_CH_LOWER(ch) (ch | 0x20) + + + +/****************************************************************************** +* * +* Paramètres : ch = octet dont la valeur est à analyser. * +* seen = suivi des octets déjà rencontrés. [OUT] * +* uniq = volume d'octets originaux à actualiser. [OUT] * +* letters = nombre de lettres rencontrées. [OUT] * +* * +* Description : Note l'intêret de rechercher un octet particulier. * +* * +* Retour : Note positive ou négative. * +* * +* Remarques : - * +* * +******************************************************************************/ + +int rate_byte_quality(bin_t ch, uint8_t *seen, size_t *uniq, size_t *letters) +{ + int result; /* Note à retourner */ + + switch (ch) + { + case 0x00: + case 0x20: + case 0x90: + case 0xcc: + case 0xff: + result = 12; + break; + + case 'A' ... 'Z': + case 'a' ... 'z': + if (letters == NULL) + result = 20; + else + { + result = 18; + (*letters)++; + } + break; + + default: + result = 20; + break; + + } + + if (seen[ch]++ == 0) + (*uniq)++; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : ch = octet dont la valeur est à analyser. * +* seen = suivi des octets déjà rencontrés. [OUT] * +* uniq = volume d'octets originaux à actualiser. [OUT] * +* letters = nombre de lettres rencontrées. [OUT] * +* * +* Description : Annihile l'intêret de rechercher un octet particulier. * +* * +* Retour : Note positive ou négative. * +* * +* Remarques : - * +* * +******************************************************************************/ + +int unrate_byte_quality(bin_t ch, uint8_t *seen, size_t *uniq, size_t *letters) +{ + int result; /* Note à retourner */ + + switch (ch) + { + case 0x00: + case 0x20: + case 0x90: + case 0xcc: + case 0xff: + result = 12; + break; + + case 'A' ... 'Z': + case 'a' ... 'z': + if (letters == NULL) + result = 20; + else + { + result = 18; + assert(*letters > 0); + (*letters)--; + } + break; + + default: + result = 20; + break; + + } + + if (--seen[ch] == 0) + { + assert(*uniq > 0); + (*uniq)--; + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : rating = note d'évaluation courante. * +* uniq = volume d'octets originaux relevés. * +* max = nombre d'octets considérés à la base. * +* * +* Description : Termine la notation d'un ensemble d'octets. * +* * +* Retour : Note positive ou négative. * +* * +* Remarques : - * +* * +******************************************************************************/ + +int finish_quality_rating(int rating, size_t uniq, size_t max) +{ + int result; /* Note à retourner */ + bool bad; /* Indice de mauvaise qualité */ + + if (uniq == 1) + { + bad = (rating % 12) == 0; + + result = (bad ? -10 * max : 2); + + } + + else + result = uniq * 2; + + result += rating; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : raw = définition de la bribe à enregistrer. * +* maxsize = taille max. des atomes (mise en commun optimisée). * +* atom = informations de suivi constituées. [OUT] * +* letters = nombre de lettres rencontrées. [OUT] * +* * +* Description : Détermine la portion idéale de recherche. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void find_best_atom(const sized_binary_t *raw, size_t maxsize, tracked_scan_atom_t *atom, size_t *letters) +{ + size_t i; /* Boucle de parcours #1 */ + bin_t ch; /* Octets à étudier */ + size_t best_letters; /* Mémorisation de décompte */ + size_t *ptr_letters; /* Pointeur vers le décompte */ + int raw_rating; /* Notation brute de séquence */ + uint8_t seen[256]; /* Mémorisation des passages */ + size_t uniq; /* Nombre d'octets originaux */ + const bin_t *last; /* Dernier caractère étudié */ + int best_rating; /* Meilleur notation obtenue */ + size_t max_loop; /* Limitation des itérations */ + size_t k; /* Boucle de parcours #2 */ + size_t local_letters; /* Décompte courant des lettres*/ + int local_rating; /* Notation courante */ + const bin_t *first; /* Premier caractère étudié */ + + /* Si la chaîne fournie est plus petite que la taille d'un atome... */ + if (raw->len <= maxsize) + { + atom->pos = 0; + atom->len = raw->len; + atom->rem = 0; + + atom->fast_check = true; + + if (letters != NULL) + { + *letters = 0; + + for (i = 0; i < raw->len; i++) + { + ch = raw->data[i]; + + if (IS_CH_LETTER(ch)) + (*letters)++; + + } + + } + + } + + /* ... ou si une sélection doit s'opérer */ + else + { + /* Etablissement d'une mesure de référence à la position 0 */ + + atom->pos = 0; + atom->len = maxsize; + + ptr_letters = (letters != NULL ? &best_letters : NULL); + + best_letters = 0; + raw_rating = 0; + + memset(seen, 0, sizeof(seen)); + uniq = 0; + + last = raw->static_bin_data; + + for (k = 0; k < maxsize; k++) + raw_rating += rate_byte_quality(*last++, seen, &uniq, ptr_letters); + + best_rating = finish_quality_rating(raw_rating, uniq, maxsize); + + /* Parcours du reste du contenu */ + + max_loop = (raw->len - maxsize); + + ptr_letters = (letters != NULL ? &local_letters : NULL); + + local_letters = best_letters; + local_rating = best_rating; + + first = raw->static_bin_data; + + for (i = 0; i < max_loop; i++) + { + raw_rating += rate_byte_quality(*last++, seen, &uniq, ptr_letters); + raw_rating -= unrate_byte_quality(*first++, seen, &uniq, ptr_letters); + + local_rating = finish_quality_rating(raw_rating , uniq, maxsize); + + if (local_rating > best_rating) + { + atom->pos = i + 1; + + best_letters = local_letters; + best_rating = local_rating; + + } + + } + + /* Conclusion */ + + 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))); + +} + + +/****************************************************************************** +* * +* Paramètres : src = chaîne ed référence à dupliquer. * +* atom = préselection opérée en amont. * +* count = nombre de lettres présentes. * +* * +* Description : Etablit la liste des cas de figures ignorant la casse. * +* * +* Retour : Liste de toutes les combinaisons possibles. * +* * +* Remarques : - * +* * +******************************************************************************/ + +sized_binary_t *make_atoms_case_insensitive(const sized_binary_t *src, const tracked_scan_atom_t *atom, size_t count) +{ + sized_binary_t *result; /* Liste à retourner */ + size_t i; /* Boucle de parcours #1 */ + size_t replaced; /* 2^(alternatives créées) */ +#ifndef NDEBUG + size_t check; /* Validation du compte max. */ +#endif + bin_t ch; /* Octet à recopier */ + size_t k; /* Boucle de parcours #2 */ + size_t divisor; /* Taille de la découpe */ + size_t quotient; /* Reste de la position */ + + /* Création du réceptacle */ + + result = malloc(count * sizeof(tracked_scan_atom_t)); + + assert(src->len == (atom->pos + atom->len + atom->rem)); + + for (i = 0; i < count; i++) + { + result[i].data = malloc(src->len); + result[i].len = src->len; + + memcpy(result[i].data, src->data, atom->pos); + memcpy(&result[i].data[atom->pos + atom->len], &src->data[atom->pos + atom->len], atom->rem); + + } + + /* Remplissage */ + + replaced = 2; + +#ifndef NDEBUG + check = 1; +#endif + + for (i = atom->pos; i < (atom->pos + atom->len); i++) + { + ch = src->data[i]; + + if (IS_CH_LETTER(ch)) + { + for (k = 0; k < count; k++) + { + divisor = count / replaced; + quotient = k / divisor; + + if ((quotient % 2) == 0) + result[k].data[i] = MAKE_CH_UPPER(ch); + else + result[k].data[i] = MAKE_CH_LOWER(ch); + + } + + replaced *= 2; + +#ifndef NDEBUG + check *= 2; + assert(check <= count); +#endif + + } + else + for (k = 0; k < count; k++) + result[k].data[i] = ch; + + } + + assert(check == count); + + return result; + +} + + +/****************************************************************************** +* * +* 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 des octets partiels.* +* * +* Retour : Liste de toutes les combinaisons possibles. * +* * +* Remarques : - * +* * +******************************************************************************/ + +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 * repeat_times; + + /* Création du réceptacle */ + + result = malloc(*produced * sizeof(tracked_scan_atom_t)); + + maxiter = result + *produced; + + /* Remplissage */ + + for (i = 0; i < seq_len; i++) + { + for (iter = result; iter < maxiter; ) + { + for (j = 0; j < 16; j++) + { + assert(bytes[i].mask == 0x0f || bytes[i].mask == 0xf0); + + 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; + + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : raw = définition de la bribe à enregistrer. * +* backend = moteur de recherche à préchauffer. * +* atom = informations de suivi constituées. [OUT] * +* * +* Description : Amorce l'insertion de l'atome déterminé d'une série d'octets.* +* * +* Retour : Bilan de l'opération à renvoyer. * +* * +* Remarques : - * +* * +******************************************************************************/ + +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->static_bin_data + atom->pos; + + 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); + + return result; + +} |