Generating dependency graphs for analyzing program behavior

Patent metadata

Field	Value
Publication number	US-9727441-B2
Application number	US-201113208370-A
Country	US
Kind code	B2
Filing date	Aug 12, 2011
Priority date	Aug 12, 2011
Publication date	Aug 8, 2017
Grant date	Aug 8, 2017

Abstract

An analysis management system (AMS) is described that analyzes the in-field behavior of a program resource installed on a collection of computing devices, such as mobile telephone devices or the like. In operation, the AMS can instruct different devices to collect data regarding different observation points associated with the program resource, thus spreading the reporting load among the devices. Based on the data that is collected, the AMS can update a dependency graph that describes dependencies among the observation points associated with the program resource. The AMS can then generate new directives based on the updated dependency graph. The AMS can also use the dependency graph and the collected data to infer information regarding observation points that is not directly supplied by the collected data.

First claim

What is claimed is:

1. A method, implemented by physical and tangible computing functionality, for generating a dependency graph, comprising:
receiving a dependency graph that describes dependencies among observation points associated with a program resource;
determining at least one focus of investigation pertaining to the dependency graph based on at least one analysis factor;
generating at least one directive based on said at least one focus of investigation;
transmitting said at least one directive to at least one device;
receiving collected data from said at least one device in response to said at least one directive;
updating the dependency graph, if deemed appropriate, based on the collected data; and
repeating said determining, generating, transmitting, receiving collected data, and updating at least one time.

2. The method of claim 1 , wherein said at least one device comprises at least one mobile device.

3. The method of claim 1 , wherein at least one observation point pertains to a behavior or characteristic of the program resource.

4. The method of claim 1 , wherein at least one observation point pertains to a behavior or characteristic of hardware provided by said at least one device.

5. The method of claim 1 , wherein at least one observation point pertains to a context within which said at least one device operates, without being a property of the said at least one device itself.

6. The method of claim 1 , wherein the dependency graph that is initially received is produced by:
receiving initial dependency information that indicates candidate dependencies among the observation points;
generating a first dependency graph based on the initial dependency information; and
updating the first dependency graph based on collected data received from trial devices within a report-intensive trial phase of operation, to produce an initial dependency graph.

7. The method of claim 1 , wherein one analysis factor pertains to existence of an uncertain dependency hypothesis, as expressed in the dependency graph.

8. The method of claim 1 , wherein one analysis factor pertains to existence of an undiagnosed failure, associated with the collected data.

9. The method of claim 1 , wherein said generating at least one directive comprises:
generating a first set of directives to be transmitted to a first group of devices; and
generating a second set of directives to be transmitted to a second group of devices,
wherein the first group of devices at least partially differs from the second group of devices, and the first set of directives at least partially differs from the second set of directives.

10. The method of claim 1 , wherein said updating comprises:
determining whether the collected data conforms to the dependency graph; and
if the collected data does not conform to the dependency graph, updating the dependency graph so that the dependency graph is more conformant with the collected data.

11. The method of claim 1 , further comprising inferring information regarding at least one observation point based on the dependency graph in conjunction with the collected data.

12. The method of claim 1 , further comprising:
classifying behavior of the program resource based on available evidence associated with the program resource, to provide at least one conclusion; and
notifying an entity associated with producing the program resource of at least one of: (a) the available evidence; and (b) said at least one conclusion.

13. The method of claim 12 , wherein the available evidence comprises one or more of:
the collected data;
one or more inferences drawn from the collected data; and
the dependency graph.

14. The method of claim 1 , further comprising receiving at least one directive from an entity associated with producing the program resource.

15. An analysis management system, comprising:
a processor configured to:
maintain a dependency graph that describes dependencies among observation points associated with a program resource;
determine plural sets of directives to be sent to plural respective groups of mobile devices, wherein at least one set of directives at least partially differs from another set of directives; and
receive collected data from the plural groups of mobile devices in response to the plural sets of directives.

16. The analysis management system of claim 15 , further comprising updating the dependency graph based on the collected data, and generating updated sets of directives to be sent to the plural respective groups of mobile devices based on the collected data.

17. The analysis management system of claim 15 , further comprising
classifying behavior of the program resource based on available evidence associated with the program resource, to provide at least one conclusion; and
notifying an entity associated with producing the program resource of at least one of: (a) the available evidence; and (b) said at least one conclusion.

18. The analysis management system of claim 17 , wherein the available evidence comprises one or more of:
the collected data;
one or more inferences drawn from the collected data; and
the dependency graph.

19. A computer readable storage device for storing computer readable instructions, the computer readable instructions providing an analysis management system when executed by one or more processing devices, the computer readable instructions comprising:
logic for providing a dependency graph that describes dependencies among observation points associated with a program resource;
logic for determining at least one focus of investigation based on at least one uncertain dependency hypothesis, as expressed in the dependency graph;
logic for generating at least one directive based on said at least one focus of direction, to be transmitted to at least one device;
logic for receiving collected data from said at least one device in response to said at least one directive;
logic for classifying behavior of the program resource based on available evidence associated with the program resource, to provide at least one conclusion, the available evidence comprising:
the collected data;
one or more inferences drawn from the collected data; and
the dependency graph; and

logic for notifying an entity associated with producing the program resource of at least one of: (a) the available evidence; and (b) said at least one conclusion.

20. The computer readable storage device of claim 19 , further comprising logic for updating the dependency graph, if deemed appropriate, based on the collected data.

Assignees

• Agarwal Sharad
• Mahajan Ratul
• Zheng Alice X
• Bahl Paramvir
• Microsoft Technology Licensing Llc

Inventors

• Agarwal Sharad
• Mahajan Ratul
• Zheng Alice X
• Bahl Paramvir

Classifications

• G06F11/3604

  Analysis of software for verifying properties of programs (testing of software G06F11/3668) · CPC title

• G06F11/2257

  using expert systems · CPC title

• G06F11/0709

  in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems · CPC title

• G06F11/3612 Primary

  by runtime analysis (performance monitoring G06F11/3466) · CPC title

• G06F11/079

  Root cause analysis, i.e. error or fault diagnosis (in a hardware test environment G06F11/22; in a software test environment G06F11/36) · CPC title