Source-linked AI summary
Metamorphism: A mathematical challenge for antivirus technology
Luis M. Augusto
TL;DR
The paper addresses the difficulty of detecting metamorphic viruses, whose code can produce highly dissimilar copies while preserving functionality. It uses van Wijngaarden grammars to formalize pure viral metamorphism and identifies Turing-machine language decision as the antivirus challenge. The paper also states that viral detection and evolution questions receive negative answers through reduction to the halting problem, while the proposed grammar construction is subject to syntactic and finiteness conditions.
Problem
Metamorphic viruses can mutate their code into highly dissimilar replicas, making static analysis insufficient and antivirus detection difficult.
Method
The paper formalizes pure metamorphic viruses with van Wijngaarden grammars and frames antivirus analysis through Turing machines deciding the generated language.
Results
The paper claims that pure metamorphic viruses can be designed with van Wijngaarden grammars and states that viral detection and evolution problems are undecidable.
Takeaways & Limitations
The proposed formalization makes viral metamorphism a problem in formal-language theory and computability rather than only code-pattern recognition.
Takeaways & Limitations
The language generated by a van Wijngaarden grammar is a recursively enumerable language only when its RS set is finite; otherwise it is equivalent to a context-free language.
Abstract
from arXiv · showhide
Metamorphic viruses, currently the most advanced computer viruses in the wild, have the unique ability of mutating their own code virtually into infinitely many highly dissimilar copies of themselves that nevertheless have the same functionality. This ability -- metamorphism -- together with other advanced ob- fuscation techniques makes these computer viruses virtually undetectable by the antivirus software available in the market today. In this paper, we show that viral metamorphism is fully attainable by the employment of van Wijngaarden grammars. The challenge then for an antivirus software is to embed the Turing machine that decides the language generated by the grammar.
1 Introduction
The paper presents metamorphic viruses as a mathematically intensified antivirus challenge: they generate highly dissimilar replicas, and their construction and detection involve advanced computational properties.
- 1 Introduction: Virus designers use mathematical techniques and advanced obfuscation, increasing the technical demands placed on antivirus companies.The paper describes this broader approach as malicious mathematics and mentions k-ary coding as an additional obfuscation technique.
- 1 Introduction: The paper places malware design using mathematics within a broader literature on malicious mathematics and its applications.It notes related work in monographs and papers, including applications to cryptography.
- 1 Introduction: Metamorphic viruses generate highly dissimilar replicas of themselves to evade antivirus detection and analysis.Unlike typical viruses, their construction requires strong mathematical skills in addition to computing expertise.
- 1 Introduction: Metamorphic viruses are difficult to write but offer near-undetectability, making their analysis necessary and urgent.The paper connects this urgency to their potential hybridization with advanced obfuscation and their prospective role in warfare.
- 1 Introduction: The paper associates metamorphic viruses with van Wijngaarden grammars and claims that such grammars can design a pure metamorphic virus.It frames antivirus analysis as embedding a Turing machine that decides the language generated by the grammar.
2 Preliminary De nitions and Results
This section develops computability and Turing-machine foundations for formalizing viruses, then connects self-replication and evolution to viral sets and computable functions.
- 2.1 Preliminary Definitions: A computer virus is formalized as a program that replicates its code in a host and may evolve different copies during replication.The formal viral-set definition represents replication through Turing-machine computations that write a new virus at a sufficiently distant tape position.
- 2.1 Preliminary Definitions: Computability is defined through effective calculation, with Turing machines serving as the model of effective calculability.The section distinguishes total computable functions from partial computable functions, which may be undefined for some inputs.
- 2.1 Preliminary Definitions: Primitive computable functions are generated from zero, successor, and projection functions through composition and primitive-recursive schemata.The section presents these functions as a special group within computable functions.
- 2.1 Preliminary Definitions: Turing machines are specified by states, an alphabet, tape motions, an output function, a transition function, and a motion function.The temporal-function framework identifies tape cells, machine steps, time instants, and computation history.
- 2.2 Self-Replication: The section connects self-replication with computability results, including closure of partial computable functions under fixpoint definitions.It also states that computably equivalent machines compute the same function and relates machine representations to self-replicating machines.
- 2.3 Viral Evolution: Viral evolution is defined as modifying a virus's code during replication so that each offspring is a mutation of its predecessor.The section states that finite unions of viral sets are also viral sets and introduces a largest viral-set construction.
3 Evolving Viruses and Further Computability Theory
The section frames viral detection, evolution, and computability as decidability problems, then distinguishes encryption, polymorphism, and metamorphism by how virus code changes across generations.
- Decidability Problems: Three questions address whether virus status, evolution from v to v′, and viral evolution of arbitrary strings can be decided in finite time.They are termed the viral detection, viral evolution, and viral computability problems.
- Decidability Problems: Cohen gives negative answers to viral detection and evolution by reducing them to the halting problem, while viral computability has a positive answer.Any string computable by the universal Turing machine may be a viral evolution.
- Mutating Viruses: A mutating virus is a pair (v, v′) where v′ differs from v but both belong to the language recognized by the same Turing machine.Each replication or copy v′ is called a mutation or generation of the root virus v.
- Mutating Viruses: The language L(M) of a mutating virus is countable, with successive mutations indexed as v0, v1, and so on.The proof identifies the root virus as v0 and its successive generations as vi for i = 1, 2, ....
- Code Camouflage: Encryption keeps the decryptor constant, polymorphism changes the decryptor while keeping the encrypted body constant, and metamorphism changes both.The three categories differ by which components change from generation to generation.
- Antiviral Techniques: Static analysis searches for invariant viral signatures, but metamorphic mutations leave fewer than the sixteen unique bytes required for detection.Antivirus software therefore resorts to dynamic techniques such as code emulation for viruses whose code mutates during replication.
- Polymorphic vs. Metamorphic Viruses: Polymorphic viruses can be detected through emulation, whereas metamorphic viruses need not retain a constant body or decryptor and instead require only a metamorphic engine.The paper connects this distinction to the integration of data and programs in viral code and introduces the s-m-n theorem.
- Polymorphic vs. Metamorphic Viruses: The formalization realizes polymorphic and metamorphic viruses through two distinct mutation engines, with the latter characterized by S(p) ≠ S′(p).The paper states that Figures 1 and 2 show these distinct engines.
4 Viral Metamorphism and Formal Grammars
The paper frames metamorphic-virus detection as a formal-language decision problem and argues that van Wijngaarden grammars can construct viruses whose code and grammar mutate while functionality is preserved. It further identifies undecidability as the central challenge for antivirus technology.
- 4.1 The Viral Decision Problem and Formal Language Theory: Metamorphic-virus detection is presented as an intractable decision problem within formal-language theory.The paper connects viral programs with strings in formal languages and frames detection as deciding language membership or equivalence.
- 4.1 The Viral Decision Problem and Formal Language Theory: A recognizer M decides whether the language generated by grammar G equals the language accepted by M.This theorem supplies the formal basis for treating a recognizer as a solution to a language decision problem.
- 4.2 Viral Polymorphism and Polymorphic Grammars: Regular grammars can generate potentially infinite mutation patterns, but their decision problems remain decidable in complexity class P.Using CFGs or CSGs can move polymorphic-virus identification from P to NP, while the cited regular-language construction remains decidable.
- 4.1 The Viral Decision Problem and Formal Language Theory: Metamorphic coding is associated with greater antivirus difficulty because metamorphic viruses change code while preserving functionality, unlike ordinary polymorphic variation.The paper also notes that metamorphism has applications in protecting proprietary software code.
- 4.3 Pure Metamorphic Viruses and the van Wijngaarden grammars: The paper claims that a pure metamorphic virus can be constructed entirely with a van Wijngaarden grammar.Its formal support requires showing language membership, potentially infinite mutations, preserved functionality, and an unsolvable decision problem.
- 4.3 Pure Metamorphic Viruses and the van Wijngaarden grammars: A van Wijngaarden grammar can generate multiple strict subgrammars, allowing a virus to change its grammar as well as the words produced by each grammar.The paper distinguishes this grammatical mutation from polymorphism, which changes code forms without requiring grammar changes.
- 4.3 Pure Metamorphic Viruses and the van Wijngaarden grammars: Van Wijngaarden grammars preserve meaning during syntactic change through the coincidence SLs(GS) = bG.The paper identifies this semantic correspondence as the source of metamorphism in the generated language.
- 4.3 Pure Metamorphic Viruses and the van Wijngaarden grammars: Languages generated by van Wijngaarden grammars can be recursively enumerable and undecidable, with undecidability depending on grammar structure and syntactic properties.The paper states that REL generation requires a finite strict-rule set, while other WG configurations can be equivalent to context-free languages; it also gives an undecidability result for unique left parses.