Potential denial-of-service threats identified and their cause eliminated

Weaknesses of current XML technology have been identified, and solutions for eliminating them have been presented by Professor of Computer Science Pekka Kilpeläinen at the University of Eastern Finland. XML is a universally applied recommendation by the World-Wide Web Consortium (W3C) as an industrial standard for data representation, for example, of messages interchanged between web services.

XML supports the implementation of different application-specific data representations, whose format is defined by so called "XML schemas". The W3C XML Schema recommendation requires a certain unambiguity constraint to be checked by the schema processors. Prof. Kilpeläinen has demonstrated that implementations of this unambiguity check have flaws in current processors, which make them either to give erroneous results or to require exponential amounts of processing time and memory.

An exponential complexity opens possibilities for denial-of-service attacks through exhausting the resources of a processor with relatively small pathological inputs. As a solution to this problem, Prof. Kilpeläinen has presented an unambiguity-checking algorithm which operates in linear time with respect to the size of its input.
Linear-time solutions scale optimally, which means that it is practically impossible to exhaust their resources with attacks based on problematic inputs.

For further information, please contact Professor Pekka Kilpeläinen, tel. +358 40 355 3761, fax +358 17 16 2595, email: pekka.t.kilpelainen@uef.fi

Original article:
P. Kilpeläinen. Checking determinism of XML Schema content models in optimal time. Information Systems (May 2011), doi:10.1016/j.is.2010.10.001

Artikkelin kirjoitusvuosi: 2011

Takaisin tämän vuoden artikkeleihin