In re Knowlton

500 F.2d 566, 183 U.S.P.Q. (BNA) 33, 1974 CCPA LEXIS 130

• Court: Court of Customs and Patent Appeals
• Decided: August 15, 1974
• Docket: Patent Appeal No. 9106
• Status: Published

Opinions

BALDWIN, Judge.

This appeal is from the decision of the Patent Office Board of Appeals, adhered to on reconsideration, affirming the examiner’s rejection of claims 1-8, all the claims in appellant’s application.¹

The Invention

Appellant’s invention relates to a system and method for detecting programming errors or “bugs” in programs for electronic data processors or computers. The application states:

Many modern computers utilize a stored program. In order to make the program available to the computer at its interval operating speed, the program is stored in the internal memory of the computer, often in the same memory as the data to be processed is stored. Such a stored program computer is particularly liable to certain types of programming errors, such as addressing errors.

One addressing error which is particularly difficult to locate and correct is a data fetch in which the wrong storage location is addressed. Whatever is stored in that location is treated as the desired data, and processing continues, compounding the error by many subsequent stages of processing. The exact point at which the original error occurs is often very difficult to locate and correct.

Similarly, a transfer of control might be effected to an undesired memory location. Processing will normally continue, in spite of the error, and many incorrect processing sequences are executed before an impasse arises. Again, it is often difficult to locate the exact source and nature of the error.

In accordance with the present invention, the above and similar types of programming errors are detected by executing the same program at least twice. For each execution, the component subprogram parts of the program are stored in the computer memory in different sequences. Since transfers and data fetches then take place to and from completely different memory addresses, a comparison of the memory location contents for the different cases will immediately indicate addressing errors.

The invention can most advantageously be used in modern data processors of the type using multiple central processors and multiple memories. In this case, the program can be loaded in normal and in scrambled order in the different memories, or different portions of the same memory, and a separate central processor can be used to execute each program sequence. Provisions can then be made to compare the instructions executed and the data retrieved in real time, as they are executed or retrieved. The processing sequence can therefore be terminated immediately upon the occurrence of an error, and subsequent erroneous processing can be avoided. The same effect can be obtained with a single processor by alternately executing program steps from the two differently stored versions of the program, and comparing results after the execution of each pair.

The application contains simplified block diagrams (Figs. 1 and 3) of single and multiprocessor computers and descriptions thereof, which are suitable for use with appellant’s error detection system and method.

The application also contains the following figures and descriptions thereof which relate to the procedures for storing a program in the computer in a normal and “scrambled” order:

In FIG. 2A, for example, there is shown a graphical or schematic representation of what might be considered the normal or natural order of the program. As can be seen in FIG. 2A, the program is divided into subsections, 30, 31, 32, 33, 34, 35, and 36. These subdivisions may be entirely natural divisions of the programs, representing different subroutines, for example, or may be entirely arbitrary subdivisions, taking care to avoid breaks in the range of a “skip” type of instruction, in transfer vectors and in the range of “relative-to-current-address” types of instructions. The entry point for each subdivision is then given a location symbol (“A”, “B”, “DATA 1”, etc.) and a transfer instruction inserted at the end of each subdivision, directing transfer to the next succeeding subdivision. These successions, of course, are logical, and need not be physical. The rules for such subdividing are sufficiently simple that they could be built into an assembler or compiler and thus be done automatically. The successive vertical positions of the subdivisions, of course, represent successive physical locations in the internal memory of the computer.

In accordance with the invention, at least one scrambled version of the program is also prepared for use with the arrangement of FIG. 1. One such scrambled version of the program mapping of FIG. 2A is shown in FIG. 2B. In FIG. 2B, the logically similar program subdivisions are labeled with the same reference numerals, but primed in FIG. 2B. Thus, the second program subdivision in FIG 2B is subdivision 32', corresponding to the third subdivision 32 in FIG. 2A. Not only are the program instructions (30, 31 and 32) subdivided and scrambled (30', 31' and 32'), but the data blocks (33, 34 and 35) are likewise subdivided and scrambled (33', 34', and 35'). Moreover, instruction subdivisions and data subdivisions may be intermingled. The single instruction block 36 (a single transfer instruction) remains the first block in each version, however, to insure the beginning of execution at the logical beginning of the program.

The scrambled order shown in FIG. 2B is only one of many possible scrambled orders. Any other order is equally suitable provided only that a substantial degree of actual scrambling is involved. One simple scrambling technique which can be easily implemented automatically in an assembler or compiler is a simple reversal of order of the subdivisions. Other simple scrambling rules can likewise be easily implemented to take place automatically.

Claims 1, 4, and 5 are exemplary:

1. An error detection system for computers comprising

a memory having a first portion storing a first sequence of program instructions and data items and having a second portion storing a second sequence of program instructions and data items,

said second sequence being substantially identical to said first sequence except for the ordering of the respective sequences of said instructions,

means for executing said program instructions from each of said sequences, and

means for comparing intermediate results of said executions, (paragraphing ours).

4. The method of detecting programming errors in a computer program comprising the steps of

(1) mapping said program into storage in at least two substantially different sequential orders,

(2) executing both said substantially different sequential orders for said program, and

(3) comparing intermediate results of step (2) for mismatches.

5. Apparatus for detecting programming errors in a computer program comprising

(1) means for mapping said program into storage in at least two substantially different sequential orders,

(2) means for executing both said substantially different sequential orders of said program, and

(3) means for comparing the intermediate results of said executing means for mismatches.

The Rejection

The board sustained the examiner’s rejection of all the claims as based on an inadequate disclosure, relying upon the first paragraph of 35 U.S.C. § 112.

The examiner stated:

The specification is deemed sufficient in setting forth the apparatus for carrying out the proposed error detection arrangement once the two versions of a hypothetical program to be debugged are stored in memory and ready for execution and comparison of certain intermediate results. However, the means and method of carrying out the essential “scrambling” process have not been disclosed in such full, clear, concise, and exact terms as to enable one of ordinary skill in the art to make and use the invention ....

* * * * * *

As stated previously, the charts of Figures 2A and 2B and the written portion of the specification represent no more than a graphic illustration of two different mapping orders of a hypothetical computer program and can be considered in no manner to represent an algorithm upon which an assembler or compiler program may be based. Appellant further contends that an assembler or compiler program . for “scrambling” the sequence of instructions in a program to be debugged would be obvious to one of ordinary skill in the art and cites a portion of the book The Language of Computers, by B. A. Galler, as a basis for this contention. It should be noted that the referenced textual material describes the process of arranging sets of items such as numbers, letters, etc. into some particular order. The desired order may be simply arranging numbers into increasing numerical value. Thus, the scope of the textual material is limited to teaching the sorting or arranging of like items into a desired sequence. Appellant’s claimed means for mapping, however, appears to be more than the mere sorting of like items into a desired se-quenc[e]. Reference is made in appellant’s application to limitations imposed upon the “scrambling” process which results in a procedure of higher complexity than a simple sort procedure. Prior to even considering the reordering of program sequences in the original version of the program to be debugged, the matter of selecting appropriate and workable subdivisions into which the program is broken down must be considered. The considerably higher degree of complexity in practicing the instant invention over that of performing a simple sort routine is pointed out by such limitations as requiring that the two versions of the program be “logically identical” * * * and further that if the subdivisions are not “natural” divisions of the program, then care must be taken to avoid breaks in the range of the “skip” type of instruction, in transfer vectors and in the range of “relative-to-current-address„ types of instructions * * *. Thus, the contention that simple sorting techniques are well known in the art is not convincing in determining the adequacy of disclosure relative to the obviousness of an assembler or compiler program for implementing the “scrambled” mapping of a computer program such as claimed in the instant disclosure.

The board stated that after reviewing the rejection in light of the comments of both appellant and the examiner, it also concluded that the disclosure was not enabling within the meaning of the first paragraph of 35 U.S.C. § 112. However, the board also made the following additional comments which expressed its doubts as to the sufficiency of the disclosure :

Although appellant asserts that there are many different “scrambling” techniques that could be used to practice his invention the only one set forth in the application is that'illustrated in Figs. 2A and 2B. Appellant asserts * * * that the scrambled and unscrambled programs are “logically identical.” Of course, the location in memory of each individual instruction and segment of data differs in each program so that each instruction that transfers program control or fetches data must have the same logical, relative address if the two programs are to be logically identical. Appellant has not told us nor is it in any way apparent to us how two programs that are “logically identical” could operate differently or could produce different results if the error in the original program were a logical error as in the ease of a “wild” transfer * * * or of a “wild” fetch •x- * *

Assuming, as appellant contends, that it would be only an elementary programming procedure to prepare a computer program that would convert the original program into the scrambled program, this implies that there is a one to one conversion between the two sets of addresses and the two sets of instructions and data, otherwise they would not be logically identical.

For example, if a programming error were made by requesting a fetch from the next adjacent memory location to the correct one this incorrect or “wild” fetch address would of necessity be translated into the corresponding address of the previously inaccurate data, so that the scrambled program should give the same results as the original program without detecting the logical error.

*****■•»

Since appellant has not given us an algorithm for the scrambling which could carry out the purpose of detecting logical errors in a computer program and we are not aware of such an algorithm, we find appellant’s specification defective in not being in such full and exact terms as to enable a person skilled in the art to make and use appellant’s program error detecting system or method.

Appellant then submitted a detailed Request for Reconsideration attempting to demonstrate the incorrectness of the statements made by the board, supra. In so doing, appellant submitted a “specific coded example” demonstrating how a typical error could occur and how it is detected using appellant’s invention. This example was also relied upon to rebut comments made by the board which appellant considered to constitute “another ground of rejection based possibly on an alleged failure to exhibit operativeness (utility) in the sense of 35 U.S.C. 101.” On reconsideration, the board denied having made any such rejection and commented that the newly offered evidence would not be considered.

OPINION'

In deciding the instant controversy, we are guided by the following principle:

[A] specification disclosure which contains a teaching of the manner and process of making and using [an] invention in terms which correspond in scope to those used in describing and defining the subject matter sought to be patented must be taken as in compliance with the enabling requirement of the first paragraph of § 112 unless there is reason to doubt the objective truth of the statements contained therein which must be relied upon for enabling support. Assuming that sufficient reason for such doubt exists, a rejection for failure to teach how to make and/or use will be proper on that basis; such a rejection can be overcome by suitable proofs indicating that the teaching contained in the specification is truly enabling. In re Marzocchi, 439 F.2d 220, 58 CCPA 1069 (1971).

Upon examining the reasoning set forth by the examiner,² we have concluded that there was a reasonable basis for questioning the adequacy of the instant disclosure which does not include sufficient information for implementing appellant’s mapping or “scrambling” of a computer program.³

The evidence submitted to overcome the examiner’s reasoning is found not to be responsive to such criticism. Appellant’s reliance upon the book by Galler, supra, may well establish that simple sorting techniques are well known in the programming art. However, as the examiner noted, appellant’s invention requires more than just a simple sorting procedure. The disclosure states that in scrambling subdivisions of programs, which are not natural divisions such as subroutines, care must be taken to “avoid breaks in the range of a ‘skip’ type of instruction, in transfer vectors and in the range of ‘relative-to-current-address’ types of instructions.” Based upon the meager record before us,⁴ we cannot conclude that the simple sorting procedures of the Galler book demonstrate that one of ordinary skill in the art would be able to make and use an algorithm for achieving the apparently more complex “mapping” of appellant’s invention.

Appellant has not only failed to offer any evidence to refute the comments made by the examiner with respect to the necessary precautions to be taken when the program is not subdivided into natural subdivisions such as subroutines, but appellant in all of his arguments has ignored those comments and has taken the position that only natural program segments or subroutines are relevant to our inquiry of whether or not the disclosure is enabling. In his brief, appellant stated:

Whether the error detecting method and apparatus will detect errors when special circumstances, e. g., the existence of other than “natural” program segments (subroutines are the most natural segments) is irrevelant [sic]; such special circumstances are not recited in the claims.

The fallacy of such an assertion, and all of appellant’s arguments based thereon, is apparent. The claims do embrace scrambling of other than natural program segments, or subroutines, insofar as the claims are not in any manner limited to scrambling only natural program segments. Furthermore, appellant’s specification states that the program subdivisions “may be entirely natural divisions ... or may be entirely arbitrary subdivisions.” (Emphasis added).

For the foregoing reasons, the decision of the Patent Office Board of Appeals sustaining the rejection of claims 1-8 under the first paragraph of 35 U. S.C. § 112 is affirmed.

Affirmed.

1 . Serial No. 610,837, filed January 23, 1967.

2 . We agree with appellant that the board’s reasoning, supra, may only be construed as doubting the utility or operativeness of the claimed invention. Although that reasoning could have led to a rejection under 35 U.S.C. § 101, it can also be a basis for a rejection under the how-to-use provision of § 112. In re Fouche, 439 F.2d 1237, 58 CCPA 1086 (1971). However, since the solicitor in his brief has assumed that appellant’s invention is both useful and subject to patenting within the meaing of § 101 — a position which we regard as conceding the operativeness of appellant’s invention for purposes of this appeal — and since appellant’s rebuttal to the board’s comments on this issue was not considered by the board, we have not considered the additional comments expressed by the board with regard to any alleged inopera-tiveness of appellant’s invention.

3 . Appellant argues that since claims 1-3 do not recite such a mapping or scrambling means, those claims have an adequate supporting disclosure assuming, arguendo, that such a means is not adequately disclosed. Suffice to say that in analyzing claim 1, which states that “said second sequence being substantially identical to said first sequence except for the ordering of the respective sequences of said instructions,” not in a vacuum, but in light of the disclosure, it is clear that claims 1-3 seek a scope of protection for which the scope of enablement must include a sufficient teaching of the means for reordering or mapping the second sequence. In re Moore, 439 F.2d 1232, 58 CCPA 1042 (1971).

4 . But for the reference to the Galler book, the record consists solely of the arguments and opinions of appellant’s attorney — there are no affidavits in the record before us which set forth any facts whatsoever. Factual affidavits could have certainly been of help as, at least, some evidence on the question of enablement. In re Brandstadter, 484 F.2d 1395 (Cust. & Pat.App.1973).