Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
1998-10-09
2002-08-20
Wong, Peter (Department: 2181)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C714S021000, C714S025000, C714S039000
Reexamination Certificate
active
06438712
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention pertains to the field of software correction. More particularly, the present invention pertains to locating bugs using a list of files (a “batch” file) which makes up an input stream for a processor.
2. Description of the Related Art
A common problem encountered in the field of computer engineering is the occurrence of bugs in a part of a computer system, whether hardware or software. For purposes of discussion here, the emphasis will be on software, although it may be applicable to bugs in hardware as well. As used herein, software means information of any kind that can be processed by a processor, and may include data, instructions, or both; and a bug means a portion of software, or an interaction between portions of software, which cause a processor which processes the software to yield erroneous results or to malfunction.
One type of bug which is particularly difficult to locate occurs while processing batch files. When a batch file is processed in sequence, a bug may be witnessed while a particular file (witnessing file) is being processed, but be caused by some processing of predecessor files. Processing of a predecessor file may, for example, cause the witnessing file to crash by allowing data to be overwritten at memory addresses allocated to the witnessing file. Thus, the witnessing file may crash even if it would be properly processed by itself.
Identifying such bugs by conventional means is very difficult. Exhaustive testing is highly impractical because bug frequency typically increases at about an exponential rate relative to the amount of software under scrutiny. Further, conventional tools for locating bugs typically test an individual program, or a set of linked programs, and usually are not well suited at identifying bugs resulting from processing of batch files. To locate a bug, the computer user must search through a lengthy sequence of files, many of which are not involved in causing the bug. This is cumbersome and time consuming even for skilled programmers, and requires significant programming expertise.
There is thus a continuing need in the area of computer engineering for an improved tool which locates and identifies bugs resulting from processing of batch files. Applicability of such tools to identifying such bugs resulting from a batch of print files is highly desired. Such tools preferably should yield a minimal boundary range or minimal list of files for each bug.
SUMMARY OF THE INVENTION
A bug location system and method are presented according to the present invention for identifying one or more bugs resulting from a plurality of files. In a preferred mode of operation, the files comprise an input stream for a printer, and the bugs comprise printing bugs which cause the printer to malfunction when the files are printed. However, the bug location system and method are generally applicable to various types of bugs which may be encountered on various computer or processor platforms.
According to one aspect of the present invention, a printer emulator is implemented as a software program which is run on a processor. Several data structures are used with the printer emulator which allow the processor to implement the bug location method in accordance with the present invention. The processor on which the printer emulator and data structures operate preferably is the central processing unit (CPU) of a general purpose computer or the processing unit of a printer.
According to another aspect of the present invention, a given sequence of files results in a bug, and the bug location system and method determine a smaller sequence of these files which results in the same bug. Bugs are identified as being the same in these sequences according to various indicators. One such indicator is that both sequences crash on the same line of code during processing of a of a particular witnessing file when run with the same options. A further or alternative indicator comprises both sequences having substantially identical core dump traces upon crash or other failure. In accordance with the present invention, the bug is considered to be the same even though some or all of the files not in the smaller sequence of files might contribute to anomalies when the larger sequence of files is processed. This beneficially aids in identifying bugs to sufficient extent that they can be quickly corrected.
According to another aspect of the present invention, a given sequence of files results in a bug, and the bug location system and method determine a smaller sequence of these files that results in the bug and that includes all files of the given sequence between the first and last file of the smaller sequence. Preferably if files are excluded from the beginning or end of this smaller sequence, then the resulting sequence will not result in the bug. Such a sequence is referred to as a minimal boundary range for the bug. When the given sequence is already a minimal boundary range for the bug, then the determined sequence typically will be this minimal boundary range.
According to another aspect of the present invention, a given sequence of files results in a bug and the bug location system and method determine a smaller sequence of the files that result in the bug and that cannot be any smaller. That is, if any files are excluded from this sequence, then the resulting sequence will not result in the bug. Such a sequence is referred to as a minimal list for the bug. When the given sequence is already a minimal list for the bug, then the determined sequence typically will be this minimal list. To speed up convergence on a minimal list for the bug, the given sequence is expected to be a minimal boundary range for the bug, and may be obtained using the bug location method as described above.
According to another aspect of the present invention, the bug location system and method locate a bug resulting from a sequence of files according to the following steps. The bug location method selects and excludes a portion of the files from the sequence of files. The bug location method then determines whether the sequence results in the bug. If not, the bug location method returns a portion of the excluded files to the sequence, and the sequence of files is then tested to determine if it results in the bug. This is repeated until the sequence results in the bug.
According to another aspect of the present invention, if a portion of the files in such a sequence are selected and excluded, and the sequence still results in the bug, additional portions of files in the sequence are iteratively excluded until the sequence no longer results in the bug or no more files can be excluded. At that point, the excluded files are returned to the sequence until the sequence again results in the bug. These steps are repeated as desired to further reduce the length of the sequence. Where the last file of the sequence witnesses the bug, files preferably are excluded from the beginning of the sequence. About half of the files preferably are excluded from the sequence during the first excluding step. About half as many files preferably are returned during each returning step as were either excluded or returned in the most recent step which is either an excluding step or a returning step. Except for a first excluding step, preferably about half as many files are excluded during each excluding step as were either excluded or returned in the most recent step which is either an excluding step or a returning step. Rapid binary convergence on a minimal boundary range for the bug is thus provided.
According to another aspect of the present invention, the bug location method locates a bug caused by processing a sequence of files according to the following steps. The bug location method selects and excludes a file from the sequence, and then determines whether the bug results from the sequence. If not, the file is returned to the sequence. These steps preferably are repeated until a minimal list for the bug is obtained. Very rapid convergence on a minim
Lahive & Cockfield LLP
Oak Technology, Inc.
Vo Tim
Wong Peter
LandOfFree
Quick identification of defect-uncovering files does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Quick identification of defect-uncovering files, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quick identification of defect-uncovering files will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2927304