Unit Testing Unconstrained Input

Having just sat through a demonstration of a formal methods (property-checking) tool for hardware designers, I was thinking about one of their examples and wondering how I would code UnitTests for it in a software implementation.

The problem is very simple: recognize an input sequence and unlock a door when the sequence is matched. This is very easy to test. So then we add the second requirement: the door is not unlocked unless the correct input sequence is presented. This is a bit harder to test with dynamic test-by-example approaches like UnitTests.

Would anyone care to give it a go? To keep life interesting, imagine the input sequence contains 10 decimal digits.

I think it's safe to assume that this type of problem (indeed, any security problem) can only be solved by static analysis of the code. To what extent can/should UnitTesting be replaced by static analysis? Has anyone used XP with formal proofs? Eiffel users? -- DaveWhipp

Never, ever say "replace" in regarded to such different beasts. Testing (including but not limited to unit testing) and static analysis complement each other.

People are fond of looking for a single ultimate answer, but in practice, nothing is an ultimate solution, so it will always behoove us to use multi-pronged approaches.

An advocate of producing informal proofs of code before the code is written (compare with CodeUnitTestFirst and NeverWriteaLineOfCodeWithoutaFailingTest) noted that no UnitTest advocates had replied to this since 2002/05/31. Unfortunately, the comment was undated. The following discussion ensued ...

Wouldn't the testing depend on your level of concern with the second requirement? I mean, it seems pretty simple to write a test to make sure that the correct code unlocks the door. The only thing is you wouldn't want to write a test to successively try all 10-digit numbers and make sure they fail would you? But do you really need to verify that? Isn't it enough to say that it "fails" for all other values?

I think people have different and often mismatched expectation for UnitTest. They've been suffering quite a lot of hype and are therefore overrated. UnitTest are quite often statistically good enough to steer developers away from whatever nonsense they like to bring unto themselves, but they are not a foolproof quality assurance tool. It is entirely possible that code that passes all the UnitTests is crappy code with lots of bugs. UnitTest are written by developers, after all. If developers can produce bugs in the software, they can also produce lousy/irrelevant/ineffective tests. UnitTests should be used mostly internally for getting developer's confidence rather than as a conclusive indication of software quality. -- CostinCozianu

I had a bizarre experience of that once. Management got into a methodology craze, and insisted on highly formalizing everything, including a hash table I'd written - to make sure it was reusable by other projects; their intentions were good.

So, we did a design review on that working hash table (I had a UnitTest for it). Philosophical fault was found with it, it was redesigned by committee, I documented its interface and its externals in detail, reimplemented it in a big hurry because all this was taking so much time, the documentation and code was reviewed with a fine tooth comb, and it was reintegrated into the code that used it, with the UnitTest and the IntegrationTest passing. Ironically, it was never reused and the company went out of business a few months later, but that's not the moral...

No, the funny thing is, I dragged it out next time I needed a hash table a few years later, and the damn thing was severely broken, with both implementation and design flaws. Since it had been reviewed so carefully, I had bought into the delusion that it was high quality, but actually what happened was that I let the reviewers and redesign committee do all the thinking, out of unconscious laziness, so I didn't notice all the problems - and it passed all the tests. On the previous system. By sheer luck. The UnitTest flagged failure in every possible way on the new architecture.

I took away several morals from that, one of them being that UnitTests certainly can pass fundamentally broken code. Another is that testing is no substitute for thinking. There are more.

Gee. I wrote a program like this a few weeks ago. The application was a control signal sequence decoder in a voice-over-ip application. I got a variety of signals from the hardware driver, signals like carrier-detected and digit-decoded, to which I added millisecond level timing. I was about to design a state machine to detect the cases I was looking for, but I had this nasty feeling that I wouldn't get it right and that I would never know. So instead I encoded the event stream as a character string, adding blanks at specific inter-event intervals, and pattern matched against the result. This divided my testing problem into two parts: showing that event sequences produced the expected strings, and showing that my patterns matched only the desired ones. Two easy jobs. -- WardCunningham

I don't understand how that solves the original trial. Can you elucidate? -- EricHodges

I think it is extremely easy. Just submit your program to a sizeable set of random data. This should get you going with the development and steer you away from some obvious mistakes. Of course, that won't prove that your code does not suffer from bugs, but no UnitTest ever will. You also have to actively seek tests with peculiar (rather than random data) because sometimes program will work perfectly on randomized data and fail on real life data. Any good book on software testing will discuss these issues at some length. -- CostinCozianu

Systems that support tracking what percentage of BasicBlock?s have been executed during testing are helpful in this regard; it is sobering to see that extremely extensive tests may actually only hit 30% of all possible code paths, without even considering combinations of paths.

UnitTests work best with constrained input, especially in relation to why they're used in TestDrivenDevelopment. Formally proving code is much better if requirements, such as security, require proof that not only does the code do things under certain situations but that it doesn't do them under all other situations.

So I say to myself, "Self, to the implementation, the test sure looks like an implementation."

By which I mean, what happens if you have several implementations which are broken in interesting ways, which the test must fail in order to pass? This gives you the opportunity to describe known failure cases which the tests must consistently catch; i.e., an implementation known to be vulnerable to a buffer-overflow, an implementation known to fail in a corner case, etc.

I think this might also get around the issue that, even if you write the unit tests which handle all the corner cases correctly for the implementation, a lot of those tests may look to be arbitrarily repeated with minor unimportant changes; in my own experience, when I come back to my own tests months later and see such weirdness, I find it difficult to keep those tests around. At the very least, it creates a working example of the issue at hand, and a very obvious place to document the issue (as opposed to writing a paragraph with each test explaining why that test is important without being able to see the implementation that is being discussed).

-- WilliamUnderwood

One Solution

This problem is a simple state machine. The testing solution is to decompose the problem and this decomposition would probably have occurred naturally if TestFirstDesign had been used.

The state machine requires a sequence of N matches to Open. For each step, there are two possible results, either advance to the next stage or fall back to stage 0. This mechanism can be rigorously tested simply by cycling through all possible single inputs, though at this level one is really only validating the language's equality comparator. For most applications, one case verifying each of the logic branches is sufficient.

It is by applying the concept of UnitTesting that this becomes feasible. Low level pieces are rigorously tested so that when they are combined, that portion does not need to be retested. One need only ensure that the lower level components are being used and rigorously test the new functionality applied by the next higher level.