Systems and Methods for Efficiently Authenticating Multiple Objects Based on Access Patterns

• US 20090019520A1
• Filed: 03/27/2008
• Published: 01/15/2009
• Est. Priority Date: 10/29/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yin, Jian, Iyengar, Arun Kwangil
• Granted Patent: US 8,127,134 B2
• Time in Patent Office: Days
• US Class Current: 726/2
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

Techniques for efficiently authenticating multiple objects and clustering objects based on access patterns are provided. For example, in an illustrative aspect of the invention, a technique for generating and/or reading authentication information, wherein the authentication information provides evidence that a plurality of objects were one of generated and sent by an entity, comprises using one or more object access patterns indicative of whether at least two of the plurality of objects are accessed within a similar time period to group objects together to reduce an overhead for at least one of generating and reading the authentication information.

Claims

1. A method for one of generating and reading authentication information, wherein the authentication information provides evidence that a plurality of objects were one of generated and sent by an entity, comprising the step of:

using one or more object access patterns indicative of whether at least two of the plurality of objects are accessed within a similar time period to group objects together to reduce an overhead for at least one of generating and reading the authentication information.

2. The method of claim 1, further comprising the step of determining the one or more object access patterns.

3. The method of claim 1, wherein the object access pattern using step further comprises an accessed object being one of an object being read and an object being updated.

4. The method of claim 1, wherein the object access pattern using step further comprises grouping objects together using at least one graph.

5. The method of claim 4, wherein the step of using at least one graph further comprises using at least one Merkle hash tree.

6. The method of claim 4, wherein the object grouping step further comprises placing two objects in a same graph if the objects have similar access patterns.

7. The method of claim 1, further comprising the step of maintaining a set of objects which are likely to be updated in close temporal proximity to each other.

8. The method of claim 7, wherein the maintaining step further comprises determining the set of objects using at least one of an object dependency graph, analysis of code generating a plurality of objects, and on-line analysis of change patterns of a plurality of objects.

9. The method of claim 1, further comprising the step of maintaining a set of objects which are likely to be read in close temporal proximity to each other.

10. The method of claim 9, wherein the maintaining step further comprises determining the set of objects using at least one of analysis of code which reads a plurality of objects and analysis of read patterns of a plurality of objects.

11. The method of claim 1, further comprising the step of partitioning objects into authentication groups using write sets with a weight exceeding a threshold.

12. The method of claim 1, further comprising the step of partitioning objects based on read sets.

13. The method of claim 1, wherein objects are placed in authentication groups and a size of an authentication group can be adjusted to trade off central processing unit overhead and signature size.

14. The method of claim 1, further comprising the step of assigning an object to a plurality of authentication groups in order to reduce client overhead.

15. The method of claim 1, further comprising the step of using an old version of a signature of an object if the object has not changed.

16. The method of claim 1, further comprising the step of exploring an object read order to reduce a size of authentication information transferred across a network.

17. The method of claim 1, further comprising the step of a client caching a signature of a previously read object to reduce the overhead for a future authentication.

18. The method of claim 17, further comprising the step of a client adjusting a number of cached signatures based on one of memory size, write frequency, and a network bandwidth cost.

19. The method of claim 1, further comprising the step of an intermediate layer tracking which signatures a client has cached using client identification information.

20. The method of claim 19, wherein the identification information comprises one of an Internet Protocol address and a cookie.

21. The method of claim 1, further comprising the step of a client informing an intermediate layer of a signature the client has cached in a request for a new object.

22. Apparatus for one of generating and reading authentication information, wherein the authentication information provides evidence that a plurality of objects were one of generated and sent by an entity, comprising:

a memory; and

at least one processor coupled to the memory and operative to use one or more object access patterns indicative of whether at least two of the plurality of objects are accessed within a similar time period to group objects together to reduce an overhead for at least one of generating and reading the authentication information.

23. An article of manufacture for use in one of generating and reading authentication information, wherein the authentication information provides evidence that a plurality of objects were one of generated and sent by an entity, comprising a machine readable medium containing one or more programs which when executed implement the step of:

using one or more object access patterns indicative of whether at least two of the plurality of objects are accessed within a similar time period to group objects together to reduce an overhead for at least one of generating and reading the authentication information.