Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

(I imagine this would be a good interview question, but in my case it's more pragmatic than that.)

We have a large & complex application that models an extremely long and sophisticated chemical reaction process between dozens of chemical components. We are at the stage of designing Acceptance Tests for the application, but we are somewhat daunted by the intractable number of possible paths to test. It occurred to me that our situation is very much like what the Google Maps dev team must have faced when it came time to test the route-planning algorithm in their "Get Directions" feature. Obviously they couldn't test (verify and validate) every possible route. So how did they get confidence that their application would work in every situation?

And since I don't expect to find out how they did it, let me ask you: How would you go about designing a test suite with adequate code coverage, to satisfy yourself that a given application is robust -- when it is literally impossible to probe every potential path through the system?

What I'm looking for are the principles that you would use to break down an intractable problem into smaller, tractable pieces, the sum of which provide a satisfactory estimate of the whole: "I can't test everything, but I can test this, this and this -- and that's enough." I'm not looking for an approach that is "provably correct", but rather one that is prudent, given real-world budget/time constraints.

(I'm using the Google maps example as something of a foil to solicit answers that are as specific as possible.)

share|improve this question
    
Google Maps in the past has tried to direct me onto bus only streets, the wrong way down one-way streets, and to make turns at intersections that don't exist (e.g. a flyover with only an offramp). I believe they have a "report incorrect directions" feature, but that's probably not something that would work in your situation. The answer to the bit about them testing everything? They didn't, and they didn't really need to. –  jozzas Aug 12 '12 at 23:31
    
As always with this kind of question, I recommend that you read Nassim Nicholas Taleb's books and articles. Here's a technical article that gets into the math but I highly recommend reading his books. –  jfrankcarr Aug 12 '12 at 23:57
    
I don't believe you can design a test that covers all cases for something that is sufficiently complex. If you know how the insides work you can come up with tests for every obvious path but there will always be things nobody ever thought of. You just think of as many as you can and hope the ones you miss aren't too big a problem. –  Loren Pechtel Aug 13 '12 at 2:49
2  
@jozzas: Everything you are describing is database errors, not actually a problem with Google's direction algorithm. An equivalent would be this morning my satnav tried to direct me down an unmaintained road. On the other hand, when it gave me a lane closure advisory about a road I was about to leave that's an actual bug. (The advisory obviously only looks at the road you're on, not the route it's following.) –  Loren Pechtel Aug 13 '12 at 2:53
1  
Call it "Beta". Done. Tis the Google way. –  Paystey Aug 13 '12 at 15:36

3 Answers 3

up vote 10 down vote accepted

I worked in the car navigation field over a decade ago.

Step A) Use a reference package and select a large sample set, run A/B tests. Not looking for exactness, looking for outliers - The reference set showed Reroute 1234 as 10.34km, and we calculated 123.5km.

Step B) - Refine our software and the reference software - Add more samples and reduce the tolerances.

Step C) - In house testing using local knowledge across global data sets.

Step D) UAT... "User Acceptance Test" As in "Sell this stuff and see what the customers complain about the most"

If you ever used mapping products circa Mid 1990's - 2000, you know what I mean, those of us that did still check the turn by turn directions every time.

Back to you example question. What you are being asked is how to prove that a piece of software is correct. If you want mathematical proof, it's been shown it can be done - for simple software at a price that exceeds any realistic budgets, for a complex software package, well, that is still research.... NASA has models for writing highly reliable software within economically manageable prices, as do DoD and the aviation industry - although still much higher than most are willing to pay. In the end, it comes down to how much are you prepared to pay.....

Edit : I just re-read you OP. It seems what you are looking for is a quick and cheap way to Test the quality of a complex piece of software. You cannot test in quality. You need to have a robust process so you know that what is built works correctly. If you have got to thinking about how to prove it's correct and you already have a the "large and complex application", you are too late.

share|improve this answer

We're one of Google's competitors. Our answer? Basically two.

First, we do calculate the complete address-to-address solution. Yup, that's a big matrix. Even worse, we do so for all times of day, all days of the week. There's sufficient similarity in the input domain to cache intermediate results, which makes the problem tractable. Still, try to get a bulk rate on harddisks.

Note that this offline calculation is done using a different algorithm. It uses far more memory than the algorithm we intend to test, but not linearly more (i.e. it uses less than 1000 times more memory when calulating a thousand routes).

Secondly, participating users provide us with real-world results. We validate millions of routes driven. Are the actual routes as fast as predicted?

And sure, you do find bugs that way. All the times. E.g. a stretch of road that's bounded on both sides by a "local traffic only zone" *. There's only one way ;) that you're going to find that in testing, and that's when you plan a route to that particular road.

* A "local traffic only zone" may only be used when you're starting or ending a route in such a zone. The stretch in the middle is therefore disconnected from the main roadnetwork. This is either a zoning or a map fault.

share|improve this answer

It's not like google writes separate code for every pair of addresses in the world. With the exception of heuristics that kick in at a larger scale, the algorithm for a 3-leg journey is exactly the same as for a 3000-leg. You thoroughly test the shorter paths and use induction to show the testing applies to longer paths as well.

You pick a healthy sample of real-world routes, and check it against what a human comes up with. You pay a lot of attention to end user feedback in your first releases, and make it easy for them to provide it. You test the boundary conditions, like if the best route actually requires traveling away from the destination for a while, or if the shortest route by distance has 18 turns compared to a more direct route that's slightly longer. You do negative testing, like if you're trying to drive from California to Hawaii, and make sure clever easter eggs are in place.

share|improve this answer
    
I'm sure everything you have suggested is accurate, but I can't help but feel that it still not adequately rigorous. "Picking a healthy sample of routes" sounds more like what I might do for a college term project, than what a world-class development team would devise. And while I agree with your observation about the 3-leg vs 3000-leg routes, testing even a large fraction of the 3-leg routes still seems quite ambitious. I feel that we are still missing something fundamental here. –  kmote Aug 13 '12 at 4:19
    
@kmote: "but I can't help but feel that it still not adequately rigorous" Why not, its worked for the software industry for a generation, and there no real sign that it is about to be superseded anytime soon. We get paid to write code that makes money, not to write code that is perfect. Come to think of it' its whats used in Medicine, Engineering and virtually all professions and it seems to do those industries adequately well. –  mattnz Aug 13 '12 at 4:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.