search

rubys / nokogumbo

A Nokogiri interface to the Gumbo HTML5 parser.
Apache License 2.0
186 stars 114 forks source link

Fix O(n^2) behavior when checking for duplicate attributes #144

Closed stevecheckoway closed 2 years ago

stevecheckoway commented 4 years ago

Code in question is here.

This can lead to a DoS. See #143.

flavorjones commented 2 years ago

@stevecheckoway Do we still need to address this? If so, should we move this issue over to Nokogiri?

stevecheckoway commented 2 years ago

I think so.

My recollection is that libxml2 checks for duplicate attributes whenever an attribute is added to an element and the only way it has to do this is by walking the linked list of attributes.

If we want to manipulate the xmlNode structure directly rather than calling functions to modify it, we should be able to get amortized O(n) behavior by collecting the set of attributes to add and checking for duplicates.

flavorjones commented 2 years ago

Moved to https://github.com/sparklemotion/nokogiri/issues/2568