A Python example on finding connected components in a graph

Today I’ve been coding a solution for a problem we’ve encountered with @ggdaniel (cr0hn) during the development of GoLismero 2.0. It called for an implementation of an algorithm to find connected components in an undirected graph. You can find the source code at the bottom of this post.

A graph algorithm a day keeps the CS doctor away…

Suppose we have an undirected graph (connected by lines rather than arrows) in which we can find one or more “islands” of nodes that form connections to each other, but not to nodes in other “islands”. In graph theory, these “islands” are called connected components. In the image below, we see a graph with three connected components:

Now, suppose we have a set containing all nodes, and we can visit each node to know what are its neighbors, that is, the other nodes it’s connected to. We want to find all the connected components and put their nodes into separate sets. How would we do that?

An example dependency resolution algorithm in Python

I’ve been toying with dependency resolution a bit today, since it’s one of the features we plan to add to GoLismero 2.0 plugins with @ggdaniel (cr0hn). So I came up with this short example that’s reasonably fast and doesn’t use recursion at all, unlike many of the examples that I found on the net.

The basic idea is this: given a set of tasks (nodes) and the tasks that need to be performed before them, build a dependency graph and find the sets of tasks that can be run concurrently while satisfying the dependencies. For example, suppose we have tasks A, B, C and D. Task A can be run directly, it has no dependencies. Tasks B and C must be run only after A has completed, so we say B and C depend on A. Then task D depends on B and C, which in turn depend on A.

Dependency graph example

What the algorithm does, instead of traversing the graph recursively, is iteratively finding and removing from the graph all nodes that have no dependencies – that is, no arrows coming out of them. In our example, the first iteration removes node A, the second iteration removes nodes B and C, and the last iteration removes node D. And these are precisely the three batches of tasks that can run concurrently – first task A runs, on completion tasks B and C can run in parallel, and once both are finished task D can be started.

If at some point there are still nodes in the graph but we can’t find any nodes without dependencies, that means we have a circular dependency.

Circular dependency graph example

Quickpost: Cheating on XKCD

In case you missed it, today’s XKCD comic titled Click and Drag is simply amazing! Go check it out first, spend a few hours lost in it, and come back only when you’re done having fun. I’ll wait here.

…

Ok, you’re back. Naturally you’ll want to cheat on it at some point, to make sure you didn’t miss out on any hidden easter eggs! So let’s take a look at the web page.

The easiest route is loading the comic on Google Chrome, or Chromium. Just right click on the image and select “inspect element”. This quickly reveals how the neat trick works.

Taking a peek under the hood…

The “world” is divided into tiles of fixed size, and at all times the page loads the tile you’re currently viewing and the surrounding ones, in order to seamlessly stitch them together when scrolling. The clickable area is a map and the coordinates are used to build the URL to the images, which always follows the same pattern (north, south, and east and west coordinates). Trying out a few numbers reveals the “north” coordinate goes from 1 to 5, the “east” coordinate goes from 1 to 48 and the “west” coordinate goes from 1 to 33. Not all coordinates seem to work around the edges of the world (north 2 west 5 doesn’t work for example) and I couldn’t get south to work with manual tries. I suppose a couple empty images are used for those (one for black and one for white) but I didn’t confirm it.

The first thing I tried was just accesing the parent directory to see if directory indexing was enabled, but no such luck. Instead, I wrote this quick and dirty script in Python to download all images, using urllib to download them and shutil to write them to disk. Missing tiles are simply skipped.

This should be enough to check for easter eggs, but it’d be interesting of someone assembles a big image containing all the tiles. Let me know if you do!

Update 1: I originally missed the east coordinate, so the script was updated to try and bruteforce in all directions 1 to 10 north and south, and 1 to 50 east and west. This means a lot more HTTP requests, so I also added a pause between them as good netizens should.

Update 2: This seems to be the complete list of valid image URLs.

Update 3: A commenter pointed out somebody did assemble the entire world image! Check it out here.

Update 4: @prigazzi on Twitter pointed out this fully navegable map as well, based on Google Maps. Check it out! It’s IMHO the best one yet.

Update 5: The previous link no longer works, but this works pretty much the same way: xkcd-map.rent-a-geek.de

[Quickpost] Updated Impacket/Pcapy installers for Python 2.5, 2.6 & 2.7

Hi folks! In a previous post I talked about using Impacket and Pcapy on Python 2.6. Since those installers are now out of date, here are fresh ones for various versions of Pcapy and Python, built against WinPcap 4.1.2. There’s also a new Impacket MSI installer that works against all Python versions.

Enjoy!

Edited 6-May-2013: updated Impacket to version 0.9.10

Download Impacket 0.9.10

impacket-0.9.10.win32.msi

impacket-0.9.10.win-amd64.msi

Download Pcapy 0.10.5

pcapy-0.10.5.win32-py2.5-winpcap4.1.2.msi

pcapy-0.10.5.win32-py2.6-winpcap4.1.2.exe

pcapy-0.10.5.win32-py2.7-winpcap4.1.2.exe

pcapy-0.10.5.win-amd64-py2.6-winpcap4.1.2.exe

pcapy-0.10.5.win-amd64-py2.7-winpcap4.1.2.exe

Hackito Ergo Sum 2012

Hi everyone. Last week I’ve attended Hackito Ergo Sum 2012, and I wanted to share with you some of the things that I found most interesting during the talks. This won’t be a detailed review of each talk, but rather an account of a few details on the talks that I personally found more interesting, in no particular order. If you’re looking for a detailed review of each talk check out this blog.

Oh, by the way. I totally made up the names of the talks. I think it’s more fun that way.

The event took place at the headquarters of the French Communist Party, and I have to say the conference room was quite impressive. It was an underground dome all covered with white metallic plates and lamps behind, giving a peculiar visual effect.

An additional advantage of this place is that some security agencies can’t send their spooks there. Hurray to the ridiculously outdated cold war laws!

One thing I didn’t like though, was that the slides were projected in a sort of tilted curved screen, making it a bit difficult to read the slides unless you were sitting in the middle. I don’t think I was the only one with this problem because I saw a lot of heads tilted sideways…

Quickpost: Installers for BeaEnginePython, Pymsasid, PyDasm and Libdisassemble

I’ve packaged the BeaEngine Disassembler along with its Python bindings into a no-frills Windows installer. Certainly easier than manual install, and it really helps me when installing it on virtual machines.

Enjoy!

Update: Just added another disassembler package, Pymsasid.

Update: Added precompiled Windows binaries for PyDasm on Python 2.6 and 2.7.

Update: My installers were added to the Python Arsenal for RE.

Update: The Pymsasid package was updated with a small change, so the importation works just the same as loading the .py files from the current directory (it’s just an “import *” in __init__.py)

Update: Added a simple setup script for Libdisassemble 2.0. Since I had to put the sources inside a package the import statement in your scripts will have to be adjusted if using this version. With a simple try/except block you can make scripts compatible with both versions as well, if you need to.

Downloads

BeaEngine win32 installer: BeaEnginePython-3.1.0.win32.exe

BeaEngine win64 installer: BeaEnginePython-3.1.0.win-amd64.exe

BeaEngine source installer: BeaEnginePython-3.1.0.zip (run “python setup.py install”)

Libdisassemble 2.0 win32 installer: libdisassemble-2.0.win32.msi

Libdisassemble 2.0 win64 installer: libdisassemble-2.0.win-amd64.msi

Libdisassemble 2.0 source installer: libdisassemble-2.0.zip (run “python setup.py install”)

PyDasm precompiled binaries: PyDasm-1.5-precompiled.zip (run “python setup.py install”)

Pymsasid source installer: pymsasid-0.3.1.zip (run “python setup.py install”)

Heappie! + WinAppDbg

In case you missed it, Aníbal Sacco released a new tool called Heappie! to analyze heap sprays in multiple platforms. It uses PyGame and PythonCard for the GUI and Kenshoto’s VTrace as the backend. It’s really cool, check it out

Now, I never get tired of saying how great VTrace is. It’s written in Python, supports multiple platforms and quite comfortable to develop with. But alas, I tend to prefer my own debugger (call me biased if you wish!). So today I went ahead and added WinAppDbg support to Heappie!. When WinAppDbg is installed, it’s chosen automatically as the backend. If not found, it falls back to VTrace. That way we don’t lose support for other platforms, since WinAppDbg naturally only works on Windows.

This patch also adds support for 64 bit versions of Windows, in case you were thinking this was just an exercise in self indulgence. Well, it is that, but not just that. Ahem.

TL;DR

Just download the file above, go to Aníbal’s blog to learn how to use it, and exploit all the bugs!

Download

Heappie-WinAppDbg.zip

Posting anonymously to Pastebin.com

While going through some old code of mine to document it using Epydoc at a friend’s request, I found something funny. Some time ago I made a quick and dirty script to access the Pastebin.com API from Python. Well, it turns out the API has changed quite a bit since then – most importantly, now it requires a mandatory API key that’s linked to a user account (which in turn, if you used OAuth, is linked to your Gmail address or Twitter feed). That means it’s no longer possible to post anonymously using the official API.

Funny thing is, my old script was still working! Apparently the folks at Pastebin have left the legacy API still running. The old documentation is gone though, and now even to read the updated documentation you need to log in…

Now, this takes care of the API key problem, but there’s still the issue of Pastebin seeing your IP address. An HTTP proxy can fix that… provided you trust that proxy not to store your IP somewhere in the logs. The procedure is simple, just set the HTTP_PROXY environment variable to wherever your proxy is, and voilà! The standard Python module urllib will automatically connect through the proxy.

If you don’t have a trusty HTTP proxy, the best way to go is through the Tor network. You’ll need to install the Tor service itself and the Privoxy HTTP proxy in your machine, then set the HTTP_PROXY variable to 127.0.0.1:8123. This document from the Tor Project explains it in detail.

Once you’ve set up your proxy, download pastebin.py and send a file to Pastebin like this:

    $ python pastebin.py manifesto.txt
    manifesto.txt --> http://pastebin.com/ixSetT5f

The script accepts multiple filenames as well. You can also set the syntax highlighting format (useful for source code, config files or logs) as follows:

    python pastebin.py --format=apache /var/log/apache2/access.log /var/log/apache2/error.log

And set an expiration time, after which it gets automatically deleted. In the following example a SQL dump is uploaded and automatically deleted the next day:

    python pastebin.py dump.sql --format=sql --expire=1D

So, that’s pretty much it. There’s a limit of 512Kb per file uploaded, in order to bypass this you’ll have to split the file into multiple pieces (something similar to this but using pastes instead of URLs). I may do it another day, but for now it’s left as an exercise to the reader.

There’s one thing I don’t quite understand: why did the Pastebin folks think it was necessary to have a mandatory API key? Even if the legacy API had been shut down, it would still be possible to figure out how the web page was doing it and replicate it in Python. The API key being linked to the user account seems a bit strange too… Their intention might be to catch script kiddies uploading illegal stuff, but it may also be an attempt to do data mining on people’s posts. Who knows…

Download

pastebin.py

Quickpost: “Hiding” your Python source with ROT13

First of all I want to make something clear: this is an absolutely lame way to obfuscate your code. I guess some antivirus, IDS or other kind of security scanner may fail to properly analyze the code if it’s encoded like this, but you can’t really fool a human.

Anyway, it was fun and that’s my main motivation to write this blog in the first place, soooo… here it is! A Python source code obfuscator that uses ROT13.

How does it work? Simply put, by misusing the Python source encodings feature. I stumbled upon this idea while reading a thread in Stack Overflow. Python allows us to use any supported form of text encoding for our source code, by placing a magic comment in either the first or second line of the script:

    #!/usr/bin/env python
    # -*- coding: <codec-name-goes-here> -*-

This is useful for example to use UTF-8 and other encodings that allow non-english characters. But Python also has some other fun encodings, like ROT13 (the ancient Roman empire encryption system). The following snippet from Stack Overflow shows how to do it:

    #!/usr/bin/env python
    # -*- coding: rot13 -*-

    cevag "Uryyb fgnpxbiresybj!".rapbqr("rot13")

The only caveat is, ASCII strings are not decoded when you run the script, so you have to do it yourself. Unicode strings on the other hand are decoded automatically.

    #!/usr/bin/env python
    # -*- coding: rot13 -*-

    cevag h"Uryyb fgnpxbiresybj!"

There are some other fun encodings like “base64″, “uuencode”, “zlib” or “bz2″ that you can experiment with too. If you try them let me know how it went.

I wrote a quick script to use the ROT13 trick. Naturally the source code itself is also encoded in ROT13, decoding it is left as an exercise for the reader. Enjoy!

Download

Source code: rot13src.py

Quickpost: Using Google Search from your Python code

Hi everyone. Today I’ll be showing you a quick script I wrote to make Google searches from Python. There are previous projects doing the same thing -actually, doing it better-, namely Googolplex by Sebastian Wain and xgoogle by Peteris Krumins, but unfortunately they’re no longer working. Maybe the lack of complexity of this script will keep it working a little longer…

The interface is extremely simple, the module exports only one function called search().

        # Get the first 20 hits for: "Breaking Code" WordPress blog
        from google import search
        for url in search('"Breaking Code" WordPress blog', stop=20):
            print(url)

You can control which one of the Google Search pages to use, which language to search in, how many results per page, which page to start searching from and when to stop, and how long to wait between queries – however the only mandatory argument is the query string, everything else has a default value.

        # Get the first 20 hits for "Mariposa botnet" in Google Spain
        from google import search
        for url in search('Mariposa botnet', tld='es', lang='es', stop=20):
            print(url)

A word of caution, though: if you wait too little between requests or make too many of them, Google may block your IP for a while. This is especially annoying when you’re behind a corporate proxy – I won’t be made responsible when your coworkers suddenly develop an urge to kill you!

Below are the download links (source code and Windows installers) and the source code for you to read online. Enjoy!

Changelog

• Version 1.0 (initial release).

• Version 1.01 (fixed the IOError exception bug).

• Version 1.02 (fixed the missing href bug reported by Rahul Sasi and the duplicate results bug reported by Slawek).

• Version 1.03 (extracts the hidden links from the results page, thanks ubershmekel!).

• Version 1.04 (added support for BeautifulSoup 4, thanks alxndr!).

• Version 1.05 (added compatibility with Python 3.x, better command line parser, and also added some improvements by machalekj)

Download

Source code: google-1.05.zip

Windows 32 bits installer: google-1.05.win32.msi

Windows 64 bits installer: google-1.05.win-amd64.msi

Documentation: google-1.05-doc.zip

Source code

Get the source code from GitHub: https://github.com/MarioVilas/google