Document Open Access Logo

Provably Secure Virus Detection: Using The Observer Effect Against Malware

Authors Richard J. Lipton, Rafail Ostrovsky, Vassilis Zikas

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.32.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Richard J. Lipton
Rafail Ostrovsky
Vassilis Zikas

Cite As Get BibTex

Richard J. Lipton, Rafail Ostrovsky, and Vassilis Zikas. Provably Secure Virus Detection: Using The Observer Effect Against Malware. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.32

Abstract

Protecting software from malware injection is one of the biggest challenges of modern computer science. Despite intensive efforts by the scientific and engineering community, the number of successful attacks continues to increase.

This work sets first footsteps towards a provably secure investigation of malware detection. We provide a formal model and cryptographic security definitions of attestation for systems with dynamic memory, and suggest novel provably secure attestation schemes. The key idea underlying our schemes is to use the very insertion of the malware itself to allow for the systems to detect it. This is, in our opinion, close in spirit to the quantum Observer Effect. The attackers, no matter how clever, no matter when they insert their malware, change the state of the system they are attacking. This fundamental idea can be a game changer. And our system does not rely on heuristics; instead, our scheme enjoys the unique property that it is proved secure in a formal and precise mathematical sense and with minimal and realistic CPU modification achieves strong provable security guarantees. We envision such systems with a formal mathematical security treatment as a venue for new directions in software protection.

Subject Classification

Keywords
  • Cryptography
  • Software Attestation
  • Provable Security

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. T. AbuHmed, N. Nyamaa, and D. Nyang. Software-based remote code attestation in wireless sensor network. In GLOBECOM'09, pages 4680-4687. IEEE Press, 2009. Google Scholar
  2. W. A. Arbaugh, D. J. Farber, and J. M. Smith. A secure and reliable bootstrap architecture. In SP'97, pages 65-, Washington, DC, USA, 1997. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=882493.884371.
  3. J. Baron, K. El Defrawy, J. Lampkins, and R. Ostrovsky. How to withstand mobile virus attacks, revisited. In M. M. Halldorsson and S. Dolev, editors, PODC 2014, pages 293-302. ACM Press, 2014. Google Scholar
  4. A. Boldyreva, T. Kim, R. J. Lipton, and B. Warinschi. Provably-secure remote memory attestation for heap overflow protection. Cryptology ePrint Archive, Report 2015/729, 2015. Google Scholar
  5. D. Boneh, R. A. DeMillo, and R. J. Lipton. On the importance of checking cryptographic protocols for faults. In EUROCRYPT' 97, volume 1233 of LNCS, pages 37-51. Spriger, 1997. Google Scholar
  6. B. Chen and R. Morris. Certifying program execution with secure processors. In HOTOS'03, pages 23-23. USENIX Association, 2003. Google Scholar
  7. D. Dachman-Soled, F.-H. Liu, E. Shi, and H.-S. Zhou. Locally decodable and updatable non-malleable codes and their applications. In TCC 2015, volume 9014 of LNCS, pages 427-450. Springer, 2015. Google Scholar
  8. Y. Dodis, S. Goldwasser, Y. T. Kalai, C. Peikert, and V. Vaikuntanathan. Public-key encryption schemes with auxiliary inputs. In TCC 2010, volume 5978 of LNCS, pages 361-381. Springer, 2010. Google Scholar
  9. Y. Dodis, Y. T. Kalai, and S. Lovett. On cryptography with auxiliary input. In STOC '09, pages 621-630. ACM, 2009. Google Scholar
  10. S. Dziembowski, K. Pietrzak, and Daniel Wichs. Non-malleable codes. In ICS 2010, pages 434-452, 2010. Google Scholar
  11. K. El Defrawy, G. Tsudik, A. Francillon, and D. Perito. SMART: secure and minimal architecture for (establishing dynamic) root of trust. In NDSS 2012. The Internet Society, 2012. Google Scholar
  12. C. C. Elgot and A. Robinson. Random-access stored-program machines, an approach to programming languages. J. ACM, 11(4):365-399, October 1964. Google Scholar
  13. S. Faust, P. Mukherjee, J. B. Nielsen, and D. Venturi. A tamper and leakage resilient von neumann architecture. In J. Katz, editor, PKC 2015, volume 9020 of LNCS, pages 579-603. Springer, 2015. Google Scholar
  14. A. Francillon, Q. Nguyen, K. B. Rasmussen, and G. Tsudik. A minimalist approach to remote attestation. In DATE'14, pages 244:1-244:6. European Design and Automation Association, 2014. Google Scholar
  15. S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, and B. Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In FOCS 2013, pages 40-49. IEEE Computer Society, 2013. Google Scholar
  16. P. Gemmell and M. Naor. Codes for interactive authentication. In CRYPTO'94, volume 773 of LNCS, pages 355-367. Springer, 1994. Google Scholar
  17. M. Jakobsson and K.-A. Johansson. Practical and secure Software-Based attestation. In LightSec 2011, 2011. Google Scholar
  18. M. Jakobsson and G. Stewart. Mobile malware: Why the traditional AV paradigm is doomed, and how to use physics to detect undesirable routines. In BlackHat 2013, 2013. Google Scholar
  19. A. Juels and B. S. Kaliski Jr. Pors: Proofs of retrievability for large files. In CCS 2007, pages 584-597. ACM, 2007. Google Scholar
  20. R. Kennell and L. H. Jamieson. Establishing the genuinity of remote computer systems. In SSYM'03, pages 21-21. USENIX Association, 2003. Google Scholar
  21. X. Kovah, C. Kallenberg, C. Weathers, A. Herzog, M. Albin, and J. Butterworth. New results for timing-based attestation. In SP 2012, pages 239-253. IEEE Computer Society, 2012. Google Scholar
  22. R. J. Lipton, R. Ostrovsky, and V. Zikas. Provably secure virus detection. U.S. Patent (pending), Application No. 62/054,160, 2014. Google Scholar
  23. R. J. Lipton, R. Ostrovsky, and V. Zikas. Provably secure virus detection: Using the observer effect against malware. Cryptology ePrint Archive, Report 2015/728, 2015. Google Scholar
  24. F. McKeen, I. Alexandrovich, A. Berenzon, C. V. Rozas, H. Shafi, V. Shanbhogue, and U. R. Savagaonkar. Innovative instructions and software model for isolated execution. In HASP'13, pages 10:1-10:1. ACM, 2013. Google Scholar
  25. W. S. McPhee. Operating systems integrity in os/vs2. IBM Systems Journal, 13 Issue 3, pages 230-252, 1974. Google Scholar
  26. R. Ostrovsky and M. Yung. How to withstand mobile virus attacks (extended abstract). In L. Logrippo, editor, PODC '91, pages 51-59. ACM, 1991. Google Scholar
  27. A. Sahai and B. Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In STOC 2014, pages 475-484. ACM, 2014. Google Scholar
  28. A. Seshadri, M. Luk, A. Perrig, L. van Doorn, and P. Khosla. Scuba: Secure code update by attestation in sensor networks. In WiSe'06, pages 85-94. ACM, 2006. Google Scholar
  29. A. Seshadri, M. Luk, E. Shi, A. Perrig, L. van Doorn, and P. Khosla. Pioneer: Verifying code integrity and enforcing untampered code execution on legacy systems. In SOSP'05, pages 1-16. ACM, 2005. Google Scholar
  30. A. Shamir. How to share a secret. Communications of the ACM, 22(11):612-613, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact