Today is the fifteenth anniversary of my first day of full time work here at Microsoft. Hard to believe it has been a decade and a half of writing developer tools. I am tremendously fortunate to be able to work with such a great team on such a great toolset for such great customers. I’m looking forward to the next decade and a half!

Now back to our regularly scheduled puzzling.

There are two curious properties of the string I mentioned last time. The first somewhat curious property is that this string has the same hash code as the empty string. A reader posted a comment to that effect within a half an hour of the blog post going up.

Of course, there are only four billion possible hash codes and way more than four billion possible strings, so there have got to be collisions in there somewhere. There are infinitely many strings that have this property; this just happens to be a particularly short one.

What is much more interesting is that any number of concatenations of this string yields a string that also has the same hash code as the empty string! A number of readers discovered this property.

I hinted that the curious property was one shared by a common string. And indeed, the property of having the same hash code for arbitrarily many concatenations is also shared with the empty string. Ha ha!

I noted in my first hint that this property was platform-dependent; you need to be using a non-debug 32 bit version of CLR v4. As we document in the MSDN page, the string hashing algorithm is subject to change at any time, and in fact has changed in the past. The debug version of the CLR changes its string hashing algorithm every day, so as to be sure that none of our internal infrastructure depends on the hash code algorithm remaining stable.

What gives this particular string this bizarre property?

The internals of the hashing algorithm are pretty straightforward; we start with two integers in a particular state, and then mutate those integers in some way based on successive bytes of the string data. The algorithm works on considering two characters (four bytes) of string data at a time for efficiency. The transformation consists of some bit shifts and adds and whatnot, as you’d expect.

You can think of the hashing algorithm as a finite state machine with 64 bits of state. Each four bytes of input from the string changes the 64 bits of state. The final hashed result is derived from those 64 bits of state at the point where the input stream ends.

This particular sequence of four bytes – A0 A2 A0 A2 – has the property that it transforms the start state bits into themselves. As long as that input keeps coming in, the internals of the hash calculation never get out of the start state, and therefore must always output the same hash code as that of the empty string.

If you have a function f, and a value x such that f(x) = x, the value x is called a “fixed point” of f. What I’ve found here is technically not exactly a fixed point of the state transition function, but it has the same sort of flavour as a fixed point. Fixed points in various forms come up a lot in computer science and mathematics; they have many interesting and useful properties which I might go into in later fabulous adventures. Today though I want to think a bit about the security implications.

Essentially what we have here is a way of constructing arbitrarily many strings that all have the same hash code. (*) If a hostile client can feed many such strings into a hash table on a benign server, the attacker can essentially mount a denial-of-service attack against the server that uses the hash table. The hash table will be unable to hash the strings into different buckets, and therefore it will get slower, and slower, and slower.

It’s not much of an attack, but it is an attack. (**)

As always, when thinking about how to mitigate attacks, think about “defense in depth”. If you think you might be vulnerable to this sort of attack, make the attacker do several impossible things, not just one, to pull off the attack. For example:

* Monitor inputs to ensure that one user isn’t sending an unusually huge amount of data for processing; throttle them back if they are.

* Filter inputs for unusual characters; attacks on hash tables are likely to involve out-of-the-ordinary data that has been specially crafted. Most people aren’t going to be sending strings to a database full of Yi Script characters.

* Monitor system performance, looking for slowdowns that might be indicative of DoS attacks

* Build a custom hash table that uses its own string hashing algorithm. When you make a new hash table, randomize the starting state and the transformation of the hash.

And so on. Of course, this is just a sketch of a few ideas; if you are genuinely worried about such an attack, it is quite tricky to actually design and implement an attack-resistant hash table. Consult an expert. (I am not an expert on this!)

———–

(*) Of course there are plenty of ways to come up with hash collisions; like I said before, there are infinitely many hash collisions since there are only four billion possible hash codes. This is just a particularly cheap and easy way to come up with hash collisions.

(**) And of course an attack by hostile clients on a slow hash table is just a special case of “attacking” yourself by accidentally hitting a slow code path due to a buggy design, as I learned the hard way.

There are all kinds of interesting things in the Unicode standard. For example, the block of characters from U+A000 to U+A48F is for representing syllables in the “Yi script”. Apparently it is a Chinese language writing system developed during the Tang Dynasty.

A string drawn from this block has an unusual property; the string consists of just two characters, both the same: a repetition of character U+A0A2:

string s = “ꂢꂢ”;

Or, if your browser can’t hack the Yi script, that’s the equivalent of the C# program fragment:

string s = “\uA0A2\uA0A2”;

What curious property does this string have?

I’ll leave some hints below — scroll down — and post the answer next time.

–

–

–

–

–

–

Hint #1: The curious property is platform-dependent; you’ll want to be using a 32 bit version of CLR v4.

–

–

–

–

–

Hint #2: The curious property is also a property of a much more commonly-used string.

–

–

–

–

Hint #3: This string has the same hash code as the empty string, but that’s not the only thing that is curious about it that it has in common with the empty string.

Here’s a common problem that we face in the compiler realm all the time: you want to make an efficient immutable lookup table for mapping names to “symbols”. This is in a sense the primary problem that the compiler has to solve; someone says x = y + z; and we have to figure out what x, y and z mean before we can do any more analysis. An obvious way to do that is to figure out all the name-to-symbol mappings for a particular declaration space once, ahead of time, stuff the results into a lookup table, and then use that lookup table during the analysis.

The lookup table can be immutable because once it is built, it’s built; no more symbols are going to be added to it. It’s going to be used solely as a lookup mechanism. A common and cheap way of doing that is to use what I whimsically call “popsicle” immutability: the data structure is a fully mutable structure until you freeze it, at which point it becomes an error to attempt to change it. This technique differs markedly from the sort of “persistently re-usable data structure” immutability we’ve talked about in the past, where you want to reuse existing bits of the data structure as you build new, different data structures out of it.

For example, we might write up a really simple little hash table that supports “freezing”. Something like this:

abstract class Symbol
{
  public string Name { get; protected set; }
}
sealed class SymbolTable
{
  private bool frozen = false;
  private class BucketListNode
  {
    public Symbol Symbol { get; set; }
    public BucketListNode Next { get; set; }
    public BucketListNode Prev { get; set; }
  }
  private BucketListNode[] buckets = new BucketListNode[17];
  private int GetBucket(string s)
  {
    return Math.Abs(s.GetHashCode()) % buckets.Length;
  }
  public void Add(Symbol symbol)
  {
    // Omitted: error checking for null symbol, null name,
    // duplicated entry, and so on.
    if (this.frozen)
      throw new InvalidOperationException();
    int bucket = GetBucket(symbol.Name);
    var node = new BucketListNode();
    node.Symbol = symbol;
    node.Prev = null;
    node.Next = buckets[bucket];
    if (node.Next != null)
      node.Next.Prev = node;
    buckets[bucket] = node;
  }
  public void Freeze()
  {
    this.frozen = true;
  }
  public Symbol Lookup(string name)
  {
    // Omitted: error checking
    int bucket = GetBucket(name);
    for (var node = buckets[bucket]; node != null; node = node.Next)
    {
      if (node.Symbol.Name == name)
        return node.Symbol;
    }
    return null;
  }
}
sealed class SymbolTable
{
  private bool frozen = false;
  private class BucketListNode
  {
    public Symbol Symbol { get; set; }
    public BucketListNode Next { get; set; }
    public BucketListNode Prev { get; set; }
  }
  private BucketListNode[] buckets = new BucketListNode[17];
  private int GetBucket(string s)
  {
    return Math.Abs(s.GetHashCode()) % buckets.Length;
  }
  public void Add(Symbol symbol)
  {
    // Omitted: error checking
    if (this.frozen)
      throw new InvalidOperationException();
    int bucket = GetBucket(symbol.Name);
    var node = new BucketListNode();
    node.Symbol = symbol;
    node.Prev = null;
    node.Next = buckets[bucket];
    if (node.Next != null)
      node.Next.Prev = node;
    buckets[bucket] = node;
  }
  public void Freeze()
  {
    this.frozen = true;
  }
  public Symbol Lookup(string name)
  {
    // Omitted: error checking
    int bucket = GetBucket(name);
    for (var node = buckets[bucket]; node != null; node = node.Next)
    {
      if (node.Symbol.Name == name)
        return node.Symbol;
    }
    return null;
  }
}

Very simple. We have an array of seventeen doubly-linked lists. We balance the table by choosing which of the seventeen linked lists to go with by hashing the name of the symbol. That way our lookup cost is one-seventeeth the cost of doing a straight lookup in a complete list.

Now of course there are other ways to do this efficiently. We could be sorting the list of symbols and doing a binary search. We could be re-hashing into a larger array of bucket lists if it turns out that there are thousands of symbols in this table. For the sake of argument, let’s suppose that we’ve decided to go with a fixed-number-of-buckets hashing approach, as we’ve done here.

One of the much-touted benefits of immutable data structures is that they are “threadsafe”. Since they cannot be written to, you’ll never run into a situation where a write operation is interrupted halfway by a thread switch, causing another thread to read an inconsistent data structure. However, it is a fallacy to believe that just because a data structure does not admit any way for you change its contents, its implementation must be threadsafe!

Suppose for example we do a real-world performance analysis of our little table here and discover that in practice, this sort of pattern comes up a lot in our customers’ code:

    x.Foo();
    x.Bar();
    x.Blah();
    y.Abc();
    y.Def();
    y.Ghi();

That is, the same identifier is looked up multiple times in a row in the context of a particular symbol table. We might decide to add a little optimization to our table’s lookup method:

for (var node = buckets[bucket]; node != null; node = node.Next)
{
  if (node.Symbol.Name == name)
  {
    MoveToFront(bucket, node);
    return node.Symbol;
  }
}
...
private void MoveToFront(int bucket, BucketListNode node)
{
  if (buckets[bucket] == node)
    return;
  node.Prev.Next = node.Next;
  if (node.Next != null)
    node.Next.Prev = node.Prev;
  node.Prev = null;
  node.Next = buckets[bucket];
  node.Next.Prev = node;
  buckets[bucket] = node;
}

We have essentially tweaked our hash table to have an array of Most Recently Used Lists, rather than merely an array of Doubly Linked Lists. That might be a performance win in the case where the lists get long and the same identifiers tend to be looked up in clusters. (It is enough of a real-world win that in the VBScript engine, the lookup tables use a variant of this optimization.)

But you see what we’ve done here? Reading the table now sometimes mutates its interior structure, and that mutation is not threadsafe! Even though there is no way for the user to logically change a frozen table, we do not ensure that reading the data is threadsafe.

In practice, most data structures do not do mutations on reads, but you cannot rely upon that unless it is documented. For example, the documentation for the Dictionary class notes that a Dictionary is threadsafe for multiple readers so long as there are no writers (though of course the actual enumerators are not threadsafe objects, as they are constantly mutating; rather, the collection being enumerated is threadsafe). Unless the author of a particular object makes a guarantee to you like that, you should assume that none of the operations are threadsafe, even if they appear to be read-only.

Original:

https://web.archive.org/web/20150523082529/http://blogs.msdn.com/b/ericlippert/archive/2011/05/23/read-only-and-threadsafe-are-different.aspx