3
$\begingroup$

I have an ordered set of $M$ software modules compiled together. The interaction of some $N$-tuple of these modules is causing a bug when the program is run.

I can run the program with any desired subset of the modules enabled/disabled, so I can test the program by running it with a certain subset of modules enabled and seeing whether it crashes or not (call that "a test"). I would like to identify which $N$ modules are causing this issue with the minimal number of tests. Assume that any particular test will lead to a crash if and only if it includes all of the $N$ problematic modules (and possibly others; but at least those $N$).

$N$ is known ahead of time.

For $N=1$, I can efficiently identify the culprit in $\log_2(M)$ tests by binary search.

For other values of $N$, what approach can I take to identify the $N$ culprits?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ @mappu, thanks for the explanation. I've edited the question accordingly. I think with this extra explanation it is fine. It is just that this is a specific, unusual setting, so it is better to specify those assumptions explicitly. I've edited the question to do so -- I think it's fine now. $\endgroup$ – D.W.♦ Jun 27 '14 at 23:26
4
$\begingroup$

Now that the question has been edited to make it clearer what you are asking, there is a simple and elegant answer. The solution is: delta debugging. Delta debugging solves exactly this problem.

Let me elaborate.

Problem statement

I am interpreting your question as asking about the following problem:

  • We have $M$ software modules, and some way to run the program in a way where only a subset of them are active (and we can choose the subset freely).

  • There is a subset $S$ of $N$ of the modules. There's a fault that is triggered whenever we run the program with all of those modules active. In other words, if the set of active modules is a superset of $S$, a fault will occur; otherwise, no fault will occur.

  • The fault is perfectly reproducible and detectable.

  • Now, we want to find the set $S$ using as few tests (invocations of the program) as possible.

Solution: delta debugging

Delta debugging will solve this problem. If you have $M$ software modules, and some subset of $N$ of them are responsible for the fault, delta debugging can find the minimal subset that trigger the fault.

Delta debugging works by starting with all of the modules active, and gradually removing some of them. It picks out some chunk of modules, and tries running the program with those modules inactive. If the fault still occurs, then we know that none of them are responsible for the fault, so they can be permanently deactivated in all future tests. Delta debugging starts with large chunks, and gradually reduces the chunk size: it first tries deactivating the first $M/2$ modules, then deactivating the second $M/2$ modules; if neither of those offers any progress, then it tries deactivating the first $M/4$ modules, then the second $M/4$ modules, then the third $M/4$ modules, and then the last $M/4$ modules; then it moves on to chunks of size $M/8$; and so on.

For more details, allow me to point you to a nice description of delta debugging.

Delta debugging is efficient

Delta debugging is expected to take about $O(N \lg M)$ tests, to find the subset.

You might notice how this is a nice generalization of binary search. When $N=1$, binary search needs $O(\lg M)$ tests, just as delta debugging does. The difference is that delta debugging also scales nicely when $N>1$.

You might also notice that this is close to optimum. We can prove a $\Omega(N \lg(M/N))$ lower bound (roughly). In particular, there are ${M \choose N}$ possibilities for the subset $S$, and each test provides one bit of information (either it triggers a fault or not), so it is easy to see that we need at least $\lg {M \choose N}$ tests. Now

$$\lg {M \choose N} \approx \lg (M^N/N!) \approx N \lg M - N \log N \approx N \lg M - 0.7 N \lg N \ge N (\lg M - \lg N).$$

Therefore, delta debugging is approximately asymptotically optimal, in terms of the number of tests required.

For a more detailed performance analysis, see this analysis by Jesse Ruderman.

Discussion

That said, I am somewhat skeptical of whether this will be useful in practice. A crucial assumption here is that you could run the program with a chosen subset of its modules active, and the rest artificially deactivated. I don't see how to do that in practice. Therefore, I do not see how this can be applied in practice.

I suspect your theoretical model of the problem probably needs to be adjusted, but since you didn't tell us anything about your particular application setting or the justification for your model, I don't have enough information to specify how to fix the model.

Typically, delta debugging is used for a different purpose. Normally, delta debugging is used to reduce the size of the test case (not the size of the program). Say you have a test case with $M$ lines that crashes your program, but only a subset of $N$ of the lines are actually necessary to trigger the crash (the rest are all irrelevant), and you want to find the minimal subset of lines needed. In other words, given a long complex test case that crashes your program, you want to "minimize" it: to find a smaller, shortest test case that also crashes the program -- because small test cases usually make the debugging process easier. Then delta debugging can be used to solve that problem; in fact, that's what it was invented for, and what it's most commonly used for.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the pointer, this approach would work efficiently and with no additional storage. It doesn't at all use the fact that N is known ahead of time, which makes me suspect it requires more tests compared with my approach - i may come back with a performance simulation. $\endgroup$ – mappu Jun 26 '14 at 6:06
  • $\begingroup$ I think simply by insisting on the fixed chunk offsets, it's very easy to find a worst-case for this algorithm. Mine always requires the minimum $log_2 \binom{M}{N}$ tests. However the storage requirement for combinations may prove prohibitive for certain problems, in which case this may be a better solution. $\endgroup$ – mappu Jun 26 '14 at 6:23
  • $\begingroup$ @mappu, that's right, this is a "typical-case" analysis. If you are worried about adversarial cases, there are straightforward techniques to deal with that (e.g., randomly permute the blocks first, then do delta debugging), but in practice those techniques don't seem to be needed, and in fact the structure found in real programs means that often the algorithm does even better than a typical-case/worst-case analysis would suggest. You mention "your" algorithm, but you don't actually list an algorithm in your answer, as I mentioned in my comments there. $\endgroup$ – D.W.♦ Jun 26 '14 at 14:18
  • $\begingroup$ Forgive my naiveness, but I am missing a point. If some modules cause bugs, that means that they are actually used by your software. So how can you test the software without these modules. Are you assuming that modules are fully independent and that you can replace any of them by an older version supposed to be reliable? $\endgroup$ – babou Jun 27 '14 at 8:12
  • $\begingroup$ @babou, yes, exactly! That is the point I was trying to make in my "discussion" section at the end of my answer. I find the assumptions in the question extremely dubious, but am doing my best to answer the question on its own terms, even though I suspect that the question doesn't make sense. In other words, I agree with you. Anyway, I think your comment is really a question to the author of the question, not to me (I did see the earlier copy of the comment that you posted under the question). $\endgroup$ – D.W.♦ Jun 27 '14 at 16:16
1
$\begingroup$

The answer depends upon whether you are interested in this as a theoretical exercise or if you have a practical problem to solve.

The theory

There are tons of theory papers written about how to select a set of such tests. The standard catchphrase is "combinatorial testing". You should easily be able to find tons and tons of research papers, white papers, tools, and written material explaining the approach. It is known in the literature how to design tests that involve the minimum number of tests possible. See also "pairwise testing", which is basically the special case where $N=2$.

Incidentally, it is not correct that for $N=1$, $O(\lg M)$ tests suffice. Typically, $N$ tests will be needed, since all you have is an oracle that says "found the bug" or "that wasn't the bug". Binary search can only be applied if you have a way to also get ordering information (e.g., "the bug is in a higher-numbered component"), which usually isn't available in software testing.

A practical perspective

Don't get too caught up in the theory. The practical value of these methods is dubious.

A short summary of the research literature is: the fancy methods don't perform much better than random testing. Combinatorial test design gives at most an $N$ reduction in the number of tests, compared to random/exhaustive testing. Since $N$ is usually small (e.g., $N=2$), this is a small improvement. (When $N$ is large, you usually can't use exhaustive combinatorial testing anyway, since there are too many combinations.) And combinatorial testing is complicated, whereas random testing is very easy to implement. Usually, generating a few extra test cases isn't that hard. Therefore, the extra developer time and effort needed to implement combinatorial testing often isn't worth it. Generating test cases is cheap; but developer time is expensive. So, in most software development settings, combinatorial testing just isn't a win in most cases.

Pragmatically, it's often better to just generate random tests, use them to find reproducible failures, and debug from there.

Also, you shouldn't assume that the world will be so clean as your model indicates. Let's say the bug involves modules D and Q. It doesn't necessarily mean that any input that activates modules D and Q will necessarily find the bug; typically, there are other complex conditions. Also, usually obtaining full coverage of even a single module is quite challenging, so the premises of the theoretical model tend not to fit the real world very well.

More resources

See, e.g., the following questions on the Software Quality Assurance & Testing StackExchange site:

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Although the oracle is boolean, the set is ordered, so of course you can do it in log_2(M) tests - run one test with the first half of the modules, check for pass/fail, narrow in on half of that as necessary. I guess it's not strictly binary search, but the same principle. $\endgroup$ – mappu Jun 24 '14 at 5:25
-1
$\begingroup$

The problematic set of modules is an $N$-tuple. Checking every distinct $N$-tuple would take $\binom{M}{N}$ tests (an upper bound).

You can do binary search on the union of $N$-tuples, which takes $\log_2 \binom{M}{N}$ tests - at the expense of some temporary storage to hold the tuples.

This reduces the problem to the $N=1$ case in the problem statement.

Aside:

(It can be done in $M$ tests even for unknown $N$ by leaving all modules enabled, and running $M$ tests each with one module disabled.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't think your "Second improvement" answers the question. You don't say how to do binary search on the union of $N$-tuples. It's not that easy. That's a lower bound on the number of tests needed, but you haven't described a constructive algorithm that meets that lower bound. The other answers are far slower than need be; see my answer for a much more efficient solution. $\endgroup$ – D.W.♦ Jun 25 '14 at 18:40
  • $\begingroup$ The search is "that easy" - one of the constructed N-tuples is exactly the problematic tuple. By testing unions of N-tuples, the problem is reduced to the N=1 case given in the question statement. $\endgroup$ – mappu Jun 26 '14 at 5:50
  • $\begingroup$ Again, I think you are fooling yourself. It's not that easy. I suggest you try writing out the algorithm. Binary search requires a total order, and an oracle to answer questions "is your secret number $\le x$". It's not clear how to obtain both of those simultaneously, for the situation where $N>1$. What's your total order? How would you implement the oracle? You have not presented an algorithm, and until you try to write one down, I don't think you will be able to appreciate the issues here. $\endgroup$ – D.W.♦ Jun 26 '14 at 14:21
  • 1
    $\begingroup$ You know what? I started to implement my approach, and of course the oracle is not sufficient to distinguish whether to search the left- or right- hand half set if both half sets contain the problem. Searching both halves changes the complexity analysis to worse than your approach, which i realise now is much better (i.e. should actually work). I appreciate your patience with this! $\endgroup$ – mappu Jun 27 '14 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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