Patent Description:
Bugs often cause, or are associated with, the corruption of data, which can include corruption of the data of the stack. Debugging is very difficult to perform when relevant data, such as the return addresses on the stack, are corrupted or even missing entirely. Additionally, debugging, especially when performed on large quantities of data, is inefficient. More specifically, as part of debugging, one or more return addresses are generated from information contained in the stack trace utilizing a reverse engineering process known as "unwinding". Unwinding, especially when performed repeatedly, consumes processor cycles and introduces inefficiencies.

In some instances, such as in cloud computing environments, debugging cannot be performed at the time the bug occurs. Instead, a collection of a broad swath of data is performed, with the hopes that such data includes the information relevant to performing the debugging, and that future analysis of such data will be able to successfully debug the bug. Such a collection of data is often referred to as a "dump" of data, and automated mechanisms are utilized to triage such dumps in order to focus, and thereby render more effective, subsequent human analysis thereof. For example, analysis of one or more data dumps may reveal a particular set of characteristics that are associated with a specific bug. Other data dumps can be evaluated for the existence of those characteristics, thereby enabling data dumps to be triaged between those that exhibit the characteristics of known bugs, and those which represent previously unidentified, or unreviewed, errors, such as previously unknown bugs. Human effort can then be focused on the unknown bugs. The evaluation of data dumps for purposes of detecting characteristics includes the unwinding of stack traces, which, as indicated, is inefficient. Accordingly, the evaluation and triaging of large quantities of data dumps, such as would be generated in cloud computing environments, consumes substantial processing resources, including CPU cycles, memory, and other like computing resources.

<NPL>", relates to relates to SoK: Shining Light on Shadow Stacks. A new parallel shadow stack mechanismis provided that encodes the offset in a dedicated register, allowing the offset to the shadow stack to be determined at runtime. Further, the offset varies from thread to thread as registers are thread local, and the offset can be set when the thread is created. This register is only updated once, when the offset is determined for the thread, and therefore adds no per function call overhead (unlike shadow stack pointers for compact shadow stacks). Shadow stack mechanisms can ensure a valid return address in two ways: by either comparing the program and shadow return addresses, or by using the shadow return address. Comparing the shadow and program return addresses detects corruptions of the program return address immediately, and can halt execution. Immediate detection is useful during testing and debugging as it helps isolate the bug.

<CIT> relates to relates to a method of protecting a computer stack. Two computer stacks are created, a first computer stack operates as a traditional stack would, and a second computer stack, or shadow stack, stores the return address upon a call to a subroutine, the address of the return address on the first computer stack, and a user-definable state variable. After jumping to, and executing a subroutine, the return address from both the first computer stack and the second computer stack are compared. If the return addresses match, the method jumps to the return address. If the return addresses do not match, a mismatch situation exists. When a mismatch occurs, the second stack is searched for a matching return address. First, below the stack top is searched, and then above the stack top is searched. If a matching return address is found, it is checked to make sure that the corresponding address of the stack pointer stored in the second stack matches the current location of the first stack's pointer, and that the user-definable variable indicates that the data was stored on the second stack as a return address datatype.

It is the object of the present invention to improve debugging in a cloud or server environment with reduced computational effort and with reduced storage requirements.

A verified stack trace can be generated by utilizing information contained in a shadow stack, such as a hardware protected duplicate stack implemented for malware prevention and computer security. The shadow stack contains return addresses which are obtainable without requiring an unwinding of the traditional call stack. As such, triaging based on return address information can be performed more quickly and more efficiently, and with a reduced utilization of processing resources. Additionally, the generation of a verified stack trace can be performed, with such a verified stack trace containing return addresses that are known to be correct and not corrupted. The return addresses can either be read from the traditional call stack, or derived therefrom, and then verified by comparison to corresponding return addresses from the shadow stack, or they can be read directly from the shadow stack.

Additional features and advantages will be made apparent from the following detailed description that proceeds with reference to the accompanying drawings.

The following detailed description may be best understood when taken in conjunction with the accompanying drawings, of which:.

The following description relates to the utilization of shadow stack data for purposes other than the protection and security of a computing device, namely to render more efficient and more accurate the analysis of unintended consequences that occur during the execution of computer-executable instructions. A verified stack trace can be generated by utilizing information contained in the shadow stack. The shadow stack contains return addresses which are obtainable without requiring an unwinding of the traditional call stack. As such, triaging based on return address information can be performed more quickly and more efficiently, and with a reduced utilization of processing resources. Additionally, the generation of a verified stack trace can be performed, with such a verified stack trace containing return addresses that are known to be correct and not corrupted. The return addresses can either be read from the traditional call stack, or derived therefrom, and then verified by comparison to corresponding return addresses from the shadow stack, or they can be read directly from the shadow stack.

Although not required, the description below will be in the general context of computer-executable instructions, such as program modules, being executed by a computing device. More specifically, the description will reference acts and symbolic representations of operations that are performed by one or more computing devices or peripherals, unless indicated otherwise. As such, it will be understood that such acts and operations, which are at times referred to as being computer-executed, include the manipulation by a processing unit of electrical signals representing data in a structured form. This manipulation transforms the data or maintains it at locations in memory, which reconfigures or otherwise alters the operation of the computing device or peripherals in a manner well understood by those skilled in the art. The data structures where data is maintained are physical locations that have particular properties defined by the format of the data.

Generally, program modules include routines, programs, objects, components, data structures, and the like that perform particular tasks or implement particular abstract data types. Moreover, those skilled in the art will appreciate that the computing devices need not be limited to conventional personal computers, and include other computing configurations, including servers, hand-held devices, multi-processor systems, microprocessor based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, and the like. Similarly, the computing devices need not be limited to stand-alone computing devices, as the mechanisms may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.

With reference to <FIG> and <FIG>, exemplary systems <NUM> and <NUM> are illustrated, providing context for the descriptions below. More specifically, the exemplary systems 101and <NUM> illustrate an intended operation of a shadow stack, such as the exemplary shadow stack <NUM>, namely to prevent the execution of malicious computer-executable instructions, and otherwise protect the computing device.

Turning first to the exemplary system <NUM> illustrated in <FIG>, the exemplary system <NUM> is shown as comprising a computing device, such as the exemplary computing device <NUM>. The exemplary computing device comprises one or more microprocessor-based processing units, such as the ubiquitous Central Processing Unit (CPU). One or more CPUs are represented by the exemplary CPU <NUM> shown in <FIG>. On modern computing devices, the execution of computer-executable instructions is performed within the context of multiple execution threads, such as the exemplary threads <NUM>. When a thread, such as the exemplary thread <NUM>, is to be executed by the CPU <NUM>, the thread is loaded from a computer-readable storage medium, such as the exemplary memory <NUM>, onto the CPU <NUM>. In the exemplary system <NUM>, the loading of the exemplary thread <NUM> onto the CPU <NUM> is illustrated by the action <NUM>.

The execution of a thread by the CPU <NUM> entails the performance of individual computer-executable instructions, such as the exemplary computer-executable instructions <NUM>. An instruction pointer, such as the exemplary instruction pointer <NUM>, of the CPU <NUM>, identifies an instruction to be executed. In the exemplary system <NUM>, the exemplary instruction <NUM>, identified by the instruction pointer <NUM>, can be a CALL instruction, or other like instruction that results in a jump <NUM> in the execution of the computer-executable instructions <NUM> from the instruction <NUM>, to a different, nonconsecutive instruction, such as the exemplary instruction <NUM>. As part of the CALL instruction <NUM>, a return address, such as the exemplary return address <NUM>, is written onto a call stack, such as the exemplary call stack <NUM>, which is associated with the execution of the computer-executable instructions <NUM> within the context of the executing thread <NUM>. As utilized herein, the term "stack", by itself, means any hardware or software implemented structure that temporarily stores data in a first-in-last-out format. Within the context of processing units, such as the CPU <NUM>, a "stack", as that term is utilized herein, means the hardware processing unit support for the temporary receipt, storage and subsequent provision of return addresses, function-local data, function parameters and other like information. The term "call stack", as utilized herein, means a data structure that comprises at least one or more return addresses. A "call stack" can optionally also include additional parameters, function-local data, and other like information. The term "stack trace", as utilized herein, means the reconstruction of an execution flow by discovering the values of return addresses placed onto a call stack. A "stack trace" can further include the reconstruction of an execution flow by discovering other values placed onto a call stack, such as additional parameters, function-local data, and other like information. The terms "stack trace" and "backtrace" all have the same meaning as utilized herein and the verbs "stack tracing", "backtracing" and "stack unwinding" all have the same meaning as utilized herein, namely the generation of the aforedefined "stack trace". The writing of the return address <NUM> onto the call stack <NUM> is illustrated by the action <NUM>, which is performed as part of the execution of the instruction <NUM> by the CPU <NUM>. Within the exemplary system <NUM>, the return address <NUM> is illustrated as identifying the address of the instruction <NUM>. Once the execution of the computer-executable instructions (to which execution jumped after the execution of the instruction <NUM>) is completed, the execution will return to the address specified by the return address <NUM> and continue instruction therefrom. Thus, in the exemplary system <NUM>, the execution will return to the computer-executable instruction <NUM>, as identified by the return address <NUM>, an execution of the computer-executable instructions <NUM> by the CPU <NUM> will continue therefrom.

Because a stack, such as the exemplary call stack <NUM>, is a data structure maintained in read/write memory, the data stored therein is subject to being overwritten. In some instances, such overwriting is maliciously performed. For example, if a return address, such as the exemplary return address <NUM>, is modified to identify different computer-executable instructions, such as malicious computer-executable instructions, then many known mechanisms for preventing the execution of such malicious instructions are bypassed, and the malicious instructions will be executed, despite efforts to prevent their execution.

One mechanism to modify portions of a stack, including return addresses stored thereon, takes advantage of poorly designed computer-executable instructions that allow the modification of data without verification as to size or boundary. More specifically, malicious computer-executable instructions attempt to store a value, utilizing allowed commands, with the size of the value that is attempted to be stored being substantially greater than the size that was expected or allowed for by the existing mechanisms. In such an instance, if such a large value is, in fact, written to memory, it will exceed the portion of memory set aside for it and will "overrun" that portion and, thereby, cause modification to subsequent sections of memory. If one such subsequent section comprises the return address of a stack, the return address will modified, including being modified to identify a new location in memory.

To prevent such overrun mechanisms from being utilized to bypass other protections and trigger execution of malicious computer-executable instructions, modern CPUs, and other like microprocessors, have been modified to include mechanisms by which return addresses written to a stack are protected, including through hardware-based protections. Such protection mechanisms include the utilization of a second stack data structure whose contents are protected from being improperly overwritten by hardware-based protections. Such a second stack data structure is referred to as a "shadow stack".

Turning back to <FIG>, the exemplary CPU <NUM> includes so-called "Control-flow Enforcement Technology" or "CET" (also called "Hardware-enforced Stack Protection" or "HSP") and, as such, includes hardware mechanisms that utilize a shadow stack, such as the exemplary shadow stack <NUM>. Moreover, the data stored in the shadow stack <NUM> is hardware protected, as illustrated by the protections <NUM>. When a CPU having control-flow enforcement technology executes an instruction that places a return address on a call stack, such as the execution of the exemplary CALL instruction <NUM>, resulting in the placement of the return address <NUM> on the exemplary call stack <NUM>, the CPU <NUM> further copies that return address <NUM> to the shadow stack <NUM>. As illustrated in the exemplary system <NUM>, such a copy <NUM> results in a copy of the return address <NUM>, in the form of the return address <NUM>, being stored as part of the shadow stack <NUM>. Although illustrated as being copied from the call stack <NUM>, the return address <NUM> can be written onto the shadow stack <NUM> approximately, or exactly, concurrently with the writing of the return address <NUM> onto the call stack <NUM> by the execution of the CALL instruction <NUM> by the CPU <NUM>.

Turning to the exemplary system <NUM> shown in Figure 2b, the utilization of the shadow stack <NUM>, and the data stored thereon, to prevent the execution of malicious computer-executable instructions, and to further protect the computer system, is illustrated. More specifically, in the exemplary system <NUM>, the return address <NUM> that was placed on the call stack <NUM> by the execution of the CALL instruction <NUM>, as illustrated exemplary system <NUM>, has been replaced with a malicious address <NUM> that points to, or otherwise identifies, malicious computer-executable instructions, such as the exemplary malicious computer-executable instructions <NUM>.

As indicated previously, such a malicious address <NUM> can have been written onto the call stack <NUM> either intentionally (e.g., code obfuscation techniques), or due to a bug (e.g., an overrun of data written to another destination that was not properly range-bound, use-after-free bugs, or type-confusion bugs), or other like mechanisms. In some situations, a modification of the call stack <NUM> will have occurred while the call stack <NUM> was stored in memory <NUM> as part of the execution thread <NUM>, such as when the execution thread <NUM> was temporarily stored in the memory <NUM> while a different execution thread was being executed by the CPU <NUM>.

The subsequent restoring of the execution thread <NUM> to the CPU <NUM>, as illustrated by the action <NUM> can result in execution resuming with a computer-executable instructions, such as the exemplary computer-executable instruction <NUM>. The exemplary computer-executable instructions <NUM> can be a RET instruction, which "pops" a return address off of the call stack <NUM> and continue execution with the computer-executable instructions identified by the return address. In the specific example illustrated in the systems <NUM> and <NUM>, if the return address <NUM> was still stored on the call stack <NUM> when the RET instruction <NUM> was executed, the popping of the return address <NUM> off of the call stack <NUM> would have resulted in execution of the computer-executable instructions <NUM> proceeding with the instruction <NUM>, since that instruction was identified by the return address <NUM> as illustrated by the exemplary system <NUM>. However, in the exemplary system <NUM>, the exemplary malicious address <NUM> does not identify the exemplary instruction <NUM>, but rather identifies the exemplary malicious computer executable instructions <NUM>. Consequently, when the RET instruction <NUM> is executed, and the malicious address <NUM> is read from the call stack <NUM>, as illustrated by the action <NUM>, processing will proceed with execution of the malicious computer-executable instructions <NUM>.

To prevent the above-described attack vector, the exemplary CPU <NUM> implements the aforementioned CET (or HSP), in the form of the shadow stack <NUM>. More specifically, and as illustrated by the exemplary system <NUM>, the writing of the return address <NUM> onto the call stack <NUM> results in the writing of the same return address (assigned the number <NUM> in <FIG> and <FIG> to signify that it is a different copy) onto the shadow stack <NUM>. Subsequently, when an instruction, such as the exemplary RET instruction <NUM> is executed, prior to execution proceeding with the execution of computer-executable instructions starting at the address identified on the call stack <NUM>, the CPU <NUM> compares the address stored on the call stack <NUM> with the corresponding address stored on the shadow stack <NUM>. In the exemplary system <NUM>, such a comparison <NUM> compares the malicious address <NUM>, which was maliciously inserted into the call stack <NUM> in the place of the previously stored return address <NUM>, to the return address <NUM> (which, as indicated, is a copy of the return address <NUM>). Such a determination reveals that the malicious address <NUM> differs from the return address <NUM>. Further execution can then be halted, such as by generating an error, and interrupt, or other like prevention of the further execution of the instructions identified by the malicious address <NUM> can be performed. Such prevention of the exemplary RET instruction <NUM> receiving the address <NUM> from the call stack <NUM>, and continuing execution from the address identified thereby, is graphically represented in <FIG> by the arrow <NUM>.

As can be seen, the shadow stack is part of the aforementioned CET (or HSP) that was implemented for the sole purpose of preventing the execution of malicious computer-executable instructions and protecting the computer system therefrom. The mechanisms described herein, however, utilize the shadow stack for an entirely different purpose. In particular, the mechanisms described herein utilize the shadow stack to improve debugging. As defined above, the term "bug" means the consequences that result from the execution of computer-executable instructions were not intended by the programmer, including due to faulty programming, unexpected interactions between different sets of computer-executable instructions, hardware failures, and other like causes of unintended consequences in the execution of computer-executable instructions.

In performing "debugging", attempts to identify the cause of the bug often include reconstruction of the call stack and analysis of data from the call stack, since such data can indicate the computer-executable instructions, subroutine, process, or other like construct that was being executed when the unintended consequence occurred. Reconstruction is difficult without debug symbols because guesses must be made as to which values in a stack are return addresses. Even with debug symbols, however, if there is stack corruption, reconstruction may be impossible as the stack values (including the call stack) may be unrelated to the original call stack values. This can be true even with only a single call stack value on the stack being overwritten, since it may be difficult or impossible to accurately reconstruct the call stack And, unfortunately, unintended consequences often include the corruption of data. As such, the information obtained from a call stack may not be accurate, since it may have been corrupted, lost, or otherwise be inaccurate and reconstruction of the call stack may be impossible.

Turning to <FIG>, the exemplary system <NUM> shown therein illustrates a verified stack trace generation component, such as the exemplary verified stack trace generation component <NUM>, which generates a verified stack trace, such as the exemplary verified stack trace <NUM>. In particular, the verified stack trace generation component <NUM> utilizes data from the shadow stack <NUM> to verify the correctness and accuracy of at least some of the data being presented in the verified stack trace <NUM> that is generated thereby, namely the return addresses.

A traditional stack trace is generated by obtaining the data on the call stack <NUM>, such as when an unintended consequence, exception or fault occurs during execution of computer-executable instructions. As illustrated in the exemplary system <NUM>, during execution of computer-executable instructions, a corresponding call stack can include return addresses, such as was detailed above. The exemplary call stack <NUM> is illustrated in the exemplary system <NUM> of <FIG> as comprising two return addresses, namely the exemplary return addresses <NUM> and <NUM>. In addition to return addresses, a call stack, such as the exemplary call stack <NUM>, can contain other stack data, such as the exemplary other stack data <NUM>, which can be data placed onto the call stack <NUM> by the execution of other computer-executable instructions, including values assigned to one or more variables, counters, or other like data structures. As detailed above, such other stack data <NUM> may not have been copied over and protected within the construct of the shadow stack <NUM>. However, the return addresses, such as the exemplary return addresses <NUM> and <NUM> will have corresponding copies in the shadow stack <NUM>, namely the exemplary return addresses <NUM> and <NUM>, respectively.

When generating the verified stack trace <NUM>, the verified stack trace generation component <NUM> verifies the correctness of information obtained from the call stack <NUM> by comparing that information to the corresponding information in the shadow stack <NUM>. More specifically, in the case of return addresses, such as the exemplary return addresses <NUM> and <NUM>, the verified stack trace generation component <NUM> compares those return addresses to the corresponding exemplary return addresses <NUM> and <NUM> from the shadow stack <NUM>. Such comparisons are graphically represented in <FIG> as the comparisons <NUM> and <NUM>. According to one aspect, hardware mechanisms implemented by the CPU are utilized to perform the comparisons <NUM> and <NUM> in the same manner as such comparisons would be performed when a return address was read from the call stack, such as in the context of the exemplary system <NUM> described above. According to another aspect, however, the comparisons <NUM> and <NUM> are performed via software, such as through existing software-invocable interfaces by which data can be obtained from the shadow stack <NUM>.

If the comparisons, such as the exemplary comparisons <NUM> and <NUM>, reveal that the return addresses <NUM> and <NUM>, from the call stack <NUM>, are the same as the corresponding return addresses <NUM> and <NUM> from the shadow stack <NUM>, then those return addresses are included in the verified stack trace <NUM>. For example, the comparison <NUM> is illustrated as determining that the return address <NUM>, from the call stack <NUM>, is the same as the corresponding return address <NUM> from the shadow stack <NUM>. Such a determination informs the provision <NUM> of the return address <NUM>, from the call stack <NUM>, into the verified stack trace <NUM> generated by the verified stack trace generation component <NUM>.

By contrast, if the comparisons of return addresses obtained from the call stack <NUM> reveal that the return addresses obtained from the call stack differ from the corresponding return addresses from the shadow stack, the correct return address from the shadow stack can be provided as part of the verified stack trace <NUM>. Thus, for example, the comparison <NUM> is illustrated as determining that the return address <NUM>, from the call stack <NUM>, is not the same as the corresponding return address <NUM> from the shadow stack <NUM>. For example, as a result of the bug that is being investigated, the return address <NUM> can have become corrupted, modified, deleted, or otherwise changed from the return address that was originally placed on the call stack <NUM>. However, as detailed above, because the shadow stack <NUM> is hardware protected, the data stored thereon, such as the return address <NUM>, did not change. Accordingly, the return address <NUM> represents the correct return address that should be provided for purposes of debugging. Therefore, the comparison <NUM>, revealing that the return address <NUM> is not correct, informs the provision <NUM> of the return address <NUM>, from the shadow stack <NUM>, as part of the verified stack trace <NUM>. As shown, therefore, the verified stack trace <NUM> comprises data from the call stack <NUM>, including the other stack data <NUM> that represents data that is part of the call stack <NUM> but is not duplicated in the shadow stack <NUM> by the hardware-implemented mechanisms described above. In addition, the verified stack trace <NUM> also comprises data from the shadow stack <NUM>, including, for example, the return address <NUM>, thereby correcting incorrect information, such as the exemplary corrupted return address <NUM> that was part of the call stack <NUM>.

While illustrated in the exemplary system <NUM> of <FIG> as replacing an incorrect address with a known correct address, the verified stack trace generation component <NUM> can implement alternative mechanisms in the event that a comparison, such as the exemplary comparison <NUM>, reveals that return address data differs between the call stack <NUM> and the shadow stack <NUM>. For example, it can be beneficial to know what the difference is, since the specific corruption, modification, or other like change experienced by the return address <NUM> can be useful in debugging. In such an instance, the verified stack trace generation component <NUM> can be set to provide both the return address <NUM> and the return address <NUM> in the verified stack trace <NUM>. According to one aspect, the return address <NUM> is explicitly indicated as being a known correct address, while the return address <NUM> is additionally provided for further debugging information.

In some instances, to obtain return addresses from the location stored the values of the call stack <NUM>, stack tracing, also referred to as "stack unwinding" or "stack backtracing" may have to be performed. Stack unwinding entails the utilization of information currently available from a stack to decipher specific information, such as the return addresses, based on the processing performed by the computer-executable instructions that were being executed prior to the obtaining of the stack data. Such stack unwinding operations are computationally expensive in that they consume additional processor cycles, memory requirements, and other like computational resources.

According to one aspect, therefore, the verified stack trace generation component <NUM> can avoid, or minimize, such stack unwinding by skipping the comparisons between the return addresses on the call stack <NUM> and the corresponding return addresses on the shadow stack <NUM>, such as the exemplary comparisons <NUM> and <NUM>. Instead, the verified stack trace generation component <NUM> can simply obtain the return addresses, such as the exemplary return addresses <NUM> and <NUM>, directly from the shadow stack <NUM>, without any need to unwind, reference, or compare to, the return addresses from the call stack <NUM>. The verified stack trace generation component <NUM> simply utilizes the return addresses obtained from the shadow stack <NUM> in the verified stack trace <NUM>. For the reasons detailed above, the return addresses obtained from the shadow stack <NUM> are known to be correct and unmodified, and, therefore, uncorrupted.

In generating the verified stack trace <NUM>, the verified stack trace generation component <NUM> can optionally generate an indication <NUM> that the verified stack trace <NUM> comprises return addresses whose correctness has been verified by reference to the shadow stack <NUM>. The generation of such an indication <NUM> is graphically illustrated by the action <NUM> in <FIG>. The indication <NUM> can be in the form of a textual indication that is presented to a user performing debugging with the verified stack trace <NUM>. Alternatively, or in addition, the indication <NUM> is accompanied by cryptographically-based indicators attesting to the truth of the verification, of the return addresses present in the verified stack trace <NUM>, by reference the shadow stack <NUM>.

In some instances, it can be desirable to minimize the processing of the data obtained from the call stack <NUM>, such as the aforedescribed replacement of return addresses from the call stack <NUM> that are determined to be incorrect with corresponding return addresses from the shadow stack <NUM> that are known to be correct. In such an instance, such processing can be performed only if a threshold level of data corruption or incorrectness is achieved. For example, as a precursor to performing the replacement of, for example, the return address <NUM> with the return address <NUM>, as illustrated by the action <NUM>, the verified stack trace generation component <NUM> first determines how many of the return addresses from the call stack <NUM>, such as the exemplary return addresses <NUM> and <NUM>, differ from their corresponding return addresses in the shadow stack <NUM>, such as the exemplary return addresses <NUM> and <NUM>, respectively. The subsequent replacing, such as the exemplary replacing <NUM>, of return addresses from the call stack <NUM> with return addresses from the shadow stack <NUM> is performed only if greater than a threshold quantity, or greater than a threshold percentage, of the return addresses obtained from the call stack <NUM> differ from the corresponding return addresses obtained from the shadow stack <NUM>.

In addition to providing verified stack trace generation to aid in debugging by providing known correct data, and identifying, and/or correcting known incorrect data, the mechanisms described herein provide further debugging advantages in the form of triaging efficiencies for debugging that is performed at a subsequent time. More specifically, on personal computing devices, it is common for software developers to execute computer-executable instructions, and then, upon determination that an unexpected consequence has occurred, performing debugging immediately thereafter. In such instances, a stack trace, such as from the call stack <NUM>, is immediately evaluated and analyzed for debugging purposes, potential causes of the bug are identified, potential ameliorative corrections are made, and the, now corrected, computer-executable instructions are again executed. Such a process can be repeated until the bug is resolved and the unexpected consequence no longer occurs.

However, in cloud computing environments, server computing environments or other like remote execution computing environments, it may be impractical or undesirable to perform debugging at the time that an unintended consequence occurs. Instead, in such instances, a collection of data is performed at the time that an unintended consequence occurs, and that data is subsequently evaluated for debugging purposes. Because debugging has not yet occurred, there is no known, or even suspected, cause for the bug. As a result, it is difficult to know in advance which data will be relevant to resolving the bug. Moreover, failure to retain the relevant data further hinders debugging efforts. Indeed, if the data that was retained does not include the relevant data, the retained data can be worthless. Accordingly, when data is collected for subsequent debugging purposes, a large, potentially overinclusive, set of data is collected including, for example, data from the call stack <NUM> and the shadow stack <NUM>, as well as information from the memory <NUM>, the CPU <NUM> and other like data. The collection of such data is referred to as a data "dump". In certain computing environments, such as cloud computing environments, a data dump can be many gigabytes in size. Accordingly, it is desirable that at least an initial analysis of data dumps be promptly performed and, if possible, triaging be performed based on such an initial analysis. Often due to the quantity of data being generated, and the frequency with which it is generated, such initial analysis is automated.

In particular, known issues, or bugs, can be catalogued for subsequent resolution. To facilitate the debugging of such bugs, analysis can be undertaken of multiple data dumps associated with a single catalogued bug. By way of a simple example, if the presentation of a drop-down font menu on a cloud-hosted word processor results in display fragmentation, the identification of such an unintended consequence can be in the form of a catalogued bug that can be associated with a description of the unintended consequence, and can further be associated with multiple data dumps that can subsequently be analyzed to perform debugging and resolve the bug. In many instances it is easier to identify characteristics of the bug, such as the presence of specific data structures in specific locations in memory, then it is to identify the causes of the bug. As a result, the characteristics of a known, catalogued bug can be utilized to identify data dumps that are associated with that known bug. As a greater quantity of data dumps associated with a known, catalogued bug are obtained, debugging may be made easier, such as by the identification of common factors, or the elimination of diverse factors as potential causes of the bug.

Turning to <FIG>, the exemplary system <NUM> shown therein illustrates an exemplary utilization and extension of the above-described mechanisms to perform triaging more quickly, more efficiently, and with a reduced consumption of computational resources. More specifically, the exemplary system <NUM> shown in <FIG> comprises one or more computing devices, such as the exemplary computing devices <NUM>, <NUM> and <NUM>, which are communicationally coupled, such as through the exemplary network <NUM>. While illustrated as separate physical devices, the exemplary computing devices <NUM>, <NUM> and <NUM> can be a single physical device executing multiple virtual computing devices, or can be a single physical device, or a single virtual device, having instances of dump files, triage components and stack generation components executing and stored thereupon.

Within the exemplary system <NUM>, one or more dump files, such as in accordance with the descriptions provided above, are stored in one or more computing devices. For example, the exemplary system <NUM> illustrates the exemplary dump files <NUM>, <NUM> and <NUM> as being generated, and stored, on the computing device <NUM>, which is an exemplary dump-generating computing device. Additionally, within the exemplary system <NUM>, one or more computing devices are executing automated triage components, such as the exemplary automated triage component <NUM> being executed by the computing device <NUM>, which is an exemplary dump-triaging computing device. As detailed above, the automated triage component <NUM> references previously identified characteristics to perform triaging. For example, the automated triage component <NUM> can compare information from the dump files <NUM>, <NUM> and <NUM> to the characteristics <NUM> determined to be indicative of a known, catalogued bug. If one or more of the dump files <NUM>, <NUM> and <NUM> is found to possess the characteristics <NUM>, the automated triage component <NUM> determines that that dump file is associated with the bug having the characteristics <NUM>, and can, accordingly, associate that dump file with that known, cataloged bug. Such an association can be stored in one or more bug databases. The exemplary system <NUM> of <FIG> illustrates one or more databases that can associate dump files with known, catalogued bugs, including database information <NUM> containing dump files associated with one known bug and database information <NUM> containing dump files associated with a different known bug. Subsequent debugging focusing on the bug whose information is catalogued with the database information <NUM> can reference such information and utilize the dump files linked thereto to perform debugging.

According to one aspect, and for the reasons detailed above, triaging can be performed substantially faster, and with the utilization of substantially fewer computing resources, if stack unwinding for the purpose of obtaining return addresses therefrom can be skipped and otherwise not performed. Accordingly, the automated triage component <NUM>, for example, initially focuses its evaluation of dump files only on those bug characteristics that are revealed in information that would be stored in a shadow stack, such as the aforedescribed return addresses. In such a manner, the automated triage component <NUM> directly reads such information from the dump files' containing of the shadow stack data and compares such information to those bug characteristics, thereby reducing the expending of computational resources on the automated triaging, and, accordingly, performing the automated triaging more quickly and less expensively.

For example, the exemplary automated triage component <NUM> parses the dump file <NUM> and obtains therefrom shadow stack information. The exemplary automated triage component <NUM> then compares that shadow stack information to the corresponding characteristics of known, catalogued bugs, such as the exemplary characteristics <NUM> and <NUM>. If there is a match, the automated triage component <NUM> generates an association, such as through a database or other like data association structure and/or mechanism, between the known, catalogued bug whose characteristics matched the data from the shadow stack that was saved as part of the dump file <NUM>. Within the exemplary system <NUM> shown in <FIG>, the action <NUM> is a graphical representation of the determination, by the automated triage component <NUM>, that the dump file <NUM> comprises characteristics in its shadow stack data that match shadow stack data characteristics <NUM> of a known, catalogued bug, and the further association of the dump file <NUM> with that bug, such as via the generation of identifying or linking information between the dump file <NUM> and the database <NUM> by the automated triage component <NUM>. Similarly, the action <NUM> is a graphical representation of the determination, by the automated triage component <NUM>, that the shadow stack data of the dump file <NUM> matches shadow stack data characteristics <NUM> of the known, catalog bug, and the further association of the dump file <NUM> with that bug, such as via the generation of identifying or linking information between the dump file <NUM> and the database <NUM> by the automated triage component <NUM>.

In some instances, the shadow stack data in a dump file may not match any of the shadow stack data that is part of the characteristics of known, catalogued bugs. According to one aspect, in such instances, a slower automated triaging is then performed utilizing the other information in the dump file and comparing that other information to the characteristics of known, catalogued bugs. In such an aspect, shadow-stack-data-based comparisons are an initial automated triage that can be performed quickly and efficiently, as detailed, with traditional automated broader-characteristic-based being relegated to a subsequent automated triage that is performed only on those dump files that were not already associated with known, catalogued bugs by the initial, more efficient automated triaging. The exemplary automated triage component <NUM> can comprise capability that can perform both the initial, more efficient shadow-stack-data-based automated triaging and the subsequent, slower traditional broader-characteristic-based automated triaging. Alternatively, the exemplary automated triage component <NUM> can comprise only the capability that can perform the initial, more efficient shadow-stack-data-based automated triaging, with another, different component, either executing on the same computing device <NUM>, or executing on a different computing device, comprising the capability to perform the subsequent, slower traditional broader-characteristic-based automated triaging.

If the automated triaging does not identify a dump file as being associated with a known, catalogued bug, the dump file can be categorized as being associated with one or more unknown bugs, such as is graphically represented by the linking of the dump file <NUM> with the database <NUM>. The dump files so categorized can receive further scrutiny, such as by the verified stack trace generation component <NUM>, whose operation was described in detail above, and which can execute on a stack-trace-generating computing device, such as the exemplary stack-trace-generating computing device <NUM>. According to one aspect, the evaluation <NUM>, such as by the verified stack trace generation component <NUM>, is performed only after determination that the dump file is associated with an unintended consequence that has not been previously catalogued.

Although not specifically illustrated by the system <NUM> shown in <FIG>, according to one aspect, the generation of the dump files themselves, such as the dump files <NUM>, <NUM> and <NUM> can be conditioned upon an analysis of the shadow stack. In particular, and as detailed above, return addresses can be obtained from the shadow stack without the processing inefficiencies in unwinding the call stack to obtain return addresses. Accordingly, in the presently described aspect, the return addresses from the shadow stack can be efficiently obtained and compared with the characteristics of known, cataloged bugs. If such a comparison reveals that a particular unintended consequence, such as a particular occurrence of an exception, is associated with a known bug, then a reduced quantity of information can be collected for the dump file. For example, for a known, cataloged bug, specific information may be have been deemed to be useful to debugging the bug and such information can be specifically enumerated so that, if the pre-checking based on the shadow stack determines that the particular unintended consequence is associated with that bug, then the resulting dump file can contain only the specifically enumerated information, to the exclusion of other information that would have normally been included in a dump file. The resulting dump files can be captured more efficiently and can consume fewer memory storage resources.

Turning to <FIG>, the exemplary flow diagram <NUM> shown therein illustrates an exemplary series of steps that are performed by the verified stack trace generation component <NUM>. Initially, at step <NUM>, generation of a verified stack trace is triggered, such as by the occurrence of an unintended consequence, by the desire to evaluate dump files that are not associated with any currently known bug, or by another trigger. Subsequently, at step <NUM> return addresses in the call stack are compared to corresponding return addresses in the shadow stack. In some instances, such as when Address Space Layout Randomization ("ASLR") is utilized, return addresses will vary because the base address that an executable is loaded to varies. Therefore, the comparisons of step <NUM> may be made using the return address directly, or may be based on additional information that may be necessary to derive the correct return address. For example, if it is known that a system randomizes the top N address bits for ASLR, the analysis may consider only the lowest M bits, where the sum of N and M is less than or equal to the total bits in the address. Similarly, if each module has a unique value for its top N address bits, all return addresses having the same top N address bits can be known to originate from the same module. Thus, the comparison may require not only a single match, but that some sequence occurs. As detailed above, in an alternative aspect, the portion of stack unwinding performed to obtain return addresses from the call stack can be avoided for efficiency purposes and the generation of the verified stack trace can simply utilize the return addresses from the shadow stack without performing the comparison at step <NUM> and the subsequent steps.

At step <NUM>, a determination is made as to whether the comparison of step <NUM> detected differences. According to one aspect, if no differences were detected, then processing proceeds to step <NUM> and the verified stack trace is generated from the call stack, or, optionally, for efficiency purposes, simply from the return addresses of the shadow stack as already indicated. At step <NUM>, then, an indication is generated that the verified stack trace was generated utilizing shadow stack data. As indicated previously, such an indication is textual and can optionally comprise a certification or other like cryptographic seal, signature, or indicator of reliability. The relevant processing then ends at step <NUM>.

Conversely, if, at step <NUM>, it is determined that there are differences, then at least some of the return addresses in the call stack may be corrupted or otherwise have been changed and processing proceeds to step <NUM>. As an optional step, step <NUM> can condition the performance of the subsequent steps on whether an amount of return addresses that differ between the call stack and the shadow stack is greater than a threshold. If step <NUM> is performed, and it is determined that the amount of return addresses that differ between the call stack and the shadow stack is not greater than the threshold, then processing can skip the remaining steps and proceed, instead, to steps <NUM> and <NUM> as described above. For purposes of establishing a threshold against which the amount of return addresses that differ between the call stack and the shadow stack is compared at step <NUM>, a percentage can be utilized, an absolute quantity can be utilized, or combinations thereof.

At step <NUM>, a determination is made, such as by reference to a user established setting, as to whether the call stack version of return address and the shadow stack version of the return address are to both be presented as part of verified stack trace. If, at step <NUM>, it is determined that both should be presented, then processing proceeds to step <NUM> and the generation of the verified stack trace includes both the return address from the shadow stack, which can further optionally be indicated to be known to be correct, as well as the return address from the call stack, which can further optionally be indicated to be known to be incorrect, or, at least, to be different than the corresponding return address from the shadow stack. Conversely, if, at step <NUM>, it is determined that both do not need to be presented, then processing proceeds to step <NUM>, with the return address from the call stack being replaced with the known correct return address from the shadow stack. After either step <NUM> or step <NUM> processing proceeds to step <NUM> and, ultimately, ending at step <NUM>, as detailed above.

Turning to <FIG>, the exemplary flow diagram <NUM> shown therein illustrates an exemplary series of steps that are performed as part of a faster and more efficient automated dump triaging. As detailed above, such a faster and more efficient automated dump triaging can be performed as an initial triaging step, with a subsequent triaging step utilizing the more complete, but slower characteristic-based triaging of dump files. Initially, at step <NUM>, the faster and more efficient automated dump triaging is initiated. Subsequently at step <NUM>, characteristics of known, catalogued bugs are generated or are previously generated and then obtained at step <NUM>. For example, focusing only on shadow stack data, machine learning algorithms can be utilized to parse existing dump files and generate new characteristics, either for previously unknown bugs, or for currently known bugs, thereby supplementing or verifying current characteristics, or combinations thereof.

Subsequently, at step <NUM> dump files to be triaged are selected and, at step <NUM>, the characteristics of a bug are selected. At step <NUM>, focusing on shadow stack data, namely return addresses, the shadow stack data from the dump files obtained at step <NUM> is compared with corresponding data from the characteristics obtained at step <NUM>. Such a comparison can be a one-to-one comparison or it can focus only on specific bits or portions of the obtained return addresses or it can look for predetermined patterns or sequences among multiple return addresses. If there is a match, as determined at step <NUM>, the dump files obtained at step <NUM> are associated with the bug selected at step <NUM>, as illustrated by step <NUM>. Conversely, if there is no match, as determined at step <NUM>, processing proceeds to step <NUM> which loops back to step <NUM> and selects new bugs, and the corresponding characteristics thereof, so long as known, catalogued bugs, with known characteristics, remain to be iterated through utilizing the loop comprising the steps <NUM> and <NUM>. If processing proceeds through such a loop, and no match is detected at step <NUM>, then the dump files obtained at step <NUM> are associated with an unknown bug at step <NUM>. As indicated previously, prior to associating the selected dump files of step <NUM> with an unknown bug at step <NUM>, a subsequent automated dump triaging can be performed utilizing and comparing data from the dump files obtained at step <NUM> that goes beyond merely the shadow stack data, but requires greater processing resources to perform and is, thereby, slower. In addition, as also detailed above, shadow-stack evaluation, such as that of steps <NUM> through <NUM> can be performed as a preliminary determinant that can inform the generation of dump files in the first place. In such an instance, the relevant steps would exclude <NUM> through <NUM> and would, instead, commence with the reading of return addresses from the shadow stack upon occurrence of an unintended consequence, and the comparison loop of steps <NUM> through <NUM>. Performance of step <NUM> would, in addition, further trigger a more focused dump collection, collecting only the data specified to be relevant to the bug matched at step <NUM>. Conversely, performance of step <NUM> would result in an omnibus dump data collection, such as would normally be performed. Returning to the automated triaging of already existing dump files, subsequent to step <NUM>, step <NUM> loops back to step <NUM> and selects new dump files, so long as dump files remain to be iterated through utilizing the loop comprising the steps <NUM> and <NUM>. If processing proceeds through such a loop, and no further dump files remain to be automatically triaged, the relevant processing ends at step <NUM>.

Turning to <FIG>, an exemplary computing device <NUM> is illustrated which can perform some or all of the mechanisms and actions described above. The exemplary computing device <NUM> can include, but is not limited to, one or more central processing units (CPUs) <NUM>, a system memory <NUM>, and a system bus <NUM> that couples various system components including the system memory to the processing unit <NUM>. The system bus <NUM> may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. The computing device <NUM> can optionally include graphics hardware, including, but not limited to, a graphics hardware interface <NUM> and a display device <NUM>, which can include display devices capable of receiving touch-based user input, such as a touch-sensitive, or multi-touch capable, display device. Depending on the specific physical implementation, one or more of the CPUs <NUM>, the system memory <NUM> and other components of the computing device <NUM> can be physically co-located, such as on a single chip. In such a case, some or all of the system bus <NUM> can be nothing more than silicon pathways within a single chip structure and its illustration in <FIG> can be nothing more than notational convenience for the purpose of illustration.

The computing device <NUM> also typically includes computer readable media, which can include any available media that can be accessed by computing device <NUM> and includes both volatile and nonvolatile media and removable and non-removable media. Computer storage media includes media implemented in any method or technology for storage of content such as computer readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired content and which can be accessed by the computing device <NUM>. Computer storage media, however, does not include communication media. Communication media embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of the any of the above should also be included within the scope of computer readable media.

A basic input/output system <NUM> (BIOS), containing the basic routines that help to transfer content between elements within computing device <NUM>, such as during start-up, is typically stored in ROM <NUM>. By way of example, and not limitation, <FIG> illustrates operating system <NUM>, other program modules <NUM>, and program data <NUM>.

The computing device <NUM> may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only, <FIG> illustrates a hard disk drive <NUM> that reads from or writes to non-removable, nonvolatile magnetic media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used with the exemplary computing device include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and other computer storage media as defined and delineated above. The hard disk drive <NUM> is typically connected to the system bus <NUM> through a non-volatile memory interface such as interface <NUM>.

The drives and their associated computer storage media discussed above and illustrated in <FIG>, provide storage of computer readable instructions, data structures, program modules and other data for the computing device <NUM>. In <FIG>, for example, hard disk drive <NUM> is illustrated as storing operating system <NUM>, other program modules <NUM>, and program data <NUM>. Note that these components can either be the same as or different from operating system <NUM>, other program modules <NUM> and program data <NUM>. Operating system <NUM>, other program modules <NUM> and program data <NUM> are given different numbers hereto illustrate that, at a minimum, they are different copies.

The computing device <NUM> may operate in a networked environment using logical connections to one or more remote computers. The computing device <NUM> is illustrated as being connected to the general network connection <NUM> (to the network <NUM>) through a network interface or adapter <NUM>, which is, in turn, connected to the system bus <NUM>. In a networked environment, program modules depicted relative to the computing device <NUM>, or portions or peripherals thereof, may be stored in the memory of one or more other computing devices that are communicatively coupled to the computing device <NUM> through the general network connection <NUM>. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between computing devices may be used.

Although described as a single physical device, the exemplary computing device <NUM> can be a virtual computing device, in which case the functionality of the above-described physical components, such as the CPU <NUM>, the system memory <NUM>, the network interface <NUM>, and other like components can be provided by computer-executable instructions. Such computer-executable instructions can execute on a single physical computing device, or can be distributed across multiple physical computing devices, including being distributed across multiple physical computing devices in a dynamic manner such that the specific, physical computing devices hosting such computer-executable instructions can dynamically change over time depending upon need and availability. In the situation where the exemplary computing device <NUM> is a virtualized device, the underlying physical computing devices hosting such a virtualized computing device can, themselves, comprise physical components analogous to those described above, and operating in a like manner. Furthermore, virtual computing devices can be utilized in multiple layers with one virtual computing device executing within the construct of another virtual computing device. The term "computing device", therefore, as utilized herein, means either a physical computing device or a virtualized computing environment, including a virtual computing device, within which computer-executable instructions can be executed in a manner consistent with their execution by a physical computing device. Similarly, terms referring to physical components of the computing device, as utilized herein, mean either those physical components or virtualizations thereof performing the same or equivalent functions.

Claim 1:
A computing device comprising:
one or more central processing units that push return addresses onto both a call stack and a shadow stack, wherein a shadow stack is a second stack data structure whose contents are protected from being improperly overwritten by hardware-based protections; and
one or more computer-readable storage media comprising computer-executable instructions, which, when executed by at least some of the processing units, cause the computing device to:
compare (<NUM>) a first return address obtained from the call stack to a corresponding first return address obtained from the shadow stack; and
generate (<NUM>) a verified stack trace comprising both the first return address obtained from the shadow stack and the first return address obtained from the call stack when the comparing reveals (<NUM>) that the first return address obtained from the call stack differs from the corresponding first return address obtained from the shadow stack, and generate (<NUM>) the verified stack trace comprising the return addresses of the shadow stack when the comparing reveals (<NUM>) that the first return address obtained from the call stack does not differ from the corresponding first return address obtained from the shadow stack.