Determining a maximal set of dependent software updates valid for installation

• US 7,568,195 B2
• Filed: 05/01/2004
• Issued: 07/28/2009
• 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., Glaum, Jeffrey D., Markley, Michael E.
• Primary Examiner(s): Dam; Tuan Q
• Assistant Examiner(s): Wei; Zheng
• Application Number:
  US10/837,176
• Publication Number:
  US 20050132350A1
• Time in Patent Office: 1,914 Days
• Field of Search: 717/175, 717/170
• US Class Current: 717/175
• 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 system having an operating system installed, the operating system being divided into a plurality of discrete packages, and wherein a plurality of version updates are available to update a first package of the installed operating system, a method for selecting an optimal set of available versions to allow for maximal version updates of the first package in the fewest update steps possible, while honoring package dependency constraints, the method comprising:

downloading, to a mobile computing device, a collection of update packages for updating an operating system that is installed on the mobile computing device, wherein the operating system is divided into a plurality of discrete packages that may each be updated independently from the other packages, and wherein the collection of update packages includes a plurality of update packages that correspond to different versions of the installed first package of the installed operating system on the mobile computing device, and wherein each update package includes an associated manifest file that describes the contents and related dependency information of the update package, including the version of the update package;

for each package of the installed operating system on the mobile computing device, generating a graph having a node for the installed version of the package, the graph being generated from a manifest file corresponding to the installed version of the package;

for each of the update packages to be installed, accessing the associated manifest file to determine on which installed package the update package depends, wherein each update package may depend on an installed package by being directly dependent on the installed package or by being recursively dependent on another update package which in turn is dependent either directly on the installed package or on another update package, and upon determining on which installed package the update package depends, adding a new node to the graph, the new node corresponding to the version of the update package, such that upon adding a new node for each of the update packages, each graph is formed as a tree having the node for the installed version at the base of the graph and branches for each of the new nodes, each new node being linked to another node on which it depends, and each new node of the same graph corresponding to a different version of the installed package that the graph represents;

subsequent to generating the graphs, determining that the graph corresponding to the first package of the installed operating system includes two paths that each include a node corresponding to the highest final version to which the first package may be updated;

subsequent to identifying the two paths, traversing each path and validating each node traversed;

upon validating each node of both paths, selecting the path that has the lowest cost of installation wherein each version in a path has a cost of installation and wherein the cost of installation of each path comprises the sum of the cost of installation of each version in the path; and

installing the update package corresponding to each node of the selected path to update the first package of the installed operating system.

2. The method of claim 1 further comprising organizing the collection of update packages into coherent groups based on the currently installed package on the mobile computing device targeted by each update package.

3. The method of claim 1 wherein the path having the fewest nodes the path having the fewest nodes is selected.

4. The method of claim 1 wherein validating each node comprises accessing a file associated with the update package corresponding to the node to determine whether the file is a suitable type of package file.

5. The method of claim 1 wherein validating each node comprises determining whether the update package corresponding to the node contains an associated manifest file that describes the update package contents.

6. The method of claim 1, further comprising determining that none of the generated graphs correspond to the update package, and in response, generating a new graph, and adding a node corresponding to the version of the update package to the new graph.

7. The method of claim 1 wherein validating each node traversed comprises determining whether a certificate chain is associated with the given node via a parent node.

8. The method of claim 7 wherein a certificate chain is associated with the given node, and wherein validating each node traversed comprises verifying whether the package corresponding to the node contains a valid signature.

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

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

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

12. The method of claim 1 wherein selecting each version for installation comprises determining a partition corresponding to each version, and sorting each version into lists by adding each version to a respective list based on the corresponding partition for that version.

13. One or more computer-readable storage media storing computer-executable instructions which when executed perform the method of claim 1.

14. The computer-readable storage media of claim 13 wherein validating each node comprises accessing a file associated with the update package corresponding to the node to determine whether the file is a suitable type of package file.

15. The computer-readable storage media of claim 13 wherein validating each node comprises determining whether the update package corresponding to the node contains an associated manifest file that describes the update package contents.