Abstract
This paper presents a new class of (malicious) codes denoted k-ary codes. Instead of containing the whole instructions composing the program’s action, this type of codes is composed of k distinct parts which constitute a partition of the entire code. Each of these parts contains only a subset of the instructions. When considered alone (e.g. by an antivirus) every part cannot be distinguished from a normal uninfected program while their respective action combined according to different possible modes results in the offensive behaviour. In this paper, we presents a formalisation of this type of codes by means of Boolean functions and give their detailed taxonomy. We first show that classical malware are just a particular instance of this general model then we specifically address the case of k-ary codes. We give some complexity results about their detection based on the interaction between the different parts. As a general result, the detection is proved to be NP-complete.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bondy, J.A.: Basic Graph Theory: Paths and Circuits. In: Graham, R., Grötschel, M., Lovasz, L. (eds) Handbook of Combinatorics, Vol. 1, North Holland (1995)
Cohen, F.: Computer viruses, PhD Thesis, University of Southern California (1986)
De Drézigué D., Fizaine J.-P., Hansma N. (2006) In-depth analysis of the viral threats with OpenOffice.org documents. J. Comput. Virol. 2(3): 187–210
Filiol, E.: Techniques de reconstruction en cryptographie et en théorie des codes. PhD Thesis, école Polytechnique (2001)
Filiol, E.: Computer viruses: From theory to applications. IRIS International Series. Springer, France, ISBN 2-287-23939-1 (2005)
Filiol E. (2007) Techniques virales avancées, IRIS Series, An English translation is pending (due mid-2007). Springer, France
Filiol E. (2007) Metamorhism, formal grammars and undecidable code mutation. Int. J. Appl. Math. Comput. Sci. 4(2): 503–508. http://www.waset.org/ijamcs/v4-2.html
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman (1979)
King, S.T., Chen, P. M., Wang, Y.-M., Verbowski, C., Wang, H.J., Lorch, J.R.: SubVirt: Implementing malware With virtual machines, University of Michigan et Microsoft Research (2006)
Papadimitriou, C.H.: Computational complexity. Addison-Wesley, Reading. ISBN 0-201-53082-1 (1995)
Riordan J., Schneier B. (1998) Environmental key generation towards clueless agents. In: Vigna G. (eds). Mobile Agents and Security Conference’98, Lecture Notes in Computer Science. Springer, Heidelberg, pp. 15–24
Rutkowska, J.: Subverting vista kernel for fun and profit. SysCan’06 Conference, Singapore, July 21 2006
Spinellis D. (2003) Reliable identification of bounded-length viruses is NP-complete. IEEE Trans. Inf. Theory 49(1): 280–284
Thomassen C. (1985) Even Cycles in Directed Graphs. European Journal in Combinatorics 6: 85–89
Zuo Z., Zhou M. (2004) Some further theoretical results about computer viruses. Comput. J. 47(6): 627–633
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Filiol, E. Formalisation and implementation aspects of K-ary (malicious) codes. J Comput Virol 3, 75–86 (2007). https://doi.org/10.1007/s11416-007-0044-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11416-007-0044-2