<commit_before># An algorithm to calculate malware phylogeny, an example and counterexample

Source code for malware can easily be had by [googling](https://www.google.com/search?q=web+shell+wso+filesman),
[searching on pastebin](http://pastebin.com/search?q=WSO)
or running [WordPress honey pot](http://stratigery.com/phparasites/).
Much of it is interpreted languages, like PHP or Perl.

I will use "Web Shell by oRb" (a.k.a "WSO", "FilesMan") and the omnipresent IRC Perl bot
(Perl/Shellbot.B) as examples.

"Web Shell by oRb" (also called "WSO", "FilesMan" and "AntiChat shell") is by far the most
popular web shell downloaded to hacked CMS web sites today. It's often reformatted, obfuscated
or otherwise slightly customized before hiding it in a WordPress installation. It comes
in many distinct versions, including [one under active development](https://github.com/wso-shell/WSO).

The omnipresent IRC Perl bot is referred to by antivirus firms as
"Perl/Shellbot" or some form of that indicating a derivative. A typical variant
can be had from [Pastebin](http://pastebin.com/CJpxW5tx).  Perl/Shellbot is a piece
of Perl that understands the IRC protocol. Specially formatted messages from
the botherder cause the bot to do things, like perform a UDP packet flood, run
a command via the system's shell, or look up "dorks" in every search engine on
the planet. The code arrives in a dazzling number of variants, some with
function names and commentary in Portugese, others with function names & etc in
English. Every botherder seems to do minor customization.

Casual reading of several variants of either WSO or Perl/Shellbot will convince
you that the variants are "related". It seems that one variant "evolved" into another via a
process of spammers making small changes to suit their needs. Perhaps a selection of the
"fittest" happens when one script kiddy copys the succssful code of another script kiddy.
Collection and comparison of variants should allow the construction of a "family tree"
of variants. This project is a description and demonstration of one method of constructing
the family tree, or phylogeny, of WSO, and less succesfully, of Perl/Shellbot.

##Source code malware evolution

Ordinary biological evolution analogies are ill-suited to guessing
malware phylogenies.
Biological phylogenies assume binary splits between two clades, and 
assume that we know the sister clades, but can't identify the
the common ancestor.
Malware can split many times from an identifiable common ancester.
Biological phylogenies assume a single common ancestor.
Malware often, maybe almost always, has more than
a single ancestor.

Souce code malware seems to evolve by feature addition or subtraction.
Malware modifiers add small chunks of code, code that might phone home
with URL, user ID and password, or just evaluate some code when
executed with a special CGI-BIN parameter.
Sometimes entire functions or subsystems are transplanted from another
program.

When the "source code" of biological families is available, it rarely if ever
shows evolution by adding or subtracting entire "features". Biological evolution
appears to happen by gradual changes over large extents of a clade's DNA. 

##Neighbor Joining

Tradtional biological phylogenies are sometimes calculated with some "distance"
metric, and tree construction algorithms like
[Neighbor Joining](https://en.wikipedia.org/wiki/Neighbor_joining).

###Normalized Compression Distance

I used the NCD algorithm from [Common Pitfalls Using The Normalized Compression Distance](http://www.ims.cuhk.edu.hk/~cis/2005.4/01.pdf)
it seems to give closer-to-zero "distance" of a piece of code to itself. The code is in
`distance_calc.php`

    NCD(x,y) = max(C(xy) - C(x), C(yx) - C(y)}/max(C(x), C(y))

`NCD(x,y)` is the normalized compression distance from string `x` to string `y`,
`max(a, b)` is the numerical maximum of numbers `a` and `b`, and `C(e)` is the
size in bytes of compressed string `e`. `xy` is string `x` with string `y`
appended. Note that `NCD(x,y)` should be numerically equal to `NCD(y,x)`.

All files in `exemplars/` are PHP source code, normalized by [pretty
printing](https://github.com/nikic/PHP-Parser), and removing ASCII carriage
return characters. I did an NCD calculation on all PHP malware in `exemplars`.
Using the neighbor joining algorithm, I produced the following phylogeny.
To get a rooted tree from neighbor joining, you have to pick an "outgroup". I
chose `lfiscanner.php`.

![WSO phylogeny by NCD and neighbor joining](https://raw.githubusercontent.com/bediger4000/malware-phylogeny/master/nj_phylogeny.png)

The horizontal lengths of branches are proportional to the normalized
compression distance the source files are apart.

NCD and neighbor joining get some parts of the phylogeny correct. Although I
chose `lfiscanner` as the out group, it correctly found the `fx29` web shell as
the next most distantly-related piece of code. It gets the basic split between
WSO 2.4 and WSO 2.5 clades, but mixes version 2.8 and 3.1 in the 2.4-based
clade - version 2.8 is clearly a minor hack of version 2.5.1, differing only by
yet another phone home. Version 3.1 descends from 2.5 by the verbatim
incorporation of a local-file-include scanner from `lfiscanner.php`.

The assumptions inherent in neighbor joining make version 2.4 into an out group
of a clade, where it should be seen as the common ancestor of most of the
verions in the sister clade.  Version 2.4 should be seen as the ancestor of a
linear progression of 2.5 to 2.5.1 to 2.8. The entire issue of multiple
ancestry doesn't come into this method of deriving a phylogeny at all.  `fx29`
and `lfiscanner.php` should show up as secondary ancestors to multiple variants
that have a WSO variant as a primary ancestor.

All told, this phylogeny is roughly correct, but has too many flaws to be more than a general
guide.

##Algorithm

Because malware evolves by feature addition, and not by changes in their genomes,
I tried to use the pieces of source code that differ between species, and
the pieces of source code that remain common between all members of a clade
to derive a phylogeny. I explictly allow for multiple ancestry.

###Determine Features

Naturally, this is the important part, and not amenable to automation. The algorithm
needs at least one trait (line or lines of source code) common between an ancestor
and all of its desendants. It will calculate two trees if this condition is not met.

The algorithm needs each pair of species to differ in at least one trait.

###Description

1. Order species in a list by decreasing number of features.
2. Remove species with largest number of feature from species list. This species becomes the current species.
3. Compare current species featuries to other specie's features in order.
4. When the other species has features that are a strict subset of current feature list,
   and contains a feature previously unmarked, assign current species as child of other species.
5. Mark all traits of the current species common to the new parent.
6. If more than one trait is unmarked, repeat from (3)
7. If no more than one trait is unmarked, go to one.
8. If you have compared traits of the current species to all species left,
   the current species hasn't been added to any species as a child,
   and still have more than one unmarked traits, add the current species
   to the set of root species.

###Performance

The algorithm above always terminates. Every species gets popped off ordered list of species.

####Worst case 
One root, many children, no grandchildren. All children have a lot of common traits,
one trait differentiating.  Worst case O(n^2) for comparison of traits.

###Effect of ill-chosen features

Two species without at least one trait to differentiate them, show up as sister species.
Correctly chosing traits could cause one to show up as the child of the other.
<commit_msg>Lots of tiny improvements and additions.<commit_after># An algorithm to calculate malware phylogeny, an example and counterexample

Source code for malware can easily be had by [googling](https://www.google.com/search?q=web+shell+wso+filesman),
[searching on pastebin](http://pastebin.com/search?q=WSO)
or running a [WordPress honey pot](http://stratigery.com/phparasites/).
Much of it is interpreted languages, like PHP or Perl.

I will use "Web Shell by oRb" (a.k.a "WSO", "FilesMan") and the omnipresent IRC Perl bot
(Perl/Shellbot.B) as examples.

"Web Shell by oRb" (also called "WSO", "FilesMan" and "AntiChat shell") is by far the most
popular web shell downloaded to hacked CMS web sites today. It's often reformatted, obfuscated
or otherwise slightly customized before hiding it in a WordPress installation.
Many distinct versions exist, including [one under active development](https://github.com/wso-shell/WSO).

The omnipresent IRC Perl bot is referred to by antivirus firms as
"Perl/Shellbot" or some form of that indicating a derivative. A typical variant
can be had from [Pastebin](http://pastebin.com/CJpxW5tx).  Perl/Shellbot is a piece
of Perl that understands the IRC protocol. Specially formatted messages from
the botherder cause the bot to do things, like perform a UDP packet flood, run
a command via the system's shell, or look up "dorks" in every search engine on
the planet. The code arrives in a dazzling number of variants, some with
function names and commentary in Portugese, others with function names & etc in
English. Every botherder seems to do minor customization.

Casual reading of several variants of either WSO or Perl/Shellbot will convince
you that the variants are "related". It seems that one variant "evolved" into another via a
process of spammers making small changes to suit their needs. Perhaps a selection of the
fittest happens when one script kiddy copys the succssful code of another script kiddy.
Collection and comparison of variants should allow the construction of a "family tree"
of variants. This project is a description and demonstration of one method of constructing
the family tree, or phylogeny, of WSO, and less succesfully, of Perl/Shellbot.

##Source code malware evolution

Ordinary biological evolution analogies are ill-suited to guessing
malware phylogenies.
Biological phylogenies assume binary splits between two clades, and 
assume that we know the sister clades, but can't identify the
the common ancestor.
Malware can split many times from an identifiable common ancester.
Biological phylogenies assume a single common ancestor.
Malware often, maybe almost always, has more than
a single ancestor.

Souce code malware seems to evolve by feature addition or subtraction.
Malware modifiers add small chunks of code, code that might phone home
with URL, user ID and password, or just evaluate some code when
executed with a special CGI-BIN parameter.
Sometimes entire functions or subsystems are transplanted from another
program.

When the "source code" (DNA) of biological families is available, it rarely
shows evolution by adding or subtracting entire "features". Biological evolution
appears to happen by gradual changes over large extents of a clade's DNA. 
The biological analogy of the way source code malware evolves would seem
to be [horizontal gene transfer](https://en.wikipedia.org/wiki/Horizontal_gene_transfer).

##Biology-influenced phylogenies

Traditional biology phylogenies are sometimes calculated with a "distance"
metric, and tree construction algorithms like
[Neighbor Joining](https://en.wikipedia.org/wiki/Neighbor_joining).

###Normalized Compression Distance

I used the NCD algorithm from [Common Pitfalls Using The Normalized Compression Distance](http://www.ims.cuhk.edu.hk/~cis/2005.4/01.pdf)
it seems to give closer-to-zero "distance" of a piece of code to itself. The code is in
`distance_calc.php`

    NCD(x,y) = max(C(xy) - C(x), C(yx) - C(y)}/max(C(x), C(y))

`NCD(x,y)` is the normalized compression distance from string `x` to string `y`,
`max(a, b)` is the numerical maximum of numbers `a` and `b`, and `C(e)` is the
size in bytes of compressed string `e`. `xy` is string `x` with string `y`
appended. I used PHP's `bzcompress()` function.

All files in `exemplars/` are PHP source code, normalized by [pretty
printing](https://github.com/nikic/PHP-Parser), and removing ASCII carriage
return characters. I did an NCD calculation on all PHP malware in `exemplars`.
Using the neighbor joining algorithm, I produced the following phylogeny.
To get a rooted tree from neighbor joining, you have to pick an "outgroup". I
chose `lfiscanner.php`.

![WSO phylogeny by NCD and neighbor joining](https://raw.githubusercontent.com/bediger4000/malware-phylogeny/master/nj_phylogeny.png)

The horizontal lengths of branches are proportional to the normalized
compression distance separating source files.

NCD and neighbor joining get some parts of the phylogeny correct. Although I
chose `lfiscanner` as the out group, it correctly found the `fx29` web shell as
the next most distantly-related piece of code. It gets the basic split between
WSO 2.4 and WSO 2.5 clades, but mixes version 2.8 and 3.1 in the 2.4-based
clade - version 2.8 is clearly a minor hack of version 2.5.1, differing only by
yet another phone home. Version 3.1 descends from 2.5 by the verbatim
incorporation of a local-file-include scanner from `lfiscanner.php`.

The assumptions inherent in neighbor joining make version 2.4 into an out group
of a clade, where it should be seen as the common ancestor of most of the
verions in the sister clade.  Version 2.4 should be seen as the ancestor of a
linear progression of 2.5 to 2.5.1 to 2.8. The entire issue of multiple
ancestry doesn't appear at all.  `fx29`
and `lfiscanner.php` should show up as auxilliary ancestors to multiple variants
that have a WSO variant as a primary ancestor.

All told, this phylogeny is roughly correct, but has too many flaws to be more than a general
guide.

##Algorithm

Because malware evolves by feature addition, and not by changes in genomes,
I tried to use the pieces of source code that differ between species, and
the pieces of source code that remain common between all members of a clade
to derive a phylogeny. I explictly allow for multiple ancestry.

###Determine Features

Naturally this is the important part, and not amenable to automation. The
algorithm needs at least one trait (line or lines of source code) common
between an ancestor and all of its desendants. It will calculate multiple
independent trees if this condition is not met.

The algorithm needs each pair of species to differ in at least one trait, 
and descendants must differ from ancestors by at least one trait.

###Description

Species are represented by data structures that can contain a set of features,
and allow each feature to be marked. Sets of features in two species must be
comparable to determine a subset relationship.  The data structure must be able
to keep a list of immediate descendant species. The data structure must be
capable of being marked to indicate that it has at least one ancestor.

1. Order species in a list by decreasing number of features.
2. Remove species with largest number of feature from ordered species list. This species becomes the current species.
3. Compare current species featuries to other specie's features in order.
4. When the other species has features that are a strict subset of current feature list,
   and contains a feature previously unmarked, assign current species as child of other species.
5. Mark all traits of the current species common to the new parent.
6. If more than one trait is unmarked, repeat from (3)
7. If no more than one trait is unmarked, go to one.
8. If you have compared traits of the current species to all species left,
   the current species hasn't been added to any species as a child,
   and still have more than one unmarked traits, add the current species
   to the set of root species.

###Performance

The algorithm above always terminates. Every species gets popped off ordered list of species,
and there's only a finite number of comparisons (traits or species) made.

####Worst case 
Consider a phylogenetic tree with one root, many children, and no
grandchildren, where all children have a number of common traits. Only one
trait differentiating between any two child species.  Worst case O(n^2) for
comparison of traits.

###Effect of ill-chosen features

Two species without at least one trait to differentiate them, show up as sister species.
Correctly chosing traits could cause one to show up as the child of the other.

{'fraction_non_alphanumeric': 0.05517324640830617, 'fraction_numerical': 0.00676083544609441, 'mean_word_length': 4.564998320456835, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 11, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '271216', 'n_tokens_mistral': 4630, 'n_tokens_neox': 4248, 'n_words': 2488}