Description

sg3-141-592

opened on Sep 21, 2023

Issue body actions

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

Activity

1. sg3-141-592

   added

   type-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error

   on Sep 21, 2023
2. serhiy-storchaka

   added this to CSV issues 📊on Sep 21, 2023
3. AA-Turner

   added

   performancePerformance or resource usagePerformance or resource usage

   3.13only security fixesonly security fixes

   on Sep 22, 2023
4. iritkatriel

   added

   stdlibStandard Library Python modules in the Lib/ directoryStandard Library Python modules in the Lib/ directory

   on Nov 24, 2023
5. serhiy-storchaka

   self-assigned this

   on Jan 9, 2024
6. serhiy-storchaka

   closed this as completedin #153694on Jul 21, 2026
7. github-project-automation

   moved this to Done in CSV issues 📊on Jul 21, 2026
8. serhiy-storchaka

   reopened this on Jul 21, 2026
9. serhiy-storchaka

   added

   3.14bugs and security fixesbugs and security fixes

   3.15bugs and security fixesbugs and security fixes

   on Jul 21, 2026
10. serhiy-storchaka commented on Jul 21, 2026

    

    serhiy-storchaka

    on Jul 21, 2026

    Member

    More actions

    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.
11. serhiy-storchaka

    removed their assignment

    on Jul 21, 2026
12. pikammmmm commented on Jul 29, 2026

    

    pikammmmm

    on Jul 29, 2026

    More actions

    Excluding the quote character from the first class reproduces your n=60 numbers
    almost exactly, but the improvement does not hold past them.

    Timing dq_regexp.search() directly on 3.15.0b1 (Windows x86-64, delim ,,
    quote "), sample '"",' * k + '"' * k + '0' + '"' * k + '0':

    sample	3.15	quote excluded from class 1	GH-154868
    302 B	9.86 s	0.235 s	0.0000 s
    402 B	—	0.768 s	0.0000 s
    602 B	—	3.76 s	0.0000 s
    802 B	—	11.9 s	0.0000 s

    So the exclusion buys roughly 2.5x in input length rather than removing the
    blowup — an 802-byte sample costs the "fixed" pattern about what the
    302-byte one cost the unfixed pattern.

    The leading \W* is a second amplifier that the exclusion does not touch:
    \W matches the quote character and every non-word delimiter, so a run of
    commas both supplies start positions for ((delim)|^) and gives \W* more
    ways to split. With '"",' * 3 + ',' * k + '"' * (2 * k) + '0' the exclusion
    variant is back to 7.6 s at 370 bytes.

    GH-154868 stays flat on both shapes — 0.0006 s on a 50 KB sample, about 10^5
    times the size at which the others become unusable. I also checked it still
    detects the doubled quotes the old pattern detected (,"a""b", "a""b",
    x,"a""b",y, "x""y" across a newline, 1,"He said ""hi""",2, "","a""b")
    and still declines the ones it declined (,"",, a,b,c, "plain","fields"):
    0 disagreements with 3.15 on those.

    Mentioning it because I had opened GH-154869 using the exclusion-only change
    and have closed it — the measurements above are why I don't think that
    approach should land on the maintenance branches either.

    Reacted by Serhiy Storchaka
13. Punisheroot

    added 6 commits that reference this issue on Jul 30, 2026

    pythongh-109638: Avoid pathological backtracking in csv.Sniffer

    a45aca2

    pythongh-109638: Avoid pathological backtracking in csv.Sniffer

    7ba94ca

    pythongh-109638: Test literal quotes in unquoted fields

    91680c6

    pythongh-109638: Avoid pathological backtracking in csv.Sniffer

    1705351

    pythongh-109638: Test literal quotes in unquoted fields

    c62c513

    pythongh-109638: Keep space-delimiter matching linear

    d3c62be
14. hugovk

    added a commit that references this issue on Aug 3, 2026

    [3.15] gh-109638: Fix exponential time in csv.Sniffer for doubled quo…

    d52184b
15. serhiy-storchaka

    added 2 commits that reference this issue on Aug 3, 2026

    [3.13] gh-109638: Fix exponential time in csv.Sniffer for doubled quo…

    eaa9bac

    [3.14] gh-109638: Fix exponential time in csv.Sniffer for doubled quo…

    ca87a0a
16. Yhg1s

    added a commit that references this issue on Aug 4, 2026

    [3.12] gh-109638: Fix exponential time in csv.Sniffer for doubled quo…

    94ea52f
17. deadlovelll

    added a commit that references this issue on Aug 5, 2026

    [3.14] pythongh-109638: Fix exponential time in csv.Sniffer for doubl…

    599560c
18. pablogsal

    added 2 commits that reference this issue on Aug 10, 2026

    [3.11] gh-109638: Fix exponential time in csv.Sniffer for doubled quo…

    f4a8862

    [3.10] gh-109638: Fix exponential time in csv.Sniffer for doubled quo…

    19e5024
19. serhiy-storchaka

    closed this as completedon Aug 11, 2026
20. icanhasmath

    added a commit that references this issue on Oct 28, 2026

    [3.10] pythongh-109638: Fix exponential time in csv.Sniffer for doubl…

    5025039

Issue actions