00001 //--------------------------------------------------------------------------
00002 // Copyright (C) 2014-2017 Cisco and/or its affiliates. All rights reserved.
00003 // Copyright (C) 2005-2013 Sourcefire, Inc.
00004 //
00005 // This program is free software; you can redistribute it and/or modify it
00006 // under the terms of the GNU General Public License Version 2 as published
00007 // by the Free Software Foundation. You may not use, modify or distribute
00008 // this program under any other version of the GNU General Public License.
00009 //
00010 // This program is distributed in the hope that it will be useful, but
00011 // WITHOUT ANY WARRANTY; without even the implied warranty of
00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
00013 // General Public License for more details.
00014 //
00015 // You should have received a copy of the GNU General Public License along
00016 // with this program; if not, write to the Free Software Foundation, Inc.,
00017 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00018 //--------------------------------------------------------------------------
00019
00020 // bnfa_search.h author Marc Norton <mnorton@sourcefire.com>
00021
00022 #ifndef BNFA_SEARCH_H
00023 #define BNFA_SEARCH_H
00024
00025 /*
00026 ** Basic NFA based multi-pattern search using Aho_corasick construction,
00027 ** and compacted sparse storage.
00028 **
00029 ** Version 3.0
00030 ** date: 12/21/05
00031 */
00032
00033 #include <cstdint>
00034
00035 #include "search_common.h"
00036
00037 /* debugging - allow printing the trie and nfa in list format
00038 #define ALLOW_LIST_PRINT */
00039
00040 /* debugging - enable full format
00041 #define ALLOW_NFA_FULL */
00042
00043 /*
00044 * DEFINES and Typedef's
00045 */
00046 //#define SPARSE_FULL_STATE_0
00047 #define BNFA_MAX_ALPHABET_SIZE 256
00048 #define BNFA_FAIL_STATE 0xffffffff
00049 #define BNFA_SPARSE_LINEAR_SEARCH_LIMIT 6
00050
00051 #define BNFA_SPARSE_MAX_STATE 0x00ffffff
00052 #define BNFA_SPARSE_COUNT_SHIFT 24
00053 #define BNFA_SPARSE_VALUE_SHIFT 24
00054
00055 #define BNFA_SPARSE_MATCH_BIT 0x80000000
00056 #define BNFA_SPARSE_FULL_BIT 0x40000000
00057 #define BNFA_SPARSE_COUNT_BITS 0x3f000000
00058 #define BNFA_SPARSE_MAX_ROW_TRANSITIONS 0x3f
00059
00060 typedef unsigned int bnfa_state_t;
00061
00062 /*
00063 * Internal Pattern Representation
00064 */
00065 struct bnfa_pattern_t
00066 {
00067 bnfa_pattern_t* next;
00068 uint8_t* casepatrn; /* case specific */
00069 void* userdata; /* ptr to users pattern data/info */
00070
00071 unsigned n; /* pattern len */
00072 int nocase; /* nocase flag */
00073 int negative; /* pattern is negated */
00074 };
00075
00076 /*
00077 * List format transition node
00078 */
00079 struct bnfa_trans_node_t
00080 {
00081 bnfa_trans_node_t* next;
00082 bnfa_state_t key;
00083 bnfa_state_t next_state;
00084 };
00085
00086 /*
00087 * List format patterns
00088 */
00089 struct bnfa_match_node_t
00090 {
00091 void* data;
00092 void* rule_option_tree;
00093 void* neg_list;
00094 bnfa_match_node_t* next;
00095 };
00096
00097 /*
00098 * Final storage type for the state transitions
00099 */
00100 enum
00101 {
00102 BNFA_FULL,
00103 BNFA_SPARSE
00104 };
00105
00106 enum
00107 {
00108 BNFA_PER_PAT_CASE,
00109 BNFA_CASE,
00110 BNFA_NOCASE
00111 };
00112
00113 /*
00114 * Aho-Corasick State Machine Struct
00115 */
00116 struct bnfa_struct_t
00117 {
00118 int bnfaMethod;
00119 int bnfaCaseMode;
00120 int bnfaFormat;
00121 int bnfaAlphabetSize;
00122 int bnfaOpt;
00123
00124 unsigned bnfaPatternCnt;
00125
00126 int bnfaMaxStates;
00127 int bnfaNumStates;
00128 int bnfaNumTrans;
00129 int bnfaMatchStates;
00130
00131 bnfa_pattern_t* bnfaPatterns;
00132 bnfa_trans_node_t** bnfaTransTable;
00133 bnfa_state_t** bnfaNextState;
00134 bnfa_match_node_t** bnfaMatchList;
00135 bnfa_state_t* bnfaFailState;
00136 bnfa_state_t* bnfaTransList;
00137
00138 const MpseAgent* agent;
00139
00140 int bnfaForceFullZeroState;
00141
00142 int bnfa_memory;
00143 int pat_memory;
00144 int list_memory;
00145 int queue_memory;
00146 int nextstate_memory;
00147 int failstate_memory;
00148 int matchlist_memory;
00149 };
00150
00151 /*
00152 * Prototypes
00153 */
00154 void bnfa_init_xlatcase();
00155
00156 bnfa_struct_t* bnfaNew(const MpseAgent*);
00157
00158 void bnfaSetOpt(bnfa_struct_t* p, int flag);
00159 void bnfaSetCase(bnfa_struct_t* p, int flag);
00160 void bnfaFree(bnfa_struct_t* pstruct);
00161
00162 int bnfaAddPattern(
00163 bnfa_struct_t* pstruct, const uint8_t* pat, unsigned patlen,
00164 bool nocase, bool negative, void* userdata);
00165
00166 int bnfaCompile(struct SnortConfig*, bnfa_struct_t*);
00167
00168 unsigned _bnfa_search_csparse_nfa(
00169 bnfa_struct_t * pstruct, const uint8_t* t, int tlen, MpseMatch,
00170 void* context, unsigned sindex, int* current_state);
00171
00172 int bnfaPatternCount(bnfa_struct_t* p);
00173
00174 void bnfaPrint(bnfa_struct_t* pstruct); /* prints the nfa states-verbose!! */
00175 void bnfaPrintInfo(bnfa_struct_t* pstruct); /* print info on this search engine */
00176
00177 /*
00178 * Summary - this tracks search engine information across multiple instances of
00179 * search engines. It helps in snort where we have many search engines, each using
00180 * rule grouping, to track total patterns, states, memory, etc...
00181 *
00182 */
00183 void bnfaPrintInfoEx(bnfa_struct_t* p, const char* text);
00184 void bnfaAccumInfo(bnfa_struct_t* pstruct); // add info to summary over multiple search engines
00185 void bnfaPrintSummary(); /* print current summary */
00186 void bnfaInitSummary(); /* reset accumulator for global summary over multiple engines */
00187 void bnfa_print_qinfo();
00188 #endif
00189
END OF CODE