Determining a maximal set of dependent software updates valid for installation

• US 20050132350A1
• Filed: 05/01/2004
• Published: 06/16/2005
• Est. Priority Date: 12/16/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shell, Scott R., Markley, Michael E., Glaum, Jeffery D.
• Granted Patent: US 7,568,195 B2
• Time in Patent Office: Days
• US Class Current: 717/168
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57

Abstract

Described is a system and method by which a collection of software packages for installing (e.g., on an embedded computing device) are reviewed for their dependent relations, whereby it is possible to choose a maximal set of install possibilities to allow for maximal version updates for any given package in the fewest update steps possible, while honoring package dependency constraints. An update validation process organizes and validates update packages that have been downloaded to a device, and builds a graph for each group. The graph data including paths between updates are processed to validate the updates and to determine a minimal and optimal set of packages that can be applied to the existing image on the device to produce the desired update, with the least amount of weight (cost) when more than one path can be used to get to the same version.

Claims

1. In a computing environment, a method comprising:

reviewing a collection of update packages that are ready to install on a device, including determining dependency relationships among the update packages and dependency relationships with package data from at least one other package already installed on the device; and

for package data to be updated, determining a set of at least one update package to install that will result in a maximal version of the package data being installed to the device.

2. The method of claim 1 wherein reviewing a collection of update packages that are ready to install on a device further comprises determining dependency relationships among the update packages with package data from at least one other package queued for installation on the device.

3. The method of claim 1 wherein at least two sets will result in the maximal version of the package being installed, and further comprising, selecting one of the sets based on a lowest cost of installation.

4. The method of claim 1 wherein determining a set of at least one package to install comprises building a graph having nodes representing the packages, and analyzing paths between the nodes, wherein the paths correspond to dependency relationships between the packages.

5. The method of claim 1 wherein reviewing a collection of update packages comprises validating each package.

6. The method of claim 5 wherein validating each package comprises determining whether a file is a suitable type of package file.

7. The method of claim 5 wherein validating each package comprises determining whether a file has an associated manifest file that describes the package contents.

8. The method of claim 1 further comprising, adding a node for each package to a package graph.

9. The method of claim 8 wherein adding a node for each package to a package graph comprises determining whether a package graph corresponding to that package already exists, and if so, adding the node to the existing package graph, and if not, creating an new package graph and adding the node to the new package graph.

10. The method of claim 8 further comprising, processing each branch in the package graph and processing each node in each branch to determine whether each node should remain in the package graph.

11. The method of claim 10 wherein to determine whether a given node should remain in the package graph, processing each node includes determining whether a certificate chain is associated with the given node via a parent node, and if not, removing the node by pruning the branch for that node from the package graph.

12. The method of claim 11 wherein a certificate chain is associated with the given node, and wherein to determine whether the given node should remain in the package graph, processing each node includes verifying whether the package corresponding the node contains a valid signature, and if not, removing the node by pruning the part of the branch starting at the given node from the package graph.

13. The method of claim 12 wherein the signature is valid for the given node, and further comprising, adding weighting data to the branch based on that node.

14. The method of claim 13 further comprising, traversing the package graph to find a lowest weighted branch, and adding information corresponding to that branch to an update list.

15. The method of claim 10 wherein at least one node remains in the package graph and wherein at least one remaining node is in a branch having an associated weight value, and further comprising, traversing the package graph to find a lowest weighted branch, and adding information corresponding to that branch to an update list.

16. The method of claim 15 further comprising adding packages to an update graph, and processing each package including determining a partition corresponding to each package having a representative node in the graph, and sorting each node into lists by adding each node to a respective list based on the corresponding partition for that node.

17. One or more computer-readable media having computer-executable instructions which when executed perform the method of claim 1.

19. The system of claim 1 wherein the update ordering component determines an update path for installing packages based on a lowest cost of installation.

20. The system of claim 19 wherein the validation component validates each package comprises by determining whether a file corresponding to that package is a suitable type of package file.

21. The system of claim 19 wherein the validation component validates each package comprises by determining whether a file has an associated manifest file that describes the package contents.

22. The system of claim 19 wherein the update ordering component determines the update path by building a graph having nodes representing package versions, and analyzing paths between the nodes that correspond to dependency relationships between the package versions.

23. The system of claim 19 wherein the update ordering component constructs edges between the nodes based on dependency information.

24. The system of claim 19 wherein the update ordering component adds a node for each package to a package graph by determining whether a package graph corresponding to that package already exists, and if so, adding the node to the existing package graph, and if not, creating an new package graph and adding the node to the new package graph.

25. The system of claim 24 wherein the update ordering component traverses the package graph to find a lowest weighted branch, and adds information corresponding to that branch to an update list.

18. In a computing device, a system comprising:

a validation component that provides information as to whether a package is valid for installation; and

an update ordering component configured to;

input information corresponding to an install set of at least one package for which installation is requested;

communicate with the validation component to eliminate packages from the install set that are not valid for installation;

determine dependency relationships with package data from packages already installed on the device and/or with packages queued for installation on the device; and

determine based on the dependency relationships at least one update package in the install set to install that will result in a maximal version of package data being installed to the device.