OP here ;-)
3 and 4: The article isn't at all about the tool we built, it's supposed to shine a light on the different kinds of tasks that Test Engineers do. Think of it as not very subtle job advertising.
1. The idea was definitely out there (some other commenter posted a link to pacts, which were a strong influence). Part of the process (and I hope this comes out in the article) was to try to find good ways to write better tests. We couldn't really (long story, let's just say "legacy code" to summarize it). So in the end we went for this technique. The whole process took a year to do, and as far as NIH goes, the existing implementations do not work in Google's setting. So we had to roll our own implementation. That did not take very long, though.