{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T00:57:38Z","timestamp":1760057858600,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T00:00:00Z","timestamp":1741046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Union","award":["830929"],"award-info":[{"award-number":["830929"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>The formal study of computer malware was initiated in the seminal work of Fred Cohen in the mid-80s, who applied elements of Computation Theory in the investigation of the theoretical limits of using the Turing Machine formal model of computation in detecting viruses. Cohen gave a simple but realistic formal definition of the characteristic actions of a computer virus as a Turing Machine that replicates itself and proved that detecting this behaviour, in general, is an undecidable problem. In this paper, we complement Cohen\u2019s approach by providing a simple generalization of his definition of a computer virus so as to model any type of malware behaviour and showing that the malware\/non-malware classification problem is, again, undecidable. Most importantly, beyond Cohen\u2019s work, our work provides a generic theoretical framework for studying anti-malware applications and identifying, at an early stage, before their deployment, several of their inherent vulnerabilities which may lead to the construction of zero-day exploits and malware strains with stealth properties. To this end, we show that for any given formal system, which can be seen as an anti-malware formal model, there are infinitely many, effectively constructible programs for which no proof can be produced by the formal system that they are either malware or non-malware programs. Moreover, infinitely many of these programs are, indeed, malware programs which evade the detection powers of the given formal system.<\/jats:p>","DOI":"10.3390\/cryptography9010016","type":"journal-article","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T04:58:17Z","timestamp":1741064297000},"page":"16","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Construction of Countably Infinite Programs That Evade Malware\/Non-Malware Classification for Any Given Formal System"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1162-5490","authenticated-orcid":false,"given":"Vasiliki","family":"Liagkou","sequence":"first","affiliation":[{"name":"Computer Technology Institute and Press\u2014\u201cDiophantus\u201d, University of Patras Campus, 26504 Patra, Greece"},{"name":"Department of Informatics and Telecommunications, University of Ioannina, 47100 Arta, Greece"}]},{"given":"Panagiotis E.","family":"Nastou","sequence":"additional","affiliation":[{"name":"Applied Mathematics and Mathematical Modeling Laboratory, Department of Mathematics, University of the Aegean, 83200 Samos, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5396-3749","authenticated-orcid":false,"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Liverpool L3 5TR, UK"},{"name":"Department of Computer Engineering and Informatics, University of Patras, 26504 Patra, Greece"}]},{"given":"Yannis C.","family":"Stamatiou","sequence":"additional","affiliation":[{"name":"Computer Technology Institute and Press\u2014\u201cDiophantus\u201d, University of Patras Campus, 26504 Patra, Greece"},{"name":"Department of Business Administration, University of Patras, 26504 Patra, Greece"}]}],"member":"1968","published-online":{"date-parts":[[2025,3,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1112\/plms\/s2-42.1.230","article-title":"On Computable Numbers, with an Application to the Entscheidungsproblem","volume":"S2-42","author":"Turing","year":"1937","journal-title":"Proc. Lond. Math. Soc."},{"key":"ref_2","unstructured":"Cohen, F. (1985). Computer Viruses. [Ph.D. Thesis, University of Southern California]."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/0167-4048(87)90122-2","article-title":"Computer Viruses: Theory and Experiments","volume":"6","author":"Cohen","year":"1987","journal-title":"Comput. Secur."},{"key":"ref_4","first-page":"513","article-title":"On the Philosophical Relevance of G\u00f6del\u2019s Incompleteness Theorems","volume":"234","author":"Raattkainen","year":"2005","journal-title":"Rev. Int. Philos."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s11416-015-0261-z","article-title":"A comparison of static, dynamic, and hybrid analysis for malware detection","volume":"13","author":"Damodaran","year":"2017","journal-title":"J. Comput. Virol. Hack. Tech."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Liagkou, V., Nastou, P.E., Spirakis, P., and Stamatiou, Y.C. (2021, January 8\u20139). Effective Enumeration of Infinitely Many Programs that Evade Formal Malware Analysis. Proceedings of the 5th International Symposium on Cyber Security Cryptography and Machine Learning (CSCML2021), Be\u2019er Sheva, Israel.","DOI":"10.1007\/978-3-030-78086-9_18"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1090\/S0002-9947-1953-0053041-6","article-title":"Classes of Recursively Enumerable Sets and Their Decision Problems","volume":"74","author":"Rice","year":"1953","journal-title":"Trans. Am. Math. Soc."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Choi, S., Jang, S., Kim, Y., and Kim, J. (2017, January 18\u201320). Malware detection using malware image and deep learning. Proceedings of the 2017 International Conference on Information and Communication Technology Convergence (ICTC), Jeju, Republic of Korea.","DOI":"10.1109\/ICTC.2017.8190895"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s11416-008-0084-2","article-title":"Code obfuscation techniques for metamorphic viruses","volume":"4","author":"Borello","year":"2008","journal-title":"J. Comput. Virol."},{"key":"ref_10","unstructured":"Venkatachalam, S., and Stamp, M. (2011, January 18\u201321). Detecting undetectable computer viruses. Proceedings of the 2011 International Conference on Security & Management (SAM\u201911), Las Vegas, NV, USA."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/s11416-010-0148-y","article-title":"Hunting for undetectable metamorphic viruses","volume":"7","author":"Lin","year":"2011","journal-title":"J. Comput. Virol."},{"key":"ref_12","unstructured":"Adleman, M. (1988). An Abstract Theory of Computer Viruses. Advances in Cryptology, Crypto\u201988, Springer. LNCS 403."},{"key":"ref_13","unstructured":"Young, A., and Yung, M. (1996, January 6\u20138). Cryptovirology: Extortion-Based Security Threats and Countermeasures. Proceedings of the IEEE Symposium on Security & Privacy, Oakland, CA, USA."},{"key":"ref_14","unstructured":"Young, A., and Yung, M. (2010). Malicious Cryptography: Exposing Crytovirology, Wiley."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"3319","DOI":"10.1098\/rsta.2011.0332","article-title":"From Turing machines to computer viruses","volume":"370","author":"Marion","year":"2012","journal-title":"Philos. Trans. R. Soc. A"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1016\/j.jnca.2012.10.004","article-title":"Classification of malware based on integrated static and dynamic features","volume":"36","author":"Islam","year":"2013","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_17","unstructured":"Elgamal, M.E.A. (2014). The Extended Maurer Model: Bridging Turing-Reducibility and Measure Theory. [Ph.D. Thesis, University of Victoria]."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"e3675","DOI":"10.1002\/ett.3675","article-title":"Android malware detection through generative adversarial networks","volume":"33","author":"Amin","year":"2022","journal-title":"Trans. Emerg. Telecommun. Technol."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1758","DOI":"10.1016\/j.future.2012.02.006","article-title":"State of the art: Dynamic symbolic execution for automated test generation","volume":"29","author":"Chen","year":"2023","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"You, I., and Yim, K. (2010, January 4\u20136). Malware obfuscation techniques: A brief survey. Proceedings of the 2010 International Conference on Broadband, Wireless Computing, Communication and Applications (BWCCA), Fukuoka, Japan.","DOI":"10.1109\/BWCCA.2010.85"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Mohammed, M.M.Z.E., Chan, H.A., and Ventura, N. (2008, January 16\u201319). Honeycyber: Automated signature generation for zero-day polymorphic worms. Proceedings of the MILCOM 2008\u20142008 IEEE Military Communications Conference, San Diego, CA, USA.","DOI":"10.1109\/MILCOM.2008.4753178"},{"key":"ref_22","unstructured":"Avgerinos, T., Cha, S.K., Brent, B.T.H., and Brumley, D. (2011, January 6\u20139). AEG: Automatic Exploit Generation. Proceedings of the Network and Distributed System Security Symposium, NDSS 2011, San Diego, CA, USA."},{"key":"ref_23","unstructured":"Kirat, D., Jiyong, J., and Stoecklin, M. (2018). Deeplocker Concealing\u2014Targeted Attacks with AI Locksmithing, IBM. IBM Research Report."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Chaganti, R., Ravi, V., Alazab, M., and Pham, T.D. (2021). Stegomalware: A systematic survey of malware hiding and detection in images, machine learning models and research challenges. arXiv.","DOI":"10.36227\/techrxiv.16755457"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Cobb, S., and Lee, A. (2014, January 3\u20136). Malware is called malicious for a reason: The risks of weaponizing code. Proceedings of the 6th International Conference on Cyber Conflict (CyCon 2014), Tallinn, Estonia.","DOI":"10.1109\/CYCON.2014.6916396"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Fritsch, L., Jaber, A., and Yazidi, A. (2022). An Overview of Artificial Intelligence Used in Malware. Nordic Artificial Intelligence Research and Development, Proceedings of the 4th Symposium of the Norwegian AI Society (NAIS 2022), Oslo, Norway, 31 May\u20131 June 2022, Springer. Communications in Computer and Information Science.","DOI":"10.1007\/978-3-031-17030-0_4"},{"key":"ref_27","unstructured":"Kubovi\u010d, O., Ko\u0161in\u00e1r, P., and J\u00e1no\u0161\u00edk, J. (2018). Can Artificial Intelligence Power Future Malware?, ESET. Technical Report."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"27","DOI":"10.13164\/mendel.2019.2.027","article-title":"A survey on artificial intelligence in malware as next-generation threats","volume":"25","author":"Thanh","year":"2019","journal-title":"Mendel"},{"key":"ref_29","unstructured":"Zouave, E., Gustafsson, T., Bruce, M., and Colde, K. (2020). Artificially Intelligent Cyberattacks, Totalf\u00f6rsvarets Forskningsinstitut FOI. Technical Report, FOI-R-4947-SE."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"150","DOI":"10.2307\/2267778","article-title":"On notation for ordinal numbers","volume":"3","author":"Kleene","year":"1938","journal-title":"J. Symb. Log."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Davis, M. (2018). The Universal Computer: The Road from Leibniz to Turing, CRC Press. [3rd ed.].","DOI":"10.1201\/9781315144726"},{"key":"ref_32","unstructured":"Hopcroft, J., and Ullman, J.D. (1979). Introduction to Automata Theory, Languages, and Computation, Addison-Wesley."},{"key":"ref_33","unstructured":"Evans, D. (2011). Introduction to Computing: Explorations in Language, Logic, and Machines, CreateSpace Independent Publishing Platform."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Liagkou, V., Nastou, P.E., Spirakis, P., and Stamatiou, Y.C. (July, January 30). On the undecidability of the Panopticon detection problem. Proceedings of the 6th International Symposium on Cyber Security, Cryptology and Machine Learning (CSCML 2022), Be\u2019er Sheva, Israel.","DOI":"10.1007\/978-3-031-07689-3_6"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/1008335.1008336","article-title":"Independence results in computer science","volume":"8","author":"Hartmanis","year":"1976","journal-title":"ACM SIGACT News"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"297","DOI":"10.25088\/ComplexSystems.25.4.297","article-title":"A relatively small Turing machine whose behaviour is independent of set theory","volume":"25","author":"Yedidia","year":"2016","journal-title":"Complex Syst."},{"key":"ref_37","unstructured":"O\u2019Rear, S. (2025, February 21). Metamath Turing Machines. Available online: https:\/\/github.com\/sorear\/metamath-turing-machines."},{"key":"ref_38","unstructured":"Quine, W.V. (1940). Mahematical Logic, Harvard University Press."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/358198.358210","article-title":"Reflections on trusting trust","volume":"27","author":"Thompson","year":"1984","journal-title":"Commun. ACM"}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/9\/1\/16\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:46:46Z","timestamp":1760028406000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/9\/1\/16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,4]]},"references-count":39,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,3]]}},"alternative-id":["cryptography9010016"],"URL":"https:\/\/doi.org\/10.3390\/cryptography9010016","relation":{},"ISSN":["2410-387X"],"issn-type":[{"type":"electronic","value":"2410-387X"}],"subject":[],"published":{"date-parts":[[2025,3,4]]}}}