Virus localization using cryptographic hashing
View Patent ↗Methods for using integrity checking techniques to identify and locate computer viruses are provided. A method for virus localization for each of three types of virus infections is provided, including the steps of computing a sequence of file blocks, calculating hashes for the sequences of file blocks from a host file and calculating hashes for the same or related sequences of file blocks from an infected file, and comparing the hashes from host file to the hashes from the infected file from the same or related sequences of file blocks such that when some of said first hashes and said second hashes do not match, a location of a virus is output. Methods are provided for computing the sequence of file blocks depending on the type of virus infection, and for calculating the hashes using a collision resistant hash function, a digital signature scheme, a message authentication code, or a pseudo-random function.
1. A method for virus localization comprising:
determining a sequence of file blocks from a host file by determining a sequencing formula for the host file, wherein the sequencing formula is an exponential formula determined in part by solving for an exponential component based at least in part on a number of file blocks in the host file;
calculating first hashes for the sequence of file blocks from the host file, the sequence of file blocks determined using the sequencing formula;
calculating second hashes for a corresponding sequence of file blocks from a modified host file, the corresponding sequence of file blocks determined by applying the sequencing formula recursively to a modified host file;
comparing the first hashes and the second hashes; and
outputting an estimated location of a virus relative to the modified host file based upon a number of the first hashes and the second hashes that do not match.
2. The method according to claim 1 , wherein said calculating first hashes and calculating second hashes are performed using one of a collision-resistant hash function, a digital signature scheme, a message authentication code, or a pseudo-random function.
3. The method according to claim 1 , wherein said virus comprises content modified from the host file.
4. The method according to claim 1 , wherein said location of said virus comprises a sequence of file blocks not larger than the virus by more than a predetermined multiplicative factor.
5. The method of claim 1 wherein the outputting the estimated location of the virus relative to the modified host file comprises outputting a range of file blocks including file blocks wherein the first hashes and the second hashes do not match.
6. The method of claim 1 wherein the outputting the estimated location of the virus relative to the modified host file comprises outputting a sequence subset for the modified host file wherein second hashes for the sequence subset do not match the corresponding first hashes.
7. A non-transitory tangible computer-readable medium storing instructions such that, if executed by a machine, will cause the machine to execute a method comprising:
determining a sequence of file blocks from a host file by determining a sequencing formula for the host file, wherein the sequencing formula is an exponential formula determined in part by solving for an exponential component based at least in part on a number of file blocks in the host file;
calculating first hashes for the sequence of file blocks from the host file, the sequence of file blocks determined using the sequencing formula;
calculating second hashes for a corresponding sequence of file blocks from a modified host file, the corresponding sequence of file blocks determined by applying the sequencing formula recursively to a modified host file;
comparing the first hashes and the second hashes; and
outputting an estimated location of a virus relative to the modified host file in terms of a particular sequence of file blocks based upon mismatching first hashes and second hashes.
8. The tangible computer-readable medium of claim 7 storing further instruction such that, if executed by a machine, will cause the machine to execute outputting the estimated location of the virus relative to the modified host file including outputting a range of file blocks including file blocks wherein the first hashes and the second hashes do not match.
9. A system configured to detect and locate a computer virus in a modified file, the system comprising:
a set of first hashes stored in a memory wherein the first hashes correspond to a processing result of a host file;
a modified file stored in the memory;
at least one processing circuit of a computer device, the processing circuit in communication with the memory, the processing circuit configured to calculate second hashes for the modified file using a corresponding sequence of file blocks as used to calculate the first hashes, the corresponding sequence of file blocks determined by applying a sequencing formula recursively to the modified file wherein the sequencing formula is an exponential formula determined in part by solving for an exponential component based at least in part on a number of file blocks in the host file;
wherein the at least one processing circuit is configured to compare the first hashes and the second hashes and to output an estimated location of a virus relative to the modified host file in terms of a particular sequence of file blocks based upon mismatching first hashes and second hashes.
10. The system of claim 9 wherein the particular sequence of file blocks based upon mismatching first hashes and second hashes comprises a sequence subset for the modified host file wherein second hashes for the sequence subset do not match the corresponding first hashes.
11. The system of claim 9 wherein the particular sequence of file blocks based upon mismatching first hashes and second hashes comprises a range of file blocks including file blocks wherein the first hashes and the second hashes do not match.