Microsoft Technology Licensing, LLC

Wolfram Schulte

Nikolai Tillmann

Wolfgang Grieskamp

Margus Veanes

Colin L Campbell

Henricus Johannes Maria Meijer

Barend Hermanus Venter

Erik Meijer

Christopher Lovett

Michael Barnett

Chia-Hsun Chen

Lev Borisovich Nachmanson

Matthew J Warren

Yuri Gurevich

Jonathan Paul De Halleux

Nikolaj Skallerud Bjorner

Manuel Alfred Fahndrich

Gavin Mark Bierman

John Thomas Erickson

Ethan K Jackson

Vinod Sridharan

Daniel J P Leijen

Sudipta Sengupta

Avner Y Aharoni

Oludare Victor Obasanjo

Brian M Grunkemeyer

David N Schach

Ralf Lammel

Lars Kuhtz

K Rustan M Leino

Dandan He

Michal J Moskal

Nicolas Kicillof

Feng Chen

Xianzheng Dou

Bart Jacobs

Erik C Mavrinac

Nikolai Tillman

Andreas Blass

Matthew J Wararen

Eunsuk Kang

Dries Vanoverberghe

Deduplication is integrated with software building and chunk storing. A dedup module includes dedup software, a build graph interface, and a chunk store interface. A dedup graph includes a portion of the build graph, and a portion that represents build artifact file chunks. The dedup software queries whether chunks are present in the chunk store, submits a chunk for storage when the chunk is not already present, and avoids submitting the chunk when it is present. Queries may use hash comparisons, a hash tree dedup graph, chunk expiration dates, content addressable chunk store memory, inference of a child node's presence, recursion, and a local cache of node hashes and node expiration dates, for example. A change caused by the build impacts fewer dedup graph nodes than directory graph nodes, resulting in fewer storage operations to update the chunk storage with new or changed build artifacts.

Chunk storage deduplication using graph structures

Technologies that allow for a significant reduction in the time required to incrementally build large computer programs, and increase in the scale of build systems that perform builds. The time reduction is caused by reducing the time required for processing systems in a distributed build system to acquire files needed for the respective processing system to perform their respective part of the build. The scale increase comes from relying on local processing systems instead of centralized processing systems. This is done by establishing a tier of cache locations on which appropriate files for a build may be found by the appropriate processing system. A system may be established that allows for the processor systems to validate that the files have not been tampered with by using signatures, and were appropriately identified.

Ordered cache tiering for program build files

A tracing just-in-time (TJIT) compiler system is described for performing parallelization of code in a runtime phase in the execution of code. Upon detecting a hot loop during the execution of the code, the compiler system extracts trace information from sequentially recorded traces. In a first phase, the compiler system uses the trace information to identify at least one group of operation components that can be operated on in a parallel manner. In a second phase, the compiler system provides instructions which allocate the group of operation components to plural processing resources. A native code generator module carries out those instructions by recompiling native code that directs the operation of a native system to perform parallel processing. The compiler system terminates a group if it encounters program data in a loop iteration that is not consistent with previously encountered predicated information (upon which it records a new trace in a sequential manner).

Automatic parallelization in a tracing just-in-time compiler system

A finite domain approximation for symbolic terms of a symbolic state is derived, given some finite domains for basic terms of the symbolic state. A method is executed recursively for symbolic sub-terms of a symbolic term, providing a domain over-approximation that can then be provided to a solver for determining a more accurate domain. The method can be applied to a wide array of system terms, including, for example, object states, arrays, and runtime types.

Approximating finite domains in symbolic state exploration

A design space exploration (DSE) system automatically discovers viable solutions within a design space. The DSE system operates by creating or receiving a design specification that is described using a design language. The design specification contains a collection of constraints that an acceptable architecture is expected to satisfy. The DSE system then symbolically executes the design specification to provide a logical formula. The DSE system then interacts with a theorem prover module to identify one or more solutions to the formula. Finally, the DSE system converts the solutions into a user-interpretable form (e.g., expressed in the format of the modeling language) for viewing by a user. Each solution pertains to an architecture that satisfies the collection of constraints. The DSE system ensures that the solutions are diverse by disfavoring any solution that is deemed similar to any solution that has been previously encountered.

Providing diverse solutions using design space exploration

A state component saves a present state of a program or model. This state component can be invoked by the program or model itself, thereby making state a first-class citizen. As the state of the program evolves from the saved state, the saved state remains for reflection and recall, for example, for testing, verification, transaction processing, etc. Using a state reference token, the saved state of the program or model can be accessed by the program or model. For example, the program or model by utilizing a state component, can return itself to the saved state. After returning to the saved state, a second execution path can be introduced without requiring re-execution of the actions leading to the saved state. In another example, the state space of an executing model is saved in order to generate inputs required to exercise a program or model.

State as a first-class citizen of an imperative language

An extension of symbolic execution for programs involving contracts with quantifiers over large and potentially unbounded domains is described. Symbolic execution is used to generate, from a program, concrete test cases that exhibit mismatches between the program code and its contracts with quantifiers. Quantifiers are instantiated using symbolic values encountered during a set of exhibited runs. In this setting, quantifier instantiation is limited to values supplied to or produced by a symbolic execution. Quantifier instantiation is controlled by performing a matching algorithm that uses run-time values of input and program variables in order to guide and limit the set of quantifier instantiations. With a sufficient set of instances, test cases are derived that directly witness limitations of the auxiliary assertions.

Symbolic runtime checking of quantified contracts

In one embodiment, a computer system provides an application programming interface (API) for augmenting an application API. A computer system receives software code written in a second programming language indicating a user's intention to augment an application API with contracts from a contract API written in a first programming language. The software code includes a reference to the contract API. The contracts include assertions indicating appropriate use of the application API. The computer system accesses portions of the contract API according to the reference in the software code and compiles the received software code and the referenced portions of the contract API into an intermediate language (IL) version of the software code. The IL version is in an intermediate language common to both the first programming language and the second programming language. The IL version includes the assertions indicating appropriate use of the application API.

Contract programming for code error reduction

A type system employing structural subtyping is disclosed herein. A core type system supports several structural types, such as stream, choice, intersection and sequence. Also part of the core type system is a new invariant type, which denotes values whose dynamic type is the same as its static type, and type restrictions for limiting a range of a base type. Furthermore, a streamlined structural version of delegates, called structural delegates and a validation method thereof are introduce into the type system. To further facilitate type safety, strict statically checked interface casts are introduced.

Core object-oriented type system for semi-structured data

A developer can declare one or more tasks as being replicable. A library manages all tasks that are accessed by an application, including replicable tasks, and further establishes a task manager during requested task execution. During execution, the library generates a plurality of worker threads, and each of the worker threads is assigned to be processed on one of a plurality of different central processing units. When one or more worker threads have finished processing assigned tasks, and other threads are still busy processing other tasks, the one or more idle worker threads copy over and process replicable tasks assigned to the other, busier worker thread(s) to help with processing. The system can also synchronize processing of the replicable task by the plurality of different worker threads and different processors to ensure no processing discrepancies.

Executing tasks through multiple processors that process different portions of a replicable task

Modeling protocols. A method includes accessing a number of model programs. Each model program includes computer-executable instructions. The computer-executable instructions describe the behavior of at least one of another program, system, or component. Model programs may be disjointed in that they have independent meaning or dependent in that they include at least one of a state variable, action, or precondition that is dependent on another model program to impart meaning to the model program. An output model program is composed by unification including substituting state variables into another of the model programs without executing the model programs. Traces are generated from the output model program. Each of the traces includes a path of labels. The labels describe actions of the output model program from an initial state to an accepting state where a run is allowed to stop. The traces are output to a user.

Feature oriented protocol modeling

The present invention provides systems and methods that isomorphically maps constructs between domain spaces (e.g., object, markup, relational and user interface domains). The systems and methods employ a mapping component that utilizes at least one suppress label(s), introduce label(s) and/or mediating schema to facilitate construct mapping. Examples of such mapping include transforming a named construct to an anonymous construct, a named construct to a named construct, an anonymous construct to a named construct, and an anonymous construct to an anonymous construct. In general, introduce labels can be utilized to provide names for anonymous constructs and/or modify existing names; suppress labels typically are utilized to suppress names such as introduced names or names a user desires to be suppressed; and mediating schema can be utilized to provide a default or user customized mapping to an intermediate schema before, during and/or after construct mapping.

Systems and methods that transform constructs from domain to domain

Symbolic execution identifies possible execution paths of a computer program or method, each having certain constraints over the input values. The symbolic execution also records updates of memory locations, e.g. updates of the fields of symbolic objects in the heap of an object oriented program, involving a description of the previous heap, the updated symbolic object, a field identification, and a newly assigned symbolic value. The symbolic execution can also record calls to summarized methods, involving a description of previous calls, an identification of the summarized methods, and its symbolic arguments. The behavior of summarized methods can be expressed by axioms. Axioms describe the relationship between summarized methods under certain conditions. Axioms can be generated from parameterized unit tests. A parameterized unit test is a method with parameters which executes a sequence of calls to methods of an implementation under test; it asserts constraints over the inputs and outputs of the calls. A software testing program receives a parameterized unit test of an implementation under test, and symbolically executes the parameterized unit test. It can re-use axioms generated from other parameterized unit tests, and use them to emulate summarized methods.

Symbolic execution of object oriented programs with axiomatic summaries

Techniques and tools are described for flattening nested streams. For example, a stream flattening tool processes nested streams on a stack to traverse the nested streams. The tool produces a flattened stream that enumerates the elements of the nested streams. In one embodiment, the tool initially pushes a stack frame onto the stack for a stream representing all of the nested streams. As the tool iterates across the 'active' stream having the frame on the top of the stack, the tool may encounter and produce elements in the 'active' stream. Or, the tool may encounter a nested stream and push a stack frame for the nested stream onto the stack, then continuing by iterating across the new active stream. The tool pops the stack frame for the active stream from the stack when the end of the stream is reached, or potentially earlier if handling a nested tail stream.

Fast flattening of nested streams

Growing community of inventors

Bellevue, WA, United States of America

Wolfram Schulte