Microsoft Technology Licensing, LLC

Other

Lev Borisovich Nachmanson

Margus Veanes

Wolfgang Grieskamp

Wolfram Schulte

Nikolai Tillmann

Colin L Campbell

Michael Barnett

Yuri Gurevich

Fabian Omar Winternitz

Timothy Garry Dwyer

Kael R Rowan

Stuart John Harding Kent

Jacqueline Lynette Reid

Nikolai Tillman

Andreas Blass

An interactive connector routing system and method for creating a connector between two shapes in a digital canvas or workspace that is based on a shortest path. The system and method avoid the use of a tangent visibility graph when possible to minimize computation time. When the graph is used, it is built one portion during pointing device events. Source and target ports are set and it is determined whether a valid simple path can be created between these ports. If no simple path exists, then the system and method build an extended tangent visibility graph during pointing devices events. Building the extended tangent visibility graph includes an iterative process that enlarges an active rectangle until it contains the necessary obstacles and shapes to generate the shortest valid path for the connector. The system and method also use finishing techniques to clean up and smooth the connector path.

Interactive connector routing between obstacles

A computer system identifies a source node that is to be connected to a target node, where the target node is connected to the source node using an edge that links a connection region associated with the source node to a candidate connection region of the target node. The computer system identifies candidate connection region constraints that place restrictions on where the candidate connection regions can be positioned on the target node and determines, based on the identified candidate connection region constraints, the position of each candidate connection region relative to the target node. At least two of the candidate connection regions are disconnected so that an edge's connection to the target node can change between the disconnected connection regions. The computer system also visually represents the position of each of the candidate connection regions of the target node.

Edge routing using connection regions

Techniques and tools for testing multi-threaded or distributed software systems are described. For example, a multi-threaded system is instrumented and executed to produce logs of events that are performed by each of its agents. The agent logs contain a totally ordered series of events per agent, as well as information about accesses to resources shared between the agents. With this information, a partial ordering of the events performed by all the agents is described for the execution. The agent logs are then multiplexed into one or more serialized event orderings, which can then be compared to a specification of the system in a conformance testing engine.

Conformance testing of multi-threaded and distributed software systems

Techniques and tools for generating test cases for methods or programs with input preconditions are described. For example, after finding feasible control flow paths for a tested method along with each path's associated input conditions, a new program is created which tests these conditions along with the precondition. By analyzing this new program's control flow graph, a class of test cases is found while avoiding inefficiencies created by doing complete searches of paths through the combined control flow graph of the precondition and the method. Additional efficiencies are introduced by partitioning a control flow graph for the precondition into branched and straight sections.

Generating test cases for software with complex preconditions

A computerized method creates test coverage for non-deterministic programs. The method receives a graph of edges and states representing a program under test, and creates a continuous cycle of edges that reaches each edge in the graph at least once. In one example, the method splits the continuous cycle into discrete sequences that end at edges reaching non-deterministic nodes in the graph, and verifies that the executing program conforms to the behavior represented by the discrete sequences. In another example, a method creates probabilistic strategies for reaching one or more vertices in a non-deterministic graph. The strategies provide a graph path with a high probability of reaching a desired vertex.

Non-deterministic testing

Techniques and tools for generating finite state machines ('FSMs') for a software system with asynchronous callbacks are described. For example, method invocations in a model of the software system are partitioned into observable and controlled method invocations. The controlled method invocations are those which can be run from a test harness while the observed method invocations are those which are observed asynchronously as they are invoked in the system. An FSM is created with observation and control nodes such that observable transitions are found from observation nodes and controlled transitions are found from control nodes. If a state of the model contains both controlled and observable invocations, a timeout transition is added to the FSM to give an implementation time to come up with an observed method invocation before continuing to controlled invocations.

Generating finite state machines for software systems with asynchronous callbacks

State spaces are traversed to produce test cases, or test coverage. Test coverage is a test suite of sequences. Accepting states are defined. Expected costs are assigned to the test graph states. Strategies are created providing transitions to states with lower expected costs. Linear programs and other approximations are discussed for providing expected costs. Strategies are more likely to provide access to an accepting state, based on expected costs. Strategies are used to append transitions to test segments such that the new test segment ends in an accepting state.

Extending test sequences to accepting states

Exploration algorithms are relevant to the industrial practice of generating test cases from an abstract state machine whose runs define the predicted behavior of the software system under test. Here, a new exploration algorithm allows multiple state groupings to simultaneously guide the search for states that are interesting or relevant for testing. In some cases, the algorithm allows exploration to be optimized from exponential to linear complexity. An extended example is included that illustrates the use of the algorithm.

State exploration using multiple state groupings

A change management method and system for tool-based document generation which incorporates tool input changes, tool changes, and user changes during iterative document creation. After a tool-based document is generated and saved by a tool, and then edited by a user, during a next iteration of creating the edited document, the tool first generates a new base document. The base document is then saved, and a three-way merge is performed on the former iteration's base document, this iteration's new base document, and the former iteration's edited document. The former iteration's base document serves as the base of the merge process. The merge outputs a merged document, and when further edits are needed, the merged document is edited, and saved as the edited document. If no edits are necessary, the merged document is saved directly as the edited document. In each iteration, the new base document and the edited document are saved for a possible next iteration.

Tool-based iterative document management

The technologies allow a digital content developer to define, and a user to switch between or select, various versions of digital content for purposes of displaying, rendering, improving, or testing digital content. For example, a source code developer inserts identifiers in source code, and a source code layer viewer displays code segment choices defined by the identifiers. A user (e.g., the developer or others) selects code segments for inclusion in a source code version. The technology is also useful for providing versions of media content such as audio, video, DVD, images, text, etc.

Growing community of inventors

Redmond, WA, United States of America

Lev Borisovich Nachmanson