My Code Here

On International Data Privacy Day

2012-01-28T15:19:00.017Z

Europe to Google

Really, Google? You're getting rid of over 60 different privacy policies and replacing them with one that's a lot shorter and easier to read? Gee, thanks for doing that! I do have trouble with anything requiring an adult's attention span. What's that, your new policy covers multiple products and features, reflecting your desire to create one beautifully simple and intuitive experience? Terrific! You believe this stuff matters? Well that's great, just great.

First of all: why oh why, in the name of all that's hairy (and private); why did you ever send this notification to my Sky Mail account? I know you provide their service; but you know, that only makes them, not me, your customer. My contract is with Sky. They carry a privacy policy, to which I've agreed. Your opinions were neither sought nor welcome, and your policy (or policies) has (or have) no dominion over me there.

Secondly: do you never learn? You killed the much over-hyped Google Buzz in 2010 by deliberately implementing and obscuring such default privacy settings as would shame Facebook. You just killed off any last chance of social network success, by enforcing your account naming policy in Google+ (latest feeble "concessions" notwithstanding). Now you impose, without an opt-out, this unification of accounts across all Google services. What makes you think that I will continue to want to entrust any of my business correspondence, private letters, other documents and messages, contact lists, calendars, photographs, videos, even this blog, to such a capricious company? To you, who might delete everything I own at any time, on a whim and without appeal, simply because you suddenly decide you don't like my name?

Thirdly and finally: shut up, sit down, and pay attention. European citizens will not have privacy policies dictated to them by their service providers. Europe shall determine the privacy policy to be applied to, and by, its service providers. That, or else providers will no longer be providers to Europeans.

Sufficient Unto The Day

And the same applies across the pond. Facebook Live, in conjunction with the National Cyber Security Counsel, streamed last Thursday's NCSA event anticipating International Data Privacy Day (which is today). This included the keynote opening speech by Federal Trade Commissioner Julie Brill, but if Zuckerberg and co thought their coverage would smooth the ride, then it's safe to say she surprised them. The full text of her remarks can be read here:

http://www.ftc.gov/speeches/brill/120126datarivacyday.pdf

But here are a few samples.

Our enforcement actions in the privacy area are also a call to industry to put important privacy principles into practice. Facebook and Google learned this the hard way.

The Commission’s complaint against Facebook alleges a number of deceptive and unfair practices [...] These include the 2009 changes made by Facebook so that information users had designated private became public.

We also addressed Facebook’s inaccurate and misleading disclosures relating to how much information about users apps operating on the site can access [...] that the company misrepresented its compliance with the U.S.-EU Safe Harbor. And we called Facebook out for promises it made but did not keep: It told users it wouldn’t share information with advertisers, and then it did; and it agreed to take down photos and videos of users who had deleted their accounts, and then it did not.

Google received similar coverage of the FTC's complaint against them in the Buzz era. Both companies settled their respective complaints, and have been left embarrassingly subject to a decades-long regime of shame, rehabilitation, audit and assessment. Yet both seem determined to keep testing and risking their parole.

Facebook and Google: sufficiently evil, unto the day.

EU Data Protection Reform 2012

2012-01-25T16:17:00.021Z

Europe Sets the Standard

The European Commission today proposed a comprehensive reform of the EU's 1995 data protection rules, to strengthen online privacy rights and boost Europe's digital economy. The text of the proposals (pdf) comprises a hefty 91 articles and supporting material, spread over 120 pages. Here, summarised in the form of annotated bullet points, are eight of the most important and/or controversial aspects from an initial reading of today's proposals.

One Rule for All

The intention is to introduce a single regulation (law) across all 27 member countries. This contrasts with the 1995 directive, which specified only the desired results. While these results were themselves binding, they were left to the individual states to implement, using their own chosen methods and mechanisms. Nobody seriously considers the outcome of that process, predictably enough a patchwork of 27 variegated rule sets, to have been a resounding success.

No Geographical Boundaries

Article 3 declares the scope of the new regulation, which would extend to anyone, anywhere in the world (yes you too, America!), involved in the processing of any personal information, relating to any EU citizen. And by personal information is meant not only names, dates, and places, but also technical data such as IP or Mac addresses; (explicitly) information of a genetic, biometric, or health nature; and so on. Service providers like Facebook or Google must accept these obligations in full, or else deny their services to EU citizens.

The Right to Erasure

Article 17 guarantees EU citizens the right to "extended erasure" of their personal data. Not only will the organization that processes personal data have to erase it on demand, but the they will also have to "take all reasonable steps, including technical measures" to get any copy, link, or replication on the Internet removed. Now, although in practice search engine data removal can mostly be automated, data removal from e.g. sites repeating CC-licensed Wikipedia content could be problematic.

Data Portability

Article 18 introduces the right to data portability - that is, to obtain a complete copy of stored or active data in a structured format. For example, this will allow users to switch between web mail systems with all their data intact.

Mandatory Assessments

Article 30 binds organizations to systematic security risk evaluations; unlawful forms of processing, unauthorized disclosure, dissemination or access, or alteration of personal data must be prevented. Here, the commission reserves the right to define: what constitutes the state of the art, for specific sectors and in specific data processing situations, in particular taking account of developments in technology and solutions for privacy by design and data protection by default.

Mandatory Notifications

Article 31, already being dubbed the Playstation Clause, requires organizations to disclose to their supervisory authority, effectively immediately, and in any case within a maximum of 24 hours, any personal data security breach. Sony famously waited one full week before telling their SEVENTY MILLION customers their personal data might have been compromised. This provision has of course come in for immediate and heavy criticism; 24 hours is not a lot of time for the kind of investigations that might be needed to avoid many false alarms. It might also be too short an interval to prepare measures to ensnare hackers, and serve only to warn them their attacks have been noticed and actioned.

Enforcement: Data Protection Officers

Article 36 provides for data protection officers, designated in regard to their knowledge on data protection laws, who will be independent, and will receive no instructions pertaining to the exercise of their function. These officers will be mandatory in three prescribed cases, namely:

for any public authority or body;
for any company permanently employing more than 250 persons; and
for any company whose core activity consists of monitoring data subjects [qv].

One important corollary is the end of general notifications to local agencies, which measure alone should simplify the regulatory environment and save an expected 130 million € per annum.

Enforcement: Enormous Fines

Article 79 aims to give the legislation the necessary "teeth" to enforce these rules. This it does by providing individual national data privacy agencies with huge administrative sanctions. Various levels are countenanced, depending upon the particular violation, but the headline figures are: up to one million €, and up to 2% of an enterprise's annual worldwide turnover. Just to put that in context, to Microsoft in 2008, that would have come to 1.2 billion € plus tips.

Conclusion

It's a bold proposal, obviously designed to take the lead in the international areas of user privacy, data ownership, and data security. Certain of its provisions appear superficially to be quite "heavy" in their commercial import; some rather impractical, and maybe idealistic, although given the technological representation present and the consultancy that has taken place over the last 17 years, certainly not as naive as recent American proposals in adjacent fields (SOPA, ProtectIP). The Commission has clearly decided to take a stand against the piecemeal, partial, and largely failed implementations of its earlier directive. It will be very interesting to see how and where this extensive new structure flexes under the opposing pressures of commerce and politics in coming months.

Picture: Berlaymont building of the European Commission (Wikipedia).

Alabaster Jones - Glasgow 20/1/12

2012-01-20T23:47:00.027Z

Pimp My Funk

Last time I set foot in the Classic Grand, Jamaica Street, was in the mid 1970s. My friend Spike and I went to see an X-certificate (18 - yes, we were both underage) ~~porno flick~~ French film of self-discovery called La Vallée. At that time, the small Glasgow movie theatre was renowned for its X-cert fare. So much so, the locals used to call it the Classic Gland, and joke that the clientele all wore plastic macs. However, we weren't there - we told ourselves - to ogle and drool at the pretend humping. The big attraction was actually the film's soundtrack: the Pink Floyd album, Obscured By Clouds. Written and recorded during the Dark Side of the Moon sessions, it does contain a few rather great songs...

Tonight I returned with my wife to the now-converted rock club & live music venue that is the repurposed Classic Grand. As before, the motivation was music. We arrived, as seems usual for us nowadays, just as the last band of this YRock-organised evening took to the stage at 9:30 :-(so we missed all of Picnic Railway, Erin Todd, Rosie Bans, and Motion Play)-:

Named for the King of the Hill Oklahoma City pimp voiced by Snoop Dogg, Alabaster Jones are a band with a solid direction, and that direction is funk. Unwavering, uncompromising, and unadulterated, even though alternative. Now, maybe they will develop an appetite for greater variety one day, when they're free to play longer sets than tonight's (the very, very best part of an hour). That should be quite a day. For who would dare to predict what musical dissertations a band, who number among their influences Prince, Hendrix, and The Mars Volta, might end up writing? But until then, they're playing a winning formula with this relentlessly dirty, alt-funk groove odyssey which they do so well.

Front and centre on keys and main vocals is Paul Loughran, who after the opening one-two salvo of Too Late and Pure Gold, complains about being hit in the back of the legs by the bass drum. The quality keeps rolling out with Brand New Day and the hugely original and catchy Superkrunk! - Andy Mushet's slap happy bass melds satisfyingly with tight syncopation from Liam Cutkelvin's drumwork, turning all of us into dancing fools. Paul answers a certain heckler shouting "Get a haircut!" with "I can't believe I've just been told to get a haircut by my dad!"

What's that intro sound? Wailing and noodling like... is it Pink Floyd again? Dire Straits? Nah, it's Funkatron! A sad story maybe ("That's why I'm mean..."), but in seconds we're back in that familiar warm and funky groove again.

New Song

Down In The Mud is a new song they're premiering at tonight's gig, but I've already downloaded and learned it from Soundcloud, so I'm singing along as Paul gives his humongous keyboard a rest, cavorting and vocalising instead like some over-animated Jay Kay. There's some particularly lovely guitar sketches by maestro Adam Millar in this performance tonight. Next, Funkatron part 2: where the party is at gives all three front men a good workout in vocal harmonies, to great effect. And Grease The Wheels (bring me the butter) provides a fitting Zappaesque finale, reaffirming the band's quirky sense of humour, and sending us off still dancing.

Tonight's gig was filmed. Professionally, with two cameras an' everything! Unfortunately that meant that we couldn't really stroll up to the front to get any action photos of our own, not without spoiling the video project. Second downer of the night: the bar shuts at 10, in order to let the venue reopen as a club at 11. This meant some people had to be happy with one drink, when the ideal number would obviously have been something more in the region of two.

Great gig though. Huge fun. Setlist (with Soundcloud links where available):

Too Late
Pure Gold
Brand New Day
Superkrunk!
Funkatron
Down In The Mud
Funkatron part 2: where the party is at
Grease The Wheels (bring me the butter)

Disclosure: keys and vocals funkmeister Paul is a working colleague of my wife, who insists he is not only a keen and diligent worker, but also one of the nicest blokes you could ever hope to meet. It'll be a sad day for her company when Alabaster Jones get the rewards and recognition they deserve!

Happy 10th Birthday SDL

2012-01-12T12:15:00.008Z

Many Happy Returns

Or successful continuations, if that's your programming paradigm of choice. They're busily blowing out candles and popping the fizz over at Microsoft Security Development Lifecycle Group. It's exactly ten years to the day since William Henry "Bill" Gates III,

[...] in response to customer feedback, grabbed his dilemma by the horns, and issued a back-me-or-sack-you directive known lovingly as Trustworthy Computing. Company-wide memos like this were rare. This one went into every department, as company-wide memos are wont to do, and demanded sweeping improvements in the "four pillars" on which the customer experience is based: security, privacy, reliability, and business integrity.

(from my Security 101: Part 2 a couple of years ago).

The Microsoft SDL Blog is itself celebrating with an appropriately crusty reminiscence, Trustworthy Computing’s 10 Year Milestone – Reflecting on Humble Beginnings, by Steve Lipner, Senior Director of Security Engineering Strategy, on behalf of the rest of the Trustworthy Computing team; frankly outdone by Principal Cybersecurity Architect Michael Howard's comprehensive memoir What a Journey It Has Been, and noted in turn by David Burt at the Microsoft Privacy & Safety TechNet blog among countless other well- (and ill-!) wishers.

[As an aside, while you're checking out those accounts, the new SDL post Compiler Security Enhancements in Visual Studio 11 by Tim Burrell (MSEC security science) gives a rare preview of the new /sdl and updated /GS switches.]

Let's join in wishing the Microsoft SDL another ten years of security enhancement and threat mitigation!

Picture of His Billness courtesy of Wikipedia.

Li1up0phi1up0p

2012-01-10T11:52:00.008Z

Just Don't Go There

I've numfuscated the name of this domain, just to try to ensure that you won't end up going there accidentally. But Li1up0phi1up0p reached a significant milestone last week. In an ecosystem of low to medium spread, low to medium profile SQL Injection attacks, many quite serious and mitigated only by these low numbers, this one has over the span of six or more weeks, achieved in excess of one million infected URLs. I've been watching it grow...

Mark Hofman of Shearwater reported on December 1 last year, several websites becoming infected with a SQL Injection script containing the string

"></title> < script src="hXXp://Li1up0phi1up0p.com/sl.php"> < /script>

(or, as I said, something quite like it :-). Checking Google, he found the number of infections at that time to be about 80, covering all versions of MSSQL. Next day, similar checks revealed about 200 infections in the morning, a thousand by lunchtime, and over four thousand that afternoon. One week and 160,000 infected websites into the event, it had become clear the attack was spreading rapidly via several and various automated sources. The most affected single region was .uk, followed by .de and then .com.

Mark's log at the SANS Internet Storm Center blog ISC Diary contains details of database "probing" occurring some time prior to the actual commencement of the attack, and some detailed information about its motive (it's attached to a fake AV scam), while at Kaspersky's ThreatPost, Dennis Fisher reveals something of its modus operandi as it works through various IIS, ASP and Microsoft SQL Server vulnerabilities.

A very similar attack with the moniker lizamoon also achieved a million infections earlier in 2011.

Scattered Along the River of Heaven

2012-01-05T09:51:00.005Z

A Happy New Year to everyone who's currently using the same calendar as me.

Here's a great short to kindle your new year, new found, interest in Science Fiction. Aliette de Bodard is an American born, Franco-Vietnamese author and defence video analyst who lives in Paris. She has a strong interest in ancient Aztec, Vietnamese and Chinese cultures. This piece, based on four original poems in ancient Chinese (Qing and Tang) styles, is one of those stories you start re-reading immediately upon finishing it:

http://clarkesworldmagazine.com/de_bodard_01_12/

Amnesty International UK Attacked

2011-12-24T08:54:00.009Z

Serving up Malware

Wouldn't it be ironic, and not in a wholesome or entertaining way, if the very act of visiting my (loosely) security based blog, and clicking on my very well intentioned Amnesty International sidebar, were to leave you infected with malware of a context-specific kind? Namely Trojan Spy-XR, the kind that spies on the activities of human rights activists, returning the electronic information so obtained to... certain countries...

Okay: China. There is evidence (from this ThreatExpert analysis) that the malicious Java file, currently being served in a cross-site way through a certain genuine but compromised Brazilian automotive website, appears to be associated with China. Brian Krebs reports the malware as belonging to "a notorious family of backdoor Trojans" from that quarter, and Chinese hacking groups are well known to be waging an ongoing campaign against dissident and human rights organizations, to extract personal and logistic information about them.

So ironic or not, that's what might have happened to you, had you clicked the aforementioned sidebar link within the past week or so. Sorry about that.

Mitigated by Unpopularity and... Java

Being unaware of the previous and ongoing targeting of human rights workers by this nefarious scheme and others like it, I had assumed that the relative lack of popularity of the Amnesty site (Alexa.com rating below 90,000) - not to mention that of my own blog! - made it a comparatively safe cross-link. But today I learned the organization’s site was hacked with a drive-by attack last April, while its Hong Kong website was in November 2010 hacked and seeded with an exploit dropping malware based around a previously unknown IE zero-day vulnerability (see this Websense report). In possible mitigation, these attackers are clearly not out for financial data or gain.

These attacks, as noted by Brian Krebs, serve to highlight the importance of keeping up to date with security patches. In the case of Java, a safer option might be to remove frequently targeted software you don’t really need.

My Top Ten Christmas Songs

2011-12-12T00:00:00.020Z

OK Let's Get This Thing Over

Ho³! Everyone seems to be indulging this humbug a little early this year, but as XKCD shows (click through for full details), at least in America, and subjectively here in the UK too, there appears to be a huge cultural bias towards 40s and 50s Christmas songs. For once, I won't be straining to reach as far back in time as my braces will permit, as I own up to some personal favourites in the genre.

10. Mike Oldfield, who could never be bothered waiting around for everyone else to learn their parts, started the trend of playing everything yerself. This is from 1975, although originally from the middle ages:

9. Not strictly a Christmas song, more of a fine study in adolescent rivalry and frustration, slapped on to the B-side of 1986's Trumpton Riots with the word Christmas gratuitously grafted into the title: these are the peerless Half Man Half Biscuit...

8. Justin Hawkins pouted perfectly in 2003: Now how the hell am I gonna make it into the new year?

7. Another non-Christmas song, Joni Mitchell's River just happened to be set at Christmas time in 1971, on a rather melancholy variation of Jingle Bells...

6. This kazoo-festooned KT Tunstall cover of Mele Kalikimaka (Christmas In Hawaii) lit up 2007, but originally written by Robert Alex Anderson in 1949 and appearing on Bing Crosby's White Christmas album, it's the only of our ten falling within the XKCD boom years:

5. Greg Lake, replete with Troika (from Sergei Prokofiev's Lieutenant Kijé, 1934) protested the commercialization of Christmas 1975...

4. John Lennon would have shown that Lake guy a thing or two about protest in 1971...

3. Kirsty, we will never forget you... with The Pogues, perennially since 1987:

2. A prog masterwork from 1976, Ring Out Solstice Bells can be found on The Jethro Tull Christmas Album, alongside such yuletide favourites as A Christmas Song and Another Christmas Song...

1. Topping my festive selection: 1981 had the coolest Christmas song ever!

Please don't mention The Spice Girls. Have a happy holiday season, everyone.

Sony Handheld Nonportable

2011-12-06T16:54:00.013Z

Vita has Flash Problem

And I don't mean Adobe. Even though discontinuing Flash development for mobile devices, Adobe are still in negotiations with Sony for a Vita version of (probably) Flash Mobile 11 - the last version they'll ever make available for phones and tablets. But Steve Jobs has driven all web video irrevocably in the direction of HTML5; and as for Flash games, well, they're mostly rubbish on wee displays like the Vita's 5" OLED capacitive touchscreen anyway. No, the issue I'm referring to is this new announcement from Sony, that the PS Vita will require the use of proprietary memory cards. And just why exactly might that be? A Sony spokesperson explains: [we are] using proprietary memory cards, both for security reasons, and to ensure a consistent experience for all users.

Ah right, security reasons, of course. And yes, a consistent user experience. Always thinking about its beloved users, Sony is. About their security. And about the consistency of their experience. So, we should expect these proprietary sticks to be priced similarly to existing, industry standard flash memory cards, right?

Prices are in dollars. Source: Amazon.com, except for Sony prices, which are current listings at Gamestop.

DeepEnd Research

2011-11-24T11:52:00.014Z

New Security Group

Last month the security community welcomed a new member, DeepEnd Research...

[...] an independent information security research group that will focus on threat and intelligence analysis. Our emphasis will be on malware, exploit analysis, botnet tracking, the underground economy and overall cyberthreats. We will blog about various collection and analysis techniques, observations, and other areas of interest.

The group has also declared another primary goal: fostering collaborative research and analysis efforts with other security groups and organizations. It is staffed by a team of (currently eight) established security researchers, some of whom are already quite well known:

Andre' M. DiMino of the Shadowserver Foundation gathering, tracking and reporting volunteer group;
Mila Parkour, the independent blogger who in February first exposed the hacking of personal Gmail accounts belonging to military and government employees, and their associates;
Yuriy Khvyl, Malware Analyst with CSIS Security Group;
Someone called W---T--- (my guess is the American born painter and graphic artist James Abbott McNeill Whistler, 1834-1903, who faked his own death to continue his security research);
Jart Armin from HostExploit;
Marnie King;
Rossano Ferraris, Senior Research Engineer for CA Technologies ISBU;
and Chris Lee, a self confessed Unix geek with a love of security research and teaching.

The new group's first post, Dirt Jumper DDoS Bot - New versions, New targets, is a combined research and analysis effort by the first two named above. This is quite a piece of work - complete with its own table of contents! - and signals an intent to deliver on the promise held out by the new team's name.

Dirt Jumper, also commonly known as Russkill, is a cheap (~£200) commercial crimeware kit sold on the hacker underground. It works its DDoS magic by forcing tens of thousands of infected systems to request the home page of a targeted site, or more frequently, of many such sites en bloc. Brian Krebs was recently the focus of its attentions, an experience out of which he naturally blogged the living daylights.

Event Store Methods - part 2 of 2 (guest post)

2011-11-19T12:04:00.028Z

This is the second and concluding part of Colleague C's account of his experience using an Event Store within a system designed on the Command Query Responsibility Segregation (CQRS) pattern. All text references to actual projects and namespaces have been removed, leaving only the code snippets essential to the general discussion.

Previously: Aggregates, Entities and Events.

Applying and Replaying Events

Now I can finally get to the interesting implementation: how events are applied and replayed. It's important to understand how this happens for events applied far down the object graph, distant from the root. Most examples you’ll see online don’t go beyond the root level, and really lack infrastructure to propagate events down to the entities where they must be applied. Our implementation has been based around how the Ncqrs Framework handles these scenarios.

I’m going to detail how this is done, by going through the commands used for creating a new workflow, a stage for that workflow, and a tasklist for that stage. Let’s first take a look at the command handler for creating a new Workflow, which is pretty straightforward:

To take a look at how the events are being applied, we’ll need to have a look at the code inside that CreateWorkFlow factory method:

You can see here that some basic business logic is performed before the event is applied. Our little example application unfortunately isn’t very interesting, but it illustrates the point. When we make a call to that private constructor, before we reach that code, a call is made to the constructor of the AggregateRoot base class. Let’s have a look at that constructor:

The interesting bit is the mapping strategy. It alleviates the need to write code manually for registering event handlers, which are just methods on the aggregate root or entity. The mapping strategy implements an interface, so it would be possible to define other strategies, and you could have different aggregate root base classes using different strategies (rather that than inject the mapping strategy in; I prefer to keep the domain clear of constructor injection). You’ll notice that you pass a reference to the instance of the aggregate root into the method.

Let’s take a look at that method on the mapping strategy:

First, we get all the public and private instance methods on the target object. We then run a LINQ query to filter those methods to the ones starting with “On”, and having a single parameter implementing IEvent.

After that, we loop through each of those methods and create a delegate to call each, with a reference to the target object. This is important for the entity-based event handlers; if you have a set of children, you need to be able to handle an event on the correct child (we’ll come to this a bit later). The method is then wrapped inside an event handler, which has some logic to determine whether a particular handler can handle an event that it’s been passed. Finally, the list of handlers is returned to the aggregate root constructor, and the aggregate root adds each to its event handler collection.

In the case of the Workflow instance, a couple of event handler methods will be found:

We now come out of the base class constructor, and enter the constructor of the Workflow instance:

We can see that we’re now going to attempt to apply the WorkflowCreatedEvent to this instance, which takes us back to the AggregateRoot base class, since the Apply method is a protected method on the base. Let’s take a look at that:

Since we’re just creating the workflow at this stage, this call to GetNewEventVersion() is going to return 1. We then take a copy of the current list of event handlers - at this point in time, a couple of handlers. Why take a copy? During these event handler calls, other event handlers can be added to the aggregate root’s collection. Don’t be alarmed by this, it will make sense shortly! If you didn’t take a copy, you’d get an exception thrown, as you can't add items to a collection that you’re iterating over.

Anyway, we want to apply a WorkFlowCreatedEvent. We’re going to loop over all the handlers and figure out which one should handle this event. Remember that the event handlers are actually inside a wrapper, so the call to HandleEvent here will be a call into this wrapper method. It's a really simple method, and can be found by going to the EventHandler class:

Again, this is pretty simple. We figure out if this handler is to handle this event by checking that the type of event passed in is the same type as the first parameter on the handler (this type was passed in when we created the event handler in the mapping strategy). If it is, we’ll call the handler, passing in our event to be applied. Remember that the handler has a reference to a target, which in this case happens to be the Workflow instance.

As a result, we’ll end up calling the OnWorkflowCreated method on the Workflow instance, which will set its ID and title. After that, we’ll return back to the base Apply method. You’ll notice that we assign the AggregateId of the event in the base class. We need to do that after the event application, because in the case of an event that creates an aggregate, the ID would still be empty if we attempted to assign it before the event had been applied. It would also be possible to assign the AggregateId in the event handler, but it’s preferable to have that behaviour in the base class so it’s not forgotten. Finally, we add the applied event to the list of uncommitted events, get back to the private constructor that called the Apply method, then return to the static CreateWorkflow method, which will return our new instance back to our command handler.

The only thing that we need to do now to complete this command is to use the repository to save the Workflow that we’ve just created. Or more correctly, to save the WorkflowCreatedEvent we’ve just generated. The repository doesn’t do much. It has access to an IEventStore interface with a Store method to commit events. The aggregate root implements an IEventProvider interface, exposing a method to get the uncommitted changes, so this event provider is passed in through the Store method.

Here is a sample implementation of the Store method, using SQL Server based storage for the event store:

You can see it’s actually fairly straight forward. There is a concurrency check, that the current version of the aggregate root you’re about to save matches that of the stored one. Otherwise, someone has updated the same aggregate root during the time in which we’ve tried to apply other events. If everything is OK with respect to concurrency, each event is saved and published. The publish method will put the event on a queue without blocking, until it has been processed. Then, the version number is updated on the aggregate root, and updated in the Aggregates table. In the case of the exception there, I think that that exception should probably be wrapped up in some sort of EventStoreSaveException. That exception would then bubble up to the point where the command handler is being called, and you could deal with it in whatever way is appropriate.

With all that done, the command has now been handled successfully.

The next command will demonstrate how event handlers are registered on ‘child’ entities:

It’s worth taking a quick look at restoring the Workflow. Here’s the implementation of that repository method:

When the aggregate constructor is called there, we go through the same process as previously to register all the event handlers. After that, the previous events related to that aggregate are fetched from the event store, using a simple SELECT SerializedEvent FROM Events WHERE AggregateId = Id query. These events are then applied to restore the object to its current state. You call exactly the same Apply method already discussed. The only difference: when the object is restored, the applied events collection gets cleared at the end of the process, as you’re only interested in saving subsequently applied events.

So now that we have our workflow restored, we want to add a stage to it. If you take a look at the AddStage method, after performing a little bit of uninteresting business logic, we’ll apply a WorkflowStageAddedEvent. The event handler for this was registered when the aggregate root was being constructed, so we’ll find the event handler based on the type of the event. Eventually, this simple handler will be called:

This is obviously an extremely simple method. What's interesting is what goes on in the construction of the Stage class, which inherits from the base Entity class. You can see we’re passing a reference to the ‘parent’ aggregate root via the “this” keyword. The constructor for the Stage itself is pretty simple, the interesting work taking place in the base constructor:

It’s important for the entity to have a reference to its aggregate root. The event handlers for the entity get registered at the aggregate root level, because events are applied and saved at that level. We can see here that the exact same mapping strategy is used, as with the aggregate root. So, the same mechanism for finding event handler methods on the aggregate root is used for the Stage. Notice there that the reference passed into the mapping strategy is a reference to the current entity, rather than the aggregate root. This means any event handlers found are registered for this particular entity. In the case of the stage, there's one event handler method, OnWorkflowStageTaskListAdded. However, if the workflow had 6 different stages, you’d have 6 different event handlers - one for each stage instance.

This is why it’s key for the event handler to store a reference to the instance on which to call the method. If you remember back to the process of applying events, the aggregate root goes through its registered handlers, figuring out what handler to use by matching up the type of the received event with the type of the first parameter on the registered handler. The process is just slightly different for events on entities, which is why you put the event handler in a wrapper. Here’s the code that figures out whether the event gets handled in the case of the entity:

As you can see, there is actually a different type for entity based events. The difference is that the entity event exposes an EntityId property, which it uses to make a comparison. Remember, this method is being called from the context of an aggregate root. That’s why you have the first null check; non-entity-based events could be received by this method, in which case you'd return straight away, since you obviously can’t handle those.

The second check, to see whether we should use this handler for this event, is a comparison of the ID of the entity with the ID that got stored with the event. Again, if this test fails, we return; we need the correct instance upon which to apply the event. After passing all checks, we call into the same event handler code that the aggregate roots do, and this will just match up the parameter types.

So, for each handler found on the entity, a wrapper is created and registered with the aggregate root, rather than the entity. While these entities are being created, their handlers are registered. So when the item is being restored from the event store, and a WorkflowStageAdded event is encountered, this will create a new Stage and register its event handlers. This works no matter far down the object graph you go in terms of descendants: you will never encounter a WorkflowStageAdded event before a WorkflowCreated event, if everything has been versioned correctly.

When that Stage was created there, one event handler got registered - OnWorkflowStageTaskListAdded. This would be applied when you called the AddTaskList method on the Stage class.

I guess there's no necessity to walk through the essentially identical command logic to create a TaskList on a Stage. However, there is a difference in the event application on the entities, which is nicely handled in the base class:

The entity ID gets set. Again, it would be possible to do this in the event handler, but it’s easier to ensure it takes place on the base class. The important part again is that the actual application of the event takes place on the aggregate root, where the handler is registered. So, the event will be applied to the entity, then saved at the aggregate root level, and committed to the event store.

~ END ~

Event Store Methods - part 1 of 2 (guest post)

2011-11-19T08:32:00.007Z

Those QC articles were a long squawk, chomping chunks from evenings and weekends over a big month. While I recover, trying to remember what free time and my wife look like, Colleague C has kindly consented to guest blog the following, to help make up the numbers. It's all about discovering the delights of using an Event Store, within a system designed on the Command Query Responsibility Segregation (CQRS) pattern. Having edited the article slightly for style and panache, I'm bound to assume responsibility for any errors thus introduced. Ladies and gentlemen, His Code Here proudly presents: Colleague C!

Aggregates, Entities and Events

In our system based on an event source, objects are restored to their "current" state by replaying a set of ordered historical events. The one canonical example most often used to describe event sourcing is the common or garden bank account. Your account has a current balance, but you don’t just store that balance - you arrive at it, via a historical record of debits and credits, re-applied from an initial (empty) starting point, to eventually produce the current balance.

Events are simple objects containing no behaviour; they just describe the event in terms of a set of property values. They are ordered using a version number. When you want to restore an entity to its current state, you fetch the events relating to it, order them by version number, then apply them in order. Application of events involves nothing more than changing the state of the entity - there is no logic when an event is applied. This is because historical events which have already been applied, and saved, must always be re-playable and never subject to failure, so that the entity can be restored.

What would happen if business logic were to be included in event application? Business logic is something that potentially changes throughout the lifetime of an application. Initially, for example, you might have a text field on an entity, defined to have a size limit of 255 characters. When applying your event, you would validate that the field contained no more than 255 characters, and everything being OK, you'd proceed with the event application. Later on down the road, a decision is made to change the size limit of this field to 50 characters. So an event in the past that applied 150 characters to that text field is now invalid, in the context of this new rule, and an exception will be thrown - meaning you can’t restore your entity.

Business logic always occurs before you apply an event. And, an event is only applied to the entity if the requested operation is valid by all business rules.

When events are applied to effect changes on entities, obviously they do change the state of the entity, but what we’re presently interested in is the collection of newly applied events, rather than the state change. In event sourcing, when you persist an entity, it’s not like persisting objects with a traditional database style approach. There, you change the state of the entity, then save its new current state in some table(s). When you save an entity in an event sourced system, you save just the newly applied events. In this context, the state change resulting from a new event application is a mere side effect! One that of course does no harm.

The storage of events is very straightforward, and many options are available. One is to use a very simple database schema, consisting of just two tables:

The Aggregates table contains a list of all the aggregates in the system, with the ID of the aggregate, its Type (for debugging purposes only), and the current version. This last is a little optimisation.

Each row in the Events table describes one event, using:

an AggregateID identifying the aggregate to which the event relates;
the version of the event; and
a serialized representation of the event, containing all property values that need to be applied.

Note that the Aggregate ID column will usually be indexed, since all queries retrieving events will use it.

A crucial point here is that events are always saved and applied at the aggregate root level. It might take a bit of time to illustrate this point, but I’ll explain this in the context of a simple model. In our example, a workflow has a title and a collection of stages. Each stage has a title and a collection of task lists. Each task list has a title. We might take it a bit further and say that each task list has a list of tasks, but we’ll stop at the task list. Now let’s describe the model using domain driven design terminology.

First I'll introduce some important terms for the benefit of people who perhaps haven’t read the Eric Evans book Domain-Driven Design: Tackling Complexity in the Heart of Software. When I was first reading about this stuff via blog posts and articles found on the net, the terms aggregate and aggregate root were used in such ways, I wondered if they were synonymous. Perhaps I had also been a bit confused by looking at code from DDD example projects, where the terms used in the book don’t quite map directly to the code (I’ll come to that shortly). Since I won’t explain it better than Eric, I’m going to quote his definition:

An Aggregate is a cluster of associated objects that we treat as a unit for the purpose of data changes. Each aggregate has a root and a boundary. The boundary defines what is inside the Aggregate. The root is a single, specific Entity contained in the Aggregate... Entities other than the root have local identity, but that identity needs to be distinguishable only within the Aggregate, because no outside object can ever see it out of the context of the root Entity.

We can now attempt to describe our model using these terms. The entire diagram represents the aggregate and its boundary, and we see from it that our workflow is an entity, our aggregate root. A stage is an entity that's a child of a workflow. It only has local identity, as we'll only ever be interested in a stage in the context of a workflow instance. Similarly, a task list is an entity that's a child of a stage. It has identity local to the stage instance (although still local to the entire aggregate too), as we'll only be interested in a task list in that context. However, as I mentioned a bit earlier, it’s important to note that the task list, despite being a child of a stage, still refers to the workflow as its aggregate root, and not the stage.

It’s particularly important in the context of the implementation, where a reference to an aggregate root is maintained down the entire graph of an object. This is necessary so we can save and apply events at the aggregate root level. Even when we want to save new events that have taken place on children, such as adding a task list to a stage, still we need to save the entire aggregate root. After all, events always relate to an aggregate root - remember, we query by AggregateID to retrieve them.

So, how exactly do the proper terms fail to map exactly on to the code?

You can see that our Workflow class inherits from an AggregateRoot class, which happens to be an abstract base class. Since we mentioned that a workflow is an entity, perhaps we might expect to see it inheriting from Entity? Then we would have a reference to it inside some aggregate root class. Well, as just mentioned, the AggregateRoot class is abstract. It doesn’t really make sense to create an instance of that; you’d rather create instances of actual concrete aggregate roots. So, even though an aggregate root is an entity, in the code we’ll define any root entities as inheriting from AggregateRoot.

There is also an Entity abstract base class. Stage and TaskList inherit from this. In the code, entities that are not aggregate roots must have a reference to an aggregate root. The entity has a protected AggregateRoot field, a reference to the ‘parent’ aggregate root, although as hopefully my previous explanation will have made clear, this is not really a parent. The AggregateRoot must be passed into the entity's constructor. The only reason that it’s protected as opposed to private is so it can be passed, when a concrete entity creates a child, into the new child.

Both of these base classes provide all the behaviour for managing event application and replaying.

Having established all that, I can finally get to the interesting implementation: how events are applied and replayed.

Next time: Applying and Replaying Events.

Quantum Computing #5: Quantum Teleportation

2011-11-10T21:00:00.007Z

Previously:

Introduction
Single Qubit Gates
Multiple Qubit Gates
Measurement & Review
Superdense Coding

Beam Me Over

If you took the time to digest the previous article on the Superdense Coding protocol, you'll find comparatively few surprises in this one. Remember how two entangled qubits were initially prepared in a special Bell State; then one was sent directly to Bob, while Alice processed the second to encode two classical bits of data. Later, Bob successfully decoded those two classical bits. Didn't it seem to you as if Alice somehow reached across the divide, fiddling with the independent states of both qubits, using some kind of spooky action at a distance?

The Quantum Teleportation protocol is a very similar trick. In fact, you could say that it's exactly the same trick, but performed in reverse. This time, using the magic of the entangled qubit pair, and precisely the same set of quantum gates as before, Alice will teleport to Bob the full state vector of an arbitrary third qubit - using only two classical bits of information.

There are three preliminary, new, key concepts - all related to the notion of measurement - that we'll need in order to investigate and explain the Quantum Teleportation phenomenon today. The first of these is:

The Measurement Basis

Specifically, the performance of a measurement in an arbitrary basis. Recall that in part one we said the labels 0 and 1 might represent unit steps in some arbitrary x- and y-directions. When later we made a measurement in the computational basis, we were in effect holding up a filter, constraining the result to be either 0 or 1 in this sense. But we are free to change this basis!

To take a brief physical detour, suppose our qubit is a photon, and measurement involves holding up a pair of polarized sunglasses, either horizontally or vertically, to see whether or not the photon gets through the lens. We know there's a 50-50 chance it that will, simply because holding up two such identical and overlapping lenses, one horizontally and one vertically, will prevent any photons from getting through. But what's to prevent us holding our sunglasses at ±45° to the horizontal?

Nothing. All we're doing is changing the basis of measurement, from the original computational basis, i.e. horizontal 0 or vertical 1, to this new one, where perhaps 0' and 1' mean pointing respectively up or down at 45°. From the diagram we see these new basis vectors can be expressed readily in terms of the originals, like this:

0' = (0+1)/√2,
1' = (0-1)/√2.

But this is precisely the state transformation performed by the Hadamard gate. Now we can see that it corresponds to a particular reflection, in a line at 22½° to our basis 0 vector (the light grey line in the diagram is this axis of symmetry). Incidentally this illustrates nicely why the Hadamard gate, like any reflection, is its own inverse; since we also have these perfectly symmetrical equations,

0 = (0'+1')/√2,
1 = (0'-1')/√2.

And just as 0' and 1' give us an alternative orthonormal basis for measuring single-qubit states previously expressed in terms of our original computational basis 0 and 1, so too are there any number of alternative bases for a given multi-qubit measurement. One important example in 2-qubit systems is:

The Bell Basis

This is today's new concept number two. Starting from any given 2-qubit computational basis 00, 01, 10 and 11, the Bell basis can be defined as

B₀ = (00+11)/√2,
B₁ = (10+01)/√2,
B₂ = (00-11)/√2,
B₃ = (10-01)/√2.

Notice that these four are exactly the states that Alice prepared last time, in the Superdense Coding protocol, by inserting either an X or a Z gate (or both, or neither) into the path of the top qubit of a pair - an entangled pair, which happened to have been prepared in a certain special initial state. We now recognise that state as B₀ = (00+11)/√2.

Exactly as before, it's easy to check by substitution that we can express the Bell state mapping the other way round, for convenience in our subsequent conversions:

00 = (B₀+B₂)/√2,
01 = (B₁-B₃)/√2,
10 = (B₁+B₃)/√2,
11 = (B₀-B₂)/√2.

Partial Measurements

Our third and final new concept of the day is that of a partial measurement. What happens to a composite, multi-qubit state when we perform measurements upon some, but not all, of its constituent qubits? Answer: measured qubits collapse into appropriate basis states in accordance with the probabilities in effect, while unmeasured ones continue in renormalized superpositions.

Take for example the 2-qubit state (a, b, c, d) = a00 + b01 + c10 + d11, and suppose that we perform a measurement, in the computational basis, on its first qubit. Then the probability of getting a result of 0 is simply the sum of the probabilities of getting either 00 or 01 from a full, 2-qubit measurement. Similarly, the probability of a 1 is just the sum for 10 and 11:

prob(0?) = prob(00) + prob(01) = |a|² + |b|²,
prob(1?) = prob(10) + prob(11) = |c|² + |d|².

Okay, that tells us everything we can ever know about the first qubit. What can we say about the posterior state of the second qubit, i.e., its state after this partial measurement? We can answer this by rewriting the original state, collecting terms involving a result of 0 or 1 for the first qubit measurement:

(a, b, c, d) = a00 + b01 + c10 + d11 = 0 (a0 + b1) + 1 (c0 + d1).

This lets us read off the result. If the measurement yielded 0 for the first qubit, then the second qubit is now in the state indicated by a0 + b1, which of course we must renormalize as usual:

(a0 + b1) / √(|a|² + |b|²).

Similarly, a measurement of 1 for the first qubit implies that the second is now in this state:

(c0 + d1) / √(|c|² + |d|²).

Quantum Teleportation

Now we finally have enough background to understand the Quantum Teleportation protocol, which is illustrated in the diagram below. Alice starts with an arbitrary qubit state which I've called ψ, pronounced sigh, out of deference to 86 years of quantum mechanics... sorry about that!

So Alice starts with ψ = (a, b) = a0 + b1, where |a|² + |b|² = 1. This is the state she wants to communicate to Bob; and she also has access to one qubit of an entangled pair, previously prepared in the state

B₀ = (00+11)/√2.

She now performs the "decoding" second half of the Superdense Coding protocol on her two qubits. So that's a cNOT, followed by a Hadamard on the first qubit, then a 2-qubit measurement. Remember, this was the operation performed by Bob last time, and it yields a couple of classical bit results. We've shown these as thick double wires, intended to give the impression of big, strong, macroscopic classical logic levels, insusceptible to decoherence. This decoding operation is actually termed a measurement in the Bell basis. Furthermore, in this setup it's a partial measurement. Recall that we are dealing with a system of three entangled qubits, but measuring only two of them. The third, the bottom one in the diagram, is simply transmitted directly to Bob.

Now Bob examines those two classical bits of data he's received from Alice, and uses them to decide which, if any, of his decoding X and Z gates to apply. His logic is exactly the reverse of the "encoding" step used in the first half of the Superdense Coding protocol. And that's all there is to the Quantum Teleportation protocol; the output that Bob ultimately obtains is identical to Alice's initial, arbitrary state ψ.

I Don't Believe You

And who can blame you! Okay, but be warned: I'll be renormalizing throughout today, so as to avoid any sleight-of-hand accusations. So let's start with the initial state of the 3-qubit system,

(a0 + b1)(00 + 11) / √2 = [a (000 + 011) + b (100 + 111)] / √2.

Alice begins by passing the first two qubits through a cNOT gate. This flips the state of the second qubit in the last two terms, i.e., those where the first "control" qubit is 1, resulting in the state

[a (000 + 011) + b (110 + 101)] / √2.

Next she passes the first qubit through a Hadamard. The effect of this is to replace every initial 0 with (0+1)/√2, and every initial 1 with (0-1)/√2. Collecting terms and combining the √2 divisors, we now have the state

[a (000 + 011 + 100 + 111) + b (001 + 010 - 101 - 110)] / 2.

This is the point at which Alice performs the partial measurement upon the first two qubits. The probability of her getting a result of 00 is

prob(00?) = prob(000) + prob(001) = (|a|² + |b|²) / 4 = ¼,

since |a|² + |b|² = 1. And in fact if you work out the remaining probabilities for results 01, 10 and 11, they all turn out to be ¼. Think about that - the measurement outcome is absolutely random, and completely independent of the particular state of the input qubit ψ! This happens because - thanks to the cNOT and H gates - we are performing the measurement in the Bell basis, and not in the original computational basis where we started.

Fascinating as this detail may be, nevertheless it's not quite what we're after here. We want to know the posterior state of the third qubit. This does depend critically upon the particular 2-bit classical result just obtained, so just as in the Superdense Coding protocol, we now have four distinct cases to consider.

________

Case 00: keeping only the 000 and 001 terms from our state expression and renormalizing, we obtain the state received by Bob:

00 (a0 + b1) = 00 ψ.

That's the magic of quantum teleportation! Without doing anything further, Bob knows from the classical measurement 00 that his third qubit is already in Alice's initial state, ψ.

________

Case 01: keeping only the 010 and 011 terms from our state expression, and renormailzing, we obtain the state received by Bob:

01 (a1 + b0).

Notice however that the 1 bit in the classical measurement result activates the X gate in Bob's decoding circuit, causing a logical inversion of the third qubit, and a final state of

01 (a0 + b1) = 01 ψ.

Again, Bob has successfully received Alice's full state ψ in that third qubit.

________

Case 10: keeping only the 100 and 101 terms from our state expression, and renormailzing, we obtain the state received by Bob:

10 (a0 - b1).

Notice however that the 1 bit in the classical measurement result activates the Z gate in Bob's decoding circuit, causing a sign change in the second basis component of the third qubit, and a final state of

10 (a0 + b1) = 10 ψ.

Again, Bob has successfully received Alice's full state ψ in that third qubit.

________

Case 11: keeping only the 110 and 111 terms from our state expression, and renormailzing, we obtain the state received by Bob:

11 (a1 - b0).

This time both bits in the classical measurement result are 1, so this state becomes subjected to both the full logical inversion and the phase (sign) change, and the final 3-qubit state is

11 (a0 + b1) = 11 ψ.

So in all four cases - in other words, regardless of the outcome of the partial measurement operation - Bob has successfully received Alice's full state ψ in the third qubit.

________

Interactive Demo

Once again Brad Rubin steps up with the Wolfram Demonstrations Project simulation of the Quantum Teleportation protocol, a model of clarity:

This ingenious demo lets you vary both the arbitrary input state ψ, by dragging the indicator point in the upper graph, and the 2-qubit partial measurement result, using the radio buttons below it. Intermediate states of the 3-qubit system are displayed as continuously updated column vectors.

Picture of Star Trek transporter chamber from Wikipedia.

Quantum Computing #4: Superdense Coding

2011-11-06T00:01:00.003Z

Previously:

Introduction
Single Qubit Gates
Multiple Qubit Gates
Measurement & Review

Note: Last week's removal of Greek lettering and matrices has proved too popular to ignore, all feedback being either positive or neutral, so I'll continue using this "new" notation wherever possible.

Breaking News! A single qubit can transmit two full classical bits of information.

Not on its own, though. We can only ever encode one single classical bit of information into a solitary, unentangled qubit. But when we have access to an entangled pair, we can choose to send one unmodified to our intended recipient, and encode a full two classical bits into the other. To see how, we'll have to examine four quite similar quantum circuits. And we'll need the help of a new single-qubit gate we haven't met before:

The Z Gate

Like its partner the X gate, Z is a kind of inverter. It maps the input qubit state (a, b) to (a, -b). We say that it inverts the phase of the second basis vector. For the sake of completeness alone, here is its matrix representation:

Preparing the Bell State

The two qubits that we'll be using to perform the superdense coding trick have to be entangled, so first let's see how to achieve that. One way is to prepare them both initially in the 0 state. Next, we pass the first qubit of the pair through a Hadamard gate. Finally, we use the output of the H gate as the control input of a controlled-NOT gate, conditionally inverting the second qubit:

The H gate converts the first 0 into 0+1, where I'm going to use '+' and '-' to mean "normalized vector sum" and "normalized vector difference", just to get rid of all the visual noise generated in the calculations by incessant divisions by √2. Since the second qubit remains at 0, the combined state after the H gate is 00+10. Nothing strange about this so far; all it says is that a measurement on the first qubit will yield either 0 or 1, each with 50% probability, while a measurement on the second qubit will still yield 0, with 100% certainty.

Next, the qubits arrive at the cNOT gate. This has no effect upon the first part 00 of the superposition, since there the control (first) qubit is 0. However the second part, 10, has a 1 in the control bit position, causing the cNOT gate to invert the second qubit. The combined state at the output of the cNOT gate is therefore 00+11.

This is termed a Bell State, and it's actually a fairly remarkable state when you think about it. It says that the qubit pair is in a perfectly balanced superposition of the 00 and 11 states. Expressed as a sequence of renormalized amplitudes, it is

(a, b, c, d) = (1/√2, 0, 0, 1/√2)

Since |a|² = |d|² = ½, while |b|² = |c|² = 0, this says that a measurement is equally likely (50%) to yield 00 or 11, and to do so absolutely randomly; but it can never yield 01 or 10. Now if you measure just one of the qubits, whatever result you obtain, 0 or 1, you'll get exactly the same outcome when you measure the second qubit. Even if it's hours or years later, miles or light years away.

Encoding and Decoding

Remember that both Hadamard gates and inverters are their own inverses. If we were to make a mirror image of the above diagram and then join the two together, our final output state would be the same as the originally prepared 00, with probability 100%. This mirror image decoder is shown below, if we temporarily ignore the "?" gate (imagine it to be just a quantum wire, or an Identity gate I):

Suppose Alice is in charge of the "?" box, and Bob is performing the final measurements. Alice wants to send 2 classical bits of data to Bob, but she's only allowed to operate upon the first of the two qubits (the top one in the diagram) to do it. What should she put in the "?" box?

Well, if the bits she wants to send are 00, then she need apply nothing but a simple quantum wire, since we've just seen that this will result in Bob's measurements yielding the result 00 with 100% certainty. In the more general case, she needs to examine both of the classical bits that she wants to send. If the first is 1, then she should add our new friend the Z gate in place of the "?". If the second is 1, she adds an X. Note that if both bits are 1, she will now have added both a Z and a following X.

00 → I
01 → Z
10 → X
11 → Z followed by X

And that's all there is to the Superdense Coding Protocol. With those arrangements in place, Bob's measurements will always yield, with 100% certainty, the particular combined state 00, 01, 10, or 11 that Alice wanted to send him.

I Don't Believe You

No, you'd be mad to, unless you're already a QC expert! We'll go through the four cases individually in detail. Remember, the starting point for Alice is in each case the Bell State 00+11. It will also be useful to remember the reversibility of the H gate. Just as it converts basis states 0 and 1 respectively into their sum 0+1 and difference 0-1, so when presented with a sum 0+1 at its input, does it output 0; and with a difference 0-1, output 1.

Case 00: We already established, using an argument based on considerations of symmetry, the correct operation of the circuit for this first case. Still, it's worth running through the detailed sequence of decoding steps, since these are the same for all subsequent cases. So: Alice does nothing to the 00+11 state, which is then passed immediately into the second cNOT gate. This has no effect on the 00 portion of its input, but changes the 11 part (because the first, control bit is 1) into 10. The cNOT output is therefore 00+10. The first of these qubits, 0+1, is fed to the second Hadamard, which as mentioned above, converts it to 0. Therefore, the final 2-qubit output is 00, with probability 100%.

Case 01: Alice inserts an X gate in the path of the first qubit, converting the initial 00+11 to 10+01. The cNOT changes this to 11+01, feeding the first qubit 1+0 into H, which outputs 0. Therefore, the final 2-qubit output is 01, with probability 100%.

Case 10: Alice inserts a Z gate in the path of the first qubit, converting the initial 00+11 to 00-11. The cNOT changes this to 00-10, feeding the first qubit 0-1 into H, which outputs 1. Therefore, the final 2-qubit output is 10, with probability 100%.

Case 11: Alice inserts both a Z and a following X into the path of the first qubit, converting the initial 00+11 first to 00-11 as in the previous case, then to 10-01. The cNOT changes this to 11-01, feeding the first qubit 1-0 into H, which outputs 1. Therefore, the final 2-qubit output is 11, with probability 100%.

Quantum Erat Demonstrandum!

The second most surprising thing about Superdense Coding - other than the fact that in reality, it works exactly as advertised! - is the time it took to get itself discovered. The whole subject of Quantum Mechanics was kicked off by Werner Heisenberg in 1925, with Quantum Computing eventually appearing with Richard Feynman in 1982; yet it was a further ten years after that before the definitive Bennett & Wiesner paper appeared, noting that certain "EPR" (Einstein-Podolsky-Rosen) states "allow two bits to be encoded reliably in one spin-½ particle..."

Interactive Demo

The Wolfram Demonstrations Project contains a great interactive demo of the Superdense Coding protocol, one of several contributed by Brad Rubin. This varies a little from the our example, specifically in the order of the X and Z gates during the 11 case, but the difference vanishes during final measurement. You interact with it by downloading the Computable Document Format (CDF) Player, and optionally the Superdense Coding demo file itself, which looks like this:

As you can see, it displays all the intermediate states of the qubits during this quantum computation - and fully normalized, hence all the "1/√2"s.

Footnote

In this series I've been avoiding discussion about the physical realisation of qubits, but the day after I posted this comment on digital simulator Logicly's Facebook page...

Has anyone ever asked for a quantum circuit version? You seem to have all the component building and layout logic that would require. Qubit signals: rather than boolean, these would be pairs of complex numbers (or quadruples of floats), and there would be a "measurement" gate with a classical boolean 0 or 1 output. Now seems a good time to start training up on these!

... noted futurologist and SF author Charles Stross predicted room temperature quantum computing on integrated circuitry within 5 to 20 years, based on a fascinating discovery about silicon carbide. My guess is that many more suitable materials will be discovered quite soon, making available QC technologies that will have absolutely no trouble attracting capital investment at the left hand edge of that range.

Next time: Quantum Teleportation.

My Work in Print: 1985

2011-11-05T21:00:00.004Z

I've previously written about the very competitive crafting of optimum machine code programs for Personal Computer World magazine's 1980s Sub Set series, here and there. In 1985, the incumbent series editor David Barrow convinced Century Communications to publish two books of the best submissions. According to the descriptions on their publication history pages, these books were "Edited and produced working directly from the author's word-processor by NWL Editorial Services, Rushley, High Ham, Somerset" - a huge novelty in the publishing world at the time. Book geeks: note the cool adjacent ISBNs!

Best of PCW Assembler Routines for the Z80

Although the first IBM PC with its 8-bit Intel 8088 chip had already been available for about four years, still most business software was based on the CP/M operating system, and the more powerful, backward compatible Zilog Z80. Joined to legion Sinclair hobbyists, these users constituted quite an army. Here is the index of my contributions to the Z80 edition:

ECAL - Calculate error correction byte; pp. 70-71.
EFIX - Validate data with error correction byte; pp. 71-72.
NEWPC - Anticipate PC contents after next instruction; pp. 78-82.
RDM32 - 32-bit pseudo-random number generator; pp. 147-149.
SQR31 - Square root of 32-bit signed (positive) value; pp. 169-170.
SQR32 - Square root of 32-bit unsigned (absolute) value; pp. 169-170.
CURT16 - Cube Root of a 16-bit unsigned integer value; pp. 170-174.
CURT32 - Cube Root of a 32-bit unsigned integer value; pp. 174-176.
SDIV4 - 4-byte signed integer division; pp. 183-185.

Barrow, David (editor)
Best of Personal Computer World Assembler Routines for the Z-80
Century Communications Ltd
1985
ISBN 0 7126 0506 1

Best of PCW Assembler Routines for the 6502

While businessmen cycled their Z80s, many hobbyists with an aversion to dead-flesh rubber keyboards were devouring Commodore VIC-20s and 64s, and Acorn's BBC Micro. All of these used the MOS Technology 6502 processor. Here is the index of my contributions to the 6502 edition:

RINXY - Register Indirect addressing mode emulator; pp. 20-22.
ECAL - Calculate error correction byte; pp. 88-90.
EFIX - Validate data with error correction byte; pp. 90-91.
SQR15 - Square root of 16-bit signed (positive) value; pp. 125-127.
SQR16 - Square root of 16-bit unsigned (absolute) value; pp. 125-127.
SQR31 - Square root of 32-bit signed (positive) value; pp. 127-129.
SQR32 - Square root of 32-bit unsigned (absolute) value; pp. 127-129.
CURT16 - Cube Root of a 16-bit unsigned integer value; pp. 129-134.
CURT32 - Cube Root of a 32-bit unsigned integer value; pp. 134-137.

Barrow, David (editor)
Best of Personal Computer World Assembler Routines for the 6502
Century Communications Ltd
1985
ISBN 0 7126 0507 X

A Disassembler in ~1KB

Colleague C keeps reminding me that The SUBSET editor David Barrow was able to trim only one byte from John Kerr's compact code. What the hell is he talking about? The quote comes from this ZX Spectrum Utility, whose author explains: The stated aim was to write a Z80 disassembly routine in as short a space as possible and, at just over 1K (1090 bytes), it is a rather incredible program.

Unfortunately my DISZ80 routine was submitted too late - by about two years - for inclusion in the book, and I no longer have the magazine that it appeared in. At the risk of sounding a bit JR Hartley, if anyone out there has that 1987 issue, it would be good to be able to restore the line comments to the utility. I work in self-documenting, high level languages now, eschewing comments almost universally. But part of the strict Sub Set documentation standard insisted that every single machine code instruction got fully commented. Oh, and it would also be nice to see exactly where Dave Barrow's one-byte optimization appeared!

Cube Root Algorithm

I derived the method of cube root extraction used in both books, by applying a kind of induction by analogy to the existing square root algorithm. Dave thought my description of the process sufficiently interesting to publish it. Click for readability:

I Hate Susan Adele Greenfield

2011-11-04T18:51:00.027Z

With A Vengeance

I think I've despised her since puberty. Mine, not hers. Which was of course some decades ago, and it certainly feels so long, and the hatred so matured, since first I saw her interviewed on some godforsakenly neurological or psychological subject or another. In an age of great expositors, of scientific enlightenment and the engagement of the public, of TV with James Burke, Jacob Bronowski, Carl Sagan, Patrick Moore, Nigel Calder... it seemed perfectly clear to me, from my viewpoint of almost complete ignorance of the subject, that she was winging it. Faking it. Had absolutely no clue what she was talking about. Was doing nothing more than trot off her own personal preconceptions and prejudices, representing these as scientific fact. Cod philosophy claptrap about consciousness and identity.

Now I am delighted to discover that all this time, almost everyone else with an opinion about her has been quietly in agreement with mine. Quietly, because she seems also to be one ferociously litigious bitch.

Recently sacked - sorry, wishful thinking there - recently made redundant (January 2010) from her job as Director of the Royal Institution, for having driven that esteemed charity into a £3M debt crisis and near bankruptcy with her ineffective £22M renovation of its still unpopular Albemarle Street wine bar, her response was to sue the world's oldest independent research body for supposed "sex discrimination". And win an out-of-court settlement, what's worse. At least the lawyers had the decency to prevent her blabbing about it, otherwise she might have continued badmouthing the Institution's venerated custodians to this day, milking it for publicity - she has just written her first novel, you see. Appropriately enough, given her press profile (see below), it's a work of fiction about the effects of technology on the mind.

In fact, the abolition of the post of Director was the only legal means anyone could find of getting rid of her. So if you grew up as I did, watching faithfully each year's Royal Institution Christmas Lectures, and if you wondered why at the turn of the millennium they took a swerve from their rightful home on BBC Two, wandering aimlessly and destitute through Channel 4, Channel Five, More4 and BBC Four, begging for commercial scraps while their resources and their scale, if not their scope, dwindled; well, now you know precisely whose catastrophic mismanagement was to blame for their woes.

Retractable Roof and Patio

Greenfield sold off the institution's entire £15m Mayfair property portfolio to raise funds. At the same time as the wine bar fiasco, a flat she used was refurbished with a retractable roof and patio. She got her arse kicked out of that: "The flat only came with the post," said an RI representative, "[and] she is no longer in the post, so it would be inappropriate if she used it." To her credit perhaps, she did not even try to defend herself at the time, saying only "Redundancy is supposed to be about the post, not the person. So my personal performance should not be relevant." A resolution proposed by her supporters that would have led to the replacement of the RI's council, paving the way for her return as director, was defeated by an overwhelming margin. On BBC Radio 4's Today programme she squirmed: "I was charge of the organisation and I was the person who had the vision. The financial decisions were collective." Last August she told the London Evening Standard's Sophie Goodchild, her epitaph would be “She knew herself, and had a laugh.”

Yet for me, the worst slight of all is that the bogie herself presented the Institution's 1994 lectures. This was in my view an unspeakable act of scientific and cultural vandalism, to daub her all-cursed name on so pristine a list stretching back to Michael Faraday (pictured), their 1825 initiator. A list containing too my contemporary heroes of science and technology: Desmond Morris, Bernard Lovell, Eric Laithwaite, Richard L Gregory, George Porter, John Napier, David Attenborough, Heinz Wolff, Carl Sagan, Lewis Wolpert, Richard Dawkins and Ian Stewart, to name only some of the presenters I've personally enjoyed over the years.

The Greenfield and her demented slobbering have naturally had a well documented exposure in the gullible press. She has been responsible for a rash of scare stories spouting baseless drivel about the dangers of the Internet and video games, like the Daily Mail's Social websites harm children's brains: chilling warning to parents from top neuroscientist or Computer games leave children with 'dementia' warns top neurologist, or the Telegraph's Baroness Susan Greenfield: society should wake up to harmful effects of internet or Computers could be fuelling obesity crisis, says Baroness Susan Greenfield. Serious claims, backed up by absolutely no published research.

Hypocrisy and Fraud

Why then does she promote these "harmful" games for her own personal financial gain? That reeks not merely of a Carol Vorderman-like level of hypocrisy, but of fraud. For example, out of three studies that she claims prove the £88 game MindFit improves mental abilities, two had "basic design flaws" (no control group, the most fundamental scientific defect of all), while the third failed to show the game was any more effective a mental stimulation than playing Tetris. Maybe she's not actually a scientist at all. Writing in The Guardian, Doctor Ben Goldacre has wondered why she has never formally written up and published her claims of imagined technological harm, with evidence to back them, rather than continuing to use the media as a platform for her pet hypotheses on technology's evils:

Baroness Greenfield has a theory that computers – which are extremely widespread – pose a serious environmental hazard to children. She therefore has a clear duty to her peers, and more importantly to the public, to present this theory clearly and formally in an academic journal, with the evidence, so that her scientific peers can assess the threat.

Greenfield's response was to liken Goldacre to certain epidemiologists who denied that smoking causes cancer. "That seems to me to be simply offensive, and unhelpful", he comments. Sounds to me more like the raving of some mad third world dictator, than the output you'd expect from our most eminent female scientist. But I think Ben, who has had her in his telescopic sights for some time, dealt her a killer blow today, when on his primary blog Bad Science he asked again, this time getting both slashdotted and echoed on Boing Boing:

Why, in over 5 years of appearing in the media raising these grave worries, has Professor Greenfield of Oxford University never simply published the claims in an academic paper?

Which reminds me, Ben's on QI tonight, so I'll have to curtail my torrential diatribe at this point. Baroness Greenfield: in my humble opinion, you are a disgrace to your profession, to science, to neuroscience and pharmacology, to writing, and to broadcasting; an embarrassment to the peerage; an ugly carbuncle upon the arse of the British Empire; and a poisonous force for evil, ignorance, and prejudice in our world. Either STFU, or DIAF.

Pictures of Greenfield and Faraday courtesy of Wikipedia.

Algebra of Functions, Part 4: Parsers

2011-11-01T09:00:00.006Z

A Series of Tubes

Note: this 2010 series of articles (part one, two, three, 3½) was abandoned incomplete when overtaken by events at the Microsoft C# compiler factory. My utimate target, actually intended to be the article right after this one, was the Continuation Monad; but Eric Lippert got there before me with a surprise sprint (Continuation Passing Style Revisited, part one, two, three, four, five) leading up to his introduction to async/await marathon (Asynchrony in C# 5, part one, two, three, four, five, six, seven, eight). The only reason to publish this short excerpt now is to have a convenient index into the work of Brian McNamara and Luke Hoban, as linked at the end.

Today we take a look at another popular exhibit from the monad menagerie: the Parse monad.

Parsing is such a popular example of the application of monads, because it so neatly fits the characteristic template of a data processing pipeline with side effects. When parsing a string into any given language, each successive step

consumes part of the input string, and then
passes the remainder on to the next step in the sequence.

That constitutes the main process. But as a side effect, the just-parsed value is also made available in some way. This might be a keyword of the language, the name of a variable, or perhaps a binary value representing a data value of some particular type; but it could equally well be discardable whitespace, or any character, etc.

In terms of our monad then, the unamplified type is the input type string. The amplified type, which must be capable of holding all of the output from an operation of parsing, needs to store both a string, representing the remainder of the unconsumed input, and another, parsed value, of some arbitrary type.

Language geeks love all monads and parser combinators in equal measure, and there is a wealth of information about all this stuff on the web. As for C#, one of the best and most detailed I've seen is Brian McNamara's December 2007 series, "Monadic Parser Combinators", which gets as far as Part Eight before surrendering to F#:

Part: One, Two, Three, Four, Five, Six, Seven, Eight.
Source: Part 4, Part 5/6.

Very succinct and readable is Luke Hoban's contribution, also from 2007:

Monadic Parser Combinators using C# 3.0

Quantum Computing #3: Measurement + Review

2011-10-30T08:00:00.025Z

Previously:

Introduction
Single Qubit Gates
Multiple Qubit Gates

Why One?

When we looked at the state of a single qubit, ψ = α0 + β1, we noted that this vector had to be of unit length, a stipulation encoded in the normalization condition |α|² + |β|² = 1. Similarly when we extended to a 2 qubit system, ψ = α00 + β01 + γ10 + δ11, we maintained the analogous constraint |α|² + |β|² + |γ|² + |δ|² = 1. This was accomplished by only ever applying so-called unitary (magnitude-preserving) matrix operations to the current state.

The reason for this has to do with the method of getting results out of a quantum computer, which is done by the process of measurement. The outcome of a given measurement operation can be any one of the system's basis states. that is, it will be either 0 or 1 for a single qubit system; 00, 01, 10 or 11 for a 2-qubit system; and so on. Which of the basis states actually gets detected depends upon various probabilities, and in fact these probabilities are just |α|², |β|², etc.

So to clarify, when we perform an operation of measurement in the computational basis on an n-qubit system, we are effectively forcing the state vector to settle into one of its 2ⁿ basis states. Taking the 2-qubit case as an example, the result of the measurement will be either

00 with probability |α|²,
01 with probability |β|²,
10 with probability |γ|², or
11 with probability |δ|².

Since these are the only possible outcomes, it's easy to see why the sums of the squares of the coefficients α, β, γ and δ must be unity - after all, there's a 100% probability the outcome will be one of these states!

Destructive Read

The measurement operation irrevocably destroys the previously existing superposition of states, leaving only the single basis state that is the result of the measurement. This means that the original state can never be directly observed. All that we can ever know about it comes from the results of destructive read operations.

For example, suppose we prepare a qubit in the 0 state, then immediately make a measurement. What will the outcome be? Well, the qubit state is ψ = 0 = α0 + β1, where α = 1 and β = 0. Measurement will deliver either the state 0 with probability |α|² = 1 (100% certainty), or else the state 1 with probability |β|² = 0 (0% impossibility). So far, so perfectly common sensible...

Now, suppose we pass the qubit through a Hadamard gate before making the measurement. The diagram below shows this new process:

The output of the H gate prior to measurement is ψ = α0 + β1, where α = β = 1/√2; so we have |α|² = |β|² = ½. In other words, the measurement is equally likely to deliver either 0 or 1; the probability of each is 50%. But regardless of which outcome is observed, the state of the qubit after the measurement is just that observed basis state; the original superposition of equal quantities 0 and 1 has been obliterated by the measurement operation.

Review

More than one reader still finds too much unfamiliar notation in my little introductory series, so here's a quick redux of the story so far, without all the matrices and Greek letters...

Qubits without Greek

A single qubit can be represented as an ordered pair of numbers (a, b), where |a|² + |b|² = 1. In this scheme, the pair (1, 0) represents the classical logical 0, while (0, 1) represents classical 1:

(1, 0) = 0
(0, 1) = 1

Similarly, an entangled pair of qubits can be represented as an ordered sequence (a, b, c, d), where |a|² + |b|² + |c|² + |d|² = 1, and the four particular values (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0) and (0, 0, 0, 1) stand respectively for the classical states 00, 01, 10 and 11:

(1, 0, 0, 0) = 00
(0, 1, 0, 0) = 01
(0, 0, 1, 0) = 10
(0, 0, 0, 1) = 11

An entangled triplet is represented as a sequence of eight amplitudes (a, b, c, d, e, f, g, h), where |a|² + |b|² + |c|² + |d|² + |e|² + |f|² + |g|² + |h|² = 1, and the following correspondence holds between basis and classical states:

(1, 0, 0, 0, 0, 0, 0, 0) = 000
(0, 1, 0, 0, 0, 0, 0, 0) = 001
(0, 0, 1, 0, 0, 0, 0, 0) = 010
(0, 0, 0, 1, 0, 0, 0, 0) = 011
(0, 0, 0, 0, 1, 0, 0, 0) = 100
(0, 0, 0, 0, 0, 1, 0, 0) = 101
(0, 0, 0, 0, 0, 0, 1, 0) = 110
(0, 0, 0, 0, 0, 0, 0, 1) = 111

When our quantum computers are big enough to contain n entangled qubits, there will be 2ⁿ coefficients or "amplitudes" a, b, c, ..., and still the sum of all their squares will be 1.

Quantum Gates without Matrices

Like classical logic gates, quantum gates are defined by the operation they perform upon their inputs. In the case of a single qubit gate, we could say the input state (a, b) results in the output (a', b'):

(a, b) → (a', b'),

where of course |a'|² + |b'|² = 1. The single-qubit gates we looked at in part 1 were: firstly the quantum wire I, which transmits the input qubit unaltered:

(a, b) → (a, b)

secondly the quantum inverter or NOT gate X, which swaps the two amplitudes of its single-qubit input, and so in particular, converts classical 0 to 1 and vice-versa:

(a, b) → (b. a)

(1, 0) → (0, 1) = 0 → 1
(0, 1) → (1, 0) = 1 → 0

and lastly, for a bit of quantum exclusivity, the Hadamard gate H, which can combine pure basis states:

(a, b) → ((a+b)/√2, (a-b)/√2)

You might find this last operation written without the √2 scale factors, particularly in multi-step quantum computations, when it is common to roll up such adjustments into a single normalization following the final step of the calculation:

(a, b) → (a+b, a-b)

The only multiple-qubit gate we've seen so far is the controlled-NOT or cNOT gate, which swaps the last two amplitudes of its entangled input qubit pair:

(a, b, c, d) → (a, b, d, c)

By explicitly tracing through the details of the four transitions, we found that this twist corresponded to an inversion of the second qubit, if and only if the first qubit was 1:

(1, 0, 0, 0) → (1, 0, 0, 0) = 00 → 00;
(0, 1, 0, 0) → (0, 1, 0, 0) = 01 → 01;
(0, 0, 1, 0) → (0, 0, 0, 1) = 10 → 11;
(0, 0, 0, 1) → (0, 0, 1, 0) = 11 → 10.

Measurement

Finally, in the first half of this article, we have just covered the question of getting results out of the qubit complex. When you perform a measurement in the computational basis, the single qubit (a, b) will deliver a result of either (1, 0) = 0, with probability |a|², or else (0, 1) = 1, with probability |b|². The qubit will also adopt that measured state, from the point of the measurement onwards; having collapsed into probabilities, there now remains no trace of the original state amplitudes (a, b).

To take a numerical example, the (unknowable) initial state of the qubit might be (a, b) = (+0.8, -0.6). Now suppose a measurement is performed on this qubit. The outcome will be either 0, with a probability of |a|² = 0.8² = 64%, or else 1, with a probability of |b|² = 0.6² = 36%. Notice that the two outcomes have probabilities adding up to 100%, and that between them, they exhaust all the possibilities.

A similar measurement upon a qubit pair in the state (a, b, c, d) will yield a result of (1, 0, 0, 0), i.e. 00, with probability |a|²; alternatively, a result of (0, 1, 0, 0) = 01, with probability |b|²; and so on.

Next time: Superdense Coding.

China Commands And Controls

2011-10-27T16:33:00.005+01:00

Over 90% of C&C Centres in Beijing

Last March security firm RSA revealed one of the most spectacular data breaches in history. Not because of the methods used, which were a combo of a Trojan and some fairly elementary social engineering (though perhaps understandably, RSA felt it necessary to characterise the breach as an extremely sophisticated cyber attack). Neither because of the quantity of data compromised in that one attack. But because of the sensitivity of the data, which compromised in turn the SecurID two-factor authentication products, and hence the crown jewels, of many other corporations and organisations.

Back then, security experts claimed that "dozens of other multinational companies" were simultaneously infiltrated in much the same way. In fact the truth now emerges to have been closer to 760 or more organizations, including almost 20% of Fortune 100 companies, who had their networks hit by the same resources as were used against RSA, in a series of attacks which actually began last November. Brian Krebs has the full list here.

But even more startling is the following chart, which shows the geographic distribution of the command and control networks used to coordinate these attacks:

299 of the 329 Command & Control centres are in or around Beijing.

Avira Attacks Self

2011-10-27T13:18:00.005+01:00

It's like CA eTrust all over again

Always a bit of a guilty laugh whenever this happens to some poor unsuspecting antivirus vendor. After Wednesday's signature update, Avira's freebie anti-virus offering started marking certain components of its own code as "potentially malign".

Stefan Berka of Avira Operations broke the news thusly on their own support forum: Hello, We have had an false positive for the Avira file AESCRIPT.DLL which was detected as "TR/Spy.463227". Their statistics show around 4,000 false positive samples received on Oct 26, before the fixed Virus Definition File was deployed.

False positives in application files or Windows components are actually quite common, particularly in free offerings like this one, but the last time such an "auto-immune" false detection is known to have occurred was over two years ago, when the CA eTrust antivirus went completely mad, renaming and quarantining parts of itself, together with various bits of MS Visual Studio, Incredibuild, and others. Users at that time were advised to block the update, as well as to consider temporarily disabling on-access scanning. And that was only one month after its previous attack on them pesky Windows system files.

Quantum Computing #2: Multiple Qubit Gates

2011-10-23T22:50:00.011+01:00

Previously:

Introduction
Single Qubit Gates.

Entanglement

Last time we saw that a single qubit can be in either basis state, 0 or 1, or any normalized superposition of the two:

ψ = α0 + β1, where |α|² + |β|² = 1.

When we come to analyse systems of two or more qubits, it's important to realise that we don't just replicate the above, once per additional qubit, as we would in classical logic. This is because qubit states can be entangled. They have to be treated as a whole: as the overall state of the qubit set. Therefore, to take the next simplest example, a two-qubit system can be in any of the four basis states, 00, 01, 10 or 11, as well as any normalized superposition of these four:

ψ = α00 + β01 + γ10 + δ11, where |α|² + |β|² + |γ|² + |δ|² = 1.

As before, we can introduce an arbitrary set of orthogonal column vectors to represent each of these four basis states,

which gives us this representation of the multi-qubit state as a column vector:

and in general, an n-qubit system will have 2ⁿ pairwise independent (orthogonal) states in its computational basis, and hence 2ⁿ components in its state column vector.

The Controlled-NOT Gate

Recall what single-qubit gates such as X and H looked like: 2x2 unitary matrices operating on unit state column vectors. Similarly, n-qubit gates are represented by unitary 2ⁿx2ⁿ matrices. Our next example is termed the Controlled-NOT gate, or cNOT (feel free to invent your own pronunciation). This has two inputs and two outputs. The first input is passed through unchanged to the corresponding output. When this first input is 0, the second input is also passed through unchanged to its corresponding output. But when the first input is 1, the second input gets inverted as through an X gate. Here is the matrix representation of cNOT, and its operation upon a general 2-qubit state column vector:

To see exactly how this matrix represents a cNOT operation on two qubits, we consider its effect upon each of the four basis states in turn:

By checking each of these four cases in turn, we can confirm that the gate operates as advertised in the description above. Finally for the sake of completeness, and courtesy of Wikipedia, here is the circuit diagram symbol of a cNOT gate. The top quantum wire represents the "control" qubit, which is transmitted unaltered, while the bottom path represents the "controlled", i.e. conditionally inverted, qubit.

Miscellany

That's the meat of the present article in the series. I'll finish with a couple of general remarks on what we've seen so far.

There's actually an entire family of controlled gates similar to cNOT, differing only in the particular single-qubit operation that's applied to the controlled qubit when the control is 1. Their matrices are easily obtained by substituting the single-qubit operation's 2x2 sub matrix in the bottom right quadrant of cNOT.

All quantum gates have square matrix representations, since they all have the same number of outputs as inputs. That's because quantum computations have to be reversible. It's easy to show that gates like the classical AND, OR etc. can't be made reversible, as there's less information in their output (one bit) than in their inputs (two or more bits). This also implies that those classical gates necessarily dissipate energy during their operation.

Next time: Measurement; also, a Review of the story so far, devoid of matrices & Greek letters!

Electro '08

2011-10-21T14:17:00.029+01:00

Top 5 Electro of 2008?

This week French shoegazy dreampop act M83 released their sixth album, the two disc Hurry Up We're Dreaming, prompting the impeccable Dan Cairns (Sunday Times) to compare it to their previous, Saturdays=Youth, "the twin peak - with Cut Copy's In Ghost Colours - of 2008 electro". The comparison seems to be made a little unfavourably, though exactly how much so would have been easier to gauge had not the ST sadly, recently, discontinued its out-of-five star ratings.

Fussy genre definitions thus loosened, the comparison elicits the above question. Chiefly because Dan is always right. He has technical and theoretical musical knowledge, setting him apart from most so-called music critics. He knows, and will show you on a stave, exactly why the songwriting of Charlotte Hatherley must be cherished. Two weeks ago, he declared Lana Del Rey's Video Games the song of the year, with disregard to the currents of hype and other irrelevancies engulfing that artist. Declared it as scientific fact; Dan does not equivocate, nor trade mere opinion.

So yeah, he's right too about the eminence of both acts in the twin peak quote. But which of their songs are the true, 80s-retro royalty of 2008? And what other acts and tracks deserve inclusion beside these?

I'll start...

Oddly enough, M83 were not named after the south/east section of Glasgow's M8 junction 25, between the Clyde Tunnel Expressway and the South-Link Motorway. In fact no UK road has ever received that designation, which only ever appeared on that one Corporation / Fairclough gantry and local route sign drawing. So they chose instead to be named after the Southern Pinwheel Galaxy, a barred spiral in Hydra.

They released a prolific four singles in 2008, all from the haunting Saturdays=Youth. The second of the four, Graveyard Girl, is naturally the most haunted - even without its haunty spoken section:

I'm 15 years old
and I feel it's already too late to live
don't you?

Now let's get the second half of the twin peak quickly out of the way: Cut Copy. Nobody, not even Jeff Lynne himself, ever channeled ELO better than the Aussies' So Haunted. However, my vote goes to track one, for the Melbourne electro outfit's funky 80s retrocapture tech, first displayed here at 1:17:

The production work lavished on MGMT's fairly ordinary ditties by Mercury Rev / Flaming Lips producer Dave Friddman elevated Oracular Spectacular to electro royalty, and 2008 saw a total of four singles released from it, from Time To Pretend through Kids. I won't pretend to choose between those two.

Ladytron continued to innovate with their fourth album Velocifero in 2008, and particularly with a change of direction in their first single Ghosts. This might have given them their worst UK chart performance of the millennium to date, but the more typically daytronic Runaway laughingly made up for that with a breakthrough at #30 in the US dance chart:

Finally a confession: this isn't actually my top 5 electro from 2008. A well-thumbed TSM Radio review from May 2008 fondly recalls Epic New Song by the now tragically defunct Futuristic Retro Champions. Now, I honestly don't know whether this is my favourite FRC, since I once tried in vain to grade them all for a playlist, ending up with a total of twelve songs scoring 10/10. So my sixth and final, thank you, goodnight and safe home selection, is a sampling (the full collection Love And Lemonade is available at iTunes) of the most emotronic happy hardcore ever committed to disc ... in or around 2008.

Epic New Song - Futuristic Retro Champions by everythingflows

Jenna - Futuristic Retro Champions by everythingflows

Told Ya - Futuristic Retro Champions by everythingflows

Your mileage may vary. Hey, I'm no Dan Cairns.

Image credits: M83 road sign, Messier 83, all via Wikipedia.

Quantum Computing #1: Single Qubit Gates

2011-10-16T09:51:00.012+01:00

Previously:

Introduction

Mathematics? What Mathematics?

Recent mention of Mike Nielsen's Quantum Computation videos sparked a flurry of interest among friends and colleagues, mostly tempered by wariness about the mathematics involved. That's a pity, because there's actually very little mathematics needed to make a start on this stuff. Complex numbers, for example, are not strictly essential for an introduction to the subject. And even when they become so, well after all, they are just pairs of normal numbers, with a special rule for multiplication. Similarly, matrices are nothing more than a shorthand way of multiplying ordinary numbers pairwise, two by two, and then adding up the results.

Still it can be a sub-optimal experience to jump into Wikipedia's Quantum gate page, finding yourself immediately surrounded by not only these, but also the curious ket notation. Well, let's at least see if we can get started without that!

This is the first in a series of articles on quantum computation, to be published over the next several Sundays, loosely following the content of Prof. Nielsen's videos. It describes, in a thoroughly simplified style, a couple of single-qubit gates. Future articles will apply the same stripped-down approach to multiple qubit gates, and then measurement, and in surprisingly short order, superdense coding and quantum teleportation.

Another unusual aspect of these articles, also owed to Prof. Nielsen, is the complete lack of any reference to physical implementations of quantum gates and circuits. This is just how classical Boolean logic (or the propositional calculus) developed historically, many years before physical AND gates were realised in switches, valves, water sluices, dominoes or marbles. We simply describe a two-value quantum computational algebra, taking it on trust that there's no shortage of potentially available physical realisations.

The Computational Basis

Like a classical, logical bit, the quantum bit or qubit has two computational basis states; 0 and 1. Some writers use instead ↑ and ↓ to represent the basis states. Personally I'd have preferred to use something like T and F, but hey. Whatever symbols are used, they're usually embedded in the forementioned ket marks, like these:

but for purely typographical reasons I'll be omitting those, at least to start with, and using instead just the bold 0 and 1.

For the purposes of the matrix transformations which follow, the basis states can conveniently be represented by any two orthogonal unit column vectors. Note that the unfortunately named 0 is not the zero vector; 0 is just a label for the ordinary, basis state vector we've chosen to represent "logical zero". For example, the labels 0 and 1 might represent unit steps in some arbitrary x- and y-directions, respectively:

The qubit's actual state ψ can also be any linear combination (or superposition) of these basis states,

where |α|² + |β|² = 1.

Quantum Gates

Quantum computing has its own "gates", by analogy with the classical AND, OR, NOT etc. These can be represented by square matrices. For example, a single-qubit gate might be represented by a 2x2 unitary matrix M.

Wait, what? Unitary? - Well, a gate matrix multiplying any given quantum state column vector yields a new state, and this new state must also satisfy the above normalization condition, |α|² + |β|² = 1. Unitary matrices are just those which preserve this criterion. In other words, they preserve the unit length of the state vector ψ.

The simplest quantum gate is the single-qubit "wire", which - pay careful attention now - looks like this:

and just transmits the state vector unaltered. The matrix representation of this is the 2x2 Identity matrix, I.

The NOT Gate

For historical reasons, the quantum NOT gate is also known as the Pauli-X gate, and appears in both circuit diagrams and matrix representations as the letter X. Here's its symbol for use in quantum circuits:

This gate "inverts" its input, in the sense that given an input of 0, its output will be 1; and conversely, given an input of 1, its output will be 0. As for those peculiar superposition states, it seems reasonable that an arbitrary input state ψ containing a certain quantity α of the 0 basis vector, together with a corresponding quantity β of the 1 basis vector, should upon passing through a NOT gate, have those quantities reversed. And that's just what this X does:

Like the classical logical inverter, the quantum X gate is its own inverse. In terms of linear algebra it's trivial to show, by explicit matrix multiplication, that XX = I:

The quantum circuit diagram below is therefore equivalent to a single wire.

The Hadamard Gate

Our first truly quantum gate, without a classical analogue, is the Hadamard gate H. Given an input of 0, its output is the sum of the 0 and 1 basis states (normalized, of course). Similarly, given an input of 1, its output is the normalized difference between the two basis states. It's like this:

The √2 is the normalization adjustment needed to give the output vector unit length. "Noise" like this is often omitted from practical quantum computations, it being universally acknowledged that the state vector always requires such normalization; but I'll retain it, to avoid confusion.

The Hadamard gate is also its own inverse. In terms of linear algebra it's trivial to show, by explicit matrix multiplication, that HH = I:

and hence that the series circuit of two Hadamard gates, just like the case of two inverters, is also equivalent to a single quantum wire.

Next time: Multiple Qubit Gates.

The Dangerous Mod

2011-10-15T07:56:00.005+01:00

Popup Worry

Kaspersky continues to perform as one of the best available Internet security packages, and although everyone is only ever one slip away from a major breach and a catastrophic loss of reputation, I would not hesitate to recommend it. Maybe that's why I've given this little popup notification a bit more attention than it warrants at first sight.

A look in the usual forum or three reveals that people have indeed found messages like this one quite confusing. For one thing, they are unforgivably ambiguous. Is it the application, or the modification, that is being flagged as "potentially dangerous"? And quite separately, which one is it that has no digital signature - the original app, or the process (installer) trying to update it?

Then there's the question of relevancy when it comes to "98% of users trust this application". Do they trust the modified or unmodified version? And why exactly do they trust it? You don't have to be particularly security savvy to know: the mere fact that "more than a million" users have run a program, doesn't prove it's not malware. Aren't those users being a little bit cavalier, at this time of apparently ubiquitous fake certificates?

Of course, clicking "Help" does nothing to improve matters, unless you count as progress, advice on how to prevent these pesky warnings from appearing at all. The so-called "Help" link just takes you to a description of popup warning management options within the security app itself, completely oblivious to the context of your present dilemma!

Finally, I have to grumble about the available options. None of these is entirely satisfactory. Yes, I trust - as we have just been told - obviously risks running a "potentially dangerous modification of the application". Yet how is a typical user supposed to evaluate the Restrict option? Why on earth would you ever consider allowing "dangerous operations" in the first place?

As for the seemingly safe Block option: nothing terrifies me more than the prospect of trying to update my wife's iPad2 to iOS5, as I am destined soon to do, then being blocked halfway through an elaborate backup / restore operation because the necessary instructions are stuck in a blocked QuickTime Task. Where is the "Ask me later, when it actually tries to do something" option? Remember, almost everyone now has this kind of update configured to run automatically in the background. I probably won't want to have to deal with this warning as soon as it pops up. Yet it cannot be dismissed without making an apparently irrevocable decision about the fate of a potentially critical app.

Nor can it be ignored; it's a stay-on-top window.

Calm Down, Dear

Now, it goes without saying (to security experts like you and me :-) that the correct option is to click the inconspicuous little information icon beside the application name, and verify as many details as possible, sans signature. In this case, the app name, path, vendor, product version and create / modified dates check out, while I can see that it's the original app that had no sig. Hey, it's been running that way since July! Only now is the warning disambiguated: it's about the modification of an unsigned file.

Here, both the original file and the agency performing the modification are trusted. So I choose Yes, I trust and get on my way.

This rant is all about UI design and user guidance. Kaspersky, you might be as I contend, the best in the personal computing security business; but you sometimes make the mistake of assuming you're communicating with colleagues. Often instead, you need to explain as you would a child.

Quantum Computing for the Determined

2011-10-08T10:10:00.013+01:00

Moving Pictures

Nobody seems willing to predict when quantum computing will take off. Some are even beginning to question whether it will ever do so. Meanwhile, optimists patiently await that crucial breakthrough, the discovery of the perfect physical realisation of the qubit. There's no shortage of candidates. The Nitrogen Vacancy (NV) centre in diamond is one. NVs are the crystal lattice imperfections in pink diamonds that give them their hue. Then again, a lot of progress has recently been made involving trapped ion systems.

The optimists wait - impatiently, on second thoughts! - for one of these, or for some other exotic virtual particle inhabiting some material (or as yet unknown metamaterial), that will finally and abruptly realise the qubit as coherent, entangled and scalable.

As they wait, they polish their grasp of linear algebra, matrices, the various fundamental and second-order quantum "gates" that have been conceived, and the circuits made possible by these. Rehearse the limitations imposed by their fragility and inscrutability. Marvel at the astonishing algorithms that have been developed in qubit theory, while worrying about their scant number and opaque discoverability.

Almost to a man or woman, they have found and honed their new algebraic skills using The Book: Quantum Computation and Quantum Information, by Michael A. Nielsen (University of Queensland) and Isaac L. Chuang (IBM / Stanford University). Or Mike and Ike, as this revered tome is universally known. A literally pioneering work, it was the first of its kind, and is still today the standard to which all else is inevitably compared (my earlier review is here). In fact it's the most highly quoted physics publication of the last 25 years, and one of the ten most highly quoted physics books of all time (source: Google Scholar, December 2007).

In support of its tenth anniversary edition, Professor Nielsen has released a set of 22 short video lectures on his blog. They're a great introduction to the subject. However, he has stopped just short of completing the course, due to intervening work commitments. He has promised to complete it if there's enough interest in the videos produced so far. Here's the first one:

You know what you must do!

Next time: Single Qubit Gates.

Public Key Cryptography

2011-09-28T00:30:00.011+01:00

Brave New Cipher

As an avid reader of Scientific American in the 1970s, and of Martin Gardner's Mathematical Games column in particular, I was lucky enough to be schooled in the basics of public key cryptography just as it was being invented. Well, two years after its 1975 inception, to be accurate. Firstly through Martin's column, which in the August 1977 issue became the first to publicize the PKC method worldwide; and then in the same journal, subsequently from the writings of Rivest, Shamir and Adleman (RSA) themselves.

It was an exciting time for anyone of a mathematically sympathetic imagination. For the first time in history, the question of the practicability of devising a cipher, to be encoded and decoded rapidly by computer, used repeatedly without changing the key, and unbreakable by sophisticated cryptanalysis, received an answer and a proof; and the answer was affirmative.

Martin's original article can be read here:

http://www.fortunecity.com/emachines/e11/86/cipher1.html

The number theory behind the scheme is simple and elegant, as we hope from such things. But that very beauty of theory and expression can distract the student from the equally important subject of housekeeping.

Secure Public Keys

This is the main message in Eric Lippert's recent article, Keep it secret, keep it safe. As an example, most of us will be aware that Alice and Bob each have one private and one public key, based upon a certain mathematical "trapdoor function", namely prime factorisation. Each party must ensure that his or her private key remains known only to him or herself. What's perhaps less obvious is that their initial exchange of public keys must also be made via a guaranteed secure channel.

Why? Surely the strength of the scheme rests on the fact that eavesdropper Eve can do nothing with full knowledge of these keys? True enough, but Eve is not the only shadowy figure in the telephone exchange room.

Historical note: in cryptography discussions such as these, the cast of characters (Alice, Bob, Eve, etc.) is mostly drawn from Bruce Schneier's seminal book, Applied Cryptography.

Eric uses Mallory to denote this malicious, meddlesome, man-in-the-middle, although Trudy (for intruder) is possibly more common. If Mallory can intercept the initial exchange of public key information, then he may modify these keys in transit, replacing them with his own public key.

Any message from Alice will be encrypted using her private key, and Bob's public key. But now Mallory can intercept such messages, and replace them with alternatives containing his own subversive propaganda, encrypted using his own private key, and Bob's public key. Bob will then in turn decrypt the bogus message using his own private key and Mallory's public key, which he still believes to be Alice's; and so all will appear to be well. Oops!

An Opportune Time

This is a particularly urgent time to be reminding ourselves of the basic mechanics of the system. We have recently seen Certifying Authorities become compromised, appearing to issue shedloads of bogus certificates, and even go bust (DigiNotar). Ironically, RSA itself has become the victim of one of the most wide-ranging breaches in the history of the industry, its SecurID token system and thereby the security of its targeted (Lockheed Martin) and collateral clients being utterly compromised. Meanwhile, the SSL itself, in its most common implementation (TLS 1.0/SSL 3.0), has been hacked by a cookie thieving BEAST.

It's only by understanding the detailed operation of PKC that we'll be able to discern the implications of breaches and failures such as these. But the important details are not in the pretty mathematics, they're higher up in the wider system, where the real, exploitable vulnerabilities reside. They're in the arena of public/private key housekeeping. As Eric puts it, solve the key management problem first!

Related articles:

Authencity of Web pages comes under attack
Hackers impersonating 'trusted' Web pages
Secure online payment system requires end-to-end encryption

Pic: Adi Shamir, 2009. Source: Wikipedia.

Risk Shift

2011-09-26T13:55:00.005+01:00

The Trouble With Politics?

In the LA Times just over a week ago, there was an interesting report about a recent study of teenage drivers:

http://www.latimes.com/health/la-he-teen-driver-laws-20110914,0,7056006.story

Basically, the situation in all the states (California being no more than a particular case in point) has been, for over a decade, that the newest drivers, which is to say 16-17 year olds, have been subjected to various restrictions on their ability to (a) carry passengers, and (b) drive at all during certain times of day. There have also been other restrictions adopted by certain states, such as driving without supervision, or the ability to use mobile phones while driving, but these two have been the main and most popular ones in every state since the first of these so-called "graduated driver licensing programs" was originally introduced in Florida in 1996.

What the study has revealed is that the anticipated - and indeed observed - reduction in fatal accidents involving 16-17 year old drivers, has been "almost exactly matched" by a corresponding increase in fatalities involving 18-19 year olds. In other words, the carnage has merely been pushed two years into the future.

(According to my reading of the evidence, the increase is actually closer to half the earlier reduction, but we'll let that go for now.)

Hot Potato

It's obvious with hindsight, that what these programs have done is to mask the immaturity and inexperience of new drivers for a year or two. By preventing them from being exposed to certain driving situations and environments, the restrictions have of course done nothing to prepare them for such eventual exposure.

Politically, this has become a very awkward truth. During the first couple of years of every such program, public officials have been able to point to a real reduction in young driver related fatalities, and boast with confidence that their policies have been saving lives. Now that it turns out in general not to have been the case, what are the chances that these programs will be cancelled overnight?

Absolute zero, obviously. But for more than just the usual reasons, i.e. short elected terms, and blissful ignorance of the actual evidence. This will not become just another case of badly thought out laws surviving through inertia. For if these programs were discontinued, there would be a bow wave of doubled fatalities lasting for as long as the initial reduction, namely two years, as today's pre-existing 18-19 year olds meet the newly liberated 16-17 year old wave of fresh idiots.

Obviously there's a lot that can be done, in terms of education and training, to defuse these unintended consequences and arrive at a program that does make sense. Still, it's an interesting study, and a good reminder of how shortsighted, wilfully or otherwise, we and our politicians can be.

It Will Be A Good Day

2011-09-24T11:00:00.008+01:00

Six For Saturday

▲ What you get when you play Charlotte Hatherley's White video backwards.

▲ They're all good days.

▲ 2005 electro with a dark tone, superbly conveyed by Helen Marnie's understated delivery.

▲ Flautist Kate Holmes (no, not that one) is also "Client A" in CLIEИT, where Charlotte Hatherley once appeared as "Client C" (and when you read that Charlotte has two elder sisters, Abigail and Beatrice, a heartbreaking little narrative springs to mind).

▲ Bars of seven measures from Poland's greatest export! Love the funky piano @ 3:50.
Yes I know there aren't "measures" in a musical "bar". It's a pub gag.

▲ One of my favourite pop songs - Carla J Easton (Futuristic Retro Champions). Nuff said.

Algebra

2011-09-09T09:14:00.009+01:00

Don't you just hate those Microsoft developers?*

You've just started replacing that fusty old, string-based SQL Builder with a modern, class-based model, featuring fully composable queries, query clauses, and expressions, all the way down to basic arithmetic. Suddenly, they bring out LINQ.

Some time later, recognising the monadic algebra behind the new pattern-based query comprehension keywords, you decide to harness it to implement the continuation monad, which will allow you to write asynchronous code in a purely synchronous paradigm. Suddenly, they announce async/await.

No matter how good, how revolutionary your design, the fact remains that you just can't beat a good keyword. There's simply no better or more powerful implementation, nothing tidier than a well conceived and designed primary language feature. This observation highlights the need to know thoroughly, completely and perfectly, the nature of the feature under implementation.

Unless your main business is writing compilers, your greatest enemy is the client specification, perhaps represented by the design engineer, stating non-goals like there is no requirement to compare or subtract two fields. Because you know that there will be. And when that requirement is finally unearthed, you will already have been forced down the Agile pipe, and have implemented a horribly hobbled subset of the operations that would have been required to express properly a well-formed algebra - of queries, or asynchronous tasks, or whatever.

The sad truth is that many of us lack the basic mathematical skills to appreciate the seachange wrought on your design by a proper, complete, closed and proven algebra. And while the scope for such effort and expenditure by application developers continues to shrink, and a good job too, with the increasing power and usability of production compilers and other tools; still it is imperative to be ready to identify such situations when they do occur, and to be prepared to design the solution along veins of sound, algebraic principles.

Vindication

Eric Lippert's latest blog article is a beautiful exercise in such pure, abstract, algebraic thinking, and brilliantly displays its payoff. He asks, what in C# is a type? The naive answers most of us would propose, these have all by now been discounted with the aid of counterexamples, in the predecessor article. A type is not a name with a set of values. Neither can it be defined as a set of assignment rules. Still less is a type some kind of predicate for determining which among an infinite set of values belong to it. Eric demonstrates the strictly formal application of mathematical logic at work in his conception, when he actually makes essential use of Russell's Paradox in proving the inadequacy of these attempts!

A type, in the mind of compiler writer Eric, is nothing more than an abstract mathematical entity obeying certain algebraic rules. He follows this definition with a good analogy based on Giuseppe Peano's axiomatic definition of natural number. Turning back to his equally axiomatic type definition, he then shows how its axioms can be used to construct compile-time proofs of runtime type safety (ignoring temporarily wrinkles like the cast operator, or unsafe array covariance).

But perhaps the best illustration of the power of the abstract analytical approach is seen when he dips into Gödel's undecidability results, and identifies areas where such proofs cannot be constructed reliably. The lesson here is that still, the formal analysis rigorously controls the progress toward a compiler solution; this time accurately and unambiguously delineating the "holes in the road" where practical workarounds must be applied, or where - in measurably unrealistic, and perfectly predictable situations - a compiler failure can be tolerated.

Expression too complex to analyse.

Pic: Giuseppe Peano, from Wikipedia. Not actually a Microsoft dev.
*I just love those Microsoft developers!

Project Security Review #1

2011-09-08T11:00:00.011+01:00

Threat Modelling

Now we're really moving! It might only have been a 90 minute session last thing in the working day, but yesterday, we finally managed to convene our very first, "formal", Threat Modelling meeting.

Summary

Good representation - included people from across the spectra of projects, departments, job descriptions and levels - including director!
Refresher coverage of threat / vulnerability terminology and STRIDE classifications.
Brief look at the latest SDL Threat Modelling software - well, at least it installed and ran OK - but we reverted to a big whiteboard (thanks Colin!), and directed most of our efforts to:

A Game Of Cards

Yes, we finally got to take the wrapper off Adam Shostick's deck, and play a round of Elevation Of Privilege. Now when I say "a round" I really mean "one trick", as it took the best part of an hour to get just those seven cards played. That also meant that we really concentrated on just Tampering vulnerabilities for the whole session, since it's built into the rules of the game that you must start with that suit.

And that was one of the main lessons learned from this exercise. The card game exists only to facilitate and drive forward the brainstorming exercise. It dislodges little hints of system vulnerabilities, encouraging their discussion in a welcoming, improv-style, "Yes, and..." atmosphere. Anything that impedes this process needs to be removed, even when that involves abandoning or changing certain rules of the game.

Now I just have to get that Data Flow Diagram tidied up and entered into the Threat Modelling tool, in time for the imminent follow-up...

Hannes Bok

2011-09-04T07:53:00.005+01:00

The Futurian Artist in Chief

Inveterate name dropper Fred Pohl's first hand reminiscences on the early history of SF, memories from the elder half of the previous century, continue to amaze me with their depth and clarity. Meanwhile his blog sparkles too with pithy one-liners and snarky, short form, political comment. ♥

This weekend's treat: part one of a biographical sketch of Hannes Bok (real name Wayne Woodard), the only member of the pro-crashed fan club Futurians of New York ever to win a Hugo for illustrative drawing and painting. The story covers his fortuitous early association with one aspiring writer named Ray Bradbury, and the role played by the first ever World Science Fiction Convention (WorldCon).

Update (Sep 7):

Hunter Two

2011-08-26T10:46:00.005+01:00

Via bash.org

I telephoned the 90s, and overheard this chat on IRC:

[Cthon98] hey, if you type in your password, it will show as stars
[Cthon98] ********* see!
[AzureDiamond] hunter2
[AzureDiamond] doesn't look like stars to me
[Cthon98] [AzureDiamond] *******
[Cthon98] that's what I see
[AzureDiamond] oh, really?
[Cthon98] Absolutely
[AzureDiamond] you can go hunter2 my hunter2-ing hunter2
[AzureDiamond] haha, does that look funny to you?
[Cthon98] lol, yes. See, when YOU type hunter2, it shows to us as *******
[AzureDiamond] that's neat, I didnt know IRC did that
[Cthon98] yep, no matter how many times you type hunter2, it will show to us as *******
[AzureDiamond] awesome!

(pause)

[AzureDiamond] wait, how do you know my password?

(pause)

[Cthon98] I just copy pasted YOUR ******'s and it appears to YOU as hunter2 cause it's your password
[AzureDiamond] oh, ok.

SDL Tools TFS 2010 Update

2011-08-26T09:50:00.010+01:00

Better, Late

Team Foundation Server 2010 takes credit for most of the just-released updates to Microsoft's SDL toolset:

Threat Modeling Tool v3.1.8

The main pre-coding system security analysis tool has been updated with a number of bug fixes, improving the stability of the product's Visio 2010 and TFS 2010 support. 6MB msi.

MiniFuzz Tool v1.5.5

This SDL verification phase helper has also benefited from several stability-related bug fixes, and improved control of target application shutdown. It too has had TFS 2010 support added. 2MB msi.

RegExFuzz Tool v1.1.0

H Beam Piper and John Scalzi's retro SF aside, this is my favourite little fuzzy. It allows checking against a specific class of DoS attack, via regular expression patterns with exponential evaluation times. The update again contains a number of bug fixes based on version 1 feedback. 2MB msi. Unfortunately there are still a couple of unresolved known issues, albeit fairly minor ones. From the supplied documentation (ReadMe.rtf):

The tool does not handle nested anchors in a regular expression. A regular expression can be assumed to start with ‘^’ and ended with ‘$’. If these tags or their variants are included in a target regular expression, the tool will throw an unhandled exception. The work-around is to break up the nested regular expression and test the resulting regular expressions individually.

The tool requires that hexadecimal (‘\x’ prefix) characters within the regular expression be 2 characters. Those with a 0-padding assumed single character description will cause the tool to throw an unhandled exception. The work-around is to make all hexadecimal character descriptions two characters ‘\xCC’.

FOADIACFWLS

2011-08-23T15:18:00.009+01:00

Turning the Heat on the Cold Callers

Got another phone call yesterday from a lady in India, number withheld, asking if I had a Windows PC. None of your business, I informed her. It may be none of my business, but we are having a lot of trouble with the infections on your computer! she offered.

I thought about stringing her along, as I usually do; but I was busy. I had work to do. And I'm getting a bit tired of these organised criminal gangs of cold calling bastards, ripping off innocent and vulnerable users for hundreds of pounds with their fake antivirus scams. So on something of an impulse, I suggested: Fuck off and die in a car fire with leather seats!

Her immediate response was: You fuck off, you son of a bitch. [click] [bzzz]

Now I'm going to take a wild guess, that a genuine technical support organisation would have had a much higher level of professionalism than that. Maybe next time I'll go with I can tell you I don't have money. But what I do have are a very particular set of skills...

Oh! and also, wouldn't it be great, using a combo of tech, psych, and you know, Jeff Goldblum, to be able to upload a virus to them?

Cheap Chips and Network Security

2011-08-21T15:22:00.005+01:00

(Via Charlie Stross)

In 1980 two eminent computer scientists were discussing trends in microprocessor production. One objected to the other's claim, "But there's no market for such cheap chips! What are you going to do, embed them in door handles?"

Five years later, checking into a hotel, he suddenly realized he was using a magstripe card to open his room door. There was a microprocessor in the door handle.

This piece is an extension to Charlie's brilliant, speculative USENIX 2011 Keynote: Network Security in the Medium Term, 2061-2561 AD. Both articles are highly informative and entertaining, written by one of our greatest living Science Fiction novelists - who also happens to have penned the first published "mainstream" technical review of Linux (in 1994), among scores of similar articles during his tenure at Computer Shopper. And both are, of course, highly recommended reading.

Simple Regular Expressions #4

2011-08-11T12:23:00.028+01:00

That Old Saw

Another Regex question, another blog post! This time, Colleague A wants to highlight search terms by inserting some CSS spans into his HTML. It's the old problem of ignoring the content of tags during substitution. For example, suppose he highlights the search term school by applying the CSS class xred. This causes injection of spans like this into his output:

Alan went to class at <span class="xred">school</span> next day.

So far the rendering is as expected:

Alan went to class at school next day.

Trouble is, he next wants to highlight the search term class in xgreen:

Alan went to class at school next day.

Doing another simple replace operation would cause the new, "false positive" instances of the term class (occurring within the previously added HTML tags) to be incorrectly incorporated into new xgreen spans, resulting instead in invalid markup, and an onscreen train wreck.

Alan went to class at class="xred">school next day.

The following method of avoiding substitutions within tags is far from the best available solution, even among those offered by Regex. However, it does provide a conveniently simple example to let me introduce another Regex concept, namely Assertions.

Zero Width Assertions

In the context of regular expressions, an assertion is simply a statement about the context of the current match. The simplest examples are the "begins with", "ends with" and "exact match" assertions, which use the ^ and $ characters to match the beginning and end of the line, respectively. Suppose our input is 12345. Then the pattern 234 will match this successfully. The pattern ^234 will not, because the caret ^ constrains the matching to occur at the start of the input string, and ours does not start with 234 (the pattern ^123 will of course succeed). Similarly in the pattern 234$, the dollar $ constrains the matching to occur at the end of the input string, and so this will also fail to match our input, whereas 345$ will succeed. Finally, using both assertions, ^12345$ will match only the entire input string 12345, while any other sub-pattern such as ^1234$ fails.

These two meta characters are examples of atomic zero-width assertions, also known as anchors. Zero-width means that they do not cause the engine to advance through the string or consume characters; they just assert something about the current position in the input. There are several other anchors, but now I want to turn to more general assertions.

Assertion Types

Both of the above examples can be characterised as positive assertions, in that they require something to be true about the current position; namely that it is the start, or end, of the line. You could imagine another assertion type, where you want to match a particular sequence anywhere except either or both of those positions. And yes, such negative assertions are available, as we'll soon see.

Another characteristic of assertions is the direction they face. The caret ^ is termed a look-behind assertion; it states that no input exists before the current position. Similarly the dollar $ is termed look-ahead, as it states there's no further input available beyond the current position.

Finally, the new assertions I'm about to introduce, while still zero-width, are no longer atomic. Instead of referring to known fixed points, such as the beginning or end of the string, line, previous match, or word/non-word boundary, these new assertions contain their own independent subexpression patterns, which they assert do (or do not) occur immediately before (or after) the current position in the input. The parentheses here reflect the difference between positive and negative assertions, and between look-behind and look-ahead behaviour. So there have to be four types, right?

They all use syntax similar to grouping constructs. Positive assertions are indicated by =, negative by !. By default these are assumed to be look-ahead, unless prefixed by < to signify look-behind.

positive look-ahead: (?= subexpression)
negative look-ahead: (?! subexpression)
positive look-behind: (?<= subexpression) ◀ this is the one we are going to use
negative look-behind: (?<! subexpression)

Back To Highlighting

Refer to MSDN for examples of each of these. Now I just want to finish by showing how a zero-width positive look-behind assertion can be used to protect the content of those HTML tags.

How can we write a pattern to match search terms ignoring tag contents? If we're inside a tag, then there's a < somewhere to our left, as yet unmatched by a closing >, while if we're outside, then either there are no < on the left, or else every such < is matched by a corresponding > also on our left. In other words, we want everything on our left to consist of: start of line ^, followed by any number of (a) non-< characters, or else (b) < characters with eventual matching > characters:

^([^<]|<[^>]*>)*

Finally, wrap that as the subexpression in the third template above, and we're done:

(?<=^([^<]|<[^>]*>)*)

Code Sample

private static string Highlight(string input, string search, string cssClassName)

{

  const string assertion = "(?<=^([^<]|<[^>]*>)*)";

  var pattern = string.Format("{0}{1}", assertion, search);

  return Regex.Replace(

      input,

      pattern,

      match => string.Format("<span class=\"{0}\">{1}</span>", cssClassName, match.Value));

}



private static string Test()

{

  return Highlight(

      "<span class=\"ignorethisclass\">This</span> is the class.",

      "class",

      "highlight");

}



// Output: <span class="ignorethisclass">This</span> is the <span class="highlight">class</span>.

Disclaimer

Remember, this is only an illustrative example. As a practical HTML postprocessing solution, there's still a number of holes in it!

Ten Visitors

2011-08-02T20:16:00.006+01:00

Featuring: A Litter of Bichon Frise

Sounds like a wine order to me! "Waiter, if you would send to my table, a carafe of Pinot Noir. Yes, and a litter of Bichon Frise, thank you."

Half a dozen of the little Water Spaniel / Standard Poodle descendants, who came visiting last night. They brought their parents, Pepi and Popi. And they brought their owners, our friends Bojan and Theresa.

At no point did Linda consider, even for a second, keeping any of them - as you can clearly see from her picture:

No, not even the one she'd picked out and decided to name "Number Five":

If anything my own resolve was tougher still. No way did I want to keep one of these...

...never mind two...

...and least of all, erm, three...

All too soon, the pups had to be packed away again...

I do hope that they will all find excellent homes. But not before they've visited us again!

Yes: Fly From Here

2011-07-30T13:00:00.010+01:00

I'm in a minority, albeit far from unique within the Yes fan base, in being already aware of - in fact, for decades very familiar with - the musical sapling at the centre of this new Yes album. That was due to my extensive collection of live bootleg CDs of the band, at one point containing several thousand discs.

The Horn/Downes penned demo We Can Fly From Here was played at a total of 67 shows on the 1980 Drama tour of North America and Europe. I owned recordings of 32 of these performances.

Despite its live coverage, the song was never included on a studio album. Not even on the 2004 Rhino release of Drama, expanded though that was from 6 to 16 tracks, with the inclusion of much bonus material, some less worthy. Though it did have an official live release in 2005, on the Rhino live box set The Word Is Live, it wasn't until this most recent blinding roundabout of personnel changes, ending in the reunion of core Yes men Chris, Steve and Alan, with the song's original writers, that a studio release became a possibility. And actually, much more than that.

Old School Prog

To say that I disapproved of the replacement, in 1980, of angelic but abstract singer/lyricist Jon Anderson, and classically trained keyboard maestro Rick Wakeman, by those two Age Of Plastic Buggles Trevor Horn and Geoff Downes, would be completely to misapply the moderate and perfectly serviceable concept of disapproval. In fact, I suffered a complete breakdown of rationality, an implosion of incredulity, which sounded a little like this: What? The! Fuck?!

Looking back, I knew nothing about record production, and so missed the fact that a lot of the best and my favourite 80s pop - Propaganda, Frankie Goes To Hollywood (with Steve Howe on guitars!), Art Of Noise, Lisa Stansfield, Simple Minds - all was Trevor Horn produced.

Fly From Here

The main, 25 minute, 6 part epic (including the now obligatory Overture) is not at all bombastic, quite the opposite; for the most part it canters and trots a few simple themes which weave around themselves, or around light relief at one stage reminiscent of Zappa's Tink Walks Amok. All the same, and following in the tradition of their peerless Close To The Edge, which grew out of a single melodic idea by Steve Howe, it is unmistakably an old school Yes reworking of seed material, by way of thematic contributions from all band members, into a thing of epic scale.

It also shares a lot more than just structural outline and scale with its 1973 predecessor. Simplicity for one thing, in both its wondrously plain but beautiful musical motifs, and its simplistic lyrics. I get up, I get down has become a static descriptive thread about an abandoned airfield. Then too there's variety of texture, with its Madman at the Screens diversion, or the madly sauntering, Howe-penned Bumpy Ride. And it all ends, of course, with the equally obligatory Reprise.

This analysis of the title piece is borne out during the 18½ minute "Making Of" DVD, which came free with my copy. Everyone interviewed attests to the same narrative of frictionless collaboration and inclusiveness. Production god Trevor Horn tellingly emphasises, "I didn't want anything programmed," shaking and lowering his head as if discarding too heavy, unpleasant baggage; "I wanted it to sound more like the band sounded in the 70s, necessarily, than the band sounded in the 80s." Steve Howe cements the account: "It would be an illusion to say: Ah! This record sounds like the 70s. But the thing might be, there might be a concept in our new album, Fly From Here, that does carry a lot of that 70s... but it's not about copying the sound, it's really about just thinking in that way."

By turns anthemic, acoustic, inspirational, soft, rocking, and diverting, the album's centrepiece is an unconditional melodic, harmonic, rhythmic and organisational success. As for the remaining tracks...

The Man You Always Wanted Me To Be

A love song with melodic hooks and an irresistible message. Uncomplicated pop, flavoured with the soft rock sensibility of Downes' and Howe's Asia work.

Life on a Film Set

Another Buggles written reworking. Starts off slow and acoustic, then switched midstream to a fiesta dance, eleven to the bar. Nice cross-cutting solo guitar work from Steve. Yes!

Hour of Need

The Japanese release has an extended version of this song, a ballad written by Steve Howe. I'll withhold my verdict until I manage to get hold of that, as it's reputed to be a great improvement on this little three minute ditty.

Solitaire

This is my favourite Steve Howe solo work, out of the entire canon comprising his own solo releases and those acoustic spots with Yes. Many long time fellow Yes fans have already disagreed with me on this, but I hear the richest ever concatenation of varied guitar styles, the most accurate fretboard and pick fingering, and melodies mostly sweet, only occasionally and at the very end, minor and sinister.

Into the Storm

A strong finish, again featuring some great solo work by Steve, who appears to have gone all out for quality over number of notes this time.

Conclusion!

Fly From Here is a great little album with a clearly retro sensibility. One I felt inspired and obliged to write about at length. One that deserves a chance of commercial success, however unlikely that might be for almost any artist today, least of all a 40+ year old progressive rock outfit. The overall sound can be summed up by saying you can hear all the instruments, something unfashionable given recent fads for production munge*, compression and clipping. Also something at which the previous album, 2001's Magnification (Yes! From ten years ago!) spectacularly failed - at least if you ask Steve Howe.

Fittingly, the cover artwork is a superb Roger Dean original in something of a career-spanning amalgam of styles, started in 1970, and left unfinished until now.

*My own term. Fortuitously, I now discover its usage in computer security, specifically password creation, where it means Modify Until Not Guessed Easily. Well, that is precisely what I mean by munge in the context of musical production: modified until there's nought but a thick beige soup, whose ingredients can no longer even be guessed. Except maybe for mechanically recovered broiler chicken.

Happy Birthday (2) To Me

2011-07-29T12:00:00.002+01:00

Little Bloggie's 2nd Birthday

Cool, so I've been blogging here for two whole years! Time for another bit of metaspection.

Most of what I have to say about that is just to repeat last year's birthday message. The targets for the blog have remained the same: two posts per week, half the posts technical in nature, half nontechnical. Oh, and half the technical ones security related. Those targets continue to be met - the technical and security quotas comfortably, and the overall to within about 10%.

How successful has the endeavour been to date? Just as last year, the technical articles have continued to prove the less popular, and the security related ones, less so again. This echoes a typical Facebook experience, where comments on world affairs of any importance get ignored, while random posts about toasted cheese or mismatched shoes attract dozens of comments...

The blog's popularity, according to Google Analytics, has risen slowly but steadily to around 300 unique visitors per month. At this low level, comment spam remains almost nonexistent. I've only ever had to delete two comments in that category. Speaking of Google Analytics, can you see the point where my post about Sony's PS3 Linux crimes got linked at NeoGAF?

Our design, development and test departments have now had one Day O' Security presentation, or rather two identical half-presentations, that went quite well overall. Though it remains to be seen at the forthcoming Game O' Cards, as well as the promised Son O' Day O' Security: Clowns and Dancing Girls, how many colleagues have retained their new knowledge of CIA and STRIDE!

On a negative note, I've just lost my protégé, which probably seems a bit careless. Kind of a dev-elopement, you could say. Too soon to know for certain whether my mentoring on the fascinating realm of computer security testing drove him to his extreme of plank-walking despair, or enabled some shimmering new empire-building opportunity in the arena of inhouse penetration testing. Either way, our own security team having just been binarated (by analogy with decimated), I'd best go start recruiting once more. We're going to need a bigger budget...

Happy 2nd birthday, little bloggie.

Photo credit: Abdulrahman Bin Slmah www.abdulz.com CC licensed

Attack Type Update

2011-07-27T10:57:00.006+01:00

Popularity Upheaval

Imperva's just published web application attack report (3.46MB PDF) contains something of a surprise. For some time now, it's been the case that XSS (cross-site scripting) attacks were the most popular, having overtaken SQL injection. Not any more. They have been edged out, at least where implicated in application attacks, by a narrow margin of 37% to 36% (SQLi remaining at 23%), by new kid Directory Traversal.

The Four Main Attack Types

(from Imperva’s Web Application Attack Report Edition #1 - July 2011)

What is it? Essentially finding a way to pass-through the sequence of characters that represents the command “traverse upward to the parent directory”, into one of the vulnerable application's file APIs. Such a vulnerability can be present because of either insufficient security validation, or else insufficient sanitising of a user-provided input selecting a particular file name or path. The result of a Directory Traversal attack is exposure to the attacker, of the contents of files and folders not intended to be thus accessible.

Obviously the severity of the attack depends upon the nature of the exposed material. Favourite targets include such particularly sensitive files content as users' personal account information, system metadata, and so on. The technique itself of course is not new, only its paramount popularity.

Imperva Web Application Attack Report Edition #1 (July 2011):

http://www.imperva.com/docs/HII_Web_Application_Attack_Report_Ed1.pdf

John And Linda's Big French Adventure II

2011-07-17T00:29:00.037+01:00

Wednesday 29 June

As is becoming commonplace immediately prior to a holiday in France, our religiously serviced and meticulously maintained Civic develops sudden and spontaneous maladies out of le bleu. This year it's a grinding sound from one of the wheels during forward motion, and a cacophanous monotone whining buzz when reversing. Both seem related to the offside rear disc brake (offside when it's in the UK, that is). Incidentally, why do we even have a phrase like "rear disc brake"? Surely that alone indicates a bug, a fatal and fundamental flaw in your design. Like "pilot light", or, dunno, maybe "exploding nipple ring". Give me rear drums, or give me... erm... well, multiple handbrakes, I suppose.

Thursday 30 June

Car Guy Noel says we're good to go, despite sounding like angle grinders driving, or a lovelorn wookie in reverse; repairs are necessary, but can't be organised with zero notice. I could fix it myself, assuming of course that brake pads haven't been replaced by multicore proprietary silicon since last I looked in there. But I'm bound by the same time constraints as Noel, vis-a-vis obtaining any necessary replacement parts. Either way, they'll have to await our return in une Quinzaine or so.

My heart's not in my work, and I've finished doing anything nearly productive by about 6:20pm. Still a good hour and a bit in credit, but not the 7pm finish I'd promised my long suffering colleagues. What can I say, there's nothing left in the tank guys, I feel as guilty as a newborn lamb. Off to collect Linda, get home, start packing.

7pm: collect Linda, go home, make dinner (sausages!), eat dinner (yuk.), collapse into bed too knackered to pack. Luckily, Linda's already got most of it done: like, from about a month ago.

Friday 1 July

7am: bounce out of bed and pack the car; finally depart about 12. Yes, seriously. What's the rush? All we have to do is reach Portsmouth sometime today. At 4pm there's a rumble in my psychic powers. I turn on the car radio, search MW for 5 live, and we're just in time to catch the first few points of Murray v Nadal. Andy wins the first set! Then loses pretty much every remaining point in the match.

Car continues to grind and buzz. Thanks to a 2 hour gridlock near Brum, we don't hit Victory until after 10pm. Unload suitcases into the Hilsea Travelodge, where the brasserie is already closed. Damn, that would have been ace, sitting outside on a night like this, getting wired into some big steak. Instead we're forced to chow down on local chip shop fare: sausages again (puke).

Besides the apologetic and mildly despairing "Smile" notice, there's a mysterious second door in our Travelodge bedroom. Solid varnished darkwood, it has no handle, and no keyhole. We try prising it open by squeezing our fingers into the frame gap. There is no movement. We settle down to a somewhat wary rest, fully expecting it to admit a headless intruder at some point during the night. When it does finally burst open at 4am, admitting an eight foot wall of torrenting blood, Linda sleeps through it all, apparently remembering nothing about it in the morning.

Now playing: Queen - Absolute Greatest... which reminds me, here's one I wrote earlier! For Harry Hill: Careful, Freddie! You've already broken two of those! What more do you want? Freddie Mercury: I want to break free...

samedi 2 juilliet

Travelodges have no phones, so the 6 o'clock alarm is a polite knock on the door, simultaneous with both of our mobiles going quite loopy. But we're already up, half washed, two-thirds dressed, three-quarters way to the ferry port by then. No worries, plenty time! With a full English breakfast at the self-service on board the beautiful MV Normandy (big fat 6-hour cruise ferries each way this year, none of that Express crossing nonsense), we wave goodbye to the last of our sterling.

We're On A Boat!

Exploring the extent of our freedom above deck, soon we decide it's a little breezy up here, and go visiting the various shops on board. Before long we take up a comfy table in the bar, silently participating in the quiz being run by entertainments crew. Can't believe that not a single entrant identified the voice of Groucho Marx - what on earth are we coming to? Oh shut up, Mr Grumpy.

A couple of hours later we realise France can be seen approaching, so we're back out on deck devouring its coastline with eyes and cameras. Next, in no time we're back in our cars; then it's an (almost) error-free afternoon drive to Paimpol, confidently following nothing but the intermediate road signs via St Malo, Dinard, and St Brieuc. The contrast with last year's refugee landing and midnight random drive now seems like chalk and, well, anti-chalk.

Resolved to buy some local bread, cheese and Bordeaux to mark our arrival, we are lucky enough to reach Paimpol's Carriefour just before its 8pm closing. As we wait in the checkout queue, Linda tells me she's noticed our landlord M. Koffe standing in another line. When I investigate I'm unconvinced it's the right guy, and return to tell her this. Didn't you ask if it was him? Well no, curiously not; call me a big fat feartie, but I decided not to approach some random Frenchman with the salutation "Monsieur Koffe!" on the sole basis that he was black...

It's about two minutes after closing time when Linda tries to get someone to show her where to find un adaptateur. That person's insincerity, unhelpfulness and feigned ignorance are a blot on the whole nation's image and reputation! Luckily this will be our last cause for complaint about the locals this year.

Spook!

Departing for Ploubazlanec, I'm suddenly aware that we were supposed to phone ahead if arriving after 8pm local time, and of course when we get to the gîte at 8:15 there's no sign of life. Linda asks if I'm going to go round to see the neighbour, Emily, who was keyholder last year. And this part is true, and Linda is my witness: for no reason I can discern or imagine, I tell her, "Sure, but I don't think she'll be there. I think there might just be a man, doing some work upstairs in her house." She looks at me a little askance, and I don't blame her.

There's a note with two telephone numbers on the door, but we can't get through on either; a recorded French voice just keeps telling us, Orange. Blablah, blablah, blablah. The note says in English, "We are at Paimpol with friends," and so we go back there, thinking the problem might be nothing more than poor mobile reception; perhaps we can just pick up the key from them in town. But none of that is the case. I do however succeed in leaving a message on their home answering service, the longest French monologue I've ever attempted or achieved in my life, ending with "Au secours! C'est tout! Au revoir! A très bientôt!" But their home being in Nantes, 250 kilometres away, I don't expect much to come of that.

We return to Ploubazlanec looking for our Plan B. I take a walk round to Emily's house and ring the bell, but she's not there. Instead, a disembodied male voice from behind and above me demands, "Qui est là?"

"Où êtes-vous?" I ask, looking and turning around in a circle. I move into the middle of the driveway and there, poking out of a high attic window, I spot a rather distinguished looking, grey haired and bespectacled gentleman, holding a hammer.

Il Arrive!

I manage to explain our plight in broken French phrases, ending with my animated headshaking impression of the recorded voice, Orange. Blablah, blablah, blablah. "Etes-vous anglais?" - "Nous sommes écossaise" - "Attendre là," he offers, chuckling "C'est une distinction très importante!" and disappearing. I do a little jig, waiting for him to reappear in the doorway. Which he does. With a phone! Now we're communicating. I pass him the note from the door and he phones M. Koffe, announcing after a minute's conversation, "Il arrive!" - "Fantastique!" I opine, thanking him très beaucoup...

Returning to Linda, I tell her how my odd little prediction has just come true. She makes one of her own: there will be a bottle of cider in the fridge. Naturally enough, once M. & Mme Koffe arrive, full of welcomes and apologies, allow us in, waive the deposit, and then depart, this prediction too proves correct.

dimanche 3 juilliet

Just look at all that beautiful Breton countryside! After croissants, raspberry jam and coffee, Linda can't wait to walk the 100m or so downhill to la plage. I stay behind, clean up in the kitchen and try to get my mobile working by swapping SIMs and topping up. Once that's done I test it by phoning Linda, and my goodness gracious me, wasn't it just as well that I did! The poor wee darling is stranded on the margin, with sunstroke and unsocked heels and toes blistered from her brand new holiday shoes. I ride gladly to the rescue.

Her iPod now charging nicely, my clever wife arranges for lunch alfresco - or should that be en plein air? - under the parasol, with gourmet pork and Camembert. All this from last night's leftovers! Even the Diet Coke tastes ten times better here. After yesterday's early rise, six hour cruise, four hour drive and access crisis, today's theme is a day of rest. I start reading my holiday book, The Wise Man's Fear by Patrick Rothfuss, a thousand-page hardback edition I'd bought some weeks earlier and saved for Brittany. Later we venture to our favourite restaurant for our favourite Sunday dinners - moules à la crème, and filet de bœuf à la béarnaise. Now we're really here!

lundi 4 juilliet

Early morning trip to la boulangerie for bread, strawberry jam, etc. Get the maps out. Plan an excursion. Go to the seaside!

Evening meal: Président Camembert on baguette, with duck, pork, salad, etc. Check one box on my holiday list. That just leaves "barbecue"...

mardi 5 juilliet

Merde! J'ai oublié mes médicaments!

(to be continued)

Facebook: An Ugly Stupid Service

2011-06-30T10:41:00.006+01:00

... designed to teach you to systematically undervalue your privacy.

Author and freedom fighter Cory Doctorow in great form on this subject, censorship, psychology, and education (from TEDxObserver):

Rediscovered this morning at this Boing Boing post - itself inspired by John Scalzi's Whatever.

TEDTalks are distributed under a Creative Commons (CC) licence.

Security Testing Part 4 - Pentests

2011-06-27T10:29:00.014+01:00

A Monotone Spectrum

Pentests, short for Penetration Tests, describe the simulation of malicious attacks for the purpose of evaluating a computer system or network's security. These attacks are available in any colour, as long as it's greyscale...

In The Clear

Pentests are quite often clear box (or white box, or full disclosure) attacks, simply because as testers we more often than not have full access to, and complete knowledge of, the infrastructure to be tested. So, why not make best use of this advantage? Such knowledge includes all available information about the internal data structures and algorithms employed, the relevant source code used to implement these, the network diagrams, IP address data, actual passwords, and so on.

Examples of white box testing include:

API, Fault Injection and Mutation Testing methods.
Most static testing, e.g., code reviews, inspections and Valkyries (damn autocorrect: I meant walkthroughs); testing where the software isn't actually used. Instead for example, the code may be read, or scanned automatically for syntactic validity.
Code coverage can only be delivered through white box testing. Without inspecting the source code, there can be no guarantee that any given code path is exercised.

White box methodology is frequently used to evaluate the completeness of test suites created through black box testing methods (see below). This strategy allows the examination of the rarely tested parts of a system, ensuring coverage of the most important function points.

In The Black

Pentests can also of course be black box (also known as blind) tests, where there is assumed to be no prior knowledge of the infrastructure to be tested. As testers, we must first determine the location and extent of the system under test, before commencing analysis. When we use black box penetration testing methods, we are assuming the role of a real, external, black hat hacker, who is trying to intrude into our system without much actual knowledge about it. By contrast - almost literally! - white box testing can be seen as simulating what might happen after a leak of sensitive information, or equivalently, during an "inside job", when the attacker has access to confidential information.

Grey Goo

In between these two extremes, a school of grey box testing has evolved. As the name suggests, these pentests combine aspects of black and white box attacks. The main reason to do this is to provide customised test coverage for various elements in distributed systems. For example, we might use our knowledge of internal data structures and algorithms for the purpose of designing our test cases. Then when it comes to the point of actually executing these tests, we perform them as a normal user, i.e., at a black box level.

A good example of grey boxing is when we modify the content of a data repository, which is not itself part of the delimited system under test. That's not something which a user would normally be able to do, so it can introduce a white box element into an otherwise black box test or attack suite. Another example in a similar vein might be the determination of error message contents, or system boundary values, by reverse engineering.

Note that most instances of input data manipulation and/or output formatting do not qualify as grey box techniques, because by definition, input and output are not part of the system under test. So for example, integration testing between two code modules written by two distinct developers, where only certain interfaces are exposed for test, is still regarded as black boxing.

Careful Now!

Elementary white box penetration testing can often be done automatically, and therefore cheaply. Black box attacks are another matter entirely. Because you are literally attacking a network (often a working production system) blindly, your test activities will inevitably comprise actual security attacks. You will cause denial of service, both intentionally and as a side effect of the stress you put on network response time via vulnerability scanning. At worst, you might cause actual harm to the system, rendering it just as inoperable as had a real black hat attacked. Much of the time and effort required with black box pentests lies in trying not to destroy things, while still reaching deeply enough to expose vulnerabilities.

Pronounced "Awe Stem"

The OSSTMM, or Open Source Security Testing Methodology Manual, is both a peer-reviewed security testing, metric measurement and analysis methodology, and a philosophy of operational security. It is a Creative Commons licensed publication of the Institute for Security and Open Methodologies (ISECOM). As such, the encapsulated methodology, covering what / when / where to test, is itself free to use and distribute under the Open Methodology License (OML).

The Manual's primary objective is to create a scientific methodology and metrics for operational security evaluation, based upon test results. It suits most kinds of security audit: penetration tests, ethical hacks, security and vulnerability assessments, and so on. Secondarily it acts as a central reference in all security tests regardless of the size of the organization, technology, or protection, and provides analyst guidelines, enabling a certified OSSTMM audit by assuring:

test thoroughness and legal compliance;
inclusion of all necessary channels;
results quantification, consistency and repeatability; and
that factual information is derived exclusively from tests.

According to the ISECOM website, a handbook version of version 3 of the manual will be "available soon".

Previously:

Part 1 - Overview
Part 2 - Lab Work
Part 3 - The Attack Surface

Remember EA_Spouse?

2011-06-23T12:37:00.009+01:00

Well She Wrote A Book

No, not about the labour practices of a top video games firm in 2004 and beyond. Although that singular LiveJournal article certainly showed, among other things, that the (then anonymous) Erin Hoffman had a terrific talent for certain kinds of writing; EA: The Human Story was nominated for Joel Spolsky's Best Software Essays of 2004.

Subsequent events showed her to be equally determined, single purposed and shit stirring when deciding to embark upon a campaign, to highlight or right a wrong, to raise the profile of an issue she feels is getting brushed under the beanbag. Her gamewatch.org forum today holds over 12,000 posts in as many topics, though it seems not to have changed that world; for example, one comment from five years into the project (July 2009) revealed:

They're still doing it. I have a friend who is working 6am to 9pm 7 days a week as his project approaches release.

Despite Riccitiello's assurances otherwise, his middle management is fighting him and refusing to change. They are still paying below-the-poverty-line wages, they still are incapable of figuring out a schedule that doesn't involve abuse of its employees, and they are still playing games with employee classifications to avoid providing full benefits.

I'm in the industry, and if my company ever got acquired by EA, I would quit on the spot. My salary would be cut, my hours increased without compensation, and my work transformed into a bureaucratic mess (I've heard how heavy in middle management EA is). I'd be spending more time filling out useless make-the-managers-look-busy reports and attending endless meetings than coding and documenting. Nothing is worth this price, and people looking to enter the industry need to realize that.

Anyone but EA.

So Not About That Then

So no, like I said, the book's not actually about any of that. As you might more reasonably have guessed, Sword of Fire and Sea - subtitled The Chaos Knight, Book One - is a fantasy, written by one "obsessed with hidden truths, and the responsibility involved in uncovering them." Main character Captain Vidarian Rulorat is the last surviving member of his family. Obligated to an allegiance with the High Temple of Kara'zul by his great-grandfather's abdication of imperial commission (for love of a fire priestess, no less), Vidarian struggles to resolve the conflicts between the real world of his family legacy, and Andovar's hidden and morally ambiguous history.

One of the things drawing me towards this title, in addition to its glowing reviews by multiple Hugo Award winning SF/F novelists ("Read it and be swept away" says Allen Steele), is its length. Or rather, the dearth of it. Erin has made the very deliberate choice to keep it succinct. Short novels, she says, are rare in fantasy these days. She loves the short form, and obviously hopes many others secretly do too. From her Big Idea piece via John Scalzi:

I want to get in, get euphoric, and get out, without getting bogged down in lengthy genealogy records or endless hikes across Mordor.

Available to preorder at amazon.co.uk.

Computer Museum (2)

2011-06-19T14:15:00.039+01:00

Re-Animation

Fun though it was to dig out my old Sharp PC-1211 for the previous article in this series, it was a little disheartening to realise that any attempt to procure its toxic little mercury batteries would likely land me on a terrorist watchlist for the rest of my life. So it was a happy surprise to be reminded that its successor, the PC-1500, takes four bog standard AA cells. Here it is, recently emerged from the loft, all powered up and asking for permission to erase its now random memory contents, the dream debris of its (almost three decade) nap.

This 1983 purchase was funded through the usual channels. In other words, I initially went halfers with my pal Brian. Then once I'd accumulated enough buroo cheques, I did him over like Eric Cartman for full ownership. Honestly, sometimes I wonder how my friends ever did put up with my behaviour. But the time between striking this partnership and its ultimate betrayal was a golden age; the PC-1500 turned out to be a hacker's wet dream.

Peek And Poke

We discovered various ways to abuse this BASIC programmable pocket computer, forcing it to interpret pre-crafted code memory contents as data, and vice-versa. This first revealed that the BASIC ROM recognised several keywords not mentioned in the official user's manual. Not just any keywords, but the holy trinity of PEEK, POKE, and the almighty CALL. Soon we had discovered enough single machine code I/O instructions to discern that the processor was very Z80-like in its architecture, at which point Troy fell, and shit was lost.

Soon armed with the full processor instruction set, we started writing super fast Moon Landers, Star Treks, Snakes, Space Invaders... and of course my own personal favourite, Son of the Revenge of Complex Arithmetic III. Having figured out the display hardware too, we had what felt like unlimited graphics power. Although the monochrome LCD was just 156×7 pixels, it was much cleaner and sharper looking than that of the PC-1211, which had used an ugly yellow-green filter to protect its fragile, almost still prototypical, vampiric liquid crystals, from damage by daylight.

Actually on second thoughts, I think Dominoes was my favourite, for several reasons. It was the first game I wrote using the full power of the machine, and the one that paid off the initial purchase costs. The domino images were pixel-perfect, and the game let me introduce my dad to computers (no mean feat for a geek in the early 80s), because its UI was so friendly: to play the 3-4 domino, you just typed 34. Finally, the AI was terrific; it made a truly formidable opponent. How did I achieve this level of awe? I programmed it to look at your hand.

Technology Caught Evolving

So here's what my PC-1500 looks like inside. Notice the two 0.1" pitch chips, the ones labelled TC5514P, sticking up like sore thumbs on an otherwise 0.05" pitch surface mount 2-layer board with through plating. Those are 1K by 4 bit static RAMs. The big LH5801 on the bottom board is the CMOS static 8-bit CPU, its LH5811 neighbour the peripheral I/O controller (an unwritten law said these always had to be named +10 higher than the corresponding CPU part number). The whole machine, like all such pioneers, screams a thoroughgoing compromise of new and old technology; 6V performance versus 130mW C-MOS battery life.

No Peripheral Vision

We never did fork out for the audio cassette interface and printer. This might seem unbelievable now, but it's true: the ritual and preamble to playing a computer game involved an hour or so of typing it all back in again. From your own notebooks, or from multipage magazine listings. Quite often this was the point at which games evolved, as you'd notice some possible improvement, or identify a great extension, each time you laboriously re-typed the now familiar code.

That was bad enough for BASIC code. But now we had to enter machine code and hexadecimal data, all without the aid of an assembler. Not something you want to have to do even once, but we did it every day. More than the lack of program memory, it was this tiresome drudgery that taught us only ever to write optimum code, first time.

I did design, and build into one of those pale blue Marshalls Electronics project boxes, a DC power supply to use with the PC-1500. Sadly I never really trusted my own crowbar overvoltage protection circuit enough to use it for more than a few minutes at a time. Eventually binned it just last year.

Previously: Computer Museum (1)

▶ Update (June 25): the day after I power it up, the old PC-1500 begins haemorrhaging from the top right corner of the display. Click the photo on the right to sleuth the evidence. What the hell is this? So I dismantle it...

◀ Inside there's this 10cm dark red opaque plastic block, soft yet brittle, seemingly stuck to the top of the display with strawberry jam. That's it on the right hand side, while the trail of blood can now be seen on the PCB, display, bezel, and other components of the casing. This is going to take a lot of solvent, and a few drums of cotton buds...

Half a bottle of meths and 100 cotton buds later: burp. Well that was an epic, what a fiddly stripdown, clean and rebuild. But the operation, the sticky gunky gluey plastic blockectomy, has been a success, and the wee beastie is back in pristine working condition. As for the thing I removed, not been able to find any reference to that in the online PC-1500 reference material. I suspect it may have been a thermal mass.

The late seventies belonged to the bright, power hungry, red 7-segment LED wristwatch and calculator. Arriving in their New Romantic mullets, the first LCD replacements were quite temperamental, by which I mean, temperature sensitive. They needed thermistor circuits to stabilize their viewing angle. My guess is that the soft plastic strip I've removed and discarded was designed to average out fluctuations in the sensed temperature, e.g. to stop the display from fading when the device was held in warm hands.

This work, including photography, is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported Licence.

Sonny Marvello

2011-06-18T00:13:00.022+01:00

Update 16 December 2011

This post has been removed.

Update 7 January 2012

On the other hand, the band's offensive remarks haven't yet been removed from Facebook, and are still publicly viewable. I guess it does no further harm to repeat them here:

https://www.facebook.com/sonnymarvello/posts/3015725752922

Prog Rock & Metal News

2011-06-17T20:46:00.012+01:00

Read All Around It

Most mornings, Google News is your excellent first stop shop for all that's happened in the night. The exception is Sunday, when nothing lighter than the dead tree edition of The Sunday Times will satisfy (online access not required, thanks). Truth is, I would still buy that weekly hundredweight of paper if everything except Dan Cairns's new music reviews got blacked out.

For all those other, lesser days of the week, the customizability of the Google News U.K. page* ensures there's always more than enough news, knowledge and gossip on tap. The important step is that customization. My own choice of standard sections, given geography and blogging interests, holds no surprises: World, U.K., Scotland, Glasgow, Sci/Tech, Physics, Astronomy, Space, Computer Security, Video Games, Entertainment, and Rock Music.

If you haven't personalised your Google News page yet, use the Add a section link at the top right to find and add news categories that interest you, and the Edit this page link to organise these, or to delete those of no interest. I'll never forget that enlightened day when my whole life, well my Google News experience anyway, improved tenfold as I finally got rid of those toxic default Business, Sports, Health and Spotlight pages.

The Lost Chord

But there's one more, essential category of update you won't want to be without. I speak obviously of the latest events in the world of progressive metal music. None of the standard supplied pages can quite satisfy the exacting criteria of this specific thirst for knowledge. Despair not, fellow geek headbangers, I bring you good news! Literally. I mean I've created a suitable custom section, based on the simple query "prog rock, progressive metal", which teases out of the Googleplex, just the optimum mixture of attention worthy, classic and modern, metal, prog, and their bastard offsprogs.

On the Add a section page under Search for sections, type progressive metal and hit Search. You should return just one result, titled Prog Rock & Metal; that's my page. Here's a link to its current content:

http://news.google.co.uk/news/section?pz=1&cf=all&ned=uk&hl=en&csid=7d6ecf57b214b344

Never a week goes by without at least one or two interesting developments popping up here, which I haven't yet seen elsewhere. And the page is currently enjoying a great surge in popularity! Last time I checked, I think there were a total of approximately four subscribers. Wow! Clearly this is a phenomenon whose something something now! And just imagine: you can be subscriber number five. That's right, I'm letting you in on the ground floor of this unique opportunity.

You're welcome.

* Actually the BBC News site gets roughly equal time; public service output is an excellent antidote to filter bubbling.

Update (July 18): Yes, in the wake of the phone hacking scandal, my entire extended family and I have now joined the inevitable total boycott of all News International publications. But to my shame, I should have done this many years ago. But for all its faults, crimes, and abuses, still there's nothing out there to approach the quality of The Sunday Times when it's good. Trouble is, we can no longer determine when those times are, and when by contrast, it is being controlled - nay, written - by organised criminals. My Secondary English teacher Mrs Abraitis once enjoined us all to commit to this, then venerable, paper; and as many a raped choirboy might attest, such formative imperatives often cast long shadows.

Today I can only hope that Dan Cairns will move his musical journalism expertise quickly elsewhere.

Focus!

2011-06-13T18:03:00.005+01:00

A Fortuitous Juxtaposition

RSS readers will have missed the coincidence of expression in my Technology sidebar today, where these two articles from different Microsoft blogs collided:

Nice to know the Key to Success at Microsoft is not something that you need to steal.

A Really Good 4096-bit AES Key Service

2011-06-13T17:00:00.000+01:00

Where Do I Sign?

Sorry, there's just no such thing. Oh it exists in principle, yes. In theory. In Plato's universe of ideals, yes, you can buy them there. Pick them up for free, in fact. But as Robert X. Cringely (who is not a spy) explains in the article When Engineers Lie, "Build a really good 4096-bit AES key service and watch the Justice Department introduce themselves to you."

Bob also answers the perennial question about architectural secrecy: why is it needed at all, if 1024- or 2048-bit codes really would take thousands of years to crack? Isn’t the encryption, combined with a hard limit on login attempts, good enough? The answer is no. Part of the explanation is that the U.S. government insists on nobbling the key services of every provider - RSA, Cisco, Microsoft, just everybody - to ensure they're sufficiently insecure, to enable snooping. The cost of noncompliance is, of course, jail.

For the obligatory silver lining, Bob points to IPv6 and Open Source, which he reckons "are beginning to close some of those security doors that have been improperly propped open." Go read his article at I, Cringely to find out why.

V For Vendetta

Recently this little blog hasn't been doing its job, of reporting on the latest big security breaches, how they were done, whodunnit, and to whom. Quite simply there have been far too many; an almost unprecedented number of successful attacks, on a scale rarely seen previously. And as I've said before, the media coverage of this phenomenon has been such as to render my monthly Security Digest utterly redundant.

Instead we sit on the sidelines enjoying the mayhem, grumbling agreement with Bob Cringely. Or with Patrick Grey at Risky.biz, who reckons that we - the professional security community - secretly love LulzSec. Patrick's rant is still more entertaining than Bob's, and just as thought provoking, as he laments his ten years of futility, trying to get businesses to see and acknowledge the potential for chaos which LulzSec is now so ably demonstrating, and which is gradually earning the reluctant respect of security researchers:

Security types like LulzSec, because they're proving what a mess we're in. They're pointing at the elephant in the room and saying "LOOK AT THE GIGANTIC FUCKING ELEPHANT IN THE ROOM ZOMG WHY CAN'T YOU SEE IT??? ITS TRUNK IS IN YR COFFEE FFS!!!"

Not Necessarily the Official SDL Position

Local hero and a familiar name to readers of this blog, Adam Shostack chimes in to express reluctant, or guarded, agreement. In his article Are Lulz Our Best Practice? he confides that he takes "a certain amount of pleasure in watching LulzSec. Whoever’s doing it are actually entertaining, when they’re not breaking the law. And even sometimes when they are."

In prescribing the way out of our present troubles, Adam returns to the main point being made by Bob in the first article above. Salvation lies in admitting the breaches that do occur, talking about them and about the wider world of security openly, transparently and honestly.

Seven Seas of Rhye

2011-06-12T12:33:00.009+01:00

Wouldn't exactly call myself a Queen fan.

Commercially, they had some spectacular ups; some surprising, and some predictable, downs. Theatrically, they were always sans pareil. Lyrically of course, Freddie never stopped improving for all of his life. But musically speaking, seriously, I don't think they ever bettered this song. The rolling sixth beloved of all forms of popular music, and equally overused in them all, gets a twist in the opening piano arpeggio. Verse lengths are permuted by variations in the end pause (and one minor deviation). An excursion into the subdominant bridge resolves almost too smoothly into the tonic return. And the ingenious, percussive meter of the final verse alone is worth the ticket price.

Saw them play this in Glasgow in 1973, when they supported Mott The Hoople. They got encored - while Ian Hunter, exiting stage right, had to beg for theirs! That tour was the very first, the last, the only time Queen played support for anyone.

Simple Regular Expressions #3½

2011-06-04T11:09:00.036+01:00

Undo Revisited

I've been taken to task for failing to provide a Regex-based solution to the problem in the previous article of this series, namely, removal of backtracked elements from a path. One correspondent even left a comment containing the missing Regex solution! Another complained that my I/O path specific .Net workaround would be zero help to someone just happening upon my article, maybe while researching some other aspect of the underlying patterns.

It's a fair cop, and the only way to salvage even a wee bit of reputation is to provide a full explanation of the proposed Regex solution. In mitigation, the proposed mechanism (Balancing Group Definitions, described below) is also unique to the .Net implementation of Regex. But hey, I'm only the piano player...

This is one of those curious cases where the attempt to generalise the problem reveals a simplifying hidden structure. The first underlying pattern mentioned above is the Undo (or sometimes the Delete) pattern. Consider the original example:

d:\project\client\forms\..\..\version.cs

The entire midsection "\client\forms\..\.." is redundant; we'd like to delete such missteps, obtaining a "normalised" answer such as

d:\project\version.cs

Consider the operating system's behaviour as it attempts to follow the original verbose path. It acts like a finite state machine. Each time it encounters a subdirectory name, like \client or \forms, it enters that subdirectory. Each time it encounters the parent token \.. it reverses back out of the most recently entered subdirectory.

But look what happens when we replace the phrases subdirectory name with letter, and parent token with backspace. Now the problem can be seen to be completely analogous with that of correcting a typed word.

A Typo Processor

Let's use the # symbol to represent the pressing of the backspace key. Then our new problem is to take an input comprising a sequence of letters and # symbols, and parsing it, recover the correctly typed word. For example, if I misspell yield as yeild but correct the mistake manually before completing the word, then the input string (the received sequence of keystrokes) might be yei##ield, and the required output is, of course, yield.

The pattern that our Typo Detector has to detect is: a number (one or more) of # symbols, immediately preceded by exactly that same number of letters. This then is the pattern - in the example case, ei## - that must be removed, in order to, erm, yield the corrected word.

Following the naive reasoning of the original article, we might try using something like \w# (one "word" character, followed by a backspace token) to match the typo pattern. And just as before, this fails in the second simplest test case (the ei## of the previous paragraph). What we need is \w\w## to match that case. But then we also need \w\w\w### to detect the case where three consecutive mistyped characters are corrected. And so on. In fact what we need is approximated by the pseudopattern

\w{n}#{n}

where n cannot be specified in advance, but

is greater than zero, and
represents the same number in both positions.

Actually, we want even more than that. What about cases where I make a mistake while correcting a previous typo? For example yei#i##ield. Ideally we'd also like permuted edit patterns like this one, \w\w#\w##, extracted as entire single units. Unbelievably, this functionality is readily provided by the Microsoft proprietary Regex extension known as...

The Balancing Group Definition

But first, let's revise the Group concept from the ground up. Groups are simply added to a Regex by surrounding any pattern subexpression in parentheses. For example, the pattern

0141(\d{3})\d{4}

not only matches any BT landline number in Glasgow, but also allows the central three-digit exchange code to be retrieved conveniently as a group for use elsewhere. These anonymous groups are retrieved by numerical index, which can quickly get a bit too fiddly for comfort.

The next level of usability is the named group. The prefix ? within a group introduces its name, which should be enclosed in either apostrophes or angle brackets. For example, the pattern

0141(?'exchange' \d{3})\d{4}

allows retrieval of the three-digit exchange group by name. And we are nearly there. Because it's an interesting implementation detail about groups, and in particular named groups, that they are pushed on to a stack as they are identified. This means that they can also be popped off. If we can push a group for each word character typed, pop one for each backspace token, and determine when the stack becomes empty, then we can detect all redundant groups in the input stream.

The balancing group definition will delete ("pop") a previous group, and replace it ("push") with the interval between the previously defined group and the current group. Syntactically, we append the previous group name to the current one, using a hyphen for separation. So it looks like this:

(?'curr-prev' subexpression)

The current group name curr is optional, since nothing says that all groups have to be named. The previous group name prev is mandatory; we do need some way of referring to it, since we're about to pop it.

Here is the magic pattern:

\w((?>\w(?'N')|#(?'-N'))*(?(N)(?!)))#

Since it detects an erroneous word character which is subsequently deleted, it begins naturally enough with \w( and ends with )#. Hey this is easy! Now look at the first interior pattern, west of the asterisk:

(?>\w(?'N')|#(?'-N'))

This is saying a couple of things:

If there's another word character \w then push a new group, which we call N.
Otherwise if there's a backspace token # then pop the most recent group named N.

The asterisk allows this process to happen any number of times, including zero. This corresponds to typing some characters, deleting a few, typing some more, and so on. Penultimately, east of the asterisk and just prior to the final #, we find another expression:

(?(N)(?!))

This is a trick! If there are still undeleted word character groups on the stack, i.e. an N that hasn't yet been popped, this construction forces a match against the pattern (?!) about which all we need know is that it will fail. Well okay, it's called an expressionless negative lookahead, if you really must know everything! Otherwise so long as the final # appears, we have found a wholly redundant segment.

Back To The Path

If in our magic pattern we now replace \w with a pattern for a subdirectory name, such as \\\w+, and if we further replace # with the parent directory pattern \\\.\. throughout, then we transform it into the path normalizer that was the subject of the original article. The details are horrendous, because filesystem subdirectory names can contain other than word characters, including dots. We have to exclude \.. from these, and \. requires even more special handling. Nevertheless we have solved the fundamental problem of applying Regex here, and as it so happens that all of my subdirectory names were well behaved and dotless in any case, this solution would have worked for me.

Further Generalisation

The Undo/Delete pattern itself represents a simple subset of the problems that these Regex Grouping Constructs are capable of solving. Refer to the MSDN Regex topic on the applicability of Balancing Group Definitions for a complete guide to applying these constructs in any given recursively nested construct parsing context, such as matching parentheses, opening and closing brackets, quotation marks, mathematical expressions, or lines of program code containing multiple nested calls (most of which cannot be parsed in Regex implementations other than the .Net one).

Though be warned, the expository technical language used over there assumes at least some familiarity with the domain of abstract formal languages. Perhaps a better, more gentle introduction to balancing groups can be found in either of these articles:

Update (20 June 2011): I was going to share my .NET Regex Tester online with you, before I noticed that Derek Slager's is, in his own words, better... so, here's a link to his:

http://derekslager.com/blog/posts/2007/09/a-better-dotnet-regular-expression-tester.ashx

Good luck!

Logicly

2011-05-23T09:06:00.018+01:00

The Digital Division

Little Nephew has a physics exam today, so we've been busy revising the curriculum over the weekend. Near as I can tell he's hitting full marks in the first five out of the six component units: Movement, Radiation, Telecommunications, Electricity, Sound and Music. Not that the sample questions are a great indicator of a candidate's proficiency. I'm certain you could replace your grasp of physics by the algorithm, "Divide the first number by the second", and score about 65% using that stratagem alone. He does seem already to have grasped this fact.

The sixth and final unit covers the basics of Digital Electronics. Whether because it's the most recently introduced (we have previously had multiple sessions on the other areas), or because there are no number pairs to divide into each other, this does appear to be his one comparatively weak spot.

I've written previously about the efficacy of bringing practical demonstrations and aides-mémoires into our lessons, and for several months had been toying with the idea of writing a simulator for the basic digital electronic components - gates, flip-flops, registers, switches, LEDs and so on. Even made a few aborted attempts, in C#, Logo, and Scratch. But these kept getting bogged down by one particular detail: propagation delay. If a given circuit would in reality oscillate, then I felt that the model should do likewise. Unfortunately, this single choice opens the floodgates to a torrent of design decisions, turning the unwary engineer into a startled frozen rabbit...

K.I.S.S.

Eventually yesterday, while he took his well-earned break and game of L.A. Noire between units 5 and 6, I decided I'd reinvented enough wheels for this month; performed a quick web search; and downloaded a 30 day demo of the first digital electronics simulator found. This was Logic.ly, and I could never have wished for a more perfectly dovetailed fit to match our educational requirements. Had it up and running in three seconds. Had example circuits from his textbook entered and working ten seconds after that. Okay I might be exaggerating a little; it's actually a cross-platform web based app, requiring installation of Adobe AIR to provide the offline standalone version. But that's just how it felt. Everything dragged and clicked exactly as expected, working instantly, with not a single word of prompting. Surely the only possible definition of the perfect UI.

Designer Josh Tynjala has Kept It Simple, Stupid. There's no fatally misguided attempt to model propagation delay accurately, which I see now is technology dependent anyway. After all, some ways of constructing real, physical logic gates, instead of allowing runaway oscillating designs, might go into a thermally destructive linear mode. Rather than second-guess your technology tradeoffs, Josh's gates simply tolerate forced inconsistencies, and leave aberrant behaviours to be discovered in later, practical lashups with real components. Bravo.

What's In The Box

The supplied component set was also more than ideal for our needs (hyperbole intended). Gates include inverters, and n-input gates (2 ≤ n ≤ 8) in all flavours (AND, OR, NAND, NOR, XOR, XNOR). A nice touch is the configurability of these last two for either odd/even parity or "=1" behaviour. At the next level of integration, there are flip-flops of the SR, D, JK and T kinds. Input controls include fixed logic levels, toggle and pushbutton switches, and a square wave generator. Outputs can go to either single lamps or 4-input hex digit displays.

Despite my earlier remarks on propagation time, the available components do include a buffer. According to the documentation, this "simply propagates the signal it receives. In the real world, a buffer will boost the electrical signal, if it has lost strength. In Logicly's simulation, one may use the buffer to affect propagation time." Hmm, I read that as: "future expansion".

Three demo circuits are provided to help get you started on more advanced projects: a D Latch memory cell, 1-bit Full Adder, and a Ripple Counter. Best of all, you can try the free demo online (no download required, but does need Flash 10).

Customisation

The circuit editor has configurable grid size and snap. Logic gate symbols are switchable between the distinctive shapes of the ANSI/IEEE standard, and the rectangles used by the IEC. Wire colours are used to indicate logic levels 0, 1 or indeterminate; these colours can be disabled or customised. Finally, unconnected inputs can be assigned a default logic level. When I started playing with chips in the 1970s, everything was TTL, and floating inputs went to logic "1". Some cretins even used this fact in their designs. The same idiots who bequeathed us the millennium bug, no doubt.

My Wish List

A killer feature would be the ability to package your own debugged circuit into its own little chip, a bit like the supplied flip-flop components, making it available for reuse in further designs. That's a lot of work, but I'm sure Josh has already thought of it plenty of times. Just the same, think I'll email him with the suggestion. Alternatively, or additionally, some more components from the MSI range would be good. Shift registers, multi-bit adders, that sort of thing. Lastly, a native Print option in the standalone version might not hurt a lot.

So... Did It Work?

Little Nephew is sitting his exam as I write this. I know he'll do extremely well.

Ambient Cursed Drone Psychedelic Travel Toulouse

2011-05-21T11:21:00.002+01:00

&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;a href="http://saaad.bandcamp.com/album/pink-sabbath-ep"&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt;Pink Sabbath EP by Saåad&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;lt;/a&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;gt;

Is Jonathan Fargher Entirely Trustworthy?

2011-05-20T09:25:00.026+01:00

Sony's Apology Package

Haven't had much to say about Sony's recent security troubles. Well, it's hard to travel anywhere on the news websites and blogs, without crashing into Floydian walls of opinion about the corporation and its permanently besieged Playstation Network. Even on the subject of this post, namely the "apology package", there are countless deafening choruses of "too little", "too late", "also, I want an Xbox", and related flamewars without end.

However

Jonathan Fargher, senior PR manager for Sony Computer Entertainment Europe (SCEE), has crossed a line with me. And I'm sure, with every other gamer with a gramme of technically literacy. If I may quote just two lines of his, from say the BBC's report:

Clearly there's going to be a minority of people out there who have some of those games.
We certainly believe [...] the choice of games that we're offering [...] is good value.

Of course I have to be careful what I say now, mindful of my country's draconian, and quite literally, unspeakably insane 17th century libel laws. But given these two statements, it is quite easy to prove with rigor, using little more than the rules of the predicate calculus, that Jonathan Fargher is either deranged, or a liar.

The proof doesn't depend on the truth or falsity of the individual statements themselves; given certain platitudes, it's as certain as any proof in logic, more so than any in the rest of mathematics. It is true regardless of whether or not some people already have some or all of these games; whether those people form a minority, or a majority; whether the choice of games is good value or a ripoff; and whether or not Jonathan Fargher believes some, any, all or none of the above. No single given factoid convicts. Rather, Jonathan Fargher's problem is that there's no consistent assignment of truth values to the various parts of his statements, that avoids the incriminating conclusion.

Reductio Ad Absurdum

We proceed by assuming the truth of everything Jonathan Fargher claims in those two statements above. From this we derive a contradiction. Finally we conclude that either Jonathan Fargher believes this contradiction, in which case he is arguably deranged; or alternatively, he doesn't actually believe (one or more of) his own claims. In that case, inescapably, he's a liar.

So, working from the back to the front: the second thing Jonathan Fargher believes is that the choice of games is "good value". How can we express this in less subjective terms? Let's take a look at that choice.

PS3 Title	Release Date
Dead Nation	Dec 2010
Infamous	May 2009
Little Big Planet	Oct 2008
Ratchet and Clank: Quest for Booty	Aug 2008
Wipeout HD/Fury	Dec 2009

Apart from the PSN exclusive zombie shooter Dead Nation, and the Fury addition to warhorse Wipeout HD, everything here is two or more years old.

PSP Title	Release Date
Killzone Liberation	Nov 2006
Little Big Planet PSP	Nov 2009
ModNation PSP	May 2010
Pursuit Force	Nov 2005

Wow. I'd forgotten there even was a PSP console in 2005.

Yet regardless of the considerable age and the low current prices (below £10) of many of these titles, and notwithstanding the fact that you get to pick only two games from either list, none of this allows us to deny Jonathan Fargher's claim of "good value". Why? Because here, they're free. Any attempt to compute the value-for-money of a given selection results in a division by zero error.

That can't be right. Are we now agreeing with Jonathan Fargher, and going fargher still, to say that the selection represents infinite value? No. Clearly the concept of value-for-money is inapplicable to truly free offers. A better gauge is the popularity of the selections. The more popular the game, the higher its value as a free offering. But here we begin to see the seeds of the contradiction that we seek. In a given console community, popular games are by definition those most likely to be owned already. And to such an existing owner, a free download of such a game obviously has a very low value indeed.

Summing Up

From Jonathan Fargher's Second Law, we are being offered a "good value" selection of games, in other words, a set containing at least some popular games. By definition, such games are already owned by a majority of a given console community. That contradicts Jonathan Fargher's First Law, that no more than "a minority of people" will already have any of those games.

Quod erat demonstrandum.

Obscurity ≠ Security

2011-05-09T09:00:00.003+01:00

Unintended File Sharing

In their paper presented at LEET '11, the March USENIX Workshop on Large-Scale Exploits and Emergent Threats, a team of five researchers from Belgium and France draw attention to certain very significant weaknesses in file hosting services (FHS) such as Easyshare, FileFactory, and the daddy of them all, RapidShare.

Basically these sites and many others use the secret URI method of sharing uploaded files. Of the 88 services examined in the study (12 of the original 100 having become excluded, because they offered search features, and therefore no pretence of privacy), 34 were found to employ simple sequential file identifiers. 20 of these used no further mitigation against the simplest attacks. The other 14 appended the original file name, yielding an ID effectively unknown to the attacker.

Attack!

Unfortunately, those most vulnerable 20 include some of the most popular and highly (Alexa) ranked sites. Their entire collections of private hosted files can be enumerated quite simply, by uploading a test file to acquire a valid file ID; then repeatedly decrementing that.

The researchers confirmed the viability of this attack by actually implementing an automatic crawler for those 20 sites. It managed to retrieve some 10,000 files per day for a whole month. Approximately half of these files had no other visible links on the web, suggesting that their owners do in fact regard them as effectively private data.

Decimate!

Even among the FHSs using additional obscurity, such as the original file name or randomly generated identifiers, short key lengths and restricted character sets were often found, as in many password contexts, still to leave protection relatively weak.

Additional security features available with some FHSs include CAPTCHA and a delay before download. Amusingly, most of these services also offer a paid "PRO" version which removes these "restrictions". Password protection, which makes more sense in real security terms, is only offered in about a quarter of cases.

HoneyFiles

The paper then goes on to document further vulnerabilities, for example in the publicly available software that even some of the better FHSs use to provide their services. But even that is not its best part. The researchers next went on to develop ingenious techniques utilising decoy documents, to determine the extent to which the security vulnerabilities of these websites are already being exploited by malicious users.

They even geolocated the hundreds of attacks on their "HoneyFiles". Perhaps unsurprisingly, more than half originated in Russia, and a further quarter in Ukraine. But significant contributions from fifteen other countries confirmed the world wide nature of these attack types. The researchers detected repeated attempts to use the fake credentials advertised in their HoneyFiles, as well as attempted SQL injection and file inclusion attacks.

Remedy

Encryption on the user's local computer is obviously a good mitigation. The researchers have developed a proof-of-concept Firefox add-on, automatically to encrypt and decrypt files on upload and download, and to hide encrypted files through steganography.

http://www.usenix.org/events/leet11/tech/full_papers/Nikiforakis.pdf

Mission Accomplished

2011-05-04T12:37:00.028+01:00

Ten Years After

Note: written on the day Osama Bin Laden was killed.

There's no doubt over the main news story this week: after a decade of planning, attempted operations, rhetoric, minor victories, apparently endless cold trails, dashed expectations and anticlimax, the operation was finally given the green light last weekend. To enter an impoverished strip of land, an isolated state ruled by an Islamist group regarded by some as being more than merely sympathetic to terrorism. A seemingly impossible border crossing, finally if indirectly negotiated by just over two dozen brave and dedicated professionals. A single determination and fixity of purpose, in an operation which had to be co-ordinated in utter secrecy until eventually, success was made certain, and the word was out.

Daniel Barenboim, co-founder of the West-Eastern Divan Orchestra, led an orchestra of European musicians in a "peace concert" performance in Gaza.

Daniel Barenboim, Vienna, 2008. Picture: Wikipedia.

Guerrilla Performance

Since its inception in 1999, millions have followed and been entertained, educated and inspired by the history, the example, and the performances of the West-Eastern Divan Orchestra. The brainchild of Barenboim, an Argentina-born Jew who today holds Palestinian citizenship, and his friend, the now deceased Palestinian literary scholar Edward Said, it was intended from the start to bring together young musicians from Israel and Arab countries, seeking to enable dialogue between the various cultures of the Middle East, and promoting peace and co-operation via the making of music together. Today, still featuring both Jewish and Palestinian musicians, the orchestra has members drawn from Egypt, Iran, Jordan, Lebanon and Syria, and boasts an international reputation for the quality of its performances.

First time I watched Paul Smaczny's multi-award-winning 2005 movie about the West-Eastern Divan Orchestra, Knowledge Is The Beginning, it was mostly with my jaw on my lap. I recall saying to Linda, "This wee guy's saving the world!" and also if I remember correctly, there was a wee bit of dust or some such bloody thing in my eye at the time.

The West-Eastern Divan Orchestra, Pilas, Sevilla, 2005. Picture: Wikipedia.

This latest victory against the forces of fear, ignorance and intolerance once again shows the maestro continuing from strength to strength. Israeli citizens are prohibited by law from entering Gaza, however the new Egyptian military leaders have plans to open the border at the Rafah crossing. Barenboim entered Gaza via Egypt, together with 25 other musicians. Then they played some Mozart.

Update (June 25): Well whaddayaknow, Danny boy's only gone and got himself an honorary knighthood from Her Maj. Or rather, from the British ambassador to Berlin, at a gala dinner in the German capital. He is now a KBE - Knight of the British Empire - the highest honour said empire can bestow upon mere foreigners.

I've also learned that there are two versions of Paul Smaczny's film Knowledge Is The Beginning in circulation. The one currently showing on British Sky TV is the original, and ends when the dream of a Ramallah concert seems lost. Paul yelled out Cut! and Print! then spliced in some other live performance footage to round off the work... a matter of mere days before it became clear, towards the end of the tour, that in fact the troublesome security issues had been resolved; Ramallah was going ahead.

The edition on the 2DVD set is a revised and updated version. It shows the different factions entering the West Bank, all under their Spanish diplomatic passports, but separately and at different times (the Israeli musicians not arriving until the day of the performance). This is followed by some actual footage of the Ramallah concert, and rounded off by one of (Sir!) Daniel's amazing humanitarian speeches. The second DVD is, of course, that entire concert.

Freedom House Report

2011-04-22T09:45:00.022+01:00

UK: Worst of a Good Lot

Sponsored by the United Nations Democracy Fund (UNDEF), Freedom House just published the report Freedom On The Net 2011.

The good news: UK narrowly escapes relegation from the first division, retaining its Internet freedom status designation of "Free" (up to 30 points) with a nail biting 25 bad boys - up from 2009's (adjusted) total of 23 strikes. Only Italy and South Africa, at 26 points each, fare worse in this division.

Trajectory: Slight Decline

The full league tables are here:

http://www.freedomhouse.org/images/File/FotN/MainScoreTable.pdf

The most worrying aspect, for user rights activists anyway, emerges when these scores are analysed by the three broad UNDEF categories: obstacles to access, limits on content, and more disturbingly than those, violations of user rights.

1: Obstacles to Access

The first category assesses barriers to access, both infrastructural and economic; governmental blocking of apps and/or tech; and control over access providers. Clearly there is some room for mitigation in this category, as not all of a network's shortcomings are necessarily planned to be such. The UK however makes no capital of this mitigation, scoring but a single point here - the best performance in fact among all of the (now 37) nations covered by this year's report.

2: Limits on Content

Next the survey considers "content limits" - all forms of censorship, including website filtering and blocking, content manipulation, and the availability, diversity and usage of digital media for social and political activism and news. Here we find the UK scraping its arse along the bottom of the channel, tying with Italy on 8 points, only South Africa worse on 9.

The Internet Watch Foundation comes under particular and extensive criticism for its persistent technical incompetence, absence of clarity and transparency in its blocking and removal criteria and actions, its inadequate appeals process, and lack of any judicial (or even governmental) oversight.

3: Violations of User Rights

That just leaves legal protections, restrictions and prosecutions, surveillance, privacy, imprisonment, and harassment including physical attacks. No surprises here, with the UK emphatically at the bottom of the division on 16 points (second worst is Italy on 12).

The disastrous Digital Economy Act is highlighted, although the interim conclusion on that score states "In a positive development, the newly elected coalition government has promised to review and repeal a number of laws that negatively affect online free expression and privacy." As we have now seen this fail to happen, there must be doubt over the UK's overall "Free" status today.

Conclusions

Internet freedom in the UK is measurably deteriorating year by year, as evidenced by the decline in the "free" status reported by successive Freedom House biennial surveys. The country specific report provides the details:

http://www.freedomhouse.org/images/File/UK2011.pdf

Many of these reasons have already been well publicised, for example:

The expansive restrictions of English libel law are identified as having "...a significant chilling effect on both content producers and ISPs."
Further high profile cases, illustrating the frequently ass like nature of the law, are included; such as freedom to tweet your frustration about airport closures through the medium of mad parody, and police sanctioning of cybercafe snooping by proprietors.

It's hard to escape the conclusion that we have already seen the UK's final days at the top table of Internet freedom.

Ravish Revisited

2011-04-22T00:07:00.007+01:00

New Artwork!

Having a great Easter holiday right now, driving around mostly at random. Yesterday saw a day trip to the Lake District, stopping off at Windermere, grabbing an alfresco at the Wateredge Inn. More about that later, maybe...

Day before was a lazy local sightseeing trip of New Lanark and the Tinto hills. That's when we found this lovely old pavilion. Now admit it, if you rounded a random corner to find such a distinguished, beautiful brickwork black board, you'd screech to a halt for a proper pic, and use it as artwork for your new single.

Well, we got there first. And while the super limited mini-vinylesque edition might already be sold out, you can still help yourself to the free MP3 download here:

1: Ravish
2: The Drummer's Hashpipe
3: The Devil's Pot Pipe

Artwork: Front Back

Penultimate Retrochamps

2011-04-08T23:59:00.080+01:00

Futuristic Retro Champions
The Captain's Rest, Glasgow
8 April 2011

On iTunes: Love and Lemonade

Never would have thought it possible, simultaneously to be so very sad, yet so happy. Certainly not after just that single pint of fresh orange and lemonade! But the happiness comes as standard with FRC, about whose contagious brand of emotronic happy hardcore I've written before. It comes from their performance, their open and unapologetic optimism, bright melodies and infinite smiling.

Happiness comes too from stellar songwriting, which above all else about them, so deserves to be cherished. Pleasure comes from their sheer quality of vocal harmony, arrangement, execution and production. From ingenious lyrics that create empathy, joy and sublimation. The absolute nailing of the sound they're after, with the biggest, bossest Black & Decker nail bloody gun. So nailed that sometimes you will misfile it. This can lead to hallucinations.

For example last year, on first hearing their mighty single May The Forth, I recall thinking aye - that was really well bloody good. But later the same day, the chorus still in my head as I happened to put the song on again, stupid brain said wow, didn't realise they did covers - but that sure was one fantastic classic. Shut up, stupid brain! You're out of your depth. You've pulled this trick on me before, telling me the music from that Comet ad was another legendary 80s dance anthem, when actually it was just Badly Drawn Boy's All Possibilities (2002).

Hey I Thought This Was About FRC -
You Said Something About Sadness?

Ah yes, the sadness. Having known for this past half-year, that tonight's show would be their last ever appearance in Glasgow; tomorrow's in Edinburgh's Wee Red Bar, their last anywhere. It was a sign of the greatest affection that this loyal knot of fans, as the band took the stage tonight and a smiling Sita began "Oh well, here we are then, this is it", reacted with one voice: boo.

This warm welcome seemed entirely expected, and they brushed it off instantly. Seconds later, all were dancing to Epic New Song. Swiftly followed by Hi!, the first song they ever recorded. Oooh, meta - Retrochamps get nostalgic! A beaming Fergus Weir joined them on stage, providing chant vocals in Let's Make Out.

The gentle Isn't It Lovely showed another side of the band, who continued to inject variety into the night with everyone taking a turn at lead vocals. When Sita steps up to the mic, every inch the pop star, she owns it. Yet from Harry's showcase Speak To Me, through Carla's riotous DIY Love Song to Ceal's vocal debut Uh Oh (No Show) when she asks politely for a little more volume on her mic "just for this one song", the singing duties are passed round with that generosity, that freedom from ego, so often found in art school and music college bands, and so rarely elsewhere. Harry and Ceal even swapped guitar and bass duties toward the end.

The (New Order? Ladytron?)-styled gem You Make My Heart exhibits again that time warping magic, paradoxically at once both retro classic and brightly original. As for the peerless Jenna - like I said, Sita simply owns. She actually made eye contact with me as together we sang one of their funniest lines, "But you're so tall, and I'm Pieraccini!"

Packed into that tiny cellar, we sang all their words back to them. Poor Linda, squeezed in even closer to the deafening PA than I during May The Forth, sought in vain any conscious hint of irony as certain fans in the... mature category, not quite pulling box shapes like others half their age and size, would belt out - Watching you dance / has given me / a second chance to feel young again...

The one band member not accorded equal respect with everyone else was their beleaguered "one trick" drum machine, who showed some signs of giving out early on. Our fault, quipped Sita, running him five years on that one set of batteries. At the end of the night, I knew how he felt.

Setlist: Epic New Song, Hi!, Let's Make Out, Speak To Me, Strawberries And Vodka Shots, Count To Ten, Uh Oh (No Show), DIY Lovesong, Isn't It Lovely?, May the Forth, Jenna, You Make My Heart.

Band Wiki

Though on the night we did catch FRC's full set, we were as usual irredeemably late, missing out on the decks of Manda Rin and most of Little Eskimos. This was partly due to our driver (=me) mentally relocating The Captain's Rest, first to Bath Street, then even less helpfully to St Vincent Street, before finally giving up entirely and heading off randomly - not to mention fortunately - in the direction of Great Western Road.*

When we arrived, Carla's brother Murray Easton on the door recognised me as the band's shadow lurking, unofficial Wikipedia guy. And he must have told; for after the show, when I asked Sita to autograph my new copy of the 2CD Love And Lemonade, she mentioned that Wiki in the signing [pic]. Later too Carla and her boyfriend tried to say hello, while Linda and I raved back at them (in my case a little hoarsely) about the night's performance. Murray having left with his marker pen, I was unable to collect Carla's autograph. Desolation! We might just have to take a run through to Edinburgh tonight...

On the other hand, these perfectly retro mini-vinyl style CDs hid a beautiful sealed note from "Casio Carla" (actually she drives a big Yamaha) which, given the super-limited edition of just 75 copies, might have to do instead until we meet again. No you can't see it, it's mine. Murray did let slip a few details about the new band the girls are planning soon to form, but I'm keeping shtum about that too, at least until there's an official announcement. Their level of talent and originality is just shocking; it can't happen too soon. And that goes for you too, Harry Weeks!

More photos from the gig: https://picasaweb.google.com/johnmkerr/FRCcaptainsrestApr82011# by Linda Kerr.
Free to use under the Creative Commons Attribution-ShareAlike 3.0 Unported licence.

* Wow, eight adverbs counting "first". Candidate for worst sentence ever written!

[Update: 9 Apr 2011]

Ultimate Retrochamps: The Disbanding

Ten o'clock on a soft Glasgow April evening. Forty miles to the east, FRC play the final tumultuous chord of their ultimate show (our last ever show ever!), and Saturday night curfew sounds in Edinburgh's Wee Red Bar. Meanwhile back here, forty miles in the west, a sad duty calls. Wikipedia won't update itself:

FRCs ~~are~~ were...
~~Current~~ Members...
2006 - ~~present~~ 2011...

Farewell, you Futuristic Retro Champions. When you quit, you were still - in the words of Manda Rin - the best new band in Scotland.

[Update: 12 Apr 2011]

Check out Murray's account of that whole weekend: http://musicinglasgow.blogspot.com/2011/04/futuristic-retro-champions-last-weekend.html.