Thursday, February 10, 2011

Java Pushy API

It's been some time since I've spruiked Pushy, so here we go. One of my colleagues was talking the other day about how he had implemented a netcat-like service for STAF, an automation framework aimed at testing. This got me thinking about how this could be done relatively easily, using the pushy.net package, something I haven't written about much, primarily because it's still a work in progress.

Back in version 0.3, I introduced a Java API to Pushy, as I mentioned in an earlier post. I briefly mentioned the incorporation of packages which mimic, and in many cases are interface compatible with, packages in the Java standard library such as java.io and java.net.

The pushy.net package currently contains three main classes:
  • RemoteInetSocketAddress (extends java.net.InetSocketAddress)
  • RemoteSocket (extends java.net.Socket), and
  • RemoteServerSocket (extends java.net.ServerSocket).
RemoteInetSocketAddress simply provides a means of creating an InetSocketAddress whose address is resolved at the remote host. RemoteSocket is a wrapper around a remote Python socket object, but extends java.net.Socket to provide a familiar interface to Java developers. Similarly, RemoteServerSocket extends java.net.ServerSocket, and wraps a remote Python socket object.

So how about netcat emulation? Well, I won't cover the whole implementation of a netcat clone, as that would be a non-trivial undertaking. But I will show you one of the fundamental requirements: to bind a server socket, accept a client connection, and print out the data received from that client.

Step 1. Bind a socket, and listen for connections.

import java.net.ServerSocket;
import java.net.Socket;
import pushy.Client;

public class Test {
    public static void main(String[] args) throws Exception {
        Client conn = new Client("local:");
        try {
            ServerSocket server = new pushy.net.RemoteServerSocket(conn, 0);
            try {
            } finally {
                server.close();
            }
        } finally {
            conn.close();
        }
    }
}

In this code snippet, we're creating a RemoteServerSocket, and assigning it to a java.net.ServerSocket, to illustrate interface compatibility. The first argument to the constructor is the pushy.Client object we previously created, and the second argument is the port to bind to. Specifying a port of zero, means that we want to bind to an ephemeral port.

The creation of the RemoteServerSocket involves creating a Python socket object on the remote host, and performing the bind and listen methods on it.

Step 2. Accept a client connection.

Socket client = server.accept();
try {
} finally {
    client.close();
}

Here we can see that accepting a client connection is exactly as we would do with a standard java.net.ServerSocket. This probably isn't surprising, since we've upcasted our RemoteServerSocket to a plain old ServerSocket. One thing of interest here is that the Server object returned is in fact a RemoteServerSocket, wrapping a remote Python socket object.

Step 3. Read data from the client connection.

InputStream in = client.getInputStream();
byte[] buf = new byte[1024];
int nread = in.read(buf, 0, buf.length);
while (nread != -1) {
    System.out.write(buf, 0, nread);
    System.out.flush();
    nread = in.read(buf, 0, buf.length);
}

Et voila! We can read the remote socket's output via a java.io.InputStream object, returned by the getInputStream method, which is overridden by RemoteSocket. One thing you may have noticed: to run this all on the local host, sans Pushy, you could substitute the right-hand side of the initial ServerSocket construction with a standard ServerSocket, and the rest of the code would remain unchanged.

There are a few defects in the 0.3 release related to the pushy.net package, which will prevent these examples from working. I have rectified them in the process of writing this post. If you grab the trunk, it should all work nicely. There is one defect remaining: the InputStream returned by RemoteSocket is based on a a file returned by Python's socket.makefile method. This differs from the InputStream returned by Java's standard Socket, in that a request for N bytes will not return until all N bytes, or EOF, are received. I hope to have this fixed in the coming days.

Sunday, February 6, 2011

Facebook Puzzles

So a couple of weeks ago I came across a forum post on XKCD about programming puzzles.Figuring that's a significantly better way to while away the hours I'd previously been spending playing computer games, I thought I'd take a crack.

So after browsing around, I came across Facebook Puzzles, which seems to be part of Facebook's recruitment tools. Solve some puzzles, apply for a job, and say how rad you are for having solved all of their puzzles. Something like that. Anyway, I had no intention of applying to Facebook, I just wanted to revive my fading computer science knowledge, and have a bit of fun in the progress. I don't see what the big fuss is about working there; so many other companies are producing much more interesting, constructive things.

Naturally I went straight to the most difficult puzzle on the list, Facebull. It didn't take long for me to realise this was an NP-hard problem. It's fairly straight forward to see that this is a graph problem. A little more formally, we're given a directed graph (digraph), and we're asked to find a minimum cost strongly-connected sub-digraph, containing all vertices, but a subset of the edges.

Spoilers ahead. Turn back now if you don't want any help.

Originally I had thought that it was the Asymmetric Traveling Salesman Problem (ATSP) in disguise, which is just the Traveling Salesman Problem (TSP) with directed edges. I spent a couple of hours here and there reading the literature, since I didn't know anything about exact solutions (which is what the puzzle requires), and was only vaguely aware of approximation algorithms (which might help, for example, to reduce the search space.) For anyone wanting to read up on the TSP problem, I would definitely recommend the survey paper The Traveling Salesman Problem, by Jünger, Reinelt and Rinaldi. Also, this website provides a great, gentle introduction.

Not too long after, it dawned on me that the problem was not ATSP at all, since vertices ("compounds") might be visited more than once. For example, consider a graph with the following edges:
    (C1, C2), (C2, C1)
    (C1, C3), (C3, C1)
This could not be solved by the ATSP, since we would have to visit C1 twice to complete a cycle from C1 to C2 to C3 and back to C1. However, it is required to be solvable for the Facebull puzzle. Back to the drawing board...

The general approach I took was similar to the one that would be taken for ATSP, though, and that is to use a "Branch and Bound" algorithm. This is a fancy way of saying, enumerate all possible solutions, backtracking at the earliest possible opportunity by computing lower and upper bounds. For example, we might start with an upper bound of infinity, and update it whenever we find a candidate solution with a lower cost than the upper bound. A lower bound can be computed by taking into a constraint: each vertex must have an in-degree of at least one, and an out-degree of at least one. By remembering the cost of each edge in the graph, we can easily compute a lower bound.

Is this enough? Perhaps, but we can do better. One more thing we can do is to prune edges. For example, if we have the edges (Ci, Cj), (Ci, Ck), and (Ck, Cj), and the sum of the cost of the latter two is less than the cost of the first, then we can eliminate the first.

In total, I submitted my solution nine times. Why so many, you might ask? Because I didn't parse the input correctly, and didn't realise this while I was banging my head against the problem for two weeks. I wasn't handling white space at the end of the file, and I (foolishly) assumed that the test cases would not assign multiple edges to the same pair of vertices. Why would you have such a trivial test case to trip people up, when the underlying puzzle is hard enough as it is? It turns out my accepted solution (written in C++) ran in 300ms, so I guess the focus was more or less centred on correctness, rather than speed. That was a little frustrating, but at least I had some fun and learnt a few tricks along the way.

There is still something wrong with my solution, however. It is not finding the optimal solution to some of the test cases people have published. But it passed the puzzle robot, so that's the main thing that matters. I had one more optimisation, which was to identify edges which are absolutely required, up-front. This can be done very cheaply, and may significantly reduce the search space in sparse graphs. This optimisation was interacting badly with my enumeration function, though; I'm not sure what the problem is, perhaps I'll go back and take another look some time.

Now, back to wasting my time playing computer games...

Saturday, August 7, 2010

Pushy Public Documentation

So, I finally got around to writing some proper documentation for Pushy.

I had originally used Epydoc to extract docstrings, and generate API documents, which I have been hosting. Then I realised I could publish HTML to PyPI, so I thought I'd do something a little more friendly than presenting the gory details of the API.

In the past I've used Asciidoc, a lightweight markup language, in the vein of Wiki markup languages. I found Asciidoc fairly simply to write, and there is a standard tool for processing and producing various output, including of course HTML. I wanted to make my documentation to have the look and feel of the Python standard library, so I've been looking into reStructuredText.

I have to say that reStructuredText is very easy to learn, and Sphinx, which is the processing tool used to generate the HTML output for the Python documentation, is a pleasure to use. The format of reStructuredText is similar to that of Asciidoc. So far I don't have any particular affinity to either - I mainly went with reStructuredText/Sphinx for the Python documentation theming.

Saturday, July 10, 2010

Java-to-Python

Did you ever want to call Python code from Java?

Until Java 5, I wasn't much of a fan of the Java language. The addition of enums, generics, and some syntactic sugar (e.g. foreach) makes it more bearable to develop in. But all of this doesn't change the fact that Java purposely hides non-portable operating system functions, such as signal handling and Windows registry access. Sure, you can do these things with JNI, but that makes application deployment significantly more complex.

Python, on the other hand, embraces the differences between operating systems. Certainly where it makes sense, platform-independent interfaces are provided - just like Java, and every other modern language. But just because one platform doesn't deal in signals shouldn't mean that we can't use signals on Linux/UNIX.

I realise it's probably not the most common thing to do, but calling Python code from Java needn't be difficult. There's Jython, which makes available a large portion of the Python standard library, but still has some way to go. Some modules are missing (e.g. _winreg, ctypes), and others are incomplete or buggy. That's not to say that the project isn't useful, it's just not 100% there yet.

Enter Pushy (version 0.3). In version 0.3, a Java API was added to Pushy, making it possible to connect to a Python interpreter from a Java program, and access objects and invoke functions therein. So, for example, you now have the ctypes module available to your Java program, meaning you can load shared objects / DLLs and call arbitrary functions from them. See below for a code sample.

import pushy.Client;
import pushy.Module;
import pushy.PushyObject;

public class TestCtypes {
    public static void main(String[] args) throws Exception {
        Client client = new Client("local:");
        try {
            // Import the "ctypes" Python module, and get a reference to the
            // GetCurrentProcessId function in kernel32.
            Module ctypes = client.getModule("ctypes");
            PushyObject windll = (PushyObject)ctypes.__getattr__("windll");
            PushyObject kernel32 = (PushyObject)windll.__getattr__("kernel32");
            PushyObject GetCurrentProcessId =
                (PushyObject)kernel32.__getattr__("GetCurrentProcessId");

            // Call GetCurrentProcessId. Note that the Python interpreter is
            // running in a separate process, so this is NOT the process ID
            // running the Java program.
            Number pid = (Number)GetCurrentProcessId.__call__();
            System.out.println(pid);
        } finally {
            client.close();
        }
    }
}

Neat, eh? What I have demonstrated here is the following:

  • Connecting a Java program to a freshly created Python interpreter on the local host.
  • Importing the ctypes module therein, and then getting a reference to kernel32.dll (this assumes Windows, obviously. It would be much the same on Linux/UNIX platforms.)
  • Executing the GetCurrentProcessId function to obtain the process ID of the Python interpreter, and returning the result as a java.lang.Number object.
The final point is an important one. Pushy automatically casts types from Python types to their Java equivalent. For example, a Python dictionary object will be returned as a java.util.Map. If that map is modified, then the changes will be made in the remote dictionary object also. Tuples, which are immutable, are returned as arrays, whilst Python lists are returned as java.util.List objects.

The Pushy Java API aims to provide Java standard library equivalent interfaces to Python standard library modules where possible. For example, there is a pushy.io package for dealing with files in the Python interpreter using  java.io.-like classes. Similarly, a pushy.net package exists for performing socket operations using a java.net-like interface.

One can also connect to SSH hosts, as is possible through the Pushy Python API. This is achieved by creating a connection to a local Python interpreter, and thence to the remote system using the Pushy Python API in the subprocess. This is all done transparently if a target other than "local:" is specified in the Java program.

Enjoy!

Wednesday, June 30, 2010

First Post

Woohoo!

On a more serious note... if anyone stumbles across this page, I will be using it for discussing my project Pushy. Pushy is a Python (now Java too) package for connecting to a remote Python interpreter, and accessing objects therein as if they were local. In other words, it's a sort of RPC package.

So why another RPC package? While I was working on test automation, I identified a couple of things I didn't like about existing RPC frameworks:
  1. Invariably, a nailed-up (i.e. runs for an extended period of time) server is required to be running for you to connect to. This leads to the problem #2.
  2. Custom software needs to be maintained on both the client and the server.
  3. The security mechanisms in existing frameworks have a tendency to suck. For nailed-up servers running as an arbitrary user, the server program must perform its own authentication/authorisation to ensure the user can't access resources it isn't supposed to.
My thinking was this: rather than implementing RPC services and maintaining them on all of these different servers, why can't I put all of the logic in the client? The Python Standard Library is rather extensive, why don't we just expose that to the client, and let the client define the "service"? That's the basis of Pushy.

So first I started hacking away to develop a proof of concept, using XML-RPC to transparently access objects in a remote interpreter, automatically creating proxy objects to represent remote objects and performing method/operator calls by sending requests. Then I found RPyC, which did essentially the same thing, only better. 

So at this stage I've moved the "service" from server to client, but I still need to run some code on the server, and it's still "nailed-up". What's more, is that the server is running as a single user, which poses a massive security risk. How can we do better? Enter SSH... SSH is prevalent on Linux and UNIX operating systems, and one of the cool things you do with it is remotely execute a command and pipe to/from its standard I/O. Maybe we could do something with that?

Using SSH solves all three problems, in fact. Pushy works as follows: the client application imports the Pushy package, and invokes a function to "connect" to a remote host. What this does is creates an SSH connection to the remote host, using the username and password (or public-key encryption) specified by the caller. After the connection is created, Pushy executes Python in the remote system, passing it a command-line program. i.e. Something like "python -c 'run_server()'". This command-line program is a short one, which reads a larger program off its standard input stream, and executes it to start the Pushy server program. The program didn't exist on disk before the connection, and won't exist after.

So let's revisit the three problems now:
  1. (Problem: a nailed-up server is required.) Unless you count sshd, no nailed-up services are required on the server. I think it's fair to discount sshd, as it is so commonplace.
  2. (Problem: custom software must be maintained on both client and server.) As described in the paragraph above, there is no longer any custom server code required to be maintained on the server. So we can implement programs to access arbitrary portions of the Python Standard Library on a remote system, with nary a change on the server. There is an added benefit here: if the client/server protocol changes, there's still nothing to upgrade on the server.
  3. (Problem: server code must perform application-level authentication/authorisation.) Did I mention I'm lazy? Doing authentication/authorisation properly is a pain in the neck, and I'd like to avoid it if I can. Turns out I can if I'm using SSH, as the "server" program is running as the user specified by the client program. Usual operating system authentication and access controls ensues.

Over time I decided to drop RPyC in favour of a writing my own protocol. I was using RPyC for things it wasn't intended and it showed in various areas, such as exception handling. One thing remains though: the auto-importing feature of RPyC is lovingly imitated by Pushy.