News Column

Researchers Submit Patent Application, "Analysis of Propagated Information Using Annotated Forests", for Approval

July 3, 2014



By a News Reporter-Staff News Editor at Computer Weekly News -- From Washington, D.C., VerticalNews journalists report that a patent application by the inventors Kaler, Christopher G. (Sammamish, WA); Babang, Mayila (Renton, WA); Zhang, Xin (Bellevue, WA), filed on December 12, 2012, was made available online on June 19, 2014.

The patent's assignee is Microsoft Corporation.

News editors obtained the following quote from the background information supplied by the inventors: "In computing, a function is a segment of source code that performs a task. A function that calls another function is a caller or calling function. A function that is called by another function is a callee function. A call graph is a directed graph that represents calling relationships between callers and callees in a computer program. Each node in the call graph represents a function and each edge indicates a caller and a callee. For example, an edge (a,b) indicates that function a calls function b. Call graphs can be used for program analysis. For example, a call graph can be used to provide a visual that helps humans understand how a program works. Call graphs are typically used to detect errors in program execution. A forest is a directed graph comprised of a disjoint union of trees."

As a supplement to the background information on this patent application, VerticalNews correspondents also obtained the inventors' summary information for this patent application: "An annotated forest representing relationships between entities of a computing system can be analyzed to determine the effects of a particular condition or set of conditions on the computing system. An annotated forest representing a software system can be analyzed to determine the effects of a particular condition or set of conditions on the software system. Segments of program code of a software system can be annotated in the source code. A segment of program code can be a function or a block of code that has a particular capability or dependency, a data type or other code segment. A forest can be created directly or indirectly from the source code, wherein relationships between code segments are represented by parent and child nodes. Annotations associated with a child node can be propagated to its immediate parent and to all parents of the immediate parent and so on potentially all the way up to one or more root nodes of the annotated forest. Annotations associated with a child node can be repeatedly propagated to a parent node to a specified depth or place or at nodes with one or more particular characteristics or annotations. The propagation can be performed on-demand to all or some subset of nodes.

"A call forest representing relationships between segments of code of a software system where the segments of code are functions, can be created directly or indirectly from annotated source code. The call forest can represent multiple independent programs each of which is represented by a call tree. One or more annotations associated with a node representing a callee function represented by a child node can be associated with the node representing a caller function that calls the callee function, represented by a parent node of the child node. The one or more annotations associated with the caller function that calls the callee function can be associated with functions that call the caller function and so on potentially all the way up to one or more root nodes of the annotated call forest. The one or more annotations associated with the caller function that calls the callee function can be associated with functions that call the caller function to a specified depth or place or at nodes with one or more particular characteristics or annotations. The propagation can be performed on-demand to all or some subset of nodes. The annotated call forest can be analyzed by traversing the annotated call forest to determine how many functions call a callee function, which functions call a callee, entry points to access a particular function and so on. The analysis information can be provided in a tangible form such as but not limited to a list of functions, entry points, protocols, etc. which can be displayed on a screen, provided in a printed report, etc.

"A call forest representing relationships between segments of codes that are functions can be created directly or indirectly from one or more annotation files that associates callee functions with one or more annotations. The one or more annotations associated with a callee function in the annotation file(s) can be associated with the node in the call forest representing the callee function. The one or more annotations can be associated with a caller function that calls the callee function. The one or more annotations associated with the caller function that calls the callee function can be associated with functions that call the caller function and so on all the way up to one or more root nodes of the annotated call forest or to a specified depth or place or at nodes with one or more particular characteristics or annotations. The propagation can be performed on-demand to all or some subset of nodes.

"An annotated forest comprising a collection of message trees can be created. A message tree can represent a message and the derivation of the message. For example, a message tree can be created from an HTTP (HyperText Transfer Protocol) message extracted from one or more TCP (Transmission Control Protocol) messages extracted from one or more IP (Internet Protocol) messages extracted from one or more Ethernet packets in a messaging system. A forest can be created from the one or more message trees representing the messaging system. Nodes in the forest can be associated with annotations comprising information including but not limited to error messages to create an annotated forest. One or more annotations associated with a child node can be propagated up the annotated forest to the immediate parent nodes, and to parent nodes of those nodes and so on potentially all the way up to one or more root nodes of the annotated forest or to a specified depth or place or at nodes with one or more particular characteristics or annotations. The propagation can be performed on-demand to all or some subset of nodes.

"A forest comprising a collection of object and/or sub-object trees for a software system can be created. An object tree can represent an object and objects or sub-objects derived from the object. An object forest comprising a collection of objects and/or sub-objects for a software system can be created. An object forest can comprise a collection of object trees representing relationships between the objects and sub-objects in a software system. Nodes in the forest can be associated with annotations comprising information about the object that is to be tracked or correlated such as, but not limited to errors, usage patterns, particular conditions, requirements, security concerns, etc. One or more annotations associated with a child node can be propagated up the annotated forest to the immediate parent nodes, and to parent nodes of those nodes and so on potentially all the way up to one or more root nodes of the annotated forest or to a specified depth or place or at nodes with one or more particular characteristics or annotations. The propagation can be performed on-demand to all or some subset of nodes.

"A forest comprising a collection of type trees for a software system can be created. A type tree can represent a type and subtypes derived from the type. A type forest comprising a collection of types for a software system can be created. A type forest can comprise a collection of type trees representing relationships between all the types and subtypes in a software system. Nodes in the forest can be associated with annotations comprising information about the type that is to be tracked or correlated such as, but not limited to: errors, usage patterns, particular conditions, requirements, security concerns, etc. One or more annotations associated with a child node can be propagated up the forest to the immediate parent nodes, and to parent nodes of those nodes and so on potentially all the way up to one or more root nodes of the annotated forest or to a specified depth or place or at nodes with one or more particular characteristics or annotations. The propagation can be performed on-demand to all or some subset of nodes.

"This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

BRIEF DESCRIPTION OF THE DRAWINGS

"In the drawings:

"FIG. 1a illustrates an example of a system 100 that creates and/or analyzes an annotated forest in accordance with aspects of the subject matter described herein;

"FIG. 1b illustrates another example of a system 101 that creates and/or analyzes an annotated forest in accordance with aspects of the subject matter described herein;

"FIG. 2a illustrates an example of a method 200 that analyzes the propagation of information in a software system in accordance with aspects of the subject matter disclosed herein;

"FIG. 2b illustrates examples of callers and callees in accordance with aspects of the subject matter disclosed herein;

"FIG. 2c illustrates an example of a forest 256 created from the examples of FIG. 2b in accordance with aspects of the subject matter disclosed herein;

"FIG. 2d illustrates an example of an annotated forest 264 created from the forest of FIG. 2c in accordance with aspects of the subject matter disclosed herein;

"FIG. 2e illustrates another example of an annotated forest 266 created from the annotated forest of FIG. 2d in accordance with aspects of the subject matter disclosed herein;

"FIG. 2f illustrates another example of an annotated forest 270 created from the annotated forest of FIG. 2e in accordance with aspects of the subject matter disclosed herein;

"FIG. 3 is a block diagram of an example of a computing environment in accordance with aspects of the subject matter disclosed herein.

"FIG. 4 is a block diagram of an example of an integrated development environment (IDE) in accordance with aspects of the subject matter disclosed herein."

For additional information on this patent application, see: Kaler, Christopher G.; Babang, Mayila; Zhang, Xin. Analysis of Propagated Information Using Annotated Forests. Filed December 12, 2012 and posted June 19, 2014. Patent URL: http://appft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=%2Fnetahtml%2FPTO%2Fsearch-adv.html&r=213&p=5&f=G&l=50&d=PG01&S1=20140612.PD.&OS=PD/20140612&RS=PD/20140612

Keywords for this news article include: Software, Microsoft Corporation.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Computer Weekly News