[prev in list] [next in list] [prev in thread] [next in thread] 

List:       sqlite-users
Subject:    Re: [sqlite] MC/DC coverage explained wrong in the home page?
From:       Richard Hipp <drh () sqlite ! org>
Date:       2011-09-24 1:17:43
Message-ID: CALwJ=Mx7s5FdU5BohVkZyYhfJXuRGe=xUr-9dtAZ-mvrRtHFtA () mail ! gmail ! com
[Download RAW message or body]

On Fri, Sep 23, 2011 at 5:57 PM, Sami Liedes <sliedes@cc.hut.fi> wrote:

> [Note: In case my explanations are not clear enough, there's a fairly
>  formal position paper by Certification Authorities Software Team
>  (CAST-10) clarifying MC/DC here:
>
>
> http://www.faa.gov/aircraft/air_cert/design_approvals/air_software/cast/cast_papers/media/cast-10.pdf
> ]
>

Quoting from the above paper:

----------------------
1. Structural coverage guidelines are:
  a) Every statement in the program has been invoked at least once;
  b) Every point of entry and exit in the program has been invoked at least
once;
  c) Every control statement (i.e., branchpoint) in the program has taken
all possible outcomes (i.e., branches) at least once;
  d) Every non-constant Boolean expression in the program has evaluated to
both a True and a False result;
  e) Every non-constant condition in a Boolean expression in the program has
evaluated to both a True and a False result;
  f) Every non-constant condition in a Boolean expression in the program has
been shown to independently affect that expression's outcome.
2. Based upon these definitions:
  • Statement Coverage requires (a) only
  • DC requires (b, c, d)
  • MC/DC requires (b, c, d, e, f)
----------------------

The object-code branch coverage testing of SQLite clearly fulfills
guidelines a, b, c, d, and e.  The question at hand is does 100% branch
coverage fulfill f in a short-circuit language such as C/C++.  Note that the
paper above completely ignores this issue.  It is as if the authors had
never heard of short-circuit evaluation.  Or, perhaps they are familiar with
the problem but could not reach agreement on its solution so simply didn't
bring it up.

(NB:  The paper above uses "branch" in the context of source code.  A source
code branch might involve multiple conditions.  When SQLite claims 100%
branch test coverage, it is using "branch" in the context of object code,
where there is exactly one branch per condition.  It is important to
distinguish between these two entirely different meanings of the word
"branch".)

My claim is that in a short-circuit language, guideline e implies guideline
f.  In other words, if all boolean operators are short-circuited, then
obtaining e automatically means that you also obtain f.

But who knows what the FAA really wants.  I've discussed this problem
informally with DERs but I have never put SQLite through a formal review.
If and when that happens, and if guideline f becomes an issue, I may have to
add additional test cases.  But for now, I think I will continue to claim
MC/DC coverage.



>
> On Fri, Sep 23, 2011 at 02:05:40PM -0400, Richard Hipp wrote:
> > For case (1), since B is uncomputable, we can deem it to be true.  Then
> > since case (3) has a different outcome from cases (1) and (2), we do show
> > that each term is independent of the other.  The fact that B is deemed
> true
> > in case (1) might raise eyebrows, but in a shortcutting language, that's
> the
> > best you can do, I think.
>
> Yes, that reasoning makes sense. But even allowing for that doesn't in
> all cases satisfy the fourth MC/DC criterion. It does for the simple
> (A && B) case, but consider a more complex expression,
>
> ((A && B) || (C && D)):
>
> Now the truth table (with "_" as possibly uncomputable) would be
>
>      A  B  C  D   branch taken
> (1)   0  _  0  _   F
> (2)   0  _  1  0   F
> (3)   0  _  1  1   T
> (4)   1  0  0  _   F
> (5)   1  0  1  0   F
> (6)   1  0  1  1   T
> (7)   1  1  _  _   T
>
> So using your approach, that is the plain Condition/Decision Coverage,
> I believe these test cases would suffice:
>
>      A  B  C  D   branch taken
> (1)   0  _  0  _   F
> (2)   0  _  1  0   F
> (6)   1  0  1  1   T
> (7)   1  1  _  _   T
>
> This satisfies all three plain C/DC criteria:
>
> (a) Every point of entry and exit in the program has been invoked at
>    least once -- does not apply to this if statement
>
> (b) Every condition in a decision in the program has taken all
>    possible outcomes at least once -- A is tested by (1,6), B by
>    (6,7), C by (1,2), D by (2,6)
>
> (c) every decision in the program has taken all possible outcomes at
>    least once -- false branch taken in (1), false branch in (6)
>
> But this is not sufficient for the fourth criterion of MC/DC (quoting
> from Wikipedia):
>
> (d) Each condition has been shown to affect that decision outcome
>     independently. A condition is shown to affect a decision’s outcome
>    independently by varying just that condition while holding fixed
>    all other possible conditions.
>
> This criterion is satisfied for only for condition A (by 1;7), but not
> for B (6;7 would if the branches taken were different), C (1;2 would
> if the branches taken were different) or D.
>
> Note that the "affects outcome" requirement really forces us to
> consider the branch taken alongside with the conditions taken.
> Short-circuiting operators are really mostly an orthogonal concern to
> this. You simply cannot do MC/DC analysis without considering the
> branch taken in conjunction with the values taken by the conditions.
>
>        Sami
> _______________________________________________
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>



-- 
D. Richard Hipp
drh@sqlite.org
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

[prev in list] [next in list] [prev in thread] [next in thread]