No one will argue against the benefits of testing as well as you reasonably can. Testing is often good enough to reach the level of confidence you want for code.
But you are simply /wrong/ to think that non-exhaustive testing can somehow "prove" that code works.
And there are some classes of problem for which testing is extremely unlikely to identify the problem. In particular, for anything involving race conditions or timing, you cannot /test/ your way to working code. You have to write the code correctly in the first place, because the chances of spotting the microsecond window of disaster in your lab testing is tiny. (I am not saying you need to formally prove the code - again, this is all about appropriate balances of time and effort - but testing does not help.)
Analysis is much easier when you have restrictions on what can happen. In a pure functional programming language, your function takes some input and works solely on that input, and the only effect of the code is to generate the output. That means you can analyse it in isolation. In general C code, your function might use or change global state - it all quickly becomes a lot more complicated.
OK. If you figure it out, we can take it up again - otherwise I think any replies I'd make would add to the confusion (mine, yours, or everyone else's).
If you know the possible origin of race conditions, you can actually detect them using faked versions of selected functions in an API. It still doesn't prove anything, and I'm not sure how often it is cost effective, but it is worth being aware of the possibility.
We've done it on one legacy project I've worked on. The system is database-heavy, and has a high risk of problems due to race-conditions on database modifications. We created a modified version of the database API implementation, where we easily can inject what will appear as competing modifications of the database from other processes. It doesn't find all the problems, but it easily reveals to worst blunders.
I am pretty sure you can do similar things in other cases - like file system interactions - but I'm not sure how often it is worth the effort. Maybe such a modified test implementation should be distributed with all libraries, where there is a serious risk of race-conditions in using the API. On the other hand, if you know that much, when you create a library, you might as well try to write the API so it (to the extent possible) lets the user avoid race-conditions completely.
Greetings,
Jacob
--
"I remember being impressed with Ada because you could write
an infinite loop without a faked up condition. The idea
being that in Ada the typical infinite loop would normally
be terminated by detonation." -- Larry Wall
That's a interesting idea. I have done something a little similar when tracing timing problems. Basically, if your problem occurs when event A happens during processing B, then stick a big slow loop in the middle of B and the crash becomes far more likely. (Tests can't prove your code has no bugs - but they /can/ prove your code /does/ have bugs, and can be helpful in finding them.)
As you probably know, several static-analysis tools have the ability to detect possible race conditions, as accesses to unprotected shared variables from two or more threads/tasks.
I have used the AdaControl tool for this (and other) analysis of Ada code, and found real race conditions.
The tool-based race-condition analyses are most likely imperfect (for example, because shared variables are accessed via pointers), but nevertheless useful.
"Proof" isn't that interesting outside of certain contexts. By "proof" I mean fully formal verification that it's 100% known to be correct.
We want to find a break-even variation on that. We want the cost and the risk to be commensurate.
Turns out, just measuring the risk is pretty hard.
Not in harness, but you can prove out the approach being used as a demonstration and reasoning tool. And it depend on the problem - you might be able to generate test vectors that get darned close.
You point is probably "yes, but how close?" :) And it's a good one.
As an example, I had a "one producer/one consumer" buffer. I wasn't
100% sure if it needed semaphores - one producer, one consumer, right?
I thought about it a bit , built a driver loop and was able to prove that I did indeed need semaphores. To be fair, I was leaning that way anyway.
Maybe it's bias from seeing stuff online, but I get the feeling that many people ( and I'm pretty sure you, David, are not one of them ) just sort of despair of the whole thing.
You said it man. :)
But the thing you must learn with C is how to constrain the use of global state.
And for functional - in C.A.R. Tony Hoare's lecture on "The Billion Dollar Mistake", a guy stands up at the end with the message "Haskell is all fun and games until you invoke the I/O monad" :)
It would be - in my opinion, we're obligated to do everything within our power to get things as close to correct as possible. And, for some reason, there isn't that much taught about how to do this, so we're probably on our own. But the fact remains that we must do this.
This begins with design to provide information to help determine that things work as expected. It continues with spending time on frameworks, whether built or bought, to help check things.
There was a threading library I read about which had a debug/trace version you could link with. It recorded all thread scheduling based on its synchronisation primitives. If you hit an error case, you could replay the same test case and it would replay the exact same scheduling decisions for you, so you could debug the cause of the error. Presumably when a thread asked for a resource that was available (but which wasn't on the faulty run) it would block the thread until the correct sequence was able to be continued.
I never used it, but that seems like a really good idea.
If you can detect problems via static analysis tools, that is always good - finding them early means you can fix them early.
Another way to avoid some kinds of problems is through smart use of programming languages. C++ "tag" classes are useful here - you can use them to make some kinds of multitasking errors into type errors. For example, suppose you have two locks - A and B - and want to be sure that you can't take lock "B" unless you also have lock "A". Calls to function "foo" should only be done when you have lock "A", and calls to function "bar" should only be when you have lock "B".
You can make an class "GotLockA" whose constructor acquires lock A and whose destructor releases it. This class can actually be empty - it does not have any values. (It is /not/ a wrapper around lock objects - it is a type for a /particular/ lock.) Function foo then takes a parameter of type GotLockA (it doesn't do anything with the parameter) - and now any code that tries to call "foo" without holding lock A is a compile time error. Similarly, you make a class GotLockB whose constructor requires a GotLockA instance and acquires lock B. You can then only call "bar" if you've got lock B, which also implies you have lock A.
There is work to be done deciding about copying and moving these classes. But the principle is that you match the dynamic, run-time state of locks to static scope and types.
Hopefully everyone reading this thread knows what the author's misunderstanding is here. Yet we have all seen code written this way.
How much testing do you need before you are likely to catch a problem here?
If the timer is run at 1000 Hz, you'll get a 16-bit overflow once per minute. If you have something like a 10 MHz msp430 processor, you've got maybe a 0.2 microsecond window where there is a danger while reading the counter. Perhaps you read 100 times a second. That means you spend
1/50,000 of your time in the danger zone. So every minute, you have a
1/50,0000 chance of a disaster. If my sums are right, you'll have a 50% chance of trouble after about 35,000 minutes - or 24 days. And that's assuming the problem is immediately obvious.
You are /never/ going to catch this in any practical lab testing. But if you sell 10,000 units, it /will/ occur in live installations.
So how close is your testing at showing the code is good? Absolutely useless.
This is not an unrealistic example. And you don't even need something this unlikely. Boeing made engine controllers that failed if they ran for something like 600 days without a restart - no one could spot that problem in testing. Microsoft's Win 95 crashed reliably after 49 days when a 32-bit millisecond counter overran - it took /ten years/ to spot the problem, despite the huge numbers of systems in use.
There are things in code that you simply have to get right - you /cannot/ test that they are cocrect. (As others have said, you might catch them with static analysis tools.)
Simplification of your structures and interactions can make it vastly easier to figure out what is correct and what is not.
I am certainly not in despair! I am merely concerned when people apparently think that good testing is all they need to be sure their code works correctly.
That is the challenge with functional programming languages - for real life code, you usually need some state!
Agreed.
These points are true in themselves - but miss 90% of the more important issues. If you leave the paragraph so unfinished, it gives entirely the wrong impression.
And for another example, consider the Patriot missile failure:
formatting link
The other significant problem is developing good tests is /at least/ as difficult as developing the application.
It is hard enough to get developers to write tests that adequately test "happy days" (?daze?) normal operation. Getting them to develop good tests for fault conditions is more difficult.
Hell, many times they don't even /conceive/ of failure modes, and /actively/ argue "that can't happen, the framework takes care of it". Oh, so the framework has solved the Byzantine General's problem, has it? And too many other examples.
That's just not the customer's job! It's rather called (good) analysis: replied again the developer, though conscious of the decades of relentless demolition campaigns of analysis to begin with... i.e. of the very premise for doing any job properly (and for taking responsibility for results).
If that's your main problem, you haven't seen nearly enough...
Excellent example. It's the sort of thing we would hope would be covered in an undergraduate's section on semaphores.
Oh, I think either of us could devise a mechanism to test it :)
I attribute those to "the fog of war". If anyone had been afforded the time to think about them properly, they would have found them ( by inspection ) but the phone rings, you have meetings, yadda yadd.
Very much so.
Oh, I didn't consider you to be in despair. Others, however, seem to be.
I expect that anything beyond those quite general statements would require more domain-specific information.
Unfortunately in the real world... I've been unpleasantly surprised by some of the people that were hired before my time.
Indeed, but that presumes the possibility is understood. And that's becoming more difficult where people "design" via stackexchange+cut'n'paste for the framework du jour (and du project).
And if the tests show a "green light", that is taken as proving it is working. Seriously :(
XP/Agile leaves it up to the customer to decide whether there is time. Guess what happens next?
/How/ would you test for this occurring, in a way that does not imply enough understanding to know how to write the code so that the problem never occurs?
There is no point in knowing how to test for a bug that you would never have written in the first place.
Well. We are human, so we may occassionally make mistakes. (I have enough experience to know that I can make errors I never really would make.) There is also the matter of protecting the construct against later (incorrect) modification.
Greetings,
Jacob
--
"make it easy for folks to make changes that remain consistent
with the documentation and discourage them from those changes
that would result in the comments being invalidated"
Oh, we can all make mistakes. But some mistakes are easier to avoid than others.
I can appreciate that some programmers don't realise that "volatile" does not mean "atomic", and will - as in my example - not realise that reading a 32-bit value on a 16-bit cpu is not atomic. (Even on a 32-bit cpu, changing the value is unlikely to be atomic - but in the example, the change was safe.)
And people can make mistakes even when they /do/ know about such things
- perhaps code was ported from a 32-bit system to a 16-bit system, or the type was originally 16-bit and later changed to 32-bit.
However, I find it hard to believe that someone would know a good way to test for such mistakes in the code without also knowing how to avoid them - or that someone would think that this variable needs a test, without also thinking that this variable needs to be read more carefully.
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.