Patched code sample

import collections.abc

class FixedHTTPHeaders(collections.abc.MutableMapping):
    """
    This class demonstrates the patched version of Tornado's HTTPHeaders,
    fixing the Denial of Service vulnerability (similar to CVE-2023-28370).

    The fix avoids O(n^2) string concatenation by storing multiple values for the
    same header in a list internally. The values are only joined into a single
    comma-separated string when the header is accessed, which is an O(n) operation.
    """

    def __init__(self, *args, **kwargs):
        self._dict = {}
        self.update(*args, **kwargs)

    def add(self, name: str, value: str) -> None:
        """
        Adds a new value for the given header name.

        This is the fixed method. If a header name is repeated, it appends
        the new value to a list instead of concatenating strings. This avoids
        the quadratic complexity that caused the DoS vulnerability.
        """
        norm_name = self._normalize_name(name)
        if norm_name in self._dict:
            # The header already exists.
            existing_value = self._dict[norm_name]
            if isinstance(existing_value, list):
                # If it's already a list, just append.
                existing_value.append(value)
            else:
                # If it was a single value, convert to a list.
                self._dict[norm_name] = [existing_value, value]
        else:
            # This is the first time we've seen this header.
            self._dict[norm_name] = value

    def __getitem__(self, name: str) -> str:
        """
        Returns the value for the given header name.

        If multiple values were added for this header, they are joined with
        a comma. This 'join' operation is performed only once upon access,
        making it efficient.
        """
        norm_name = self._normalize_name(name)
        value = self._dict[norm_name]
        if isinstance(value, list):
            # Join the list of values into a single string.
            # This is an O(n) operation, a significant improvement over the
            # previous O(n^2) concatenation on each `add` call.
            return ", ".join(str(v) for v in value)
        else:
            return str(value)

    def __setitem__(self, name: str, value: str) -> None:
        norm_name = self._normalize_name(name)
        self._dict[norm_name] = value

    def __delitem__(self, name: str) -> None:
        norm_name = self._normalize_name(name)
        del self._dict[norm_name]

    def __len__(self) -> int:
        return len(self._dict)

    def __iter__(self):
        return iter(self._dict)

    @staticmethod
    def _normalize_name(name: str) -> str:
        """Normalizes a header name to its canonical form (Title-Case)."""
        return "-".join([part.capitalize() for part in name.split("-")])

# # Example of how the fixed code prevents the DoS.
# # This part is for demonstration and would not be in the final answer.
# if __name__ == '__main__':
#     # In the vulnerable version, this loop would become progressively slower.
#     # In the fixed version, each 'add' operation is fast (amortized O(1)).
#     fixed_headers = FixedHTTPHeaders()
#     print("Demonstrating the FIX: Using a list to store multiple headers.")
#     for i in range(5):
#         fixed_headers.add("X-Repeated-Header", f"value{i}")
#         print(f"Internal state after adding value{i}: {fixed_headers._dict}")

#     print("\nAccessing the header triggers a single, efficient 'join' operation:")
#     # The expensive operation (joining) is deferred until access and happens only once.
#     final_value = fixed_headers["X-Repeated-Header"]
#     print(f"Final combined header value: {final_value}")

#     # Compare this with the vulnerable approach (pseudo-code)
#     # vulnerable_value = ""
#     # for i in range(5):
#     #     vulnerable_value = vulnerable_value + "," + f"value{i}" # O(n^2) over the loop