Design Article
Tell us What You Think
We want to know what you thought about this Design. Let us know by adding a comment.
Driving Blindfolded – Solving The Triage Challenge
Daniel Hansson - Verifyter
9/10/2012 10:25 AM EDT
Linear vs. binary search
The algorithms that can be used to step back and rerun a failing test on older revisions in order to find the first faulty revision are linear or binary search. The linear approach is costly as it tests all older revisions in reverse chronological order, but on the other hand the first faulty revision will be found with certainty. The binary search method is faster, where only the middle revision is tested between a passing revision and a failing revision, but it only works when you have just one bug as it requires the test results to provide directional information, whether the next revision to test should be younger or older.
If you have had two bugs introduced recently and one of the bugs has been fixed, then the binary search will not work. It will find the faulty revision of one of the bugs, but not necessarily the faulty revision of the bug which is still open. The linear approach will be able to identify the correct faulty revision, but at a higher test cost as more revisions will be tested.
In the example in Figure 2, a test fails at the latest revision, which is revision 5. An error was introduced in revision 5 which can be concluded as the test result on the previous revision, revision 4, is a pass. The linear algorithm will capture this as it will rerun the failing test on revision 4. However, the binary search algorithm will fail to find the correct faulty revision even for such a simple example. The first step in the binary search algorithm is to identify a revision in the middle of the revisions for when the test last passed and the latest failure, which in this example is revision 3. The test fails also on revision 3, which is why the binary search method continues to test revision 2, which is in the middle of this revision and the last pass. Finally the binary search algorithm concludes that the faulty revision is revision 2. It is correct that revision 2 is faulty, but what the binary search algorithm misses is that this issue has already been fixed in revision 4. Only the linear approach works in this case.
Also, if there is no known previous passing revision available, for example the first time you perform automatic triage, then binary search does not work, only linear search works.
As a conclusion, the problem with linear search is that it is not fast enough to be of practical use in large systems. The problem with binary search is that it cannot handle multiple bugs, which means it is also not of practical use in large systems.
Representative testing
This paper introduces a novel algorithm which is fast and able to handle multiple bugs and which can be used on large systems.
First, all test failures are analyzed and grouped into bugs, where each group of test failures is assumed to be caused by the same bug. The grouping takes into account test results, build characteristics, log files and historical test results provided by a test result database.
The second step is to select the best agent to represent each group of failures. The agent is selected based on the following factors:
The goal is to find agents that provide fast and robust results.
The example in Figure 3 shows a system where all tests failed on the latest revision, i.e. revision 5. Test 5 is selected as agent and the failure is diagnosed down to revision 2 which is the faulty revision. Once the faulty revision for test 5 is known, the rest of the tests are tested on revision 1 and 2 to verify that they also have started to fail here due to the faulty revision no 2. Thus the conclusion is that revision 2 is a faulty revision which caused all tests to fail and the fault has not yet been completely fixed as the diagnosis of test 5 shows. There is a chance that the fault in revision 2 was partially fixed benefiting some of tests 1-4, but that these tests then suffered from a fault that was introduced later, e.g. in revision 3 or 4. If this, less likely scenario, is true, than these bugs will be correctly diagnosed once the fault in revision 2 has been fixed. The importance is that the diagnosis of the agent is robust. As with all testing, once you have fixed an issue, more issues may be revealed later.
Once a faulty revision is found for each agent, the algorithm validates the other tests in the group whether they also have the same first faulty revision. As the algorithm validates the assumptions made during grouping, a correct result is ensured.
If any assumptions are found to be wrong then we will go back to grouping, following by selection and testing of agents and non-agents. Consequently, the better test failure grouping, the better performance, but the end-result is never affected.
Representative testing does not require a certain underlying search algorithm. Both linear and binary search algorithms may be used together with representative testing. What representative testing does is to speed up the diagnosing process to such a degree that it allows the linear search method to be used, thus providing results that are both fast and accurate.
Next: Result noise
The algorithms that can be used to step back and rerun a failing test on older revisions in order to find the first faulty revision are linear or binary search. The linear approach is costly as it tests all older revisions in reverse chronological order, but on the other hand the first faulty revision will be found with certainty. The binary search method is faster, where only the middle revision is tested between a passing revision and a failing revision, but it only works when you have just one bug as it requires the test results to provide directional information, whether the next revision to test should be younger or older.
Figure 2. Test Result Example
If you have had two bugs introduced recently and one of the bugs has been fixed, then the binary search will not work. It will find the faulty revision of one of the bugs, but not necessarily the faulty revision of the bug which is still open. The linear approach will be able to identify the correct faulty revision, but at a higher test cost as more revisions will be tested.
In the example in Figure 2, a test fails at the latest revision, which is revision 5. An error was introduced in revision 5 which can be concluded as the test result on the previous revision, revision 4, is a pass. The linear algorithm will capture this as it will rerun the failing test on revision 4. However, the binary search algorithm will fail to find the correct faulty revision even for such a simple example. The first step in the binary search algorithm is to identify a revision in the middle of the revisions for when the test last passed and the latest failure, which in this example is revision 3. The test fails also on revision 3, which is why the binary search method continues to test revision 2, which is in the middle of this revision and the last pass. Finally the binary search algorithm concludes that the faulty revision is revision 2. It is correct that revision 2 is faulty, but what the binary search algorithm misses is that this issue has already been fixed in revision 4. Only the linear approach works in this case.
Also, if there is no known previous passing revision available, for example the first time you perform automatic triage, then binary search does not work, only linear search works.
As a conclusion, the problem with linear search is that it is not fast enough to be of practical use in large systems. The problem with binary search is that it cannot handle multiple bugs, which means it is also not of practical use in large systems.
Representative testing
This paper introduces a novel algorithm which is fast and able to handle multiple bugs and which can be used on large systems.
First, all test failures are analyzed and grouped into bugs, where each group of test failures is assumed to be caused by the same bug. The grouping takes into account test results, build characteristics, log files and historical test results provided by a test result database.
The second step is to select the best agent to represent each group of failures. The agent is selected based on the following factors:
- Test and build failure pattern, e.g. do all tests fail for a specific build type or does one test fail across all build types
- Test times
- Build times
- Checkout times from the VCS
- Known bugs
- Historical test data, available in the test result database.
The goal is to find agents that provide fast and robust results.
Figure 3. Representative Testing
The example in Figure 3 shows a system where all tests failed on the latest revision, i.e. revision 5. Test 5 is selected as agent and the failure is diagnosed down to revision 2 which is the faulty revision. Once the faulty revision for test 5 is known, the rest of the tests are tested on revision 1 and 2 to verify that they also have started to fail here due to the faulty revision no 2. Thus the conclusion is that revision 2 is a faulty revision which caused all tests to fail and the fault has not yet been completely fixed as the diagnosis of test 5 shows. There is a chance that the fault in revision 2 was partially fixed benefiting some of tests 1-4, but that these tests then suffered from a fault that was introduced later, e.g. in revision 3 or 4. If this, less likely scenario, is true, than these bugs will be correctly diagnosed once the fault in revision 2 has been fixed. The importance is that the diagnosis of the agent is robust. As with all testing, once you have fixed an issue, more issues may be revealed later.
Once a faulty revision is found for each agent, the algorithm validates the other tests in the group whether they also have the same first faulty revision. As the algorithm validates the assumptions made during grouping, a correct result is ensured.
If any assumptions are found to be wrong then we will go back to grouping, following by selection and testing of agents and non-agents. Consequently, the better test failure grouping, the better performance, but the end-result is never affected.
Representative testing does not require a certain underlying search algorithm. Both linear and binary search algorithms may be used together with representative testing. What representative testing does is to speed up the diagnosing process to such a degree that it allows the linear search method to be used, thus providing results that are both fast and accurate.
Next: Result noise
|
|
|
|
|
Navigate to related information