]> git.ipfire.org Git - thirdparty/suricata.git/commit
radix: fix FP/FN issue in IP-only
authorVictor Julien <vjulien@oisf.net>
Fri, 11 Feb 2022 14:50:01 +0000 (15:50 +0100)
committerVictor Julien <vjulien@oisf.net>
Thu, 17 Feb 2022 15:58:59 +0000 (16:58 +0100)
commit6aa6e3f95372e256006b78e921391d88c1010f15
treed3cd5ae74f070675ada5c1339f6cecc3d0f1defb
parent6381b1a643bb9cc4ea8860def42b633a70c35e3e
radix: fix FP/FN issue in IP-only

A bug was reported about the IP-only rules not correctly matching. This was
traced to the rules in question not getting recorded into the IP-only radix
tree correctly.

Sequence:

- 100.117.241.0/25 inserted into the tree

- 100.117.241.0/26 inserted into the tree

Both are part of the same radix node, but recorded by their different netmasks
in the user data portion.

Then faulty insert happens:

- 100.117.241.64/26

For reference, these net blocks compute to:

- 100.117.241.0/25:  100.117.241.0  - 100.117.241.127
- 100.117.241.0/26:  100.117.241.0  - 100.117.241.63
- 100.117.241.64/26: 100.117.241.64 - 100.117.241.127

The IP-only engine first does a search to get to the user data it may need to
include. It does so for with `SCRadixFindKeyIPV4ExactMatch` for single IPs, or
using `SCRadixFindKeyIPV4Netblock` in case of a netblock. Any "match" from
either of these is considered an "exact match" by the IP-only setup code.

This exact match expectation turned out to be wrong and
`SCRadixFindKeyIPV4Netblock` behaved more like "best match" instead, which is
a non-exact match, but its the next best match if no exact match is found.

The way the look up for 100.117.241.64/26 went wrong, is that it returned
the user data for 100.117.241.0/26. This happens as follows:

- first it would do an exact find, which didn't give a result

- then it removed bits from the keystream until it found a matching node
  and explore if any of the netmasks it contained matched. Here the first
  step of the bug started:

  it considered the netmask (with user data) a match that matched the
  number of bits of the matching key, but not of the actual range netmask cidr
  value.

  So in this case the number of shared bits between `100.117.241.0/25` and
  `100.117.241.64/26` was 25, so it assumed that the user data for the
  netmask 25 was the match.

  To summarize this step, there are 2 problems with this:
  1. it returns a match on something that isn't an exact match
  2. it considered the wrong netmask value

- the radix code then took the returned node, and did the netmask check
  again. This time it did use its own netmask value, so this time
  it did find the netmask 26 (+ user data). However because of the node that
  was returned, this netmask (+user data) belongs to `100.117.241.0`, not to
  `100.117.241.64`.

- the IP-only detection code was satisfied with what it assumed to be
  "exact match" and just updated the user data to include the user data that
  should have been associated with `100.117.241.64/26` to `100.117.241.0/26`.

This patch addresses the issue as follows:

It makes `SCRadixFindKeyIPV4Netblock` also return an exact match by propagating
the netmask in the search and in the evaluation of the stored netmasks.

It does away with the secondary netmask (+user data) evaluation.
`SCRadixFindKeyIPV4Netblock` is expected to handle this correctly.

The IP-only engine will fall back to the "not found" path, which does an explicit
"best match" lookup and then insert a new entry into the radix tree based on
the user data of the "best match".

Issue was present for IPv6 as well.

Bug: #5066.
src/util-radix-tree.c