9

I've collected a large number of "Web Shell by oRb" (a.k.a. "FilesMan" backdoor, a.k.a. antichat backdoor) files by running a WordPress honeypot, and searching pastebin. The code in the variants is obviously related. I'd like to figure out a "phylogeny" of WSO variants. I found D. Gusfield, Efficient algorithms for inferring evolutionary trees, which has a clearer explanation of the phylogeny generating algorithm in Caroline Uhler's Finding a Perfect Phylogeny.

Unfortunately, the folks who created some of the WSO variants borrowed code from other variants, so a "perfect" phylogeny doesn't exist - some variants have two or more immediate ancestors due to the malware writer equivalent of "horizontal gene transfer" as practiced by real life bacteria. The only thing I've been able to find about phylogenies that are directed acyclic graphs, is Constructing Computer Virus Phylogenies. The problem with that paper is that it doesn't seem to actually show you an algorithm - either no algorithm is present, or it's buried in the assorted lemmas, theorems, definitions and proofs.

Are there other papers that actually display an algorithm or pseudocode for an algorithm that can generate "phyloDAGs"? I'd settle for an implementation in a major programming language, even.

  • 5
    When you write it, please come back here and answer your own question with a link to your code! – JaimeCastells Nov 13 '15 at 23:07
  • 1
    Have you tried to use Levenshtein distance (example on StackOverflow) or something similar? – A.L Nov 18 '15 at 23:11
  • @A.L - I've used Normalized Compression Distance, and Neighbor Joinging to find phylogenies. Unfortunately, due to code chunks appearing in multiple versions, WSO doesn't have a perfect phylogeny. The biological assumptions of a single common ancestor don't hold, so if you look at actual code, Neighbor Joining based on NCD gives a false phylogeny. – Bruce Ediger Nov 18 '15 at 23:15
3

Yes. You are looking for Ancestral Recombination Graph (ARG) algorithms. ARGs are the natural extension of phylogenies (trees) to DAGs. ARG algorithms tend to be exponential algorithms, while phylogeny algorithms are polynomial. This means that the dag problem appears to be significantly more difficult than the tree problem.

Please see the book:

D. Gusfield. Recombinatorics. MIT Press. 2014.

https://mitpress.mit.edu/books/recombinatorics

  • 1
    I'd love to know if these algorithms work for you. Please post if you get any results. – Brent Kirkpatrick Mar 14 '16 at 12:06
  • -I certainly will do that. – Bruce Ediger Mar 14 '16 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.