# US 8,572,555 B2 · Automated testing of software with targeting of deep paths > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,572,555 B2 - Document ID: US8572555B2 - Status: Granted - Kind: B2 - Application number: 12/632,859 - Filed: 2009-12-08 - Published: 2011-06-09 - Granted: 2013-10-29 - Earliest claimed: 2009-12-08 - Assignees: Telcordia Technologies, Inc. - Applicants: James L. Alberi; Hiralal Agrawal - Inventors: James L. Alberi; Hiralal Agrawal - Web page: https://patentgrep.com/patent/US8572555B2 ## CPC - G06F 11/3672: {Test management} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method is provided for generating a test case for testing a program, which can include analyzing instructions of the program to identify basic blocks and superblocks, each basic block containing at least one executable instruction, and each superblock containing a plurality of basic blocks. The method can include executing instructions by a processor to perform determining respective weights of superblocks, each weight representing a number of basic blocks which require execution when the superblock is executed; determining the constraints which cause a superblock having a high weight to be executed, and using the determined constraints to generate a test case which, upon execution of the program, causes the high weight superblock to be executed. ## Claims ### Claim 1 A method of generating a test case for testing a program, the program containing a set of computer-readable instructions recorded on a computer-readable medium, at least some of the instructions being conditionally executable by a processor upon occurrence of a constraint, the method comprising executing instructions by a processor to perform: a) analyzing at least some of the instructions to identify basic blocks and superblocks and to determine the constraints thereof, each basic block containing at least one executable instruction, each superblock containing a plurality of basic blocks, wherein all basic blocks of each superblock require execution whenever any basic block thereof requires execution; b) determining respective weights of superblocks, each weight representative of a number of basic blocks which require execution when the superblock is executed; c) determining the constraints which cause a superblock having a highest weight to be executed; and d) using the determined constraints to generate at least one test case which, upon execution of the program, is capable of causing the high-weighted superblock to be executed, wherein the test case is a first test case, the method further comprising, (e) after performing step (d), determining respective weights of remaining superblocks whose execution is not required when executing the program using the first test case, (f) determining the constraints which cause remaining superblocks to be executed, the remaining superblocks having different weights; and (g) using the constraints determined in step (f) to generate at least one second test case which, upon execution of the program, is capable of causing at least one superblock selected from the remaining superblocks to be executed. ### Claim 2 (depends on 1) A method as claimed in claim 1, wherein the high weight is a highest determined weight for any of the superblocks. ### Claim 3 (depends on 1) A method as claimed in claim 1, wherein the at least one selected superblock has a higher weight than at least one other of the remaining superblocks. ### Claim 4 (depends on 1) A method of testing a program using a test case as generated according to the method as claimed in claim 1, the method of testing further comprising executing the program using the test case. ### Claim 5 (depends on 1) A method of generating a test case as claimed in claim 1, wherein step (a) includes reading the at least some instructions prior to executing the instructions and determining at least some of the constraints prior to executing the at least some instructions. ### Claim 6 (depends on 1) A method as claimed in claim 1, further comprising generating a seed test ease for enabling generating a test case. ### Claim 7 An information processing apparatus comprising: a processor; and instructions executable by the processor to perform a method of generating a test case for testing a program containing a set of instructions recorded on a computer-readable medium, the method including: a) analyzing at least some of the instructions to identify basic blocks and superblocks and to determine the constraints thereof, each basic block containing at least one executable instruction, each superblock containing a plurality of basic blocks, wherein all basic blocks of each superblock require execution whenever any basic block thereof requires execution; b) determining respective weights of superblocks, each weight representative of a number of basic blocks which require execution when the superblock is executed; c) determining the constraints which cause a superblock having a high highest weight to be executed; and d) using the determined constraints to generate at least one test case which, upon execution of the program, is capable of causing the high-weighted superblock to be executed, wherein the test case is a first test case, the method further comprising, (e) after performing step (d), determining respective weights of remaining superblocks whose execution is not required when executing the program using the first test case, (f) determining the constraints which cause remaining superblocks to be executed, the remaining superblocks having different weights; and (g) using the constraints determined in step (f) to generate at least one second test case which, upon execution of the program, is capable of causing at least one superblock Selected from the remaining superblocks to be executed. ### Claim 8 (depends on 7) An information processing apparatus as claimed in claim 7, wherein the high weight is a highest determined weight for any of the superblocks. ### Claim 9 (depends on 7) An information processing apparatus as claimed in claim 7, wherein the at least one selected superblock has a higher weight than at least one other of the remaining superblocks. ### Claim 10 (depends on 7) An information processing apparatus as claimed in claim 7, wherein the method further comprises executing the program using the test case. ### Claim 11 (depends on 7) An information processing apparatus as claimed in claim 7, wherein step (a) of the method includes reading the at least some instructions prior to executing the instructions and determining at least some of the constraints prior to executing the at least some instructions. ### Claim 12 (depends on 7) An information processing apparatus in claim 7, further comprising generating a seed test case for enabling generating a test case. ### Claim 13 A non-transitory computer-readable medium having instructions stored thereon, the instructions being executable by a processor to perform a method of generating a test case for testing a program, the program containing a set of instructions recorded on a computer-readable medium, the method including: a) analyzing at least some of the instructions to identify basic blocks and superblocks and to determine the constraints thereof, each basic block containing at least one executable instruction, each superblock containing a plurality of basic blocks, wherein all basic blocks of each superblock require execution whenever any basic block thereof requires execution; b) determining respective weights of superblocks, each weight representative of a number of basic blocks which require execution when the superblock is executed; c) determining the constraints which cause a superblock having a highest weight to be executed; and d) using the determined constraints to generate at least one test case which, upon execution of the program, is capable of causing the high-weighted superblock to be executed, wherein the test case is a first test case, the method further comprising, (e) after performing step (d), determining respective weights of remaining superblocks whose execution is not required when executing the program using the first test case, (f) deter mining the constraints which cause remaining superblocks to be executed, the remaining superblocks having different weights; and (g) using the constraints determined in step (f) to generate at least one second test case which, upon execution of the program, is capable of causing at least one superblock selected from the remaining superblocks to be executed. ### Claim 14 (depends on 13) A non-transitory computer-readable medium as claimed in claim 13, wherein the high weight is a highest determined weight for any of the superblocks. ### Claim 15 (depends on 13) A non-transitory computer-readable medium as claimed in claim 13, wherein the at least one selected superblock has a higher weight than at least one other of the remaining superblocks. ### Claim 16 (depends on 13) A non-transitory computer-readable medium as claimed in claim 13, wherein the method further comprises executing the program using the test case. ### Claim 17 (depends on 13) A non-transitory computer-readable medium as claimed in claim 13, wherein step (a) of the method includes reading the at least some instructions prior to executing the instructions and determining at least some of the constraints prior to executing the at least some instructions. ### Claim 18 (depends on 13) A computer-readable medium as claimed in claim 13, further comprising generating a seed test case for enabling generating a test case.