DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-15 are pending and examined in this office action.
Claim 14 recites “a symbolization unit”. It should be “a symbolization step”. Correction is requested.
Specification
The title of the invention is not descriptive. A new title is required that is clearly indicative of the invention to which the claims are directed.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are: a constraint generation unit, a symbolization unit, an instruction execution unit, a processing unit, a test case generation unit, a loop upper limit adjustment unit, a test code generation unit, an annotation processing unit in claims 1, 6, 7, 9. Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f), it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-15 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, mathematical relationship or an abstract idea) without significantly more.
Statutory Category: Claim 1 recites an information processing device comprising: a constraint generation unit that generates a constraint from at least one of a source code, an annotation written in a source code, or an annotation of a source code written in an external file; a symbolization unit that generates a source code that runs on a symbol execution engine and is obtained by symbolizing a motion and an input, on a basis of the constraint generated by the constraint generation unit; an instruction execution unit that executes an instruction of the source code generated by the symbolization unit, line by line with the symbol execution engine; a processing unit that performs processing in accordance with an instruction reached by the instruction execution unit, to collect path constraints; and a test case generation unit that solves the collected path constraints using a constraint solver, to generate a test case as a solution of the path constraints.
Step 2A – Prong 1: claim 1 recites: a constraint generation unit that generates a constraint from at least one of a source code, an annotation written in a source code, or an annotation of a source code written in an external file; (a mental step of generating a constraint); a symbolization unit that generates a source code that runs on a symbol execution engine and is obtained by symbolizing a motion and an input, on a basis of the constraint generated by the constraint generation unit (a mental step of generating a source code); a processing unit that performs processing in accordance with an instruction reached by the instruction execution unit, to collect path constraints (a mental step of processing an instruction to collect path constraints); a test case generation unit that solves the collected path constraints using a constraint solver, to generate a test case as a solution of the path constraints (a mental step of solving path constraints to generate a test case). That is, nothing in the claim elements precludes the steps from practically being performed mentally or using pen and paper. If a claim limitation, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of generic computer components, then it falls within the mental process grouping of abstract idea. Accordingly, the claim recites an abstract idea under step 2A prong 1.
This judicial exception is not integrated into a practical application. In particular, the claim 1 recites additional elements such as an instruction execution unit that executes an instruction of the source code generated by the symbolization unit, line by line with the symbol execution engine, which is an extra solution activity of executing a generated instructions, that is a Well-Understood, Routine, Conventional (WURC) Activity, as evidenced in Tanida (page 261, left column, "SymJS is an extended version of Rhino [12], an opensource implementation of JavaScript. Our extensions include symbolic execution of target code, constraint solving to obtain concrete test input data, and state management"). Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. The claim is directed to an abstract idea under Prong II step 2B.
Dependent claims 2-13 do not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a practical application, the dependent claims 2-13 recite more steps of a mental process (such as adding, searching, measuring, discarding, solving, generating, modifying, outputting, processing) which can be performed mentally or using pen and paper. The additional element of dependent claims 2-13 recite more extra-solution activities (executing, running code), which do not impose any meaningful limits on practicing the mental process (insignificant additional element that is well known in the field of the art). Therefore, these claims are not patent eligible.
Independent claim 14 is a method claim that recite similar limitations as claim 1. The additional element in the claim amounts to no more than a generic hardware component with instructions to apply the exception, which cannot integrate a judicial exception into a practical application or provide an inventive concept.
Independent claim 15 recites computer instructions running on a computer to perform functions described in claim 1. The additional element in the claim amounts to no more than a generic hardware component with instructions to apply the exception, which cannot integrate a judicial exception into a practical application or provide an inventive concept.
Claim 15 is also rejected under 35 U.S.C. 101 because the claimed invention is directed to a non-statutory subject matter. Claim 15 discloses a computer program written in a computer-readable format. Under the broadest reasonable interpretation, a computer-readable format can include signal propagation medium. A signal propagation medium is a non-statutory subject matter. (See MPEP 2106).
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-2, 4-5, 7, 9, 11, 14-15 are rejected under 35 U.S.C. 103 as being unpatentable over Tanida et al. (Automatic Unit Test Generation and Execution for JavaScript Program through Symbolic Execution, 2014, provided in applicant's IDS) hereinafter Tanida, in view of Godefroid et al. (US PGPUB 2009/0265692) hereinafter Godefroid.
Per claim 1, Tanida discloses an information processing device comprising: a symbolization unit that generates a source code that runs on a symbol execution engine and is obtained by symbolizing a motion and an input, on a basis of the constraint generated by the constraint generation unit (page 262, right column, “our symbolic stub generation technique produces stub for functions and classes specified. Our driver generation technique emits code which calls functions specified”; page 262, left column, “SymJS interprets bytecode compiled from target program source code. This approach is taken by existing symbolic executors such as KLEE”; page 259, left column, “In order to symbolically execute a program, input variables to the program are handled as symbolic variables with their concrete values unknown”; i.e. symbolizing an operation/motion and associated input variables); an instruction execution unit that executes an instruction of the source code generated by the symbolization unit, line by line with the symbol execution engine (page 261, left column; SymJS interprets bytecode compiled from target program source code. SymJS is implemented as an interpreter of Rhino bytecode, which updates the program state (content of heap/stack and path condition) on execution of every bytecode instruction; i.e. executing generated instructions line by line); a processing unit that performs processing in accordance with an instruction reached by the instruction execution unit, to collect path constraints; (page 260-261; “during symbolic execution of a program, constraints to be met in order to execute each path are calculated iteratively. After visiting every possible path within the program, constraints for all the path are obtained”; i.e. collecting path constraints); a test case generation unit that solves the collected path constraints using a constraint solver, to generate a test case as a solution of the path constraints (page 261, left column, “Concrete values of variables meeting the constraints can be obtained with solvers such as SMT solver. Obtained values are input data to exercise paths corresponding to the constraints, which we can use for testing”; page 261, right column; “If it is possible to obtain solutions satisfying the constraints, they can be used as inputs used during testing. Constraints on numbers can be solved by feeding them into SMT solvers”; i.e. solving path constraints to generate input values for future testing).
While Tanida discloses a symbolization unit that generates a source code that runs on a symbol execution engine and is obtained by symbolizing a motion and an input, Tanida does not explicitly teach a constraint generation unit that generates a constraint from at least one of a source code, an annotation written in a source code, or an annotation of a source code written in an external file; a symbolization unit that generates a source code that runs on a symbol execution engine, on a basis of the constraint generated by the constraint generation unit. However, Godefroid suggests the above (paragraph [0008]; performing a symbolic execution of the software to produce path constraints; injecting issued constraints into the software where each issue constraint comprises a coded formula; i.e. generating constraints based on a source code, generating modified source code based on the generated constraints). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine Tanida and Godefroid to generate constraints based on a source code, and to generate modified source code based on the generated constraints; as such method can be used for an automated testing session to dynamically check many properties thoroughly and efficiently (paragraph [0004]).
Claims 14 and 15 recite similar limitations as claim 1. Therefore, claims 14 and 15 are rejected under similar rationales as claim 1.
Per claim 2, Tanida further discloses wherein, in a case where the instruction execution unit has reached a conditional branch, the processing unit adds a branch condition to the path constraints, and searches for a path having a branch (page 261, left column; “Upon hitting branch instruction, it duplicates the program state and continues with the execution of both the branches”; “After visiting every possible path within the program, constraints for all the path are obtained”; i.e. every path is searched).
Per claim 4, Tanida further discloses wherein the processing unit discards an execution path that is unable to meet a constraint (page 261, left column; “Upon hitting branch instruction, it duplicates the program state and continues with the execution of both the branches”; “After visiting every possible path within the program, constraints for all the path are obtained. Concrete values of variables meeting the constraints can be obtained with solvers such as SMT solver. Obtained values are input data to exercise paths corresponding to the constraints, which we can use for testing”; i.e. concrete values are obtained by solving the constraints, and only paths for which satisfying values exist can be exercised with a generated test case; those paths without satisfying values are discards, no test case is generated for those paths).
Per claim 5, Tanida further discloses wherein, when the instruction execution unit finishes executing a function to an end, the processing unit solves the path constraints collected during a previous search using the constraint solver, to generate a test case that is a solution of the path constraints (page 261, left column; “After visiting every possible path within the program, constraints for all the path are obtained. Concrete values of variables meeting the constraints can be obtained with solvers such as SMT solver. Obtained values are input data to exercise paths corresponding to the constraints, which we can use for testing”).
Per claim 7, Godefroid further discloses a test code generation unit that generates a test code on a basis of the generated test case (paragraph [0031]; if the decision block decides that a solution exists, then a generation block 150 generates new test input (test case), as explained, the new test input is based at least in part on output from the constraint solver, which may be mapped to input for the software undergoing testing (i.e. generating test code based on test case)).
Per claim 9, Tanida further suggests an annotation processing unit that processes an annotation added to a test target function (page 263, right column; “Symbolic drivers are generated from source code of functions to be tested. Source code need to contain annotations expressing type of arguments passed to the function, in order to automatically generate symbolic driver to invoke the function. Type of parameters passed to functions are often given with @param annotation for JSDoc3. Symbolic driver for the function func0() can be generated from the annotations in Figure 7, attached to the function. The annotations give types of parameters for the function, allowing generation of the symbolic driver in Figure 3”).
Per claim 11, Tanida further suggests the annotation processing unit processes an annotation added in a form of a comment regarding designation of an argument type to be passed on to a variable-length argument (page 263, right column; “Symbolic drivers are generated from source code of functions to be tested. Source code need to contain annotations expressing type of arguments passed to the function, in order to automatically generate symbolic driver to invoke the function. Type of parameters passed to functions are often given with @param annotation for JSDoc3. Symbolic driver for the function func0() can be generated from the annotations in Figure 7, attached to the function. The annotations give types of parameters for the function, allowing generation of the symbolic driver in Figure 3”).
Claim 3 is rejected under 35 U.S.C. 103 as being unpatentable over Tanida, in view of Godefroid, and in view of Copty et al. (US PGPUB 2018/0232523) hereinafter Copty.
Per claim 3, Tanida does not explicitly teach in a case where the instruction execution unit has reached a branch to enter a loop, the processing unit measures a line coverage of the loop. However, Copty suggests the above (paragraphs [0086][0100]; measuring test coverage during program execution, measurement of the coverage may be a percentage of the instructions of the program invoked during the execution, coverage metrics also include a loop coverage metric and a branch coverage metric). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to combine Tanida, Godefroid and Copty to measuring test coverage during a program execution, including measuring a loop coverage metric and a branch coverage metric; as these metrics can reveal the effectiveness of executed test cases, and to help a user to determine if more testing is needed.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. See PTO-892 form.
Tillmann et al. (US PGPUB 2007/0033442) disclose a test system comprises a mock behavior generator creates a symbolic object with stubs to receive calls and mock behavior that returns symbolic values upon receiving a call to the stub. A symbolic executor symbolically executes the parameterized unit test to obtain path constraints for an implementation under test, and at least one path constraint includes the symbol returned in response to the call to the stub. A constraint solver provides solutions for the paths including concrete values assigned to returned symbols. The mock behavior generator creates mock objects that return the concrete values when the implementation under test is executed.
Li et al. (US PGPUB 2012/0204154) disclose a symbolic execution for GPU, includes symbolically executing bytecode with the configuration information; and, based on the symbolic execution, generating one or more results conveying a functional correctness of the software program. The number of states and generated test cases can become extremely high for programs containing extensive branches--especially when the branches are within nested loops. Particular embodiments apply reduction techniques to cut similar paths while keeping more important ones to maintain higher coverage.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to HANG PAN whose telephone number is (571)270-7667. The examiner can normally be reached 9 AM to 5 PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Chat Do can be reached at 571-272-3721. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/HANG PAN/Primary Examiner, Art Unit 2193
Prosecution Insights