I've changed my script into an open source project! I'd like to formally introduce lightbulb. Lightbulb is a utility to read in proxy log data and use entropy based analysis to determine beacons associated with malware. You can tailor it to do just about anything you'd like and it may provide network admins with a deeper understanding of their network and the activity happening around them.

For the first official release of lightbulb I wanted to make some significant improvements to the code and the reporting. There are more changes to come, but what you'll find new in this version is.

• Reporting back of the actual beacon time intervals
• Outliers listed according to the standard deviation of all data

It's a nice improvement and it's coming a long way. The next version has a scheduled change in the backbone to boost performance. As well as taking a look at different learning algorithms. Stay tuned for more changes. All updates on the project will now be hosted at google code as well as on here. I'll try to keep the changelog up to date. :)

http://code.google.com/p/lightbulb

In my last post, I gave sample code to locate a hard-coded beacon using proxy logs as a source of information. I found some results on the small scale, but nothing that blew me away. To be honest, the results were spotty at best.

Well, it's been a while (just about 60 days) since I was last down that route. I've been working on a better way to determine anomalous behavior. I found a couple dead ends and a couple of promising avenues.

Let's start off with a couple of ideas.
1. Human behavior on the Internet is unpredictable at best.
2. Machine behavior is typically not.
3. If randomness is added in, it's typically a 'true' random distribution.
4. Humans are bad at generating random numbers.

Alright, so the starting with the shortcomings of the last script.
1. It couldn't detect beacons with random time signatures.
2. Only compared other values with the first beacon in the list.
3. The tolerance was letting a lot of false positives through the door.
4. Took FOREVER to run.

Using entropy to look for anomalous behavior is not a new idea. In fact, Shannon's entropy method was introduced in 1948. Some of the first novel uses involved using it to detect cipher text and different encryption algorithms. In fact there are tons of applications across all the sciences.

So what does it do? Roughly speaking, it'll tell you how predictable a set of data is. If your set of data consisted of just one number, it's entropy would be zero. However, if it was completely random it's entropy would be greater than 0 (depending on the size of the set). Let's take a look at the mathematics of it, and then how to implement it.

First off, here's what it looks like:



Let's use this against a data set. [50,50,50,50,50,50....50]

First we need to calculate the probability mass function for all values in the list. For this example it's trivial. 50 appears for every entry so the probability that 50 will occur is 1/1.
We then take this and compute
-[(1/1)*(Log(1)/Log(2))] (The reason for dividing by Log(2) is the change of base formula when you're using Log base 10. Algebra - FTW)
This equals 0. That tells us how 'random' our list is. For this example, it's easy to see that it's not very random at all.

So let's take a more 'random' entry: [30,40,30,40,30,40,30,40,30,40.....]
We'll put it to the test by plugging it into our formula.

30 and 40 are the only 2 numbers that appear so the probability that each on happens is 1/2.

- [(1/2)*(Log(1/2)/Log(2)) + (1/2)*(Log(1/2)/Log(2))] = 1

So this is a little more interesting......

One more, just entertain me: [15,65,8,7,99,35,200,3201,5,5]

This last one looks pretty random to me. Let's see what the Shannon's entropy has to say about this. First let's set up our pmf.

15 = 1/10
65 = 1/10
8 = 1/10
7 = 1/10
99 = 1/10
35 = 1/10
200 = 1/10
3201 = 1/10
5 = 1/5

Putting this into Shannon's formula looks a little like this
- [(1/10)*(Log(1/10)/Log(2))*8 + (1/5)*(Log(1/5)/Log(2))] = 3.12193

At this point it should be evident that the more random the number list is, the higher the level of entropy.

So how does this tie into finding beacons or automated behavior?
Building on the last entry and not being so rigid with our time entry items, this can give us a good idea of the behavior of the user hitting a particular site. Essentially, this will break down into a couple steps.
First, Build a hash of arrays of all IPs and every site that they've talked to:
{192.168.1.100 : evil.com} => [12:05:00, 12:10:00, 12:15:00, 12:20:00...]

Then take the time differences (in seconds)
{192.168.1.100 : evil.com} => [300,300,300,300....]

Next, calculate the entropy for each array and store
{192.168.1.100 : evil.com} => 0

...and that's all! Sort our lists and report on our findings!

Seems easy enough right? There are still some shortcomings of this method though. Let's discuss.

Network latency - Slowness in the network can mess with the beacon times and make them appear not to be perfect. The hope is that they will be "close enough" for enough common values to lower the entropy. Another way around this is to build in a tolerance to allow for a small amount of flexibility. As I found out in the last entry though, the tolerance will allow for a lot of false positives to come through the door.

Flagging regular user activity - It may not be uncommon for a user to click a link on a site every second. To a script, this looks like 'predictable' behavior. A way to avoid this problem is set a minimum tolerance for the beacon interval, this may allow for less false positives, but it will cut down a significant amount. The idea is that the user will visit the site more later on in a less predictable fashion and result in a higher entropy.

What about the results?
Simply put, it works. I've used this to locate beacons or just to better understand the network that I work in.

For now, the reporting capabilities are somewhat weak and could go for a little improvement. More on that later. One idea is to look at things like the standard deviation of the list and only list the outliers, flagging the rest as regular traffic. I guess that only time and testing will tell.

The script that I'm attaching is written in ruby for ease of reading. My future plans are to rewrite this in something faster like OCAML or even go as low as C or C++. Speed and memory are difficult to manage when you're dealing with terabytes of information, regardless of what language you're writing in. In these sorts of scenarios though, any small difference may go a long way. The results have uncovered a lot of quirks in the network, and have already allowed me to profile some machines. It also gives the ability to break up their activity based on user generated vs machine generated traffic, which to an incident responder, is huge.

Until next time.

Searching for beacons in network traffic is not a trivial problem to solve. In fact, network anomalies in general are getting harder and harder to detect. The days of just looking for a 'spike' are long gone.

Before I get started, I wanted to apoligize for messy code segments, Blogger isn't the best engine in the world for posting well formatted code.

What I've been digging into recently is ways of detecting beacons. Visualization tools may aid this however it would take some specific knowledge of what to look for before any real patterns are going to make sense.

So first off, what's the classic way of detecting a beacon?
Search for a spike every x minutes?
Grep for traffic to a particular host and then look for the difference in time stamps?

While those may work, these ideas are assuming that you know the external site that software is beaconing to. What if you don't know exactly what is talking on your network and which external sites are getting hit? Searching through these by hand are simply not an option. That is unless you've managed to hire hoards of monkeys.... I wouldn't count that option out yet.

If you're any good company I'd assume that you have all your web traffic tunneled through proxies and EVERYTHING is logged. I can't stress that last part enough.

Let's take a look at our ingredients:

• Ruby for this example (any scripting language will do, PERL, Python, or you can amaze us all and write in C)
• Proxy Logs
• A fast processor
• A ton of RAM

As a side note, I usually try to keep my scripts pretty lightweight and low on the I/O. I found that when dealing with huge log files, unless I'm creating temp files, this is hard to do. Creating temp files would also violate my second rule.

How does this work?
Well, let's think of this script as elegant as a brute forcer in cryptography. It gets the job done, but it's going to cost in terms of time and memory consumed.

The way that it works is by taking in all IPs and the sites that they've visited and dumping those into a hash.
Secondly, we take all the times that each particular site was hit and keep track. For easy time calculation, I'm using the ruby time class.
What we're looking for is the frequency at which these sites have been visited. So we're not really concerned with everything that occurred at any single visit. So we take all the times and compute the differences.
Then we begin computing. Crunch crunch crunch. For this one, feel free to go on your lunch break and await results when you get back.
Once all that is over, we'll add in a threshold and a confidence level. Due to network, quirks, latency or just a bad setup it's not uncommon for a beacon to fail or to be running a little late so we need to account for these things. One thing to keep in mind, however is that when a threshold goes up, our confidence should go down.
Then we see how closely these distances match a particular pattern and then report back our findings.

This will solve the general beacon problem. However there are other ways around this. Malware writers may add some randomness to their beacons or even have the interval long enough where it's not talking multiple times a day. Trying to track down a beacon that only talked once a week or month would probably be near impossible. That's comforting. :)

So let's take a look at the source... (and don't be too harsh on the code, this is alpha quality)

Read the logfile in from STDIN and put it into a hash with corresponding URL values. I'll need to keep some of the code generic. Since there are a billion different log formats and some may not match the type I've tailored to.


data = Hash.new
print "Reading Log File"
while(line = STDIN.gets)
temp = line.split(" ")
#make sure the line isn't a comment or a header
if temp[0].scan("#").length.eql?(1)
next
end
#declare all values
begin
key = URL.to_s + " : " + IP.to_s
time = Time.local(year, month, day, hour, min, sec)
if data.has_key?(key)
data[key].push(time)
else
data[key] = Array.new.push(time)
end
rescue Exception => e
next
end
end
print "...done!\n"

We've got our main data structure established here. It's a large hash of arrays, something in the form of this:
google.com : 192.168.0.2 => time1, time2, time3, etc ….
yahoo.com : 192.168.0.2 => time1, time2, time3, etc …
google.com : 192.168.0.1 => time1, time2, time3, etc …

Now for the second part, we'll compute the differences in the times and store those in a hash similar to our first one.

difference = Hash.new
print "Computing Differences"
data.each_key do |key|
index = 0
begin
difference[key] = Array.new
while(index <> diff = (data[key] [index+1].to_f - data[key] [index].to_f).abs.to_f
#check below for explaination
if diff <> else
difference[key].push(diff.to_f)
end
index += 1
end
rescue Exception => e
next
end
end
print "...done!"

*The reason for this is when multiple requests are made for images, scripts, etc all in relation to the same site it will have a lot of redundant information that'll lead to false positives. We need to make sure that a change has occurred rather than just a single request. The 5 can be tweaked as necessary depending on the logs.

Now we set our tolerances and run. For this example, my tolerance is 50 and can be set depending on how loose you'd like to be.


tolerance = 0
while tolerance < report =" Hash.new" num =" difference[key].first" lower =" num" upper =" num"> 15
#number of beacons you'd expect
puts tolerance.to_s + " - " + key.to_s
end
difference.delete(key)
end
tolerance += 10
end


That's all there is to it! The number of beacons can be changed, but obviously the more verbose something is, the easier it is to catch. The lower you set this number and the higher that you set your tolerances can greatly change the outcome and confidence of this script.

The fun part: Let's see if it works.....

Now let's run it on a big logfile to get an idea of what to expect.

On a logfile that is 82.1 Megs and 273653 lines long, it took:
real 0m49.325s
user 0m46.591s
sys 0m2.416s

Which isn't miserable, but let's start looking at some bigger data sets. On a file that is 3.6 Gigs and 11726177 lines long.
real 158m53.342s
user 155m54.865s
sys 2m10.196s

...ouch. Given I don't own a horribly fast computer and my amount of RAM is less than stellar.

More importantly, did we get any results?
0 – 192.168.0.12 : updates.installshield.com
0 – 192.168.0.229 : update.intervideo.com
0 – 192.168.0.76 : updates.installshield.com
0 – 192.168.0.165 : yahoowidget.weather.com
…..
(There were a little over a 200 results which I didn't paste in to save space)

I don't know about you, but looking for beacons on the network is a lot easier when there is only ~200 results (for a 3.6G logfile) instead of 11726177!

The first number is our tolerance (the lower the better) and then IP followed by site that the IP is beaconing to. In this case there isn't any surprise, there's computers on the network beaconing for updates.

That's all I've got. If there are any changes or modifications that can/should be done to the code, please let me know and I'll keep updating this script accordingly. I'll also be happy to make changes if you flat out think that it's wrong :) Hopefully it can shrink down in size and increase in efficiency through the more eyes that see it.

Until next time.