diff options
Diffstat (limited to 'src/analysis/scan/patterns/backends/acism-int.h')
| -rw-r--r-- | src/analysis/scan/patterns/backends/acism-int.h | 206 |
1 files changed, 206 insertions, 0 deletions
diff --git a/src/analysis/scan/patterns/backends/acism-int.h b/src/analysis/scan/patterns/backends/acism-int.h new file mode 100644 index 0000000..c4a72ca --- /dev/null +++ b/src/analysis/scan/patterns/backends/acism-int.h @@ -0,0 +1,206 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * acism-int.h - prototypes internes pour la méthode de recherche basée sur l'algorithme Aho-Corasick Interleaved State-transition Matrix + * + * Copyright (C) 2022 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_BACKENDS_ACISM_INT_H +#define _ANALYSIS_SCAN_PATTERNS_BACKENDS_ACISM_INT_H + + +#include "acism.h" + + +#include <stdint.h> + + +#include "../backend-int.h" +#include "../../../../common/bits.h" + + + +//#define __USE_BYTE_FREQ +//#define __SORT_BEFORE_BITMASK + + +#define ACSIM_ATOM_SIZE 7 + + + +/* Définition d'une portion de cible */ +typedef struct _acism_source_t +{ + /** + * Champs renseignés dans g_acism_backend_setup_for(). + */ + + const uint8_t *atoms; /* Motif remarquable */ + size_t len; /* Nombre d'octets considérés */ + + /** + * Champs renseignés dans g_acism_backend_build_trie(). + */ + + bool is_first; /* Première instance rencontrée*/ + + union + { + uint32_t coverage[2]; /* Départ et quantité de suivis*/ + struct + { + size_t first_source; /* Indice de première source */ + uint32_t index; /* Position dans la liste */ + }; + }; + +} 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 +{ + unsigned int frequency; /* Occurrences d'un octet */ + uint8_t rank; /* Valeur dudit octet */ + +} acism_freq_rank_t; + +/* Identifiant unique pour une valeur 8 bits donnée (max 257) */ +typedef uint16_t acism_code_t; + +#define MIN_ACISM_CODE 0 +#define MAX_ACISM_CODE 0xffff + +#define ROOT_STATE_INDEX 0 + +/* Noeud de l'arborescence brute */ +typedef struct _acism_trie_node_t +{ + struct _acism_trie_node_t *parent; /* Noeud parent pour remontée */ + struct _acism_trie_node_t *sibling; /* Noeud de même niveau suivant*/ + struct _acism_trie_node_t *child; /* Noeud de lecture suivant */ + struct _acism_trie_node_t *suffix_link; /* Retour en cas d'échec */ + + bin_t data; /* Donnée brute représentée */ + acism_code_t code; /* Identifiant du noeud */ + + 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 */ + + size_t matched_atom; /* Indice de correspondance */ + + size_t state_index; /* Indice de le tableau final */ + +} acism_trie_node_t; + +#if __LONG_WIDTH__ < 64 + +/* Cellule du tableau compressé final */ +typedef struct _acism_state_t +{ + union + { + /* Indice 0 */ + struct + { + unsigned int match : 1; /* Correspondance ici */ + unsigned int unused : 4; /* Espace encore disponible */ + unsigned int atom_size : 3; /* Taille d'atome représenté */ + unsigned int suffix : 1; /* Correspondance ailleurs */ + }; + + /* Indice 1 et + */ + unsigned int code : 9; /* Position depuis la base */ + + }; + + unsigned int index : 23; /* Indice de saut */ + +} acism_state_t; + +#else + +/* Cellule du tableau compressé final */ +typedef union _acism_state_t +{ + /* Indice 0 */ + 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 */ + }; + + /* Indice 1 et + */ + uint32_t code; /* Position depuis la base */ + + /* Tous */ + struct + { + uint32_t any; /* Saut de bits */ + uint32_t index; /* Indice de saut */ + }; + +} acism_state_t; + +#endif + +/* Méthode de recherche basée sur l'algorithme Acism (instance) */ +struct _GAcismBackend +{ + GEngineBackend parent; /* A laisser en premier */ + +#ifdef __USE_BYTE_FREQ + acism_code_t codes_for_bytes[256]; /* Traduction octets -> codes */ + acism_code_t codes_count; /* Quantité de traductions */ +#endif + + acism_source_t *sources; /* Liste de motifs remarquables*/ + size_t sources_count; /* Quantité de ces motifs */ + + size_t nchars; /* Taille cumulée des motifs */ + +#ifdef __USE_BYTE_FREQ + acism_freq_rank_t frequencies[256]; /* Fréquences des octets */ +#endif + + acism_trie_node_t *nodes; /* Liste de noeuds */ + size_t nodes_used; /* Nombre de noeuds utilisés */ + + bitfield_t *bitmap_usage; /* Localisation des usages */ + acism_state_t *states; /* Tableau de transitions */ + uint32_t *coverages; /* Bornes de suivi de positions*/ + +}; + +/* Méthode de recherche basée sur l'algorithme Acism (classe) */ +struct _GAcismBackendClass +{ + GEngineBackendClass parent; /* A laisser en premier */ + +}; + + + +#endif /* _ANALYSIS_SCAN_PATTERNS_BACKENDS_ACISM_INT_H */ |