System and method to infer call stacks from minimal sampled profile data

Methods and systems for inferring call stacks in a program, such as a video game or simulation program, are described herein. The call stack data can be inferred using a database of previously captured call stacks along with a minimal set of identifiers that fingerprint each call stack. If just the minimal fingerprint can be captured during a subsequent profile, then the corresponding call stack can be inferred.

BACKGROUND

An inference is a process of deriving a conclusion based on premises that are known or assumed to be true. Inferences come in many different forms. For example, mathematics can apply statistical inferences to draw conclusions in situations of uncertainty. Logical inferences can be drawn to deduce conclusions based on known facts and/or assumptions. Inferences have a variety of applications and can even be used when profiling a running software program.

DETAILED DESCRIPTION OF EXAMPLE NON-LIMITING EMBODIMENTS OF THE TECHNOLOGY

Software profilers aid in analyzing the dynamic behavior of a computer program (e.g., for optimizing the program's performance or finding bugs or other problems). Commonly-assigned U.S. application Ser. Nos. 12/533,845, 12/534,048, 14/165,818, 14/249,514, and 14/288,747 (all of which are incorporated herein by reference) describe example profilers. This disclosure describes various embodiments to improve upon current software profiler systems in order to infer call stacks from minimal sampled profile data.

A running computer program can be profiled, essentially monitoring and capturing a running program's behavior. A profiler can use a statistical-based approach in order to minimally impact the behavior of the running program. A profiler works by periodically interrupting the program, recording pertinent information, then allowing the program to run again. During each sample, information such as the currently running function or the entire call stack can be recorded, among other possibilities.

Recording an entire call stack during a sample is highly desirable since it sheds much more light on the actual behavior of the program compared with only capturing the currently running function. Unfortunately, on particular CPU architectures such as ARM®, capturing a call stack is extremely time consuming, which adversely affects the program behavior and reduces the number of samples that can be taken in a given period of time. Therefore, it would be advantageous if the call stack could be inferred from a minimal amount of information, rather than analyzed and recorded directly. Another benefit is that the recorded data is much smaller, allowing for more samples to be recorded given a fixed-sized buffer.

Example embodiments of the technology of this application presents systems and methods in which call stack data can be inferred using a database of previously captured call stacks along with a minimal set of identifiers that fingerprint each call stack. If just the minimal fingerprint can be captured during a subsequent profile, then the corresponding call stack can be inferred. When sampling a call stack, certain fingerprint identifiers can be recorded. These fingerprint identifiers include stack depth size in bytes, CPU core, and/or thread ID. In one example embodiment, recording the stack depth in bytes is required in the process where recording the CPU core and thread ID are optional. The same fingerprint identifiers can be recorded during a minimal non-call stack profile that records the currently running function. Using one or more fingerprint identifiers, the systems and methods can infer that a particular call stack corresponds to our minimal non-call stack sample.

It should be appreciated that the fingerprint ID is not limited to the stack depth size, CPU core, and/or thread ID and could contain a variety of other identifiers. For example, the fingerprint ID could also include where in the frame a particular call stack occurs. These examples of course are non-limiting and the technology described herein envisions a variety of identifiers that could be included in the fingerprint ID.

These processes for inferring the call stacks are effective because of how functions operate in conjunction with the stack. That is, the stack is a dedicated area in memory where temporary data and bookkeeping information is stored to facilitate function processing and function calls. When a function runs, it might store temporary data on the stack, thus increasing the total amount of stack space being used. When a function call takes place, the currently running function will store to the stack its address (e.g., the return address) and store arguments that the soon to be executed function will need. As functions successively call each other and run, the depth of the stack increases (e.g., stacks grow downward in the memory space, thus resulting in “stack depth” where a deeper stack implies a larger stack). Thus, at any point during a running program, the exact depth of the stack in bytes is a result of every function in the current call stack, making the current function and stack depth in bytes indicative of the current call stack. Different call stacks could result in the same stack depth value in bytes, but in actual production software it is somewhat rare.

These processes have yielded an observation that the matching from previous call stack profiles will allow roughly 70% to 95% of call stacks to be inferred, as shown inFIGS. 2-4, and described in detail below. The remaining call stacks can be “guessed” through a combination of static analysis of function calls and the neighboring inferred call stacks, as shown inFIGS. 9-15, and described in detail below. It should be appreciated that the strategies shown and described inFIGS. 9-15leverage at least two key observations: (a) the actual call stack is likely very similar to the sample before and/or after the one in question, and (b) shorter call stacks are statistically more likely than longer ones.

The technology described herein is thus directed to creating a sample profile of functions executing in a running program. This profile is then used during further sampling of an executing program to infer call stacks from running functions by, at least, comparing the stack depth size and currently sampled function to stack depth sizes and “leaf” functions (e.g., the last called function in a particular call stack) in the sample profile. It should be appreciated that the specification may refer to “stack depth size” and “call stack.” As a non-limiting example, stack depth size could preferably refer to the depth of a stack in bytes (e.g., a size of a block of memory) where the call stack could preferably refer to functions comprising a call stack (e.g., called functions from a root function to a leaf function).

It should be appreciated that the techniques described herein can also utilize a weighting technique that assigns weights to different inference strategies (as a non-limiting example, those strategies described herein and as shown inFIG. 4 through 11) and their converted inferred call stack so that certain inferences in the analysis will be weighted with a higher degree of confidence than others. In one non-limiting example implementation, inferred call stacks using samples from the call stack database will be given a higher confidence weight while those using only neighbor evidence will be given a lower confidence weight. By utilizing these weights, any number of inference strategies may be used to determine the inferred call stack, from a single inference strategy to all inference strategies. The inference strategy that produces an inferred call stack with the highest degree of confidence will then be the one selected as the inferred call stack provided back to the user. Thus, a user may have some perspective as to the confidence level with which samples were converted to inferred call stacks.

Example Software Profiling System

FIG. 1is a block diagram showing an illustrative non-limiting implementation of a software profiling system1, which can include, for example, an embedded computing device. The software profiling system1can be used, for example, in classifying and displaying types of anomalous behavior in software execution. Although example software profiling system1can be specifically used for analyzing video game software, it should be understood that it can profile any type of software. System1runs functions while also providing analysis. The system1includes a computing system10connected to a display12(or display device12) and an input device14. The computing system10includes a processor16, which can execute a video game or other program. The game or other program can be stored in a non-transitory game software memory18. System1further includes a graphics engine19that generates graphics for display on the display12. The system1is not limited to a single processor or memory, but can comprise multi-core architecture, multiple processors and/or multiple memories, and/or remotely accessed network (e.g., cloud) computing components. Input from input device14can affect/control program execution.

The graphics engine19includes a frame buffer memory that composes images periodically at a frame rate (e.g., every 1/30thor 1/60thof a second) and reads out the images for display on the display12. Frame refresh rate may be controlled by a timer that interrupts the processor16periodically or non-periodically. Display12may output audio/video data from the program being executed on system10.

The computing system10can further include an analyzer20used in gathering the program execution data when the processor16executes a software program. The analyzer20can be implemented in any combination of software, hardware, and firmware. In one non-limiting illustrative embodiment, the analyzer20is a form of a software profiler that monitors a sequence of operations performed by the processor16while the processor executes the software program. The analyzer20collects data, which may specify various functions that are called during the execution of the software program, and their addresses, which in turn indicate where in the memory program the instructions are stored, as well as counts of times particular functions are called. The analyzer20can store the collected data in a non-transitory log memory buffer21.

The system1also includes a software analysis device30(or information processing apparatus30) capable of communicating with the computing system10via a communications device33, for example. The data that is stored in the log memory buffer21can be conveyed to the software analysis device30. The software analysis device30is also configured to have a processor31for analyzing the execution of a software program and a non-transitory memory32capable of storing a program for analyzing the execution of a software program. Likewise, the device30can be in communication with an input14′ and a display12′.

The analysis device30is also configured with an analyzer34that can analyze the dynamic program behavior of a software program based on the analysis data provided from the computing system10. Any of the components shown in system1could be incorporated in system10and/or on a remote system connected via a network (e.g., in the cloud or datacenter).

Display12′ can display a visualization of the analysis being performed by device30. For example, a user can play a video game using system10where the game is displayed on display12while device30analyzes the gameplay and displays a visualization on display12′. The technology is not limited to separately displaying these items and the same information can be conveyed on a single display or across a multitude of displays.

FIG. 2shows a non-limiting example for sampling multiple call stacks using a software profiler. In the example shown inFIG. 2, call stack samples CS1-CSn are sampled during execution of a running program. Each call stack has an associated root function RF1, one or more intermediate functions IF1, and a leaf function LF1. The root function RF1is representative of a base function (e.g., a first function) that is called in a particular call stack when executing a process. Likewise, the intermediate functions IF1could be representative of one or more functions that have been called between the root function RF1and the currently execution function (i.e., the leaf function LF1). Storing information regarding the root function RF1and intermediate functions IF1can be advantageous when attempting to infer which call stacks are associated with a sampled call stack.

It should be appreciated that a leaf function LF1can represent a currently running function that is being called during a particular sample. That is, the software profiler may collect samples at various points of time during program execution and at a certain point in time, the currently running function (e.g., the “leaf” function) can be recorded along with the stack depth size SD1measuring the depth of a stack in bytes, for example. It should be appreciated that stack depth size is not limited to measuring how big in size the stack is at a particular point in time and could be measured using a variety of alternatives, including measuring how long a stack has been executing a particular process. The information sampled inFIG. 2can be recorded in a database (e.g., a call stack database) for use in inferring which later call stacks should be associated with a known call stack stored in the database.

FIG. 3shows a non-limiting example of functions sampled by a software profiler without associated call stacks. In the example shown inFIG. 3, the software profiler could sample several leaf samples LS1-LSn and in sampling the leaf samples LS1-LSn, the profiler could record the currently executing function (e.g., the “leaf” function) as well as a measured stack depth size SD1at that point in time. That is, in the example shown inFIG. 3, the profiler records only the measured stack depth size SD1as well as the currently executing function (leaf function LF1) without recording the other information associated with the call stack (e.g., the root functions and intermediate functions).

Thus,FIG. 3shows an example simple profile where certain functions can be executing where each executing function has an associated stack depth size. Using this information alone, many call stacks can be inferred from these executing functions by referencing this information against a database (e.g., a call stack database).

It should be appreciated that the information obtained from the initially sampled program may be stored in a database or in any storage medium in which the information can later be accessed (e.g., by indexing elements of the stored information). For example, the information can be stored in a text file, a comma and/or tab separated file, and XML document, or any other variety of known file types in which information can be stored in a tabular manner and accessed by a software program. In other example embodiment, the information stored in the database may also be used as a database of examples for a training set that is input into a machine learning algorithm.

FIG. 4depicts a non-limiting example of how samples shown inFIG. 3can be converted to inferred call stacks using the call stack database formed from the procedures described with respect toFIG. 2as the key. In the example shown inFIG. 4, the system can use the leaf function and stack depth size (e.g., measured in bytes) in an attempt to match those values to a complete call stack (e.g., stored in a call stack database). It should be appreciated that not all of the samples shown inFIG. 4may be matched to data stored in a call stack database. For example, leaf samples LS7and LS8show examples of two functions having respective stack depths where the call stack is unknown (represented by unknown functions UF1and UF2).

Other leaf samples may have matched to known call stacks in the call stack database. For example, leaf sample LS1has a leaf function noted as “Function D” and a stack depth size of 592 bytes. Using these two values alone, the system can look to the call stack database to see if there is a possible match. In the example shown inFIG. 4, leaf sample LS1has matched a known sample in the database that has a leaf function as “Function D” and a stack depth size of 592 bytes. That is, the information in the database indicates that a call stack with stack depth size of 592 bytes having a leaf function of “Function D” will most likely have a call stack including intermediate functions A, B, and C (CS6inFIG. 2). Thus, the profiler can advantageously analyze an executing program and infer which call stacks certain functions belong to simply by comparing the executing function and stack depth size against a known leaf function and stack depth size stored in a database (e.g., call stack database). This allows the profiler to analyze the running program and infer call stacks of executing functions by only knowing how deep a stack is for an executing function (as well as by virtue of the name/type of the running function itself).

As shown inFIG. 4, there will be certain instances where a call stack cannot be inferred just by comparing the leaf function and stack depth size to known samples. For example, there could be instances where the call stack database may have more than one call stack matching a stack depth size and leaf function of a currently executing function. Using the example fromFIG. 4, the call stack database could encounter an instance where the sampled call stacks have more than one call stack with a leaf function of “Function D” and a stack depth size of 592 bytes. Likewise, there could be instances where the call stack database produces no match to a known call stack having a leaf function of “Function D” and stack depth size of 592 bytes. In these instances, the profiler can employ additional methods when inferring which call stack the function should be associated.

FIG. 5shows a non-limiting example of how samples taken before and after an unmatched unknown sample can be used to guess at part of the call stack. In the example shown inFIG. 5, at least two methods can be employed to infer a call stack from a function having a leaf function and/or stack depth size that is unknown to the database. Both of these methods take into account one or more neighboring functions (e.g., neighboring in sequence/time of execution) to infer the content of the leaf function in question's call stack. It should be appreciated that neighboring in sequence and/or in time could refer to neighboring in sequence of execution and/or time of execution. For example, a neighboring function could be considered as a function that directly precedes or directly follows a currently executing function being sampled and/or analyzed. Likewise, the neighboring function may indirectly precede or indirectly follow the currently executing function (e.g., executes a few functions prior to or executes a few functions following the currently executing function).

In the example shown inFIG. 5, unknown samples US2aand US2bhave a leaf function as “Function F” and a stack depth size of 752 bytes. In this example, the database could not match any functions having a leaf function of “Function F” and stack depth size of 752 bytes. Thus, the system can infer which functions could make up the intermediate functions running between a root function and a leaf function by looking to the neighbor “evidence.”

In the example shown inFIG. 5, a two neighbor evidence method can be employed to determine which intermediate functions make up a call stack for unknown sample US2a. As can be seen inFIG. 5, unknown sample US2ahas a neighboring sample (e.g., neighboring in sequence/time) illustrated to the left of the sample (e.g., prior in time) as inferred sample IS1a, and a neighboring sample illustrated to the right of the sample (e.g., subsequent in time) as inferred sample IS3a. In this example, both inferred sample IS1aand IS3ahave different leaf functions and stack depth size as unknown sample US2a. But, certain intermediate functions can be inferred as existing in unknown sample US2abased on their commonality to functions in inferred samples IS1aand IS3a. For example, both samples IS1aand IS3ahave common root functions as well as Function A and Function B. Thus, the system can infer that at least the root function, Function A, and Function B make up the call stack for unknown sample US2a. It should be appreciated that the system may not be able to entirely infer the remaining functions in the call stack or may conclude that the call stack should only consist of the functions based on the results of the neighbor evidence. In this respect, the system can employ alternate methods for determining which functions comprise the call stack.

Instead of (or in addition to) using evidence from two neighboring samples, the system may take evidence from only one neighboring sample. In the example shown inFIG. 5, the system infers other functions being called in the call stack based on evidence from the neighboring sample inferred sample IS1b(i.e., to the left of the unknown sample US2b). In this example, Functions C, D, and E are used to infer additional functions in the call stack for unknown samples US2b. The functions from inferred sample IS3bare not used for this portion of the analysis because, in part, inferred sample IS3bhas no additional functions than the ones that were in common with inferred sample IS1b. It should be appreciated that the system can employ any variation of this process here and is not limited to what is shown in this example. For example, inferred sample IS3bmay have additional functions not common to inferred sample IS1b(e.g., Functions X, Y, and Z). Thus, a decision could be made to simply ignore those functions when inferring the functions in the call stack for unknown sample US2b.

It should be appreciated that inferring call stacks from one or more neighboring samples can lead to accurate results because the call stack will have many functions in common with neighboring samples when being sampled/analyzed at different points in time. This could be due to, for example, certain functions not having yet been popped from the call stack. That is, the call stack can be thought of as quite literally a stack of functions that are pushed onto the stack in order and popped from the stack in the reverse order in which they were pushed. In the example ofFIG. 5, Functions A and B may not have necessarily been popped from the stack at points in time between when the function was called during execution of samples IS1aand IS3a. Thus, it is logical that when unknown sample US2aexecutes, Functions A and B will most likely comprise a portion of the call stack as they have not been popped from the stack by the time the functions in sample IS3aexecute.

Likewise, one could infer that certain functions prior in time may still form a part of a currently running stack. For example, Functions C, D, and E could be inferred as still forming part of the call stack for unknown sample US2bas those functions may not have yet been popped from the stack by the time Function F in sample US2bexecutes. Furthermore, this inference could be made also given the fact that the stack depth size of sample US2bis greater than that of sample IS1b. That is, as sample US2bhas a stack depth size of 752 bytes where sample IS1b(e.g., prior in sequence) has a stack depth size of 624 bytes, one could infer that by the time sample US2bfunctions are executing, that functions from the call stack have not been reduced, but have been increased. Under this assumption, the functions from sample IS1bcan be added as “known” intermediate functions executing for sample US2b.

It should be appreciated that the methods employed inFIG. 5do not necessarily have to be limited to only one function prior and/or subsequent in time. For example, the system could analyze several functions prior and/or subsequent in time (e.g.,5functions) to determine which functions comprise the call stack for sample US2b. The system can also perform a search to find additional “unknown” functions that cannot be inferred based on neighbor evidence.

FIG. 6shows a non-limiting example for inferring a call stack when there are two or more call stacks previously seen with identical leaf functions and identical stack depth sizes (e.g., in bytes) in the database. In the example shown inFIG. 6, call stack samples CS5and CS9are two different call stacks with identical leaf functions (i.e., Function K) and identical stack depth sizes (i.e., 208 bytes). This scenario could possibly occur where, when the sample was taken, a function may not necessarily have fully run. That is, the samples CS5and CS9may have been sampled at different points during execution of Function K. For example, sample CS5may have been sampled at the point where Function K has fully executed, where sample CS9may have been sampled at the point where Function K was called but has not executed any portion yet. Thus, when analyzing a currently executing function having the same function and stack depth size, the system cannot use the database alone for finding a match and must employ another strategy for determining which functions comprise the call stack.

In the example ofFIG. 6, guess sample GS2cannot be matched to one call stack alone as it also has a leaf function of Function K and stack depth size of 208 bytes. Thus, one method that could be employed is to select that sample in the database that most closely matches the neighboring evidence. In this example, the strategy employed looks for the shortest call stack requiring all neighbor evidence. That is, neighboring evidence that is common to either of the stored call stack samples may be used to generate the inferred call stack for sample GS2. For example, inferred samples IS1and IS3both have Function A and B in common (which are also common to samples CS5and CS9). But, sample IS1also comprises Function C (which is common to sample CS9). Thus, using this strategy, sample CS9would be used as sample IS1has more functions in common with sample CS9. One could also look at this method as performing a logical OR operation on each sample. That is, a logical OR is applied between samples CS5and CS9based on whether the functions common to both CS5and CS9have been called by any of the neighboring functions. As such, the system could infer that the proper call stack for sample GS2corresponds to the call stack of sample CS9.

FIG. 7shows another strategy the system could employ when there are two or more call stacks with identical leaf functions and identical stack depth sizes (e.g., in bytes). The strategy employed inFIG. 7uses a shortest call stack requiring two neighbor evidence. That is, the strategy looks to both neighbors to determine which functions are in common between the neighbors and looks to match that set with a known call stack in the sample. In the example shown inFIG. 7, the system looks at neighboring samples of guess sample GS2(i.e., inferred samples IS1and IS3) and determines which, if any, functions are in common between the two samples. In this case, guess sample GS2has Functions A and B in common between inferred samples IS1and IS3. Thus, when matching between call stack samples CS5and CS9, the system, employing the methodology of choosing the shortest call stack, will select sample CS5as it also has Functions A and B in common. Thus, under the strategy shown inFIG. 7, the system essentially performs a logical AND operation by selecting functions in common with neighboring call stacks that also match a known sample (i.e., sample CS5).

FIG. 8shows another non-limiting example for determining which call stack to infer when there are two or more call stacks previously seen with identical leaf functions and identical stack depth sizes (e.g., in bytes). In the example shown inFIG. 8, the system employs a strategy that selects the shortest call stack by disregarding the neighbor evidence. In this example, if one or more call stacks match a leaf function and stack depth size in the call stack database, this strategy will pick the sample having the shortest call stack. That is, in the example shown inFIG. 8, sample CS5will be selected as it has the shortest call stack compared to sample CS9. As an alternative, the system could count the number of times a particular call stack sample has been sampled and pick the sample having a highest number. For example, sample CS5may have been profiled ten times during the initial “calibration” profile where sample CS9may have only been profiled four times. Thus, the system could select sample CS5as it had more occurrences than sample CS9during the initial profile. Of course, these strategies are non-limiting and the system envisions using a variety of alternate strategies in determining the best call stack to select.

FIG. 9shows a non-limiting example for “guessing” a call stack when a call stack has not been seen with a particular leaf function and/or stack depth size (e.g., in bytes). The system could use static analysis information of which functions can call other functions and can “guess” the call stack by preferring a shortest call stack that contains the maximum amount of neighbor evidence (e.g., “one neighbor evidence” and “two neighbor evidence”).

In the example shown inFIG. 9, there are several call stacks (possible call stacks PC1-4) that lead to leaf function “Function F” based on static analysis of the functions. Thus, when guess sample GS2is analyzed, the system will attempt to match leaf function “Function F” with stack depth size of 725 bytes against the call stack database. When no result is returned, the system can employ several strategies in determining which call stacks of possible call stacks PC1-4lead to Function F of sample GS2.

In the strategy shown inFIG. 9, the system could employ a method (similar to the one shown inFIG. 6) of selecting a shortest call stack requiring all neighbor evidence (e.g., a logical OR). In this example, the system will analyze each neighboring function and select a highest number of functions that are also in common with the possible call stacks. In this example, inferred samples IS1and IS3both have in common Function A and B, where sample IS1also includes Functions C, D, and E. Using this strategy, Functions A-E are in common with call stack PC1and PC2. But, call stack PC1is the shorter call stack between the two and is thus selected over call stack PC2. As such, sample GS2will be inferred as also having Functions A-E in common under this approach.

FIG. 10shows another non-limiting example for “guessing” a call stack when a call stack has not been seen with a leaf function and/or stack depth size. The system could use static analysis information of which functions can call other functions and can “guess” the call stack by preferring a shortest call stack that contains the maximum amount of “two neighbor evidence” (i.e., ignoring “one neighbor evidence”). Similar to the example shown inFIG. 9, several possible call stacks PC1-4leading to Function F are derived based on static analysis of functions. The strategy employed in this example will analyze both neighbors of a guess sample GS2(i.e., inferred samples IS1and IS3) and select functions for the call stack that are common to both neighbors. In this example, both neighboring samples have Function A and B in common and thus the shortest call stack having at least these two functions in common is selected. That is, in the example ofFIG. 10, possible call stack PC3is the shortest call stack containing both Function A and B and thus call stack PC3is used to “populate” the inferred call stack of sample GS2. Similar to the strategy employed inFIG. 7, this strategy uses a logical AND operation on neighboring call stacks to select a possible call stack.

FIG. 11shows another example for “guessing” a call stack when a call stack has not been seen with a leaf function and/or stack depth size. The system could use static analysis information of which functions can call other functions and can “guess” the call stack by preferring a shortest call stack. The strategy employed inFIG. 11could make this “guess” by ignoring all neighbor evidence. For example, guess sample GS2could be analyzed as having a leaf function “Function F” and stack depth size of 752 bytes. When compared to the database, no matches may result. As such, the possible call stacks PC1-4(which are analyzed using static analysis of functions) is used to select a shortest call stack disregarding neighbor evidence. Thus, while sample GS2has inferred samples IS1and IS3as neighbors, the system will select the shortest call stack from call stacks PC1-4. In this example, call stack PC4contains the shortest call stack and is thus selected as being the inferred call stack for sample GS2. It should be appreciated that, again, the inferred call stacks are weighted and thus using this approach may result in an inferred call stack having a lower weight than that of other call stacks inferred through other approaches.

FIG. 12shows a non-limiting example where the gap between inferred samples contains multiple unknown samples. In the example shown inFIG. 12, guess samples GS2-4form a gap between inferred samples IS1and IS5. The system could employ strategies that also use a pool of possible call stacks PC1-5that are formed from static analysis of functions to determine the paths leading to the leaf functions in samples GS2-4(i.e., Function F and Function G). Thus, the example ofFIG. 12shows a situation where there is a gap of several samples that could not match to the call stack database.

FIG. 13shows a non-limiting example for “guessing” at the unknown samples employing a strategy seen inFIG. 9. That is, the system can “work” from the outside inferred samples and move towards the middle to infer the call stacks of each guess sample in the gap. The strategy employed inFIG. 13uses a shortest guess requiring all neighbor evidence, working from the outside toward the middle. For example, guess sample GS2can be compared to neighboring inferred sample IS1where sample IS1contains Functions A-E. In this example, the system could select the shortest call stack having these functions from the possible call stacks PC1-PC5. As call stack PC1and PC2also have Functions A-E in common, the system would select call stack PC1as it is shorter when compared to call stack PC2. Likewise, guess sample GS4would be compared to neighboring inferred sample IS5where it is determined that Function A and B comprise the call stack of sample IS5. The system could narrow the possible call stacks to call stacks PC1, PC2, and PC4because they all have Function A and B in common. But, the system, using the strategy described inFIG. 13, would select call stack PC4as it is the shortest of the call stacks compared to call stacks PC1and PC2. The system could iteratively continue this process as it progresses towards the middle-most function in the gap, in this example, guess sample GS3.

FIG. 14shows a non-limiting example where the strategy shown inFIG. 13has been fully “solved.” As shown inFIG. 13, guess samples GS2and GS4were inferred based on an analysis of neighboring inferred samples IS1and IS5, respectively as well as possible call stacks PC1-5. However,FIG. 14shows the solution for the remaining guess sample that is unsolved (i.e., guess sample GS3). In the strategy shown inFIG. 14, guess sample GS3will analyze the inferred call stacks of now “solved” neighboring guess samples GS2and GS4and select the “best” call stack from possible call stacks PC1-5based on this analysis. In this example, a path to leaf function “Function F” is analyzed using evidence from both neighboring samples. As sample GS4has no inferred path to “Function F,” sample GS2will be more preferred in inferring which call stacks lead to “Function F.” Here, sample GS2has Functions A-E which are also found in possible call stacks PC1and PC2. As call stack PC1is shorter than call stack PC2, the system will infer that sample GS3has a call stack of call stack PC1. Thus, sample GS3will be inferred as including Functions A-E.

FIG. 15shows another non-limiting example where the solution for determining which call stack to infer among a gap of unknown samples is solved using a shortest guess requiring no neighbor evidence. Thus, in this example, inferred samples IS1and IS5are not as relevant to the analysis inasmuch as the call stack size of possible call stacks PC1-5. Here, guess samples GS2and GS3lead to leaf function “Function F” and thus possible call stack PC3is selected as it is the shortest call stack from the pool of call stacks leading to “Function F.” As such, samples GS2and GS3will comprise Functions A and P. Likewise, sample GS4will comprise the functions of call stack PC5which is the shortest call stack leading to Function G. Thus, sample GS5will comprise Function A which matches the call stack of possible call stack PC5.

FIG. 16shows a non-limiting example of a flow of processes used for inferring a call stack of a currently executing function. The flow of processes ofFIG. 16describe a general procedure for inferring a call stack for a given executing function and can be carried out by system1.

The process begins by sampling one or more call stack profiles (S1) to build a database (e.g., call stack database). It should be appreciated that this process could be viewed as a “calibration” where the system initially samples several call stack profiles to form a set or database of call stack profiles. These sampled profiles are later used to infer call stacks of a currently executing function. In this process, CPU core and thread information can also be optionally recorded.

After creating a database from the sampled call stack profiles, the system can sample a currently running program to sample one or more currently running functions (S2). In performing this process, the system can record the currently running function as well as the stack depth size (e.g., in bytes). In this process as well, CPU core and thread information can also be optionally recorded.

Upon obtaining the currently running functions and stack depth size, the system can compare these two values to determine if a profile in the database matches a leaf function and stack depth size (S3). If there is no match, the system can attempt to infer the call stacks for a given function based on evidence related to (or unrelated to) neighboring call stack samples, as discussed in further detail with respect toFIGS. 9-15.

If there is a match, the system can determine if there are multiple matches (S4). If multiple matches exist, the system can also attempt to match a call stack for a given function based on evidence related to (or unrelated to) neighboring call stack samples (S6). In this instance, the system could employ the procedures discussed with respect toFIGS. 5-8.

If the system does not have multiple matches, the system infers the call stack based on the match found from the database (S5). It should be appreciated that the system can also weight the inferred call stacks to allow an individual viewing the analysis to have an appreciation of a degree of confidence that the call stack has been properly inferred. The system can also filter certain functions from analysis when, for example, examining “neighboring” functions. For example, the system can filter functions to include only neighboring functions that are executing on the same core and/or thread as the function for which the system is attempting to infer the call stack.