Visitar URL original
Fix quadratic CPU use in schemaless container decoding · pyasn1/pyasn1@a36e3a3 · GitHub
Skip to content

Commit a36e3a3

Browse files
committed
Fix quadratic CPU use in schemaless container decoding
Stop adding tag sets once two distinct types establish the container kind. This bounds hash-collision comparisons while preserving decoded values and order. Add BER, CER, and DER regression coverage for colliding tags and streaming.
1 parent 4ce0079 commit a36e3a3

3 files changed

Lines changed: 189 additions & 1 deletion

File tree

‎pyasn1/codec/ber/decoder.py‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -695,7 +695,10 @@ def _decodeComponentsSchemaless(
695695
break
696696

697697
components.append(component)
698-
componentTypes.add(component.tagSet)
698+
# Two distinct types settle the choice; keep the set bounded
699+
# to avoid quadratic comparisons for colliding tag hashes.
700+
if len(componentTypes) < 2:
701+
componentTypes.add(component.tagSet)
699702

700703
# Now we have to guess is it SEQUENCE/SET or SEQUENCE OF/SET OF
701704
# The heuristics is:

‎tests/codec/__main__.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@
88

99
suite = unittest.TestLoader().loadTestsFromNames(
1010
['tests.codec.test_streaming.suite',
11+
'tests.codec.test_decoder_schemaless.suite',
1112
'tests.codec.ber.__main__.suite',
1213
'tests.codec.cer.__main__.suite',
1314
'tests.codec.der.__main__.suite',
Lines changed: 184 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,184 @@
1+
#
2+
# This file is part of pyasn1 software.
3+
#
4+
# Copyright (c) 2026, Simon Pichugin <simon.pichugin@gmail.com>
5+
# License: https://pyasn1.readthedocs.io/en/latest/license.html
6+
#
7+
import io
8+
import sys
9+
import unittest
10+
from itertools import product
11+
12+
from tests.base import BaseTestCase
13+
14+
from pyasn1.codec.ber import decoder as ber_decoder
15+
from pyasn1.codec.cer import decoder as cer_decoder
16+
from pyasn1.codec.der import decoder as der_decoder
17+
from pyasn1.error import SubstrateUnderrunError
18+
from pyasn1.type import tag
19+
from pyasn1.type import univ
20+
21+
22+
class SchemalessContainerDecoderTestCase(BaseTestCase):
23+
codecs = (
24+
('ber-def', ber_decoder, False),
25+
('ber-indef', ber_decoder, True),
26+
('cer-def', cer_decoder, False),
27+
('cer-indef', cer_decoder, True),
28+
('der', der_decoder, False),
29+
)
30+
containers = (
31+
(0x30, univ.SequenceOf, univ.Sequence),
32+
(0x31, univ.SetOf, univ.Set),
33+
)
34+
35+
def _encodeLength(self, length):
36+
if length < 128:
37+
return bytes([length])
38+
39+
octets = length.to_bytes((length.bit_length() + 7) // 8, 'big')
40+
return bytes([0x80 | len(octets)]) + octets
41+
42+
def _encodeConstructed(self, identifier, body, indefinite):
43+
if indefinite:
44+
return identifier + b'\x80' + body + b'\x00\x00'
45+
46+
return identifier + self._encodeLength(len(body)) + body
47+
48+
def _substrate(self, containerTag, tagIds, indefinite, definiteTags=False):
49+
components = []
50+
for idx, tagId in enumerate(tagIds):
51+
octets = [tagId & 0x7f]
52+
tagId >>= 7
53+
while tagId:
54+
octets.append((tagId & 0x7f) | 0x80)
55+
tagId >>= 7
56+
57+
# Long-form context tag, explicitly wrapping a one-octet value.
58+
identifier = b'\xbf' + bytes(reversed(octets))
59+
body = b'\x04\x01' + bytes([idx % 256])
60+
components.append(self._encodeConstructed(
61+
identifier, body, indefinite and not definiteTags))
62+
63+
return self._encodeConstructed(
64+
bytes([containerTag]), b''.join(components), indefinite)
65+
66+
def _tagSet(self, tagId):
67+
return univ.OctetString.tagSet.tagExplicitly(
68+
tag.Tag(tag.tagClassContext, tag.tagFormatConstructed, tagId))
69+
70+
def _assertValue(self, value, expectedType, tagIds):
71+
assert type(value) is expectedType
72+
assert len(value) == len(tagIds)
73+
for idx, tagId in enumerate(tagIds):
74+
component = value.getComponentByPosition(idx)
75+
assert type(component) is univ.OctetString
76+
assert component.asOctets() == bytes([idx % 256])
77+
assert component.tagSet == self._tagSet(tagId)
78+
79+
def testHomogeneous(self):
80+
for codec, container, tagIds in product(
81+
self.codecs, self.containers,
82+
((32,), (32, 32, 32), (32 + sys.hash_info.modulus,) * 3)):
83+
name, decoder, indefinite = codec
84+
containerTag, sequenceType, recordType = container
85+
with self.subTest(codec=name, container=sequenceType, tags=tagIds):
86+
value, tail = decoder.decode(
87+
self._substrate(containerTag, tagIds, indefinite))
88+
self._assertValue(value, sequenceType, tagIds)
89+
assert tail == b''
90+
91+
def testHeterogeneous(self):
92+
for codec, container, tagIds in product(
93+
self.codecs, self.containers,
94+
((32, 33), (32, 32, 33, 32), (32, 33, 34, 33, 32))):
95+
name, decoder, indefinite = codec
96+
containerTag, sequenceType, recordType = container
97+
with self.subTest(codec=name, container=recordType, tags=tagIds):
98+
value, tail = decoder.decode(
99+
self._substrate(containerTag, tagIds, indefinite))
100+
self._assertValue(value, recordType, tagIds)
101+
assert tail == b''
102+
103+
def testCollidingTags(self):
104+
for codec, container, count in product(
105+
self.codecs, self.containers, (16, 32, 64)):
106+
name, decoder, indefinite = codec
107+
containerTag, sequenceType, recordType = container
108+
with self.subTest(codec=name, container=recordType, count=count):
109+
# Distinct integer IDs separated by the hash modulus collide
110+
# without replacing TagSet's public hash implementation.
111+
tagIds = [32 + idx * sys.hash_info.modulus
112+
for idx in range(count)]
113+
assert len({hash(self._tagSet(tagId)) for tagId in tagIds}) == 1
114+
substrate = self._substrate(containerTag, tagIds, indefinite)
115+
comparisons = 0
116+
originalEq = tag.TagSet.__eq__
117+
118+
def countedEq(left, right):
119+
nonlocal comparisons
120+
# Exclude fixed dispatch-table lookups and count only
121+
# comparisons between explicitly tagged components.
122+
if (isinstance(right, tag.TagSet) and
123+
len(left) == len(right) == 2 and
124+
left[-1].tagClass == tag.tagClassContext and
125+
right[-1].tagClass == tag.tagClassContext):
126+
comparisons += 1
127+
return originalEq(left, right)
128+
129+
tag.TagSet.__eq__ = countedEq
130+
try:
131+
value, tail = decoder.decode(substrate)
132+
finally:
133+
tag.TagSet.__eq__ = originalEq
134+
135+
self._assertValue(value, recordType, tagIds)
136+
assert tail == b''
137+
assert comparisons <= count, (
138+
'%d tag comparisons for %d components' %
139+
(comparisons, count))
140+
141+
def testStreaming(self):
142+
class NonBlockingStream(io.BytesIO):
143+
def read(self, size=-1):
144+
chunk = io.BytesIO.read(self, size)
145+
if not chunk and size:
146+
return None
147+
return chunk
148+
149+
for codec, container, tagIds in product(
150+
self.codecs, self.containers,
151+
((32, 32, 32), (32, 32, 32 + sys.hash_info.modulus, 32))):
152+
name, decoder, indefinite = codec
153+
containerTag, sequenceType, recordType = container
154+
expectedType = sequenceType if len(set(tagIds)) == 1 else recordType
155+
with self.subTest(codec=name, container=expectedType, tags=tagIds):
156+
# Keep explicit wrappers definite so resumption exercises
157+
# the container's own indefinite-length path.
158+
substrate = self._substrate(
159+
containerTag, tagIds, indefinite, definiteTags=True)
160+
stream = NonBlockingStream()
161+
iterator = iter(decoder.StreamingDecoder(stream))
162+
supplied = 0
163+
underruns = 0
164+
while True:
165+
value = next(iterator)
166+
if not isinstance(value, SubstrateUnderrunError):
167+
break
168+
169+
assert supplied < len(substrate), 'Decoder did not resume'
170+
position = stream.tell()
171+
stream.seek(0, io.SEEK_END)
172+
supplied += stream.write(substrate[supplied:supplied + 3])
173+
stream.seek(position)
174+
underruns += 1
175+
176+
assert underruns > 1
177+
assert supplied == stream.tell() == len(substrate)
178+
self._assertValue(value, expectedType, tagIds)
179+
180+
181+
suite = unittest.TestLoader().loadTestsFromModule(sys.modules[__name__])
182+
183+
if __name__ == '__main__':
184+
unittest.TextTestRunner(verbosity=2).run(suite)

0 commit comments

Comments
 (0)