Simulated program execution error detection method and apparatus5790778Abstract A computer program error detection system that detects errors in a computer program by simulating execution of program statements. An internal format structure is retrieved along with a list of all functions defined by the computer program. The internal format structure is analyzed to determine all function calls and the function call ordering. External behavior models corresponding to the discovered function calls are retrieved and stored in a model table. One or more control flow paths are traversed through the computer program. For each path traversed, a structural memory model is maintained to represent the effect of the simulated execution of statements along the control flow path. A statement is simulated by executing a built in model of the operation. A function call is emulated by executing an external behavior model corresponding to the called function. Execution of an external behavior model causes the structural model memory to be updated to reflect execution of the called function. Information describing the manipulation of the memory model is logged for automodelling purposes. Invalid conditions in the structural memory model are detected and reported. The information logged for automodelling purposes is scanned after analysis of each path to build an outcome for that path. After individual path analysis completes, the different outcomes are processed, duplicates are removed, and an external behavior model representing the computer program under analysis is generated. Claims We claim: Description CROSS REFERENCE TO MICROFICHE APPENDIX
TABLE 1
______________________________________
Package Description Packages Used
______________________________________
ana analyzer none
auto automodelling bot,conf,ctx,vim,
ins,sym
bot utilities none
conf configuration bot,err
cph choice point bot,conf
history
ctx execution context
bot
edg parser none
eng main control block
bot,conf,mcil,
exe,err
err error reporting
bot,conf,edg,ctx
exe execution bot,conf,auto,
ins,sym,vim,ctx
ins instructions bot,conf,ctx,vim,
auto,cph,err
mcil multiple bot,conf,edg
intermediate files
sym symbol table bot,edg,vim
vim virtual image bot,conf,ctx,err
______________________________________
The "Packages Used" column in Table 1 refers to other packages accessed by the package listed in the "Package" column. A package is dependent on all other packages that it accesses. Therefore, the "Packages Used" column gives a list of package dependencies. Dependencies are noted because a package may be adversely affected by a malfunction in a package that it depends upon. Bot: Utilities Package Bot, the utilities package, provides general purpose functions for manipulating strings, files, filenames, memory, and collections. These utilities insulate other packages from portability problems. In the embodiment of FIG. 2, analyzer 202 is executed on CPU 204. If a different CPU is used, resources offered by the operating environment might change. The bot package shields all other packages from these changes. Furthermore, the utilities in the bot package provide a uniform calling convention for packages that need to use system resources. Having uniform calling conventions for often used functions increases the maintainability of analyzer 202. The bot package does not depend on any other package. Table 2 provides a reference to the utilities provided by the bot package contained in one embodiment of the present invention.
TABLE 2
______________________________________
Utility Description
______________________________________
bot.sub.-- col
collections; fixed and variable sized
arrays and lists
bot.sub.-- date
date handling
bot.sub.-- debug
debugging printing and topics
bot.sub.-- fio
file input and output
bot.sub.-- fname
file names
bot.sub.-- mem
memory allocation, reallocation,
freeing
bot.sub.-- str
string handling
bot.sub.-- sys
miscellaneous system calls
______________________________________
Collections The bot.sub.-- col utility supports collections. A collection is conceptually an ordered set or bag (i.e., allowing duplicates) of members. Members can be used as keys, in which case some additional data can be associated with each member. Collections have a type, contents description, and size. The type is simply an uninterpreted integer used for comparing the expected type against the actual type of a collection. Thus, collections are explicitly typed, meaning that each collection expects a specific class of data. The contents description specifies what the collection is comprised of: bits, integers, copied strings, etc. The size of a collection is the number of members in the collection. In one embodiment of the present invention collections of the following items are supported: booleans pointed-to strings (where the collection simply stores a pointer to a string) copied strings (where the collection allocates memory for the string and copies it over) integers pointers (where the collection has no information about what is being pointed to) bytes (where the collection has no information about the structure of those bytes). In analyzer 202, common uses for collections are: fixed-size arrays of bits (suppression codes, choice point history) variable size lists of strings where look-up by name is important (configuration options) the symbol table: variable-sized with an uninterpreted pointer as an index fixed-size of stored values for chunks and for fetched values fixed-size subsets of arrays of stored values per-path external tables (in auto package) collections of predicates collections of outcomes (in a model) collections of externals (in an outcome) the model table: variable-sized with a model identifier as an index collections of function pointers (produced by mcil) A collection is created by invoking the bot.sub.-- col.sub.-- create utility and supplying an initial size and a maximum size. The initial size may be zero elements and the maximum size may be unbounded. One embodiment of the present invention defines a constant called BOT.sub.-- COL.sub.-- NO.sub.-- MAX.sub.-- SIZE which is passed to the bot.sub.-- col.sub.-- create utility to indicate the collection size is unbounded. Fixed-size collections are created by setting the initial size value equal to the maximum size value. Fixed-size collections allow for some optimized implementations. For example, fixed-size boolean collections are implemented as bits. Collections can also be created by invoking the bot.sub.-- col.sub.-- copy utility to copy an existing collection or bot.sub.-- col.sub.-- subset utility to take a subset of an existing collection. Each member of a collection can have some associated raw data. Having associated raw data with a member is useful for implementing symbol tables as collections. A symbol table is a mapping of names to values. A symbol table implemented as a collection would represent a name as a member and its value as the associated raw data. In one embodiment of the present invention, collections are often used to implement arrays. Members are added to the array by using the bot.sub.-- col.sub.-- add.sub.-- member utility which returns the index of the new member. Members at a particular index are retrieved from an array by invoking the bot.sub.-- col.sub.-- get.sub.-- member utility. Both the value of a member and its associated raw data can be retrieved by invoking the bot.sub.-- col.sub.-- get.sub.-- member.sub.-- and.sub.-- raw utility. The value of the member of an array is replaced by using the bot.sub.-- col.sub.-- replace.sub.-- member utility. It is often necessary to iterate through the members of an array. Moving through the members of an array is typically done using a for loop and is well understood in the art. The bot.sub.-- col.sub.-- get.sub.-- num.sub.-- members utility returns the size of the array and can be used to establish the upperbound of the for loop. As mentioned above, inside the body of the for loop, bot.sub.-- col.sub.-- get.sub.-- member can be used to retrieve each member of the array. In one embodiment of the present invention, look-up tables are typically implemented as collections. The bot.sub.-- col.sub.-- lookup.sub.-- member utility can be used to return the index of a member with a particular value. A look-up table identifies a correspondence between an input value and output value. Look-up tables are well understood in the prior art. Detailed Description of Analysis Engine 308 As mentioned earlier, analysis engine 308 is invoked by the user from the command line (or indirectly by automated tools) to generate fault indicators 106 and models 118. According to one embodiment of the present invention, processing in analysis engine 308 is illustrated by block diagram 800 (FIG. 8). Processing begins with initialize global data structures in base packages action 802 (hereinafter "action 802") where global data structures required by four base packages are initialized. The four base packages are the bot, err, ctx and conf packages. Action 802 performs the setup required by analysis engine 308 to process computer program 104. All packages use utilities provided by the bot package. Therefore, global data structures required by the bot package are initialized first. After initialization, the utilities in the bot package are available to the other packages. Next, the global data structures in the err package are initialized so that the err package is available to handle any errors encountered in processing configuration options. After err package processing, an execution context block 2100, a global data structure defined by the ctx package, is allocated and cleared. The err package refers to execution context block 2100 for context information inserted into error messages. Execution context block 2100 is described below in greater detail. Once execution context block 2100 is initialized, the global data structures of the conf package are initialized. In the embodiment of FIG. 8, initializing the global data structures of the bot, err, ctx and conf packages is performed by routines. In the embodiment of Microfiche Appendix A, the routines to initialize the global data structures of the bot, err, ctx and conf packages are labeled respectively bot.sub.-- begin, err.sub.-- begin, ctx.sub.-- begin and conf.sub.-- begin. Processing transfers from action 802 to process default configuration file action 804 (hereinafter "action 804"). Configuration options influence much of the processing performed by analysis engine 308. Accordingly, as the necessary setup has been accomplished in action 802, configuration options are processed in action 804. Configuration options are stored within configuration files 110. A default configuration file 110 contains the default option settings. The default configuration file 110 provides a standard configuration for analysis engine 308. The default configuration file 110 is processed within action 804. First the default configuration file is located. In one embodiment of the present invention, the default configuration file is stored in the home directory of analyzer 202. After default configuration file 110 is located, the default option settings are loaded into analysis engine 308. The option settings are read in one at a time until all the options contained in the default configuration file are loaded. In the embodiment of FIG. 8, default configuration file 110 is processed by a routine. In the embodiment of Microfiche Appendix A, action 804 is performed by the conf.sub.-- load.sub.-- defaults routine which uses the conf.sub.-- read.sub.-- file routine to read in all of the options. The conf.sub.-- read.sub.-- file routine iterates line by line through a configuration file 110 and uses the conf.sub.-- parse.sub.-- option routine to parse each line of the configuration file and retrieve an option. The function performed by action 804 is well known to one of ordinary skill in the art. Configuration options control the level of analysis performed by analysis engine 308 and the type and quantity of output produced by analysis engine 308. For example, configuration options can determine the number of paths executed in the code being tested, what errors are reported, the style in which they are reported and where certain errors are reported. For the embodiment of FIG. 8, a list of configuration options and a description of each is contained in Appendix B. Processing transfers from action 804 to process user-specified configuration info action 806 (hereinafter "action 806") where a user-specified configuration file 110 is processed. A user has the option of customizing the processing performed within analysis engine 308 by specifying a configuration file 110 on the command line within command line information 108. The configuration options set in a user-specified configuration file 110 override the corresponding options found in the default configuration file 110. In one embodiment of the present invention, the optional user-specified configuration file 110 is identified using a "-config" control word on the command line. The "-config" control word is followed by blank space and then the name of a user specified configuration file 110. For example, "-config custom" identifies a user-specified configuration file 110 called "custom". Action 806 first determines if the user specified an optional configuration file 110. If not, no more processing is required by action 806. If a user-specified configuration file 110 is identified, processing continues in a manner similar to action 804. Within action 806, the user-specified option settings are loaded into analysis engine 308. These user specified option settings override the corresponding default settings that were set in action 804. The option settings are read in one at a time until all the options contained in the user-specified configuration file 110 are loaded. In the embodiment of FIG. 8, user-specified configuration files 110 are processed by a routine. In the embodiment of Microfiche Appendix A, action 806 is performed by the conf.sub.-- load routine which uses, as does the conf.sub.-- load.sub.-- defaults routine, the conf.sub.-- read.sub.-- file routine to read in all of the options. Action 806 also processes any command line configuration options specified by the user. Multiple configuration options can be specified on the command line within command line information 108. In one embodiment of the present invention, control line configuration options (and their values) are preceded by a "-prefix.sub.-- opt" control word. The "-prefix.sub.-- opt" control word is followed by an assignment of a value to a configuration option set off by quotation marks. In other words, a command line configuration option specification has the following form: -prefix.sub.-- opt "option name=option value". For example, the "maximum.sub.-- paths" configuration option can be set on the command line by specifying: -prefix.sub.-- opt "maximum.sub.-- paths=300". Appendix B contains various configuration options and permitted option values for one embodiment of the present invention. Action 806 processes the command line configuration options in a left to right fashion respective to their position on the command line. Any given command line configuration option specification has precedence over all previously specified configuration options whether the configuration options were specified on the command line or contained within a configuration file 110. Processing transfers from action 806 to initialize remaining global data structures action 808 (hereinafter "action 808") where the remaining packages are initialized in preparation of analyzing computer program 104. After the configuration options are loaded, the manner in which processing will be conducted is known. At this time, global data structures required for processing are initialized. In one embodiment of the present invention, the auto, cph, exe, ins, mcil, sym and vim packages all have global data structures which must be initialized. In the embodiment of FIG. 8, global data structures in a package are initialized using routines. In the embodiment of Microfiche Appendix A, initializing global data structures in packages is accomplished by routines labeled "pkg.sub.-- begin", where "pkg" stands for the name of the package. For example, the global data structures in the auto package are initialized by the routine labeled "auto.sub.-- begin". Processing transfers from action 808 to action intermediate file read 810 (hereinafter "action 810") where intermediate files 306 that are listed on the command line, within command line information 108, are read and preparatory processing is performed. First, the list of intermediate files 306 contained on the command line is retrieved. Then the contents of each intermediate file 306 are read into memory. A user may specify multiple intermediate files 306, separated by blank space, on the command line. Preprocessor 302 inserts analyze function list 310 into every intermediate file 306 built. Analyze function list 310 contains all the functions in the corresponding intermediate file 306 that are to be analyzed (i.e., the list of all functions defined by the program represented by parse tree structure 304). A composite list of all analyze function lists 310 from all intermediate files 306 specified on the command line is created to form an analyze function master list identifying all functions to analyze. Once the name of all functions that require analysis are known, processing continues to determine the name of all called functions. A "called function" denotes a function which is transferred (usually temporarily) control of execution. A list of all called functions is generated by looping through the analyze function master list. For each function needing analysis, the corresponding parse tree structure 304 is traversed and any functions called are noted. Action 810 determines both the names of all the called functions and also the order of function calls. Analysis engine 308 emulates the execution of a called function. Analysis engine 308 can perform a more robust emulation of a called function if it can execute a corresponding model 118. Otherwise, analysis engine 308 performs a minimal emulation consisting of indicating the called function executed normally. Once names of all the called functions are collected, it is possible to collect all the models existing for those functions. Additionally, the order of function calls generated within action 810 permits analysis engine 308 to tailor the ordering of function analysis to conduct a more thorough examination of the overall program. As much as possible, analysis engine 308 will analyze and model a function before that function needs to be emulated in another part of the analysis. The proper order of function analysis is determined by doing a topological sort of the function call ordering information at the end of action 810. The topological sort produces an ordered function call list. Functions are processed in the order presented in the ordered function call list. Topological sorting is well understood in the prior art. Example 1, illustrated in FIG. 10, presents a sample function call ordering. Referring to FIG. 10, function F1 1002 calls function F2 1004. Function F2 1004 calls functions F3 1006 and F4 1008. In this example, functions f1 1002, f2 1004 and f3 1006 are on the analyze function master list (i.e. require analysis). The list of called functions includes f2 1004, f3 1006 and f4 1008. Of these functions, only a model of function f4 1008, f4 model 1010, exists at the start of analysis. So, f4 model 1010 is executed to emulate calls to function f4 1008. Beyond which models exist at the start of analysis, it is the function call ordering that determines which function is analyzed first. Analyzing f1 1002 first, before a model of f2 1004 is built, results in minimal emulation of f2 1004. Function f1 1002 could be analyzed in more detail if f2 1004 was analyzed and modeled first. Similar reasoning leads to the conclusion to analyze and model f3 1006 before analyzing f2 1004. Once f3 1006 is analyzed and modeled, a more thorough analysis of f2 1004 is possible which ultimately leads to better analysis of f1 1002. Processing transfers from action 810 to action model table build 812 (hereinafter "action 812") where the model table is built. The model table is a collection of pointers to model table entries 900. Each model table entry 900 corresponds to a called function on the called function list. Model table entry 900 is illustrated in FIG. 9. Model table entry 900 includes fields: "function name" 902, "model pointer" 904, "model source" 906, "output destination" 908, "newer model index" 910, "loaded flag" 912, "missing flag" 914, "report missing flag" 916, "automodel flag" 918, "newer model flag" 920, "written flag" 922, "replace flag" 924 and "queue for write flag" 926. Field "function name" 902 specifies the identifier of the function associated with model table entry 900. Field "model pointer" 904 points to a model 118 represented by model table entry 900. Field "model source" 906 specifies where the model pointed to by "model pointer" 904 was read from. Field "output destination" 908 points to the file where to write the model pointed to by "model pointer" 904. Field "newer model index" 910 specifies an index of an entry in the model table which points to a more recent version of a model for the same function that the instant model table entry 900 is associated with. "Loaded flag" 912 indicates if a model has been loaded for this table entry. "Missing flag" 914 indicates if the special "missing model" has been assigned to this table entry. "Report missing flag" 916 indicates if a "missing model" message has been issued regarding this table entry. "Automodel flag" 918 is true if the model pointed to by "model pointer" 904 was created by the automodeller during the current analysis. "Automodel flag" 918 is false even if the model was originally made by the automodeller outside the context of the current analysis. "Newer model flag" 920 indicates if the automodeller has added a model table entry 900 representing an automodeller generated model 118 for the same function that the instant model table entry 900 is associated with. "Written flag" 922 indicates if the model was written out to a file. "Replace flag" 924 indicates if the automodeller replaced the model 118 pointed to by "model pointer" 904. Finally, "queue for write flag" 926 is true if the model should be written out at the end of analysis; otherwise it is false. First, within action 812, a collection is created to embody the model table. A collection of pointers is created because the model table is a set of pointers to model table entries 900. At the time the collection for the model table is created, there are no entries in the table. Next, the initial entries in the model table are created; meaning, members are added to the model table collection that point to model table entries 900. In one embodiment of the present invention, the model table collection is built by a routine. In the embodiment of Microfiche Appendix A, routine ins.sub.-- mt.sub.-- read controls the building of the model table and calls the bot.sub.-- col.sub.-- create.sub.-- collection utility routine to create the model table collection. Action 812 next creates the initial model table entries pointed to by the model table. Action 812 loops through each function on the list of called functions constructed within action 810. For each function on that list, a model table entry 900 is allocated and initialized. Field "function name" 902 is set to the name of the current called function. Then the model table entry 900 is set to indicate the missing model by setting field "missing flag" 914 to true. A pointer to the newly created model table entry is inserted into the model table by adding a member to the model table collection. Also, flag "replace flag" 924 is turned on to signify that the missing model should be replaced by a model 118 generated by the automodeller. In this manner processing iterates through the called function list. Thus, after action 812 completes, there is one model table entry 900 pointed to by the model table for every function on the called function list. In one embodiment of the present invention, the model table is initialized through a routine. In the embodiment of Microfiche Appendix A, routine mcil.sub.-- get.sub.-- next.sub.-- model.sub.-- to.sub.-- read iterates through the list of called function names, routine ins.sub.-- mt.sub.-- insert creates a model table entry 900 and initializes it to indicate the missing model, and the bot.sub.-- col.sub.-- add.sub.-- member utility routine is used to add members to the model table collection. Processing transfers from action 812 to model collection action 814 (hereinafter "action 814"). Action 814 collects any previously built models 118 corresponding to each model table entry 900 referenced in the model table (i.e., for all the functions on the called functions list). The first step in the search for available models 118 is to construct a list of locations to search for model files. A model file is a file that contains models, and, by convention, a model file is recognized by a distinguishing file extension identifier. For example, "mod" and "mar" are two extensions that identify a model file. The "mod" extension denotes a model file that contains current models 118 and the "mar" extension denotes a model file that contains archived models 118. Multiple models 118 may be stored in a single model file. A model file may have index information at the beginning and end of the file that indicates which functions are modeled in the file. Typically, model files are located in directories and the list of places to search for files is a set of directories. Each directory in the set is searched for model files. All files with appropriate file extensions are processed. For each file selected, the model file is allocated and opened. After opening the model file, the index is scanned to determine if any of the models 118 in the file correspond to a function needed for analysis. This is done by comparing function names in the model file index to names on the called function list. For each match, unless "loaded flag" 912 is set to true in the model table entry 900 representing the matched function, the corresponding model 118 is parsed and copied into memory. A pointer to the copied model 118 is put into the corresponding model table entry 900 at field "model pointer" 904. The "missing flag" is turned off for that model table entry 900. Also, for that same model table entry 900, "loaded flag" 912 is set to true and "replace flag" 924 is set to false. When set to true, "loaded flag" 912 means action 814 should ignore all subsequent models 118 that match the function represented by the model table entry 900. After all matches are processed, processing for the selected model file is complete and the model file is closed and deallocated. Models 118 are described below in greater detail. In one embodiment of the present invention action 814 is performed by a routine. In the embodiment of Microfiche Appendix A, routine ins.sub.-- mt.sub.-- read finds the previously built models 118 and routine ins.sub.-- mt.sub.-- parse parses a model within a model file. Action 814 also generates a list of files, the output model files list, which designates the output destinations for models 118 built during analysis. The output model files list is dynamically built as models 118 are inserted into model table entries 900. When a model 118 is linked to a model table entry 900, the output model files list is checked to see if there is a corresponding output model file with the same file name as the source intermediate file 306 for the function represented by the model 118 and with a file extension of "mod". If the sought after output model file is not found then it is added to the output model files list. A model 118 built to represent a function is stored in the output model file corresponding to the intermediate file which originally defined the function. For example, if intermediate file "test.il" contained function f1, then a model 118 built to represent function f1 is stored in output model file "test.mod". When action 814 initializes a model table entry 900, field "output destination" 908 is set to record the name of the output model file corresponding to the intermediate file 306 containing the function identified in field "function name" 902. Model files are described below in more detail. Processing transfers from action 814 to analyze functions action 816 (hereinafter "action 816"). Action 816 analyzes all of the functions on the analyze function master list. The order of processing is controlled by the ordered function call list. Functions are analyzed in order from the first function to the last function on the ordered function call list. For each function, the corresponding parse tree structure 304 is read into memory. Analysis of a function produces fault indicators 106 (if an error is detected) and a model 118 representing the function analyzed. When analysis of the function is complete, the parse tree structure 304 that was read into memory is discarded. In this fashion, by storing the parse tree structure 304 for only as long as needed, memory resources of CPU 204 are conserved. A detailed account of the per-function processing performed in action 816 is described below. Processing transfers from action 816 to output models action 818 (hereinafter "action 818"). Action 818 is responsible for storing the models 118 created by action 816. Each output model file in the output model files list is processed in turn. First, a model output file is created, allocated and opened. Next, action 818 iterates through the model table and queries each model table entry 900. If field "output destination" 908 equals the name of the current model output file and flag "queue for write flag" 926 is true, then the model 118 pointed to by field "model pointer" 904 is stored in the current model output file. "Written flag" 922 is set to true. When processing is complete for the last file in the output model files list, control transfers to free global data structures action 820 (hereinafter "action 820"). Processing concludes with action 820 where storage cleanup is conducted. In the embodiment of FIG. 8, global data structures in a package are freed or cleaned up using routines. In the embodiment of Microfiche Appendix A, global data structures in a package are freed or cleaned up by executing a routine labeled "pkg.sub.-- end", where "pkg" stands for the name of the package. For example, global data structures in the err package are cleaned up by the routine labeled "err.sub.-- end". "Pkg.sub.-- end" routines are run for the following packages: bot, err, conf, auto, cph, ctx, exe, ins, mcil, sym and vim. At this point, processing of computer program 104 is completed. Function Analysis As described above, analysis of the functions listed on the analyze function master list occurs in action 816. The ordered function call list (created by the topological sort executed in action 810) controls the order in which the functions are analyzed. Action 816 loops through the ordered function call list and for each function on the list performs per-function processing as shown in block diagram 1100 (FIG. 11). The instant function under analysis is designated the current function. Per-function processing begins with initialize per-function data structures action 1102 (hereinafter "action 1102"). Action 1102 allocates or initializes any data structures that are used on a per-function basis. In the embodiment of FIG. 11, per-function data structures in a package are allocated or initialized by using routines. In the embodiment of Microfiche Appendix A, routines labeled "pkg.sub.-- begin.sub.-- function", where "pkg" stands for the name of the package, allocate or initialize per function data structures in a package. For example, per-function data structures in the exe package are allocated by the routine labeled "exe.sub.-- begin.sub.-- function". "Pkg.sub.-- begin.sub.-- function" routines are invoked in the following package order: ctx, mcil, err, vim, sym, ins, cph, auto and exe. Action 1102 also posts information to execution context block 2100. Execution context block 2100 is shown in FIG. 21. Execution context block 2100 includes fields: "filename" 2102, "function name" 2104, "current function" 2106, "current iteration" 2108, "current statement" 2110, "current line number" 2112, "current expression" 2114, "emulation depth" 2116 and "emulation context list" 2118. Field "filename" 2102 identifies the source file containing the current function. Field "function name" 2104 identifies the current function. Field "current function" 2106 is a pointer to a node in the parse tree structure 304 currently being processed that uniquely identifies the current function. Field "current iteration" 2108 refers to a count of the number of paths in the current function that have been analyzed. Field "current statement" 2110 is a pointer to a node in the parse tree structure 304 currently being processed that identifies the statement currently under analysis. Field "current line number" 2112 identifies the line in the source file of field "filename" 2102 containing the statement currently under analysis. Field "current expression" 2114 is a pointer to a node in the parse tree structure 304 currently being processed that identifies the expression currently under analysis. Field "emulation depth" 2116 is the depth in a nested function call of the function in field "function name" 2104. Field "emulation context list" 2118 is a collection of context information for each function called in a nested function call. A function call is "nested" when it is used as an argument to another function call or it uses another function call as one of its own arguments. Field "emulation depth" 2116 and "emulation context list" 2118 are only meaningful when the expression currently under analysis is a function call. Action 1102 sets "filename" 2102, "function name" 2104 and "current function" 2106. In one embodiment of the present invention, a routine is used to initialize the first three fields of execution context block 2100. In the embodiment of Microfiche Appendix A, the routine labeled "ctx.sub.-- begin.sub.-- function" initializes the first three fields of execution context block 2100. Processing transfers to load parse tree structure action 1104 (hereinafter "action 1104") after per-function data structures are allocated or initialized and global data structures are updated with function level information. Action 1104 reads into memory the parse tree structure 304 that represents the current function. Processing transfers from action 1104 to analyze paths action 1108 (hereinafter "action 1108"). Action 1108 analyzes the current function by tracing simulated execution of multiple code paths through the current function. Action 1108 keeps executing code paths until either the number of maximum paths has been reached (if the maximum.sub.-- path option has been set) or there are no more code paths to execute. The maximum.sub.-- path option allows users to set a limit on the amount of analysis performed for each function. When the maximum.sub.-- path option is set, it sets an upper boundary on the number of paths analyzed (even if some code paths in the current function are not traversed). Action 1108 performs a loop that first finds a path to execute and then executes that path. Action 1108 finds a path using a deterministic choice point history. The execution of a function is modeled as a choice point history (CPH) tree that consists of choice point nodes and choice edges. A CPH tree is of a similar structure as the parse tree illustrated in FIG. 5. The root node of the CPH tree is the first unresolved choice point in the current function, leaf nodes are function returns and function exits. As mentioned earlier, a choice point is a point in a program where a selection is made between one of two or more alternative sets of program statements based upon the value of a condition or predicate. A choice point node corresponds to a choice point which analysis engine 308 does not have enough information to resolve. Choice point nodes contain a pointer to the node in the parse tree structures 304 that corresponds to the unresolved choice point in the current function. Choice edges correspond to the different possible resolutions of a choice point. For example, a test for equality can resolve to either true or false. A choice point node corresponds to the equality test. This particular choice point node will have two choice edges; one choice edge will correspond with the "true" result and one with the "false" result. A choice point history is deterministic in the sense that each path is replicable. If in different executions of the code each unresolved choice point is resolved in the same way, then the same path through the code is followed. Each choice point node has a fixed number of choice edges. That means that the number of paths leading away from an unresolved choice point node is fixed. Although the number is unknown before execution, the number is determined the first time a choice must be made for the choice point node. The whole CPH tree structure is unknown before execution of the current function. The CPH tree is dynamically constructed during analysis of the current function. The CPH tree is constructed during program execution using a modified breadth-first construction method. Action 1108 maintains a "current level" value. The current level value indicates which choice point nodes have been added to the CPH tree. At any given time, all nodes in the CPH tree that are one or more levels above the current level have been visited. Thus, all their choice edges are determined. Action 1108 picks a new path to execute by randomly picking an unvisited choice edge coming out from a node that is one level above the current level and walking back to the root node. In this way, action 1108 determines a path that starts at the root node and traverses the CPH tree to the selected node one level above the current level. If an unvisited choice edge coming from a node one level above the current level cannot be found, then the current level value is increased by one and the step is repeated. Increasing the current level value means analysis has moved down one level in the CPH tree. If the current level value is increased and there are still no unvisited choice edges coming out from a node one level above the current level, then no more possible paths can be found. In one embodiment of the present invention, a new path is determined by a routine. In the embodiment of Microfiche Appendix A, the "cph.sub.-- path.sub.-- find" routine determines a new path. For each path determined, action 1108 creates a memory model, simulates the effect on the memory model of instructions along the code path, emulates any function calls on the code path, generates fault indicators 106 upon detecting errors and gathers information necessary to building a model 118 of the current function. A detailed account of this per path processing performed in action 1108 is described below. Processing transfers from action 1108 to gather function externals action 1110 (hereinafter "action 1110"). Action 1110 gathers the externals for the current function for future use during model creation. Action 1110 puts the collected externals into global variables. During later processing, model creation routines will extract these externals from the global variables. A function external is an object within a function that can be referenced outside the function or that has values which persist across function calls, e.g., local static variables. The two most common examples of a function external are parameters and return values. Once the externals of the current function are stored, processing is transferred from action 1110 to release parse tree structure action 1112 (hereinafter "action 1112"). Action 1112 releases the parse tree structure 304 representing the current function. Releasing the parse tree structure 304 representing the current function as soon as it is not needed provides for efficient use of memory resources. In one embodiment of the present invention, action 1112 is performed by a routine. In the embodiment of Microfiche Appendix A, the routine mcil.sub.-- release.sub.-- memory.sub.-- region releases the parse tree structure 304. Processing transfers from action 1112 to free or clean up per-function data structures action 1114 (hereinafter "action 1114"). Per-function processing concludes with action 1114 where storage that is used on a per-function basis is cleaned up. In one embodiment of the present invention, per-function data structures in a package are freed or cleaned up using routines. These routines are invoked in the following package order: exe, auto, cph, ins, sym, vim, err, mcil and exe. In particular, the respective auto package routine creates a model 118 for the current function. Automodelling is described below in greater detail. In the embodiment of Microfiche Appendix A, routines labeled "pkg.sub.-- end.sub.-- function", where "pkg" stands for the name of the package, clean up or free storage used on a per-function basis. For example, per-function data structures in the vim package are freed by the routine labeled "vim.sub.-- end.sub.-- function". "Pkg.sub.-- end.sub.-- function" routines are invoked in the reverse order of "pkg.sub.-- begin.sub.-- function" routines. At the completion of action 1114, per-function processing terminates. Path Analysis As described above, action 1108 analyzes the current function by tracing multiple simulated execution code paths. Action 1108 traverses the parse tree structure 304 representing the current function (hereinafter referred to as the "current parse tree structure 304") one time for each path analyzed. For each path analyzed, action 1108 performs per-path processing as shown in block diagram 1200 (FIG. 12). The instant path under analysis is designated the current path. Per-path processing begins with read pragmas action 1202 (hereinafter "action 1202"). Action 1202 determines if a pragma is defined for the current function. A pragma is an Intrinsa directive that sets control for a function or statement immediately following the pragma. A user can specify configuration options by embedding an Intrinsa pragma into the source code of a function. A pragma placed immediately before a function applies to the entire function. For example the following pragma applies to all statements in the main function.
______________________________________
#pragma INTRINSA "supress=null.sub.-- pointer, uninitialized"
int main ( )
int i,j:
j = 1 + 2;
return 0;
}
______________________________________
Details about the "suppress" configuration options can be found in Appendix B. When action 1202 finds a pragma, it first saves the current settings of the configuration options specified by the pragma, and then sets those configuration options according to the values stated in the pragma. Processing transfers from action 1202 to initialize per-path data structures action 1204 (hereinafter "action 1204"). Action 1204 allocates or initializes any data structures that are used on a per-path basis. In the embodiment of FIG. 12, per-path data structures in a package are allocated or initialized by executing a routine. These routines are invoked in the following package order: ctx, mcil, err, vim, sym, ins, cph, auto and exe. In the embodiment of Microfiche Appendix A, the routines executed in action 1204 are labeled "pkg.sub.-- begin.sub.-- path", where "pkg" stands for the name of the package. For example, per-path data structures in the sym package are allocated by the routine labeled "sym.sub.-- begin.sub.-- path". The chunk table is an example of a per-path data structure created by action 1204. The chunk table contains the set of all modelled memory and is used for storage management and leak detection purposes. In one embodiment of the present invention, the chunk table is implemented as a collection of pointers to chunks. Chunks are modelled pieces of known memory and are described below in greater detail. Conceptually, every path traced is a different execution of the function, so a new memory model is created to support each execution. In one embodiment of the present invention, the chunk table is created by a routine. In the embodiment of Microfiche Appendix A, the "vim.sub.-- begin.sub.-- path" routine creates the chunk table. Another per-path data structure created by action 1204 is the symbol table. The symbol table associates parse tree nodes containing names (the "symbol") with locations in the memory model. The symbol table is a collection of pointers to symbol table entries 1300. Each symbol table entry 1300 corresponds to a variable used in the current function. Symbol table entry 1300 is shown in FIG. 13. Symbol table entry 1300 includes fields: "parse tree pointer" 1302, "symbol type" 1304, "memory type" 1306, "symbol location" 1308, "symbol location pointer" 1310 and "parent index" 1312. Locations in the memory model are described below in greater detail. Field "parse tree pointer" 1302 points to the node in the current parse tree structure 304 that defines the symbol represented by the symbol table entry 1300. Field "symbol type" 1304 identifies the kind of symbol represented by the symbol table entry 1300. In one embodiment of the present invention, some possible values for the field "symbol type" 1304 are "variable", "constant", "routine", "dereference" and "return.sub.-- value". Field "memory type" 1306 describes the type of memory used to hold values for the symbol represented by the symbol table entry 1300. Memory types are described below in more detail. Field "symbol location" 1308 is an encoded pointer to the chunk that stores values for the symbol represented by the symbol table entry 1300. Encoded pointers will be described below in more detail. Field "symbol location pointer" 1310 is an encoded pointer to a chunk that stores an encoded pointer to the chunk pointed to by "symbol location" 1308 (i.e., a pointer to the value for the symbol being described). Field "parent index" 1312 is used only for dereferences. A dereference refers to a value pointed to by a pointer. When the symbol table entry represents a dereferenced value, field "parent index" 1312 holds the index into the symbol table of the pointer followed to arrive at the dereferenced value. For example, if the symbol table entry is for *P (the value pointed to by P) then field "parent index" 1312 will contain the index in the symbol table of pointer P. Action 1204 also posts information to execution context block 2100. Action 1206 updates the count in field "current iteration" 2108 by one (indicating the number of the instant path). Processing transfers to layout return value action 1206 (hereinafter "action 1206"). Action 1206 lays out modeled memory for the return value of the current function. Action 1206 also puts the return value into the symbol table. First, action 1206 determines the amount of memory required to represent the return value. This amount, the length of the return value, is measured in bytes. Then, action 1206 calls memory creation unit 1500 with the amount of memory needed to represent the return value. Memory creation unit 1500 creates a piece of modeled memory to hold the return value and returns to action 1206 an encoded pointer to the newly created location in the memory model. Operation of memory creation unit 1500 is described below in greater detail. Next, action 1206 lays out a pointer to the return value location just created. In the embodiment of FIG. 12, pointers are four (4) bytes long. As before, action 1206 calls memory creation unit 1500 to create an appropriate sized piece of modeled memory and is returned an encoded pointer to the newly created model memory location. Action 1206 stores the encoded address of the location of the return value into the location for the pointer to the return value. Finally, action 1206 places the return value in the symbol table. Action 1206 creates a symbol table entry 1300. A pointer to the parse tree node containing the return value is placed in field "parse tree pointer" 1302. A symbol type of "variable" is placed in field "symbol type" 1304. "Return value" is placed into field "memory type" 1306. An encoded pointer to the first location created to hold the return value is placed in "symbol location" 1308. An encoded pointer to the second location created to store a pointer to the return value is placed in field "symbol location pointer." 1310. Field "parent index" 1312 is not used because action 1206 is not storing a pointer dereference in the symbol table. In one embodiment of the present invention, a symbol table entry 1300 is placed in the symbol table by a routine. In the embodiment of Microfiche Appendix A, the routine labeled "sym.sub.-- add.sub.-- symbol" places a symbol table entry 1300 into the symbol table. Processing transfers to process statements along path action 1208 (hereinafter "action 1208"). Action 1208 is responsible for traversing the current path and imitating execution of each statement. Action 1208 performs processing that is appropriate to either simulate or emulate the execution of each individual statement type. A detailed discussion of the processing of action 1208 is presented below under the heading "Statement Analysis". After action 1208 finishes processing each statement along the current path, processing transfers to order symbol table action 1210 (hereinafter "action 1210"). In one embodiment of the present invention, action 1208 is realized by a routine. In the embodiment of Microfiche Appendix A, the routine labeled "exe.sub.-- execute.sub.-- statement" performs the function of action 1208. Action 1210 sorts the symbol table to impose the same order on the symbol table for each path traversed by analysis engine 308. Automodelling requires that the results of different paths be compared. Sorting the symbol table makes it easier to compare the result of executing the current path with the results of executing other paths. In one embodiment of the present invention, the symbol table is sorted in alphabetical order. The reason for sorting the symbol table is best described by way of example. During automodelling, as described later, every symbol in the symbol table needed for automodelling purposes is examined. If the symbol table entry 1300 is a pointer, the pointer chain is followed. Each location along the pointer chain is labeled with the name of the symbol at the head of the chain preceded by one asterisk ("*") for each level of indirection required to reach the location. For example, referring to FIG. 14a, p 1412 is a pointer in symbol table 1410 that points to "Loc1" location 1416. "Loc1" location 1416, being one level of indirection removed from pointer p 1412, is labeled "*p". In turn, "Loc1" location 1416 points to "Loc2" location 1418. "Loc2" location 1418, being two levels of indirection removed from pointer p 1412, is labelled "**P". Symbols are put into the symbol table in the order they are encountered along the path of a function. Symbols may be encountered in a different order when traversing different paths of a function. In FIG. 14a, pointer p 1412 was encountered on the code path before pointer q 1414 and thus p 1412 is in symbol table 1410 before q 1414. In FIG. 14b, representing a different path through the same function, pointer q 1414 is encountered before pointer p 1412. Thus, in FIG. 14b, q 1414 is recorded in symbol table 1420 before p 1412. Pointers p 1412 and q 1414 point to a shared memory model location 1422 (Loc1) that points to a memory model location 1424 containing the value zero (Loc2). Performing the labeling step described above on symbol table 1410 in FIG. 14a leads to the result of "*p=0". This result derives from labeling "Loc1" location 1416 as *p based on starting the chain with pointer p 1412. Performing the labeling operation on symbol table 1420 in FIG. 14b leads to the result of "*q=0". This result derives from labelling location 1422 (Loc1) as *q based on starting the chain with pointer q 1414. Although both paths have the same actual result, it is hard to merge the outcomes because of their disparate expression ("*p=0" as compared to "*q=0"). Sorting the symbol table ensures that pointer p 1412 will always be processed before pointer q 1414. That way, both paths express the result as "*p=0". By ordering the symbol table, the result of the two paths can be collapsed into a single outcome. Thus, ordering the symbol table allows automodelling processing to easily compare the results of different paths. In one embodiment of the present invention, ordering the symbol table is accomplished by a routine. In the embodiment of Microfiche Appendix A the routine "sym.sub.-- order.sub.-- table" orders the symbol table. Processing transfers from action 1210 to leak detection action 1212 (hereinafter "action 1212"). Action 1212 performs leak detection processing. Action 1212 loops through all of modeled memory and scans the information about memory allocation accumulated during analysis of the current path. Action 1212 identifies any chunk of memory that will be leaked when the current function exits. A piece of memory is leaked when it is allocated, but it will not be pointed to by any symbol after the function exits. Action 1212 also detects leaked resources. A detailed explanation of the processing performed by action 1212 is given below under the heading "Leak Detection". Processing transfers from action 1212 to reset pragma.sub.-- options action 1214 (hereinafter "action 1214"). Action 1214 restores any configuration options set in action 1202. If a pragma is defined for the current function, then action 1214 sets the configuration options specified in the pragma to the values saved in action 1202. Action 1214 transfers processing to free or clean up per-path data structures action 1216 (hereinafter "action 1216"). Per-path processing concludes with action 1216 where storage that is used on a per-path basis is cleaned up and global data structures are updated with information about the current path. In the embodiment of FIG. 12, per-path data structures in a package are freed or cleaned up by executing routines. These routines are called in the reverse package order of the routines executed in action 1204. The routines called by action 1216 are invoked in the following package order: exe, auto, cph, ins, sym, vim, err, mcil and ctx. In the embodiment of Microfiche Appendix A, the routines called by action 1216 are labeled "pkg.sub.-- end.sub.-- path", where "pkg" stands for the name of the package. For example, per-path data structures in the exe package are freed by the routine labeled "exe.sub.-- end.sub.-- path". The routine executed by action 1216 corresponding to the auto package is of particular importance in that it gathers information about the "execution" of the current path to help in creating a model 118 for the current function. Automodelling is described below in greater detail. At the completion of action 1216, per-path processing terminates. Memory Creation Unit 1500 As described above, memory creation unit 1500 creates data structures required to model memory. The memory model created by analysis engine 308 represents memory used by a program during execution. Analysis engine 308 creates a structural memory model because the model imitates the internal composition of a value rather than the value as a single unit. For example, in one embodiment of the present invention that analyzes C language programs, a long integer is represented as a composition of four, individually addressable bytes as opposed to one single addressable value. However, the memory model is not physically contiguous as is the heap storage used by many computer programs to store temporary values. The memory model is comprised of the chunk table, chunks 1700 and stored values 1800 linked together by pointers. As mentioned earlier, the chunk table records all of the modeled memory. A chunk 1700 models one or more contiguous memory locations. A stored value 1800 holds the value stored in one or more memory locations (i.e., a chunk 1700). Chunks 1700 and stored value 1800 are described below in greater detail. Create memory unit 1500 processing commences with capture-origin information action 1502 (hereinafter "action 1502"). Action 1502 keeps track of the context in which memory is created. Action 1502 creates an origin context structure 1600 which encapsulates context information at the time memory creation unit 1500 started processing. Origin context structure 1600 is stored in chunk 1700 as described later. Origin context structure is shown in FIG. 16. Origin context structure 1600 includes fields: "external id type" 1602, "external id" 1604, "memory type" 1606, "statement created on" 1608, "expression from" 1610, "in emulation flag" 1612, "source code file" 1614, "source line number" 1616, "input name" 1618 and "output name" 1620. Field "external id type" 1602 indicates the type of item that storage is created for. In one embodiment of the present invention, possible item types are "symbol", "stored value", "string", "return value" and "unknown". "Stored values" are discussed below and "unknown" means the item type cannot be determined. Items of type "symbol" and "string" are well understood by one of ordinary skill in the art. Field "external id" 1604 contains a pointer to a node in the current parse tree structure 304 that uniquely identifies the item triggering the creation of modeled memory. Field "memory type" 1606 categorizes what the memory is being created for. As will be described in more detail later, field "memory type" 1606 is used for modelling purposes. If the memory is being created for an item visible outside the function, then it will be used in automodelling. In one embodiment of the present invention, the types of memory modeled are: constant, global, dereference of global, static, dereference of static, local, parameter, dereference of parameter, heap memory, resource definition, resource, temporary, unknown, address constant, character constant and zero constant. One of ordinary skill in the art will understand constant, global, local, static, parameter and return value items. As mentioned earlier, a dereference refers to the value pointed to by a pointer. For example, dereference of global indicates a memory location that holds a value pointed to by a global variable. The memory type of "unknown" indicates that the piece of memory modeled is not visible outside the function. Items of memory type "unknown" are not used in creating a model 118 for the current function. Temporary values come from intermediate steps of computations performed by the current function and are identified in the current parse tree structure 304. Heap memory is memory allocated by the current function. For example, a "malloc(10)" function call in the C language creates 10 bytes of heap memory. Resources and resource definitions indicate objects used by a function such as files and windows. The more general "constant" memory type is distinguished from the specific cases of address, character and string constant to allow for optimization of processing within analysis engine 308. Because zero is an often used number, analysis engine 308 models only one instance of the constant zero for every use in the current function. Leak detection processing is improved because only address constants, as opposed to other constant types, are dereferenced. Overall efficiency is improved because a check to determine if an item is a valid pointer does not have to be made on character constants. Optimized memory management and decision making improve the performance of analysis engine 308. Field "statement created on" 1608 is a pointer to the parse tree node in the current parse tree structure 304 that identifies the statement containing the item identified in field "external id" 1604. Field "expression from" 1610 is a pointer to the parse tree node in the current parse tree structure 304 that identifies the expression containing the item identified in field "external id" 1604. Flag "in emulation flag" is true when modeled memory is being created for the execution of a model 118. Field "source code file" 1614 identifies the name of the source code file which contains the current function. Field "source line number" 1616 identifies the line number in the source code file identified by field "source code file" 1614 of the statement identified by field "statement created on" 1608. Field "input name" 1618 contains the name of the original stored value associated with the piece of modeled memory being created. Field "output name" 1620 contains the name of the final value associated with the piece of modeled memory being created. Field "input name" 1618 and field "output name" 1620 are used by the automodeller to record if the memory location being modeled is accessible at the beginning ("input name" 1618) or ending ("output name" 1620) of the current function. After origin context structure 1600 is properly filled in, processing transfers to action 1504. Action 1504 creates a model for one or more contiguous memory locations. A memory location is the smallest unit of memory that can be explicitly and uniquely specified by means of an address. Typically, computer memory is byte addressable, and thus, a location is one byte. Action 1504 models memory using a chunk 1700. Chunk 1700 is shown in FIG. 17. Chunk 1700 includes fields: "freed flag" 1702, "reachable flag" 1704, "lost flag" 1706, "memory type" 1708, "chunk number" 1710, "origin context structure pointer" 1712, "stored value pointer" 1714 and "original stored value pointer" 1716. Flag "freed flag" is true when the memory locations modeled by chunk 1700 have been freed. Flag "reachable flag" 1702 is used by leak detection processing to determine if the memory location is reachable. Flag "lost flag" 1706 is true when it can not be determined if the memory modeled is freed or leaked. With lost memory, it is possible that nothing will point to the memory after the function exits, but just because there is no record of a pointer to the memory does not mean that such a pointer does not exist. For example, memory can be allocated and then passed to a routine which is modeled by the missing model. Analysis engine 308 can not ascertain what happened to the allocated memory passed into the routine. Thus, the memory is marked as "lost". Field "memory type" 1708 holds the same information as field "memory type" 1606 described above. Field "chunk number" 1710 is a unique identifier for chunk 1700. Field "origin context structure pointer" 1712 points to the origin context structure 1600 created in action 1502. Field "stored value pointer" 1714 points to the current value in the modeled memory location. Field "original stored value pointer" 1716 points to the original value in the modeled memory location. First, action 1504 iterates through the chunk table looking at chunks 1700 to determine if a chunk 1700 can be reused. If action 1504 can not reuse any chunks 1700 then it must create a new chunk 1700. A pointer to the new chunk 1700 is put into the chunk table. Chunk number 1710 is assigned a number that uniquely identifies new chunk 1700. Flags "freed flag" 1702, "reachable flag" 1704 and "lost flag" 1706 are initialized to false. Field "memory type" 1708 is set to equal "memory type" 1606 set in action 1502. Field "origin context structure pointer" 1712 is set to point to the origin context structure 1600 built in action 1502. Processing then transfers to model values action 1506 (hereinafter "action 1506") to create the stored value set. Action 1506 models values placed into the location modeled by the chunk 1700 created in action 1504. Memory creation unit 1500 models values by creating stored value sets. A stored value set is a collection of stored values. Each stored value is a data structure that represents one unit of memory. In the embodiment of FIG. 15, memory creation unit 1500 imitates the memory management characteristics of the C computer language. The C computer language allocates values as contiguous sets of bytes. Each stored value represents one byte of memory. Thus, a set of stored values represents the collection of bytes used to store one value. For example, a regular integer is typically four bytes long. Action 1506 models an integer by creating four stored values and putting them in a stored value set. Action 1506 creates one stored value for each byte of memory being created. A pointer to each stored value created is put into a stored value set. Thus, a stored value set is a collection of pointers to stored values. A stored value is represented by a stored value block 1800. Stored value block 1800 is shown in FIG. 18. Stored value block 1800 contains the following fields: "origin pointer" 1802, "resource flag" 1804, "exact value known flag" 1806, "initialized flag" 1808, "assumed value flag" 1810, "constraints flag" 1812, "results flag" 1814, "guards flag" 1816, "exact value" 1818, "byte from input" 1820 and "byte from output" 1822. Field "origin pointer" 1802 points to the origin context structure 1600 created in action 1502. Flag "resource flag" 1804 identifies if this data structure represents a stored value or a stored resource. Flag "resource flag" 1804 is always false if the data structure represents a stored value. Resources are represented in an analogous manner to stored values, except that a stored resource block 1900 is used instead of a stored value block 1800. Stored resource blocks 1900 are described below. Flag "exact value known flag" 1806 is true when field "exact value" 1818 contains a valid value. Flag "assumed value flag" 1810 is true if this value was assumed during processing. Flag "constraints flag" 1812 is true if this value can be used in a constraint in a model 118. Flag "results flag" 1814 is true if this value can be used in a result in a model 118. Flag "guards flag" 1816 is true if this value can be used in a guard in a model 118. Constraints, results and guards are described in more detail under the "Modelling Concepts" heading. Field "exact value" 1818 contains the exact value stored in the modeled memory location. Field "byte from input" 1820 identifies the particular byte in the original stored value set (pointed to by "original stored value pointer" 1716) corresponding to this stored value. Field "byte from output" 1822 identifies the particular byte in the final stored value set (pointed to by "stored value pointer" 1714) corresponding to this stored value. Alternatively, if memory creation unit 1500 is called to model memory for a resource then action 1506 will create a stored resource block 1900. Stored resource block 1900 is shown in FIG. 19. Stored resource block 1900 contains the following fields: "origin pointer" 1902, "resource flag" 1904, "leakable flag" 1906, "reachable flag" 1908, "lost flag" 1910, "assumed flag" 1912, "resource type" 1914 and "resource state" 1916. Field "origin pointer" 1902 points to the origin context structure 1600 created in action 1502. Flag "resource flag" 1904 identifies if this data structure represents a stored value or a stored resource. Flag "resource flag" 1904 is always true if the data structure represents a stored resource. Flag "leakable flag" 1906 is true when the resource may not be pointed to after the current function exits. Flag "reachable flag" 1908 is used in leak detection processing as described below. Flag "lost flag" 1910 indicates analysis engine 308 can not predict if the resource is pointed to after the current function terminates. Flag "assumed flag" 1912 is true when the resource was assumed during processing in analysis engine 308. Fields "resource type" 1914 and "resource state" 1916 hold the type and state respectively of the resource requiring modeled memory. After the needed number of stored value blocks 1800 or stored resource blocks 1900 are created and placed in a stored value set, processing transfers to link memory locations with values action 1508 (hereinafter "action 1508"). Action 1508 links the modeled value (or resource) to the modeled memory location. If this is the first stored value set for chunk 1700, both stored value pointer 1714 and original stored value pointer 1716 are set to point to the stored value set created in action 1506. Otherwise, only stored value pointer 1714 is set to point to the stored value set created in action 1506. In this manner, the original stored value set for a location and the most recent stored value set for a location are remembered in chunk 1700. Intermediate instances of a stored value are discarded because they are not needed for automodelling purposes. A model 118 describes the results a function obtains and not how the results are reached. Thus, only the initial and final instances of a stored value and not the intermediate instances are examined for automodelling purposes. Processing for memory creation unit 1500 terminates and action 1508 returns to the caller of memory creation unit 1500 an encoded pointer to the newly modeled memory. An encoded pointer consists of a pointer to chunk 1700 plus an offset into the stored value set pointed to by stored value pointer 1714. Encoded pointers are required because a location in modeled memory is a simulated memory location. For example, refer to the simplified diagram of the linkage between data structures used to model memory shown in FIG. 20. Chunk 2004 is located through an entry in chunk table 2002. In turn, chunk 2004 contains a pointer to the associated stored value set 2006. Offset into stored value set 2006 are pointers to stored values 2008, 2010 and 2012. Thus, in modeled memory, unlike a true memory location, a value cannot be accessed with a simple physical address. So, modeled memory locations or, more simply, locations are encoded pointers to stored value blocks 1800. Leak Detection As discussed above, leaks are detected in action 1212 at the end of path analysis after the statements in a path have been processed. Memory Leaks are detected using a mark and sweep method. First, action 1212 iterates through the chunk table and marks each chunk as unreachable. A chunk 1700 | ||||||