Topology Manual Review Findings

TYG-01M: Potentially Invalidated Assumption

Type	Severity	Location
Logical Fault		Topology.sol:L34

Description:

The Topology::childrenBounds function assumes that the first member of the array will be the root (i.e. with a parent pointing to itself), however, this trait is not guaranteed by the sanitization performed at Integrity::enforce.

In detail, the Integrity::_topology function ensures that the array is in ascending order but not in a strictly ascending order, permitting equalities between members. As such, it is possible for a conditions array whereby the "root" is located at the nth element to exist as long as all the preceding elements have a parent equal to the nth element.

In such a case, the topology evaluated would be incorrect as the parent count would "reset" and not count the preceding elements while bounds will include the root itself, potentially causing an infinite recursion loop to manifest.

Impact:

The topology generated for a valid condition list that contains a root within it would be incorrect, causing multiple levels of validation throughout the code to fail proper execution.

Example:

Copy
23function childrenBounds(
24    ConditionFlat[] memory conditions
25) internal pure returns (Bounds[] memory result) {
26    uint256 count = conditions.length;
27    assert(count > 0);
28
29    unchecked {
30        // parents are breadth-first
31        result = new Bounds[](count);
32        result[0].start = type(uint256).max;
33
34        // first item is the root
35        for (uint256 i = 1; i < count; ++i) {
36            result[i].start = type(uint256).max;
37            Bounds memory parentBounds = result[conditions[i].parent];
38            if (parentBounds.start == type(uint256).max) {
39                parentBounds.start = i;
40            }
41            parentBounds.end = i + 1;
42            parentBounds.length = parentBounds.end - parentBounds.start;
43        }
44    }
45}

Recommendation:

We advise either the Integrity::_root function to be updated to ensure the root is present solely in the first element or the Topology::childrenBounds function to be adjusted to accommodate for a case whereby the root is located within the array, either of which we consider an adequate resolution to this exhibit and the former of which we advise.

Alleviation:

The code of Integrity::enforce and in detail Integrity::_root has been updated to mandate a single parent located at the first index of the conditions array thus alleviating this exhibit in full.