ASSERT-KTH / xPerturb

perturbation analysis, correctness attraction and randomization, by KTH Royal Institute of Technology
https://hal.archives-ouvertes.fr/hal-01378523/file/correctness-attraction.pdf
7 stars 5 forks source link

getting 100% success rate incorrectly #10

Closed arameskandari closed 5 years ago

arameskandari commented 6 years ago

for numerical values i++ we get 100% success rate when running correction analysis. this tells us that this point should be an anti-fragile point, which is obviously wrong

danglotb commented 6 years ago

Hi @arameskandari

which is obviously wrong

How do you know that? Do you have an example?

arameskandari commented 6 years ago

Hi @danglotb , Yes sorry I can see now that I was a bit unclear.

I have a few examples because we have run tests on a few sorting algorithms that all has a bunch of for-loops, and for every algorithm I have gotten 100% success rate for numerical incrementing variables in a for loop.

One example I can give is from BubbleSort. I have attached a picture of the BubbleSortInstr.java-file that shows that point 6 and 13 are i++ and j++, these are included in two nestled for loops for int i=0; i<arraylength; i++, and the same for j. I have also attached a picture of the file called IntegerAddOne.CallExplorer.analysis.graph.data, as you can see both points 6 and 13 have 100% success rate, and this is the same for all algorithms with incrementing for loops.

The strange thing is that when I did the PONE manually, so when I manually changed i++ to i = i+2, the oracle gave me "false". This means it's not a fault of the oracle, so I'm not sure why it's happening.

EDIT: I also posted a picture of the original BubbleSort-code that we used, if you want to look at line 9 and 10 where the for loops are.

screen shot 2018-04-28 at 14 18 00 screen shot 2018-04-28 at 14 18 35 screen shot 2018-04-28 at 14 32 06
danglotb commented 6 years ago

The fact is, that when you perturb i++, let's say, p(1, i++), it not equivalent to the manual perturbation you propose.

In fact here, we perturb the returned value by i++ and not i itself.

So, the perturbation is not changing the value of i.

Example: int x = p(1, i++), here the value inside x is being perturbed, while the value of i is not.

In one hand, we could try to have two perturbation point rather than one with p(1, p(2, i)++) for instance, but I think this is not compilable.

In the other hand, we could modify all the increment ++ (and also decrement of course) to have explicit assignment, i.e. i = i + 1, but we must think about the order, post or pre increment/decrement.

arameskandari commented 6 years ago

Ok so I have probably misunderstood what the perturbation does in the incrementing case. What kind of perturbation is happening for the BubbleSort I posted a picture of when it says 100% success rate for i++ on line 9 and j++ on line 10? Is there some kind of returned value that is being incremented here? Because the for loop doesn't return any value.