Matching sets of regular expressions

[vpax]

@JustinAzoff and I were discussing how we could significantly speed up some of our code that currently loops through sets of patterns if Zeek could tell us which pattern(s) were matched. For example, it would be neat if code like this:

global a: table[pattern] of count;

a[/foo/] = 3;
a[/bar/] = 7;
a[/(foo|bletch)/] = 9;

print a["x"], a["foo"], a["bar"], a["bletch"];

would print

[], [3, 9], [7], [9]

My recollection was that Zeek in fact has this information internally but it gets lost in the layering used for matching patterns. I took a look in the internals and sure enough that's the case, and in fact this is leveraged by the signature framework to tell which of several signatures have matched.

I took a quick stab at prototyping and got the above example to work with < 150 lines of new code (topic/vern/pattern-tables-work). Assuming that given its feasibility, there's interest in developing this further (which I'd hope, as it really is helpful in some situations!), several questions come to mind:

• is table[pattern] of X the right way to expose this feature to users? It's certainly convenient for some cases.
• should the match be exact, anywhere, or user-selectable (maybe via some syntax)? My prototype implements exact, which seems best as one can always add .* on either side to make a pattern anywhere.
• are we okay with not supporting /.../i or /.../s distinctions? (The prototype just loses these.) It would not be hard to make them apply to all patterns, but due to the way the implementation works they would be difficult to support for only some of the patterns but not others. Un-pretty.

BTW I'm perfectly happy for someone else to pick up the prototype and build out the rest - just would like to see some functionality along these lines available sometime soon!

[timwoj]

is table[pattern] of X the right way to expose this feature to users? It's certainly convenient for some cases.

Would using vector of pattern and then returning the indices be better than having to do table lookups? You said you're iterating over a collection of patterns, and it seems vector iteration should be easier.

are we okay with not supporting /.../i or /.../s distinctions? (The prototype just loses these.)

What's the reason for it losing them? Assuming it's using the normal RE code, shouldn't it just return whether it matched or not?

[vpax]

Ah I see I wasn't clear. The point here isn't syntactic sugar - instead, it's much faster matching. The example I showed turns into a single regular expression that's matched in a new way (though not new inside the underlying DFA stuff) yielding all of the matches rather than a simple Yes/No answer. There's no more iteration-across-each-pattern, which can really matter when you have dozens or even 100s of patterns, like some of our code does.

This is also why /.../i and /.../s are hard to support on a pattern-by-pattern basis. Those both apply internally to entire patterns, and the way the new approach works under the hood is it makes a special X|Y|...|Z pattern that has each of the table index patterns 'or'd together. Because it uses a single match, it can only apply those modifiers to the whole thing, or none of it.

[JustinAzoff]

table[pattern] of X 

would be perfect. Because of the question I was even thinking how else you would use this.. and then I thought of paraglob. Then I wondered if paraglob could do this either. It turns out, yes.. but it's a few steps. This also has the limitation that it can only do the basic patterns that paraglob supports.

event zeek_init ()
{
	local browsers: table[string] of string = {
		["*Chrome*"] = "chrome",
		["*Mozilla*"] = "firefox",
		["*Firefox*"] = "firefox",
		["*curl*"] = "curl",
		["*wget*"] = "wget",
		["python*"] = "python",
		["*linux*"] = "linux",
	};
	local pats: vector of string = {};
	for (b in browsers) 
		pats += b;


	local p1 = paraglob_init(pats);

	local uas: vector of string = {
		"Google Chrome blah blah",
		"Mozilla Firefox on linux",
		"libcurl v.2121",
		"python v.325",
	};
	for (n in uas) {
		local ua = uas[n];
		print uas[n], "->";
		local matches = paraglob_match(p1, ua);
		for (mm in matches) {
			print "  ", browsers[matches[mm]];
		}
		print "";
	}
}

[vpax]

BTW turns out that I was wrong about supporting /i and /s, looks like the internals actually handle this fine!

[ckreibich]

I'm all for supporting faster set-matching. I also agree that Paraglob isn't the way to go here, not only because it's clumsy to make it support this use case, but especially because of its focus on globs. I do have a few comments on the table approach:

• It'd be one more instance of different semantics in the lookup — the other is tables/sets with subnet index allowing indexing with IP addresses. I think we're in agreement that this is wanted functionality, but it does complicate table implementations and has bugged us on occasion. I seem to recall a discussion around using strings to access tables with pattern index type, and we decided not to go that route, but I don't recall specifics and can't find it. It might well have been because it didn't seem pressing at the time.
• It adds different return value semantics, namely not returning the table value type, but a vector of it. (With overlapping subnets the lookup returns just one of them, not all of the matching ones — IIRC the one with the largest prefix.)
• I presume normal index operations will continue to work — for example, /foo/ in a should still return T.
• Are update operations on such tables problematic? I'm wondering about surprises of one adds/deletes patterns later on of you have 100s of entries.
• Is it clear when the code builds an optimized regex that it can reliably locate which of the original input patterns matched?

For the subnet-indexed table scenario there's a set of BiFs that address other lookup needs: matching_subnets(), filter_subnet_table(), check_subnet(). I wonder whether BiFs would be the natural way to allow the different use cases like matching vs searching, while keeping table return value types consistent. This could be pattern_table_search(), pattern_table_match(), etc, returning vectors of the value type.

Btw — I currently can find neither documentation of the table[subnet] behavior regarding IP address lookup, nor a btest verifying it. I really hope I just overlooked at least the latter...

[awelzel]

Vern's work has been integrated. Closing this discussion.