[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

US8224848B2 - System and method for entropy-based near-match analysis - Google Patents

System and method for entropy-based near-match analysis Download PDF

Info

Publication number
US8224848B2
US8224848B2 US12/722,482 US72248210A US8224848B2 US 8224848 B2 US8224848 B2 US 8224848B2 US 72248210 A US72248210 A US 72248210A US 8224848 B2 US8224848 B2 US 8224848B2
Authority
US
United States
Prior art keywords
entropy
file
target
value
data
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active, expires
Application number
US12/722,482
Other languages
English (en)
Other versions
US20100235392A1 (en
Inventor
Shawn McCreight
Dominik Weber
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Open Text Holdings Inc
Original Assignee
Guidance Software Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Guidance Software Inc filed Critical Guidance Software Inc
Priority to US12/722,482 priority Critical patent/US8224848B2/en
Assigned to GUIDANCE SOFTWARE, INC. reassignment GUIDANCE SOFTWARE, INC. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: MCCREIGHT, SHAWN, WEBER, DOMINIK
Publication of US20100235392A1 publication Critical patent/US20100235392A1/en
Application granted granted Critical
Publication of US8224848B2 publication Critical patent/US8224848B2/en
Assigned to SILICON VALLEY BANK reassignment SILICON VALLEY BANK SECURITY INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: GUIDANCE SOFTWARE, INC.
Assigned to OPEN TEXT HOLDINGS, INC. reassignment OPEN TEXT HOLDINGS, INC. MERGER (SEE DOCUMENT FOR DETAILS). Assignors: GUIDANCE SOFTWARE, INC.
Assigned to BARCLAYS BANK PLC reassignment BARCLAYS BANK PLC SECURITY INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: OPEN TEXT HOLDINGS, INC.
Assigned to BARCLAYS BANK PLC reassignment BARCLAYS BANK PLC SECURITY INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: OPEN TEXT HOLDINGS, INC.
Assigned to BARCLAYS BANK PLC reassignment BARCLAYS BANK PLC SECURITY INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: OPEN TEXT HOLDINGS, INC.
Assigned to THE BANK OF NEW YORK MELLON reassignment THE BANK OF NEW YORK MELLON SECURITY INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: OPEN TEXT HOLDINGS, INC.
Assigned to OPEN TEXT HOLDINGS, INC. reassignment OPEN TEXT HOLDINGS, INC. RELEASE OF SECURITY INTEREST IN PATENTS (REEL/FRAME 063558/0682) Assignors: BARCLAYS BANK PLC
Active legal-status Critical Current
Adjusted expiration legal-status Critical

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/60Protecting data
    • G06F21/62Protecting access to data via a platform, e.g. using keys or access control rules
    • G06F21/6209Protecting access to data via a platform, e.g. using keys or access control rules to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90Details of database functions independent of the retrieved data types
    • G06F16/901Indexing; Data structures therefor; Storage structures
    • G06F16/9014Indexing; Data structures therefor; Storage structures hash tables
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90Details of database functions independent of the retrieved data types
    • G06F16/903Querying
    • G06F16/90335Query processing
    • G06F16/90344Query processing by using string matching techniques
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/60Protecting data
    • G06F21/64Protecting data integrity, e.g. using checksums, certificates or signatures
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/60Protecting data
    • G06F21/64Protecting data integrity, e.g. using checksums, certificates or signatures
    • G06F21/645Protecting data integrity, e.g. using checksums, certificates or signatures using a third party

Definitions

  • U.S. Pat. No. 6,792,545 assigned to the Assignee of the present application, discloses a system and method for performing secure investigations of networked devices over a computer network. Part of the investigation might entail locating a document in a target device that is identical to a reference document. This might be accomplished, for example, by computing a hash value of the reference document and then comparing the computed hash value against the hash value of the documents in the target device. Two documents with matching hash values are deemed identical to one another.
  • One way in which a malicious user of the target device may frustrate the use of cryptographic hashing to locate files of interest is by making minor alternations to the files. Changing even a single bit of a file changes its cryptographic hash. Thus, a forensic investigation system that uses a set of known cryptographic hashes for locating matching files is unsuccessful if an otherwise identical file has data that has been inserted, modified, or deleted.
  • fuzzy hashing such as, for example, a fuzzy hashing algorithm known as “ssdeep.”
  • fuzzy hashing constructs hash signatures of chunks of data whose boundaries are determined by the context of the input. The hashes are then used to compute a numerical difference, usually expressed as a percentage, between the two files to which the fuzzy hashing algorithm was applied.
  • Embodiments of the present invention are directed to a system and method for identifying one or more files in one or more target machines that are a near-match to a reference file.
  • the method includes computing or identifying an entropy of the reference file and outputting a first entropy value.
  • a second entropy value of a target file stored in the one or more target machines is also identified.
  • a likeness of content in the target file is determined to content in the reference file based on the first and second entropy values.
  • a tolerance threshold is also identified.
  • a near-match between the target file and the reference file is determined if the likeness of the target file to the reference file is within the tolerance threshold. Information on the target file is then displayed in response to the determining of a near-match.
  • FIG. 1 is a block diagram of an exemplary computer investigation system according to one embodiment of the invention.
  • FIG. 2 is an architecture block diagram of examining and target machines according to one embodiment of the invention
  • FIG. 3 is a conceptual layout diagram of an exemplary input file according to one embodiment of the invention.
  • FIG. 4 is a conceptual layout diagram for organizing 0th derivative values of a file for calculating a 0th order entropy according to one embodiment of the invention
  • FIG. 5 is a conceptual layout diagram for organizing 1st derivative values for calculating a 0th order entropy of a file according to one embodiment of the invention
  • FIG. 6 is a conceptual layout diagram for organizing 0th derivate values of a file for calculating a 1st order entropy according to one embodiment of the invention
  • FIG. 7 is a conceptual layout diagram for organizing 1st derivative values of a file for calculating a 1st order entropy according to one embodiment of the invention.
  • FIG. 8 is a flow diagram of a process of a document comparison module for performing an entropy-based near-match analysis according to one embodiment of the invention.
  • FIGS. 9A-9B are screen shots of a graphical user interface (GUI) for configuring certain parameters for performing an entropy-based near-match analysis according to one embodiment of the invention.
  • GUI graphical user interface
  • FIG. 10 is a screen shot of a GUI for building entropy sets according to one embodiment of the invention.
  • FIG. 11 is a screen shot of a GUI for providing a summary of an entropy-based near-match analysis according to one embodiment of the invention.
  • FIG. 12 is a screen shot of a GUI for providing information on matching files from all considered targets according to one embodiment of the invention.
  • FIG. 13 is a screen shot of a GUI for providing information on matches per target machine according to one embodiment of the invention.
  • FIG. 14 is a screen shot of an analysis report according to one embodiment of the invention.
  • embodiments of the present invention are directed to a forensic investigation system that identifies files stored in a target machine, hereinafter referred to as target files, that are almost, but not exactly, identical, to a reference file.
  • the identification is made when it would not otherwise be made via traditional cryptographic hashing techniques.
  • the target files may be identical to the reference file except for one or more bytes of data that have been added, removed, or modified, in the target files.
  • identical files may also be identified via the embodiments of the present invention, as well as files that may be quite different and not almost identical to the reference file.
  • embodiments of the present invention are configured to identify files in a context free manner. That is, the likeness of content contained in two files may be identified for any types of files, and is not constrained to identification of specific types of files, such as, for example, files containing text. Furthermore, unlike prior art mechanisms such as ssdeep that return hash values that are not fixed in size, the information returned from the target machines for determining likeness of a target file to a reference file is compact and fixed in size. In this regard, the information that is used for determining the likeness of the target file is an information entropy value of the file. According to one embodiment, an information entropy identifies a randomness of information contained in a file.
  • a computing processor engages in a near-match analysis by computing the information entropy of the reference and target files, and determining the likeness of the target files to the reference file based on the computed entropies.
  • the computing processor determines a near match between the target file and the reference file if the likeness of the two files is within a user-defined tolerance level.
  • the information entropy is a weighted value that takes into account the size of the file.
  • the forensic investigation system flag files with weighted entropies that are within a given tolerance of the entropy of a reference file as being files that may be similar to the reference file, and at least those files are transmitted to a forensic investigator for further review.
  • Weighted entropy values take into account the size of the files being computed.
  • original entropy values are used for determining the likeness of files.
  • entropy value is used generically to refer to either a weighted or not weighted (original) entropy value.
  • the difference in the entropy values of the reference and target files is representative of the differences of the data content in the two files.
  • the smaller the perceived difference of the contents of the two files the smaller difference in the computed entropy values.
  • a file containing the text HELLO THERE would be perceived by a viewer to be different from a file containing the text THERE HELLO, even if both files contain the same two words.
  • the entropy values computed for these two files should reflect this difference.
  • the reflected difference should be small enough to flag the second file as being similar to the first file.
  • FIG. 1 is a block diagram of an exemplary computer investigation system 101 that allows the identification of almost identical files during a forensic investigation session.
  • the computer investigation system 101 includes various network devices coupled to a data communications network 103 over data communication links 105 .
  • the data communications network 103 may be a computer network, such as, for example, a public Internet, a private wide area network (WAN), a local area network (LAN), or other wired or wireless network environment conventional in the art.
  • the network devices may include a vendor computer 107 , a secure server 111 , an examining machine 115 , one or more target machines 117 , and a keymaster computer 113 .
  • the data communication link 105 may be any network link conventional in the art, such as, for example, a direct wire, an infrared data port, a wireless communications link, global communications link such as the Internet, or any other communications medium known in the art.
  • a vendor having access to the vendor computer 107 provides the organization with a computer investigation software 109 which enables the organization to effectively perform forensic investigations, respond to network safety alerts, and conduct network audits and other investigations over the data communications network 103 .
  • the investigation software is stored in a computer readable medium (e.g. ROM, flash memory, magnetic computer storage device, optical discs, and the like), that is accessed by the secure server 111 .
  • the computer investigation software 109 provides computer program instructions which, when executed by one or more processors resident in the secure server 111 , cause the secure server to broker safe communication between the examining machine 115 and the target machines 117 .
  • the computer investigation software further facilitates the administration of users, logs transactions conducted via the server, and controls access rights to the system.
  • the examining machine 115 (which may also be referred to as the client) allows an authorized examiner to conduct searches of the target machines 117 and their associated secondary storage devices 104 .
  • the examining machine 115 is a computer device with a processor configured to access a computer-readable media storing a client software 116 which includes the functionality and interoperability for remotely accessing the secure server 111 and corresponding target machines 117 .
  • the processor may execute the client software to search one or more target machines for target files that are almost identical to a known reference file.
  • Each target machine 117 is exemplarily the subject of a computer investigation conducted by the examining machine 115 .
  • the target machine may be a portable device such as, for example, a laptop, personal digital assistant, or any device that may connect and disconnect from the network.
  • each target machine 117 is coupled to one or more secondary storage devices 104 over an input/output connection 114 .
  • the storage devices include any nonvolatile storage media such as, for example, hard disks, diskettes, Zip drives, redundant array of independent disks (RAID) systems, holographic storage devices, or any other device configured to store data that may be subject to an investigation.
  • a servlet 118 installed on a particular target machine 117 responds to commands provided by the examining machine 115 to remotely discover, preview, and acquire dynamic and/or static data stored at the target machine and/or the associated secondary storage device(s) 104 , and transmit the acquired data to the examining machine via the secure communication path created between the target machine and the examining machine.
  • the servlet may also be configured to make entropy calculations of one or more files stored in the secondary storage devices 104 , and communicate the entropy values to the examining machine via the secure communication path.
  • the servlet may be implemented as any software module conventional in the art, and is not limited to applets in a web browser environment.
  • Computer instructions for implementing the servlet may be stored in a computer readable media (e.g. ROM, flash memory, magnetic computer storage device, optical discs, and the like), that is accessed by the target machine.
  • the computer investigation system 101 illustrated in FIG. 1 further allows an authorized examiner direct or remote access to the examining machine 115 via an examiner device 119 in any manner conventional in the art.
  • the examiner device 119 may be an input and/or output device coupled to the examining machine 115 , such as, for example, a keyboard and/or monitor.
  • the examiner device 119 may alternatively be a personal computer or laptop communicating with the examining device over a wired or wireless communication mechanism.
  • the examiner is a trusted individual who safely stores in the examining machine 115 , one or more encryption keys used for authenticating to the secure server 111 and conducting the secure investigation of the target machines 117 , as is described in more detail in the above-referenced U.S. Pat. No. 6,792,545.
  • the client software 116 includes a document comparison module 200 a with computer program instructions to compute or retrieve an entropy value of a reference file, and determine based on the entropy value whether the reference file is within a desired threshold of similarity with a target file stored in the secondary storage device 104 of a particular target machine 117 .
  • the files in the secondary device of the target machine are transmitted to the examining machine over the data communication links 105 to enable the entropy computation to be performed by the processor of the examining machine 115 .
  • the entropy computation is performed by the processor in the target machine 117 that invokes a document comparison module 200 b which may be similar to the document comparison module 200 a run by the examining machine 115 .
  • the document comparison module included in the servlet helps eliminate unnecessary data transfer of documents that are outside the desired threshold of similarity.
  • the documents that are transmitted to the examining machine 115 are documents that are determined by the document comparison module 200 b to be similar to the reference file based on the entropy computations.
  • the document comparison modules 200 a , 200 b are collectively referred to as document comparison module 200 .
  • FIG. 2 is an architecture block diagram of the examining and target machines 115 , 117 according to one embodiment of the invention.
  • the machine 115 , 117 includes a processor 30 operatively coupled via a system bus 54 to a main memory 32 and an input/output (I/O) interface control unit 58 .
  • the I/O interface control unit 58 is operatively coupled via an I/O local bus 56 to a storage controller 38 .
  • the processor 30 is coupled via the I/O interface control unit 58 , the I/O local bus 56 , and the storage controller 38 , to a computer-readable medium such as, for example, storage device 34 .
  • Computer program instructions 36 for implementing different functionalities of the client software 116 or servlet 118 , including the functionalities of the document comparison module 200 are stored in the storage device 34 until the processor 30 retrieves the computer program instructions and stores them in the main memory 32 .
  • the processor 30 then executes the computer program instructions stored in the main memory 32 to conduct a forensic investigation of a target device.
  • the document comparison module 200 computes entropy values of at least the target files in a target machine 117 that is subject of a current forensic investigation, and determines whether the target files are similar to a reference file based on the computed entropy values.
  • the machine 115 , 117 further includes one or more output devices 40 coupled to the I/O local bus via one or more output controllers 42 .
  • Such output devices may include, for example, a display device for displaying information such as, for example, contents of a file that has been flagged for investigation, or configuration parameters of the document comparison module 200 .
  • the machine 115 , 117 further includes one or more user input devices 26 coupled to the I/O local bus via an input device controller 46 .
  • a user may use a user input device to configure various parameters of the document comparison module 200 .
  • Commands from the secure server 111 are received by a wired or wireless network interface device 44 controlled by a network interface control unit 52 , and forwarded to the processor 30 via the system bus 54 .
  • Direct communication between the examining machine 115 and target machine 117 is also enabled by the network interface device 44 .
  • the entropy calculation of a file may be based on the content of the file itself, or based on a difference in values between two adjacent blocks (e.g. bytes or other groupings of bits) of data. Taking a 0th derivative of the data contained in the file results in the data itself. Taking a 1st derivative of the data produces differences in values between two adjacent blocks of data.
  • the entropy value that results from the entropy calculation is a double-precision floating point number ranging from 0 to 8. As the entropy value approaches 8, the more random, and hence, the more unpredictable, are the values in the file. Conversely, as the entropy value approaches 0, the less random, and hence, the more predictable, are the values in the file.
  • a person of skill in the art should recognize that other range of entropy values may also be used instead of the range of 0 to 8.
  • FIG. 3 is a conceptual layout diagram of an exemplary input file containing 200 bytes of data.
  • the data represents text.
  • the document comparison module is configured to work to identify almost identical files regardless of the specific nature of the data.
  • the text in the reference and target files are represented via an ASCII character set, ANSI character set, Unicode character set, or the like.
  • An embodiment of the present invention supports 256 characters, numbered 0-255. A person of skill in the art should recognize, however, that more or less number of characters may be supported without departing from the scope and spirit of the invention.
  • the exemplary file contains the following values which may be mapped to a specific character:
  • the entropy calculation considers the probability of a byte having a particular value, given all the values in the entire file. That value might be a 0th derivative value (i.e. the data itself), or a 1st derivative value (herein referred to as a differential value), depending on the configuration of the document comparison module 200 . For either value, a 0th order entropy calculation counts a number of occurrences for the file, in terms of number of bytes, of a specific value, for calculating a probability that a byte in the file will take that value.
  • FIG. 4 is a conceptual layout diagram for organizing 0th derivative values of a file for calculating a 0th order entropy according to one embodiment of the invention.
  • the example in FIG. 4 shows that there are 100 bytes of data storing the value “2,” whereas there are 10 bytes of data storing the value “1.”
  • the probability of a byte having the value “2” is 0.5
  • the probability of a byte having the value “1” is 0.05.
  • H ( S ) ⁇ p i log 2 p i Formula 1 where p i is the probability of value i.
  • the entropy calculation is context free, that is, not tied to any specific file format.
  • embodiments of the present invention may be applied to all types of files including but not limited to text files, image files, audio files, executable files, and the like.
  • FIG. 5 is a conceptual layout diagram for organizing 1st derivative values (i.e. differential values for different byte pairs) for calculating a 0th order entropy of a file, hereinafter referred to as a 0th order differential entropy, according to one embodiment of the invention.
  • 1st derivative values i.e. differential values for different byte pairs
  • the range of possible differential values are from ⁇ 255 to 255.
  • the example of FIG. 5 shows that there are 50 bytes of data with a differential value of “ ⁇ 1,” whereas there are 10 bytes of data with a differential value of 0.
  • the probability of a differential value of “ ⁇ 1” is 0.25, whereas the probability of a differential value of “0” is 0.05.
  • the 0th order differential entropy may be calculated according to above Formula 1.
  • the entropy calculation may also consider the probability of a pair of adjacent bytes having a particular pair of values.
  • those values might be a 0th derivative values (i.e. the data itself), or 1st derivative values (differential values), depending on the configuration of the document comparison module 200 .
  • a 1st order entropy calculation counts a number times a certain byte associated with a first value is immediately preceded by another byte associated with a second value, for determining the probability that a byte pair in the file will take those values.
  • FIG. 6 is a conceptual layout diagram for organizing 0th derivate values of a file for calculating a 1st order entropy according to one embodiment of the invention.
  • the 0th derivative values are organized in a matrix which size depends on the potential values in a character set supported by the system. According to one embodiment of the invention, the size of the matrix is 256 ⁇ 256.
  • FIG. 6 shows that 10 bytes of the file have a value “2” immediately preceded by a byte having a value “1,” and 20 bytes of the file have a value “1” immediately preceded by a byte having a value “2.”
  • the values in the vertical axis may represent the values that immediately follow the values in the horizontal axis.
  • the probability that a byte having a value “2” will be immediately preceded by a byte having a value “1” is 0.05
  • the probability that a byte having the value “1” will be immediately preceded by a byte having a value “2” is 0.5.
  • the 1st order entropy of a file, H(S) may be calculated according to the below formula.
  • H ⁇ ( S ) - ⁇ i ⁇ ⁇ p i ⁇ ⁇ j ⁇ ⁇ p i ⁇ ( j ) ⁇ log 2 ⁇ p i ⁇ ( j ) Formula ⁇ ⁇ 2 where i is a certain preceding character, and p i (i) is the probability of j given i as the previous character.
  • i is a certain preceding character
  • p i (i) is the probability of j given i as the previous character.
  • FIG. 7 is a conceptual layout diagram for organizing 1st derivative values of a file for calculating a 1st order entropy of a file, hereinafter referred to as a 1st order differential entropy, according to one embodiment of the invention.
  • the matrix that is used to organize the differential values is the same as the matrix in FIG. 6 , except that the matrix also accounts for negative differential values.
  • the probability that a byte having a differential value of “1” will be immediately preceded by a byte having a differential value of “0” is 0.1
  • the probability that a byte having a differential value “0” will be immediately preceded by a byte having a differential value “1” is 0.5.
  • the 1st order differential entropy of the file may be calculated according to the above Formula 2.
  • step 500 the computing processor computes the entropy value of one or more reference files, and outputs a number, for example, between 0 and 8. The higher the entropy value, the more random and unpredictible the contents of the file. Alternatively, if the entropy value has already been computed, the processor simply retrieves the entropy value that has been stored for the reference file(s).
  • the entropy value is a 0th order entropy or a 0th order differential entropy. According to another embodiment of the invention, the entropy value is a 1st order entropy or a 1st order differential entropy.
  • step 502 a determination is made by the computing processor as to whether there are files in a comparison set that still need to be considered. If the answer is YES, a specific target file is identified in step 504 .
  • the comparison set may include all or a portion of target files in all or particularly selected target machines.
  • the entropy of the identified target file is computed by the computing processor.
  • the computed entropy uses the same parameters that were used when computing the entropy of the reference file.
  • Such parameters may relate, for example, to the Markov order (i.e. the order of the entropy calculation), a derivative order (e.g. a 0th order derivative of the data or a 1st order derivative of the data), or other configuration settings of the document comparison module 200 .
  • the computed entropy values are used to determine a likeness of content contained in the target file to the content in the reference file.
  • the computing processor computes a likeness value for the target file in relation to the reference file based, at a minimum, on the entropy values of each respective file.
  • the likeness value is based on a difference of the entropy values and a difference in the size of the target and reference files.
  • the likeness value is a weighted entropy difference that not only takes into account differences in the entropy values, but also takes into account differences in the file sizes.
  • the computing processor considers whether the target file differs from the reference file by no more than a threshold tolerance amount.
  • a default threshold tolerance amount may be set by the document comparison module. The default amount may, however, be adjusted via a user command. As a person of skill in the art should appreciate, the threshold determines how similar to dissimilar the returned files will be to the reference file.
  • the threshold tolerance amount is a threshold entropy difference value.
  • An exemplary threshold entropy difference value is 0.001.
  • the computing processor computes a difference between the entropy value of the reference file and the entropy value of the target file, and determines if the difference is within (e.g. equal or below) the set threshold.
  • the tolerance threshold amount may alternatively take the form of a likeness threshold that may be set between 0 and 100.
  • the higher the likeness threshold the more similar the files that are returned to the reference file. For example, if a likeness threshold is set to be 100, only exact matches are returned.
  • the computing processor computes the likeness value for the target file in relation to the reference file, and compares this against the set tolerance threshold amount.
  • the target file is flagged in step 510 as a near-match. Furthermore, if multiple references files were used to perform the comparison, the particular reference file to which the target file is deemed to be similar is also flagged. The flagged target files are thus identified as being similar to the particular reference file.
  • the computing of the likeness value or entropy difference (depending on the embodiment being used), and the comparing against the threshold tolerance amount to determine whether a target file is similar (or dissimilar) to the reference file(s), are all performed by the computing processor in the examining machine 115 based on entropy values returned by the target machines 117 .
  • the computation may also be performed by the target machines by other computing devices coupled to the examining machine 115 .
  • the examining machine 115 may command the target machine 117 to transmit content of one or more of the output files to the examining machine over the data communications network. If the content of the output files already have been transmitted to the examining machine by the target machine, no such command may need to be transmitted. Alternatively, the transmission of the content may occur automatically without a specific command from the examining machine.
  • the examiner may modify the tolerance threshold and/or search result size based on the number of files that are output by the document comparison module. For example, if the number of output files are in the thousands, the Examiner may want to decrease the threshold value to reduce the number of flagged files, or reduce the search result size.
  • the document comparison module 200 stores a set of default parameters for performing entropy-based near-match analyses. These default parameters may be modified by an examiner by accessing the document comparison module 200 via the examiner device 119 . If the document comparison module 200 resides in the target machine, the examiner device 119 is used to transmit commands to the servlet for modifying the configuration parameters of the document comparison module.
  • the configurable parameters include: Markov order, derivative order, sequence, mask, tolerance threshold, result size, and/or the like.
  • the Markov order is the order of the entropy calculation, and may be set to be 0 or 1.
  • the default Markov order is 1 for a 1st order entropy calculation.
  • the derivative order is the order of the derivative to be taken for the data in the file for which the entropy calculation is being made, and may be set to be 0 or 1. According to one embodiment, the default derivative order is 0 for taking a 0th order derivative of the data in the file.
  • other parameters may also be set for excluding certain bytes of data in the file which have an unnecessarily large effect on the entropy of a file for purposes of forensic investigation.
  • One such parameter is a sequence parameter which indicates a number of repeated bytes to allow before ignoring the value.
  • a sequence parameter of N indicates that if a byte is repeated more than N times, the repeated bytes after N are to be ignored until the value changes.
  • the default sequence is 2.
  • the document comparison module ignores the last three bytes containing the value “5,” and treats the file as if it contained “1, 2, 3, 4, 4, 7, 5, 5.”
  • the mask parameter is set to ignore a value “0” in order to mask the trivial difference between Unicode and ASCII text.
  • the word HELLO is represented as “H 0 E 0 L 0 L 0,” whereas in ASCII, there are no intervening 0 values between each character value.
  • the 0's are masked by default for calculating the entropy of a file containing Unicode text.
  • FILE 1 0, 0, 0, 0, 0
  • FIG. 10 is a screen shot of a GUI provided by the document comparison module for building entropy sets according to one embodiment of the invention.
  • An entropy set includes one or more reference files and associated entropy values that are to be compared against a comparison set.
  • the entropy set may identify a name 610 of a reference file, an entropy value 612 , a standard deviation 614 , a hash value 616 , a size 618 of the file, and the like.
  • the document comparison module includes into the comparison set, the types of files defined in field 604 , for all target machines in the network, particular target machines selected by a user, particular directories, folders, or storage locations, and the like.
  • FIG. 11 is a screen shot of a GUI for providing a summary of an entropy-based near-match analysis according to one embodiment of the invention.
  • a user may select a first option 650 to view information on matches per target machine, a second option 652 to view information on the entropy set used for the analysis, and a third option 654 to view information on matching files from all considered targets.
  • FIG. 12 is a screen shot of a GUI for providing information on matching files from all considered targets according to one embodiment of the invention.
  • the analysis results may include, for example, a target file name 700 , a likeness value 702 between the target file and a considered reference file, as well as an indication as to whether a hash value of the target file is identical to a hash value of a reference file 704 .
  • the document comparison module initially compares the hash values of the target file and the reference file for first determining an exact match. If the hash values differ, the document comparison module proceeds to engage in the entropy-based analysis for determining whether, although the files are not identical, they are similar enough for concluding a near-match. As discussed above, the determination as to whether the files are similar enough is based on the set threshold tolerance amount.
  • the analysis results may further include a name of the reference file 706 that resulted in the match or near match, an entropy difference 708 between the target and reference files, and a size difference 710 between the two files.
  • the analysis results may further include additional information about the target file including, for example, a date in which the target file was created 712 , a date in which the target file was written 714 , a hash value for the target file 716 , and a name of the target machine 718 in which the target file is stored.
  • FIG. 13 is a screen shot of a GUI for providing information on matches per target machine according to one embodiment of the invention.
  • the information includes a name of the target machine 800 that was considered during the analysis, a number of files that resulted in exact matches with the reference files in the entropy set 802 , a maximum likeness value 804 among the likeness values returned for the target machine as near-matches, an average likeness value 806 based on all likeness values returned for the target machine as near-matches, and a number of the near-matches 808 returned for the target machine.
  • the results of the near-match analysis may be output in the form of a report as is depicted in FIG. 14 .
  • the report may include information on the entropy set and/or information on the match results on a per machine basis and/or per file basis.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Databases & Information Systems (AREA)
  • Computer Hardware Design (AREA)
  • General Health & Medical Sciences (AREA)
  • Bioethics (AREA)
  • Health & Medical Sciences (AREA)
  • Data Mining & Analysis (AREA)
  • Computational Linguistics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
US12/722,482 2009-03-16 2010-03-11 System and method for entropy-based near-match analysis Active 2030-10-07 US8224848B2 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
US12/722,482 US8224848B2 (en) 2009-03-16 2010-03-11 System and method for entropy-based near-match analysis

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US16063409P 2009-03-16 2009-03-16
US12/722,482 US8224848B2 (en) 2009-03-16 2010-03-11 System and method for entropy-based near-match analysis

Publications (2)

Publication Number Publication Date
US20100235392A1 US20100235392A1 (en) 2010-09-16
US8224848B2 true US8224848B2 (en) 2012-07-17

Family

ID=42731528

Family Applications (1)

Application Number Title Priority Date Filing Date
US12/722,482 Active 2030-10-07 US8224848B2 (en) 2009-03-16 2010-03-11 System and method for entropy-based near-match analysis

Country Status (3)

Country Link
US (1) US8224848B2 (fr)
EP (1) EP2409232A4 (fr)
WO (1) WO2010107659A1 (fr)

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20140143680A1 (en) * 2012-11-21 2014-05-22 Guidance Software, Inc. Segmented graphical review system and method
US20150019499A1 (en) * 2013-07-15 2015-01-15 International Business Machines Corporation Digest based data matching in similarity based deduplication
US9442975B2 (en) 2013-03-13 2016-09-13 Guidance Software, Inc. Systems and methods for processing data stored in data storage devices
US9836474B2 (en) 2013-07-15 2017-12-05 International Business Machines Corporation Data structures for digests matching in a data deduplication system
US10229132B2 (en) 2013-07-15 2019-03-12 International Business Machines Corporation Optimizing digest based data matching in similarity based deduplication
US10339109B2 (en) 2013-07-15 2019-07-02 International Business Machines Corporation Optimizing hash table structure for digest matching in a data deduplication system
US10671569B2 (en) 2013-07-15 2020-06-02 International Business Machines Corporation Reducing activation of similarity search in a data deduplication system
US10789213B2 (en) 2013-07-15 2020-09-29 International Business Machines Corporation Calculation of digest segmentations for input data using similar data in a data deduplication system

Families Citing this family (19)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8504489B2 (en) * 2009-03-27 2013-08-06 Bank Of America Corporation Predictive coding of documents in an electronic discovery system
US9384198B2 (en) 2010-12-10 2016-07-05 Vertafore, Inc. Agency management system and content management system integration
US9230548B2 (en) * 2012-06-06 2016-01-05 Cypress Semiconductor Corporation Hybrid hashing scheme for active HMMS
GB2507751A (en) 2012-11-07 2014-05-14 Ibm Storing data files in a file system which provides reference data files
US9330181B2 (en) * 2012-11-26 2016-05-03 Yahoo! Inc. Methods and apparatuses for document processing at distributed processing nodes
CN103106192B (zh) * 2013-02-02 2016-02-03 深圳先进技术研究院 文学作品作者识别方法及装置
US10810303B1 (en) * 2013-02-26 2020-10-20 Jonathan Grier Apparatus and methods for selective location and duplication of relevant data
US9507814B2 (en) * 2013-12-10 2016-11-29 Vertafore, Inc. Bit level comparator systems and methods
US9367435B2 (en) 2013-12-12 2016-06-14 Vertafore, Inc. Integration testing method and system for web services
US20150317325A1 (en) * 2014-04-30 2015-11-05 Key Cybersecurity, Inc. Methods and apparatus for detection of illicit files in computer networks
US9747556B2 (en) 2014-08-20 2017-08-29 Vertafore, Inc. Automated customized web portal template generation systems and methods
RU2617631C2 (ru) * 2015-09-30 2017-04-25 Акционерное общество "Лаборатория Касперского" Способ обнаружения работы вредоносной программы, запущенной с клиента, на сервере
US9600400B1 (en) 2015-10-29 2017-03-21 Vertafore, Inc. Performance testing of web application components using image differentiation
US10121003B1 (en) * 2016-12-20 2018-11-06 Amazon Technologies, Inc. Detection of malware, such as ransomware
US11755758B1 (en) * 2017-10-30 2023-09-12 Amazon Technologies, Inc. System and method for evaluating data files
US11157188B2 (en) * 2019-04-24 2021-10-26 EMC IP Holding Company LLC Detecting data deduplication opportunities using entropy-based distance
US11636144B2 (en) * 2019-05-17 2023-04-25 Aixs, Inc. Cluster analysis method, cluster analysis system, and cluster analysis program
CN112992303A (zh) * 2019-12-15 2021-06-18 苏州市爱生生物技术有限公司 人类表型标准用语提取方法
EP3910511A1 (fr) * 2020-05-13 2021-11-17 Magnet Forensics Inc. Système et procédé pour identifier des fichiers sur la base de valeurs de hachage

Citations (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6230155B1 (en) * 1996-06-18 2001-05-08 Altavista Company Method for determining the resemining the resemblance of documents
US6282698B1 (en) * 1998-02-09 2001-08-28 Lucent Technologies Inc. Detecting similarities in Java sources from bytecodes
US6449393B1 (en) 1997-06-19 2002-09-10 Electronics For Imaging, Inc. Method and apparatus for data compression based on modeling schemes
US20030236993A1 (en) * 2002-06-20 2003-12-25 Mccreight Shawn Enterprise computer investigation system
US20050223238A1 (en) 2003-09-26 2005-10-06 Schmid Matthew N Methods for identifying malicious software
US20070152854A1 (en) 2005-12-29 2007-07-05 Drew Copley Forgery detection using entropy modeling
US20070245420A1 (en) 2005-12-23 2007-10-18 Yong Yuh M Method and system for user network behavioural based anomaly detection
US20070256057A1 (en) 2006-04-28 2007-11-01 Ricoh Company, Ltd. Code transforming apparatus and code transforming method
US7376680B1 (en) 2003-04-07 2008-05-20 Charles Loren Kettler System and method for cleansing, linking and appending data records of a database
US20080184367A1 (en) 2007-01-25 2008-07-31 Mandiant, Inc. System and method for determining data entropy to identify malware
US20080263669A1 (en) * 2007-04-23 2008-10-23 Secure Computing Corporation Systems, apparatus, and methods for detecting malware
US20090190662A1 (en) * 2008-01-30 2009-07-30 Young-O Park Method and apparatus for encoding and decoding multiview video
US7930332B2 (en) * 2007-03-23 2011-04-19 Microsoft Corporation Weighted entropy pool service

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6397205B1 (en) * 1998-11-24 2002-05-28 Duquesne University Of The Holy Ghost Document categorization and evaluation via cross-entrophy
US7877808B2 (en) * 2005-07-01 2011-01-25 Red Hat, Inc. Using differential information entropy to detect bugs and security flaws in computer programs

Patent Citations (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6230155B1 (en) * 1996-06-18 2001-05-08 Altavista Company Method for determining the resemining the resemblance of documents
US6449393B1 (en) 1997-06-19 2002-09-10 Electronics For Imaging, Inc. Method and apparatus for data compression based on modeling schemes
US6282698B1 (en) * 1998-02-09 2001-08-28 Lucent Technologies Inc. Detecting similarities in Java sources from bytecodes
US20030236993A1 (en) * 2002-06-20 2003-12-25 Mccreight Shawn Enterprise computer investigation system
US7376680B1 (en) 2003-04-07 2008-05-20 Charles Loren Kettler System and method for cleansing, linking and appending data records of a database
US20050223238A1 (en) 2003-09-26 2005-10-06 Schmid Matthew N Methods for identifying malicious software
US20070245420A1 (en) 2005-12-23 2007-10-18 Yong Yuh M Method and system for user network behavioural based anomaly detection
US20070152854A1 (en) 2005-12-29 2007-07-05 Drew Copley Forgery detection using entropy modeling
US20070256057A1 (en) 2006-04-28 2007-11-01 Ricoh Company, Ltd. Code transforming apparatus and code transforming method
US20080184367A1 (en) 2007-01-25 2008-07-31 Mandiant, Inc. System and method for determining data entropy to identify malware
US7930332B2 (en) * 2007-03-23 2011-04-19 Microsoft Corporation Weighted entropy pool service
US20080263669A1 (en) * 2007-04-23 2008-10-23 Secure Computing Corporation Systems, apparatus, and methods for detecting malware
US20090190662A1 (en) * 2008-01-30 2009-07-30 Young-O Park Method and apparatus for encoding and decoding multiview video

Non-Patent Citations (7)

* Cited by examiner, † Cited by third party
Title
Borwein et al, "Moment-Matching and Best Entropy Estimation", Journal of Mathematical Analysis and Applications 185, 1994. *
David M. Loewenstern, "Significantly Lower Entropy Estimates for Natural DNA Sequences", DIMACS Technical Report 96-51, 1996. *
Dustin Hurlbut, "Fuzzy Hashing for Digital Forensic Investigators", Jan. 9, 2009. *
International Search Report and Written Opinion dated Apr. 26, 2010 for International Application No. PCT/US 10/27052, 8 pages.
Jesse Kornblum, "Identifying almost identical files using context triggered piecewise hashing", Digital Investigation, 2006. *
Monge eat al, "An Efficient domain-independent algorithm for detecting approximately duduplcate database records", Uninversity of California, 1997. *
Neemuchwala et al, "Image matching using alpha-entropy measures and entropic graphs", University of Michigan, 2004. *

Cited By (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20140143680A1 (en) * 2012-11-21 2014-05-22 Guidance Software, Inc. Segmented graphical review system and method
US9442975B2 (en) 2013-03-13 2016-09-13 Guidance Software, Inc. Systems and methods for processing data stored in data storage devices
US20150019499A1 (en) * 2013-07-15 2015-01-15 International Business Machines Corporation Digest based data matching in similarity based deduplication
US9836474B2 (en) 2013-07-15 2017-12-05 International Business Machines Corporation Data structures for digests matching in a data deduplication system
US10229132B2 (en) 2013-07-15 2019-03-12 International Business Machines Corporation Optimizing digest based data matching in similarity based deduplication
US10296598B2 (en) * 2013-07-15 2019-05-21 International Business Machines Corporation Digest based data matching in similarity based deduplication
US10339109B2 (en) 2013-07-15 2019-07-02 International Business Machines Corporation Optimizing hash table structure for digest matching in a data deduplication system
US10657104B2 (en) 2013-07-15 2020-05-19 International Business Machines Corporation Data structures for digests matching in a data deduplication system
US10671569B2 (en) 2013-07-15 2020-06-02 International Business Machines Corporation Reducing activation of similarity search in a data deduplication system
US10789213B2 (en) 2013-07-15 2020-09-29 International Business Machines Corporation Calculation of digest segmentations for input data using similar data in a data deduplication system

Also Published As

Publication number Publication date
WO2010107659A1 (fr) 2010-09-23
EP2409232A1 (fr) 2012-01-25
EP2409232A4 (fr) 2014-07-30
US20100235392A1 (en) 2010-09-16

Similar Documents

Publication Publication Date Title
US8224848B2 (en) System and method for entropy-based near-match analysis
CN111382434B (zh) 用于检测恶意文件的系统和方法
US7840551B2 (en) Method and apparatus for automatically classifying data
EP0798619B1 (fr) Identification de documents électroniques
US20110167102A1 (en) System, apparatus and method for encryption and decryption of data transmitted over a network
CN107683481B (zh) 使用延迟求值计算加密数据
US8429364B1 (en) Systems and methods for identifying the presence of sensitive data in backups
CN104680064A (zh) 利用文件指纹来优化文件的病毒扫描的方法和系统
US20070097420A1 (en) Method and mechanism for retrieving images
US20180137149A1 (en) De-identification data generation apparatus, method, and non-transitory computer readable storage medium thereof
US11658973B2 (en) Method and system for electronic mail attachment management
US11783072B1 (en) Filter for sensitive data
US11055431B2 (en) Securing data storage of personally identifiable information in a database
CN117454436B (zh) 基于乘法群的数据对齐方法、系统及电子设备
US11783088B2 (en) Processing electronic documents
CN117591485A (zh) 一种基于数据识别的固态硬盘运行控制系统及方法
US9442975B2 (en) Systems and methods for processing data stored in data storage devices
US11343272B2 (en) Proof of work based on compressed video
KR102625319B1 (ko) 클라우드 서버 기반의 헬스케어 데이터 관리 방법 및 장치
CN111949606A (zh) 文件碎形化加密引擎及其技术
FR3103922A3 (fr) Stockage de tokens sécurisé
US20090287647A1 (en) Method and apparatus for detection of data in a data store
WO2024224504A1 (fr) Dispositif, procédé et programme de vérification
CN116738443B (zh) 一种基于多示例感知的软件漏洞检测方法及相关设备
KR102227113B1 (ko) 공유 파일 시스템 기반의 파일 처리 장치

Legal Events

Date Code Title Description
AS Assignment

Owner name: GUIDANCE SOFTWARE, INC., CALIFORNIA

Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:MCCREIGHT, SHAWN;WEBER, DOMINIK;REEL/FRAME:024076/0001

Effective date: 20100303

FEPP Fee payment procedure

Free format text: PAT HOLDER NO LONGER CLAIMS SMALL ENTITY STATUS, ENTITY STATUS SET TO UNDISCOUNTED (ORIGINAL EVENT CODE: STOL); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

STCF Information on status: patent grant

Free format text: PATENTED CASE

SULP Surcharge for late payment
AS Assignment

Owner name: SILICON VALLEY BANK, CALIFORNIA

Free format text: SECURITY INTEREST;ASSIGNOR:GUIDANCE SOFTWARE, INC.;REEL/FRAME:033940/0532

Effective date: 20140829

FEPP Fee payment procedure

Free format text: PAYOR NUMBER ASSIGNED (ORIGINAL EVENT CODE: ASPN); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

FPAY Fee payment

Year of fee payment: 4

FEPP Fee payment procedure

Free format text: PAT HOLDER CLAIMS SMALL ENTITY STATUS, ENTITY STATUS SET TO SMALL (ORIGINAL EVENT CODE: LTOS); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

AS Assignment

Owner name: OPEN TEXT HOLDINGS, INC., DELAWARE

Free format text: MERGER;ASSIGNOR:GUIDANCE SOFTWARE, INC.;REEL/FRAME:047085/0319

Effective date: 20180626

FEPP Fee payment procedure

Free format text: ENTITY STATUS SET TO UNDISCOUNTED (ORIGINAL EVENT CODE: BIG.); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

MAFP Maintenance fee payment

Free format text: PAYMENT OF MAINTENANCE FEE, 8TH YEAR, LARGE ENTITY (ORIGINAL EVENT CODE: M1552); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

Year of fee payment: 8

AS Assignment

Owner name: BARCLAYS BANK PLC, NEW YORK

Free format text: SECURITY INTEREST;ASSIGNOR:OPEN TEXT HOLDINGS, INC.;REEL/FRAME:063558/0690

Effective date: 20230430

Owner name: BARCLAYS BANK PLC, NEW YORK

Free format text: SECURITY INTEREST;ASSIGNOR:OPEN TEXT HOLDINGS, INC.;REEL/FRAME:063558/0682

Effective date: 20230428

Owner name: BARCLAYS BANK PLC, NEW YORK

Free format text: SECURITY INTEREST;ASSIGNOR:OPEN TEXT HOLDINGS, INC.;REEL/FRAME:063558/0698

Effective date: 20230501

AS Assignment

Owner name: THE BANK OF NEW YORK MELLON, NEW YORK

Free format text: SECURITY INTEREST;ASSIGNOR:OPEN TEXT HOLDINGS, INC.;REEL/FRAME:064749/0852

Effective date: 20230430

MAFP Maintenance fee payment

Free format text: PAYMENT OF MAINTENANCE FEE, 12TH YEAR, LARGE ENTITY (ORIGINAL EVENT CODE: M1553); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY

Year of fee payment: 12

AS Assignment

Owner name: OPEN TEXT HOLDINGS, INC., CANADA

Free format text: RELEASE OF SECURITY INTEREST IN PATENTS (REEL/FRAME 063558/0682);ASSIGNOR:BARCLAYS BANK PLC;REEL/FRAME:067807/0062

Effective date: 20240621