Add test for DoS vector on TypeCheckerHelper

Authored by Lucas_Werkmeister_WMDE on May 11 2017, 2:19 PM.

Unpublished Commit · Learn More

Publishing Disabled: All publishing is disabled for this repository.


Add test for DoS vector on TypeCheckerHelper

Prior to commit rEBQC0c5f4be6695e (change I39429d3), TypeCheckerHelper only
limited the recursion depth in isSubtypeOf. This fixed a simple infinite
recursion if there was a cycle in the subtype relation, but still
allowed an attacker to provoke extremely long type checking times by
introducing the same cycle multiple times, as in Q9 and Q10 added here.
When the checker tests the subtype relation on such an item, it builds
up the following tree:

       Q10               Q10
    +---^---+         +---^---+
   Q9       Q9       Q9       Q9
 +-^-+    +-^-+    +-^-+    +-^-+
Q10 Q10  Q10 Q10  Q10 Q10  Q10 Q10
 .   .    .   .    .   .    .   .
 .   .    .   .    .   .    .   .
 .   .    .   .    .   .    .   .

The old code would prune the tree at a depth of 20 levels, but by that
time it would have 2^20 (about one million) leaves, plus 2^19+2^18+...
intermediary nodes, and the checker would traverse all of them. Instead,
the new version counts total nodes visited, and completely stops the
check once the limit is exceeded.

Bug: T164948
Change-Id: I8f9919ae0e6c7805f9cca79ff59238d1ef15a972