CVE-2023-46247: Off-by-one Error (CWE-193)
value: Vyper is a Pythonic Smart Contract Language for the Ethereum Virtual Machine (EVM). Contracts containing large arrays might underallocate the number of slots they need by 1. Prior to v0.3.8, the calculation to determine how many slots a storage variable needed used `math.ceil(type_.size_in_bytes / 32)`. The intermediate floating point step can produce a rounding error if there are enough bits set in the IEEE-754 mantissa. Roughly speaking, if `type_.size_in_bytes` is large (> 2**46), and slightly less than a power of 2, the calculation can overestimate how many slots are needed by 1. If `type_.size_in_bytes` is slightly more than a power of 2, the calculation can underestimate how many slots are needed by 1. This issue is patched in version 0.3.8.
CWE description: A product calculates or uses an incorrect maximum or minimum value that is 1 more, or 1 less, than the correct value.
CVSS v3 base score: 7.5
Published: 2023-12-13T20:15Z
Repository: https://github.com/vyperlang/vyper
Language: Python
Files changed: docs/types.rst, tests/cli/outputs/test_storage_layout_overrides.py, tests/functional/test_storage_slots.py, vyper/semantics/analysis/data_positions.py, vyper/semantics/types/subscriptable.py
Commit date: 2023-04-28 17:40:15 -0700
Commit message: Merge pull request from GHSA-mgv8-gggw-mrg6

* fix: block storage allocator overflows

the storage allocator did not guard against overflow when no storage
layout override was provided. this could result in vulnerabilities like
the following:

```vyper
owner: public(address)
buffer: public(uint256[max_value(uint256)])

@external
def initialize():
    self.owner = msg.sender

@external
def foo(idx: uint256, data: uint256):
    self.buffer[idx] = data
```

while the get_element_ptr calculation for `self.buffer[idx]` is checked,
it is not checked in `mod_{2**256}` arithmetic, which can lead to
arithmetic wrapping back to the `owner` variable if the provided `idx`
is large enough.

* clean up allocator logic

also fix a bug where large allocations would use too much storage due to
floating point rounding precision

* add warning for large arrays

* add note about 2**64 behavior
Diff: diff --git a/docs/types.rst b/docs/types.rst
index 2c3a1e75d8..d669e6946d 100644
--- a/docs/types.rst
+++ b/docs/types.rst
@@ -518,10 +518,13 @@ A two dimensional list can be declared with ``_name: _ValueType[inner_size][oute
     exampleList2D = [[10, 11, 12, 13, 14], [16, 17, 18, 19, 20]]
 
     # Returning the value in row 0 column 4 (in this case 14)
     return exampleList2D[0][4]
 
+.. note::
+    Defining an array in storage whose size is significantly larger than ``2**64`` can result in security vulnerabilities due to risk of overflow.
+
 .. index:: !dynarrays
 
 Dynamic Arrays
 ----------------
 
@@ -559,10 +562,14 @@ Dynamic arrays represent bounded arrays whose length can be modified at runtime,
         for item in self.my_array:
             self.my_array[0] = item
 
 In the ABI, they are represented as ``_Type[]``. For instance, ``DynArray[int128, 3]`` gets represented as ``int128[]``, and ``DynArray[DynArray[int128, 3], 3]`` gets represented as ``int128[][]``.
 
+.. note::
+    Defining a dynamic array in storage whose size is significantly larger than ``2**64`` can result in security vulnerabilities due to risk of overflow.
+
+
 .. _types-struct:
 
 Structs
 -------
 
diff --git a/tests/cli/outputs/test_storage_layout_overrides.py b/tests/cli/outputs/test_storage_layout_overrides.py
index ff86b0cdf1..94e0faeb37 100644
--- a/tests/cli/outputs/test_storage_layout_overrides.py
+++ b/tests/cli/outputs/test_storage_layout_overrides.py
@@ -93,10 +93,25 @@ symbol: public(String[32])"""
         compile_code(
             code, output_formats=["layout"], storage_layout_override=storage_layout_override
         )
 
 
+def test_overflow():
+    code = """
+x: uint256[2]
+    """
+
+    storage_layout_override = {"x": {"slot": 2**256 - 1, "type": "uint256[2]"}}
+
+    with pytest.raises(
+        StorageLayoutException, match=f"Invalid storage slot for var x, out of bounds: {2**256}\n"
+    ):
+        compile_code(
+            code, output_formats=["layout"], storage_layout_override=storage_layout_override
+        )
+
+
 def test_incomplete_overrides():
     code = """
 name: public(String[64])
 symbol: public(String[32])"""
 
diff --git a/tests/functional/test_storage_slots.py b/tests/functional/test_storage_slots.py
index 4653625468..d390fe9a39 100644
--- a/tests/functional/test_storage_slots.py
+++ b/tests/functional/test_storage_slots.py
@@ -1,5 +1,9 @@
+import pytest
+
+from vyper.exceptions import StorageLayoutException
+
 code = """
 
 struct StructOne:
     a: String[33]
     b: uint256[3]
@@ -95,5 +99,17 @@ def test_reentrancy_lock(get_contract):
         "whatifthisstringtakesuptheentirelengthwouldthatbesobadidothinkso",
     )
     assert [c.foo(0, i) for i in range(3)] == [987, 654, 321]
     assert [c.foo(1, i) for i in range(3)] == [123, 456, 789]
     assert c.h(0) == 123456789
+
+
+def test_allocator_overflow(get_contract):
+    code = """
+x: uint256
+y: uint256[max_value(uint256)]
+    """
+    with pytest.raises(
+        StorageLayoutException,
+        match=f"Invalid storage slot for var y, tried to allocate slots 1 through {2**256}\n",
+    ):
+        get_contract(code)
diff --git a/vyper/semantics/analysis/data_positions.py b/vyper/semantics/analysis/data_positions.py
index 5c1347d5a3..8270f14558 100644
--- a/vyper/semantics/analysis/data_positions.py
+++ b/vyper/semantics/analysis/data_positions.py
@@ -4,10 +4,11 @@ from typing import Dict, List
 
 from vyper import ast as vy_ast
 from vyper.exceptions import StorageLayoutException
 from vyper.semantics.analysis.base import CodeOffset, StorageSlot
 from vyper.typing import StorageLayout
+from vyper.utils import ceil32
 
 
 def set_data_positions(
     vyper_module: vy_ast.Module, storage_layout_overrides: StorageLayout = None
 ) -> StorageLayout:
@@ -119,12 +120,11 @@ def set_storage_slots_with_overrides(
         varinfo = node.target._metadata["varinfo"]
 
         # Expect to find this variable within the storage layout overrides
         if node.target.id in storage_layout_overrides:
             var_slot = storage_layout_overrides[node.target.id]["slot"]
-            # Calculate how many storage slots are required
-            storage_length = math.ceil(varinfo.typ.size_in_bytes / 32)
+            storage_length = varinfo.typ.storage_size_in_words
             # Ensure that all required storage slots are reserved, and prevents other variables
             # from using these slots
             reserved_slots.reserve_slot_range(var_slot, storage_length, node.target.id)
             varinfo.set_position(StorageSlot(var_slot))
 
@@ -137,18 +137,33 @@ def set_storage_slots_with_overrides(
             )
 
     return ret
 
 
+class SimpleStorageAllocator:
+    def __init__(self, starting_slot: int = 0):
+        self._slot = starting_slot
+
+    def allocate_slot(self, n, var_name):
+        ret = self._slot
+        if self._slot + n >= 2**256:
+            raise StorageLayoutException(
+                f"Invalid storage slot for var {var_name}, tried to allocate"
+                f" slots {self._slot} through {self._slot + n}"
+            )
+        self._slot += n
+        return ret
+
+
 def set_storage_slots(vyper_module: vy_ast.Module) -> StorageLayout:
     """
     Parse module-level Vyper AST to calculate the layout of storage variables.
     Returns the layout as a dict of variable name -> variable info
     """
     # Allocate storage slots from 0
     # note storage is word-addressable, not byte-addressable
-    storage_slot = 0
+    allocator = SimpleStorageAllocator()
 
     ret: Dict[str, Dict] = {}
 
     for node in vyper_module.get_children(vy_ast.FunctionDef):
         type_ = node._metadata["type"]
@@ -163,40 +178,42 @@ def set_storage_slots(vyper_module: vy_ast.Module) -> StorageLayout:
         if variable_name in ret:
             _slot = ret[variable_name]["slot"]
             type_.set_reentrancy_key_position(StorageSlot(_slot))
             continue
 
-        type_.set_reentrancy_key_position(StorageSlot(storage_slot))
+        # TODO use one byte - or bit - per reentrancy key
+        # requires either an extra SLOAD or caching the value of the
+        # location in memory at entrance
+        slot = allocator.allocate_slot(1, variable_name)
+
+        type_.set_reentrancy_key_position(StorageSlot(slot))
 
         # TODO this could have better typing but leave it untyped until
         # we nail down the format better
-        ret[variable_name] = {"type": "nonreentrant lock", "slot": storage_slot}
+        ret[variable_name] = {"type": "nonreentrant lock", "slot": slot}
 
-        # TODO use one byte - or bit - per reentrancy key
-        # requires either an extra SLOAD or caching the value of the
-        # location in memory at entrance
-        storage_slot += 1
 
     for node in vyper_module.get_children(vy_ast.VariableDecl):
         # skip non-storage variables
         if node.is_constant or node.is_immutable:
             continue
 
         varinfo = node.target._metadata["varinfo"]
-        varinfo.set_position(StorageSlot(storage_slot))
-
         type_ = varinfo.typ
 
-        # this could have better typing but leave it untyped until
-        # we understand the use case better
-        ret[node.target.id] = {"type": str(type_), "slot": storage_slot}
-
         # CMC 2021-07-23 note that HashMaps get assigned a slot here.
         # I'm not sure if it's safe to avoid allocating that slot
         # for HashMaps because downstream code might use the slot
         # ID as a salt.
-        storage_slot += math.ceil(type_.size_in_bytes / 32)
+        n_slots = type_.storage_size_in_words
+        slot = allocator.allocate_slot(n_slots, node.target.id)
+
+        varinfo.set_position(StorageSlot(slot))
+
+        # this could have better typing but leave it untyped until
+        # we understand the use case better
+        ret[node.target.id] = {"type": str(type_), "slot": slot}
 
     return ret
 
 
 def set_calldata_offsets(fn_node: vy_ast.FunctionDef) -> None:
@@ -214,11 +231,11 @@ def set_code_offsets(vyper_module: vy_ast.Module) -> Dict:
     for node in vyper_module.get_children(vy_ast.VariableDecl, filters={"is_immutable": True}):
         varinfo = node.target._metadata["varinfo"]
         type_ = varinfo.typ
         varinfo.set_position(CodeOffset(offset))
 
-        len_ = math.ceil(type_.size_in_bytes / 32) * 32
+        len_ = ceil32(type_.size_in_bytes)
 
         # this could have better typing but leave it untyped until
         # we understand the use case better
         ret[node.target.id] = {"type": str(type_), "offset": offset, "length": len_}
 
diff --git a/vyper/semantics/types/subscriptable.py b/vyper/semantics/types/subscriptable.py
index a5ae075b73..4aef58ca23 100644
--- a/vyper/semantics/types/subscriptable.py
+++ b/vyper/semantics/types/subscriptable.py
@@ -101,10 +101,13 @@ class _SequenceT(_SubscriptableT):
 
     def __init__(self, value_type: VyperType, length: int):
         if not 0 < length < 2**256:
             raise InvalidType("Array length is invalid")
 
+        if length >= 2**64:
+            warnings.warn("Use of large arrays can be unsafe!")
+
         super().__init__(UINT256_T, value_type)
         self.length = length
 
     @property
     def count(self):

Vulnerable code:             # Calculate how many storage slots are required
            storage_length = math.ceil(varinfo.typ.size_in_bytes / 32)
    storage_slot = 0
        type_.set_reentrancy_key_position(StorageSlot(storage_slot))
        ret[variable_name] = {"type": "nonreentrant lock", "slot": storage_slot}
        # TODO use one byte - or bit - per reentrancy key
        # requires either an extra SLOAD or caching the value of the
        # location in memory at entrance
        storage_slot += 1
        varinfo.set_position(StorageSlot(storage_slot))

        # this could have better typing but leave it untyped until
        # we understand the use case better
        ret[node.target.id] = {"type": str(type_), "slot": storage_slot}

        storage_slot += math.ceil(type_.size_in_bytes / 32)
        len_ = math.ceil(type_.size_in_bytes / 32) * 32
Fixed code: .. note::
    Defining an array in storage whose size is significantly larger than ``2**64`` can result in security vulnerabilities due to risk of overflow.

.. note::
    Defining a dynamic array in storage whose size is significantly larger than ``2**64`` can result in security vulnerabilities due to risk of overflow.


def test_overflow():
    code = """
x: uint256[2]
    """

    storage_layout_override = {"x": {"slot": 2**256 - 1, "type": "uint256[2]"}}

    with pytest.raises(
        StorageLayoutException, match=f"Invalid storage slot for var x, out of bounds: {2**256}\n"
    ):
        compile_code(
            code, output_formats=["layout"], storage_layout_override=storage_layout_override
        )


import pytest

from vyper.exceptions import StorageLayoutException



def test_allocator_overflow(get_contract):
    code = """
x: uint256
y: uint256[max_value(uint256)]
    """
    with pytest.raises(
        StorageLayoutException,
        match=f"Invalid storage slot for var y, tried to allocate slots 1 through {2**256}\n",
    ):
        get_contract(code)
from vyper.utils import ceil32
            storage_length = varinfo.typ.storage_size_in_words
class SimpleStorageAllocator:
    def __init__(self, starting_slot: int = 0):
        self._slot = starting_slot

    def allocate_slot(self, n, var_name):
        ret = self._slot
        if self._slot + n >= 2**256:
            raise StorageLayoutException(
                f"Invalid storage slot for var {var_name}, tried to allocate"
                f" slots {self._slot} through {self._slot + n}"
            )
        self._slot += n
        return ret


    allocator = SimpleStorageAllocator()
        # TODO use one byte - or bit - per reentrancy key
        # requires either an extra SLOAD or caching the value of the
        # location in memory at entrance
        slot = allocator.allocate_slot(1, variable_name)

        type_.set_reentrancy_key_position(StorageSlot(slot))
        ret[variable_name] = {"type": "nonreentrant lock", "slot": slot}
        n_slots = type_.storage_size_in_words
        slot = allocator.allocate_slot(n_slots, node.target.id)

        varinfo.set_position(StorageSlot(slot))

        # this could have better typing but leave it untyped until
        # we understand the use case better
        ret[node.target.id] = {"type": str(type_), "slot": slot}
        len_ = ceil32(type_.size_in_bytes)
        if length >= 2**64:
            warnings.warn("Use of large arrays can be unsafe!")