csv.Sniffer regular expression has significant backtracing

[sg3-141-592]

Bug report

Bug description:

You can pass strings to csv.Sniffer that can generate significant Regex backtracing and processing time. For example

import csv
import time
 
NUM_ITERATIONS=200
# Example test str "","",""0""0
test_str = '"",'*NUM_ITERATIONS + '"'*NUM_ITERATIONS + '0' + '"'*NUM_ITERATIONS + '0'
print(test_str)
 
t0 = time.time()
 
dialect = csv.Sniffer().sniff(test_str)
 
t1 = time.time()
print(f"{t1-t0}")

Some example runs

NUM_ITERATIONS Running Time (seconds)
1              0.0008
10             0.0030
100            254.32

I've checked against different versions of Python and they all return similar results.

For input NUM_ITERATIONS 100 above
Version       : Running Time (Seconds)
Python 3.8.16 : 254
Python 3.9.16 : 250
Python 3.10.9 : 319
Python 3.11.1 : 236

This issue lies in this Regex for finding double quoted format

cpython/Lib/csv.py

Line 274 in b303d3a

r"((%(delim)s)|^)\W*%(quote)s[^%(delim)s\n]*%(quote)s[^%(delim)s\n]*%(quote)s\W*((%(delim)s)|$)" % \

I've done some testing and a zero length lookahead assertion (or atomic group) you can get a significant performance improvement

r"((%(delim)s)|^)\W*%(quote)s(?=(?P<zero>[^%(delim)s%(quote)s\n]*))(?P=zero)%(quote)s[^%(delim)s\n]*%(quote)s\W*((%(delim)s)|$)" % \

CPython versions tested on:

3.8, 3.9, 3.10, 3.11

Operating systems tested on:

Linux

Linked PRs

• gh-109638: Fix for significant backtracking in csv.Sniffer #109639
• [3.15] gh-109638: Avoid pathological backtracking in csv.Sniffer (GH-153694) #154865
• [3.15] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes #154868
• [3.15] gh-109638: Fix excessive backtracking in csv.Sniffer doublequote detection #154869
• [3.14] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (GH-154868) #155112
• [3.13] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (GH-154868) #155113
• [3.12] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (GH-154868) (GH-155113) #155114
• [3.11] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (GH-154868) (GH-155113) #155115
• [3.10] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (GH-154868) (GH-155113) #155116

[serhiy-storchaka]

Fixed in 3.16 by the csv.Sniffer rewrite (gh-83273): these regular expressions no longer exist, and your example is now instant even for 200 iterations. There is a test for it.

The maintenance branches are still affected, and a targeted fix for them is welcome. Excluding the quote character from the character class, as the lookahead variant in the first message does, reduces the time for 60 iterations from 11 s to 0.3 s on 3.15. The atomic group proposed in GH-109639 does not work: it makes the regular expression unmatchable and silently disables the doublequote detection.