网络入侵检测系统之 Suricata(十五)--IPOnly/Radix Tree 详解

Suricata 中对纯 ip 的加载是单独作为一个模块的，称之为 IpOnly 规则。

那么，本文将以三个方面来介绍如何对程序进行优化。

• 什么是 IpOnly 规则

• IpOnly 规则如何组织

• IpOnly 规则如何匹配

1 什么是 IpOnly 规则

IpOnly 规则在规则解析后，由 SignatureIsPDOnly 函数进行判断， 不满足 IpOnly 的规则大致可分为以下情况：

• 未知协议，即不在 AppProtoEnum 结构体中定义的协议

• 含模式匹配，即存在 option 带 content，或 pcre 等等

• 地址中存在非规则，即!1.1.1.1 any -> any any

• 与 IpOnly 不兼容的一些 option，例如 DETECT_FLOWBITS（需要有 setbits）

2 IpOnly 规则如何组织

IpOnly 规则比较特殊，一般认为命中源和目的 ip 地址，再校验以下其他头部信息，就可以认为该报文 可以命中这条规则。那么我们的重点就放在了如何组织 ipv4,ipv6 地址，并高效的进行匹配。

这里面 suricata 借鉴了 BSD 操作系统中路由表查找算法-Radix Tree，路由表查找本质就是对目的 ip 进行 最长掩码匹配，而索引到路由表中的下一跳。那么，我们先看看 radix tree 的基本思想。

Radix Tree 本质是一个二叉树，由内部节点和外部节点，内部节点用于指示需要进行 bit test 的位置，并根据测试结果决定查找方向，外部节点则用于存储键值。

Suricata 具体实现在 IPOnlyPrepare 中，它分别建立了 4 个 Radix Tree，代表源 ipv4/6，目的 ipv4/6。

精确 IP 添加的步骤：

1. 将插入的节点放在树中匹配，如果键值一样则挂在掩码链表的合适位置，否则就要记录它们第一次出现不同 bit 的位置。

2. 公共相同掩码切分，看下面这个图比较好理解，旧节点和新节点第一次不一样的地方是 148：

插入前：

插入后：

网段 IP 添加的步骤：

1. 类似于 192.171.192.0/18 这种网段形式的 ip 插入，首先先将 ip 和 mask 作个与运算，生成的 key 不断进行进行 bit test 找到叶子节点，然后最大公共相同的位置，生成新的父节点。这一步和精确 ip 的插入是一样的。

2. 如果当前网段 ip 的掩码小于或等于父节点的 bit 位置，那么我们可以认为这个叶子结点可以覆盖父节点下所有的节点，因此新增父节点的 netmask 为 18。

3 IpOnly 规则如何匹配

匹配在函数 SCRadixFindKeyIPV4BestMatch 及 SCRadixFindKeyIPV6BestMatch 中。 查找步骤可分为 3 步，寻叶-》辩重-》回溯：

• 不停的 bit test 进行左右路径深入，终结于某个叶子节点后，判断该叶子节点是否与查找键相同。

如果第一步骤精确匹配不到，则在这个叶子节点的重复键链表中查找掩码匹配的可能，掩码是按从大到小进行排列：192.168.0.0/16 和 192.168.0.0/20

//查掩码链表SCRadixPrefixContainNetmaskAndSetUserData(node->prefix, netmask_node->netmasks[j], 0, user_data_result))//精确匹配SCRadixPrefixContainNetmaskAndSetUserData(node->prefix, key_bitlen, 1, user_data_result)

• 如果第二步骤也没有找到，那么需要向父亲节点回溯，将查找键和该掩码进行逻辑与运算，产生一个新的查找键再进行查找，因为树顶代表的是大家拥有前缀一致的 ip 地址，那么如果存在该中间节点掩码列表中掩码够小，那么是存在网络匹配的可能的。

4 Reference

• https://blog.csdn.net/cuemes08808/article/details/100391242
  

• https://blog.csdn.net/weifenghai/article/details/53113395
  

• https://blog.csdn.net/todd911/a