7 ms·
A DoS Attack Against the C# Compiler
- vvanders 9y ago> 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.
- matthewwarren 9y agoYeah, 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!
- vvanders 9y agoYeah, 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 https://msdn.microsoft.com/en-us/library/bb985904.aspx
- stochastic_monk 9y agogcc, 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 https://gcc.gnu.org/wiki/LinkTimeOptimization [2] https://llvm.org/docs/LinkTimeOptimization.html https://llvm.org/docs/LinkTimeOptimization.html [3] https://software.intel.com/en-us/node/522667 https://software.intel.com/en-us/node/522667
- vvanders 9y agoYup, pretty sure LTO and LTCG are pretty close these days, if not the same thing.
- throwaway613834 9y agoConfused, was there ever a difference?
- vvanders 9y agoLTCG is MSVC specific, given that they're different compilers I can't say if the optimizations were identical.
- throwaway613834 9y agoOh, I thought you meant they used to be different features, not that they used to be different implementations of the same concept.
- pjmlp 9y agoBack 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.
- thwd 9y agoWhen 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.
- pjmlp 9y agoI don't believe Go will ever get generics, beyond go generate, Borland C++ 2.0 for MS-DOS style.
- dzdt 9y agoThis reminds me of the grand C++ error explosion competition : https://tgceec.tumblr.com https://tgceec.tumblr.com
- gbacon 9y agoRelated, 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/lambda-expressions-vs-anonymous-methods-part-five/ https://blogs.msdn.microsoft.com/ericlippert/2007/03/28/lamb...
- cwzwarich 9y agoIf 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.
- matthewwarren 9y agoThanks for the link. I thought I'd read all the Eric Lippert articles related to my post, but I missed this one
- vorotato 9y agopatient- Hey doc it hurts my arm when I hold it like this. doc- Well don't do that.
- matthewwarren 9y agoYeah, that sums up the problem!
- DannyB2 9y agoBut Doctor, what if I NEED to use a nested contortion of generic classes as part of my obfuscated Java homework?
- flukus 9y agoI'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.
- perlgeek 9y agoRelated 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.
- zokier 9y agoIndeed, 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.
- matthewwarren 9y ago> 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_nd8r4z 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!!
- zokier 9y agoI 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.
- ender341341 9y agoI 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.
- rwmj 9y agoThis 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-of-exponential-cost-of-ml-type-inference https://cs.stackexchange.com/questions/6617/concise-example-... And a crazy ML example: https://gist.github.com/spacemanaki/72ed52766e0c7e0b85ef https://gist.github.com/spacemanaki/72ed52766e0c7e0b85ef
- gpvos 9y agoThe 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?
- matthewwarren 9y agoHmm, 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/appdomain.cpp https://github.com/dotnet/coreclr/blob/master/src/vm/appdoma... [1]: https://github.com/dotnet/coreclr/blob/master/src/vm/appdomain.cpp#L1288 https://github.com/dotnet/coreclr/blob/master/src/vm/appdoma...
- Aloraman 9y agoThis 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
- matthewwarren 9y agoYeah 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
- Aloraman 9y agoI 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
- kovrik 9y agoJava 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
- matthewwarren 9y agoHmm, 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?
- DannyB2 9y agoSee 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.
- _old_dude_ 9y agoMost 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).
- matthewwarren 9y agoThanks 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.
- tigershark 9y agoThe 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.
- 9y ago
- snomad 9y agoI 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.
- matthewwarren 9y agoYeah 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 https://twitter.com/matthewwarren/status/928326856687915008
- ScottBurson 9y agoLooking 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!
- tomcam 9y agoThis was exponentially better than the other comments
- matthewwarren 9y agoWell played ;-) (I love a good pun!!)
- al2o3cr 9y agoThe "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.
- ScottBurson 9y agoAh, 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.
- Aloraman 9y ago
- partycoder 9y agoThis is indeed confusing: class Blah<T> where T : Blah<T> How do you actually satisfy that generic constraint? Should be illegal in my opinion.