suricata
util-port-interval-tree.c
Go to the documentation of this file.
1 /* Copyright (C) 2024 Open Information Security Foundation
2  *
3  * You can copy, redistribute or modify this Program under the terms of
4  * the GNU General Public License version 2 as published by the Free
5  * Software Foundation.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * version 2 along with this program; if not, write to the Free Software
14  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
15  * 02110-1301, USA.
16  */
17 
18 /**
19  * \file
20  *
21  * \author Shivani Bhardwaj <shivani@oisf.net>
22  */
23 
25 #include "util-validate.h"
26 #include "detect-engine-siggroup.h"
27 #include "detect-engine-port.h"
28 
29 /**
30  * \brief Function to compare two interval nodes. This defines the order
31  * of insertion of a node in the interval tree. This also updates
32  * the max attribute of any node in a given tree if needed.
33  *
34  * \param a First node to compare
35  * \param b Second node to compare
36  *
37  * \return 1 if low of node a is bigger, -1 otherwise
38  */
39 static int SCPortIntervalCompareAndUpdate(const SCPortIntervalNode *a, SCPortIntervalNode *b)
40 {
41  if (a->port2 > b->max) {
42  b->max = a->port2;
43  }
44  if (a->port >= b->port) {
45  SCReturnInt(1);
46  }
47  SCReturnInt(-1);
48 }
49 
50 // cppcheck-suppress nullPointerRedundantCheck
51 IRB_GENERATE(PI, SCPortIntervalNode, irb, SCPortIntervalCompareAndUpdate);
52 
53 /**
54  * \brief Function to initialize the interval tree.
55  *
56  * \return Pointer to the newly created interval tree
57  */
59 {
61  if (it == NULL) {
62  return NULL;
63  }
64 
65  return it;
66 }
67 
68 /**
69  * \brief Helper function to free a given node in the interval tree.
70  *
71  * \param de_ctx Detection Engine Context
72  * \param it Pointer to the interval tree
73  */
74 static void SCPortIntervalNodeFree(DetectEngineCtx *de_ctx, SCPortIntervalTree *it)
75 {
76  SCPortIntervalNode *node = NULL, *safe = NULL;
77  IRB_FOREACH_SAFE(node, PI, &it->tree, safe)
78  {
79  SigGroupHeadFree(de_ctx, node->sh);
80  PI_IRB_REMOVE(&it->tree, node);
81  SCFree(node);
82  }
83  it->head = NULL;
84 }
85 
86 /**
87  * \brief Function to free an entire interval tree.
88  *
89  * \param de_ctx Detection Engine Context
90  * \param it Pointer to the interval tree
91  */
93 {
94  if (it) {
95  SCPortIntervalNodeFree(de_ctx, it);
96  SCFree(it);
97  }
98 }
99 
100 /**
101  * \brief Function to insert a node in the interval tree.
102  *
103  * \param de_ctx Detection Engine Context
104  * \param it Pointer to the interval tree
105  * \param p Pointer to a DetectPort object
106  *
107  * \return SC_OK if the node was inserted successfully, SC_EINVAL otherwise
108  */
110 {
112 
113  SCPortIntervalNode *pi = SCCalloc(1, sizeof(*pi));
114  if (pi == NULL) {
115  return SC_EINVAL;
116  }
117 
118  pi->port = p->port;
119  pi->port2 = p->port2;
120  SigGroupHeadCopySigs(de_ctx, p->sh, &pi->sh);
121 
122  if (PI_IRB_INSERT(&it->tree, pi) != NULL) {
123  SCLogDebug("Node wasn't added to the tree: port: %d, port2: %d", pi->port, pi->port2);
124  SCFree(pi);
125  return SC_EINVAL;
126  }
127  return SC_OK;
128 }
129 
130 /**
131  * \brief Function to remove multiple sig entries corresponding to the same
132  * signature group and merge them into one.
133  *
134  * \param de_ctx Detection Engine Context
135  * \param list Pointer to the list to be modified
136  */
137 static void SCPortIntervalSanitizeList(DetectEngineCtx *de_ctx, DetectPort **list)
138 {
139  DetectPort *cur = (*list)->last;
140  if (cur == NULL)
141  return;
142 
143  DetectPort *prev = (*list)->last->prev;
144  if (prev == NULL)
145  return;
146 
147  /* rulegroup IDs are assigned much later so, compare SGHs */
148  if (SigGroupHeadEqual(prev->sh, cur->sh)) {
149  if (prev->port2 == (cur->port - 1)) {
150  /* Merge the port objects */
151  prev->port2 = cur->port2;
152  (*list)->last = prev;
153  (*list)->last->next = NULL;
154  DetectPortFree(de_ctx, cur);
155  }
156  }
157 }
158 
159 /**
160  * \brief Function to check if a port range overlaps with a given set of ports
161  *
162  * \param port Given low port
163  * \param port2 Given high port
164  * \param ptr Pointer to the node in the tree to be checked against
165  *
166  * \return true if an overlaps was found, false otherwise
167  */
168 static bool SCPortIntervalIsOverlap(
169  const uint16_t port, const uint16_t port2, const SCPortIntervalNode *ptr)
170 {
171  /* Two intervals i and i' are said to overlap if
172  * - i (intersection) i' != NIL
173  * - i.low <= i'.high
174  * - i'.low <= i.high
175  *
176  * There are four possible cases of overlaps as shown below which
177  * are all covered by the if condition that follows.
178  *
179  * Case 1: [.........] i
180  * [...................] i'
181  *
182  * Case 2: [...................] i
183  * [.........] i'
184  *
185  * Case 3: [........] i
186  * [..............] i'
187  *
188  * Case 4: [..............] i
189  * [.............] i'
190  */
191  if (port <= ptr->port2 && ptr->port <= port2) {
192  return true;
193  }
194 
195  SCLogDebug("No overlap found for [%d, %d] w [%d, %d]", port, port2, ptr->port, ptr->port2);
196  return false;
197 }
198 
199 #define STACK_SIZE 100
200 
201 /**
202  * \brief Function to find all the overlaps of given ports with the existing
203  * port ranges in the interval tree. This function takes in a low and
204  * a high port, considers it a continuos range and tries to match it
205  * against all the given port ranges in the interval tree. This search
206  * for overlap happens in min(O(k*log(n)), O(n*n)) time where,
207  * n = number of nodes in the tree, and,
208  * k = number of intervals with which an overlap was found
209  *
210  * \param de_ctx Detection Engine Context
211  * \param port Given low port
212  * \param port2 Given high port
213  * \param ptr Pointer to the root of the tree
214  * \param list A list of DetectPort objects to be filled
215  */
216 static void SCPortIntervalFindOverlaps(DetectEngineCtx *de_ctx, const uint16_t port,
217  const uint16_t port2, SCPortIntervalNode *root, DetectPort **list)
218 {
219  DetectPort *new_port = NULL;
220  int stack_depth = 0;
221  SCPortIntervalNode **stack =
223  if (stack == NULL)
224  return;
225  SCPortIntervalNode *current = root;
226  int stack_size = STACK_SIZE;
227 
228  while (current || stack_depth) {
229  while (current != NULL) {
230  if (current->max < port) {
231  current = NULL;
232  break;
233  }
234  const bool is_overlap = SCPortIntervalIsOverlap(port, port2, current);
235 
236  if (is_overlap && (new_port == NULL)) {
237  /* Allocate memory for port obj only if it's first overlap */
238  new_port = DetectPortInit();
239  if (new_port == NULL) {
240  goto error;
241  }
242 
243  SCLogDebug("Found overlaps for [%u:%u], creating new port", port, port2);
244  new_port->port = port;
245  new_port->port2 = port2;
246  SigGroupHeadCopySigs(de_ctx, current->sh, &new_port->sh);
247 
248  /* Since it is guaranteed that the ports received by this stage
249  * will be sorted, insert any new ports to the end of the list
250  * and avoid walking the entire list */
251  if (*list == NULL) {
252  *list = new_port;
253  (*list)->last = new_port;
254  } else if (((*list)->last->port != new_port->port) &&
255  ((*list)->last->port2 != new_port->port2)) {
256  DEBUG_VALIDATE_BUG_ON(new_port->port < (*list)->last->port);
257  (*list)->last->next = new_port;
258  new_port->prev = (*list)->last;
259  (*list)->last = new_port;
260  } else {
261  SCLogDebug("Port already exists in the list");
262  goto error;
263  }
264  } else if (is_overlap && (new_port != NULL)) {
265  SCLogDebug("Found overlaps for [%u:%u], adding sigs", port, port2);
266  /* Only copy the relevant SGHs on later overlaps */
267  SigGroupHeadCopySigs(de_ctx, current->sh, &new_port->sh);
268  }
269  stack[stack_depth++] = current;
270  if (stack_depth == stack_size) {
271  SCLogDebug("Stack depth %d maxed out, realloc'ing..", stack_depth);
272  stack_size *= 2;
273  void *tmp = SCRealloc(stack, stack_size * sizeof(SCPortIntervalNode *));
274  if (tmp == NULL) {
275  SCLogError("Couldn't realloc the interval tree stack");
276  goto error;
277  }
278  stack = tmp;
279  }
280  current = IRB_LEFT(current, irb);
281  }
282 
283  if (stack_depth == 0) {
284  SCLogDebug("Stack depth was exhausted");
285  break;
286  }
287 
288  SCPortIntervalNode *popped = stack[stack_depth - 1];
289  stack_depth--;
290  BUG_ON(popped == NULL);
291  current = IRB_RIGHT(popped, irb);
292  }
293  if (new_port != NULL)
294  SCPortIntervalSanitizeList(de_ctx, list);
295  if (stack != NULL)
296  SCFree(stack);
297  return;
298 error:
299  if (new_port != NULL)
300  DetectPortFree(de_ctx, new_port);
301  if (stack != NULL)
302  SCFree(stack);
303 }
304 
305 /**
306  * \brief Callee function to find all overlapping port ranges as asked
307  * by the detection engine during Stage 2 of signature grouping.
308  *
309  * \param de_ctx Detection Engine Context
310  * \param port Given low port
311  * \param port2 Given high port
312  * \param head Pointer to the head of the tree named PI
313  * \param list Pointer to the list of port objects that needs to be filled/updated
314  */
316  const uint16_t port2, const struct PI *head, DetectPort **list)
317 {
318  if (head == NULL) {
319  SCLogDebug("Tree head should not be NULL. Nothing to do further.");
320  return;
321  }
323  SCLogDebug("Finding overlaps for the range [%d, %d]", port, port2);
324  SCPortIntervalFindOverlaps(de_ctx, port, port2, ptr, list);
325 }
SCPortIntervalNode::max
uint16_t max
Definition: detect-engine-port.h:33
util-port-interval-tree.h
detect-engine-siggroup.h
SigGroupHeadEqual
bool SigGroupHeadEqual(const SigGroupHead *sgha, const SigGroupHead *sghb)
Finds if two Signature Group Heads are the same.
Definition: detect-engine-siggroup.c:480
DetectPortFree
void DetectPortFree(const DetectEngineCtx *de_ctx, DetectPort *dp)
Free a DetectPort and its members.
Definition: detect-engine-port.c:80
IRB_FOREACH_SAFE
#define IRB_FOREACH_SAFE(x, name, head, y)
Definition: interval-tree.h:549
SCLogDebug
#define SCLogDebug(...)
Definition: util-debug.h:269
DetectPort_::port
uint16_t port
Definition: detect.h:218
SCPortIntervalFindOverlappingRanges
void SCPortIntervalFindOverlappingRanges(DetectEngineCtx *de_ctx, const uint16_t port, const uint16_t port2, const struct PI *head, DetectPort **list)
Callee function to find all overlapping port ranges as asked by the detection engine during Stage 2 o...
Definition: util-port-interval-tree.c:315
SCPortIntervalNode::sh
struct SigGroupHead_ * sh
Definition: detect-engine-port.h:35
SC_EINVAL
@ SC_EINVAL
Definition: util-error.h:30
DetectEngineCtx_
main detection engine ctx
Definition: detect.h:841
IRB_ROOT
#define IRB_ROOT(head)
Definition: interval-tree.h:89
DetectPort_::next
struct DetectPort_ * next
Definition: detect.h:231
DetectPort_::sh
struct SigGroupHead_ * sh
Definition: detect.h:228
DetectPort_::port2
uint16_t port2
Definition: detect.h:219
DetectPortInit
DetectPort * DetectPortInit(void)
Alloc a DetectPort structure and update counters.
Definition: detect-engine-port.c:67
SCPortIntervalNode
Definition: detect-engine-port.h:30
SCPortIntervalInsert
int SCPortIntervalInsert(DetectEngineCtx *de_ctx, SCPortIntervalTree *it, const DetectPort *p)
Function to insert a node in the interval tree.
Definition: util-port-interval-tree.c:109
de_ctx
DetectEngineCtx * de_ctx
Definition: fuzz_siginit.c:17
detect-engine-port.h
DetectPort_
Port structure for detection engine.
Definition: detect.h:217
BUG_ON
#define BUG_ON(x)
Definition: suricata-common.h:300
DetectPort_::last
struct DetectPort_ * last
Definition: detect.h:232
SC_OK
@ SC_OK
Definition: util-error.h:27
SCPortIntervalNode::port2
uint16_t port2
Definition: detect-engine-port.h:32
IRB_LEFT
#define IRB_LEFT(elm, field)
Definition: interval-tree.h:85
SCPortIntervalNode::port
uint16_t port
Definition: detect-engine-port.h:31
SigGroupHeadFree
void SigGroupHeadFree(const DetectEngineCtx *de_ctx, SigGroupHead *sgh)
Free a SigGroupHead and its members.
Definition: detect-engine-siggroup.c:162
SCPortIntervalTreeInit
SCPortIntervalTree * SCPortIntervalTreeInit(void)
Function to initialize the interval tree.
Definition: util-port-interval-tree.c:58
SCRealloc
#define SCRealloc(ptr, sz)
Definition: util-mem.h:50
SCPortIntervalTree_::tree
struct PI tree
Definition: util-port-interval-tree.h:30
STACK_SIZE
#define STACK_SIZE
Definition: util-port-interval-tree.c:199
DetectPort_::prev
struct DetectPort_ * prev
Definition: detect.h:230
util-validate.h
SCPortIntervalTree_
Definition: util-port-interval-tree.h:29
SCLogError
#define SCLogError(...)
Macro used to log ERROR messages.
Definition: util-debug.h:261
IRB_RIGHT
#define IRB_RIGHT(elm, field)
Definition: interval-tree.h:86
head
Flow * head
Definition: flow-hash.h:1
SCFree
#define SCFree(p)
Definition: util-mem.h:61
SCPortIntervalTree_::head
SCPortIntervalNode * head
Definition: util-port-interval-tree.h:31
SCCalloc
#define SCCalloc(nm, sz)
Definition: util-mem.h:53
SCReturnInt
#define SCReturnInt(x)
Definition: util-debug.h:275
DEBUG_VALIDATE_BUG_ON
#define DEBUG_VALIDATE_BUG_ON(exp)
Definition: util-validate.h:102
SCPortIntervalTreeFree
void SCPortIntervalTreeFree(DetectEngineCtx *de_ctx, SCPortIntervalTree *it)
Function to free an entire interval tree.
Definition: util-port-interval-tree.c:92
IRB_GENERATE
IRB_GENERATE(PI, SCPortIntervalNode, irb, SCPortIntervalCompareAndUpdate)
SigGroupHeadCopySigs
int SigGroupHeadCopySigs(DetectEngineCtx *de_ctx, SigGroupHead *src, SigGroupHead **dst)
Copies the bitarray holding the sids from the source SigGroupHead to the destination SigGroupHead.
Definition: detect-engine-siggroup.c:401