• View
• Edit
• History
• Print

Applications

Notes

• April 20: several people have pointed out that because the suggested checksum is a sum, it is trivial to find additional bytes to equal a new checksum. This checksum function has been changed and other new extensions added.

Introduction

Cloud computing introduces new programming models for scalability and reliability. While Amazon provides a complete virtual machine for execution, it also provides storage and communication abstractions different than traditional operating systems. In contrast, Google AppEngine provides a restricted execution environment only for Python and Java, while Microsoft Azure provides an language-level virtual machine and programming interface.

Your job will be to implement an application using one of these cloud-programming models:

• Windows Azure introductory special provides 25 CPU hours, 500 MB storage, and 500MB of data transfer in and out.
• Google App Engine provides 1 GB/day data transfer and 6.5 CPU hours per day.
• Amazon Elastic Compute Cloud appears to provide nothing free, but is fairly cheap.

Application of your choice

If you have a particular application you would like to implement, that is great. It should be of complexity similar to the suggested application (which is low!). Please let me know in advance if you make this choice.

Suggested Application

Your goal is to build a checksum cracker: a user can upload two documents, your service will try to append data to the second document to produce another document with an identical, or at least similar, Unix checksum. For speed, your service should partition the problem and simultaneously search using multiple machines. This can be CPU intensive, and may run up against CPU limits. So, you may want to store a pre-computed dictionary of password hashes to limit the search space.

Sum function

The original checksum below should not be used. For simplicity of implementation and speed of execution, you will use a historic and not-very-secure checksum:

                   s = sum of all bytes;
                   r = s % 2^16 + (s % 2^32) / 2^16;
                   cksum = (r % 2^16) + r / 2^16;

This checksum is available on Linux with the cksum -o 2 command.

You should implement checksum using the CRC-32 checksum. Source code in C is available here, and implementations exist for most languages.

If you have this working, some possible extensions are:

• Make sure the file retains text format - no unprintable characters.
• Try to make the generated text look real, in that it contains words or word-like strings of characters rather than random characters.
• Specify a URL of an HTML page, and have it output a valid HTML page with a matching checksum.

Interface

A user should be able to go to a web, paste in an original document (or upload a file), and then a second document to be modified. The output should be the second document with data appended to make it match the original checksum.

What to turn in

Please turn in a paper describing the implementation and performance of your system.

Google App Engine help

• Getting started with Python
• Getting started with Java
• Tutorial on Google Web Toolkit including App Engine

Windows Azure Help

The Azure development kit requires a machine running Windows Vista or Windows 7. If you want to do this from a Linux workstation, you can use VMware and the lab-provided Vista virtual machine.

• Getting started with Windows Azure