Usage-based program slicing

• US 9,239,716 B1
• Filed: 10/28/2013
• Issued: 01/19/2016
• Est. Priority Date: 03/22/2011
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Allen, Nicholas Alexander
• Primary Examiner(s): Wong, Don
• Assistant Examiner(s): MORSHED, HOSSAIN M
• Application Number:
  US14/065,270
• Time in Patent Office: 813 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3089 Monitoring arrangements determined by the means or processing involved in sensing the monitored data, e.g. interfaces, connectors, sensors, probes, agents software debugging using additional hardware using a specific debug interface G06F11/3656; performance evaluation by tracing or monitoring G06F11/3466
• CPC Class Codes: G06F 2201/865 Monitoring of software
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57
• CPC Class Codes: G06F 8/75 Structural analysis for program understanding

Abstract

In certain embodiments, execution traces for a program definition of an application are accessed. Probability information for components of the program definition is computed based at least in part upon the execution traces. Program definition slices are determined based at least in part upon the probability information. The program definition slices comprises a baseline slice and at least one supplemental slice. The baseline slice is communicated to a client in response to a request for the application. At least one supplemental slice is communicated to the client to allow the patching of the baseline slice with the at least one supplemental slice to recreate at least a portion of the program definition.

Claims

1. A system comprising:

one or more memory units operable to store a program definition of an application; and

a production endpoint having one or more processing units operable to;

receive a request from a client for the program definition; and

a proxy server having one or more processing units operable to;

generate an instrumented program definition by retrieving source code comprising at least a first program component and a second program component from the production endpoint and inserting tracing logic at one or more points associated with the first and second program components;

communicate the instrumented program definition over a network to the client that is remote from the one or more processing units, wherein the client is operable to generate at least a first execution trace indicating execution of the first program component and a second execution trace indicating execution of the second program component; and

receive the first and second execution traces over the network from the client, wherein the first execution trace provides first information for determining a baseline slice of the program definition and the second execution trace provides second information for determining a supplemental slice of the program definition.

2. The system of claim 1, wherein the tracing logic comprises at least a first tracing logic and a second tracing logic and:

the first tracing logic comprises a first callback routine operable when executed to instruct the client to communicate the first execution trace over the network to the one or more processing units; and

the second tracing logic comprises a second callback routine operable when executed to instruct the client to communicate the second execution trace over the network to the one or more processing units.

3. The system of claim 1, wherein the one or more processing units are further operable to determine a plurality of program definition slices of the program definition based at least in part upon the first and second execution traces, the plurality of program definition slices comprising the baseline slice and the supplemental slice.

4. The system of claim 3, wherein the plurality of program definition slices is determined by:

calculating one or more penalties for a plurality of candidate program slices, each penalty based at least in part upon a probability that execution of a first candidate program slice will trigger execution of a second candidate program slice, wherein a lower probability results in a lower penalty; and

selecting the baseline slice and the supplemental slice from the plurality of candidate program slices based at least in part on comparing the one or more penalties.

5. The system of claim 3, wherein the one or more processing units are further operable to:

communicate the baseline slice over the network to a second client in response to a request for the application;

communicate the supplemental slice over the network to the second client; and

wherein the client recreates at least a portion of the program definition using the baseline slice and the supplemental slice.

6. A method comprising:

accessing, by one or more processing units, a plurality of execution traces indicating execution of one or more components of an instrumented program definition by a remote client, the instrumented program definition created by a proxy server that retrieves source code from a production endpoint and inserts tracing logic into the source code;

determining, by the one or more processing units, a baseline slice of the program definition based at least in part on the plurality of execution traces, the baseline slice comprising a first subset of a plurality of program components of the program definition;

determining, by the one or more processing units, at least one supplemental slice of the program definition based at least in part on the plurality of execution traces, the at least one supplemental slice comprising a second subset of the plurality of program components; and

storing, by the one or more processing units, the baseline slice of the program definition and the at least one supplemental slice of the program definition, wherein the baseline slice is executable by a client that is remote from the one or more processing units and is configured to invoke the at least one supplemental slice during execution;

communicating, by the one or more processing units, the baseline slice to the client; and

communicating, by the one or more processing units, the at least one supplemental slice to the client.

7. The method of claim 6, further comprising:

inserting, by the one or more processing units, a function stub for a function definition into the baseline slice, wherein the function definition is included in the supplemental slice.

8. The method of claim 7, wherein the function stub is configured to invoke a program loader that patches the function definition of the supplemental slice into the baseline slice.

9. The method of claim 6, further comprising:

determining a plurality of candidate partitioning schemes, each candidate partitioning scheme comprising a plurality of respective candidate program slices;

calculating a penalty for each candidate partitioning scheme; and

selecting a first candidate partitioning scheme having a penalty that is lower than a second candidate partitioning scheme, wherein the selected first candidate partitioning scheme defines the baseline slice and the supplemental slice.

10. The method of claim 9, wherein calculating the penalty for each candidate partitioning scheme comprises:

calculating a sub-penalty for each respective candidate program slice of the candidate partitioning scheme; and

calculating the penalty as a sum of each sub-penalty.

11. The method of claim 9, wherein the penalty for each candidate partitioning scheme is calculated based at least on:

size information indicating the sizes of the respective candidate program slices of the candidate partitioning scheme; and

probability information indicating a probability that execution of one or more program components of a respective candidate program slices will cause execution of one or more program components of another respective candidate program slice.

12. The method of claim 11, wherein each size information is weighted by a first weight factor and each probability information is weighted by a second weight factor.

13. The method of claim 9, further comprising determining first and second sub-slices, wherein the first and second sub-slices are slices of the supplemental slice.

14. The method of claim 13, further comprising:

determining a plurality of secondary candidate partitioning schemes, each secondary candidate partitioning scheme defining secondary slices of the supplemental slice;

calculating a penalty for each secondary candidate partitioning scheme; and

selecting the secondary candidate partitioning scheme having the lowest penalty, wherein the selected secondary candidate partitioning scheme defines the first and second sub-slices.

15. The method of claim 6, further comprising:

receiving a first response over a network from the client, the first response comprising a first application message and a first execution trace; and

receiving a second response over the network from the client, the second response comprising a second application message and a second execution trace.

16. The method of claim 6, wherein one or more of the execution traces comprise:

a component identifier indicating a component of the instrumented program definition executed by the client; and

timing information indicating an elapsed time between execution of the instrumented program definition and execution of the component.

17. One or more non-transitory computer-readable media comprising logic, the logic when executed by one or more processing units operable to:

receive a request for an application over a network from a client that is remote from the one or more processing units;

create, at a proxy server, an instrumented program definition by retrieving source code from a production endpoint;

create, at the proxy server, a baseline slice and at least one supplemental slice using the instrumented program definition;

access the baseline slice of a program definition of the application in response to the request;

communicate the baseline slice over the network to the client;

access at least one supplemental slice of the program definition, wherein the at least one supplemental slice is based at least in part on a plurality of execution traces indicating execution of one or more components of an instrumented program definition by the client; and

communicate the at least one supplemental slice over the network to the client to allow patching of the baseline slice with the at least one supplemental slice to recreate at least a portion of the program definition.

18. The media of claim 17, the logic further operable when executed by the one or more processing units to receive a second request over the network from the client, wherein accessing the at least one supplemental slice and communicating the at least one supplemental slice to the client occur in response to the second request.

19. The media of claim 17, wherein communication of the at least one supplemental slice to the client begins after communication of baseline slice to the client is complete.

20. The media of claim 17, wherein communication of the at least one supplemental slice to the client begins before communication of baseline slice to the client is complete.