Intermediate representation construction for static analysis

The analysis of an intermediate representation of source or program code. An initial version of an initial representation of the source or program code is accessed and statically analyzed. For one or more portions of this initial version, the analysis component queries an analysis-time resolution component that provides supplemental intermediate representations corresponding to the portion. This supplemental intermediate representation provides further clarity regarding the portion, and is analyzed. If defects are found, they may be reported.

BACKGROUND

In order to generate high quality software programs, it is important to test and analyze the functionality of the software program. Dynamic analysis involves actually running the program on well-chosen examples to verify actual behavior of the program. However, it is not always practical to perform dynamic analysis, especially when the individualities of the environment in which the program will be run are not known or are varied. Dynamic analysis is further performed only when the program is completed (possibly using stub classes and functions) and capable of being run.

Static analysis inspects the source or program code without running it. Path sensitive dataflow analysis attempts to exhaustively and precisely predict every path over an abstract domain. This is highly useful for diagnosing problems such as security or localizability problems. In such path sensitive dataflow analysis, a component called a “client” may collect data defined specifically for a problem that the client is suited to detect. The client is given a program in an intermediate representation, which consists of program statements and control flow edges. The client then computes outgoing state for every statement given incoming state.

However, the intermediate representation for some functions can be missing, too complex, or generic, causing the client to make more or less accurate assumptions, which can lead to the detection of false defects (“noise”) as well as non-detection of real defects.

Sometimes, only a part of the whole program is analyzed at a time, to make analysis scalable. In this case, missing external components can cause the tools to over-approximate the possible program behavior, leading them to find false defects (“noise), or miss real defects. For example, setting and getting a property of an externally defined class can cause noise when the tool thinks a value of a property could be different from the one which was set on the same defect path before.

Heavily used external components with well-known behavior, such as .Net or STL data structures, usually have code that is too complex or too large to be fully included in the analysis. However, they cause a significant amount of noise (or non-detection of real defects) if the analysis approximates them away completely by, for example, assuming anything is possible as a result of calling an external Application Program Interface (API). For example, a C++ STL map is usually implemented as a balanced tree. It can be prohibitively difficulty to induce from the complex mechanics of the various operations that, say, insert(“a”, 1) followed by retrieve(“a”) returns 1 (assuming no other code is running concurrently).

Generic functions in .Net form parameterized intermediate representation, in which statements are parameterized by a type. Such intermediate representation usually has generic-related statements, which may have a different meaning depending on the concrete instantiation. For example, creation of an object of parameterized type can mean allocation of a heap object and calling a constructor, for instantiations with reference types, or creating and initializing a stack variable, for instantiations with value types. The tools are forced then into a complicated logic of understanding the meaning of the generics-related statements depending on the concrete instantiation at each call to instantiated generic API.

BRIEF SUMMARY

At least one embodiment described herein relates to the analysis of an intermediate representation of source or program code. In accordance with one embodiment, an initial version of an initial representation of the source or program code is accessed and statically analyzed. For one or more portions of this initial version, the analysis component queries an analysis-time resolution component that provides supplemental intermediate representations corresponding to the portion. This supplemental intermediate representation provides further clarity regarding the portion, and is analyzed. If defects are found, they may be reported.

In accordance with one embodiment, an analysis-time resolution component receives queries from an analysis component that is statically analyzing an intermediate representation of a program. The analysis-time resolution component accesses information regarding the program that is used to generate a supplemental intermediate representation of the program that may more easily used to analyze the operation of the program.

This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.

DETAILED DESCRIPTION

In accordance with embodiments described herein, the analysis of an intermediate representation of source or program code is described. An initial version of an initial representation of the source or program code is accessed and statically analyzed. For one or more portions of this initial version, the analysis component queries an analysis-time resolution component that provides supplemental intermediate representations corresponding to the portion. This supplemental intermediate representation provides further clarity regarding the portion, and is analyzed. If defects are found, they may be reported. First, some introductory discussion regarding computing systems will be described with respect toFIG. 1. Then, the embodiments of the static analysis will be described with respect toFIGS. 2 through 4.

First, introductory discussion regarding computing systems is described with respect toFIG. 1. Computing systems are now increasingly taking a wide variety of forms. Computing systems may, for example, be handheld devices, appliances, laptop computers, desktop computers, mainframes, distributed computing systems, or even devices that have not conventionally considered a computing system. In this description and in the claims, the term “computing system” is defined broadly as including any device or system (or combination thereof) that includes at least one processor, and a memory capable of having thereon computer-executable instructions that may be executed by the processor. The memory may take any form and may depend on the nature and form of the computing system. A computing system may be distributed over a network environment and may include multiple constituent computing systems.

As illustrated inFIG. 1, in its most basic configuration, a computing system100typically includes at least one processing unit102and memory104. The memory104may be physical system memory, which may be volatile, non-volatile, or some combination of the two. The term “memory” may also be used herein to refer to non-volatile mass storage such as physical storage media. If the computing system is distributed, the processing, memory and/or storage capability may be distributed as well. As used herein, the term “module” or “component” can refer to software objects or routines that execute on the computing system. The different components, modules, engines, and services described herein may be implemented as objects or processes that execute on the computing system (e.g., as separate threads).

In the description that follows, embodiments are described with reference to acts that are performed by one or more computing systems. If such acts are implemented in software, one or more processors of the associated computing system that performs the act direct the operation of the computing system in response to having executed computer-executable instructions. An example of such an operation involves the manipulation of data. The computer-executable instructions (and the manipulated data) may be stored in the memory104of the computing system100. Computing system100may also contain communication channels108that allow the computing system100to communicate with other message processors over, for example, network110. The computing system100may also include a display112for displaying a user interface to a user.

FIG. 2illustrates an environment200that represents an example environment in which the principles described herein may be employed. All or portions of the environment200may be implemented on the computing system100ofFIG. 1or distributed across multiple of such computing systems.FIG. 3illustrates a flowchart of a method300for statically analyzing intermediate representations of source code. The methodology ofFIG. 3will now be described with frequent reference to the environment200ofFIG. 2.

In accordance with the method300ofFIG. 3, an initial version of an intermediate representation of source code is accessed (act301). At some point the initial representation was generated from the source code. While this generation of the intermediate representation may be performed by the same computing system that statically analyzes the intermediate representation, this is not necessary. Nevertheless,FIG. 2illustrates that the intermediate representation222is at some point generated using source code. For instance, the intermediate representation222may be generated by module221using any one of a number of different languages of source code. For instance, the source code211may represent the program written in the C# programming language, while the source code212may represent the program written in the C++ programming language. The vertical ellipses213symbolically represents that the intermediate representation222may be generated from source code in any language. As an example, the intermediate representation222may consist of primitive instructions (not necessarily program statements in the source code sense), and control flow edges for the program.

The initial version of the intermediate representation is then statically analyzed (act302). For instance, inFIG. 2, an analysis component231statically analyzes the intermediate representation. In the illustrated embodiment, one or more clients234perform the actual detection by evaluating the intermediate representation. Each client may be specifically designed and structured to detect a particular subset of one or more specific defects.

As the analysis component statically analyzes the intermediate representation, the analysis component may encounter certain portions for which it is difficult to infer, based on the intermediate representation alone, the operations that are occurring. Rather than make assumptions as this stage, the analysis component queries an analysis-time resolution component to help resolve the ambiguity. For instance, inFIG. 2, the analysis component231queries the just-in-time component232(also referred to as the analysis-time resolution component232) each time an unknown portion of the intermediate representation is encountered. In this sense, the portion is unknown to the analysis client(s)234. Examples of unknown code might be code that makes it unclear which code will be executed at runtime.

The acts performed by the analysis component in order to gain greater certainty are illustrated inFIG. 3as being contained by the box310. Specifically, the analysis component queries the analysis-time resolution component for clarification of the unclear portion of the intermediate representation (act311). In response, the analysis component231receives supplemental intermediate representation233from the analysis-time resolution component232(act312). The supplemental representation may be analyzed (act313) in conjunction with the initial version of the intermediate representation to gain more clarity.

As an example of an unclear portion of the intermediate representation, suppose that the source code specifies a method of a generic class that is parameterized by type. In that case, unless the type is known, the specific function cannot even be truly identified since the very nature of the function can change depending on the type that is provided as a parameter to the generic class instance. In this case, when the analysis component231queries the analysis-time resolution component, the unclear portion of the intermediate representation may be provided. Given knowledge of a generic method or a method of the generic class and the type to instantiate it with, the analysis-time resolution component may provide an intermediate representation of a specific instantiation of the method. In that case, the supplemental intermediate representation233is of a specific instantiation of the method.

As another example of a case in which the intermediate representation is unclear, suppose the program makes a function call to an external function that the analysis component231knows little or nothing about. In that case, the analysis-time resolution component233may understand that in this context, usually a specific function is called. Examples of this are provided below in which the external function Stream::Dispose( ) is called, and also in which the Stream::Dispose( ) function is generated. Based on knowledge of the specific function, the analysis-time resolution component233may then generate supplemental intermediate representation representing the specific external function. It is possible that the specific external function calls yet another function. That other function may be already represented by the intermediate representation, in which case, a further function query to the analysis-time resolution component233may not be necessary. Otherwise, a query may be made, and the process can be repeated recursively.

A C# code example will now be provided. The source code may include the following class definitions for a class called ReferenceTypeExample, and a class called ValueTypeExample:

The source code also includes a generic function as follows:

class GenericExample{/// <summary>/// Generic function, parameterized by type T/// which is required to have a default constructor/// T can be a value type or a reference type/// </summary>private T GenericFunction<T>( ) where T : new( ){T ret = new T( );return ret;}

Now suppose that there are two functions that call the general function called GenericFunction. The following function is called TestReferenceTypeInstantiation and calls the function GenericFunction instantiated with the ReferenceTypeExample class:

The following function is called TestValueTypeInstantiation and calls the function GenericFunction, but instantiated with the ValueTypeExample class:

Based on this source code, the following MSIL intermediate representation may be generated for GenericFunction:

Note in this example, there is a line that calls the CLR runtime function “System.Activator::CreateInstance<!!>( ). In this example, the function is special, in the sense that the function body does not exist and/or cannot be expressed at the C# source code level. Examples of such functions include C/C++ intrinsics as memset/memcpy and some CLR runtime functions. An example of this same generic function in Anvil IR (which is built from the MSIL shown above) is as follows:

Here, the line System.Activator::CreateInstance′1<!T> $L3(EH) is a specific function that is introduced by the runtime. The intermediate language may be replaced with the following different intermediate representation:

As another example, following intermediate representation may represent a specific instance of the GenericFunction instantiated with ValueTypeExample:

//// Jitted Anvil IR for GenericFunction<ValueTypeExample>// as generated by JIT at the callsite for GenericFunction in functionTestReferenceTypeInstantiation//// INITOBJECT translates to the call to the implicit default constructor (which body isalso generated by the JIT),// BOX has the usual BOX semantics of creating a wrapper object,// and CreateInstance reduces to a simple assignment.// Note that the BRANCH instruction is still there, but its false branch will never betaken,// which is easily detected by the analysis engine.///*FUNCTION[test] GenericExample::GenericFunction{grave over ( )}1<struct[test]ValueTypeExample> (size: 17)return =?ENTER thisret =?DECLAREt327 = ASSIGN &CS$0$0001= CALL [test]ValueTypeExample::$CTOR t327 $L3(EH)t285 = BOX <struct [test]ValueTypeExample> CS$0$0001 $L3(EH)t294 =?NE t285 0= BRANCH t294 true:$L11 false:$L23$L11= LABEL (references: 1)t328 = ASSIGN &CS$0$0001= CALL [test]ValueTypeExample::$CTOR t328 $L3(EH)t288- =? ASSIGN CS$0$0001$L23= LABEL (references: 1)ret = ASSIGN t288-t293 = ASSIGN retreturn = RETURN t293$L2=?EXIT (references: 0)$L3=?UNWIND (references: 3)*/

Both of the latter functions represent intermediate representations of different specific instantiations of the GenericFunction class.

As another example, the function may be a generic instantiation but there is no access to the generic version, or the function is not generic, but the body of the function cannot be accessed. In this case, pre-generated intermediate representation (sometimes approximately) models the well-known library functions. This includes the example of .Net Stream class in which the Dispose( ) function calls Close( ) which in turn calls the virtual function Dispose(bool). But the call to the Dispose(bool) function is not visible to the analysis if we only have the intermediate representation for a class derived from the stream. If the described behavior of .Net Stream class is unknown to the analysis, the following code seems to not dispose of the derived stream properly:

public static void Test01( ){using(var s = new MyStream( )){}// inner the stream is disposed properly here, since there is an implicitcall to Stream::Dispose( ), which calls Stream::Close( ), which callsMyStream::Dispose(bool), which disposes of the inner resources.}
To the client that is oblivious of the Stream implementation, the MyStream object seems not to be disposed of properly because the “using” clause will translate into the following code, where Stream::Dispose( ) is called in the final section instead of MyStream::Dispose(bool), which would dispose of the MyStream object properly:

public static void Test01( ){var s = new MyStream( )try{}Finally{s.Dispose( ); // inner the stream is disposed properly here, sincethere is an implicit call to Stream::Dispose( ), which callsStream::Close( ), which calls MyStream::Dispose(bool), which disposes ofthe inner resources.}}

The following code shows an example of MyStream class implementation used in the example above.

In this case, the following library function may assist in the generation of intermediate representations that provide the specific function. The generated code for the Stream class is shown in the following runtime.cs example.

Returning toFIG. 3, throughout the static analysis, the clients234generate a list of identified defects (act314). Potentially, the static analysis also yields corresponding intermediate representation portions giving rise to the defects. The defects (and potentially the corresponding intermediate representation) may then be visualized to a user (act315). For instance, the defects report may be visualized on display112.

Optionally, a runtime user interface223is also provided, which may perhaps also be displayed using display112. The user interface223allows a user to provide information to the analysis-time resolution component232that the analysis-time resolution component232may use to generate a supplemental intermediate representation for one or more of the at least one portion of the initial version of the intermediate representation. As an example, the information may include generic implementations of methods, so that the analysis-time resolution component232can instantiate them. This information may be provided using the display112or perhaps via files. For instance, the information may include generic implementations of methods, to that the analysis-time resolution component232can instantiate them.

FIG. 4illustrates a flowchart of a method400for the analysis-time resolution component to support a static analysis of source code by generating supplemental intermediate representation. The analysis-time resolution component232receives a query from the analysis component231(act401). As mentioned with respect toFIG. 3, this query may be generated perhaps when an unclear segment of the intermediate representation is encountered, as when perhaps a generic class or method or external function call is encountered.

In response to the query, the analysis-time resolution component accesses information that clarifies a process associated with the unclear portion (act402). Then the analysis-time resolution component generates a supplemental intermediate representation that corresponds to the portion using the accessed information (act403). The supplemental intermediate representation is then provided to the analysis component (act404).

Accordingly, the principles described herein permit for more complete and accurate static analysis of intermediate representations of source code without negatively impacting the development cost of the clients that use the intermediate representation to find defects. The present invention may be embodied in other specific forms without departing from its spirit or essential characteristics. The described embodiments are to be considered in all respects only as illustrative and not restrictive. The scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.