tcpdump takes O(n²) time to parse filter

Question

I run tcpdump with a filter like:

 not (
     (host 1.165.155.169 and port 4444)
  or (host 1.168.68.116 and port 4444)
  or (host 1.173.192.253 and port 4444)
  or (host 1.174.97.43 and port 4444)
  :
  or (host 161.138.104.1 and port 58339)
)

My problem is that tcpdump takes O(n²) time when starting, and I have several 100s of lines. When it is started, it works fine. It seems it is only the initialization that is O(n²) - not the normal processing.

Is there a way I can tell tcpdump to optimize initialization to O(n) or at least O(n log n)?

I have a table of <ip,port>.

EDIT

Thanks for the ideas. So far all of them give O(n²).

There is no reason to wait for me to test your idea. Here is a script to test with:

#!/bin/bash
Make some network noise
(sudo nice nice ping -f localhost >/dev/null) &
noisepid=$!
filter() {
    # $1 = How many entries?

    perl -e '

        $pre = "not (";

        $post = ")";

        $join = " and ";

        sub hostport {

          $host = sprintf "%d.%d.%d.%d", rand()255,rand()255,rand()255,rand()255;

          $port = sprintf "%d", rand()*65535;

          return "(host $host and port $port)";

        }

        print $pre, join($join,map { hostport() } 1..shift), $post;

    ' $1
}
export -f filter
seq 400 | parallel --joblog my.log 'sudo tcpdump -ni any "filter {}"|read a'
kill -9 $noisepid
field - https://codeberg.org/tange/tangetools/src/branch/master/field
plotpipe - https://codeberg.org/tange/tangetools/src/branch/master/plotpipe
field 14,4 < my.log | sort -n | plotpipe

tcpdump -F file is faster, but still O(n²).

EDIT2:

Graphs re-done on other server (i.e. the numbers cannot be compared with previous graph) with tcpdump and tcpdump -O

-O clearly makes it worse.

Answer 1

This looks like a bug. I have filed https://github.com/the-tcpdump-group/libpcap/issues/1255

Post an answer if you find a work-around.

Answer 2

You can work with specific IPs and ports.

Example

sudo tcpdump -n src 000.00.0.255 and tcp port 80 #You only see a packet

you should change the ip and port

sudo tcpdump -n src 000.00.0.255 and tcp port 80 > myipandport.txt #If you need to save the information