Project

General

Profile

Actions

Bug #4581

closed

Excessive qsort/msort time when large number of rules using tls.fingerprint

Added by Jeff Lucovsky over 3 years ago. Updated over 1 year ago.

Status:
Closed
Priority:
Normal
Assignee:
Target version:
Affected Versions:
Effort:
Difficulty:
Label:
Needs backport to 6.0

Description

When a large number of rules using tls.fingerprint are present, perf shows Suricata spending most of its time in qsort.

Is there room for an optimization that performs the sorting once to avoid sorting on the packet path?


Related issues 2 (0 open2 closed)

Related to Suricata - Support #3252: Matching a long list of tls.fingerprint fields is extremly CPU intensiveClosedActions
Related to Suricata - Bug #5565: Excessive qsort/msort time when large number of rules using tls.fingerprint (6.0.x backport)ClosedJeff LucovskyActions
Actions #1

Updated by Jeff Lucovsky about 3 years ago

This doesn't reproduce with modern toolchains (gcc and libc)

Actions #2

Updated by Victor Julien over 2 years ago

  • Related to Support #3252: Matching a long list of tls.fingerprint fields is extremly CPU intensive added
Actions #3

Updated by Victor Julien over 2 years ago

Perhaps we can "fix" this by keeping the keyword but replace the actual implementation with the logic from tls.cert_fingerprint. We do something similar with the legacy uricontent.

Actions #4

Updated by Jeff Lucovsky over 2 years ago

  • Status changed from New to In Review
  • Assignee set to Jeff Lucovsky
Actions #5

Updated by Jeff Lucovsky over 2 years ago

I'm using the rules at https://sslbl.abuse.ch/blacklist/sslblacklist.rules for comparing timing results.

Timing results with modifications

$ time src/suricata -c suricata.yaml -l /tmp/new -r ~/pcap/ -S ~/rules/blacklist.rules
[1657190] 17/9/2022 -- 08:45:31 - (suricata.c:1146) <Notice> (LogVersion) -- This is Suricata version 7.0.0-dev running in USER mode
[1657190] 17/9/2022 -- 08:45:32 - (tm-threads.c:1927) <Notice> (TmThreadWaitOnThreadInit) -- Threads created -> RX: 1 W: 16 FM: 1 FR: 1   Engine started.
[1657190] 17/9/2022 -- 08:47:12 - (suricata.c:2774) <Notice> (SuricataMainLoop) -- Signal Received.  Stopping engine.
[1657204] 17/9/2022 -- 08:47:12 - (source-pcap-file.c:386) <Notice> (ReceivePcapFileThreadExitStats) -- Pcap-file module read 88 files, 24079025 packets, 4356793545 bytes

real    1m41.540s
user    11m12.750s
sys    3m13.117s

Timing results from master commit bb2e11108b3ce5351f3abf45777c47fca37936af

$ time src/suricata -c suricata.yaml -l /tmp/orig -r ~/pcap/ -S ~/rules/blacklist.rules
[1655193] 16/9/2022 -- 11:30:12 - (suricata.c:1146) <Notice> (LogVersion) -- This is Suricata version 7.0.0-dev (bb2e11108b 2022-08-30) running in USER mode
[1655193] 16/9/2022 -- 11:30:12 - (tm-threads.c:1927) <Notice> (TmThreadWaitOnThreadInit) -- Threads created -> RX: 1 W: 16 FM: 1 FR: 1   Engine started.
[1655193] 16/9/2022 -- 12:31:35 - (suricata.c:2774) <Notice> (SuricataMainLoop) -- Signal Received.  Stopping engine.
[1655207] 16/9/2022 -- 12:31:41 - (source-pcap-file.c:386) <Notice> (ReceivePcapFileThreadExitStats) -- Pcap-file module read 88 files, 24079025 packets, 4356793545 bytes

real    61m29.628s
user    894m56.266s
sys     3m16.542s

Note: The following script was contributed by Justin Azoff () to create a rule file using tls.fingerprint. The script can be used to generate a file with an arbitrary number of rules.

 #!/usr/bin/env python3                                                                                                                                                                                                                                                                                                        
 import sys                                                                                                                                                                                                                                                                                                                    
 import random 

 try:                                                                                                                                                                                                                                                                                                                              
    num = int(sys.argv[1])                                                                                                                                                                                                                                                                                                    
 except:                                                                                                                                                                                                                                                                                                                           
    num = 200    

 try:                                                                                                                                                                                                                                                                                                                              
    comment_extra = int(sys.argv[2])                                                                                                                                                                                                                                                                                          
 except:                                                                                                                                                                                                                                                                                                                           
    comment_extra = 0    

 def random_fingerprint():                                                                                                                                                                                                                                                                                                         
    return ":".join([f"{x:02x}" for x in open("/dev/urandom",'rb').read(20)])    

 template='''alert tls $EXTERNAL_NET any -> $HOME_NET any (msg:"Test rule {rule}"; flow: established; tls.fingerprint:"{fingerprint}"; sid:20{rule:05d}; rev:1;)'''

 for rule in range(num):                                                                                                                                                                                                                                                                                                           
    print(template.format(rule=rule, fingerprint=random_fingerprint()))

Actions #6

Updated by Jeff Lucovsky about 2 years ago

  • Status changed from In Review to Closed
Actions #7

Updated by Jeff Lucovsky about 2 years ago

  • Label Needs backport to 6.0 added
Actions #8

Updated by Jeff Lucovsky about 2 years ago

  • Status changed from Closed to Resolved
Actions #9

Updated by Jeff Lucovsky about 2 years ago

  • Subtask #5565 added
Actions #10

Updated by Victor Julien about 2 years ago

  • Target version set to 7.0.0-beta1
Actions #11

Updated by Shivani Bhardwaj about 2 years ago

  • Label deleted (Needs backport to 6.0)
Actions #12

Updated by Victor Julien almost 2 years ago

  • Subtask deleted (#5565)
Actions #13

Updated by Victor Julien almost 2 years ago

  • Related to Bug #5565: Excessive qsort/msort time when large number of rules using tls.fingerprint (6.0.x backport) added
Actions #14

Updated by Victor Julien almost 2 years ago

  • Status changed from Resolved to Closed
Actions #15

Updated by Jeff Lucovsky over 1 year ago

  • Status changed from Closed to Resolved
  • Label Needs backport to 6.0 added

Re-opening for 6.0.x backport

Actions #16

Updated by Victor Julien over 1 year ago

  • Status changed from Resolved to Closed
Actions

Also available in: Atom PDF