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.
tcpdump
does here is compile your filter into a reduced-as-possible form. What you could try is of course could be that optimizer: Say instead of "not ( ⋃ᵢ(host Hᵢ and port Pᵢ))" do something like "not ( ⋃ᵢ (Port Pᵢ and (⋃ᵣ host Hᵢᵣ)))", if there's many hosts for one port. Generally, however, this is a satisfiability problem… and thus rather hard computationally. – Marcus Müller Jan 17 '24 at 23:28-O
? That would disable the optimization done inpcap_compile
that I suspected in my first comment. If that changes things, you can usesudo perf record -ag --symbols=pcap_compile tcpdump …
to track where the pcap library spends its time (show the results usingperf report
; gets more useful with debugging symbols for libpcap) – Marcus Müller Jan 18 '24 at 10:42