Open main menu

CDOT Wiki β

Delta debugging framework

Revision as of 20:36, 26 November 2006 by RichardChu (talk | contribs) (→‎Project News)

Project Name

Delta debugging framework

Project Description

(↑ top)

Delta debugging is an automated approach to debugging that isolates failures systematically. Given a failing test that can be mechanically verified (including a browser crash), delta debugging is a way of automatically isolating the change that introduced the failure. Having a framework in place to pull builds from CVS, bisect by date and change set (using bonsai data -- remember, CVS doesn't have changesets!), and report results would let computers make developers more productive.

Project Leader(s)

(↑ top)

Name(s) of primary people working on the project. If you want to join a project as leader, discuss with other leaders first. Include links to personal pages within wiki.

Richard Chu
Dean Woodside
Aditya Nanda Kuswanto

Project Contributor(s)

(↑ top)

Name(s) of people casually working on the project, or who have contributed significant help. Include links to personal pages within wiki.
NOTE: only Project Leader(s) should add names here. You can’t add your own name to the Contributor list.

Project Details

(↑ top)

Provides more depth than the Project Description. This is the place for technical discussions, project specs, or other details. If this gets very long, you might consider breaking this part into multiple pages and linking to them.


Based on the papers on delta debugging that I've sifted through (with From Automated Testing to Automated Debugging by Andreas Zeller being the most understandable to non-math wizards, and Yesterday, my program worked. Today, it does not. Why? also by Andreas Zeller probably being the most relevant to our project), here is an outline of my understanding of delta debugging, a summary of the concepts that must be taken into account while working on the delta debugging framework project, and an outline of the conceptual stages of developing the delta debugging framework.


Delta debugging is an algorithm that can automatically and systematically isolate/narrow down the failure-inducing circumstances that are necessary to produce the bug. Delta debugging can be applied to isolating various types of failure-inducing circumstances, including:

  • program input
  • user interaction (key presses, button presses, mouse clicks, etc.)
  • program code modification (adding / updating / deleting variables, functions, classes, etc.)


How? From my understanding, given a known bug and a known set of circumstances that can reproduce the bug, we can continually execute tests that vary the circumstances until a minimal subset of circumstances that can reproduce the bug is left. That is, for each test, a circumstance is removed, and if the bug is still present, than that circumstance can theoretically be eliminated as the cause of the bug from the set of circumstances. In this project's case, the circumstance will be certain change(s) to the program code that caused a regression in the program.


[Note: The rest of this post contains mathematical concepts that I may not fully understand but am trying to put into terms understandable to non-math wizards. A dangerous combination.]


Before we continue, here are some important terms to understand.

  • Configuration. A subset of all changes made to source code since the last known good version and the version with the regression.
  • Test. A test case or function that can determine whether a configuration contains the failure-inducing change (Fails), doesn't contain the failure-inducing change (Passes), or produces indeterminate results (possibly because of interference or inconsistency).
  • Subset. Given two sets (A and B), A is a subset of B if and only if all of the elements of set A are in set B.
  • Superset. Given two sets (A and B), B is a superset of A if and only if B contains all of the elements of A.
  • Union. Given two sets (A and B), the union of A and B contain all elements of A and B.
  • Intersection. Given two sets (A and B), the intersection of A and B are the elements that are in both A and B.


With regards to the delta debugging algorithm, we must take into account these possible concepts that may complicate it:

  • Interference. Each individual change may not cause the program to regress, but applying a combination of changes together causes the regression. Thus, there must be a method to identify the set of changes that cause the regression.
    In the case of interference, we must recursively test both halves with all changes in one half of the configuration remaining applied.
  • Inconsistency. Changes in the source code may be dependent on other changes in the source code and without them the program cannot be compiled and tested successfully. Thus, there must be a method to identify and handle dependencies (such as a dependency graph).
    [Wild, far left field thought: How can we ensure that when applying a configuration, it is consistent? Well, in the compiler process, there is a lexical analysis step which breaks the source code into tokens, then there is a dependence analysis step which produces constraints/dependencies between the tokens. Theoretically, if we can harness parts of the compilation process, we could have a method of knowing the dependencies between the changes in the source code.]
  • Granularity. A single logical change may consist of hundreds of lines of code, yet only a couple lines of the change may be responsible for the regression. Thus, There must be a method to break the change into smaller manageable chunks.
  • Monotony. If a change causes a failure, any configuration that includes this change fails as well (makes sense to me). If a configuration does not cause a failure, then all subsets of the configuration do not cause a failure, thus they can be eliminated from the change set (makes some sense to me. However, if my understanding is correct, while a subset of the configuration does not cause the failure by itself, the concept of interference suggests that the subset combined with another configuration may cause the regression).
  • Unambiguity. A failure is caused by only one configuration (No interference). Thus, for efficiency, we do not have to search the other configuration for more failure-inducing changes. Whether or not a configuration is ambiguous or unambiguous, a failure-inducing change will be produced. However, for completeness with regard to finding all failure-inducing changes, it is preferred to search both configurations.


Now that we are aware of the different concepts that we must take into account with regards to delta debugging, the next section will outline some facts and assumptions that are being made, and attempt to define the vision and process of the delta debugging framework.


Project Facts and Assumptions

(↑ top)

Project Facts:

  1. The source tree for the Mozilla project is HUGE. With many different source file types (C++, JS, XUL, etc.) in many different directories.
  2. Failure-inducing change(s) will unlikely be localized to a single directory and file. Failure-inducing change(s) may be spread across many different directories and source files.
  3. The source files could be of the same type (C++), mixed type (C++, JS), same directory, different directory. It shouldn't matter. The framework should be source type and location agnostic.
  4. The failure-inducing change(s) may not be localized to a single developer. The failure-inducing change(s) may have been caused by another developer's change(s) to a source file they were working on. That is, a single developer's source scope may not be encapsulated but interconnected and interdependent on other developers source code.
  5. The developer's current version of the source code contains the regression.
  6. The developer has a test case that can be used indicate whether the test passes/fails/is indeterminate.
  7. The developer will NOT know the date/version of the last known good version.
  8. Bonsai is a tool that can produce a list of differences between versions of a source file. (Bonsai's functionality has not been examined closely yet but will have to as it may be a key component to the framework)


OUTDATED

Possible Vision of the Delta Debugging Framework:

(subject to change based on stakeholder consultation/feedback, feasibility study)

  1. Since the last time a developer executed a test case that passed, the developer modified some source files. The source files may be of the same type or mixed type, same directory or different directory. It shouldn't matter. The framework should be source type and location agnostic. Upon executing the test case again, the result is now a failure. The developer panics. It's only days before the deadline to submit bug patches before the source tree is supposed to be closed for release and the bug is a blocker. The developer doesn't want to be shamed for delaying the release, and the source code is too complex to find the bug in time, so what should they do? Use the delta debugging framework! that's what. How? you may ask. Well keep reading to find out. * scenario may vary.
  2. The delta debugging framework may require the developer to input one piece of information. The test case/function that used to pass but now fails. It will be used to determine whether the source files with progressive changes passes/fails the test.
  3. Once the developer has inputted this piece of information, it will use Bonsai to query the source tree and compile a list of all the changes to the source files since a certain amount of time.
  4. (If there was a method of determining change dependencies so as to eliminate the possibility of inconsistencies, it would be done in this step. One possible way of reducing the possibility of inconsistencies is to logically group changes by location or check in time.)
  5. This step would be where the delta debugging algorithm would come into play. The algorithm should basically:
    1. Recursively, incrementally remove changes from the source code with the regression.
    2. Recompile the source tree.
    3. Execute the test case. There may be 3 outcomes:
      1. The test case passes. We know that the failure-inducing change(s) are in the change(s) that were removed.
      2. The test case fails. We know that the failure-inducing change(s) are not exclusively in the change(s) that were removed. I say not exclusively because of the concept of Interference (described above).
      3. The test case is indeterminate. There were some inconsistencies.

Project Flowchart

(↑ top)

The flowchart represents the simplistic version of the delta debugging algorithm. It will theoretically find a failure-inducing change set but not necessarily the minimal set or the full set of failure-inducing change(s). The algorithm is depicted as recursively linear however it could be binarily recursive. In the linear version, the theoretical maximum number of iterations (worst case scenario) is:

 

where n represents the total number of changes and r is a subset of n.

In other words, the summation of the combinations of changes without repetitions that can be made given that the size of the change set can vary from 1 to n.


Updated Delta Debugging Flowchart.


 

Here are some thoughts regarding the flowchart:

  1. The whole process revolves around a certain Test, which must be passed to complete the process. It is assumed that the source code passed this test before, but not anymore due to recent changes to the tree. The framework will locate these changes.
  2. The Test is a versatile module and can be adapted to accept any tests the user may use.
  3. When the initial test fails, the framework first attempts to locate which changeset causes this failure. This is done by "going back through time", retrieving the trees from previous revisions, and running each tree through the same test. The idea is to locate the latest revision where the test passes successfully.
  4. Once this revision is identified, the framework will extract the diff, the difference between the two revisions.
  5. The framework will then use this diff to break down the difference possibilities (e.g. directory, file, etc) and isolate the cause of the failure.
  6. Once this is done, the framework will deliver the cause of the failure in a report for the user and the operation is finished.

Project Source Repository

(↑ top)

Assuming you have SVN, the project's source can be obtained via SVN using the following command: 

svn checkout svn://cdot.senecac.on.ca/deltadbg

Project Task List

(↑ top)

Priority Legend
High Priority Medium Priority Low Priority


Status Legend
Task completed Task started but not complete Task not started


Task Description Priority Assigned to Status
Source Documentation and Licensing
Source Documentation Unsurprisingly, the source code is not thoroughly documented. Before the end of this semester, by the time the project is due to be submitted, the source code needs to be well documented. Low Nobody There is some documentation in the source files but not much. And it's not well documented.
Source License As per the requirements, the delta debugging framework will be licensed under an open source license. Which one? we don't know yet. Though, before the due date of the project, we must select one and change the source files header comments as per the selected license's requirements. Low Nobody Not started.
Unit Tests
Unit tests for the various parts of the delta debugging framework. It would be nice to have unit tests that thoroughly tests each part of the framework to ensure the correctness of the functions. It would be nice to have unit tests for each different part:
  1. Change/Changeset hierarchy of files
  2. Build-related files
  3. RCS-related files
  4. Test framework related files
  5. Delta Debugging Algorithm module
 Low Nobody There are some unit-like tests that tests parts of the framework. However, they are either not thorough or outdated.
  1. ChangesetTest.pl tests some of the functionality of the Change/Changeset hierarchy of classes. However it is not thorough and outdated.
  2. maketest.pl tests some of the functionality of the Build classes. However, it is not thorough.
  3. svntest.pl tests some of the functionality of the RCS classes. However, it is not thorough.
  4. DeltaDebuggerTest.pl tests some of the functionality of the delta debugger module. However, it is not thorough.
Change set / Change
Retrieval of Change / Change set The Granularity concept. A single revision may consist of hundreds or thousands of lines of code that were changed, yet only a couple lines of the change may be responsible for the regression. Thus, There must be a method to break the change into smaller manageable chunks. The different types of chunks we may breaking up a changeset are: Revision, Directories, Files, Code Blocks, and Lines. High Richard Chu Currently can retrieve change sets of type Revision, Directory, and File. NOT going to complete retrieval of Code Block, Line of Code change set.
Application of Change / Change set OK. Change sets can be retrieved. Now what? You must be able to apply a change or change set or subset of a change set to the source tree. Your mission is to figure out how to do that. High Richard Chu Can apply a changeset (specified by array of indices passed in) for a Revision, Directory, and File Changeset. NOT going to complete application of Code Block or Line changeset.
Unapplication of Change / Change set Changesets obviously must be able to be applied. But changesets must also be able to be unapplied. Your mission is to figure out how to do that. High Richard Chu Can unapply a changeset (specified by array of indices passed in) for a Revision, Directory, and File Changeset. NOT going to complete unapplication of Code Block or Line changeset.
GNU Make (http://www.gnu.org/software/make/)
Wrapper around the GNU make utility Mozilla uses the GNU make utility to build their source tree. your mission is to make a wrapper around the GNU make utility so that the make command can be programmatically called to build the source tree. High Richard Chu Wrapper created: makewrapper.pl. Can execute the make command with options specified by the user.
Subversion (SVN) Repository (http://subversion.tigris.org/, http://svnbook.red-bean.com/nightly/en/index.html)
Wrapper around the necessary SVN commands For the automated debugging to work, we may need to automatically modify the working copy by reverting to a different revision or updating certain directories and files. It may also need to know the differences between revisions and changesets. High Richard Chu Wrapper created: svn.pl. Currently has subroutines for commit, update, diff, and checkout commands. May need to wrap other SVN commands.
Query SVN repository for differences between two revisions Your mission is to find out the relevant commands that can return the differences between two revisions, the meta-data that is kept with each revision, how differences between two revisions are stored and formatted, and how this data can be parsed into a usable form for our project (wrapper?). High Richard Chu Done.
CVS/Mozilla Bonsai (http://www.mozilla.org/bonsai.html, CVS Book)
In my mind, Bonsai may be too bloated for our needs.
Wrapper around the necessary CVS commands For the automated debugging to work, we may need to automatically modify the working copy by reverting to a different revision or updating certain directories and files. It may also need to know the differences between revisions and changesets. Medium Dean Woodside Just starting out.
Query CVS repository for differences between two revisions Your mission is to find out the relevant commands that can return the differences between two revisions, the meta-data that is kept with each revision, how differences between two revisions are stored and formatted, and how this data can be parsed into a usable form for our project (wrapper?). Medium Dean Woodside Just starting out.
Test Case(s) (Tindexbox)
Creation / Extraction of Test Case(s) We need test cases that can return whether or not the test passes or fails. Tinderbox has a couple of tests that are executed after the source is built. Extract those tests from the Tinderbox source code so that we can use them in this project. We also need a test case that can pass/fail consistently so that we can test the delta debugger. High Aditya Nanda Kuswanto Work in progress. Found the tests! Now need to figure out how to run them and how they work.
Test Framework We ideally need a way to allow users to specify the test(s) to be run easily without them having to modify the delta debugging module. High Richard Chu Work in progress.
Obtaination of Test Repositories
Obtaination of test SVN Repository We have an SVN repository that holds our delta debugging framework source files. We need another SVN repository that we could use to test our framework. High Dean Woodside Done. The URL to the test SVN repository is: svn://cdot.senecac.on.ca/deltatest
Obtaination of test CVS Repository When the CVS version of the framework is completed, it will be useful to have a test CVS repository that we could use to test our framework. Medium Dean Woodside Work in progress. The CVS repository has been created. The web interface to the repository is: here. Apparently need to just get some forwarding issues resolved.
Implementation of Delta Debugging Algorithm (Yesterday, my program worked. Today, it does not. Why?)
The Algorithm The delta debugging algorithm. Drives the framework to retrieve change sets, apply changes, build source tree, run test case(s) to find the minimal set of failure inducing changes. The intersection of all other parts of the framework to make them work together. Ideally, should be abstract enough for easy extensibility with little impact. High Richard Chu Work in progress. Currently, it can theoretically find the failure inducing revision, and the minimal failure inducing set of directories.

Points of Confusion

(↑ top)

Bonsai issue -- unresolved


When I get confused, I draw diagrams.


 


The Clear: Seemingly Straight Forward

The RCS tree is straight forward. It will encapsulate the data and operations related to the revision control system. SVN wraps the operations of the SVN revision control system, CVS will wrap the operations of the CVS revision control system, etc.

The Build tree is straight forward. It wraps the build tool used to build the source tree.

The Blurry: Current Points of Confusion

RCS's can remember the changes (deltas) that occurred in previous versions of a file, the history of changes that occur between revisions, etc.

A Changeset and its subclasses will encapsulate the idea of a set of changes. A set of changes could be broken down into various categories such as a specific revision, a list of directories, a list of files, a list of blocks of code, and finally a line of code.

A Change and its subclasses encapsulate the idea of a single change. A change can be a change made within a directory, change made within a file, change made to block of code, or a change to a line.

A ChangesetFactory is supposed to return a change set based on the type of change set requested. To get the requested change set, one needs to know the type of revision control system (SVN, CVS, other, etc.) and/or the data required to connect to it. So there obviously need a link between RCS and ChangesetFactory/Changeset. The question is how? What is the proper/best way to link them together? One way is to pass in an RCS object to the ChangesetFactory which would then pass that object to the appropriate Changeset subclass. I don't like that solution but it's the simplest.

Also, the method to get a change set for SVN may be different from CVS. So there may be a Changeset hierarchy for SVN and another one for CVS. I don't like the idea of that at all. There must be another way.

The Blind: Future Points of Confusions

  • Applying a change in a changeset. Should the Changeset subclasses be able to do that? Are they the information expert? They know about the changes. Should they know how to apply them? How would we go abouts applying a subset of changes in a changeset? For example, there may have been changes in 10 different directories, how would we apply the changes from say 4 of the 10 directories and not the others?
  • Connecting all 3 hierarchies together. Need to be able to connect to SVN, need to be able to get and apply changes, need to be able to build the source tree.
  • The actual delta debugging algorithm.

But that's all for the future.

Project News

(↑ top)

This is where your regular updates will go. In these you should discuss the status or your work, your interactions with other members of the community (e.g., Seneca and Mozilla), problems you have encountered, etc. Put detailed technical information into the Project Details page (i.e., update it as you go), and save this section for news about participation in the project.


Nov. 26, 2006

Committed some updates to the SVN repository.

  • Updated the delta debugging algorithm module. I didn't realize this yesterday but the algorithm to find the minimal set of failure inducing files (and code block and line of code changes if those changeset types ever gets dones) is the same (with minor modifications) as the algorithm that can find the minimal set of failure inducing directories. Thus I generalized that algorithm to remove the directory changeset specific code so that it will work with all other types of changesets.
  • Removed the debugging/test related code from the source files.

Milestone:

  • Even though the test framework is incomplete, I think we can go ahead and begin the initial testing of the delta debugger on a real regressive program as I think we are ready. Coincidentally, exactly 2 months after the first project news posting on Sept. 26, 2006.


Nov. 25, 2006

I haven't posted an update in a while so here goes. What's been done since then?

Committed some updates to the SVN repository.

  • Modified the Changeset hierarchy of classes. Added a getChange() subroutine that takes an index and retrieves the change from the changeset. Also modified the getChangeset() subroutine to optionally take an array of directories/files to limit the search scope to within the directories/files passed in. These changes are possibly dangerously untested.
  • Committed the DeltaDebugger.pl file. This file houses the actual delta debugging algorithm. It requires three user-defined pieces of information: a Build object, an RCS object, and the automated test cases. Currently, it can theoretically find the failure inducing revision, and the minimal failure inducing set of directories.
  • Committed a DeltaDebuggerTest.pl file. It just tests the correctivity of the theoretical.


In the works:

  • Continue working on the delta debugging algorithm. Need to be able to find the minimal failure inducing set of files.
  • Test framework. Allow users to plug in test cases/suites without touching the DeltaDebugger.pl module.


The deadline for a version 0.01 release is looming. 1-2 weeks left to get this done. What needs to be done to accomplish this?

  • Finish everything that is in the works real soon.
  • Need a test program that we could use and upload to our test SVN repository to test the delta debugging framework. Ideally, the test program will meet the following requirements:
  1. Has source files that span multiple directories wide and deep yet be small enough that the delta debugging can be done in a short amount of time so that all aspects of the delta debugger can be tested.
  2. Has a regression. Or can easily be modified so that some functionality will stop working.
  3. Has an automated test case that tests the regressive functionality.
  • Put theory into practice. So far the delta debugging algorithm has not been tested on a real program. The correctness of the algorithm has only been confirmed in theory. We need to test the algorithm in a production environment real soon.


Nov. 19, 2006

The earlier crash case we had (see the update directly below) was a non-regressive bug--there was no former build that worked with it.

Going to use Bug #325377 instead. Having difficulty identifying when it was first introduced--the information in the bug report doesn't seem to be quite accurate. Using the nightly builds as archived at http://archive.mozilla.org/pub/mozilla/nightly/ to narrow it down.

Fortunately this crash is easily automated and does not require user interaction.


Nov. 18, 2006

  • Found a suitable crash case thanks to the people of #qa (in particular, asqueella and Aleksej). For full details on the bug, see Bug #354300.
  • Talked to Reed Loden on IRC. He will be setting up a CVS repository for us something this coming week (Tuesday at earliest).


Nov. 17, 2006

Committed some updates to the SVN repository.

  • Changed applyChanges subroutine to take array of indices instead of scalar of an index.
  • Added unapplyChanges subroutine to Changeset classes.
  • Math::Combinatorics, shamelessly stolen from here. This module is used in the Delta Debugging Algorithm module to help find the minimal failure-inducing changeset.

In the pipeline:

  • Delta Debugging Algorithm partially complete. Unthoroughly tested though can theoretically find the directories that contain the failure inducing changes.
  • Test cases and samples we may be able to use to test the algorithm.

Uploaded files into scen1 directory, containing test module for binaryTest. The test is ready to be used in the algorithm. The directory contains:

  • binaryTest.pl - test to detect the existence of a file.
  • helloWorld.pl - enough said!
  • binaryTestCaller.pl - runs helloWorld.pl, pipe the result to hello.log, and have binaryTest.pl attempt to detect it.

This is the working version of the code, labeled revision 12. Now I have to find a way to wreck it........


Nov. 14, 2006

The development of testing system for the framework is in the works. The first scenario revolves around a test called BinaryExist, which has been shamelessly ripped from the Tinderbox script. All this test does is check whether a given file exists in the system. While this test can aspire for great things, right now it's doing simple thing, like checking whether its client Hello World program is doing what it's supposed to. Initial testing reveals that this test has potential. Will be uploaded to the SVN soon.


Nov. 05, 2006

I didn't know where else to put this so I'm putting this here. While searching around for the elusive Mozilla tests that are run in Tinderbox, I found this gem. All of the tests are apparently located in the mozilla/testing directory and can be checked out using this command while at the mozilla directory: 

cvs update -d testing

The tests we would most likely be interested in are located in the tinderbox-standalone-tests subdirectory. Based on a quick scan of the perl files there, the test-mozilla.pl file in that directory seems to drive the tests located in the Tests subdirectory which seem to contain a lot of performance tests. The arguments that the test subroutines receive (such as build directory and binary name) seem to come from the Settings.pm file located in the Util directory.

Attempts to run the tests have so far been unsuccessful. If someone (hint hint) could figure out how to run these tests and how these tests work that would be great.


Oct. 31/Nov. 01, 2006

Committed some updates to the SVN repository.

  • Added file DirectoryChangeset.pl. This file gets a list of directories changed since the revision number passed in.
  • Added file DirectoryChange.pl. This file encapsulates the idea of a changed directory, sort of. Basically holds revision number and path of directory.

UPDATE:

  • I didn't feel tired so I added an applyChange() subroutine to the Changeset classes and ChangesetFactory class. This allows the user to apply a change (specified by the index passed in to the subroutine) in a changeset.

Up Next:

  • Based on how much time I predict I will have left to work on this, I don't think I will have enough time to do the Change/Changeset classes for Codeblock or Line. Therefore, it's time to skip ahead and work on the application of changes. Should the user be able to pass in an array of indices of changes to apply in a changeset? Or is just allowing the user to give one index good enough? We may find that out soon enough when we try to implement the delta debugging algorithm.


Oct. 26, 2006

Committed some updates to the SVN repository.

  • Fixed a small bug with the regular expression in FileChangeset.pl's getChangeset() subroutine.
  • Changed the data that is returned in the getChangeset() subroutines. Used to return the Change set. Now returns the number of changes in the change set. This should decrease memory requirements.
  • Merged some functions in FileChangeset.pl that was created based on an erroneous logical assumption.

Up Next:

  • Continue working on the Changeset/Change subclasses. Need to do Directory, Code block, and Line.


Oct. 24/25, 2006

Committed some updates to the SVN repository.

Updates:

  • Updated the package names for all files.
  • Updated the svn.pl file - fixed a small bug.
  • Updated makewrapper.pl - removed debug statements. I should probably rename the file to something better.

Additions:

  • Created ChangesetFactory.pl - Returns a change set based on the type of change set (revision, directory, file, code block, line).
  • Created RevisionChangeset.pl - Gets and returns all of the changes made in a specified revision.
  • Created FileChangeset.pl - Gets and returns a list of the paths to the files that were changed since a specified revision.
  • Created FileChange.pl - Encapsulates the idea of a Change to a file. Basically stores revision number and file path.
  • Created ChangesetTest.pl - Tests the subroutines in the classes and the interactions between the classes.

Up Next:

  • Continue working on the Changeset/Change subclasses. Need to do Directory, Code block, and Line.


Oct. 17, 2006

The quest to build a suitable "wrapper" for the build system is not doing well. So far I have only observed various build logs posted on Tinderbox for the SeaMonkey build. Here are some observations I come up with.

  • Successful builds - green or yellow on Tinderbox
seamonkey-bin exists, is nonzero, and executable.
seamonkey-bin exists, is nonzero, and executable.
seamonkey-bin binary exists, build successful.
  • Broken builds - red on Tinderbox
gmake[6]: *** [nsAttrValue.o] Error 1
...
gmake: *** [alldep] Error 2

Analyzing build logs may be the "lazy" solution to building a wrapper to detect build failures, but that's the best thing we've got so far. Searches for any of the strings listed above in LXR did not yield valuable result, which means the build system remains a mystery to us. Thoughts:

  • Tinderbox builds rely on report logs to capture build data. If we can figure out how to get tap into this process, we can better plan our prototype.
  • Tinderbox performs a build operation first, and then automatically starts a bunch of tests (e.g. MozillaAliveTest, regxpcom test). These tests do not exist within LXR, either, which means they reside outside the tree. If we can find the script that fires these tests, we can probably create our first prototype as a test and hook it into the build system.

So many questions... Perhaps I should start hanging out at #build.


Oct. 15, 2006

Updated the file svn.pl. Added the diff subroutine. It's a wrapper around the svn diff command. Updated the update subroutine. Added another argument and made them both optional. Subroutine can now accept a directory/file argument in addition to revision number.

Also, currently working on creating some subroutines that can break up a changeset based on the type requested. Changeset types include:

  • Revision. A revision may be a changeset. However, MANY changes may occur in each revision so it may be wise to break up the revision into smaller changesets.
  • Directory. All changes made within a directory may be considered a changeset. Again, MANY changes may occur within a directory, so it may be wise to break it up into smaller changesets.
  • File. All changes made within a file may be considered a changeset. Again, MANY changes may occur within a file, so it may be wise to break up the revision into smaller changesets.
  • Code block. Logical code blocks may be considered a changeset.
  • Line. A line in a file is the lowest change denominator.

The lower down the list you go, the higher the possibility of inconsistencies (inability to successfully compile source tree).


Oct. 10, 2006

Added two files to the SVN repository: makewrapper.pl and maketest.pl. I have no idea if the files will be useful or if I just wasted my time.

makewrapper.pl is a light wrapper around the GNU make utility used to build the source tree. This wrapper was created to be able to programmatically execute the make command with various options. One thing I haven't figured out yet is how to get the exit status code that GNU make returned (0 - successful; 2 - error) after it finishes executing so that I can return that exit code in the build subroutine.

maketest.pl just tests the subroutines in makewrapper.pl.

Starting to get a hang of Perl again after not using it for quite some time.


Oct. 09, 2006

Added two files to the SVN repository: svn.pl and svntest.pl. I have no idea if the files will be useful or if I just wasted my time.

svn.pl is a light wrapper around a couple svn commands used to manipulate the svn repository and user's working copy. This wrapper was created to be able to programmatically execute SVN commands. One thing I haven't figured out yet is how to get the exit status code that is returned after every SVN command is executed as I would like to return this exit code in the subroutines.

svntest.pl just tests the subroutines in svn.pl.

Of note, Perl's object-orientedness is quite different from the other object-oriented languages that I am used to such as C++ and Java.


Oct. 03, 2006

Discussed the project with dave humphrey. The gist of the discussion is:

<vipers101> dave: I hereby present you, richard!

<vipers101> richard: say something!

<dave> pffft...way to play like a team

<vipers101> I prefer to have my team share my griefs

......

<dave> let's assume you've got a program that used to work, but now it crashes. you'd like to figure out what changes to the code introduced the crash. you can programmatically test for the existence of the crash. so you want to have the computer go back in time and figure out what was the delta (e.g., changeset) where the crash started. you want to be able to isolate the problem down to a set of changes to a set of files. further if possible. let's say you have revisions 200 to 500, and you know the bug is caused by *something* in there. so you want to bisect your way through those changesets (in SVN each of those numbers is a changeset) until you can see where the bug was introduced

<vipers101> dave: you mean the bugs are not introduced by the recent work?

<dave> you don't know. you can't assume. maybe, maybe not. remember that working on a huge codebase means that there will be lots of changes going on around your work. so if you do a checkin, they take the weekend off, 50 other people could checkin before your next commit. what you need is a way to test for the problem (maybe a return code). then you need to be able to automatically pull and build the code, and run that test. wash, rinse, repeat

<richard> if i get this, i can't assume that the user will already have a test case/function that returns pass/fail?

<dave> right. you probably need to write something to figure this out. so a hung browser might mean you have a timer that watches for an event. or you might wait on a return code. a crash is probably easiest to test for. this is what I mean by writing a "wrapper".

<vipers101> richard: I think we just have a new task list


Sept. 26, 2006

I read through your documentation here, and it is looking good. I also spoke to Shaver by phone this morning, and we chatted briefly about this project. He suggests that you start your work by looking for a suitable Crash Case, one that happens reliably. Then you need at what would be necessary in order to bisect the change set (e.g., bonsai data) in order to get closer to the change that introduced the bug. Shaver suggested that robc (Rob Campbell) might be a good person to help you brainstorm on this.

How to Get Involved

We need a test program that we could use and upload to our test SVN repository to test the delta debugging framework. Ideally, the test program will meet the following requirements:

  1. Has source files that span multiple directories wide and deep yet be small enough that the delta debugging can be done in a short amount of time so that all aspects of the delta debugger can be tested.
  2. Has a regression. Or can easily be modified so that some functionality will stop working.
  3. Has an automated test case that tests the regressive functionality.

If you don't have a program that meets the first requirement, we could also use test programs that have multiple source files. The key being that the program has more than one source file. Programs that are contained in only one source files are useless to us.

If you have a program that meets these requirements, and you want to contribute to this project, then holla.



If you are looking for an easy way in which to contribute to this project, you can jump in by writing one or more tests for the test suite. This does not require that you learn about the delta debugging inner-workings or structure.

Basic Advice:

  • You must be able to automate the test--no human intervention is allowed.
  • Possible test types include:
    Crashing
    Can you crash the program with a minimal collection of circumstances (steps) that are easily reproducable? (In other words, can you write a script so that this happens in a controlled manner.)
    Performance-related
    Is there a threshold for unacceptable consumption of time and/or space that is reason for concern?
    Program hanging
    Does the program hang? Will it occur in a certain functionality of the software that is possible to isolate (reproduce) through scripted means?
    Unexpected return codes
    What is a normal return code for the program? What is considered unexpected? Script a series of actions and pass the return code up to the test framework.
  • Each test will fit into the test framework (which, at this point, still has to be designed). The tests must follow a few rules (again, undecided at this point).

Please check back in a few days. Expect some templates and samples up shortly to help get you going. The currently listed test types are subject to change.

Retrieved from "https://wiki.cdot.senecapolytechnic.ca/w/index.php?title=Delta_debugging_framework&oldid=6748"