Project

General

Profile

Actions

Bug #4581

closed
JL JL

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

Bug #4581: Excessive qsort/msort time when large number of rules using tls.fingerprint

Added by Jeff Lucovsky over 4 years ago. Updated almost 3 years 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

JL Updated by Jeff Lucovsky over 4 years ago Actions #1

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

VJ Updated by Victor Julien over 3 years ago Actions #2

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

VJ Updated by Victor Julien over 3 years ago Actions #3

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.

JL Updated by Jeff Lucovsky over 3 years ago Actions #4

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

JL Updated by Jeff Lucovsky over 3 years ago Actions #5

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

JL Updated by Jeff Lucovsky over 3 years ago Actions #6

  • Status changed from In Review to Closed

JL Updated by Jeff Lucovsky over 3 years ago Actions #7

  • Label Needs backport to 6.0 added

JL Updated by Jeff Lucovsky over 3 years ago Actions #8

  • Status changed from Closed to Resolved

JL Updated by Jeff Lucovsky over 3 years ago Actions #9

  • Subtask #5565 added

VJ Updated by Victor Julien over 3 years ago Actions #10

  • Target version set to 7.0.0-beta1

SB Updated by Shivani Bhardwaj over 3 years ago Actions #11

  • Label deleted (Needs backport to 6.0)

VJ Updated by Victor Julien over 3 years ago Actions #12

  • Subtask deleted (#5565)

VJ Updated by Victor Julien over 3 years ago Actions #13

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

VJ Updated by Victor Julien over 3 years ago Actions #14

  • Status changed from Resolved to Closed

JL Updated by Jeff Lucovsky almost 3 years ago Actions #15

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

Re-opening for 6.0.x backport

VJ Updated by Victor Julien almost 3 years ago Actions #16

  • Status changed from Resolved to Closed
Actions

Also available in: PDF Atom