☰

tcpdump 需要 O(n²) 时间来解析过滤器

tag-icon • tag-icon tcpdump
tcpdump 需要 O(n²) 时间来解析过滤器

我tcpdump使用如下过滤器运行：

 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)
)

我的问题是tcpdump启动时需要 O(n²) 时间，而且我有几百行。当它启动时，它工作得很好。看来只有初始化是 O(n²) - 而不是正常处理。

过滤器中的行与运行时的行 有没有一种方法可以tcpdump将初始化优化为 O(n) 或至少 O(n log n)？

我有一个 <ip,port> 表。

编辑

感谢您的想法。到目前为止，它们都给出了 O(n²)。

没有理由等我来测试你的想法。这是一个用于测试的脚本：

#!/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更快，但仍然是 O(n²)。

编辑2：

在其他服务器上重新绘制的图表（即数字无法与之前的图表进行比较）tcpdump和tcpdump -O

有或没有-O

-O显然会让情况变得更糟。

答案1

这看起来像一个错误。我已提交https://github.com/the-tcpdump-group/libpcap/issues/1255

如果您找到解决方法，请发布答案。

答案2

您可以使用特定的 IP 和端口。

例子

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

你应该改变ip和端口

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

相关内容