Branch data Line data Source code
1 : : // $Id: RuleMatcher.h 3526 2006-09-12 07:32:21Z vern $
2 : :
3 : : #ifndef sigs_h
4 : : #define sigs_h
5 : :
6 : : #include <limits.h>
7 : :
8 : : #include "BroString.h"
9 : : #include "List.h"
10 : : #include "RE.h"
11 : : #include "Net.h"
12 : : #include "Sessions.h"
13 : : #include "IntSet.h"
14 : : #include "util.h"
15 : : #include "Rule.h"
16 : : #include "RuleAction.h"
17 : : #include "RuleCondition.h"
18 : :
19 : : //#define MATCHER_PRINT_STATS
20 : :
21 : : extern int rule_bench;
22 : :
23 : : // Parser interface:
24 : :
25 : : extern void rules_error(const char* msg);
26 : : extern void rules_error(const char* msg, const char* addl);
27 : : extern void rules_error(Rule* id, const char* msg);
28 : : extern int rules_lex(void);
29 : : extern int rules_parse(void);
30 : : extern "C" int rules_wrap(void);
31 : : extern FILE* rules_in;
32 : : extern int rules_line_number;
33 : : extern const char* current_rule_file;
34 : :
35 : : class RuleMatcher;
36 : : extern RuleMatcher* rule_matcher;
37 : :
38 : : class Analyzer;
39 : : class PIA;
40 : :
41 : : // RuleHdrTest and associated things:
42 : :
43 : : // Given a header expression like "ip[offset:len] & mask = val", we parse
44 : : // it into a Range and a MaskedValue.
45 : : struct Range {
46 : : uint32 offset;
47 : : uint32 len;
48 : : };
49 : :
50 : : struct MaskedValue {
51 : : uint32 val;
52 : : uint32 mask;
53 : : };
54 : :
55 : 43 : declare(PList, MaskedValue);
56 : : typedef PList(MaskedValue) maskedvalue_list;
57 : :
58 : : typedef PList(char) string_list;
59 : :
60 : 0 : declare(PList, BroString);
61 : : typedef PList(BroString) bstr_list;
62 : :
63 : : // Get values from Bro's script-level variables.
64 : : extern void id_to_maskedvallist(const char* id, maskedvalue_list* append_to);
65 : : extern char* id_to_str(const char* id);
66 : : extern uint32 id_to_uint(const char* id);
67 : :
68 : : class RuleHdrTest {
69 : : public:
70 : : enum Comp { LE, GE, LT, GT, EQ, NE };
71 : : enum Prot { NOPROT, IP, ICMP, TCP, UDP };
72 : :
73 : : RuleHdrTest(Prot arg_prot, uint32 arg_offset, uint32 arg_size,
74 : : Comp arg_comp, maskedvalue_list* arg_vals);
75 : : ~RuleHdrTest();
76 : :
77 : : void PrintDebug();
78 : :
79 : : private:
80 : : // The constructor does not copy those attributes which are set
81 : : // by RuleMatcher::BuildRulesTree() (see below).
82 : : RuleHdrTest(RuleHdrTest& h);
83 : : // should be const, but lists don't have const version
84 : :
85 : : // Likewise, the operator== checks only for same test semantics.
86 : : bool operator==(const RuleHdrTest& h);
87 : :
88 : : Prot prot;
89 : : Comp comp;
90 : : maskedvalue_list* vals;
91 : : uint32 offset;
92 : : uint32 size;
93 : :
94 : : uint32 id; // For debugging, each HdrTest gets an unique ID
95 : : static uint32 idcounter;
96 : :
97 : : // The following are all set by RuleMatcher::BuildRulesTree().
98 : : friend class RuleMatcher;
99 : :
100 : : struct PatternSet {
101 : 0 : PatternSet() {}
102 : :
103 : : // If we're above the 'RE_level' (see RuleMatcher), this
104 : : // expr contains all patterns on this node. If we're on
105 : : // 'RE_level', it additionally contains all patterns
106 : : // of any of its children.
107 : : Specific_RE_Matcher* re;
108 : :
109 : : // All the patterns and their rule indices.
110 : : string_list patterns;
111 : : int_list ids; // (only needed for debugging)
112 : : };
113 : :
114 : 176 : declare(PList, PatternSet);
115 : : typedef PList(PatternSet) pattern_set_list;
116 : : pattern_set_list psets[Rule::TYPES];
117 : :
118 : : // List of rules belonging to this node.
119 : : Rule* pattern_rules; // rules w/ at least one pattern of any type
120 : : Rule* pure_rules; // rules containing no patterns at all
121 : :
122 : : IntSet* ruleset; // set of all rules belonging to this node
123 : : // (for fast membership test)
124 : :
125 : : RuleHdrTest* sibling; // linkage within HdrTest tree
126 : : RuleHdrTest* child;
127 : :
128 : : int level; // level within the tree
129 : : };
130 : :
131 : 0 : declare(PList, RuleHdrTest);
132 : : typedef PList(RuleHdrTest) rule_hdr_test_list;
133 : :
134 : : // RuleEndpointState keeps the per-stream matching state of one
135 : : // connection endpoint.
136 : : class RuleEndpointState {
137 : : public:
138 : : ~RuleEndpointState();
139 : :
140 : 0 : Analyzer* GetAnalyzer() const { return analyzer; }
141 : 0 : bool IsOrig() { return is_orig; }
142 : :
143 : : // For flipping roles.
144 : : void FlipIsOrig() { is_orig = ! is_orig; }
145 : :
146 : : // Returns the size of the first non-empty chunk of
147 : : // data feed into the RULE_PAYLOAD matcher.
148 : : // Returns 0 zero iff only empty chunks have been fed.
149 : : // Returns -1 if no chunk has been fed yet at all.
150 : 0 : int PayloadSize() { return payload_size; }
151 : :
152 : 0 : ::PIA* PIA() const { return pia; }
153 : :
154 : : private:
155 : : friend class RuleMatcher;
156 : :
157 : : // Constructor is private; use RuleMatcher::InitEndpoint()
158 : : // for creating an instance.
159 : : RuleEndpointState(Analyzer* arg_analyzer, bool arg_is_orig,
160 : : RuleEndpointState* arg_opposite, ::PIA* arg_PIA);
161 : :
162 : : struct Matcher {
163 : : RE_Match_State* state;
164 : : Rule::PatternType type;
165 : : };
166 : :
167 : 0 : declare(PList, Matcher);
168 : : typedef PList(Matcher) matcher_list;
169 : :
170 : : bool is_orig;
171 : : Analyzer* analyzer;
172 : : RuleEndpointState* opposite;
173 : : ::PIA* pia;
174 : :
175 : : matcher_list matchers;
176 : : rule_hdr_test_list hdr_tests;
177 : :
178 : : // The follow tracks which rules for which all patterns have matched,
179 : : // and in a parallel list the (first instance of the) corresponding
180 : : // matched text.
181 : : rule_list matched_by_patterns;
182 : : bstr_list matched_text;
183 : :
184 : : int payload_size;
185 : :
186 : : int_list matched_rules; // Rules for which all conditions have matched
187 : : };
188 : :
189 : :
190 : : // RuleMatcher is the main class which builds up the data structures
191 : : // and performs the actual matching.
192 : :
193 : : class RuleMatcher {
194 : : public:
195 : : // Argument is tree level on which we build combined regexps
196 : : // (Level 0 is root).
197 : : RuleMatcher(int RE_level = 4);
198 : : ~RuleMatcher();
199 : :
200 : : // Parse the given files and built up data structures.
201 : : bool ReadFiles(const name_list& files);
202 : :
203 : : // Initialize the matching state for a endpoind of a connection based on
204 : : // the given packet (which should be the first packet encountered for
205 : : // this endpoint). If the matching is triggered by an PIA, a pointer to
206 : : // it needs to be given.
207 : : RuleEndpointState* InitEndpoint(Analyzer* analyzer, const IP_Hdr* ip,
208 : : int caplen, RuleEndpointState* opposite, bool is_orig, PIA* pia);
209 : :
210 : : // Finish matching for this stream.
211 : : void FinishEndpoint(RuleEndpointState* state);
212 : :
213 : : // Perform the actual pattern matching on the given data.
214 : : // bol/eol should be set to false for type Rule::PAYLOAD; they're
215 : : // deduced automatically.
216 : : void Match(RuleEndpointState* state, Rule::PatternType type,
217 : : const u_char* data, int data_len,
218 : : bool bol, bool eol, bool clear);
219 : :
220 : : // Reset the state of the pattern matcher for this endpoint.
221 : : void ClearEndpointState(RuleEndpointState* state);
222 : :
223 : : void PrintDebug();
224 : :
225 : : // Interface to parser
226 : : void AddRule(Rule* rule);
227 : 0 : void SetParseError() { parse_error = true; }
228 : :
229 : : // Interface to for getting some statistics
230 : : struct Stats {
231 : : unsigned int matchers; // # distinct RE matchers
232 : :
233 : : // # DFA states across all matchers
234 : : unsigned int dfa_states;
235 : : unsigned int computed; // # computed DFA state transitions
236 : : unsigned int mem; // # bytes used by DFA states
237 : :
238 : : // # cache hits (sampled, multiply by MOVE_TO_FRONT_SAMPLE_SIZE)
239 : : unsigned int hits;
240 : : unsigned int misses; // # cache misses
241 : :
242 : : // Average # NFA states per DFA state.
243 : : unsigned int avg_nfa_states;
244 : : };
245 : :
246 : : Val* BuildRuleStateValue(const Rule* rule,
247 : : const RuleEndpointState* state) const;
248 : :
249 : : void GetStats(Stats* stats, RuleHdrTest* hdr_test = 0);
250 : : void DumpStats(BroFile* f);
251 : :
252 : : private:
253 : : // Delete node and all children.
254 : : void Delete(RuleHdrTest* node);
255 : :
256 : : // Build tree containing all added rules.
257 : : void BuildRulesTree();
258 : :
259 : : // Insert one rule into the current tree.
260 : : void InsertRuleIntoTree(Rule* r, int testnr, RuleHdrTest* dest,
261 : : int level);
262 : :
263 : : // Traverse tree building the combined regular expressions.
264 : : void BuildRegEx(RuleHdrTest* hdr_test, string_list* exprs, int_list* ids);
265 : :
266 : : // Build groups of regular epxressions.
267 : : void BuildPatternSets(RuleHdrTest::pattern_set_list* dst,
268 : : const string_list& exprs, const int_list& ids);
269 : :
270 : : // Check an arbitrary rule if it's satisfied right now.
271 : : // eos signals end of stream
272 : : void ExecRule(Rule* rule, RuleEndpointState* state, bool eos);
273 : :
274 : : // Evaluate all rules which do not depend on any matched patterns.
275 : : void ExecPureRules(RuleEndpointState* state, bool eos);
276 : :
277 : : // Eval a rule under the assumption that all its patterns
278 : : // have already matched. s holds the text the rule matched,
279 : : // or nil if N/A.
280 : : bool ExecRulePurely(Rule* r, BroString* s,
281 : : RuleEndpointState* state, bool eos);
282 : :
283 : : // Execute the actions associated with a rule.
284 : : void ExecRuleActions(Rule* r, RuleEndpointState* state,
285 : : const u_char* data, int len, bool eos);
286 : :
287 : : // Evaluate all rule conditions except patterns and "header".
288 : : bool EvalRuleConditions(Rule* r, RuleEndpointState* state,
289 : : const u_char* data, int len, bool eos);
290 : :
291 : : void PrintTreeDebug(RuleHdrTest* node);
292 : :
293 : : void DumpStateStats(BroFile* f, RuleHdrTest* hdr_test);
294 : :
295 : : int RE_level;
296 : : bool parse_error;
297 : : RuleHdrTest* root;
298 : : rule_list rules;
299 : : rule_dict rules_by_id;
300 : : };
301 : :
302 : : // Keeps bi-directional matching-state.
303 : : class RuleMatcherState {
304 : : public:
305 : 1627 : RuleMatcherState() { orig_match_state = resp_match_state = 0; }
306 : 1627 : ~RuleMatcherState()
307 [ - + ][ - + ]: 1627 : { delete orig_match_state; delete resp_match_state; }
308 : :
309 : : // ip may be nil.
310 : : void InitEndpointMatcher(Analyzer* analyzer, const IP_Hdr* ip,
311 : : int caplen, bool from_orig, PIA* pia = 0);
312 : :
313 : : // bol/eol should be set to false for type Rule::PAYLOAD; they're
314 : : // deduced automatically.
315 : : void Match(Rule::PatternType type, const u_char* data, int data_len,
316 : : bool from_orig, bool bol, bool eol, bool clear_state);
317 : :
318 : : void FinishEndpointMatcher();
319 : : void ClearMatchState(bool orig);
320 : :
321 : 28486 : bool MatcherInitialized(bool orig)
322 [ + + ]: 28486 : { return orig ? orig_match_state : resp_match_state; }
323 : :
324 : : private:
325 : : RuleEndpointState* orig_match_state;
326 : : RuleEndpointState* resp_match_state;
327 : : };
328 : :
329 : : #endif
|
