Prev: DecimalFormat
Next: Rapid development of desktop-like web apps
From: Peter Duniho on 29 Jul 2010 19:18
Joshua Cranmer wrote:
> [...]
> Instead, the simplest thing to do is to write enough tests such that all
> execution paths can be covered. Basically, find a few examples of common
> cases and use every corner case you can think of--null parameters,
> 0-length arrays, etc.

Noting, however, that those are two different goals. Many bugs relate
to execution paths that don't even exist, and in fact those are often
also related to corner/boundary cases.

Test code should definitely exercise all code execution paths. But it
needs to go beyond that in terms of coverage criteria; the test code
should in fact be designed to cover the range of possible inputs, not
the range of inputs anticipated by the developer.

Pete
From: Joshua Cranmer on 31 Jul 2010 14:27
On 07/31/2010 12:51 PM, Stefan Ram wrote:
> So you can prove the operator �&� for booleans by testing
> false&false, false&true, true&false, and true&true.

Well, this works if you have the implicit assumption that there is no
reliance on other state. I suppose you could say that the test can turn
into a proof of correctness if you know that it covers all of the
possible cases for the implementation.

> However, one can not prove Math.pow(double,double) in
> this way. (Think of the Pentium bug.)

If you know the algorithm, you can reduce it to categories and then
prove all categories correct. If you change the algorithm, though, the
test is no longer necessarily complete test coverage.

Actually, I have had to struggle with finding representative tests of a
program when you have no knowledge of how it is implemented (i.e.,
writing an autograder). That was when I discovered that most people
don't know how to thoroughly test their own code to find problems such
as a really common one brought about by implicit type conversion.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
From: Alan Gutierrez on 31 Jul 2010 17:53
Stefan Ram wrote:
> Joshua Cranmer <Pidgeot18(a)verizon.invalid> writes:
>> To quote Dijkstra, "Testing cannot prove the absence of bugs, they can
>> only prove the presence of bugs."

> Well, actually, a malign programmer could have implemented
> �bool&bool� to give false results only around midnight or
> only between 2010-07-31T18:47:24+02:00 and
> 2010-07-31T18:47:26+02:00 or only if there is a certain file
> in the current directory or only if the source file contains
> a certain comment. So, even testing once for false&false,
> false&true, true&false, and true&true does not prove the
> correct implementation of �bool&bool� for all environments.

I believe I'd make an exception for Byzantine fault tolerance.

Does that help define the concept? I'd like to be able to argue that my
program is at least as trustworthy as the platform on which it runs.

--
Alan Gutierrez - alan(a)blogometer.com - http://twitter.com/bigeasy
From: Alan Gutierrez on 31 Jul 2010 21:36
Joshua Cranmer wrote:
> On 07/31/2010 12:51 PM, Stefan Ram wrote:
>
>> However, one can not prove Math.pow(double,double) in
>> this way. (Think of the Pentium bug.)
>
> If you know the algorithm, you can reduce it to categories and then
> prove all categories correct. If you change the algorithm, though, the
> test is no longer necessarily complete test coverage.

> Actually, I have had to struggle with finding representative tests of a
> program when you have no knowledge of how it is implemented (i.e.,
> writing an autograder).

I'm not sure how you'd go about testing without source code and coverage
tools. I can imagine that you could investigate an implementation, using
a test framework, but I wouldn't have too much confidence in tests that
I wrote solely against an interface.

> That was when I discovered that most people
> don't know how to thoroughly test their own code to find problems such
> as a really common one brought about by implicit type conversion.

Which would that be? Curious. I'm probably one of the people that
doesn't know how to test for it.

--
Alan Gutierrez - alan(a)blogometer.com - http://twitter.com/bigeasy
From: Alan Gutierrez on 31 Jul 2010 22:03
Tom Anderson wrote:
> On Thu, 29 Jul 2010, Lew wrote:
>
>> On 07/29/2010 12:39 AM, Alan Gutierrez wrote:
>>
>>> I'm working on implementing a B+tree and I'd like to be a little more
>>> rigorous with testing than I have in the past. What I'd like to do is
>>> write tests that prove the validity of the algorithm.
>>>
>>> The algorithm works, mind you, but I don't feel like I can prove it. I
>>> want than a bug stomping test suite. I want tests that capture the
>>> reasoning behind the algorithm. Ideally I could point you to these tests
>>> and you could see a proof. You could find fault in the reasoning or else
>>> gain confidence in the implementation.
>>
>> Tests don't give a formal proof. They just show that certain cases
>> produce expected results.
>
> True. I think what Alan is getting at is more 'testing as argument' than
> 'testing as proof'. For instance, if i was going to write such tests for
> an implementation of quicksort, i might write tests like:
>
> // i have an isTrivialCase to weed out arrays that don't need sorting
> isTrivialCaseReturnsTrueForLengthZeroArray
> isTrivialCaseReturnsTrueForLengthOneArray
> isTrivialCaseReturnsFalseForLongerArrays // test 2, 3, 100

> At each step, i test one of the invariants which are the building blocks
> of the proof of correctness. The tests aren't a proof, but they help
> illustrate the proof - and check that my implementation conforms to the it.

Yes. I mean testing as argument, with the intent of persuading adopters
of the code that code is of a certain quality, as well as persuading myself.

I don't mean to get into a discussion about the Halting problem, nor do
I mean to assert through testing that the software will never fail under
any condition. I did however run across the field of formal verification
in my research on this topic.

CMU - Specification and Verification Center

http://www.cs.cmu.edu/~svc/

Verifying an Operating System Kernel

http://ertos.nicta.com.au/publications/papers/Klein_NEH_07.pdf

That would be overreach for me at this point.

Indeed, I'd like to structure testing so that another programmer can see
my reasoning, step though the logic for an aspect of the implementation,
feel confident that it is correct or else tell me what I might be
missing. If someone can understand that I am trying to show that
`partitionLeavesTheArrayPartitionedAroundThePivot` they are going to be
in a better position to find the edge case and show me that I'm wrong.

The JUnit FAQ has this algorithm:

becomeTimidAndTestEverything
while writingTheSameThingOverAndOverAgain
becomeMoreAggressive
writeFewerTests
writeTestsForMoreInterestingCases
if getBurnedByStupidDefect
feelStupid
becomeTimidAndTestEverything
end
end

I don't see it as aggressive versus timid. I have no problem getting the
100% line and branch coverage, because I favor testing, and any best
practice that makes something impossible to test is rejected in favor of
that which is testable.

I'd like to see it as persuasive and communicative.

So I'm wondering how to structure testing to convey reasoning and
instill confidence. Seeing a bunch of unit tests named ticket81930(),
ticket81931(), ticket81932() doesn't really instill confidence because
you just see bug squashing, but no reasoning.

Anyway, thanks to Tom for the detailed response. Maybe that is all there
is to it, create a well documented JUnit `TestCase` with comments and
meaningful method names.

--
Alan Gutierrez - alan(a)blogometer.com - http://twitter.com/bigeasy
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: DecimalFormat
Next: Rapid development of desktop-like web apps