A DoS Attack Against the C# Compiler | Hacker News Reader

A DoS Attack Against the C# Compiler

mattwarren.org

101 pointsbenaadams52 comments

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!

This was exponentially better than the other comments

Well played ;-)

(I love a good pun!!)

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.

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.

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!

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

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))

Related, with emphasis in original:

> Determining whether a given predicate has a set of valuations for its variables which make it true is an NP-complete problem; actually finding the set of valuations is an NP-hard problem. Therefore, overload resolution in C# 3.0 is at the very least NP-hard. There is no known polynomial-time algorithm for any NP-complete or NP-hard problem and it is widely believed that there is none to be found, though that conjecture has yet to be proven. So our dream of fast lambda type analysis in C# 3.0 is almost certainly doomed, at least as long as we have the current rules for overload resolution.

See Lambda Expressions vs. Anonymous Methods, Part Five[0] by Eric Lippert.

[0]: https://blogs.msdn.microsoft.com/ericlippert/2007/03/28/lamb...

If the concern is regarding real-world performance and not DoS attacks, then why can't they just adopt the conflict-driven clause learning techniques of practical SAT solvers? The corresponding SAT instances are quite small, so the problems should be handled quickly by even a relatively naive CDCL implementation.

Thanks for the link. I thought I'd read all the Eric Lippert articles related to my post, but I missed this one

> So if it takes 3 mins to compile your code, allocates 2GB of memory and then crashes, take that as a warning!!

As someone who used to spend a lot of time in C++ and LTCG I got a good laugh out of this(aside from the crashing part, ICE are always a bad thing). Our release link was ~40 minutes on each change.

Fun "bug" though.

Yeah, I guess I should've added 'So if it takes 3 mins to compile your code .. in the C# compiler'

But either way, I'm glad you enjoyed it.

> As someone who used to spend a lot of time in C++ and LTCG I got a good laugh out of this(aside from the crashing part, ICE are always a bad thing). Our release link was ~40 minutes on each change.

A long time ago I did some C++, so I know it can take longer, although I don't think I ever worked on something with 40 min build times!

Yeah, it was a great deep-dive.

The 40 minute link times comes from Link Time Code Generation which can reduce your binary size pretty significantly(along with some code speed-ups)[1], without LTCG linking on the project was about 1 minute.

Usually LTCG is a tool of last resort since the build times are so painful(and at the time was the only step that couldn't be parallelized). We were shipping on X360 with a hard memory limit and couldn't have a binary larger than 20mb if we wanted to hit them. If I recall correctly LTCG gave us back about 5-10mb which was a godsend in those times.

[1] https://msdn.microsoft.com/en-us/library/bb985904.aspx

gcc, clang, and Intel all both support this feature, calling it "Link-Time Optimization".[1,2,3] This allows them to inline virtual functions they can resolve, non-inline functions which are not visible to external units, as well as perform combinatorial optimizations by being able to "see" more of the code together at once.

In addition to binary size (which I've never worried about too much, as I mostly write code for scientific computing), it has often improved runtime significantly. The only other specific optimization besides -flto that I have had very real speedups from (not counting -O[23] or -Ofast) has been -funroll-loops. I use it on nearly every project. (And, to be honest, I haven't seen a big slowdown in compile time over just -O3, though I think a lot of my costs there are from templates.)

[1] https://gcc.gnu.org/wiki/LinkTimeOptimization [2] https://llvm.org/docs/LinkTimeOptimization.html [3] https://software.intel.com/en-us/node/522667

Yup, pretty sure LTO and LTCG are pretty close these days, if not the same thing.

Confused, was there ever a difference?

LTCG is MSVC specific, given that they're different compilers I can't say if the optimizations were identical.

Oh, I thought you meant they used to be different features, not that they used to be different implementations of the same concept.

Back in the early 2000, when I was doing a bit of C coding, even our C builds would take on average one hour per build configuration.

So doing a full release build across all UNIX and Windows variants supported by our product would take almost a full working day.

This reminds me of the grand C++ error explosion competition : https://tgceec.tumblr.com

The Don Syme article (first link) mentions "the critical nature of the interaction that app domains pose to generics". What interaction is that, and what is critical about its nature?

Hmm, that's a really good question.

I did a quick search in AppDomain.cpp [0] for 'generic' and there's quite a few comments/variables that mention it. Maybe this [1] is one of the tricky interactions?

[0]: https://github.com/dotnet/coreclr/blob/master/src/vm/appdoma... [1]: https://github.com/dotnet/coreclr/blob/master/src/vm/appdoma...

This is CoreCLR, much younger version of CLR that does not support multiple AppDomains In different open-sourced CLR implementation aka SSCLI20 (aka Rotor) there are similar interactions for type's domain discovery and DynamicClassTable, but there are also some interactions about GCStatics. I'm not sure if fullblown .Net CLR implementation was released yet

Yeah that's a good point, CoreCLR only has the single/main AppDomain code and Rotor was only 'sort of' .NET 2.0, but with a different GC and JIT.

So without asking Don Syme himself we can only guess.

> I'm not sure if fullblown .Net CLR implementation was released yet

No and AFAIK they don't plan to. There's 'Reference Source' [0], but that's the Base class libraries only, not the CLR itself.

[0]: referencesource.microsoft.com

I kinda guess this has something to do with System.__Canon type, which is a substitute type for open generic parameter type - there is no benefit in having different canon types per appdomain

This sort of thing affects functional languages in the ML family too because type unification ("algorithm W") takes exponential time.

Here's an OCaml example: https://cs.stackexchange.com/questions/6617/concise-example-...

And a crazy ML example: https://gist.github.com/spacemanaki/72ed52766e0c7e0b85ef

Related to the graphs in the article:

When you want to show that something grows exponentially, plot it with a log scale on the y axis. That way, an exponential function becomes a line, and humans are much better at judging whether something is a line than judging whether something is an exponential function.

In fact, whenever you want to honestly show that something follows a certain law, scale your axes so that you get a line in the best case.

Indeed, especially considering how bad the exponential fit is for working set, it is pretty evident that it is not just growing exponentially, but faster than that.

Of course the article just had to include this bit:

> If we look at these results in graphical form, it’s very obvious what’s going on

When it really is not obvious at all what is going on.

> Indeed, especially considering how bad the exponential fit is for working set, it is pretty evident that it is not just growing exponentially, but faster than that.

Yeah I suck at maths, according to this comment https://lobste.rs/s/j4545s/dos_attack_against_c_compiler#c_n..., it's actually 'double exponential'

> When it really is not obvious at all what is going on.

Yeah, I guess I actually meant to say 'it's very obvious that it's increasing quickly', but as you say, it doesn't read like that!!

I suck at maths too (we should start a club!), but playing around with Calc the best fit I could get (for working set) was with quadratic exponential, i.e. in the form of e^(n^2+n). It would be interesting if someone who actually knows anything about this could chime in and say conclusively what the growth rate really is here.

I think in this case the linear graph does a better job of showing the 'holy crap this exploded' better than a logarithmic graph would. That it is exponential is more of a neat aside.

It really depends on what you're after: dramatic effect, or convincing somebody of the actual relation (here that it's exponential, and not, say, x^5 or so)

I'd say strictly the reverse. Use log scale to hide differences between your results. Related: https://www.explainxkcd.com/wiki/index.php/1162:_Log_Scale

patient- Hey doc it hurts my arm when I hold it like this. doc- Well don't do that.

Yeah, that sums up the problem!

But Doctor, what if I NEED to use a nested contortion of generic classes as part of my obfuscated Java homework?

I've seen code very much like this in production c# and similar monkey patching stuff in ruby.

As humans we identify patterns far to readily and as developers we try to reduce duplication far too prematurely.

This is indeed confusing:

    class Blah<T> where T : Blah<T>

How do you actually satisfy that generic constraint? Should be illegal in my opinion.

class Foo : Blah<Foo>

And is an extremely common pattern at that.

Java 9 compiler fails with the following error (for similar code):

Error:(4, 9) java: UTF8 representation for string "LMain$Clazz<LMain$Cl..." is too long for the constant pool

Hmm, I would've thought that this would be easier for the Java compiler to handle, because it uses type erasure for generics. So in metadata, everything is just 'Object' rather than exact types, but I'm no Java expert, so I could be wrong?

See my post above. I can confirm the problem in Java. It is a different problem than the C# compiler has. But it still runs into a limit.

Most parts are erased, the method descriptor, the bytecode but the generic signature is kept for enabling separated compilation (you can also retrieve it by reflection).

Here the generic signature which is a String is just too big, the dictionary part of the classfile, the constant pool, stores a String as an UTF8 byte array prefixed by its size on 16bits (hence the 65535 limit).

Thanks for the info on Java generics, I always assumed that it 'erased' everything. I didn't appreciate that it would actually need to keep some info around, to make things work.

The limit is the class (or method) name that is bigger than 65535 in this case, it has nothing to do specifically with generics because of type erasure.

I can confirm a similar error. Java 8u152.

Four 'Inner's work. Five gives error:

The type generates a string that requires more than 65535 bytes to encode in Utf8 format in the constant pool

This is using Eclipse. So it is the Eclipse compiler which is integrated with the editor. I haven't tried Oracle's Java compiler.

Because the problem is to do with the size of a class constant pool, the limit of four Inner's should be universal across Java compilers, IDEs, and Operating Systems. (Assuming the class name mangling algorithm is part of the class specification.)

I seem to recall one of Jon Skeet's abusing C# videos with something similar. He has 4 or so up on YouTube, each is an hour and totally worth it.

Yeah I've seen several 'Abusing C#' by him, but it turns out he'd not seen this particular example before, see https://twitter.com/matthewwarren/status/928326856687915008

When I think about the generics discussion in the Go community (and even though I am personally for them), this is the kind of exponential complexity that I wouldn't want to see in any implementation thereof.

I don't believe Go will ever get generics, beyond go generate, Borland C++ 2.0 for MS-DOS style.

Reply on news.ycombinator.com