2

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.

Lines in filter vs runtime 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

with or without -O

-O clearly makes it worse.

Ole Tange
  • 35,514
  • 1
    I suspect (haven't checked the source code) that what 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
  • @MarcusMüller For testing I simply removed the port. It is faster, but still takes O(n²) to initialize. – Ole Tange Jan 17 '24 at 23:44
  • Do you launch tcpdump -n ? – MC68020 Jan 17 '24 at 23:48
  • @MC68020 Yes. The problem is clearly not DNS: The CPU is running at 100% during initialization. – Ole Tange Jan 18 '24 at 00:35
  • 1
    Applying De Morgan’s laws might help: instead of “not ((h1 and p1) or (h2 and p2) …)”, “not (h1 and p1) and not (h2 and p2) …” – Stephen Kitt Jan 18 '24 at 05:35
  • @StephenKitt This also gives O(n²). – Ole Tange Jan 18 '24 at 09:35
  • @OleTange things also don't get better with -O? That would disable the optimization done in pcap_compile that I suspected in my first comment. If that changes things, you can use sudo perf record -ag --symbols=pcap_compile tcpdump … to track where the pcap library spends its time (show the results using perf report; gets more useful with debugging symbols for libpcap) – Marcus Müller Jan 18 '24 at 10:42
  • (I don't know about the actual issue, but at least the graph looks worse than O(n^2) to me. The y-value at x=150 is about 3, but at x=300, it's already > 40, way more than a four-fold increase you'd expect for a quadratic relation.) – ilkkachu Jan 18 '24 at 13:24
  • (@ilkkachu Fair point. My n² was purely eyeballing it - it was clearly not O(n log n) ) – Ole Tange Jan 18 '24 at 21:58
  • @MarcusMüller See new graph: -O did not help. perf gives me: "+ 23.42% 23.42% tcpdump libpcap.so.1.10.1 [.] 00000000000262bc" (The --symbols=pcap_compile did not work). – Ole Tange Jan 18 '24 at 23:20
  • @OleTange Interesting! So, it is within libpcap, but not the rule optimization. Sadly, we only get a position, not a function name. I'd guess that gets better when you do get debug symbols to libpcap, but I can't guarantee it. – Marcus Müller Jan 19 '24 at 08:14

2 Answers2

0

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.

Ole Tange
  • 35,514
-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
Chris Davies
  • 116,213
  • 16
  • 160
  • 287
jilkao
  • 1
  • 2
    Did you miss the 'not' in the filter? I am not looking for packets from these servers. I am looking for all other packets. – Ole Tange Jan 18 '24 at 00:36