Description:Complete Specification:
The following specification describes and ascertains the nature of this invention and the manner in which it is to be performed:
Field of the invention:
[0001] The present invention relates to a method and a system for supporting the validation of software requirements. More specifically it relates to supporting creation of new test cases, improving software requirements, etc.
Background of the invention:
Software in embedded systems is largely based on the functionality covered by the source code in the system. The desired functionalities are generally listed in requirements, which are suitable for a high-level understanding of the software. Verifying if the functionalities are met as per the requirements document involves identification of contracts, designing numerous test cases accordingly, and running a large test suite. The inconsistencies of the design or source code with respect to requirements are identified only after running the test suite. This is effort-intensive and might result in delayed identification of inconsistencies in the source code. Generating possible functionalities covered by the source code could help in comparing the functionalities mentioned in the requirement document. This could serve as an intermediate step to identify unattended functionalities and address them in the source code, even before running the test suite and saving enormous effort at a later stage of software development.
Therefore, there is a need to generate the implementation of requirements in source code in the embedded systems through contracts containing post-conditions, actions, etc., and consequently, identify the requirements which are not addressed or addressed incorrectly in the source code.
Brief description of the invention:
The invention relates to a method for supporting validation of software requirements. The method involves generating a requirement graph from the software requirement. The requirement graph may be generated from the software requirement using Natural Language Processing (NLP) techniques. A relevant source code is retrieved corresponding to one or more requirement descriptions from a source code repository. A control flow graph (CFG) is generated for the relevant source code. A first set of nodes is identified in the CFG corresponding to post-conditions and actions specified in the requirement graph. One or more paths containing the first set of nodes are extracted from the CFG; one or more closest feasible paths are identified from these paths. The closest feasible path contains additional nodes corresponding to all additional actions specified in the requirement graph. For example. variables corresponding to the post-conditions and the actions of the software requirement are extracted from the requirement graph to identify the first set of nodes from the CFG. Then, pre-conditions of the requirement are extracted by traversing back from a root node of the closest feasible paths.
The method involves generating a subgraph containing the pre-conditions, the actions, and the post-conditions of the software requirement from the closest feasible path. Further, a test case is generated for validating the software requirement by processing the subgraph. The software requirement is improved using information contained in the subgraph.
The invention also discloses a system for supporting the validation of software requirements. The system comprises a requirement graph generator for generating a requirement graph from the software requirement. A source code retriever retrieves a relevant source code corresponding to the at least requirement description from a source code repository. A control flow graph (CFG) generator generates CFG for the relevant source code. A matching tool identifies the first set of nodes in the CFG corresponding to post-conditions and actions specified in the requirement graph. An extracting tool extracts one or more paths containing the first set of nodes from the CFG. The extracting tool also determines one or more closest feasible paths from one or more paths. The closest feasible path contains additional nodes corresponding to all additional actions specified in the requirement graph. The extracting tool further extracts pre-conditions of the requirement by traversing back from a root node of one or more closest feasible paths. The extracting tool further generates a subgraph containing the pre-conditions, the actions, and the post-conditions of the software requirement.
Brief description of the accompanying drawings:
[0002] An embodiment of the disclosure is described with reference to the following accompanying drawing,
[0003] Fig. 1 illustrates a flow chart of a method for supporting validation of software requirements, according to an embodiment of the present invention.
[0004] Fig. 2 illustrates a sample software requirement and a corresponding requirement graph, according to an embodiment of the invention.
[0005] Fig. 3 shows a part of a sample control flow graph, according to an embodiment of the invention.
[0006] Fig. 4 shows an example for a path containing a first set of nodes identified in a CFG, according to an embodiment of the invention.
[0007] Fig. 5 shows a sample closest feasible path, according to an embodiment of the invention.
[0008] Fig 6 depicts the extraction of pre-conditions from the closest feasible path, according to an embodiment of the invention.
[0009] Fig 7 shows a schematic view of a subgraph, according to an embodiment of the invention.
[0010] Fig. 8 shows a schematic block diagram of a system for supporting the validation of software requirements, according to an embodiment of the present invention.
Detailed description of the invention:
[0011] Fig. 1 illustrates a flow chart of a method for supporting the validation of software requirements, according to an embodiment of the present invention; The method involves generating a requirement graph 20 from the software requirement 10 at step S1. Fig. 2 illustrates a sample software requirement and a corresponding requirement graph, according to an embodiment of the invention. The software requirement 10 may be processed by a suitable method such as by Natural Language Processing (NLP) techniques to generate the requirement graph 20. The requirement graph 20 contains information present in the contracts i.e., actions and post-conditions, in a structured format.
[0012] At step S2, relevant source code (SC) is retrieved corresponding to one or more requirement descriptions from a source code repository (REP) or a knowledge base. The requirement descriptions are derived from the requirement graph 20. A control flow graph (CFG) 30 is generated for the relevant source code (SC) at step S3. Fig. 3 shows a part of a sample control flow graph, according to an embodiment of the invention. The CFGs 30 are more precise than the natural language text in the software requirement 10.
[0013] At step S4, a first set of nodes 40 is identified in the CFG corresponding to post-conditions and actions specified in the requirement graph 20. Fig. 4 shows an example for a path containing a first set of nodes identified in a CFG, according to an embodiment of the invention. In an embodiment of the invention, all the variables involved in the post-conditions, and actions mentioned in the software requirement are extracted from the CFG. Then, the first set of nodes 40 corresponding to the post-conditions, and the actions are identified by exploring the nodes that contain the variables corresponding to post-conditions and actions.
[0014] One or more paths 40 containing the first set of nodes are extracted from the CFG at step S4. All nodes associated with each of the actions for a requirement are considered and traversal is performed from each of these nodes until a node corresponding to the post-condition node list of that specific requirement is encountered. This results in a set of paths for each action which may or may not correspond to the specific requirement being considered.
[0015] At step S5, one or more closest feasible paths 50 are identified from these paths 40. Fig. 5 shows a sample closest feasible path, according to an embodiment of the invention. The closest feasible path 50 contains additional nodes corresponding to all additional actions specified in the requirement graph 20. Among the set of paths 40 identified in Step S4, the path 50 that contains nodes corresponding to all other actions of the specific requirement is identified and considered the closest feasible path 50, as it contains all the actions and results in the post conditions of the requirement 10. This processing usually results in one path 50 that satisfies a requirement, 10 if addressed in the source code (SC).
[0016] Further, pre-conditions of the requirement 10 are extracted by traversing back from a root node of the closest feasible paths 50. Fig 6 depicts the extraction of pre-conditions from the closest feasible path 50, according to an embodiment of the invention. For each of the identified closest feasible paths 50, the preconditions corresponding to the closest feasible paths 50, if exist, are extracted. To handle the preconditions that may exist for the current path from parent nodes, a configurable parameter is used to traverse back to the root node in the CFG 30 to identify the preconditions emerging from parent nodes. In an embodiment of the invention, preconditions for two levels are extracted above the current node, however, the number of levels to be traversed may be changed as per the project needs.
[0017] A subgraph containing the pre-conditions, the actions, and the post-conditions of the software requirement is then generated. Fig 7 shows a schematic view of a subgraph, according to an embodiment of the invention. For instance, the resultant path, including the precondition is further processed to identify the content in each node, as present in the CFG 30. This content is extracted, and the subgraph considering the extracted content and the resultant path is generated for each of the requirements present in the requirement graph. The subgraph contains all the information, in addition to the information present explicitly in the requirement.
[0018] The subgraph may be used for supporting validation of the software requirement 10 in many ways. For example, a test case is generated for validating the software requirement 10 by processing the subgraph. The subgraphs generated are processed to identify the implementations of preconditions, actions, and postconditions in the CFG and are populated to CSV against the expressions in actions and post conditions of each of the software requirements 10. The CSV file may be used for domain-specific post-processing to evaluate against the requirements for test script generation. The requirements with empty cells of preconditions, actions, and postconditions in the CSV file indicate that these specific software requirements are not addressed or missing in the source code. The software requirement 10 is improved using information contained in the subgraph.
[0019] As described earlier, the requirement graph 20 may be generated from the software requirement 10 using Natural Language Processing (NLP) techniques. Variables corresponding to the post-conditions and the actions of the software requirement 10 are extracted from the requirement graph 20 to identify the first set of nodes from the CFG 30.
[0020] Fig. 8 shows a schematic block diagram of a system for supporting the validation of software requirements, according to an embodiment of the present invention. The system 1000 comprises a requirement graph generator 100 for generating a requirement graph 20 from the software requirement 10. A source code retriever 200 retrieves a relevant source code (SC) corresponding to one or more requirement descriptions from a source code repository (REP). The requirement descriptions are obtained from the requirement graph 20.
[0021] A control flow graph (CFG) generator 300 generates CFG 30 for the relevant source code (SC). A matching tool 400 identifies the first set of nodes 40 in the CFG 30 corresponding to post-conditions and actions specified in the requirement graph 20. An extracting tool 500 extracts one or more paths containing the first set of nodes from the CFG 30. The extracting tool 500 also determines one or more closest feasible paths 50 from one or more paths. The closest feasible path 50 contains additional nodes corresponding to all additional actions specified in the requirement graph. The extracting tool 500 further extracts pre-conditions of the requirement by traversing back from a root node of one or more closest feasible paths 50. The extracting tool 500 further generates a subgraph containing the pre-conditions, the actions, and the post-conditions of the software requirement.
[0022] The subgraph contains all the information, in addition to the information present explicitly in the software requirement 10. The subgraph may be used to support the validation of the software requirement 10 in many ways. For example, a test case is generated for validating the software requirement 10 by processing the subgraph. The software requirement 10 and its scope may also be improved using information contained in the subgraph to make it complete.
[0023] Test specifications or test cases can be generated using the subgraphs 50. Software code created and collected over some time can be used to generate CFG, and subgraphs and reduce developer efforts. The method is used to derive correct triplet e.g. action, precondition, post-condition, etc., which are directly related to the test specification. The invention also could be used to flag the cases such as requirements not realized, conflicting requirements, ambiguous requirements, etc.
[0024] It should be understood that the embodiments explained in the description above are only illustrative and do not limit the scope of this invention. Many such embodiments and other modifications and changes in the embodiment explained in the description are envisaged. The scope of the invention is only limited by the scope of the claims. , Claims:We claim: -
1. A method for supporting validation of software requirement (10), said method comprises
- generating a requirement graph (20) from said software requirement (10);
- retrieving a relevant source code (SC) corresponding to said at least requirement description from a source code repository (REP);
- generating a control flow graph (CFG (30)) for said relevant source code (SC);
characterized in said method,
- identifying a first set of nodes (40) in said CFG (30) corresponding to post-conditions and actions specified in said requirement graph (20);
- extracting at least one path containing said first set of nodes (40) from said CFG (30);
- determining at least one closest feasible path (50) from said at least one path, said at least one closest feasible path (50) contains additional nodes corresponding to all additional actions specified in said requirement graph (20).
2. The method according to claim 1, further comprises extracting pre-conditions of said requirement (10) by traversing back from a root node of said at least one closest feasible path. (50).
3. The method according to claim 2, comprises generating a subgraph containing said pre-conditions, said actions, and said post-conditions of said software requirement (10).
4. The method according to claim 3, comprises generating a test case for validating said software requirement (10) by processing said subgraph.
5. The method according to claim 3, further comprises improving said software requirement (10) using information contained in the said subgraph.
6. The method according to claim 1, wherein said requirement graph (20) is generated from said software requirement (10) using Natural Language Processing (NLP) techniques.
7. The method according to claim 1, wherein variables corresponding to said post-conditions and said actions of said software requirement (10) are extracted from said requirement graph (20) to identify said first of nodes (40) from said CFG (30).
8. A system (1000) for supporting validation of software requirements (10), said comprises
- a requirement graph generator (100) for generating a requirement graph (20) from said software requirement (10);
- a source code (SC) retriever (200) for retrieving a relevant source code (SC) corresponding to said at least requirement description from a source code repository (REP);
- a control flow graph (CFG) generator (300) for generating CFG (30) for said relevant source code (SC);
characterized in said system (1000)
- a matching tool (400) identifying a first set of nodes (40) in said CFG (30) corresponding to post-conditions and actions specified in said requirement graph (20); and
- an extracting tool (500)
 extracting at least one path (40) containing said first set of nodes from said CFG (30); and
 determining at least one closest feasible path (50) from said at least one path (40), said at least one closest feasible path (50) contains additional nodes corresponding to all additional actions specified in said requirement graph (20).
9. The system (1000) according to claim 8, wherein said extracting tool (500) further extracts pre-conditions of said requirement (10) by traversing back from a root node of said at least one closest feasible path (50).
10. The system (1000) according to claim 8, wherein said extracting tool (500) further generates a subgraph containing said pre-conditions, said actions, and said post-conditions of said software requirement (10).