Cryptographic hashing for virus localization

ABSTRACT

Virus detection is an important problem in the area of computer security. Modern techniques attempting to solve this problem fall into the general paradigms of signature detection and integrity checking. In this paper we focus on the latter principle, which proposes to label an executable or source file with a tag computed using a cryptographic hash function, which later allows to detect if any changes have been performed to the file. We suggest to extend this principle so that not only changes to the file are detected, but also these changes are localized within the file; this is especially useful in the virus diagnostics which can then focus on the localized area in the file rather than the entire file. This implicitly defines an apparently new problem, which we call ``virus localization''. We design techniques to solve the virus localization problem based on repeated efficient applications of cryptographic hashing to carefully chosen subsets of the set of file blocks, for each of the most important and known virus infection techniques, such as rewriting techniques, appending and prepending techniques, and insertion techniques.

REFERENCES

• 1: F. Cohen, Computer viruses: theory and experiments, Computers and Security, v.6 n.1, p.22-35, Feb. 1987 [doi>10.1016/0167-4048(87)90122-2]
• 2: Fred Cohen, On the implications of computer viruses and methods of defense, Computers and Security, v.7 n.2, p.167-184, April 1988 [doi>10.1016/0167-4048(88)90334-3]
• 3: Ed Skoudis , Lenny Zeltser, Malware: Fighting Malicious Code, Prentice Hall PTR, Upper Saddle River, NJ, 2003
• 4: Peter Szor, The Art of Computer Virus Research and Defense, Addison-Wesley Professional, 2005
• 5: Gene H. Kim , Eugene H. Spafford, The design and implementation of tripwire: a file system integrity checker, Proceedings of the 2nd ACM Conference on Computer and communications security, p.18-29, November 1994, Fairfax, Virginia, United States [doi>10.1145/191177.191183]
• 6: G. Di Crescenzo, A. Ghosh, and R. Talpade. The design and implementation of tripwire: a file system integrity checker. Computer Security - ESORICS 2005, Proc. of 10th European Symposium on Research in Computer Security, vol. 3679 of Lecture Notes in Computer Science, Springer-Verlag, 2005.
• 7: A. Tridgell. Efficient Algorithms for Sorting and Synchronization. http://samba.org/ tridge/phd thesis.pdf.
• 8: Sean Quinlan , Sean Dorward, Venti: A New Approach to Archival Storage, Proceedings of the Conference on File and Storage Technologies, p.89-101, January 28-30, 2002
• 9: Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, John Wiley & Sons, Inc., New York, NY, 1993
• 10: 1st NIST Cryptographic Hash Functions Workshop. http://www.csrc.nist.gov/pki/HashWorkshop/2005/program.htm, 2005.
• 11: CERT Advisory CA-1992-02 Michelangelo PC Virus Warning, http://www.cert.org/advisories/CA-1992-02.html, 1997.
• 12: CERT Advisory CA-1999-04 Melissa Macro Virus, http://www.cert.org/advisories/CA-1999-04.html, 1999.
• 13: CERT Advisory CA-2001-26 Nimda Worm, http://www.cert.org/advisories/CA-2001-26.html, 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Reliability

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Validation

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

General Terms:
Algorithms, Security, Theory

Keywords:
cryptographic hashing, integrity verification, virus detection, virus tolerance