Postfix address wild-card support
=================================
There is a need for IP address pattern matching that is more
convenient than regular expressions or shell-like patterns.
Specifically, we need patterns for the _numbers_ in an IP address,
instead of patterns for individual characters in a human-readable
string.
In the text below we'll explore the problem, opportunities for
generalization, implementation requirements, and a simple API.
Initial trigger
===============
The initial trigger for this was support for DNS-based whitelists
(DNSWL). In this context the lookup result is of the form 127.0.x.y,
where x and y are small integers. For example, the x value (0..15)
indicates the sender organization category, and the y value (0..3)
indicates a confidence level for how safe it is to whitelist this
sender.
DNS-based blacklists (DNSBL) are older than DNSWLs, and use a simpler
approach. There, the lookup result is of the form 127.0.0.x, where
x indicates the spammer category (e.g., snowshoe spam operation,
direct-mail policy violation). However, the number of possible
responses is limited and exact matches are sufficient in practice.
We'll use the term DNSXL as a short-hand for DNSWL or DNSBL.
Narrow discussion: numeric wildcards
====================================
We treat the result from DNSXL lookup as four numeric fields. In a
printable string, these fields are separated by the "." character.
For this reason a Postfix wild-card address pattern also has four
fields, separated by the "." character.
Each pattern field is either a decimal number, or it is a numeric
wildcard. Decimal numbers match themselves; for example the pattern
127.0.0.2 matches the DNSXL result 127.0.0.2. A numeric wildcard
field matches one or more number values; for example, the pattern
127.0.[1,2,11].[1-3] requires that the third DNSXL result field has
the value 1 or 2 or 11, and that the fourth DNSXL result field is
any decimal number in the range 1 through 3 inclusive.
We could support "*" as an alias for [0-255], but we cannot support
"*" for multi-field (127.0.*) pattern matching or for sub-field
(127.0.1.*1) pattern matching. Remember, we need patterns for numbers
(the pattern [12-34] matches the *numbers* 12 through 34). If we
wanted patterns for individual characters (the pattern [12-34] matches
the *characters* "1" or "2" or "3" or "4") then we should use regular
expressions instead.
To avoid confusion, we will not support "*", at least not initially.
It is trivial to add later without breaking existing usage (just
pretend that we see [0-255] when a pattern field equals "*").
Generalization
==============
If we implement this pattern matching engine for DNSXL lookup
results, then we should consider making this also available in other
contexts such as match_list (mynetworks, inet_interfaces, etc.),
and perhaps even give it a dedicated map type so that it can be
used in Postfix access maps. This approach of universal support
is consistent with Postfix CIDR support.
If we generalize address wild-card patterns beyond DNSXL lookups,
then we have to support IPv6. There, a printable address form has
up to eight numeric fields separated by ':'. Each field is written
as a hexadecimal number that encodes two octets. The last property
will definitely discourage an implementation that represents wild-card
patterns as bitmaps: the worst case would require 8kbytes for each
of the 8 address fields.
IPv6 support can be added later. It has a different syntax than
IPv4 support, and it will have so little overlap with the IPv4 code
that it can be added later without breaking anything. Until IPv6
support is done, it is best not to support address wildcards outside
DNSXL lookups. Features that work for IPv4 but not IPv6 are just
too confusing.
Pattern matching syntax
=======================
Limiting support to IPv4 for now, the syntax for an IPv4 address
wild-card pattern is:
v4pattern = v4_field '.' v4_field '.' v4_field '.' v4_field
v4_field = v4octet | v4set
v4octet = any decimal number in the range 0 through 255
v4set = '[' v4set_list ']'
v4set_list = v4set_member | v4set_list ',' v4set_member
v4set_member = v4octet | v4octet '-' v4octet
Thus, empty fields or empty sets are not allowed in an IPv4 address
wild-card pattern.
Implementation requirements
===========================
Taking CIDR support as an example, it is a good idea to support
both "heavy" applications that match lots of patterns repeatedly
(e.g., lookup tables), and applications that have simpler needs
(e.g., match_list).
This means that the wild-card pattern parser should be cheap enough
that it can be called many times (for example, when compiling a
large lookup table, or when using the compiled result only once).
We also should not over-optimize the parser towards either fast
matching or fast compiling.
Instead of always requiring a bunch of expensive malloc()/free()
operations, each pattern will be parsed into one fixed-size block
of memory that can reside on the caller's stack. It is left up to
the caller whether they save the parser's result or whether they
use it only once. This choice of who saves the result is reflected
in the API below.
Instead of using memory-consuming bitmaps, we will use simple
in-memory sequences of single numbers for an exact match, and number
pairs for the upper and lower bounds of a numeric range. This
choice affects only what happens under the covers of the API, and
does not affect the API itself.
Basic API
=========
1 - Create a ready-to-match pattern:
parse_pattern(pattern_buffer, pattern)
pattern_buffer: caller-provided output buffer; on output,
pattern_buffer.length specifies the buffer portion that is used
pattern: address wild-card pattern
2 - Optionally save the parser's result (we could hide this under
the covers with a parse_save() function):
saved_pattern = mymalloc(pattern_buffer.length)
memcpy(saved_pattern, pattern_buffer, user_buffer.length)
3 - Apply the parsed pattern, perhaps multiple times:
status = match(parsed_pattern, input)
parsed_pattern: pattern_buffer or saved_pattern (see above)
input: for example, DNSWL or DNSBL result
status: true (match) or false (no match)
4 - Destroy the saved pattern (we could hide this under the covers
with a parse_free() function):
myfree((char *) saved_pattern;
Miscellaneous
=============
Quick heuristic for match_list_match() to decide if a string is a
wild-card pattern or an address literal:
cp = strchr(pattern, '[')
if (cp != 0 && cp > pattern) /* maybe address wild-card */
Little checks like these will be needed to support address wild-cards
in inet_interfaces, mynetworks, etc.
