Inter-procedural analysis of computer programs
View Patent ↗This invention concerns inter-procedural analysis of computer programs. The need for inter-procedural analysis arises, for instance, where information is to be passed across the boundaries between functions; for example, by passing a pointer of variables to another function. The pointer needs to identify a valid memory location when used by a calling function. In one aspect the invention is a method and in another aspect the invention is a computer programmed to perform the method. The heart of the method involves the use of computational tree logic (CTL) model checking each sub-structure of the code to iteratively check alternately whether guarantees associated with the code are true, false or undetermined for each external assumption, and whether the internal assumptions are consistent with the guarantees of the caller sub-structures.
1. A computer method for the inter-procedural checking of source code, comprising:
receiving source code comprising a list of functions;
expressing a required inter-procedural check as a formula expressed in computational tree logic (CTL) syntax;
decomposing the computational tree logic (CTL) syntax of the inter-procedural check into sub-formulae;
automatically mapping the functions of the source code to respective sub-structures of an associated recursive Kripke structure, wherein the sub-structures call other substructures, and wherein each sub-structure comprises the following states:
an entry location having internal guarantees,
other locations representing code statements having respective internal guarantees,
boxes that model calls to other functions, having respective internal assumptions and external guarantees,
and an exit location having internal guarantees and external assumptions;
wherein there are transitions between adjacent locations and boxes that map a value from an precursor location or box to a successor location or box;
generating a summary for each substructure capable of being represented as a table wherein each row represents a location, box or the external assumptions of the substructure, and wherein each row comprises three values that respectively represent:
whether the summary is an assumption for a box, a guarantee for a location or external assumptions,
whether the current sub-formula is true, false or undetermined at that state when a first external assumption of that substructure is assumed to be false,
and whether the current sub-formula is true, false or undetermined at that state when the other external assumption of that substructure is assumed to be true;
then, starting with the simplest sub-formula, refining the summaries by:
(i) applying computational tree logic (CTL) model checking to each sub-structure to check whether the each guarantee is true, false or undetermined for each external assumption and updating the corresponding values of the summary accordingly, then
(ii) checking whether the internal assumptions of each box are consistent with the first internal guarantees of the callee sub-structure, and whether the external assumptions are consistent with the external guarantees of the caller sub-structure and updating the corresponding values of the summary accordingly, then,
(iii) iteratively repeating steps (i) and (ii) until no further refinement of the sub-formula is possible;
then iteratively repeating steps (i), (ii) and (iii) for each sub-formula in increasing complexity, until no further refining is possible for the most complex sub-formula, and therefore the entire formula.
2. A method for the inter-procedural checking of source code according to claim 1 , wherein after the method terminates and there are values in the summary that have not been resolved as true or false, but remain undetermined; comprising resolving the remaining undetermined values by applying rules to allocate true or false values.
3. A method for the inter-procedural checking of source code according to claim 1 , comprising the step of initialization of the method by setting the value of every state of the summary to ‘undetermined’.
4. A method for the inter-procedural checking of source code according to claim 1 , wherein, when checking involves nested formulae, replacing the single values true, false and undetermined by a set of values that also record the callee sub-structure.
5. A method for the inter-procedural checking of source code according to claim 4 , further comprising the step of introducing new sets of values having more values.
6. A method for the inter-procedural checking of source code according to claim 5 , further comprising the step of merging sets of values into new sets with fewer values.
7. A method for the inter-procedural checking of source code according to claim 5 , further comprising the step of checking of sub-formulae when there are nested formulae by checking the sub-formulae bottom up from atomic propositions to the complete formula.
8. A computer programmed to conduct inter-procedural checking of source code, comprising:
an input port to receive source code comprising a list of functions;
a processor to:
express a required inter-procedural check as a formula expressed in computational tree logic (CTL) syntax;
decompose the computational tree logic (CTL) syntax of the inter-procedural check into sub-formulae;
automatically map the functions of the source code to respective sub-structures of an associated recursive Kripke structure, wherein the sub-structures call other substructures, and wherein each sub-structure comprises the following states:
an entry location having internal guarantees,
other locations representing code statements having respective internal guarantees,
boxes that model calls to other functions, having respective internal assumptions and external guarantees,
and an exit location having internal guarantees and external assumptions;
wherein there are transitions between adjacent locations and boxes that map a value from an precursor location or box to a successor location or box;
wherein the processor also generates a summary for each substructure capable of being represented as a table wherein each row represents a location, box or the external assumptions of the substructure, and wherein each row comprises three values that respectively represent:
whether the summary is an assumption for a box, a guarantee for a location or external assumptions,
whether the current sub-formula is true, false or undetermined at that state when a first external assumption of that substructure is assumed to be false,
and whether the current sub-formula is true, false or undetermined at that state when the other external assumption of that substructure is assumed to be true;
then, starting with the simplest sub-formula, the processor operates to refine the summaries by:
(i) applying computational tree logic (CTL) model checking to each sub-structure to check whether the each guarantee is true, false or undetermined for each external assumption and updating the corresponding values of the summary accordingly; then,
(ii) checking whether the internal assumptions of each box are consistent with the first internal guarantees of the callee sub-structure, and whether the external assumptions are consistent with the external guarantees of the caller sub-structure and updating the corresponding values of the summary accordingly; then,
(iii) iteratively repeating steps (i) and (ii) until no further refinement of the sub-formula is possible;
then the processor iteratively repeating steps (i), (ii) and (iii) for each sub-formula in increasing complexity, until no further refining is possible for the most complex sub-formula, and therefore the entire formula.