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상황을 더욱 악화시킬 것이 분명합니다.