Extra Polymorphic Worms

by Dr. Leovinus

All of the information, ideas, and source code appearing in this article is for educational purposes only.

I deny any responsibility for any use of the information, ideas, and code appearing here, including any responsibility for any variation thereof. My goal is to educate users on just how dangerous new generations of worms and viruses may become so that they can start developing security methods to combat such viruses. All code is written in Java due to its built-in security (which should prevent the included code from being used in destructive applets as is).

In the Winter 2000-2001 issue, xdroop presented us with a polymorphism script (for demonstration purposes only!) written after the polymorphic variant of the ILOVEYOU Visual Basic Script worm that improved on the comment rewrite strategy employed successfully by the worm. It not only added random comment characters interleaved inside the script with each generation but also removed all of the existing comments first so that there would be no comparison between the signatures left by the comments in the new generation when compared with the existing generation.

Although such a script would fool the majority of e-mail virus detectors that simply rely on known signatures during the virus detection process, they would not get by polymorphic virus detectors that were smart enough to base their signatures on executable code only (and they definitely would not get by advanced virus detectors that used standard generic decryption techniques in a virtual computer which analyzed execution sequences). However, if we take the ideas presented in the article one step further, we could easily create a worm or Trojan which did.

First of all, why stop at comment mutations? Many of today's languages, especially those that support object-based structures to some degree, make code mutation trivial. For example, in Java, I can write a simple program (ReWriter) that will rename all of the class methods and attributes of a given class - the vast majority of the time. (I failed to check for unusual or special syntax in the script and this could be a problem - the script does work on itself ad infinitum.) It is impossible to create a static signature for a worm or Trojan based on such a script.

With sufficient analysis, it is possible that one could come up with a relatively accurate dynamic signature of the form "[i1 ... i2 ... i3 ... ma ...]" (i = instruction, m = method call / jump instruction) where all method and attribute names were ignored and only the syntactical structure was analyzed, but as all programs coded in the same language are limited to a relatively small instruction set, the signature would have to be quite large to have any degree of accuracy and would thus be quite difficult to generate from a pure analysis of viral activity.

Moreover, assuming that one could develop such a generic signature dynamically from an analysis of multiple infections, we could take the random nature of our worm one step further and dynamically vary the order of operations. Most of the time, it is possible to identify groups of operations that can be performed in parallel as they are not interdependent and this will allow us to break down our program into precedence groups, where the operations in each group can be performed in random order as long as the operations in the first group are performed before the operations in the second group, etc.

This is also relatively easy to do in some languages. For example, in Java, if we break down each independent operation, or set of operations, into a different method and classify each method into a different precedence group, we can use reflection to dynamically run the methods in a pseudo-random order and produce a different instruction sequence on each run, which, when combined with polymorphic comments and user-defined names, will completely nullify any attempt to generate a usable signature and allow the virus to slip past any virus detector that is signature based. For example, if each method that can be run in a pseudo-random order inside a precedence group stores its own precedence level, one can write a method in Java in under 30 lines to pseudo-randomly execute every method in a Java class using reflection (RandomRunner).

Of course, there is still a good chance that our worm or Trojan will be intercepted by a generic decryptor that uses non-virus specific heuristics that runs the file containing the worm or Trojan inside a virtual computer before declaring the file as clean, especially if the implementation of this technology is solid. However, an extension of the above technique could be used to defeat even this technology, which is the most sophisticated anti-virus technology available. The trick is to insure that your worm or Trojan performs multiple actions on execution, including those that are benign (and maybe even beneficial). If your worm simply 1.) executes instructions to load all of the addresses in the address book, 2.) creates a copy of itself for each address, and 3.) sends itself off, this viral pattern will be detected by a well-coded generic decryptor based on a large database of heuristic evidence even though a good implementation of the above techniques will allow the worm or Trojan to slip past a signature based detection scheme.

If your worm a.) propagated itself using a prolonged, indirect variant of the algorithm used above, b.) played an included video or sound file, c.) created a useful looking document or spread-sheet according to well-accepted local system rules, and d.) automatically executed some standard commands like auto-reply and open new message window and interleaved each of these tasks into one super-task using the precedence group above, then no predictable pattern would stand out upon execution inside the virtual computer and, chances are, your worm or Trojan would be given a clean bill of health.

In summary, as with xdroop's article, I believe that the ideas presented herein form the basis of interesting and challenging problems. Problems that should be thought about, analyzed, and solved by the hacker community at large before some rogue hacker who does not represent the community solves these problems and uses the knowledge therein to infiltrate and damage systems and ruin our bad name.

I also like interesting problems and am anxious to see what others can come up with, particularly in terms of detection and identification algorithms. So I pose a challenge. Algorithmically speaking, what is the most undetectable worm, Trojan, or virus that you can devise and how would you stop such a worm, Trojan, or virus from infecting computers in the real world?

Happy sleuthing.

/* Begin ReWriter.java file */
import java.lang.reflect.Field;
import java.lang.reflect.Method;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.PrintWriter;
import java.io.FileOutputStream;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

/* This class "rewrites" itself when its rewriteSelf() method is called; it randomly changes its name, its 
 * method names, its attribute names, and its comments */
public class ReWriter {

    /* This attribute stores the symbols used in java operators / programs; these must be separated from methods
     * and attributes for the renaming to take place; fortunately, java ignores whitespace so even as strange as
     * method . runit ( abc ) may look, it is perfectly legal */
    String ops = ".[]()+-!*;,/%<>=&^|~?:";
    // note that backslash (\) and quotes (',") are omitted

    /* This attribute stores a StringCompare comparator */
    StringCompare sc = new StringCompare();

    /* This attribute stores the original names of the methods and fields being mapped */
    String originals[] = null;

    /* This attribute stores the new names of the methods and fields being mapped */
    String nameMaps[] = null;

    /* The main method */
    public static void main(String[] args) {
        ReWriter rw = new ReWriter();
        rw.rewriteSelf();
    }

    /* This method returns a replacement for the input String guaranteed to be unique among all inputs; in reality, 
     * a much more complex random mapping would be used */
    public String nameMap(String iName) {
        if (iName.compareTo("main") != 0) {
            return iName + "_xxx";
        } else {
            return "main";
        }
    } // mapName ()

    /* This method surrounds operators with white space for the rewriter */
    String spaceOutOperators(String st) {
        int j = 0;
        for (int i = 0; i < st.length(); i++) {
            if (ops.indexOf(st.charAt(i)) >= 0) {
                j = i + 1;
                while ((j < st.length()) && (ops.indexOf(st.charAt(j)) >= 0)) {
                    j++;
                }
                st = st.substring(0, i) + " " + st.substring(i, j) + " " + st.substring(j);
                i = j;
            }
        }
        return st;
    } // spaceOutOperators ( String )

    /* This method rewrites the given class */
    public void rewrite(Class c) {
        try {
            // get the method and field references
            Method[] m = c.getDeclaredMethods();
            Field[] f = c.getDeclaredFields();
            // create a map of the class, method, and field names
            int nummaps = m.length + f.length + 1;
            originals = new String[nummaps];
            nameMaps = new String[nummaps];
            // store the class name and map name
            originals[0] = c.getName();
            // store the method names
            for (int i = 0; i < m.length; i++) {
                originals[1 + i] = m[i].getName();
            }
            // store the field names
            for (int i = 0; i < f.length; i++) {
                originals[1 + m.length + i] = f[i].getName();
            }
            // sort the array
            Arrays.sort(originals, sc);
            // map the names
            for (int i = 0; i < nummaps; i++) {
                nameMaps[i] = nameMap(originals[i]);
            }
            // Load the input file
            String cName = c.getName() + ".java";
            BufferedReader br = new BufferedReader(new FileReader(cName));
            ArrayList al = new ArrayList();
            int loc = 0;
            al.add(0, " ");
            while (al.get((al.size() - 1)) != null) {
                al.add(br.readLine());
            }
            br.close();
            al.trimToSize();
            //tokenize it; search for class, method , & field names; replace with nameMaps; output
            String oName = nameMaps[Arrays.binarySearch(originals, c.getName(), sc)] + ".java";
            PrintWriter pw = new PrintWriter(new FileOutputStream(oName), true);
            StringTokenizer st = null;
            String tken = null;
            int pos = -1;
            String tmp = null;
            ops.trim();
            for (int i = 1; i < al.size(); i++) {
                if (al.get(i) != null) {
                    tmp = (String)(al.get(i));
                    tmp = spaceOutOperators(tmp);
                    st = new StringTokenizer(tmp);
                    while (st.hasMoreTokens()) {
                        tken = st.nextToken();
                        pos = Arrays.binarySearch(originals, tken, se);
                        if (pos >= 0) {
                            pw.print(nameMaps[pos] + " ");
                        } else {
                            pw.print(tken + " ");
                        }
                    } // whilte more tokens on line
                    pw.println();
                } // if there is a line to process
            } // while more lines in file
            pw.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    } // rewrite (Class)

    /* This method rewrites this class  */
    public void rewriteSelf() {
        rewrite(this.getClass());
    } // rewriteSelf()
} // Rewriter

class StringCompare implements Comparator {
    public int compare(Object s1, Object s2) {
        return ((String)(s1)).compareTo(((String)(s2)));
    }

} //StringCompare

/* End ReWriter.java file */

/* Begin RandomRunner.java file */
import java.lang.reflect.Method;
import java.util.Random;

/* This class runs its own methods in random order, by precedence group */
public class RandomRunner {

    /* This attribute stores the number of the highest precedence group , which are assumed to go from 0 to this number - 1 */
    int mg = 3;

    /* The random number generator */
    Random r = new Random();

    /* The main method */
    public static void main(String[] args) {
        try {
            RandomRunner RR = new RandomRunner();
            RR.executeMethods();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    /* The following are some * random * methods ... */
    public int method_01(Boolean getGroup) {
        if (getGroup.booleanValue()) {
            return 1;
        } else {
            System.out.println("method_01 fired");
            return 0;
        }
    } // method_01()

    public int method_02(Boolean getGroup) {
        if (getGroup.booleanValue()) {
            return 1;
        } else {
            System.out.println("method_02 fired");
            return 0;
        }
    } // method_02()

    public int method_03(Boolean getGroup) {
        if (getGroup.booleanValue()) {
            return 2;
        } else {
            System.out.println("method_03 fired");
            return 0;
        }
    } // method_03()

    public int method_04(Boolean getGroup) {
        if (getGroup.booleanValue()) {
            return 2;
        } else {
            System.out.println("method_04 fired");
            return 0;
        }
    } // method_04()

    public int method_05(Boolean getGroup) {
        if (getGroup.booleanValue()) {
            return 2;
        } else {
            System.out.println("method_05 fired");
            return 0;
        }
    } // method_05()

    /* The proceding are some * random * methods */

    /* This method creates an array with the integers 0 to l - 1 in random order */
    public int[] getRandomOrder(int l) {
        int[] x = new int[l];
        for (int i = 0; i < l; i++) {
            x[i] = i;
        }
        int tmp = 0;
        int p = 0;
        int q = 0;
        for (int i = 0; i < l; i++) {
            p = r.nextInt(l);
            q = r.nextInt(l);
            if (p != q) {
                tmp = x[p];
                x[p] = x[q];
                x[q] = tmp;
            }
        }
        return x;
    }

    /*This method executes the class methods in (pseudo) random order */
    public void executeMethods() throws Exception {
        Method[] m = this.getClass().getDeclareciMethods();
        int xg[] = new int[m.length];
        Object[] o = new Object[1];
        Object[] O = new Object[1]
        o[0] = new Boolean(true);
        O[0] = new Boolean(false);

        // get distinct precedence group for each method

        for (int i = 0; i < m.length; i++) {
            if (m[i].getReturnType() != int.class) {
                xg[i] = 0;
            } else {
                xg[i] = ((Integer)(m[i].invoke(this, o))).intValue();
            }
        }

        // count number of methods per distinct precedence group
        short[] cg = new short[mg];
        for (int i = 0; i < m.length; i++) {
            cg[xg[i]] = (short)(cg[xg[i]] + 1);
        }
        // divide methods into precedence groups
        // first create precdence groups
        Method[][] z = new Method[mg][];
        for (int i = 0; i < mg; i++) {
            z[i] = new Method[cg[i]];
        }

        // now initialize references  to first free locations in each group
        for (int i = 0; i < mg; i++) {
            cg[i] = 0;
        }
        // divide up method references
        for (int i = 0; i < m.length; i++) {
            z[xg[i]][(cg[xg[i]]) ++] = m[i];
        }

        // execute methods in random order; "0" methods do not get executed randomly
        int[] y = null;
        for (int i = 1; i < mg; i++) {
            y = new int[z[i].length];
            y = getRandomOrder(y.length);
            for (int j = 0; j < y.length; j++) {
                z[i][y[j]].invoke(this, O);
            }
        }
    } // executeMethods
} // RandomRunner

/* End  RandomRunner.java file  */

Code: ReWriter.java

Code: RandomRunner.java

Return to $2600 Index