CVE-2022-31052: Uncontrolled Recursion (CWE-674)
value: Synapse is an open source home server implementation for the Matrix chat network. In versions prior to 1.61.1 URL previews of some web pages can exhaust the available stack space for the Synapse process due to unbounded recursion. This is sometimes recoverable and leads to an error for the request causing the problem, but in other cases the Synapse process may crash altogether. It is possible to exploit this maliciously, either by malicious users on the homeserver, or by remote users sending URLs that a local user's client may automatically request a URL preview for. Remote users are not able to exploit this directly, because the URL preview endpoint is authenticated. Deployments with `url_preview_enabled: false` set in configuration are not affected. Deployments with `url_preview_enabled: true` set in configuration **are** affected. Deployments with no configuration value set for `url_preview_enabled` are not affected, because the default is `false`. Administrators of homeservers with URL previews enabled are advised to upgrade to v1.61.1 or higher. Users unable to upgrade should set `url_preview_enabled` to false.
CWE description: The product does not properly control the amount of recursion that takes place,  consuming excessive resources, such as allocated memory or the program stack.
CVSS v3 base score: 6.5
Published: 2022-06-28T17:15Z
Repository: https://github.com/matrix-org/synapse
Language: Python
Files changed: synapse/rest/media/v1/preview_html.py, tests/rest/media/v1/test_html_preview.py
Commit date: 2022-06-28 14:29:08 +0100
Commit message: Merge pull request from GHSA-22p3-qrh9-cx32

* Make _iterate_over_text easier to read by using simple data structures

* Prefer a set of tags to ignore

In my tests, it's 4x faster to check for containment in a set of this size

* Add a stack size limit to _iterate_over_text

* Continue accepting the case where there is no body element

* Use an early return instead for None

Co-authored-by: Richard van der Hoff <richard@matrix.org>
Diff: diff --git a/synapse/rest/media/v1/preview_html.py b/synapse/rest/media/v1/preview_html.py
index ed8f21a483..5f334f4634 100644
--- a/synapse/rest/media/v1/preview_html.py
+++ b/synapse/rest/media/v1/preview_html.py
@@ -10,14 +10,13 @@
 # distributed under the License is distributed on an "AS IS" BASIS,
 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 # See the License for the specific language governing permissions and
 # limitations under the License.
 import codecs
-import itertools
 import logging
 import re
-from typing import TYPE_CHECKING, Dict, Generator, Iterable, Optional, Set, Union
+from typing import TYPE_CHECKING, Dict, Generator, Iterable, List, Optional, Set, Union
 
 if TYPE_CHECKING:
     from lxml import etree
 
 logger = logging.getLogger(__name__)
@@ -274,11 +273,11 @@ def parse_html_description(tree: "etree.Element") -> Optional[str]:
     """
     # We don't just use XPATH here as that is slow on some machines.
 
     from lxml import etree
 
-    TAGS_TO_REMOVE = (
+    TAGS_TO_REMOVE = {
         "header",
         "nav",
         "aside",
         "footer",
         "script",
@@ -289,35 +288,46 @@ def parse_html_description(tree: "etree.Element") -> Optional[str]:
         "video",
         "canvas",
         "img",
         "picture",
         etree.Comment,
-    )
+    }
 
     # Split all the text nodes into paragraphs (by splitting on new
     # lines)
     text_nodes = (
         re.sub(r"\s+", "\n", el).strip()
-        for el in _iterate_over_text(tree.find("body"), *TAGS_TO_REMOVE)
+        for el in _iterate_over_text(tree.find("body"), TAGS_TO_REMOVE)
     )
     return summarize_paragraphs(text_nodes)
 
 
 def _iterate_over_text(
-    tree: "etree.Element", *tags_to_ignore: Union[str, "etree.Comment"]
+    tree: Optional["etree.Element"],
+    tags_to_ignore: Set[Union[str, "etree.Comment"]],
+    stack_limit: int = 1024,
 ) -> Generator[str, None, None]:
     """Iterate over the tree returning text nodes in a depth first fashion,
     skipping text nodes inside certain tags.
+
+    Args:
+        tree: The parent element to iterate. Can be None if there isn't one.
+        tags_to_ignore: Set of tags to ignore
+        stack_limit: Maximum stack size limit for depth-first traversal.
+            Nodes will be dropped if this limit is hit, which may truncate the
+            textual result.
+            Intended to limit the maximum working memory when generating a preview.
     """
-    # This is basically a stack that we extend using itertools.chain.
-    # This will either consist of an element to iterate over *or* a string
+
+    if tree is None:
+        return
+
+    # This is a stack whose items are elements to iterate over *or* strings
     # to be returned.
-    elements = iter([tree])
-    while True:
-        el = next(elements, None)
-        if el is None:
-            return
+    elements: List[Union[str, "etree.Element"]] = [tree]
+    while elements:
+        el = elements.pop()
 
         if isinstance(el, str):
             yield el
         elif el.tag not in tags_to_ignore:
             # If the element isn't meant for display, ignore it.
@@ -327,21 +337,26 @@ def _iterate_over_text(
             # el.text is the text before the first child, so we can immediately
             # return it if the text exists.
             if el.text:
                 yield el.text
 
-            # We add to the stack all the elements children, interspersed with
-            # each child's tail text (if it exists). The tail text of a node
-            # is text that comes *after* the node, so we always include it even
-            # if we ignore the child node.
-            elements = itertools.chain(
-                itertools.chain.from_iterable(  # Basically a flatmap
-                    [child, child.tail] if child.tail else [child]
-                    for child in el.iterchildren()
-                ),
-                elements,
-            )
+            # We add to the stack all the element's children, interspersed with
+            # each child's tail text (if it exists).
+            #
+            # We iterate in reverse order so that earlier pieces of text appear
+            # closer to the top of the stack.
+            for child in el.iterchildren(reversed=True):
+                if len(elements) > stack_limit:
+                    # We've hit our limit for working memory
+                    break
+
+                if child.tail:
+                    # The tail text of a node is text that comes *after* the node,
+                    # so we always include it even if we ignore the child node.
+                    elements.append(child.tail)
+
+                elements.append(child)
 
 
 def summarize_paragraphs(
     text_nodes: Iterable[str], min_size: int = 200, max_size: int = 500
 ) -> Optional[str]:
diff --git a/tests/rest/media/v1/test_html_preview.py b/tests/rest/media/v1/test_html_preview.py
index ea9e5889bf..61357622bd 100644
--- a/tests/rest/media/v1/test_html_preview.py
+++ b/tests/rest/media/v1/test_html_preview.py
@@ -368,10 +368,27 @@ class OpenGraphFromHtmlTestCase(unittest.TestCase):
         """
         tree = decode_body(html, "http://example.com/test.html")
         og = parse_html_to_open_graph(tree)
         self.assertEqual(og, {"og:title": "ó", "og:description": "Some text."})
 
+    def test_nested_nodes(self) -> None:
+        """A body with some nested nodes. Tests that we iterate over children
+        in the right order (and don't reverse the order of the text)."""
+        html = b"""
+        <a href="somewhere">Welcome <b>the bold <u>and underlined text <svg>
+        with a cheeky SVG</svg></u> and <strong>some</strong> tail text</b></a>
+        """
+        tree = decode_body(html, "http://example.com/test.html")
+        og = parse_html_to_open_graph(tree)
+        self.assertEqual(
+            og,
+            {
+                "og:title": None,
+                "og:description": "Welcome\n\nthe bold\n\nand underlined text\n\nand\n\nsome\n\ntail text",
+            },
+        )
+
 
 class MediaEncodingTestCase(unittest.TestCase):
     def test_meta_charset(self) -> None:
         """A character encoding is found via the meta tag."""
         encodings = _get_html_media_encodings(

Vulnerable code: import itertools
from typing import TYPE_CHECKING, Dict, Generator, Iterable, Optional, Set, Union
    TAGS_TO_REMOVE = (
    )
        for el in _iterate_over_text(tree.find("body"), *TAGS_TO_REMOVE)
    tree: "etree.Element", *tags_to_ignore: Union[str, "etree.Comment"]
    # This is basically a stack that we extend using itertools.chain.
    # This will either consist of an element to iterate over *or* a string
    elements = iter([tree])
    while True:
        el = next(elements, None)
        if el is None:
            return
            # We add to the stack all the elements children, interspersed with
            # each child's tail text (if it exists). The tail text of a node
            # is text that comes *after* the node, so we always include it even
            # if we ignore the child node.
            elements = itertools.chain(
                itertools.chain.from_iterable(  # Basically a flatmap
                    [child, child.tail] if child.tail else [child]
                    for child in el.iterchildren()
                ),
                elements,
            )
Fixed code: from typing import TYPE_CHECKING, Dict, Generator, Iterable, List, Optional, Set, Union
    TAGS_TO_REMOVE = {
    }
        for el in _iterate_over_text(tree.find("body"), TAGS_TO_REMOVE)
    tree: Optional["etree.Element"],
    tags_to_ignore: Set[Union[str, "etree.Comment"]],
    stack_limit: int = 1024,

    Args:
        tree: The parent element to iterate. Can be None if there isn't one.
        tags_to_ignore: Set of tags to ignore
        stack_limit: Maximum stack size limit for depth-first traversal.
            Nodes will be dropped if this limit is hit, which may truncate the
            textual result.
            Intended to limit the maximum working memory when generating a preview.

    if tree is None:
        return

    # This is a stack whose items are elements to iterate over *or* strings
    elements: List[Union[str, "etree.Element"]] = [tree]
    while elements:
        el = elements.pop()
            # We add to the stack all the element's children, interspersed with
            # each child's tail text (if it exists).
            #
            # We iterate in reverse order so that earlier pieces of text appear
            # closer to the top of the stack.
            for child in el.iterchildren(reversed=True):
                if len(elements) > stack_limit:
                    # We've hit our limit for working memory
                    break

                if child.tail:
                    # The tail text of a node is text that comes *after* the node,
                    # so we always include it even if we ignore the child node.
                    elements.append(child.tail)

                elements.append(child)
    def test_nested_nodes(self) -> None:
        """A body with some nested nodes. Tests that we iterate over children
        in the right order (and don't reverse the order of the text)."""
        html = b"""
        <a href="somewhere">Welcome <b>the bold <u>and underlined text <svg>
        with a cheeky SVG</svg></u> and <strong>some</strong> tail text</b></a>
        """
        tree = decode_body(html, "http://example.com/test.html")
        og = parse_html_to_open_graph(tree)
        self.assertEqual(
            og,
            {
                "og:title": None,
                "og:description": "Welcome\n\nthe bold\n\nand underlined text\n\nand\n\nsome\n\ntail text",
            },
        )