SQLite and Testing

Categorical claims are often the source of faulty statements. "Don't test with SQLLite [sic] when you use Postgres in Production"  by Robellard is a fantastic example. I actually agree with a variant of this statement: "If you need high levels of assurance, don't test with SQLite alone when you use Postgres in production."

Robellard bases his claim on several points, noting that "SQLite has different SQL semantics than Postgres," "SQLite has different bugs than Postgres," and "Postgres has way more features that SQLite." He has a couple more points, but all of these largely amount to a discrepancy between SQLite and Postgres, or between one Postgres version and another, leading to a defect. These points are a genuine concern, but his claim relies on using exactly one database back-end for testing, and exactly one risk profile for various applications.

As a quick diversion, I am not using the common definition of risk which is synonymous with chance. I am using a more stringent definition: "the effect of uncertainty on objectives" as specified in ISO Guide 73:2009. This definition often requires an assessment of both the impact and likelihood of some form of scenario to obtain a fuller picture of an "effect."

If the risk posed by defects caused by an SQLite-Postgres discrepancy is too high, then you'll likely want use Postgres as part of your testing strategy. If the risk posed is sufficiently low, then SQLite alone may be appropriate. These are predicated on the risk posed by defects, and the organisational appetite for risk.

A testing strategy comprising several different testing methodologies can often be thought of as a filter of several layers. Different layers are variously better or worse at surfacing different types of defects. Some are more likely to surface defects within components, and others are better at locating defects in the interactions between components. Other "layers" might be useful for catching other classes of defects. Each layer reduces the likelihood of a defect reaching production, which reduces the risk that defects pose. Each layer also has a cost associated with writing and maintaining that layer.

It's quite common for different layers to be run at different times. For instance, mock-based unit tests might be run very frequently by developers. This provides the developers with very quick feedback on their work. Integration tests backed by an in-memory database might be run prior to committing. These take a little longer to run and so might get run less often, but still catch most problems caused by erroneous component interactions. A continuous integration (CI) server might run integration tests backed by Postgres, and slower UI tests periodically. Finally, penetration tests might be conducted on a yearly or six-monthly basis.

This sort of process aims to allow developers the flexibility to work with confidence by providing quick feedback. However, it also provides heavier-weight checking for the increased levels of assurance required for the risk-averse organisation. An organisation with a greater appetite for risk may remove one or more of those layers, such as in-memory integration tests, to speed development. This saves them money and time but increases their exposure to risk posed by defects.

SQLite is just a tool which may be used as part of one's testing strategy. Declaring "Don't test with SQLLite [sic] when you use Postgres in Production" ignores how it may be usefully applied to reduce risk in a project. In many cases SQLite is entirely appropriate, as the situation simply does not require high levels of assurance. In other cases, it may form part of a more holistic approach along side testing against other database backends, or be removed entirely.

Not every organisation is NASA, and not every project handles secrets of national import. Most failures do not kill people. An honest assessment of the risks would ideally drive the selection of the testing strategy. Often-times this selection will be balanced against other concerns, such as time-to-market and budget. There is no silver bullet. A practical, well-rounded solution is often most appropriate.

Software Testing with Rigour

Previously, I've heard a lot about test-driven design (TDD) and why TDD is dead. Gauntlets have been thrown down, holy wars waged, and internet blood spilled.

This has resulted in widespread disaffection with TDD, and in part, some substantial disillusion with testing as a whole. I know that I suffer this; some days, I just want to cast the spear and shield of TestNG and Cobertura aside, and take up the mighty bastard-sword of SPARKAda.

I can sympathise with the feeling that testing is ineffective, that testing is a wast of time, that testing just doesn't work. When I get another bug report that the bit of code that I worked so hard to test is "just broken," I want to find the user and shake them until they conform to the code.

Clearly, assaulting end-users is not the way forwards. Unfortunately, tool support for the formal verification of Java code is also lacking in the extreme, so that route is right out too.

My own testing had been... undisciplined. Every class had a unit tests, and I even made quite a lot of integration tests. But it seemed lots of bugs were getting through.
It seems to me, that there are two things that really need to be said:

1. Testing is extremely important.
2. Creating tests up front was, at one point, basically common sense. Meyers covers this in the 1979 book, "The Art of Software Testing"

Following in Meyers' footsteps, I'd also like to make a big claim: Most people who do TDD aren't doing testing right.

TDD is often used as a substitute for program requirements, or program specification. Unfortunately, since the tests are almost always code, when a test fails, how does one really decide in a consistent way if it's the tests or the program that's broken? What if a new feature is to be worked into the code base that, on the surface looks fine, but the test suite shows it to be mutually exclusive with another feature?

Agile purists take note; a user story can work as a piece of a system's specification or requirements, depending on the level of detail in the story. If you're practicing "agile", but you don't have some way of specifying features, you actually practicing the "ad-hoc" software development methodology, and quality will likely fall.

Testing is "done right" when it is done with the intent of showing that the system is defective.

Designing Test Cases

A good test case is one which stands a high chance of exposing a defect in the system.

Unlike Meyers,  I side with Regehr on this one: Randomised testing of a system is a net good, if you have:

1. A medium or high strength oracle.
2. The time to tweak your test case generator to your system.
3. A relatively well-specified system.

If you want to add even more strength to this method, combinatorial test case generation, followed by randomised test case generation looks to be a very powerful methodology.

However, I also feel strongly that time and effort needs to be put into manually designing test cases. Specifically, designing test cases with a high degree of discipline, and the honest intent to break your code.

Meyers recommends using boundary value analysis to partition both the input domain and output range of the system, and designing test cases which exercise those boundaries, as well as representative values from each range.

Oddly, he also discusses designing test cases which will raise most coverage metrics to close to 100%, which struck me as odd; although he tempered it by using boundary value analysis to slot into the high-coverage tests. I'm not sure I can recommend that technique, as it destroys the coverage metrics as a valid proxy of testing effectiveness, and Meyers acknowledges this earlier in the book.

For a really good run down of how to apply boundary value analysis (and lots of other really interesting techniques!), I really can't do any better than referring you to Meyers' book.

Testing Oracles

Testing oracles are things which, given some system input, and the system's output, decides if that output is "wrong".

These can be hand-written expectations, or simply waiting for exceptions to appear.

The former is a form of strong oracle, the latter is a very weak oracle. If your system has a high quantity of non-trivial assertions, you've got yourself a medium-strength oracle, and can rely on that to some degree.

What To Test

Meyers and Regehr are in agreement: Testing needs to be done at many levels, though it's not as clear in Meyers' book.

Unit testing is a must on individual classes, but this is not enough. Components need to be tested with their collaborators to ensure that there are no mis-communications or mis-understandings of a unit's contract.

I guess the best way to put this across is to simply state this: unit testing and integration testing are looking for different classes of errors. It is not valid to have one without the other, and claim that you may have found a reasonable amount of errors, as there are errors which you are simply not looking for.

I, personally, am a big fan of unit testing, then bottom-up integration testing. That is, test all the modules individually, with all collaborators mocked out, then start plugging units together starting at the lowest level, culminating in the completed system.

Other methods may be more effective for you; see Meyers' book for more methods.

This method allows you to look for logic errors in individual units, and when an integration test fails, you have a good idea of what the error is, and where it lies.

How to Measure Testing Effectiveness

A test is effective if it has a high probability of finding errors. Measuring this is obviously very hard. One thing that you may need to do is work out an estimate of how buggy your code is to begin with. Meyers has a run down of some useful techniques for this.

Coverage is a reasonable proxy -- if and only if you have not produced test cases designed to maximise a coverage metric.

It would also seem that most coverage tools only measure a couple of very weak coverage metrics: statement coverage and branch coverage. I would like to see common coverage tools start offering condition coverage, multi-condition coverage, and so on.

When to Stop Testing

When the rate at which you're finding defects becomes sufficiently low.

This is actually very hard, especially in an agile or TDD house, where tests are being run constantly,  defects are patched relatively quickly with little monitoring, and all parts of development are expected to be a testing phase.

If your methodology has a testing phase, and you find that at the end of your (for example) 4 week testing window is finding more and more defects every week, don't stop. Only stop when the defect-detection rate is dropping down to an acceptable level.

If your methodology doesn't have a testing phase, this is a much harder question. You have to rely on other proxy methods of whether your testing is effective, and if you've discovered most of the defects your end users are likely to see. Good luck.

I, unfortunately, am in the latter category. I just test as effectively as I can, as I go along and hope that my personal biases aren't sinking me too badly.

Conclusion

Do testing with the intent of breaking your code, otherwise you're not testing -- you're just stroking your ego.

If possible, get a copy of Meyers' book and have a read. The edition I have access to is quite small, coming in at ~160 pages. I think that if you're serious about having a highly-effective test suite, you need to read this book.

Regehr's Udacity course, "Software Testing" is also worth a plug, as he turns out to be both very capable of effective systems testing teaching; a rare trait. Take advantage for your benefit. The course also provides a nice, more modern view on many of Meyers' techniques. His blog is also pretty darn good.

Achieving Low Defect Rates

Overview

Software defects, from null dereferences to array out of bounds and concurrency errors are a serious issue, especially in security-critical software. As such minimising defects is often a stated goal of many projects.

I am currently writing a library (OTP-Java) which provides several one-time password systems to Java applications, and this is a brief run-down of some of the steps I am taking to try to ensure that the library is as defect-free as possible. The library is not even alpha as yet. It still has several failing tests, but hopefully will be "completed" relatively soon.

Specification

Many products go forward without a specification. In many cases this is not a "bad thing" per-se, but it can make testing more difficult.

When surprising or unexpected behaviour is found, it should be classified as either a defect or simply a user without a complete understanding of the specification. With no specification, there can be so such classification. The best that can be done is to assess the behaviour and to determine if it is "wanted".

As an example, I have seen a system where one part expected a user to have access to some data, and forwarded them on to it. The system for retrieving the data had more stringent requirements, and threw a security exception. Without a clear, unambiguous specification, there's no way of telling which part of the system is in error, and hence, no immediate way to tell which part of the system should be corrected.

I would like to make it clear that I am not advocating for every system to have a large, unambiguous specification. If the product is security or safety critical,  I would argue that it is an absolute must, and many share this view. For most other systems, a specification is an additional burden that prevent a product from getting to market. If a failure of your system will sink your business or kill people, then a specification is wise. Otherwise, just listen to your users.

Defects

Given a specification, a defect is often defined simply as a deviation from that specification. Many defects are benign, and will not cause any issues in production. However, some subset of defects will lead to failures -- these are actual problems encountered by users: exception messages, lost data, incorrect data, data integrity violations and so on.

It is often seen to be most cost-effective to find and eliminate defects before deployment. Sometimes, especially in systems that do not have an unambiguous specification, this is extremely difficult to do, and in a sufficiently large system, this is often nearly impossible.

For a large enough system, it's likely that the system will interact with itself, causing emergent behaviour in the end product. These odd interactions are what make the product versatile, but also what make eliminating surprising behaviour nearly impossible, and it may even be undesired for certain products.

Static Analysis

Tools that can provide feedback on the system without running it are often invaluable. Safety critical systems are expected to go through a battery of these tools, and to have no warnings or errors.

I am using FindBugs on my OTP-Java project to try to eliminate any performance or security issues. I have found that it provides valuable feedback on my code, pointing out some potential issues.

There are also tools which will rate the cyclomatic complexity (CC) of any methods that I write. I believe that Cobertura will do this for me. This will be important, as a high CC is correlated with a high defect rate, and is also expected to make reading the code more difficult.

Testing

Randomised Testing

Fortunately, generating and verifying one-time passwords (OTPs) is a problem space where there are clear measures of success, for example, if I generate a valid OTP, I must be able to validate it. Similarly, if I generate an OTP, modify it, the result should not be valid.

This lends itself to randomised testing, where random "secrets" can be produced, and used to generate OTPs. These can then be verified or modified at will.

Other properties can also be validated, such as, requesting a 6-digit OATH OTP actually does produce a 6-digit string, and that the output is entirely composed of digits.

For the OTP-Java project, I am using the Java implementation of QuickCheck, driven by JUnit.

Unit Testing

In OTP-Java, I've augmented the randomised testing with some test vectors extracted from the relevant RFCs. These test vectors, along with the randomised tests, should provide further confidence that the code meets the specification.

Usually, unit testing only involves testing a single component or class. However, with such a small library, and with such well-defined behaviour, it makes sense to test the behaviour of several parts of the system at the same time.

In my opinion, these tests are probably too big to be called unit tests, and too small to be called integration tests, so I've just lumped them together under "unit tests". Please don't quarrel over the naming. If there's an actual name for this style of testing, I'd like to know it.

Assertive Programming

I have tried to ensure that, as far as possible, the code's invariants are annotated using assertions.


That way, when an invariant is violated under testing, the programmer (me!) is notified as soon as possible. This should help with debugging, and will hopefully avoid any doubt when a test fails as to whether it was a fluke (hardware, JVM failure, or other) or genuine failure on my part.

This has, so far, been of a lot of use in randomised testing, where there have been test failures, but determining exactly why has been shown by the assertions.

It also helps users of the library. If my input validation is not good enough, and the users subject the library to tests as part of their testing, they will also, hopefully, be helped by the assertions, as they may help explain the intent of the code.

Type System

While Java's type system does leave a lot to be desired, it is quite effective at communicating exactly what is required and may be returned from specific methods.

I have, unlike the reference implementation in the RFC (Mmm, "String key", "String crypto", and so on), tried to use appropriate types in my code, requiring a SecureRandom instead of just byte[] or even Random, to convey the fact that this is a security-critical piece of code, and one shouldn't use "any old value", as has often happened with OpenSSL's API (See also, predictable IVs) which have lead to real vulnerabilities in real products.

Shielding the user from common mistakes by the use of a "sane" or "obvious" API is as much my job as it is the final user's. The security of any product which relies on the library is formed by the library's correct specification and implementation, as well as it's correct use. Encouraging and supporting both is very important.

Code Coverage

Code coverage is often a yard-stick for how effective your testing is. Code coverage of 100% is rarely possibly. For instance, if you use Mac.getInstance("HmacSHA1"), it's nearly impossible to trigger the "NoSuchAlgorithmException".

However, many tools provide branch-coverage as well as line coverage. Achieving a high coverage can help your confidence, but when using complex decision cases (for example, if (a && b || !(c && (d || e)))), it's very hard to really be sure that you've covered all cases for "entry" into a block

Cyclomatic complexity (CC) should help here. As a rough guide, if you have a CC of 2, you should have at least 2 tests. Although, this is still just a rule of thumb, it does help me feel more confident that I've ensured that, to a reasonable level, all eventualities are accounted for.

Conclusion

Many products don't have a specification, which can make reducing surprising behaviours difficult. Similarly, not all defects lead to failures.

However, even without a specification, some of the techniques listed in this post can be applied to try to lower defect rates. I've personally found that these increase my confidence when developing, but maybe that just increases my appetite for risk.

I am by no means saying that all of the above tools and techniques must be used. Similarly, I will also not say that the above techniques will ensure that your code is defect free. All you can do is try to ensure that your defect rate is lowered. For me, I feel that the techniques and tools in this post help me to achieve that goal.

My Heart Bleeds for OpenSSL

Overview

Today has been eventful, to say that least. My colleague and I patched several services, re-issued keys for them and started the ball rolling on revocation. It took all sodding day.

The progenitor of this has caused a lot of hubris and internet opinions.

Internet Opinions

Basically, a lot of people have said a lot of things, and I'd like to address one or two of them in something more than a pithy tweet.

Dump OpenSSL

I have seen this almost everywhere I looked. The call to arms to fling out OpenSSL, or plain re-write it. I get it, I understand that OpenSSL is not the healthiest code base. I often use it as an example of an extremely unhealthy code base.

However, just because your friend is ill, doesn't mean you take them out behind the chemical sheds and shoot them.

OpenSSL has a long and "rich" history. In fact, it's got so much history, that some of it has become useful! Rewriting is almost always a mistake.

Depending on how deep we go, we could end up throwing everything away, the CA infrastructure, the cipher suite flexibility, the vast quantities of knowledge that surround the OpenSSL ecosystem and allow thousands of developers to work in a more secure manner than would otherwise be possible.

I want to cover the cipher suite flexibility quickly, just to point out how much of a fantastic idea it is. The server and client tell each other what their most-prefered ciphers are, then they agree on the strongest one that they both support.

This has massive benefits, for instance, when BEAST et. al. came along and effectively broke block cipher based OpenSSL for a while, we could jump to RC4 for a little while. When that was broke, we all hauled ass back to AES. This gives incredibly flexibility when dealing with many attacks, by simply being able to circumvent the affected parts.

Secondly, last I checked, OpenSSL still has support for DES and RC4. This allows for graceful handling of legacy clients. This is very important when you have a very large, heterogeneous installed base.

If we lost cipher suite flexibility, we'd open ourselves up to so much more Bad Stuff.

The CA Infrastructure I'm less happy with, but that's a post for another day, and, frankly, I'd be surprised if anyone seriously improved on it for your average Joe in the next 2 - 3 years. I've not looked into it much, but NameCoin, or a NameCoin-like protocol looks promising from afar.

Suddenly retraining literally tens of thousands of developers, system administrators, etc. I'm sure that will be a cheap, quick and widely accepted move. It could happen, but it's quite entrenched. I would see the move happening over several years, with what ever "comes next" supporting developers as they move from one platform to the other. In fact, it could be TLS 1.3 (I think 1.2 is the latest at the time of writing, correct me in the comments below if I'm wrong) as implemented in *drum roll* OpenSSL.

Throw Money at the Problem

I do not think OpenSSL's developers are monkeys. If you look at the project, it's effectively dying in a lot of respects. It needs more than money, it needs a huge injection of resource, people, contributions, and more than anything else, enthusiasm.

It's kinda sad that one of the most critical pieces of software to most people's lives these days has the appeal to developers of a punch right in the face.

This is mostly because the OpenSSL project is much more organic than most other projects out there -- it's grown.

I have looked at the OpenSSL code, I've tried to ... do ... things to it. It's a big and intimidating code base, and I really did not want to break anything. So much so that I abandoned my idea. I looked into the abyss, and the abyss looked into me.

An injection of cash and some good C developers on the project as their day job would make a huge dent in this. Their first job could be making the code amenable to testing and testing the result. Their second job could be adding newer, safer cipher suites, and so on. But beyond that, OpenSSL is not Java or C#. There's no benevolent banker running the show, there is only the dedication and hard work of the volunteers.

Once the project has had a good cleanup, (and probably a few bug fixes!), an audit of some sort would definitely be nice, but I think that this is of limited value. OpenSSL is a constantly evolving project. It is not the code to run a jet engine -- written once and run on well-known hardware. It's changing almost daily.

The only way to get that level of assurance would be to build an automated verification suite, or similar. I'm looking towards Frama-C, though something with more power may be required. That way, the assurances would be quite hard to break, in much the same way as introducing regression bugs is made harder by decent unit testing.

Conclusion

I feel for the OpenSSL developers, all two of them, I really do. They have come under a huge amount of fire recently. I would not be surprised if they just downed tools to go live in a cabin in the woods tomorrow, out of sheer frustration and upset. When their code works, they get no thanks, when it breaks, they never hear the end of it.

Unfortunately for some projects, it just becomes time to stop adding features, and to go and address some platform problems, to run a comb through it and straighten things out. This is often made hard by a lack of a large test suite.

We did a similar thing with our product at my day job recently. We stopped work on features for nearly 2 years to drag the system out of the dark ages, add in a real security system, upgrade the underlying technology, really improve our test suite, etc. It's painful, slow and incredibly frustrating at the time. But when you're finished, continuing to work with your product is so much easier. It stops the "Let's rewrite!" urge quite well.

Edit, 2014-04-09

There is some discussion over on Hacker News (Hello!). I'd like to address a couple of the points.

SSL/TLS /= OpenSSL

I completely agree. The reason this comes across as a point that needs to be made is that, in writing the post in the middle of the night, immediately before going to bed without hashing the ideas out right, I've managed to put issues that were solely OpenSSL's fault right next to the spec's fault.

The reason that I talk about the potential for losing things like cipher suite flexibility is that a new library would likely implement something AES & RSA based with SHA-2 or SHA-3, and leave the others for a rainy day. We need more cipher suites at our fingertips than that (and good, safe, defaults).

Beyond that, unfortunately, attacks like Lucky Thirteen were basically other attacks, but using timing information to extra data. This sort of attack is only possible with the Mac-then-Encrypt construction that SSL/TLS uses, thus being the problem with the spec. The fact that it is a timing exploit is an issue with OpenSSL. I know the bug is effectively intractable, but I'm also aware that OpenSSL has fixed it to a satisfactory level.

You can't spell

I ager.

Seriously though, while I do make an effort, it was the middle of the night and for some reason my spell checker was not red-lining. Opening up the post this morning gave me an opportunity to go through and fix these issues ;-)

OpenSSL isn't formally verified!?

No, neither is any part of your browser, your kernel, your hardware, the image rendering libraries that your browser uses, the web servers you talk to, or basically any other part of the system you use.

The closest to formally verified in your day-to-day life that you're going to get may well be the brakes on your car, or the control systems on a jet engine. I shit you not.

We live on fragile hopes and dreams.

Monoculture Leads to Mass Vulnerability

I think that this is a real problem. However, this is crypto code. I know, I know, it's still a systems problem in lots of ways, but I can't avoid the feeling of "don't roll your own."

Asking normal developers to choose between several competing libraries with different interfaces, vulnerabilities, performance characteristics, etc. would likely result in carnage. We know that developers, when asked to choose cobble together cipher primitives, are basically pants-on-heads retarded, why would they be in a position to make those kinds of decisions on a larger scale?

I that out best bet is to to ensure that OpenSSL is a rock-solid piece of software with things like automated verification, extensive testing and independent audits. Unfortunately, that's extremely expensive (don't forget, re-writing is likely more expensive).

Blogger is Awful

Yes. I am always surprised that my blog doesn't render in a browser with no JS.

Healthy Paranoia

Sometimes, I'll be coding away, make a change that I somewhat expect to break things, and nothing breaks.

Inwardly, I cheer. My test suite is perfect! It has allowed me to refactor with abandon. However, this quickly passes, and I feel the need to know if I am doing it "right", that is, I trust my intuition that it should be broken. Am I running the right version of the code? Did I restart the server to pickup my changes?

Often, I'll find that I was running an older, known-good bit of code, and that my change wasn't picked up. Once I force my changes to the local test server, I can see my changes have subtly broken something, and resume my fixing.

I like to think of this of healthy paranoia. If I've changed something that should've broken at least something, I should be looking for breakage. If none occurs, likelihood is that I've done something wrong (aside from writing bad code).