CVE-2023-47163: Uncontrolled Recursion (CWE-674)
value: Remarshal prior to v0.17.1 expands YAML alias nodes unlimitedly, hence Remarshal is vulnerable to Billion Laughs Attack. Processing untrusted YAML files may cause a denial-of-service (DoS) condition.
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: 7.5
Published: 2023-11-13T03:15Z
Repository: https://github.com/remarshal-project/remarshal
Language: Python
Files changed: pyproject.toml, remarshal.py, tests/lol.yml, tests/test_remarshal.py
Commit date: 2023-09-05 13:14:32 +0000
Commit message: fix(yaml): limit maximum nodes

Prevent a billion laughs attack carried out with YAML anchors.

Thanks to Taichi Kotake of Akatsuki Inc. for finding this vulnerability
and to JPCERT/CC for reporting it.

JVN#86156389

Diff: diff --git a/pyproject.toml b/pyproject.toml
index f6267a6..4786c20 100644
--- a/pyproject.toml
+++ b/pyproject.toml
@@ -1,8 +1,8 @@
 [tool.poetry]
 name = "Remarshal"
-version = "0.17.0"
+version = "0.17.1"
 description = "Convert between CBOR, JSON, MessagePack, TOML, and YAML"
 authors = ["D. Bohdan <dbohdan@dbohdan.com>"]
 license = "MIT"
 readme = "README.md"
 repository = "https://github.com/remarshal-project/remarshal"
@@ -134,12 +134,13 @@ target-version = "py37"
 [tool.ruff.mccabe]
 max-complexity = 14
 
 [tool.ruff.pylint]
 allow-magic-value-types = ["int", "str"]
-max-args = 11
-max-branches = 19
+max-args = 12
+max-branches = 20
+max-statements = 100
 
 [tool.ruff.per-file-ignores]
 "remarshal.py" = ["ARG001", "B904", "EM103", "RET506", "S506", "SIM115"]
 "tests/test_remarshal.py" = ["F841", "PT011"]
 "tests/*" = ["S101"]
diff --git a/remarshal.py b/remarshal.py
index 91cde12..2e29634 100755
--- a/remarshal.py
+++ b/remarshal.py
@@ -22,12 +22,13 @@ import tomlkit.items
 import umsgpack  # type: ignore
 import yaml
 import yaml.parser
 import yaml.scanner
 
-__version__ = "0.17.0"
+__version__ = "0.17.1"
 
+DEFAULT_MAX_NODES = 100000
 FORMATS = ["cbor", "json", "msgpack", "toml", "yaml"]
 
 
 # === YAML ===
 
@@ -140,10 +141,19 @@ def parse_command_line(argv: List[str]) -> argparse.Namespace:  # noqa: C901.
                 "Turn into strings boolean, date-time, and null keys for JSON "
                 "and TOML and null values for TOML"
             ),
         )
 
+    parser.add_argument(
+        "--max-nodes",
+        dest="max_nodes",
+        metavar="n",
+        type=int,
+        default=DEFAULT_MAX_NODES,
+        help="maximum number of nodes in input data (default %(default)s)",
+    )
+
     output_group = parser.add_mutually_exclusive_group()
     output_group.add_argument("output", nargs="?", default="-", help="output file")
     output_group.add_argument(
         "-o",
         "--output",
@@ -429,10 +439,31 @@ def decode(input_format: str, input_data: bytes) -> Document:
         raise ValueError(msg)
 
     return decoder[input_format](input_data)
 
 
+class TooManyNodesError(BaseException):
+    def __init__(self, msg: str = "document has too many nodes", *args, **kwargs):
+        super().__init__(msg, *args, **kwargs)
+
+
+def validate_node_count(doc: Document, *, limit: int) -> None:
+    count = 0
+
+    def count_callback(x: Any) -> Any:
+        nonlocal count
+        nonlocal limit
+
+        count += 1
+        if count > limit:
+            raise TooManyNodesError
+
+        return x
+
+    traverse(doc, instance_callbacks={(object, count_callback)})
+
+
 def reject_special_keys(key: Any) -> Any:
     if isinstance(key, bool):
         msg = "boolean key"
         raise TypeError(msg)
     if isinstance(key, datetime.datetime):
@@ -625,10 +656,11 @@ def run(argv: List[str]) -> None:
         args.input,
         args.output,
         args.input_format,
         args.output_format,
         json_indent=args.json_indent,
+        max_nodes=args.max_nodes,
         ordered=args.ordered,
         stringify=args.stringify,
         unwrap=args.unwrap,
         wrap=args.wrap,
         yaml_options=args.yaml_options,
@@ -640,10 +672,11 @@ def remarshal(
     output: Path | str,
     input_format: str,
     output_format: str,
     *,
     json_indent: Union[int, None] = None,
+    max_nodes: int = DEFAULT_MAX_NODES,
     ordered: bool = True,
     stringify: bool = False,
     transform: Union[Callable[[Document], Document], None] = None,
     unwrap: Union[str, None] = None,
     wrap: Union[str, None] = None,
@@ -661,10 +694,12 @@ def remarshal(
             msg = "input_data must be bytes"
             raise TypeError(msg)
 
         parsed = decode(input_format, input_data)
 
+        validate_node_count(parsed, limit=max_nodes)
+
         if unwrap is not None:
             if not isinstance(parsed, Mapping):
                 msg = (
                     f"Top-level value of type '{type(parsed).__name__}' "
                     "cannot be unwrapped"
@@ -699,11 +734,11 @@ def remarshal(
 def main() -> None:
     try:
         run(sys.argv)
     except KeyboardInterrupt:
         pass
-    except (OSError, TypeError, ValueError) as e:
+    except (OSError, TooManyNodesError, TypeError, ValueError) as e:
         print(f"Error: {e}", file=sys.stderr)  # noqa: T201
         sys.exit(1)
 
 
 if __name__ == "__main__":
diff --git a/tests/lol.yml b/tests/lol.yml
new file mode 100644
index 0000000..1885633
--- /dev/null
+++ b/tests/lol.yml
@@ -0,0 +1,10 @@
+lol1: &lol1 "lol" 
+lol2: &lol2 [*lol1,*lol1,*lol1,*lol1,*lol1,*lol1,*lol1,*lol1,*lol1] 
+lol3: &lol3 [*lol2,*lol2,*lol2,*lol2,*lol2,*lol2,*lol2,*lol2,*lol2]
+lol4: &lol4 [*lol3,*lol3,*lol3,*lol3,*lol3,*lol3,*lol3,*lol3,*lol3]
+lol5: &lol5 [*lol4,*lol4,*lol4,*lol4,*lol4,*lol4,*lol4,*lol4,*lol4]
+lol6: &lol6 [*lol5,*lol5,*lol5,*lol5,*lol5,*lol5,*lol5,*lol5,*lol5]
+lol7: &lol7 [*lol6,*lol6,*lol6,*lol6,*lol6,*lol6,*lol6,*lol6,*lol6]
+lol8: &lol8 [*lol7,*lol7,*lol7,*lol7,*lol7,*lol7,*lol7,*lol7,*lol7]
+lol9: &lol9 [*lol8,*lol8,*lol8,*lol8,*lol8,*lol8,*lol8,*lol8,*lol8]
+lol10: &lol10 [*lol9,*lol9,*lol9,*lol9,*lol9,*lol9,*lol9,*lol9,*lol9]
diff --git a/tests/test_remarshal.py b/tests/test_remarshal.py
index 804e61e..6bf0c2a 100755
--- a/tests/test_remarshal.py
+++ b/tests/test_remarshal.py
@@ -599,5 +599,9 @@ class TestRemarshal(unittest.TestCase):
             "toml",
             stringify=True,
         )
         reference = read_file("numeric-key-null-value.toml")
         assert output == reference
+
+    def test_yaml_billion_laughs(self) -> None:
+        with pytest.raises(remarshal.TooManyNodesError):
+            self.convert_and_read("lol.yml", "yaml", "json")

Vulnerable code: version = "0.17.0"
max-args = 11
max-branches = 19
__version__ = "0.17.0"
    except (OSError, TypeError, ValueError) as e:
Fixed code: version = "0.17.1"
max-args = 12
max-branches = 20
max-statements = 100
__version__ = "0.17.1"
DEFAULT_MAX_NODES = 100000
    parser.add_argument(
        "--max-nodes",
        dest="max_nodes",
        metavar="n",
        type=int,
        default=DEFAULT_MAX_NODES,
        help="maximum number of nodes in input data (default %(default)s)",
    )

class TooManyNodesError(BaseException):
    def __init__(self, msg: str = "document has too many nodes", *args, **kwargs):
        super().__init__(msg, *args, **kwargs)


def validate_node_count(doc: Document, *, limit: int) -> None:
    count = 0

    def count_callback(x: Any) -> Any:
        nonlocal count
        nonlocal limit

        count += 1
        if count > limit:
            raise TooManyNodesError

        return x

    traverse(doc, instance_callbacks={(object, count_callback)})


        max_nodes=args.max_nodes,
    max_nodes: int = DEFAULT_MAX_NODES,
        validate_node_count(parsed, limit=max_nodes)

    except (OSError, TooManyNodesError, TypeError, ValueError) as e:
lol1: &lol1 "lol" 
lol2: &lol2 [*lol1,*lol1,*lol1,*lol1,*lol1,*lol1,*lol1,*lol1,*lol1] 
lol3: &lol3 [*lol2,*lol2,*lol2,*lol2,*lol2,*lol2,*lol2,*lol2,*lol2]
lol4: &lol4 [*lol3,*lol3,*lol3,*lol3,*lol3,*lol3,*lol3,*lol3,*lol3]
lol5: &lol5 [*lol4,*lol4,*lol4,*lol4,*lol4,*lol4,*lol4,*lol4,*lol4]
lol6: &lol6 [*lol5,*lol5,*lol5,*lol5,*lol5,*lol5,*lol5,*lol5,*lol5]
lol7: &lol7 [*lol6,*lol6,*lol6,*lol6,*lol6,*lol6,*lol6,*lol6,*lol6]
lol8: &lol8 [*lol7,*lol7,*lol7,*lol7,*lol7,*lol7,*lol7,*lol7,*lol7]
lol9: &lol9 [*lol8,*lol8,*lol8,*lol8,*lol8,*lol8,*lol8,*lol8,*lol8]
lol10: &lol10 [*lol9,*lol9,*lol9,*lol9,*lol9,*lol9,*lol9,*lol9,*lol9]

    def test_yaml_billion_laughs(self) -> None:
        with pytest.raises(remarshal.TooManyNodesError):
            self.convert_and_read("lol.yml", "yaml", "json")