Google Jam of Code

This is the second year I try to have some fun with python and the Google Code Jam.

This year I almost forgot about it, and started the challenge when almost half of the time was gone. Anyway I managed to complete almost half of the problems, which seemed pretty good to me, given that I spent just a few hours trying.

Unfortunately, my last attempt timed out by 3 minutes (out of 8 available) when trying to compute the result, which later proved correct. This reminded me about the importance of performance in my code: a little optimization of the code after my try gave it a speedup of 3x, which would have been enough to submit the result in time.

Anyway, both this and the last year I qualified for the second round. Last year I didn’t pass it, this year I hope to do better.

 

googlecodejam2015

JSMol plugin vulnerability and thoughts about security

JMol is a library used to create 3D models of molecules in Java, which can be embedded into webpages using the usual applets. JSMol is a Javascript library which is used to provide the Jmol capabilities through the HTML5 technologies, relying on server side computation for some functionality.

Here’s a short story about how I discovered some pretty bad vulnerabilities in the JSMol software, and how it can affect every server which is hosting this software.

 

Using my university’s moodle installation, I discovered that the JMol/JSMol plugin for moodle was installed and probably misconfigured in some way: it had unusual permissions set in its directory tree.

This made me curious and I wanted to better understand what was going on.

I made some research, and discovered the plugin along with its source code (the project is entirely open source), and started to look at the source of the only PHP file in the JSMol package.

Looking through the code, I discovered a lot of parameters used without proper sanitizing and checks, and quickly discovered two related and pretty serious vulnerabilities.

The first one is a vulnerability which allows an attacker to read the entire filesystem with the PHP process’ privileges. The second is even worse, but it seems it had been fixed in the newer releases of the software, and was about arbitrary execution of commands on the server.

They derived from an insecure use of PHP’s file_get_contents() and exec() functions in combination with badly checked parameters coming from GET and POST variables.

I immediately contacted the developer of the plugin and reported the vulnerability, along with the curator of the JMol plugin of moodle.

As of today, the vulnerability has been fixed by the developer, and should be available in the latest version of the software.

Anyway, some research I’ve made suggests that the vulnerability was present in many websites using the plugin, which I thinks are unlikely to upgrade the software. In particular I analyzed every registered moodle installation from moodle.net (roughly 50k) and discovered that a small fraction (~100) had the plugin installed and was vulnerable.

I would not classify it as a widespread vulnerability, but I think this should remind us of the nature of websites’ security. In fact, I would say that every even small piece of software publicly accessible on a website should be cause of concern when thinking about security.

As is often said, the best thing to do about software security is to firmly believe that you don’t have any.

 

1-hour-app project and randomChan

The 1-hour-app project is something I started to force myself learn android programming. It’s not a serious effort to make vendible apps, but more a concept that should stimulate myself to produce something creative fast, with simple ideas and easy implementation.

As you expect, the idea is to program an app from scratch to Play Store publishing in just 1 hour. This means that the main functionality of the app should be running in an hour, further improvement and updates are of course allowed, especially if I like the result when I’m done with the first development.

Actually I think that’s both funny and useful, or at least has been so far, with my first one-hour-app: randomChan.

The app is available on the Play Store, and was refined after first publishing. Of course, it’s kind of nonsense app, which I guess will be common when making apps with deadlines that tight.

update: Google decided the app was infringing someone’s intellectual property. I don’t know whose. In the future, I may reupload the app on a different app store.

QuiXXX removed from the Play Store

The android app Quixxx, which me and Marco Virgolin developed 10 months ago, was removed from the Play Store due to violation of intellectual property. I really don’t understand whose property we have been supposed to violate, as Google didn’t specify it in its automated email.

That was particularly sad, because the app was doing very well, despite having been made in three days as a joke. We had something like 4k downloads per day, and we were even earning something from the ads, and the statistics were still raising.

I think that this experience made me reflect on the potential which one has by being able to create apps and submitting them to the public this way. It’s incredible how simple (lucky?) it was to produce an app which got a decent user base in just some months and no further effort.

This is why I started a little project, ‘1-hour-app’ to force myself to learn android programming. I will talk about it in a later post.

3D website experiment

Greatly inspired by this article, it came to my mind that would be cool making some website which could be explored like the real world, rather than just consulted or read.

I picked the original code from the article, which already let you build a simple 3D world which could be navigated in first person, and modified it to have customizable blocks, with action, photos and mouse to control the view, enriching the experience.

Actually, then I spent a lot of time developing what would be the map editor, which has been really useful when designing my own map/world.

A first experiment that I have made is here.

I also uploaded the editor so that people can design and try their own world.

Everything will be saved locally to the localstorage of the browser, so for now, you can’t share the world you have created. Anyway, I’m planning to offer the possibility to create and share your own world, but it will take some effort so I will do it later.

The thing should work fine with chrome and firefox.

Collecting Robots

Collecting Robots is a little project I have made as a project for a university course of Operating System for Robotics. The goal is to plan a strategy for some “robots” to collect some “objects” and taking them to some “collect points”. The robots also have a maximum capacity, i.e. they can take a maximum number of objects at once, so to go on they will need to take the objects to a collect point.

The problem is quite hard (I believe it is NP-hard) so my first thought was to use an heuristic approach. I implemented a genetic solution using the JSGenetic library I wrote some time ago.

Actually there’s a little problem with my implementation: the crossover operation is quite weak. It does not combine the two parent individual in a complete way, thus the generated children is often very similar to the parents. This moves the evolution capability towards the mutation process, which is much more random, and this means the evolution will lead more likely to a local optima. This is especially evident with large problems (many objects) when object positions are not uniformely distributed in the map.

The app is publicly available here.

Browser compatibility:

  • [Google Chrome/Chromium] OK
  • [Firefox] Some problems, “go” and “animate” button works but label doesn’t refresh (isn’t .innerText standard?), simulation is slower
  • [IE] Not tested
  • [Safari] Not tested

Some notes on usage of the app:

Map generation

You may use the randomly generated map which is presented on startup, generate a new one with the “randomize” button, or generate your own map.

To generate your map, just press “clear” to clear current map, then select the proper point you want to place on the dropdown list, and place it clicking on the map.

If you want to change the number of points used by the randomize option, you can place the point manually on the map, in the number and type you want them to be, and then pressing “randomize” will make a new random map with the number and type of points you placed.

Evolution of the solution

When the map is ready, you can press “init Evolver” to initialize the Evolver object, which is responsible for managing the evolution process.

Then, pressing “go” will start the evolution, showing the best solution found in the left canvas.

When you’re happy with the shown solution, press “stop”.

Simulation

Beware that you need to stop the evolution to run the simulation. Doing otherwise will lead to unknown results :P

When you have a solution (you need to at least have initialized the Evolver), you can see the robots in action in the right canvas by pressing “animate”, which will start the simulation with the current solution.

JSGeneticNeuralNetwork.js experiment

This new project is about feed forward neural network with genetic evolving weights. I’ve combined my two libraries, JSGenetic and JSNeuralNetwork, plus a little module I’ve developed about continuous genetic algorithms, and developed a little library which evolves neural networks with a genetic algorithm.

A little example I’ve made to test the library can be found here, it’s pacman learning to eat.

There are also other examples in the JSNeuralNetwork page.

QuiXXX down, quick and hopefully effective primitive load balancing system

QuiXXX, an app for android and windows phone me and a friend developed some time ago, was actually (and unbelievably) doing well. It has been receiving ~ 5 to 10 thousands visits per month, which was about 5-10k times more than we expected when we first developed it as a joke.

Anyway, recently there has been a peek in traffic (looks like mexican windows phone users liked the app) and we first noticed the problem: we are exceeding the maximum CPU load of our free hosting service (frogcp.com):

cpuexceededfrogcp

So I registered another free account on altervista.org and uploded the app there, then also mirrored the app on my domain www.nicassio.it, and wrote a very primitive load balancing redirect in php to be hosted on the original service frogcp, which redirects to one of the two mirrors with equal probability.

Let’s see if this will sort it out.

Ah, this broke the scoreboard, but this is temporary.

I’ll update this blog post when there’s further information.

[update]

We needed to do this without an actual update of the app, but this is not possibile, at least for android. Any page on a different domain will be opened in the browser, instead of within the app. That’s because we didn’t tell the app to handle redirection that way. Since we are not willing to release an updated version of the app right now, after being ublocked today I reuploaded the app to the original frogcp url making some changes to lower the cpu usage. I hope this will be enough for the near future.