Types of semantic bugs, logic errors [closed]
- by C-Otto
I am a PhD student and currently focus on automatically finding instances of new types of bugs in (Java) programs that cannot be found by existing tools like FindBugs. The existing tool currently is used to prove/disprove termination of (Java) programs.
I have some ideas (see below), but I could need more input from you (experienced programmers, potential users of my tool). What kind of bugs do you wish to find? What types of bugs exist and might be suitable for my analysis?
One strength of the approach I use is detailled information about the heap. So in contrast to FindBugs, I can work with knowledge of the form "variable x and variable y are disjoint on the heap" or "variable z is not cyclic". It is also possible to see if a method might have side effects (and if so, which variables may/may not be affected by it).
Example 1:
Vacuous call:
Graph graphOne = createGraph();
Graph graphTwo = createGraph();
Node source = graphTwo.getRootNode();
for (Node n : graphOne.getNodes()) {
if (areConnected(source, n)) {
graphTwo.addNode(n);
}
}
Imagine createGraph() creates a fresh graph, so that graphOne and graphTwo are disjoint on the heap. Then, because source is taken from graphTwo instead of graphOne, the call to areConnected always returns false.
In this situation I could find out that the call areConnected is useless (because it does not have any side effect and the return value always is false) which helps finding the real bug (taking source from the wrong graph). For this the information that x and y are disjoint (because graphOne and graphTwo are disjoint) is crucial.
This bug is related to calling x.equals(y) where x and y are objects of different classes. In this scenario, most implementations of equals() always return false, which most likely is not the intended result. FindBugs already finds this bug (hardcoded to equals(), semantics of implementation is not checked).
Example 2: Useless code:
someCode();
while (something()) {
yetMoreSomething();
}
moreCode();
In the case that the loop (so the code in something() and yetMoreSomething()) does not modify anything visible outside the loop, it does not make sense to run this code - the program has the same behaviour as someCode(); moreCode() (i.e., without the loop).
To find this out, one needs detailled information about the side effects of the (possibly useless) code. If I can prove that the code does not have any side effect that can be observed afterwards (in the example: in moreCode() or later), then the code indeed is useless.
Of course, here Input/Output of any form must be seen as a side effect, so that a System.out.println(...) is not considered useless.
Example 3: Ignored return value:
Instead of x = foo(); and making use of x, the method is called without storing the result: foo();. If the method does not have any side effect, its invocation is useless and can be dropped. Most likely, the bug here is that the returned value should have been used. Here, too, detailled information about side effects are needed.
Can you think of similar types of bugs that might be detected (only) with detailled information about the heap, side effects, semantics of called methods, ...?
Did you encounter bugs related to the ones shown below in "real life"?
By the way, the tool is AProVE and Java related publications can be found on my homepage.
Thanks a lot,
Carsten
