Local DUAs and exceptions for fault localization

[Alex-128]

Hi again!

I've continued working with BA-DUA for my project and I'm very happy with it, but I did realize there are two issues, namely that DUAs within one basic block are not tracked, and that DUAs that trigger an exception aren't marked as covered.

I did some research before coming here, and from the description in your original paper on BA-DUA (An efficient bitwise algorithm for intra-procedural data-flow testing coverage), it seems that only DUAs with a path from the def basic block and the use basic block are tracked. I'm curious as to why this is so? Was this purely a design choice, or was there another reason? I feel that tracking DUAs in the same basic block would add more information, such as in the worked example in your paper, where the faulty data-flow is the def and use of i in basic block 1. It also doesn't feel like it would be too difficult to implement, since such a DUA would be covered as soon as its definition line is executed. I was wondering whether you have any fixes for this, but since the Jaguar paper notes it as a limitation, I would guess not. If you have some advice for adjusting BA-DUA for this purpose (I assume during the instrumentation process), I would very much appreciate it.

The other issue, which the Jaguar paper also mentions, is exceptions. This feels like a more tricky issue to solve, but I would also appreciate advice if you have any.

Kind regards
Alexandra

[andrioli]

Okay let me try to respond these tricky questions.

Let me start with the easiest ones: local DUAs.

namely that DUAs within one basic block are not tracked

This is true!

it seems that only DUAs with a path from the def basic block and the use basic block are tracked. I'm curious as to why this is so? Was this purely a design choice, or was there another reason?

This was by design. But why? Because we don't need to track each individual DUA and because local DUA a trivial to track.

I feel that tracking DUAs in the same basic block would add more information, such as in the worked example in your paper, where the faulty data-flow is the def and use of i in basic block 1.

Definitely true

It also doesn't feel like it would be too difficult to implement, since such a DUA would be covered as soon as its definition line is executed.

This is basically why I said they are trivial to track. Assuming that all instructions of a basic block are always executed given the first instructions is reach, to track local DUAs we just need to track if the basic block was reach, reducing the problem to control-flow coverage. But due to exception flow, this assumptions could not be held.

We are also studying DUAs subsumption. A global DUA can subsumes a local DUA. So no need to track each individual local DUA.

I was wondering whether you have any fixes for this, but since the Jaguar paper notes it as a limitation, I would guess not. If you have some advice for adjusting BA-DUA for this purpose (I assume during the instrumentation process), I would very much appreciate it.

We didn't implemented support for local DUAs. As I said before, this was a design choice, but maybe, in the future, we will include this on BA-DUA.

If you want to implement it, my suggestions is to track which basic blocks were covered, and then on report phase, detect witch local DUAs were covered by simply verifying local DUAs within a basic block.

As always, contributions are welcome, I'll be happy to review this if you open a merge request to BA-DUA repository.

Regarding exceptions, they are more tricky, I'll need some time to elaborate a more complete response, but we already support them somehow (in an optimistic way). In the meanwhile you can review BA-DUA's validation tests on exceptions: [1], [2], [3] and [4].

[Alex-128]

Thanks for the reply! I will look into this.

[andrioli]

I did a POC a long time ago to support local duas (https://github.com/saeg/ba-dua/tree/local-duas). But I was not happy with the code, so I didn't integrate it to mainline.

[andrioli]

And note that, since you integrated local-duas branch on version 0.8 in your local repository, you probably don't need the option -Dbadua.experimental.exception_handler=true as this feature is enabled by default on latest versions.

[andrioli]

@Alex-128 I did a quick workaround on the local-duas branch. See commit 5ae1aba.

I didn't tested with the Chart bug 26, but at least the BA-DUA unit tests are still green.

Can you test if those changes will fix the problem to you ?

If so, I'll start to design a definitive implementation to support local DUAs.

[Alex-128]

Thank you, I just tested and it does work for Chart 26! Interestingly enough, it ranks the faulty DUA (1191,1192,owner), which triggers the NullPointerException, as more suspicious than the DUAs that have the "faulty" line 1192 as def. I'm unsure if that was intentional on your side, but whatever works :) Thanks again for all your effort, you have helped me so much!

[andrioli]

I'm glad it worked.

Interestingly enough, it ranks the faulty DUA (1191,1192,owner), which triggers the NullPointerException, as more suspicious than the DUAs that have the "faulty" line 1192 as def. I'm unsure if that was intentional on your side

I think this is the correct behavior, since the bug occurs in the use of the variable with value null.

next weeks I'll try to integrate this feature to the mainline definitely. I'll appreciate any feedback.

[Alex-128]

I would be happy to give feedback. Thank you for all the help, once again!

[andrioli]

So, just to be clear, since BA-DUA monitor the DUAs on an optimistic way, in case of exceptions, some DUAs that were not covered may be marked as covered.