mollybrake3's Space

The curious property revealed

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; basically, 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.

Source: http://blogs.msdn.com/b/ericlippert/archive/2011/07/15/the-curious-property-revealed.aspx

INTERDIGITAL COMMUNICATIONS INTEL INSIGHT ENTERPRISES

Laptop review: Kobalt G150

EDIT, 17th October 2011: Last week Kobalt closed down... so the choice about whether or not I'd buy from them again is now moot. However, PC Specialist sells a very similar spec, now including the matte screen...

As some of you will know, our house was burgled in April, and the thieves took three laptops (and very little else), including my main personal laptop. Obviously I ordered a replacement, partly covered by the insurance from my old laptop. However, I took the opportunity to spoil myself a little... I ordered a G150 from Kobalt Computers. Various people have taken an interest in the progress and results of this, so this post is a little review.

Specs

As I said, I spoiled myself a little... the specs are somewhat silly:

  • Overall, it's a G150 which is based on the Clevo P150HM chassis
  • Screen: 1920x1080, matte, 95% gamut
  • CPU: Intel Sandybridge Core-i7 2720QM; quad core 2.2-3.33GHz
  • Graphics: Nvidia GeForce GTX 580M
  • RAM: 16GB Corsair DDR3
  • Disk: SSD - Intel 510, 250GB
  • Optical: Blu-ray ROM; DVD/RW

How does it run?

Well how do you think it runs? :) Obviously it's very nippy indeed. I'm not sure I've ever used more than a couple of cores at a time yet, but it's nice to know I can test out parallelization when I want to :) While Windows Experience numbers are obviously pretty crude, they're pleasant enough that I might as well show them off:

Visual Studio 2010 still takes a while to come up (10-15 seconds) whereas Office components start pretty much instantly - so I don't know where the bottleneck for VS is. You can do an awful lot in terms of both disk and CPU in 10 seconds on this laptop, so it's a bit of a mystery. (Eclipse starts noticeably faster.) However, once running, Visual Studio is as fast as you'd expect on this machine - builds and tests are nippy, and the editor is noticeably more responsive than on the "make-do" laptop I've been using since April.

I can't say I'm much of a gamer, but my experiences in Call Of Duty: Black Ops and Portal 2 have been wonderful so far; I can put everything on high settings until it looks absolutely beautiful, and still get a good frame rate. I've never had a laptop with a really good graphics card before, and the one in this beast is one of the most powerful out there, so I've really got no excuse for not getting into gaming more, other than my obvious lack of free time. I'm also looking forward to investigating the possibility of writing code in C# to be executed on the GPU - I believe there are a couple of projects around that, so it'll be fun to look into.

With a fast SSD, the boot time is fabulously fast - although it does take a while to go to sleep, as I use hybrid sleep mode and it needs to dump memory to disk first. That's one downside of having a large amount of memory, of course. There's still a lot of debate around the longevity of solid state drives, but the improved performance is so noticeable that I'd definitely not go back to a "normal" hard drive now. I chose the Intel 510 over some slightly faster drives as the 510 is generally reckoned to be more reliable - so I'm hedging my bets somewhat. I suspect the difference in performance between "stupidly fast" and "ridiculously fast" is irrelevant to me.

The screen is beautiful - just "really nice" for normal desktop work, but amazing for games and video - that's where the matte nature really wins out. The contrast is particularly nice, at least in the short tests I've performed so far. The hinge feels pleasantly firm but not stiff - it's hard to judge this early, but hopefully it'll prove robust over time. This screen is one of the reasons I chose Kobalt - I believe they're the only UK company selling machines with this screen, and I'd certainly recommend that anyone who has the chance to go for the matte screen should do so.

Personally I use a separate keyboard most of the time (see below) but the keyboard on the G150 itself is a nice chiclet style one. I'm not terribly fond of the layout of the cursor keys of the fact that there's no separate home / end / page up / page down keys, but it's not a big deal. The feeling of the keys themselves is good, and not too loud. The trackpad is fine - I've turned off "tap to click" as it always ends up activating when I don't want to, but that's not specific to this particular laptop - I always find the same thing. Maybe I type with my palms particularly close to the trackpad, or something like that.

A few more random, esoteric points:

  • The power socket is "grippy" which makes it slightly harder to pull out the power, but does give a feeling of security. This is clearly a deliberate decision, and while it's not one which would suit everyone, I'm pretty happy with it.
  • The fan comes on and goes off reasonably regularly, which can prove a little distracting sometimes, but is the natural result of having a fast/hot laptop, I guess. The fan itself is fairly quiet under normal load, so I'd probably be fine with it being constantly on - it's the stop / start nature that jars a little. Not a big deal once you get used to it.
  • The webcam is really washed out - I don't think I'd really want to use it, to be honest. I don't know whether it's my particular hardware, the general make/model, or the settings (which I've played with and improved somewhat, but not to really acceptable levels)
  • The built-in microphone is located on the keyboard, which is a little bizarre and obviously not helpful for any time you'd be typing as well as talking. There's a lot of white noise with it compared with actual signal - I couldn't get a Skype test call to be audible without it also having huge amounts of hiss. Fortunately, this isn't a problem for me - I have a standalone microphone which I use for screencasts etc. That's previously been problematically quiet with other laptops, possibly due to drawing a lot of power - but it works perfectly with this laptop. I'm also getting a Corsair headset, which should be handy both for gaming and podcast recordings.
  • The machine itself is fairly bulky, and the power brick is huge - but the feeling of the chassis is a very attractive matte black. If you're looking for a sleek laptop to carry around a lot, this probably wouldn't be the best choice, but most of the time I keep my laptop on the same table at home. I went for a 15" rather than 17" as it makes a big difference when carrying it around to conferences, but the extra thickness required to house and cool the powerful components doesn't really bother me.

Overall, I'm really pleased with the laptop. As far as I can tell so far, the build quality is excellent - no problems at all. The poor quality of the microphone and webcam are a niggly disappointment, but not one that bothers me enough to find out whether they're "working as expected" or not.

The buying experience

This is where some of you may be relishing the prospect of reading a rant against Kobalt - but I'm not going to air lots of dirty laundry here. It did take a very long time for the laptop to arrive - over three months - but the causes of this were varied, and are worth mentioning at least in passing. I'm hoping that a summary of frustrations and the good parts will give the right impression without getting ugly.

My first cause of frustration occurred very early - before I'd even received a detailed order confirmation from Kobalt. They'd suffered from a high proportion of staff going down with norovirus around the time I ordered. This is the sort of thing which will obviously hit a small company like Kobalt rather more than bigger ones, but it wasn't a great start; for a week all I had was an email saying that I'd paid Kobalt for something, but I couldn't even check whether the details were right.

Some of the delays actually put Kobalt into a better light as far as I'm concerned. In particular, I'd originally ordered an AMD 6970 graphics card and a Vertex 3 SSD. Kobalt withdrew both of these components from sale: the 6970 was failing too often in testing, and the Vertex 3 was causing blue screens, sometimes in testing and occasionally on customer machines, due to an issue between the laptop chipset and the disk. Some other vendors would no doubt have kept selling these components and let the customer take the risk of losing the use of the laptop while it went back for repair, and I applaud Kobalt for not doing this.

Likewise my order was actually built twice: the first one failed testing - the motherboard failed, so had to be built from scratch. Again, I'm very happy about this - I'd obviously rather have a delay but get a working laptop in the end than get a defective one sooner. This also worked to my advantage in terms of the graphics card; although I'd only ordered a 485M, the first one was used in another customer's machine while waiting for a new motherboard for me... by which time the 485M was no longer readily available. Kobalt swapped in the 580M for no extra charge.

Other delays were only partially under Kobalt's control - for example, their order management system blew up in August. Can you blame a company for their internal systems failing? It's hard to say - and I'll be the first to admit I don't have the details. Was it due to cutting corners by getting a cheap ordering system which might be expected to be flaky? Was it due to something catastrophic which would only happen once in a million years? Should there have been better "emergency backup" procedures? I don't know - but it feels like something that customers shouldn't be exposed to.

One benefit of the delays was that I was able to change my order a couple of times - upping the CPU and memory, choosing a different graphics card and disk drive etc. Kobalt have been very flexible around this; it was considerably easier to change the configuration than I suspect it would have been with somewhere like Dell.

My main issue through all of this was communication - which wasn't all bad, but was definitely flaky. I suspect Kobalt would argue that I had unreasonable expectations, whereas I'd say it's just part of providing good customer service. The problems that Kobalt experienced obviously made all of this much worse than normal, but I still think there's a mismatched set of expectations there. I clearly wasn't the only one getting frustrated - the forums had a lot of posts complaining of a lack of updates - but equally, satisfied customers don't tend to post much to provide balance. It's very obvious on the forums that while people have been frustrated with the buying process, almost everyone's really happy with the machine they get in the end, and Kobalt are actually really good at answering questions about drivers etc afterwards.

My own experience of communicating with Kobalt was negative until the reasonably late stages of the order, but I was then phoned to be informed of the laptop coming out of testing and again to check shipping dates, which was good. (In this case it was particularly important as without the check, the laptop would have been delivered to the office on Saturday, where there may well not have been anyone prepared to sign for it.)

For a week or so after I received my laptop I still saw quite a few frustrated posts from other customers, but now that seems to have gone down significantly. It's possible that I'm just not seeing the other complaining posts (as such posts are often deleted - leading to the customer in question getting more frustrated, of course). I'm currently hopeful that I happen to have just ordered at a really bad time where Kobalt was suffering a series of unrelated problems. Whether they handled those as well as they could have done is up for debate, but hopefully new customers wouldn't see the same problems.

It should be noted that Kobalt is definitely trying to get better, too. In August they introduced a new Customer Promise around price, upgrades, and delivery times. In particular, if your order takes more than 6 weeks, you can choose between various games and accessories as a gift. (I chose two games from Steam.) Also, they're actively recruiting, so hopefully that will help on the communications front, too.

Accessories

As tends to happen while waiting for something, I got itchy and started buying accessories to go with the new laptop. I thought I might as well mention those at the same time...

External USB 3 drive: Western Digital MyPassport. I would probably have bought a eSata drive if I'd found one with as neat a form factor as this, but there just don't seem to be many eSata drives around yet. Hopefully this will change, as I do notice my USB mouse/keyboard responding sluggishly while I'm putting a lot of traffic through the drive - but apart from that, it's lovely. It's a really nice form factor, and seems to take advantage of the USB 3 ports on my laptop to deliver pretty reasonable performance. I'm expecting this to be used primarily for VMs - I've heard mixed reports of using VMs with SSDs, including the possibility that the two really don't play nicely, leading to early drive failure. I don't know whether this is accurate or not, but I'm being cautious. Overall, I'm pretty happy with this, although it's reasonably hard to get excited about a disk drive...

Keyboard: I do quite a bit of typing, and while I'm used to laptop keyboards, they're obviously somewhat constrained. I had previously been using a Logitech K340 which is nice, but I treated myself to a K800 for the new machine. Both of these use Logitech's "Unifying" receiver, which is wonderful - it's a tiny little receiver which I just leave permanently in the USB port. It works with quite a few Logitech peripherals, so I share the same receiver for my keyboard and the Anywhere MX mouse I use. The K800 keyboard is really nice - a lovely action, a sensible layout of Ins/Del/Home/End/PgUp/PgDn (which is its main benefit over the K340, to be honest) and it's rechargable via USB. The backlighting is a nice extra, although it's probably not going to actually be useful for me. It's fun to just wave your hand over it and watch it light up though... I'm easily pleased :)

I also bought a Belkin Screencast WiDi 2.0, which turns out to have been a mistake. I had thought that because I was using a Sandybridge laptop with an appropriate Intel wifi card, I'd be able to use WiDi - a technology which allows you to transmit video and sound to a receiver which can then plug into the TV. Yay, I can display Youtube etc on the TV without leaving the comfort of the sofa, right? Not so much - it turns out that this only works if you're also using the integrated graphics card; as I'm using a separate GPU, it's a no-go. This wasn't made as obvious as it might be on Intel's web site about WiDi - it's there if you dig, but it's not obvious. Just to be clear, this is in no way Kobalt's fault - they never claimed the new laptop would be WiDi compatible. I've now sent the Screencast (which was no use to me for anything else) to Kobalt so they can try it out with other laptops. (I suspect the GS150 may work with it, for example.)

VM experiment

As I've tweeted before, I did have one hope for actually using most of the 16GB of memory. I don't want to run VMs directly from the SSD, as I mentioned before - but I had a thought of having the virtual disk on the SSD, but then mounting it as a ram drive. That way I'd only need to write to the disk after shutting down the VM - one big write instead of frequent spraying access.

That would only work with a small drive, of course... but I hoped I'd just about be able to get Windows 7 Home Premium + Visual Studio into a small enough drive. With 1GB of memory for the VM and 2GB of memory for the host machine I can have a 13GB ram drive - and I can install Windows 7 on that using Virtual PC, but Virtual PC also uses disk space alongside the VHD for memory for the VM, which obviously takes another 1GB off the usable size. I nearly managed it, but not quite. I may give it another go with Virtual Box and the Express edition of VS11... I'll blog again if I get it working, but I didn't want to hold up this post forever...

In terms of getting anything working, it took a little while - DataRam's RAMDisk product kept hanging while closing down; imdisk gave me access problems even after trying all the suggested tweaks, but VSuite Ramdisk (server edition) seems to do the job. It's not hugely cheap (and I need the server edition to support a drive over 4GB) but if I can get everything working, I may go with it. Currently I'm using the trial edition.

Conclusion

I guess the obvious question to ask is "If I had my time again, would I take the same action?"

Well, it's obviously been a frustrating experience, but the results should keep me happy for a long time. I think I would be cautious about buying from Kobalt again, but probably less so than you might expect. I'd probably hang out in the forums for a while to see whether folks were generally happy at the time. I'm hoping I was just unlucky, and hit a particularly nasty time in Kobalt's history - I can't imagine the staff there have enjoyed those three months any more than I did - and that normally everything runs smoothly. If I were in a real hurry I'd probably go for an off-the-shelf solution, but that's a different matter - when you buy a custom machine you should expect it to take a bit longer. Just not three months, normally :)

I'd certainly be happy to buy from Kobalt again in terms of the quality of the product - it's a lovely laptop, and I'm delighted with its performance, display and general handling. Obviously I regret buying the Screencast, but all my other decisions - memory, disk, external keyboard etc - have turned out well so far.

Source: http://feedproxy.google.com/~r/JonSkeetCodingBlog/~3/nsJmZkaZ39o/laptop-review-kobalt-g150.aspx

PROGRESS SOFTWARE PLANAR SYSTEMS PEROT SYSTEMS

Because It?s Fun! - PHP Advent

Twelve years ago, computers were a mystery to me, but a friend of mine showed me how I could just go down to the computer parts store, pick out a motherboard, CPU, RAM, hard drive, power supply, &c., and put it together myself. It was so empowering! Those mysterious black boxes that our lives depend on were one step less mysterious.

I learned how to download Linux and install it myself for free???then, FreeBSD and OpenBSD. Then, I was building my own servers. Now, the whole web server/Internet thing was less of a mystery. This was, again, fascinating and empowering.

Ten years ago, I was the founder/owner/CEO of a music distribution company that grew from just me to 85 employees.

As the company grew, I enjoyed building all of the office PCs and web servers myself. I enjoyed setting up the same FreeBSD distribution for everyone, and writing shell scripts to automate the installation of everything. It was a fun challenge, and I?d often stay until midnight setting these things up, totally ?in the zone? and loving it.

Ten years later, I mentioned this to a friend. He said, sarcastically, ?Pffft. Yeah, that?s a good use of the CEO?s time!?

In the moment, I laughed, but later I thought, ?Well? yeah! It was my company, and I was the CEO. So, I could do whatever I wanted, and that?s what I wanted to do! What else should I be doing? Something less fun? Sitting in meetings? Why??

Just this week, an investor friend asked what I?m working on now. I spun my laptop to show him a screen filled with PHP. He said, ?Why are you doing this? You can hire someone to do it!?

I said, ?This is the only thing I love doing. Programming is pure creativity. Why would I hand off the fun stuff to someone else??

It was clear that both friends were just assuming that what I should have been doing is whatever is the most profitable thing, as if that?s the only measure that matters.

Even now, I?m trying a geeky project; I?m setting up a JSON-only REST API and requiring even my own site to use only that. When I tell this to other programmers, a few have asked, ?Why go to that trouble? You don?t need it!?

My answer is the same for everyone. ?Because it?s fun!?

No other reason is needed.

Never forget that all of these things we do???making money, building a company, whatever???are all leading to the eventual goal of having enough money to do whatever we want. So, take a shortcut to that goal, and do whatever you want in the meantime. Never feel embarrassed or defensive about doing something just because it?s fun.

Developer Gift

I recommend any loud, ticking timer to use with the Pomodoro Technique.

Don?t use an app. Get the actual physical ticking thing???it really makes a psychological difference.

Source: http://phpadvent.org/2011/because-its-fun-by-derek-sivers

SALESFORCE COM SAIC ROCKWELL AUTOMATION

Optional argument corner cases, part three

(This is part three of a series on the corner cases of optional arguments in C# 4; part two is here. Part four is here.)

A lot of people seem to think that this:

void M(string x, bool y = false) { ... whatever ... }

is actually a syntactic sugar for the way you used to have to write this in C#, which is:

void M(string x) { M(x, false); }
void M(string x, bool y) { ... whatever ... }

But it is not. The syntactic sugar here is not on the declaration side, but rather on the call side. There is only one method; when you make a call that omits optional arguments, the compiler simply inserts the arguments at the call site. That is:

M("hello");

is rewritten as

M("hello", false);

It would actually be pretty weird if we did it on the declaration side, because what would you do about this?

void N(bool a1 = false, bool a2 = false) { ... whatever ... }

Clearly we can't generate

void N() { N(false, false); }
void N(bool a1) { N(a1, false); }
void N(bool a2) { N(false, a2); }
void N(bool a1, bool a2) { ... whatever ... }

because now we have two methods with the same signature. But why would we need to generate the "a2" method in the first place? Because we added named arguments as well as optional arguments. Someone could call:

N(a2: true);

Clearly we have to rewrite the caller side, not the called side.

An argument with a default value does not change the signature at all, so anything that relies upon signature matching still needs to have an exact match. That is, even though you can say:

M("hello");

and you can say

Action<string> action = (string s)=>{M(s);};

You cannot say

Action<string> action = M;

Because M does not have a signature match with that delegate type; the delegate is expecting a method that takes a string, but you're giving it a method that takes a string and a bool. Where is the code generated that fills in the bool? There is no call site here, and the default value has to be filled in at the call site.

Similarly, you can't do something like this:

class B
{
  public virtual void M(string x, bool y = false) {}
}
class D : B
{
  public override void M(string x) {}
}

Or this:

class D : B
{
  public override void M(string x, bool y = false, int z = 123) {}
}

The signatures have to match to do an override, and default values for missing arguments are not part of the signature.

Next time: more consequences of call-site rewriting.

(This is part three of a series on the corner cases of optional arguments in C# 4; part two is here. Part four is here.)

Source: http://blogs.msdn.com/b/ericlippert/archive/2011/05/16/optional-argument-corner-cases-part-three.aspx

JACK HENRY and ASSOCIATES IXYS ITRON