Generating a transition system for use with model checking
View Patent ↗The invention concerns model program analysis of software code using model checking. Initially, a transition system ( 22 ) and an extensible markup language (XML) ( 24 ) representation of the data is generated. Next, labels ( 26 ) for the transition system are generated by querying the XML representation of the data using (markup) query language. The labels and the structure of the transition system are then used as input to model checking techniques to analyse the software code ( 28 ). It is an advantage of the invention that the problem of labelling a transition system can be transformed into the XML domain so that detailed information about the software code can be extracted using queries in a format that can be run in the XML domain which are well known. At the same time the transformation to the XML domain does not prevent the use of efficient model checking technologies.
1. A non-transitory machine-readable medium storing one or more instructions for generating a labeled transition system for use with model checking of source code in a computer, which when executed by a processor of the computer, cause the processor to perform operations comprising:
generating a transition system from the source code;
generating an extensible markup language (XML) representation of the source code comprised of nodes, each node having an identifier;
generating labels for the transition system to form the labeled transition system by running a query on the XML representation of the source code using query language to return an identifier of a node that matches the query and labeling a node in the transition system identified by the same identifier as the node that matched the query; and
using the labels and the structure of the labeled transition system as input to model checking techniques to analyze the source code.
2. The processor performed operations of claim 1 , wherein the model checking techniques involve static analysis of the source code.
3. The processor performed operations of claim 2 , wherein static analysis of the source code comprises:
identifying presence or absence of a class of software bugs in the source code;
finding security vulnerabilities of the source code; and
performing worst case execution timing analysis of the source code.
4. The processor performed operations of claim 1 , wherein the operations are performed as the source code is being written or during compile time.
5. The processor performed operations of claim 1 , wherein the query checks for static properties of the source code.
6. The processor performed operations of claim 1 , wherein the operations further comprise initially generating an abstract syntax tree representation of the source code, and wherein the operations of generating the transition system and generating the XML representation of the source code are based on the abstract syntax tree representation of the source code.
7. The processor performed operations of claim 6 , wherein the query identifies tree patterns in the abstract syntax tree representation of the source code.
8. The processor performed system of claim 1 , wherein the operations further comprise generating an abstract syntax tree representation of the source code, wherein the operations of generating the transition system and generating the XML representation of the source code are based on the abstract syntax tree representation of the source code, and wherein the node that matched the query in the XML representation of the source code is identified by the same identifier in the abstract syntax tree representation of the source code.
9. The processor performed operations of claim 1 , wherein the operations of generating the transition system and generating the XML representation of the source code are performed, at least in part, simultaneously.
10. The processor performed operations of claim 1 , wherein running the query on the XML representation of the source code comprises selecting the query from a set of predetermined queries.
11. The processor performed operations of claim 1 , wherein the query is created by a user.
12. The processor performed operations of claim 1 , wherein the labeled transition system is a control flow graph, a data flow graph or an information flow graph.
13. The processor performed operation of claim 1 , wherein the query language is XML Path Language (XPath).
14. The processor performed operations of claim 1 , wherein the operation of generating an XML representation of the source code comprises only generating data structures of the XML representation necessary to allow running of the query.
15. Software, comprising computer readable instructions stored on a non-transitory computer readable medium, installed on a computer system to control the computer system to perform the operations according to claim 1 .