Repository: deepset-ai/haystack
Pull request: fix: make `SentenceSplitter` QUOTE_SPANS_RE regex ReDoS-safe
### Related Issues

- fixes #9315 

### Proposed Changes:

Replaced the vulnerable regular expression pattern in QUOTE_SPANS_RE inside SentenceSplitter with a ReDoS-safe alternative.

### How did you test it?

- Ran unit tests locally using hatch run test:unit
- Ensured that all pre-commit hooks passed

### Notes for the reviewer

- This was originally from this [PR ](https://github.com/deepset-ai/haystack/pull/9335) - but due to the way I cloned the repo/branch or permissions I (@davidsbatista) could not push my changes into the community member PR, therefore this new one. Still, user commits are tracked on this PR, and he will be credited as contributor.

### Checklist

- I have read the [contributors guidelines](https://github.com/deepset-ai/haystack/blob/main/CONTRIBUTING.md) and the [code of conduct](https://github.com/deepset-ai/haystack/blob/main/code_of_conduct.txt)
- I have updated the related issue with new insights and changes
- I added unit tests and updated the docstrings
- I've used one of the [conventional commit types](https://www.conventionalcommits.org/en/v1.0.0/) for my PR title: `fix:`, `feat:`, `build:`, `chore:`, `ci:`, `docs:`, `style:`, `refactor:`, `perf:`, `test:` and added `!` in case the PR includes breaking changes.
- I documented my code
- I ran [pre-commit hooks](https://github.com/deepset-ai/haystack/blob/main/CONTRIBUTING.md#installation) and fixed any issue


Problem statement:
Potential REDoS Vulnerability in Haystack SentenceSplitter
We found a REDoS vulnerability in Haystack's `SentenceSplitter`.

- Problematic regex: `QUOTE_SPANS_RE` (`\W(\"+|\'+).*?\1`)
- Issue: Specially crafted input can cause catastrophic backtracking, leading to a potential DoS.

Reproduction:
```python
import time
from haystack.components.preprocessors.sentence_tokenizer import SentenceSplitter


splitter = SentenceSplitter()
text = ' ' + '"' * 20 + 'A' * 500000000 + 'B'
start = time.time()
result = splitter.split_sentences(text)
end = time.time()

print(f"Execution Time: {end - start:.2f} seconds")

# Execution Time: 33.77 seconds
```

- Execution time increases dramatically with this input.

Version: v2.13.1 (latest as of April 26, 2025).

Vulnerable function: `SentenceSplitter._apply_split_rules()`

Hints from issue discussion:
Hello @waiveyk The pattern is used in a controlled context within the SentenceSplitter component, which is primarily used for document splitting and text processing. The input to this component typically comes from document content rather than user input. That means the 500 million 'A’ characters in the example above would need to be part of such document content and they would need to be passed to a SentenceSplitter component, which is expected to be part of an indexing pipeline, where other components typically already limit the number of input characters.
Still, I agree the code could be improved so feel free to open a PR if you would like to contribute to Haystack!
Could you please advise on the preferred direction for the fix?
Would adjusting the regular expression be an acceptable approach, or would you recommend a different solution?

Commit message: Update test/components/preprocessors/test_sentence_tokenizer.py

Co-authored-by: Stefano Fiorucci <stefanofiorucci@gmail.com>

Patch to review:
diff --git a/haystack/components/preprocessors/sentence_tokenizer.py b/haystack/components/preprocessors/sentence_tokenizer.py
index 2cb77347d3..6d38d14ec7 100644
--- a/haystack/components/preprocessors/sentence_tokenizer.py
+++ b/haystack/components/preprocessors/sentence_tokenizer.py
@@ -40,7 +40,7 @@
     "ml": "malayalam",
 }
 
-QUOTE_SPANS_RE = re.compile(r"\W(\"+|\'+).*?\1")
+QUOTE_SPANS_RE = re.compile(r'"[^"]*"|\'[^\']*\'')
 
 if nltk_imports.is_successful():
 
diff --git a/releasenotes/notes/SentenceSplitter-ReDoS-fix-ca91b020cab50bf6.yaml b/releasenotes/notes/SentenceSplitter-ReDoS-fix-ca91b020cab50bf6.yaml
new file mode 100644
index 0000000000..d66f68c97a
--- /dev/null
+++ b/releasenotes/notes/SentenceSplitter-ReDoS-fix-ca91b020cab50bf6.yaml
@@ -0,0 +1,7 @@
+---
+security:
+  - |
+    Made QUOTE_SPANS_RE regex ReDoS-safe. This prevents potential catastrophic backtracking on malicious inputs
+fixes:
+  - |
+    Fixed a potential ReDoS issue in QUOTE_SPANS_RE regex used inside the SentenceSplitter component.
diff --git a/test/components/preprocessors/test_sentence_tokenizer.py b/test/components/preprocessors/test_sentence_tokenizer.py
index f8aaf68fa7..5f22d960de 100644
--- a/test/components/preprocessors/test_sentence_tokenizer.py
+++ b/test/components/preprocessors/test_sentence_tokenizer.py
@@ -1,8 +1,10 @@
+import time
 import pytest
 from unittest.mock import patch
 from pathlib import Path
 
 from haystack.components.preprocessors.sentence_tokenizer import SentenceSplitter
+from haystack.components.preprocessors.sentence_tokenizer import QUOTE_SPANS_RE
 
 from pytest import LogCaptureFixture
 
@@ -65,3 +67,48 @@ def test_read_abbreviations_missing_file(caplog: LogCaptureFixture):
         result = SentenceSplitter._read_abbreviations("pt")
         assert result == []
         assert "No abbreviations file found for pt. Using default abbreviations." in caplog.text
+
+
+def test_quote_spans_regex():
+    # double quotes
+    text1 = 'He said "Hello world" and left.'
+    matches1 = list(QUOTE_SPANS_RE.finditer(text1))
+    assert len(matches1) == 1
+    assert matches1[0].group() == '"Hello world"'
+
+    # single quotes
+    text2 = "She replied 'Goodbye world' and smiled."
+    matches2 = list(QUOTE_SPANS_RE.finditer(text2))
+    assert len(matches2) == 1
+    assert matches2[0].group() == "'Goodbye world'"
+
+    # multiple quotes
+    text3 = 'First "quote" and second "quote" in same text.'
+    matches3 = list(QUOTE_SPANS_RE.finditer(text3))
+    assert len(matches3) == 2
+    assert matches3[0].group() == '"quote"'
+    assert matches3[1].group() == '"quote"'
+
+    # quotes containing newlines
+    text4 = 'Text with "quote\nspanning\nmultiple\nlines"'
+    matches4 = list(QUOTE_SPANS_RE.finditer(text4))
+    assert len(matches4) == 1
+    assert matches4[0].group() == '"quote\nspanning\nmultiple\nlines"'
+
+    # no quotes
+    text5 = "This text has no quotes."
+    matches5 = list(QUOTE_SPANS_RE.finditer(text5))
+    assert len(matches5) == 0
+
+
+def test_split_sentences_performance() -> None:
+    # make sure our regex is not vulnerable to Regex Denial of Service (ReDoS)
+    # https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
+    # this is a very long string, roughly 500 MB, but it should not take more than 2 seconds to process
+    splitter = SentenceSplitter()
+    text = " " + '"' * 20 + "A" * 50000000 + "B"
+    start = time.time()
+    _ = splitter.split_sentences(text)
+    end = time.time()
+
+    assert end - start < 2, f"Execution time exceeded 2 seconds: {end - start:.2f} seconds"


Code review comments:
diff_hunk: @@ -65,3 +67,48 @@ def test_read_abbreviations_missing_file(caplog: LogCaptureFixture):
         result = SentenceSplitter._read_abbreviations("pt")
         assert result == []
         assert "No abbreviations file found for pt. Using default abbreviations." in caplog.text
+
+
+def test_quote_spans_regex():
+    # double quotes
+    text1 = 'He said "Hello world" and left.'
+    matches1 = list(QUOTE_SPANS_RE.finditer(text1))
+    assert len(matches1) == 1
+    assert matches1[0].group() == '"Hello world"'
+
+    # single quotes
+    text2 = "She replied 'Goodbye world' and smiled."
+    matches2 = list(QUOTE_SPANS_RE.finditer(text2))
+    assert len(matches2) == 1
+    assert matches2[0].group() == "'Goodbye world'"
+
+    # multiple quotes
+    text3 = 'First "quote" and second "quote" in same text.'
+    matches3 = list(QUOTE_SPANS_RE.finditer(text3))
+    assert len(matches3) == 2
+    assert matches3[0].group() == '"quote"'
+    assert matches3[1].group() == '"quote"'
+
+    # quotes containing newlines
+    text4 = 'Text with "quote\nspanning\nmultiple\nlines"'
+    matches4 = list(QUOTE_SPANS_RE.finditer(text4))
+    assert len(matches4) == 1
+    assert matches4[0].group() == '"quote\nspanning\nmultiple\nlines"'
+
+    # no quotes
+    text5 = "This text has no quotes."
+    matches5 = list(QUOTE_SPANS_RE.finditer(text5))
+    assert len(matches5) == 0
+
+
+def test_split_sentences_performance() -> None:
+    # make sure our regex is not vulnerable to Regex Denial of Service (ReDoS)
+    # https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
+    # this is a very long string, roughly 500 MB, but it should not take more than 2 seconds to process
path: test/components/preprocessors/test_sentence_tokenizer.py
text: @author:
```suggestion
    # this is a very long string, roughly 50 MB, but it should not take more than 2 seconds to process
```