US 10,256,977 B2Granted

Methods and systems for efficient representation of file sets

AssigneeSynopsys, Inc.

InventorsDamon Alexander Weinstein, Randolph Byrd Kilmon, Jr.

Life of this patent

Estimating the term…

Loading patent…

Abstract

Sets of files may be represented using signatures. As described, an audit system can scan a file hierarchy that includes a root directory and a plurality of elements (e.g., directories, data files, and archive files) to identify elements satisfying an element selection criteria. The audit system creates element descriptors by identifying, for each respective identified element, one or more element component values and creating an element descriptor from the element component values. The audit system forms a string descriptor comprising an aggregation of the element descriptors and generates a signature for the string descriptor. The signature may be stored in association with metadata for the root directory. The audit system can identify multiple sets of files represented by equivalent signatures and record the representations of the set of files compactly.

Claims20

Dependent claims

A method for representing a set of data files, the method comprising:

scanning, by an audit system comprising at least one computing processor, a file hierarchy comprising a root directory and a plurality of elements, wherein each element is one of a directory, a data file, or an archive file;
identifying, by the audit system, from the scanned plurality of elements, a set of identified elements satisfying an element selection criterion;
generating, by the audit system, a plurality of signatures representative of the set of identified elements by:
creating, by the audit system, for each identified element of the set of identified elements:
a first element descriptor and a second element descriptor, wherein:
(i) the first element descriptor comprises a first text string of a first set of one or more element component values representative of the identified element, and
(ii) the second element descriptor comprises a second text string of a second set of one or more element component values representative of the identified element, wherein:
the second set of element component values is different from the first set of element component values,
the second text string is different from the first text string for the element, and
each element descriptor is formatted according to one or more string descriptor formatting rules;
generating, by the audit system, a first signature from a first string descriptor comprising a first deterministic aggregation of the first element descriptors created for the set of identified elements of the file hierarchy;
generating, by the audit system, a second signature from a second string descriptor comprising a second deterministic aggregation of the second element descriptors created for the set of identified elements of the file hierarchy, wherein the second deterministic aggregation has the same size as the first deterministic aggregation irrespective of any size difference between the first element descriptors and the second element descriptors;
comparing, by the audit system, the first signature with the second signature;
and
outputting, by the audit system, audit data comprising at least one entry comprising at least one of the first signature the second signature, and a result of the comparing.

12 more elements

A system comprising one or more computing processors and memory storing instructions causing the one or more processors to:

scan a file hierarchy comprising a root directory and a plurality of elements, wherein each element is one of a directory, a data file, or an archive file;
identify, from the scanned plurality of elements, a set of identified elements satisfying an element selection criterion;
and
generate a plurality of signatures representative of the set of identified elements by:
creating, for each of the identified elements, a first element descriptor and a second element descriptor, wherein:
(i) the first element descriptor comprises a first text string of a first set of one or more element component values representative of the identified element, and
(ii) the second element descriptor comprises a second text string of a second set of one or more element component values representative of the element, wherein:
the second set of element component values is different from the first set of element component values,
the second text string is different from the first text string for the element, and
each element descriptor is formatted according to one or more string descriptor formatting rules;
generating a first signature from a first string descriptor comprising a first deterministic aggregation of the first element descriptors created for the set of identified elements of the file hierarchy;
generating a second signature from a second string descriptor comprising a second deterministic aggregation of the second element descriptors created for the set of identified elements of the file hierarchy, wherein the second deterministic aggregation has the same size as the first deterministic aggregation irrespective of any size difference between the first element descriptors and the second element descriptors;
comparing, by the audit system, the first signature with the second signature;
and
outputting, by the audit system, audit data comprising at least one entry comprising at least one of the first signature, the second signature, and a result of the comparing.

12 more elements

A non-transitory computer-readable medium storing instructions for execution by a computing system comprising one or more computing processors, execution of the instructions causing the computing system to:

scan a file hierarchy comprising a root directory and a plurality of elements, wherein each element is one of a directory, a data file, or an archive file;
identify, from the scanned plurality of elements, a set of identified elements satisfying an element selection criterion;
and
generate a plurality of signatures representative of the set of identified elements by:
creating, for each of the identified elements, a first element descriptor and a second element descriptor, wherein:
(i) the first element descriptor comprises a first text string of a first set of one or more element component values representative of the identified element, and
(ii) the second element descriptor comprises a second text string of a second set of one or more element component values representative of the element, wherein:
the second set of element component values is different from the first set of element component values,
the second text string is different from the first text string for the element, and
each element descriptor is formatted according to one or more string descriptor formatting rules;
generating a first signature from a first string descriptor comprising a first deterministic aggregation of the first element descriptors created for the set of identified elements of the file hierarchy;
generating a second signature from a second string descriptor comprising a second deterministic aggregation of the second element descriptors created for the set of identified elements of the file hierarchy, wherein the second deterministic aggregation has the same size as the first deterministic aggregation irrespective of any size difference between the first element descriptors and the second element descriptors;
comparing, by the audit system, the first signature with the second signature;
and
outputting, by the audit system, audit data comprising at least one entry comprising at least one of the first signature, the second signature, and a result of the comparing.

12 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/182,699Filed 18 Feb 2014
Published: US 2015/0234848 A120 Aug 2015
Granted: 9 Apr 2019
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

H04L 9/3239
Using cryptographic hash functions: involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
G06F 8/71
Software maintenance or management: version control ; Configuration management
G06F 16/152
File search processing: using file content signatures, e.g. hash values
G06F 16/90344
Query processing: by using string matching techniques