Oct 2, 2010

Has the bug really been fixed? (ICSE 2010) - A short review

This paper defines and formalizes the Bad Fix Problem, as per studies developers spend 50-80 % of their time fixing bugs. Many of these bug fixes themselves are a) sources of new bugs and b) do not fix the original bug for all inputs. The authors formalize these two notions as Coverage and Disruption.


Coverage of the fix measures the extent to which the fix correctly handles all the bug triggering inputs

And Disruption of a fix counts the deviations from the program’s intended behaviour introduced by a fix.

Hence for a given fix, the Bad Fix Problem is to determine the coverage and disruption of the fix.

The approach taken to calculate the Coverage for the fix is based on Distance Bounded Weakest Precondition (WP). In order to mitigate the path-explosion problem of WP the authors calculate the WP for a subset of paths near a distinguished path in the interprocedural control flow graph (ICFG).  The distance measure they use for nearness is the Levenshtein distance (which represents the minimum number of add/delete/substitutes required to change a string to another). The concrete path induced by the known bug triggering input is used as the distinguished path for calculating the Distance Bounded WP.

Once we have the distance bounded WP the coverage of a fix is determined by executing the Program symbolically using the WP and deriving a Post Condition (eliminating non-input variables from the clause).  For a buggy input the output of the program violates an assertion (say A) now if the post condition implies A then the fix is valid in terms of the coverage or else we report a counter example as a new bug triggering input.
The violations in disruption are defined by the test suite. So if the new Program runs on standard regression test cases as well as on a random subset of inputs we claim the fix valid and every test case failure is a disruption.

The authors implement this approach in a tool for the java language (FIXATION). The empirical evaluation shows that fixation is able to identify the known bad fixes in the code in reasonable time. The path explosion problem of WP is avoided by using a distance measure for calculating WP. The authors show that the analysis is able to scale for increasing values of distance “d”.

One of the limitations of this approach can be that it models the bugs as assertion failures and it relies on assertions being available or inferred. Also determining the value of distance “d” to obtain a better results is still a problem the papers suggests that the user start with a small value and increment it as more paths are explored. The possible future application of this approach can be in unit testing where the tool can directly work with the self contained assertions in a unit test case.


  1. Gu, Zhongxian, et al. "Has the bug really been fixed?." Software Engineering, 2010 ACM/IEEE 32nd International Conference on. Vol. 1. IEEE, 2010.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.