A DoS Attack against the C# Compiler

This post first appeared on my blog

Generics in C# are certainly very useful and I find it amazing that we almost didn't get them:

What would the cost of inaction have been? What would the cost of failure have been? No generics in C# 2.0? No LINQ in C# 3.0? No TPL in C# 4.0? No Async in C# 5.0? No F#? Ultimately, an erasure model of generics would have been adopted, as for Java, since the CLR team would never have pursued a in-the-VM generics design without external help.

So a big thanks is due to Don Syme and the rest of the team at Microsoft Research in Cambridge!

But as well as being useful, I also find some usages of generics mind-bending, for instance I'm still not sure what this code actually means or how to explain it in words:

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

As always, reading an Eric Lippert post helps a lot, but even he recommends against using this specific 'circular' pattern.

Recently I spoke at the CORESTART 2.0 conference in Prague, giving a talk on 'Microsoft and Open-Source – A 'Brave New World'. Whilst I was there I met the very knowledgeable Jiri Cincura, who blogs at tabs ↹ over ␣ ␣ ␣ spaces. He was giving a great talk on 'C# 7.1 and 7.2 features', but also shared with me an excellent code snippet that he called 'Crazy Class':

class Class<A, B, C, D, E, F>
{
    class Inner : Class<Inner, Inner, Inner, Inner, Inner, Inner>
    {
        Inner.Inner.Inner.Inner.Inner.Inner.Inner.Inner.Inner inner;
    }
}

He said:

this is the class that takes crazy amount of time to compile. You can add more Inner.Inner.Inner... to make it even longer (and also generic parameters).

After a big of digging around I found that someone else had noticed this, see the StackOverflow question Why does field declaration with duplicated nested type in generic class results in huge source code increase? Helpfully the 'accepted answer' explains what is going on:

When you combine these two, the way you have done, something interesting happens. The type Outer<T>.Inner is not the same type as Outer<T>.Inner.Inner. Outer<T>.Inner is a subclass of Outer<Outer<T>.Inner> while Outer<T>.Inner.Inner is a subclass of Outer<Outer<Outer<T>.Inner>.Inner>, which we established before as being different from Outer<T>.Inner. So Outer<T>.Inner.Inner and Outer<T>.Inner are referring to different types.

When generating IL, the compiler always uses fully qualified names for types. You have cleverly found a way to refer to types with names whose lengths that grow at exponential rates. That is why as you increase the generic arity of Outer or add additional levels .Y to the field field in Inner the output IL size and compile time grow so quickly.

Clear? Good!!

You probably have to be Jon Skeet, Eric Lippert or a member of the C# Language Design Team (yay, 'Matt Warren') to really understand what's going on here, but that doesn't stop the rest of us having fun with the code!!

I can't think of any reason why you'd actually want to write code like this, so please don't!! (or at least if you do, don't blame me!!)

For a simple idea of what's actually happening, lets take this code (with only 2 'Levels'):

class Class<A, B, C, D, E, F>
{
    class Inner : Class<Inner, Inner, Inner, Inner, Inner, Inner>
    {
        Inner.Inner inner;
    }
}

The 'decompiled' version actually looks like this:

internal class Class<A, B, C, D, E, F>
{
    private class Inner : Class<Class<A, B, C, D, E, F>.Inner, 
                                Class<A, B, C, D, E, F>.Inner, 
                                Class<A, B, C, D, E, F>.Inner, 
                                Class<A, B, C, D, E, F>.Inner, 
                                Class<A, B, C, D, E, F>.Inner, 
                                Class<A, B, C, D, E, F>.Inner>
    {
        private Class<Class<Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner>.Inner, 
                        Class<Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner>.Inner, 
                        Class<Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner>.Inner, 
                        Class<Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner>.Inner, 
                        Class<Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner>.Inner, 
                        Class<Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner, 
                            Class<A, B, C, D, E, F>.Inner>.Inner>.Inner inner;
    }
}

Wow, no wonder things go wrong quickly!!

Exponential Growth

Firstly let's check the claim of exponential growth, if you don't remember your Big O notation you can also think of this as O(very, very bad)!!

To test this out, I'm going to compile the code above, but vary the 'level' each time by adding a new .Inner, so 'Level 5' looks like this:

Inner.Inner.Inner.Inner.Inner inner;

'Level 6' like this, and so on

Inner.Inner.Inner.Inner.Inner.Inner inner;

We then get the following results:

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

(the dotted lines are a 'best fit' trend-line and they are exponential)

If I compile the code with dotnet build (version 2.0.0), things go really wrong at 'Level 10' and the compiler throws an error (full stack trace):

System.ArgumentOutOfRangeException: Specified argument was out of the range of valid values.

Which looks similar to Internal compiler error when creating Portable PDB files #3866.

However your mileage may vary, when I ran the code in Visual Studio 2015 it threw an OutOfMemoryException instead and then promptly restarted itself!! I assume this is because VS is a 32-bit application and it runs out of memory before it can go really wrong!

Profiling the Compiler

Finally, I want to look at just where the compiler is spending all it's time. From the results above we saw that it was taking over 3 minutes to compile a simple program, with a peak memory usage of 2.14 GB, so what was it actually doing??

Well clearly there's lots of Types involved and the Compiler seems happy for you to write this code, so I guess it needs to figure it all out. Once it's done that, it then needs to write all this Type metadata out to a .dll or .exe, which can be 100's of MB in size.

At a high-level the profiling summary produce by VS looks like this (click for full-size image):

However if we take a bit of a close look, we can see the 'hot-path' is inside the SerializeTypeReference(..) method in Compilers/Core/Portable/PEWriter/MetadataWriter.cs

Summary

I'm a bit torn about this, it is clearly an 'abuse' of generics!!

In some ways I think that it shouldn't be fixed, it seems better that the compiler encourages you to not write code like this, rather than making is possible!!

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