A DoS Attack Against the C# Compiler

Re:A DoS Attack Against the C# Compiler by ScottBurson on Wednesday November 08, 2017 @06:26PM (#15658158)

Looking at the "decompiled" version, it's clearly cubic, not exponential. There are 6 type arguments to the outer instantiation of 'Class' in the field declaration; each of those arguments is itself an instantiation of 'Class' with 6 type arguments, each of which is a third level of instantiation of 'Class' with 6 type variable references, for a total of 216 (= 6^3) type variable references.

There's nothing exponential going on here. Note that in the expression 6^3, the number that's varying is the 6, not the 3. If it were the other way around, that would be exponential.

I realize "exponential" has come into common use meaning just "growing very fast", and it's sometimes pedantic to insist on a distinction between polynomial growth and exponential growth, but in a discussion of algorithmic time complexity, we should get it right!

[ Parent | on HN ]

Re:A DoS Attack Against the C# Compiler by al2o3cr on Wednesday November 08, 2017 @07:37PM (#15658654)

The "levels" that are being changed are the number of nested `Inner`s - the decompiled example is

    Inner.Inner inner

("Level 2" in the article's terms) but the crashing one is

    Inner.Inner.Inner.Inner.Inner.Inner.Inner.Inner.Inner.Inner inner

Your calculation of the variable references is correct, but the thing the article's experiment varies is the exponent.

[ Parent | on HN ]

Re:A DoS Attack Against the C# Compiler by ScottBurson on Wednesday November 08, 2017 @08:24PM (#15658918)

Ah, I see — it's cubic in the number of type parameters, but it's exponential in the depth of the type reference in the field declaration. My bad; I didn't read carefully enough.

[ Parent | on HN ]

Re:A DoS Attack Against the C# Compiler by Aloraman on Wednesday November 08, 2017 @07:59PM (#15658769)

Well, if you variate generic arity N, you are going to get N^3 which is exponential. If you variate nest level M, you are indeed going to get 6 ^ N which is 'just' polynomial. However, if you just look upon the code sample, in most case it is assumed that both N and M are variated, and if both of them are growing with same limiting behavior, then there is O(N^N) complexity. This complexity is even worse than factorial!

[ Parent | on HN ]

Re:A DoS Attack Against the C# Compiler by unwind on Thursday November 09, 2017 @03:48AM (#15660843)

Uh it's been ... rather long since my last exposure to formal CS, but did you drop some 'M's?

[ Parent | on HN ]

Re:A DoS Attack Against the C# Compiler by Aloraman on Thursday November 09, 2017 @05:44PM (#15666406)

Oh crap... yeah. I meant O(N^3) and O(6^M). If both are varied - O(N^M), if both are increasing with same order of magnitude, then complexity can be written as O(N^N) which is O(N! * e^N / sqrt(N))

[ Parent | on HN ]

Re:A DoS Attack Against the C# Compiler by tomcam on Wednesday November 08, 2017 @06:43PM (#15658293)

This was exponentially better than the other comments

[ Parent | on HN ]

Re:A DoS Attack Against the C# Compiler by matthewwarren on Thursday November 09, 2017 @04:37AM (#15661077)

Well played ;-)

(I love a good pun!!)

[ Parent | on HN ]