Contrafactuals

Say It Don't Spray It

Just saw a mock up of a PowerPoint presentation for a proposed new product. Although it was thrown together in that Lorem Ipsum fashion (don't you just love his dresses?), still it was amusing how the bullet points conspired by chance to tell the diametric opposite of the truth about this baby. Economic gains? In fact this solution would be more expensive than traditional ones. Reduced paperwork? More sort of increased, actually. Environmental impact? Do this one yourself...

A Few Hypercomplex Numbers

Adam's Apples

Adam learned to count sitting at home. Various number systems occurred to him, each one seeming to answer still more new questions...

Initially the natural numbers N (1, 2, 3 and their friends) arrived, letting him answer stuff like "How many apples should I bring home, to avoid an argument?" Later, zero was added, giving him the whole numbers, and answering "How many of a surplus does that leave for unexpected guests?" Then negative numbers extended this arrangement to the integers Z; now he could keep track of apple debts as well as stocks.

Naturally, all of this led to apple shortages, as others began to stockpile; soon he was looking at puzzles like "There's just one apple, and two of us; how many apples each can we have?" Hence the concept of a new type of number, expressed as a sequence of two or more other, pre-existing numbers: the ratios, or rational numbers Q, combining for example 1 and 2 into the single new number ½. Yet still he couldn't answer posers like "What length's the diagonal of my mile-square orchard?" Adding radicals like √2 to obtain the algebraic numbers, still he would find other measurements, like the circumference of a two- or three-inch diameter apple, impossible to pin down.

R - The Reals

For once he got lucky, and defined a (real) transcendental number as anything that wasn't already on the line! Finally, he had the continuum of the real numbers R stretching from -∞ on the left, past his nose, and onward to +∞ on the right. He even learned enough about projective geometry to include ∞ itself, when context called for such extremes.

Everything after N and up to this point was an attempt to solve an ever growing set of equations; to answer an ever expanding realm of questions. Suppose that x = 1. Then some of these questions were,

• What's x - x? - Add zero; get the whole numbers.
• What's x - 2? - Add negatives; get the integers Z.
• What's x / (x+1)? - Add fractions; get the rationals Q.
• What's y, if y² = x + 1? - Add radicals; get the algebraics.
• What's an apple's circumference, if x is its diameter? - Add everything else on the line; get the reals R.

But damn, he thought, damn and stop me if you've heard this one before, but damn if it doesn't all go serpent shaped again, just as soon as I leave the familiar domain of apple accountancy! Here's one example still without an answer:

• What's x, if x² + 1 = 0?

But all of that was quite some time ago. The answer lay nearby, but in another dimension; in this next domain...

C - The Complex Numbers

Just give this elusive result a whole new name, and call it a number. The new name is i; one example of a square root of minus one. Another such example is -i. Now, since i is a number, it can be multiplied it by any real number y; so doing produces an imaginary number, iy. Also, any real number x can then be added to this new thing, making a complex number, x + iy.

This new number i has effectively generated a second copy of the real number line. The new line is conventionally shown at right angles to the original, intersecting at zero in an Argand Diagram (see figure, from Wikipedia). The two lines define a complex plane. So whereas real numbers were represented by points on a line, these newfangled complex numbers are instead points on a plane.

Complex numbers have proved to be insanely useful in various mathematical, scientific and engineering disciplines. At their basics, complex addition and multiplication are used to represent and to compose together planar transformations. For example, multiplication by i results in a 90° anticlockwise rotation. So, how about adding more dimensions? Can we solve still more equations, by adding in still more crazy so-called numbers?

H - The Quaternions

What about this situation: find p and q, where

• (pq - qp)² = -4

Obviously this equation has no solution in the real domain (where no square is negative), nor even the complex one. Multiplication of complex numbers is still commutative; for any real or complex p and q, we have (pq - qp) = 0, and that's never going to square to anything other than more zero. Yet believe it or not, if we now perform exactly the same trick as before, namely introducing a brand new square root of -1 into our system, then we can immediately find multiple solutions to this very odd equation.

The new guy is a completely independent square root of -1, distinct from both i and -i. Let's call him j. Now just as the real and imaginary lines generate the complex plane C, so too do i and j generate a plane. But multiplication in this plane is a little different from multiplication in C. To multiply i and j, you have to imagine the vector i "rotating" towards j, and by the rules of vector multiplication (the so-called cross product), generating a third vector ij orthogonal to both of these, perhaps in the direction that a right handed screw would be driven by such a rotation. But remember, the real line is already orthogonal to both i and j. This new vector ij can't be real; for then j himself would be merely imaginary to begin with, and not an entirely new kind of number after all.

No, i and j between them have to generate an entirely new direction ij, simultaneously orthogonal to both of these and to the real line. In fact this ij himself turns out to be yet another distinct square root of -1. As William Hamilton famously discovered in 1843: during the attempt to break out of two dimensions and into three, we're instead summarily deposited in the land of four! And by the preceding analogy with vector spaces, rotating in the opposite direction, notice this anticommutativity:

ji = -ij.

Numbers of the form a + bi + cj + dij (where a, b, c and d are real) are termed the quaternions, H. In general, if p and q are quaternions, then pq ≠ qp; they're not commutative.

Incidentally, don't take away the impression that these unit vectors, their products, and their negatives, are the only square roots of -1 in the new system. That may have been true in the complex domain, where only two numbers, the discrete ±i, held that distinction. But in the 3D vector subspace of the quaternions, i.e. the space remaining upon removal of the real axis, there's an uncountably infinite number of √-1. Every point on the surface of the unit sphere, a = 0, b² + c² + d² = 1, qualifies.

Returning to the equation at the head of this section, let's now set

p = i, q = j

then

(pq - qp)² = (ij - ji)² = (ij - (-ij))² = (2ij)² = 4(ij)² = 4(-1) = -4

So p = i, q = j is one solution to the very odd equation; and there are others.

Applications of the non-commutative quaternions were once much more numerous, but they have fallen out of favour, now displaced almost everywhere by matrix and vector algebras. Their one current party trick is modelling the camera in 3D computer games and other simulations, where they are less prone to the problems of interpolation and gimbal lock suffered by the alternatives. So we can at least claim them as a successful extension of the transformational complex numbers, from the plane into 3D and 4D spatial rotations (which are also non-commutative).

O - The Octonions

Now, what about this situation: find p, q and r, where

• ((pq)r - p(qr))² = -4
  

Say what you will about the non-commutative quaternions, at least those guys associated, just like the complex and the real: for any p, q and r, we had ((pq)r - p(qr)) = 0. Please struggle to contain your amazement as I reveal to you now, that by the simple expedient of adding still another independent square root of -1 to our system, we can immediately find multiple solutions to this new and extremely odd equation.

The drill is the same as before. Our new root k is orthogonal to all of i, j, ij, and the real line. So too are his uninvited pals, namely ik, jk, and ijk. That's a total of eight independent dimensions (the number doubles with every brand new √-1 added). Seven of these are imaginary, so our basis includes seven square roots of -1. The seven points and directed lines of the Fano Plane (below) offer a mnemonic to help us multiply these. Example: the central vertical line tells us that

• (jk)(ik) = ij, and (ik)(jk) = -ij;
  
• (ik)(ij) = jk, and (ij)(ik) = -jk;
  
• (ij)(jk) = ik, and (jk)(ij) = -ik; and so on.
  

The Fano Plane mnemonic for octonion multiplication

adapted from http://en.wikipedia.org/wiki/File:FanoMnemonic.PNG

The bottom line in particular makes this statement of antiassociativity:

i(jk) = -(ij)k.

Numbers of the form a + bi + cj + dij + ek + fik + gjk + hijk (where a, b, c, d, e, f, g and h are real) are termed the octonions, O. In general, if p, q and r are octonions, then (pq)r ≠ p(qr); they're not associative. Returning to the equation at the head of this section, let's now set

p = i, q = j, r = k

then

((pq)r - p(qr))² = ((ij)k - i(jk))² =(ijk + ijk)² = (2ijk)² = 4(ijk)² = 4(-1) = -4

So p = i, q = j, r = k is one solution to the extremely odd equation; and there are others.

Applications of the non-associative octonions are currently quite rare. They are useful in investigating eight-dimensional transformations in general, and 8D rotations in particular. Some mathematicians (like John Baez and Ian Stewart) have recently begun to speculate that there might be a central role for the octonions in certain advanced physical theories.

S - The Sedenions

Now, what about this situation: find p and q, where

• pq = 0, p ≠ 0, q ≠ 0.

In all of the number systems we've seen so far, if any two numbers p and q were nonzero, we could be sure that their product pq would also be nonzero; conversely, if a product was zero, then so too was at least one of its factors. But if we now add just one more square root of -1 to our evolving number system, we can immediately find multiple solutions to this new and pathologically odd equation.

Call the new root l. As usual he brings along an entourage of his pals, this time a further seven: il, jl, ijl, kl, ikl, jkl, and ijkl. So first, we need to go through the chore of working out the extension of the multiplication table from 8 to 16 dimensions. Here's the result (click for big):

The new 16-dimensional numbers are termed the sedenions, S. Notice that the top left quarter of the basis multiplication diagram contains the rules for octonions (previously shown encoded into a Fano Plane above); similarly in turn, the top left quarter of that contains the quaternions; the top left quarter of that, the complex numbers; and finally the top left quarter of that, the single cell "1", is of course the basis for the reals.

Returning to the equation at the head of this section, let's now set

p = ij + kl, q = ik + jl

then

pq = (ij + kl)(ik + jl) = ij(ik) + ij(jl) + kl(ik) + kl(jl) = -jk + il - il + jk = 0

So p = ij + kl, q = ik + jl is one solution to the pathologically odd equation; and there are others.

I'll not go into the 16-dimensional sedenions S any further - they are just a little too crazy! Technically, S and all subsequent extensions are no longer normed division algebras. There are only four of these, and we have already seen them all: they were R, C, H and O.

Incidentally, don't think of zero divisors as pathological in all number systems; it's just that they have no place in normed division algebras. For a particularly tame illustration, consider the integers modulo 12, as modelled by the numerals 0 to 11 on an analog clock face (if yours has 12 in place of 0, obviously you're not a C programmer). Define addition as clockwise progression, and multiplication as repeated addition. Then speaking modulo 12, we have

3 * 4 = 0.

Still Higher Dimensions

Just for fun, I can't resist mentioning the names of the next few algebras after S. These are:

• the 32-dimensional trigintaduonions;
• the 64-dimensional sexagintaquattuornions;
• the 128-dimensional centumduodetrigintanions; and
• the 256-dimensional ducentiquinquagintasexions.
  

In the unlikely event that any of these should darken your door again, let's hope they do so under the mercifully un-Latin alternative names proposed by Robert P.C. de Marrais and Tony Smith:

• P - the pathions, from the 32 Paths of Kabbalah;
• X - the chingons, from the 64 Hexagrams of the I Ching;
  
• U - the routons, from Route 128 of the "Massachusetts Miracle"; and
  
• V - the voudons, from the 256 deities of Voodoo's Ifa pantheon.

The number of crazy-looking equations soluble in each system also continues to rise. For example, there are nonzero routons whose squares are zero. There are nonzero voudons, having nonzero squares and cubes, yet whose fourth powers are zero. And so on.

Finally, I'd like to go on record here to propose the name austons for the next algebra in this series. Named of course for the capital city of the Lone Star State: area code 512. Sadly there's never likely to be any demand for these, as a certain Periodicity Theorem tells us that nothing new happens beyond the voudons.

Confessions

My aim in this article was to provide a contrast to the traditional presentation of these particular algebras, R, C, H, O and S, as a progression wherein "algebra gets a little bit worse with each step":

• going from R to C, the property of ordering is lost;
• going from C to H, commutativity is lost;
• going from H to O, associativity is lost;
• going from O to S, unique divisors, and our marbles, are lost.

Instead I've stressed what's gained with each step. Seeking out more and more equations to solve, building successively more powerful algebras, until eventually, there is nothing we can't do - and nothing we can!

During the exposition, I've taken various liberties with notation.

• There is in fact no consensus as to whether the set of natural or whole numbers, both, or neither, contains zero. I've arbitrarily gone with N = {1, 2, 3, ...}.
• Yes, my account of the "real line" misses completely the point of the continuum hypothesis. The reals weren't my principal target here.
  
• k has traditionally been used, since the day and hour of William Hamilton's discovery of the quaternions, to represent ij, rather than the "next" new √-1 (the generator of the octonions). I play fast and loose with these bases, coming from a background in electrical engineering. Over there we live and breathe, eat and drink complex numbers; but we defiantly (and consistently) use j in place of i.
  

There are many more exotic number systems to be found. In fact, the schemes covered in this article, the first few Cayley-Dickson algebras, these are just some of the more popular (or better known) main line stations on a network also contaning biquaternions (like quaternions, but with complex instead of real coefficients - can, open! worms, everywhere!), exterior algebras, various split and conic hypercomplex numbers, and connecting even further out to some very weird places indeed.

Tweets - February 2011

Leave the libraries alone. You don’t know the value of what you’re looking after. It is too precious to destroy. http://bit.ly/glagl5

— John Kerr (@dogbiscuituk) February 2, 2011

@frcmusic -- well?! that was more than 3 weeks ago!? -- "our album 'Love and Lemonade' is going to be a double! Details to follow next week"

— John Kerr (@dogbiscuituk) February 18, 2011

Is it Sony or is it Gaddafi? http://bit.ly/i0fVTd #sonyorgaddafi

— John Kerr (@dogbiscuituk) February 24, 2011

Security Testing Part 2 - Lab Work

Jarlsberg Turns to Gruyere

As of July 13, 2010, the Google Codelab formerly known as Jarlsberg is now called Gruyere. This training aid is a knowingly vulnerable application, which can be used to learn and understand web vulnerabilities.

http://google-gruyere.appspot.com/

This is a particularly useful experience for test engineers, since one of its main aims is to simulate the activity of penetration testing - simulating attacks from malicious sources (known as Black Hat Hackers, or occasionally Crackers). The process involves an active analysis of the system for potential vulnerabilities resulting from poor or improper system configuration, from known and unknown hardware and software flaws, or from operational weaknesses in process and/or technical countermeasures.

Gruyere is excellent at what it does, in its tutorial-structured, hint-led way. The contents sidebar is the best reference to what classes and detailed subtypes of vulnerability are covered. Cross-Site Scripting, Script Inclusion and Request Forgery (XSS, XSSI, XSRF) are particularly well served, pardon the pun. Other inclusions include: data tampering, information disclosure, denial of service, remote code execution and elevation of privilege.

For each vulnerability, you assume the role of a black hat (malicious hacker) and uncover the related exploit. One particularly well realised aspect of this Codelab is the way in which you are encouraged - just like a real world security researcher - to combine approaches of both major kinds: black box (e.g. probe it with some bad input data) and white box (e.g. read its source code).

What Can't Gruyere Do?

There are some significant omissions. For starters, any popular C/C++ attack with "overflow" in the name. Gruyere is written in Python, which by design, prevents any attempt at reading and writing outwith an array's bounds. For that reason, the popular attack known as buffer overflow is not covered by this lab. Similarly, Python prohibits integer arithmetic overflow, and so Gruyere includes no examples of integer overflow exploits.

It is important to note that these observations do not guarantee the immunity of the website from such attacks. All applications are exposed to so-called platform vulnerabilities. These can be security weaknesses in the web browser or other client side code, or in the underlying Python runtime. The lab doesn't cover such issues, even though sometimes you might avoid platform vulnerabilities by making changes to the app, so as to alter its platform dependencies, or its resource usage.

By far the biggest omission from this lab has to be SQL Injection - for the admittedly very good reason, that Gruyere does not use SQL. Again, there are plenty of well researched cases elsewhere on the web. For example this very readable account by Steve Friedl is a model of clarity.

Microsoft 's extensive and very professionally produced Security Virtual Labs are also well worth a look. This one on SQL Injection Vulnerabilities can take up to 90 minutes to complete (the standard allowance for these labs). It requires JavaScript plus "IE6 or above"; and you'll have to install an ActiveX control to connect to and run the lab.

A Note On Scope

While security testing obviously needs to be targeted on a specific set of possible exploits, given the vulnerabilities and their mitigations in the application or system under test, the umbrella undertakings of security training, and more generally education, must entertain no such restrictions.

Take Banned APIs for example. These are closely related to the subject of buffer and integer overflows described above, and to other vulnerabilities specific to code in languages like C/C++ but not found for example in managed code. Why should a Test Department dealing with C# WinForms apps care about these? - Well, it could happen at any time, that the Development Department will decide to slip some C/C++ code, or a legacy library, into the mix. Maybe to avoid injecting a .NET or Windows Shell dependency somewhere. Suddenly, your attack surface quadruples. Shouldn't you be prepared for that? Certainly, to the extent that you should immediately and instinctively be at least aware of the implications of that change.

Another example. Why worry about XSS attacks, when no such vulnerabilities can be exploited, due to the particular nature of our app? - Because tomorrow, the Marketing Department will demand that lucrative third party ads be served up in IFrames beside your primary content. Next day, you could be serving malware as blithely as the BBC. Clearly, just-in-time training is woefully inappropriate here.

Finally, here is the definitive word on the issue from Michael Howard, architect of Microsoft's Security Development Lifecycle, and principal security program manager on their Trustworthy Computing (TwC) Security team. In his article The SDL and the CWE/SANS Top 25 Most Dangerous Programming Errors 2010, he writes:

Even CWE 98, "PHP File Inclusion," is covered by the SDL in our required security training classes, which is especially remarkable when you consider that virtually no PHP code is written at Microsoft!

The reason that we address issues like PHP file inclusion in the SDL is that we don't simply wait for new vulnerability taxonomies to be released and then rush to add mitigations to our security processes; rather, we structure the SDL to provide developers with fundamentally sound, secure programming practices. As a result, we cover not just the known vulnerabilities of today (like the Top 25) but also many of the unknown vulnerabilities that will be discovered tomorrow. The fact that all of the Top 25 are addressed by the SDL is a great validation, but it is the result of the content of our process and not the cause.

Now Hack!

Once you've read the introductory material, including the warning paraphrased in red below, you can start your Gruyere adventure here:

https://google-gruyere.appspot.com/start

One final thing, do remember to concentrate exclusively on the suggested attacks. Seriously. Any deviation from the vulnerability cases which Google have expressly authorized here could have dire consequences of almost unlimited badness for you.

Previously:

Part 1 - Overview

Security Testing Part 1 - Overview

Fundamental Practices for Secure Software Development

Two weeks ago on February 8, 2011, the Software Assurance Forum for Excellence in Code (SAFECode) published the 2ND EDITION of their paper Fundamental Practices for Secure Software Development - A Guide to the Most Effective Secure Development Practices in Use Today (2MB PDF). Their stated ambition for their report (original 2008 edition) was "...to help others in the industry initiate or improve their own software assurance programs and encourage the industry-wide adoption of what we believe to be the most fundamental secure development methods."

Rather than a comprehensive guide to all possible secure development practices, their concise, actionable and pragmatic report provides a foundational set of these; a set that has been effective in improving software security in real-world implementations by SAFECode members across diverse development environments. They call these “practiced practices”, meaning they are actually employed by SAFECode members, having been identified through an ongoing analysis of members’ individual software security efforts, and are currently in use at leading software companies.

CWE References, Verification, and Resources

Before going into detail about the section dedicated to Testing Recommendations, notice that all subsections are bookended by these three bullets:

• CWE References: originally created by MITRE Corporation, Common Weakness Enumeration references provide a unified, measurable set of software weaknesses - a universal basis for an extended technical vocabulary, similar in this respect to the utility of software design patterns in development - enabling and encouraging effective discussion, description, selection and use of software security practices. By mapping their recommended practices to CWE, the authors provide a detailed illustration of the security issues these practices aim to resolve, and a precise starting point for interested parties to learn more.
• Verification: usefully, each subsection includes a list of methods and tools that can be used to verify whether a given practice was applied. This is aimed at checking whether development teams are actually following prescribed security practices!
• Resources: self explanatory; books, articles, reports, tools, tutorials, in short anything that can usefully be combined with the foregoing report text to expand on it in any way.
  

And So To Test

For security testing and verification, you'll want to head for page 39, and the section helpfully entitled Testing Recommendations. Here you're reminded more than once, that the goal of testing activities is not to add security by testing, but instead to validate the robustness and secure implementation of a product, reducing the likelihood of security bugs being released and discovered by customers and/or malicious users.

This and other preliminaries dispensed, there then follow the four subsections unique to security testing and verification recommendations:

1. Determine Attack Surface. Which is to say, understand the attack surface, with the aid of a good, up-to-date Threat Model, combined with such tools as port scanners, or Microsoft's Attack Surface Analyser; and your knowledge of all the program's inputs, determined from requirements & design, and supplemented by information about protocols and parsers as supplied by development.
2. Use Appropriate Testing Tools. Consider which fuzz testing tools, vulnerability scanners, and other resources can be mobilised to uncover programming errors, known vulnerability classes, and administrative issues. Which of these can be automated? What should be the level of exploratory testing, using say network packet analyzers, and network or web proxies that allow man-in-the-middle attacks and data manipulation?
3. Perform Fuzz / Robustness Testing. This is currently a fast changing area of automated security testing, seeing new research and advancement almost daily. Test departments are identifying software development training requirements, in spite of the growing availability of off-the-shelf fuzz testing tools for standard protocols and general use, because of custom file and network data formats used by the applications under test. Effort needs to be focused on the particular networking protocols or data formats in use, and on the high priority, high exposure entry points that have been identified during the threat modelling stage, as being available to attackers.
4. Perform Penetration Testing. Which is expensive, and is often partly or wholly outsourced to professional penetration and security assessment vendors. But an in-house penetration test resource or team can maintain a very valuable advantage, from one test to the next, based on the availability of internal product knowledge.

A Sample Agenda

These five pages 39-43 of the SAFECode report supply us with most of the headings we need to form a starting agenda for an introduction to security testing.

Concepts:

• Integrity, Availability, Confidentiality (CIA)
• Threat Modelling
• Attack Surface
• Inputs, Protocols and Parsers
• Fuzz / Robustness Testing
  

Classifications:

• Vulnerability Classes (SQL Injection, XSS)
  
• S.T.R.I.D.E.
• Common Weakness Enumeration (CWE)
  

Tools:

• Vulnerability Analyzers
• Network / Web Proxies
  
• Port Scanners
• Packet Analyzers
  

Finally...

Just to reiterate (and to paraphrase one of the report's authors, the SDL's Michael Howard), this paper's unique importance is its description of what SAFECode members are doing in practice, to raise the security bar. It is deeply pragmatic, not a theoretical or academic document. SAFECode is also actively seeking public comment on this paper, especially in the verification sections. So if you know of specific tools or techniques to help determine if a software development team is adhering to the practices, please let them know.

Auntie Beeb's Virus

BBC Music Websites Are Infectious

Did your antivirus software detect the BBC 6 Music / 1Xtra driveby?

According to this Virustotal scan, currently only 12 of the top 43 antivirus products correctly identify Tuesday's malware threat, which at the time of writing, is still actively serving up malicious executables from IFrame tags on these popular BBC streaming sites. In cases like these, the simple act of visiting a website is sufficient to cause infection.

Kaspersky did detect this threat, which is good news for us, both at work and at home. On the other hand we are far from complacent, noting among the failures such high profile names as AVG, BitDefender, McAfee (all editions), Microsoft and Sophos. All companies whom we have used, endorsed, and recommended to our customers and families, at one time or another. Today, I can't bring myself to link to them... nor obviously to those BBC music websites! Update (Feb 17): all of the above have now caught up, and the latest Virustotal figure is 23/43.

Here is the Websense Security Labs blog entry on the attack, which identifies the malware as having been authored using the still popular PEK toolset (Phoenix Exploit Kit, 2007).

Regex Tennis

Game History Validation

This example from the Universe of Regular Expressions illustrates a substantial, real world application of the "AB alphabet" type, famous from countless introductions and tutorials. But this example didn't arise at work. It came up while we were relaxing on holiday one summer, and watching Wimbledon. Suddenly I started sketching state diagrams on the backs of Embo postcards...

Suppose during a tennis match we want to record more than just game and set scores; we'd like to record the detailed sequence of points won and lost in each game. So for example, if player A won a "love game" (in which player B failed to score at all), we might record the four points that she won in this format:

AAAA

If instead she lost just one point out of five, but went on to win, then the game will be represented by one of these:

BAAAA
ABAAA
AABAA
AAABA

depending upon whether she lost the first, second, third or fourth point (she can't have lost the final fifth point, since she did win the game). Similarly if she lost two points, well, those could be any two out of the first five points. Applying binomial coefficients, "five choose two" = ten possibilities, and the game's history will be one of these:

BBAAAA
BABAAA
BAABAA
BAAABA
ABBAAA
ABABAA
ABAABA
AABBAA
AABABA
AAABBA

Now suppose we wish to validate such game histories. Can we use a Regex to determine whether a given sequence of As and Bs represents a legal game of tennis? Well, the scoring in any sport can be represented by a finite state machine, so yes, a Regex can certainly validate a game of tennis. But before proceeding, it's worth mentioning that Regex has no built-in support for permutations. That sometimes makes it the wrong tool for jobs like this one, which may have rather long solutions as a consequence. Solution sizes are exponential in the alphabet size, to be exact. Our alphabet has just two letters, so we'll persevere for now.

The examples given so far represent full, legal games. Illegal examples include such things as A, AA, AAA (these games are still in progress), or AAAAB (player A has already won the game before B "wins" that impossible final fifth point). In fact, when taken together with their opposites, i.e. the corresponding cases where B wins instead of A, the foregoing 15 cases already exhaust all 30 possibilities for what we'll call a short game (up to six points). So, by disjoining ( | ) all of the foregoing examples and their opposites, then forcing a full game match by delimiting the result with ^ and $, we can obtain a canonical pattern capable of validating all short games:

^(AAAA|BBBB|BAAAA|ABBBB|ABAAA|BABBB|...|AAABBA|BBBAAB)$

But we can also do a lot better. Here is a rough sketch of the state transition diagram for an arbitrary game. For simplicity, tiebreak games are excluded from this treatment, but aside from the game length, their analysis is essentially the same. Scoring on the diagram proceeds from left to right, except when forced back (arrows) from Adv_A or Adv_B to Deuce. The transition is upward whenever A wins the point, downward when B.

Our so-called short games correspond to all the valid paths through this diagram, from Start to Win_A or Win_B, and avoiding Deuce. It so happens that the analysis used here is better explained in a later part of this problem, so for now I'll just pull out of my hat this improved pattern, which matches all 30 (and only those) short games:

(AAAB?B?A|(AAB|ABA|BAA)(AB?A|BAA)|(ABB|BAB|BBA)AAA
|BBBA?A?B|(BBA|BAB|ABB)(BA?B|ABB)|(BAA|ABA|AAB)BBB)

Next we address the remaining long games. After six equally shared points, the score is "40-40", aka "Deuce". For either player to win the game from this point, she must score a further two consecutive points, making it therefore a game of 8 (or 10, or 12, ...) points in total. Now, applying binomials again, there are "six choose three" = twenty ways to reach this intermediate Deuce state, beginning at Start. This portion of the game history comprises 3 As and 3 Bs, intermixed in any one of these 20 possible sequences.

Divide and Conquer!

Cut the play in half. If there are 3 As in the first half, then there must be 3 Bs in the second:

AAABBB

Or if there are 2 As and a B in the first half, then the second must comprise some combination of one more A and 2 Bs:

(AAB|ABA|BAA)(ABB|BAB|BBA)

And so on. There are only four such partitions, and when we gather them together in a disjunction, we obtain the pattern matching any sequence of play from Start to Deuce:

(AAABBB|(AAB|ABA|BAA)(ABB|BAB|BBA)
|BBBAAA|(ABB|BAB|BBA)(AAB|ABA|BAA))

The long game pattern is completed by tacking on to this stem the playoff stage, in which the winner concludes with two consecutive points. This is simply any number (possibly zero) of AB or BA pairs, followed by a final AA or BB. Converting these words into symbols:

(AB|BA)*(AA|BB)

To obtain the final Regex pattern of a tennis game, take the disjunction of the patterns above for matching short and long games:

(AAAB?B?A|(AAB|ABA|BAA)(AB?A|BAA)|(ABB|BAB|BBA)AAA
|BBBA?A?B|(BBA|BAB|ABB)(BA?B|ABB)|(BAA|ABA|AAB)BBB|
(AAABBB|(AAB|ABA|BAA)(ABB|BAB|BBA)
|BBBAAA|(ABB|BAB|BBA)(AAB|ABA|BAA))(AB|BA)*(AA|BB))

An Alternative Approach

The above is a complete solution, and despite the pattern lengths involved, still a practical one, since these patterns or equivalents can easily be autogenerated. However, the autogeneration process is exactly equivalent to walking through the state diagram. If we can do that, then we already have a finite state machine capable of game history validation.

Class TennisGame below is one example of such a state machine, encoding the scoring rules of tennis games. It has a Play method which accepts one string parameter purporting to be a game history, and returns the validation result as a boolean. Any two adjacent characters can be used for the alphabet, so for example, a game history can be written as ABAAA, or equivalently, as "10111".

public enum Point
{
  Love, Fifteen, Thirty, Forty, Advantage, Win
}

public class TennisGame
{
  public bool Legal { get; private set; }
  public Point[] Score { get; private set; }

  public TennisGame()
  {
    Score = new Point[2];
    Reset();
  }

  public void Reset()
  {
    Score[0] = Score[1] = Point.Love;
    Legal = true;
  }

  public bool Play(string points)
  {
    Reset();
    foreach (var point in points)
      WinPoint(point & 1);
    return Legal && GameOver;
  }

  private void WinPoint(int player)
  {
    if (GameOver)
      Legal = false;
    switch (Score[player])
    {
      case Point.Love:
      case Point.Fifteen:
      case Point.Thirty:
        Score[player]++;
        break;
      case Point.Forty:
        switch (Score[1 - player])
        {
          case Point.Love:
          case Point.Fifteen:
          case Point.Thirty:
            Score[player] = Point.Win;
            break;
          case Point.Forty:
            Score[player] = Point.Advantage;
            break;
          case Point.Advantage:
            Score[1 - player] = Point.Forty;
            break;
          default:
            Legal = false;
            break;
        }
        break;
      case Point.Advantage:
        Score[player] = Point.Win;
        break;
      default:
        Legal = false;
        break;
    }
  }

  public bool GameOver
  {
    get { return Score[0] == Point.Win || Score[1] == Point.Win; }
  }
}

These two approaches are essentially equivalent in terms of not just the infinite set of game histories they'll validate, but also in runtime behaviour. That's because .NET converts regular expressions into finite state machines prior to execution (either at runtime, or when compiled with the RegexOptions.Compiled flag). It is left as an exercise for the student to extend both of these approaches to cover whole sets, matches and tournaments, with and without tiebreakers!