Second year group project demos

Last Wednesday was the culmination of the second year group projects.  We had an afternoon of demos followed by lightning talks from each group showing off their projects.

Here is a brief summary of the projects that the Queens’ students worked on:

Retail Category Manager:  Tatsiana’s group were given the brief of making it easier for retailers to list their products in online marketplaces like Amazon.  The idea was to auto-categorise a list of products based on keywords in the name and description.  They adopted a neat Bayesian approach which they trained on the products already categorised in the marketplace.  This had a nice effect that if a misclassification occurs it can be manually corrected and then the prior probabilities can be updated to reflect the new knowledge.

Location Based Teaching: Radu and Sid’s project was to build a location tracking system which tracked smart phones using iBeacons.  They then implemented a location-based callback system so that you could be notified of interesting events near-by in the building.  The location system worked by matching fingerprints of visible beacons with a previously created fingerprint map.  They managed to get quite accurate results (within 10 metres) in some parts of the building.  However, in more open spaces the accuracy was less good (sometimes even putting you on the wrong floor).   They built an Android app and a website which worked pretty well.

Sid demonstrating his location-aware Android application to Ramsey.

Sid demonstrating his location-aware Android application to Ramsey.

Building the Matrix:  Katie, Ben and Jamie got to play with two Oculus Rift headsets.  They had to build a distributed multiplayer virtual reality game. A lot of work went into this since they built their whole 3D engine from scratch in C++.  The game was bumper cars.  They had managed to get the latency on the headtracking down really well so when you moved your head the view updated very smoothly.  However, the latency of the game controls was quite a bit bigger – that’s my excuse for why I kept getting bumped off the track.

Ben and Jamie demonstrating their virtual reality game.

Ben and Jamie demonstrating their virtual reality game.

Micro friends video diary: Matt’s project involved automatically summarising video.  Their software automatically generates a short 3 second highlight clip of your video and shares in on a social network that they built.  They used various image processing algorithms (such as face tracking) to try and work out which were the best frames to include.  And they built an entire social networking website for people to share and follow other peoples video clips.

Well done to everyone for successfully delivering your projects on time.

A Friendly Competition

This week, in a session run by Jan, we were split into teams comprising one student from each of the first, second and third years and presented with a series of increasingly difficult problems to solve. There were fantastic prizes such as chocolates, flapjacks and even bottled water available for the winners, the runners up and, well, pretty much everyone.

Three people enter a room, each one with either a blue or a red hat on their head. They do not know the colour of their own hat but they can see the hats of the other two people. Once they had a chance to observe the colour of the other hats, they can guess what colour their hat is or say nothing. All guesses happen simultaneously and no other communication is allowed. if no one guesses wrong and at least one person guesses correctly, they win, otherwise they lose. Given that the colour of each hat is assigned randomly by a flip of a fair coin, what is the best strategy and how often does it win?

The first question was one of probability. Surprisingly unintuitive, perhaps you wouldn’t expect there to be a strategy any better than picking at random, but you’d have to think again. Radu, on my team, got to the answer fairly quickly but it took much longer for him to convince Holly and me that he was correct!

You are given two hourglasses. One measures 4 minutes and the others measures 7. Can you measure 9 minutes?

Bonus: given two hourglasses that measure n and m minutes, what values of k minutes can you measure and how much set up time do you need?

This question is closely related to the perhaps more widely known problem of measuring a specific amount of water given two unmarked jugs that are known to hold n and m litres respectively. You can fill the jugs up, empty them, or transfer water from one jug to the other until one is either full or empty. You can’t, say, pour out half of the water, however: you have no way of measuring exactly half, just as you have no way of knowing when exactly half of the time from one of the hourglasses is up in this problem.

Our team solved the hourglasses question more quickly than the first one, perhaps because all of us had seen the isomorphic water jugs question before.

Given a standard 52 card deck, 5 cards are randomly chosen by a member of the audience and given to a magician. He then selects one of the cards and keeps it, while arranging the remaining four cards on a table face up. A second magician then determines what card the first magician kept. What strategy did they use?

Note that while arranging the cards on the table, only their order can be significant, e.g. you cannot rotate them in any way to give extra information to the second magician.

In this clever question, it appears at first as if you do not have enough bits of information available to communicate which of the remaining 48 cards has been selected. Indeed, our team almost didn’t believe that was possible at first, and not one of the teams present was able to solve the problem after almost twenty minutes of discussion.

Eventually, Jan stepped up to the whiteboard and explained the solution — after a few people left the room, determined to come up with an answer themselves and refusing to have the game given away to them. Even once it had been explained, many of us didn’t see how the solution worked until we had discussed it amongst ourselves for another five minutes!

Following this question, the hour for the meeting was almost over, and besides, the non-muggles among us had to leave to go to a Harry Potter themed formal hall. But the dedicated computer scientists stayed for one final enigma.

You are given 3 Turing Machines and want to determine which ones terminate and which ones don’t. You have access to an Oracle that, given a Turing Machine, tells you whether it terminates or not. However you can only query it twice.

Again, this question seems impossible because you are only given two bits of information and must seemingly use those to distinguish between 8 different possibilities. However, a solid understanding of the theory of computation led Eduard to a brilliant way of generating that final bit that the Oracles cannot themselves provide.

A Non-context-free Metamorphic Virus

Last wednesday’s session was an enlightening view of the dark and mysterious world of computer viruses. Mistral was our guide, delivering a detailed and intriguing talk on the metamorphic virus he has been developing for his Part II Project

Given the wide misuse of the term by the media, it is worth clarifying what is actually meant by a virus, in the technical sense.

Virus (pl. viruses) is a program that can ‘infect’ other programs by modifying them to include a possibly evolved copy of itself.

- Fred Cohen

With this definition in mind, we can move onto metamorphic viruses, which are viruses which mutate their code in some way upon each infection.

To wet out appetite, Mistral conjured up screenshots of historic viruses (pictured), giving a brief history of computer viruses. The earliest viruses were mainly for the purposes of a joke and it was typically the intention of the creator to make it obvious to the user that their machine had been compromised. This usually took the form of displaying messages or images to the user. Indeed, mistral gave a demo of a DOS virus which he had written (!) which informed users that their PC had taken a ‘holiday’ and would then proceed to lock the PC for the entire day!

example_mistral

Mistral went on to describe various techniques deployed by anti-virus engines which attempt to detect infected processes and files on the system. He covered a range of topics, covering simple techniques such as simply hashing the whole (or parts of) the file to far more advanced techniques, including the use of finite automata to model and detect infections.

He explained the principle components of a metamorphic virus and how his virus has been designed. This list of components included a disassembler, assembler and linker as well as the analysis engine and transformation system.

The first step in the infection process if to generate the first patient, which is taken by infecting the first process with your virus, which would have been compiled into an executable. This form of the virus is the one which is transmitted and will evolve continually on each new infection. The virus will need to disassemble itself at each step, into some internal representation, analyse and transform this representation before lining and assembling the result into the new infected process. This is a huge topic but Mistral delivered detailed examples including instruction permutation and constant folding/unfolding.

The final part of Mistral’s talk involved a discussion of formal languages and automata and how viruses can be classified:

  • Language: Virus family
  • Word: Virus Instance
  • Grammar: Metamorphic engine
  • Automata: metamorphic virus detector

It turns out that there is a weakness in the design of such detection schemes and Mistral presented some of his ideas about how this can be overcome.

Overall, a thoroughly enjoyable talk, with some extremely interesting food for thought!

The Hassabis Fellowship in Computer Science

Exciting news.

One of our alumni Demis Hassabis has made a donation to college to endow two fellowships. One will be the Hassabis Fellowship in Computer Science and the other will be the Niccoli Fellowship in Natural Sciences in honour of Demis’ wife, Teresa. They met at Queens’ and she studied Natural Sciences so I think that’s very fitting.

My fellowship will henceforth be known as the Hassabis Fellowship in Computer Science.

The supervision system, and indeed the close working relationship between me and my students is very expensive to provide. Interest generated from the college’s endowment is used to subsidise this. Demis’ donation means that there is now money in the endowment specifically for the purpose of teaching Computer Science. This is a really great thing to ensure that we can carry on delivering the highest quality teaching and support to Computer Science students at Queens’.

I’m also pleased to report that the college’s Governing Body has decided to admit Demis as a Fellow Benefactor. The first ever Computer Science Fellow Benefactor at college!

Thank you Demis!

Anonymous Peer-to-Peer File Sharing

300 million people use peer-to-peer file sharing systems every month. However, with privacy being a growing concern among todays users, the need for an anonymised file sharing system is evident. This is the basis for Sam’s Part II Project, Anonymous Peer-to-Peer File Sharing.

Sam introduced us to the basic concepts of file sharing, both client-server and P2P methods. BitTorrent uses the peer to peer method which has the advantage of having higher availability, reliability and usually providing faster download speeds. There are many uses for file sharing, such as downloading music from Spotify or downloading games via apps like Steam (Eduard was particularly surprised to learn that Steam uses a P2P system). Sam argued that although these services are useful, there are many reasons to provide privacy and it is very easy for a malicious user to discover peers using the service.

sampres1

There are methods to stay anonymous when using P2P services such as using a VPN to connect, or using TOR. However, a good VPN is usually not free and usage can still be traced back to you, the user. TOR is slow and is incompatible with many clients.  As a solution to this problem, Sam has implemented a system that provides this desired anonymity using relays. The program first sets up a route to each peer and a tracker encrypts each layer; this is essential for the relays to know where to forward the data. BitTorrent is run once the route is set up, and data is encrypted using an end-to-end key.

sampres2

Sam demoed the project by showing us the transfer of a picture from one location to another on his computer and as a closing remark outlined some limitations to this approach. Unfortunately the tracker provides a central point of weakness to the system and must be trusted itself.

Sam’s project demonstrates a possible solution to meet the privacy concerns of today’s users whilst still allowing them to download all their songs and movies. Best of luck with your project Sam!

Knot Theory Presentation

This week at our weekly Queens’ Computer Science meeting, Eduard presented his Part II Project about Knot Theory. While Knot Theory is still a relatively new field of study and is largely being explored on a theoretical level, a significant application of Knot Theory has been to DNA in genetics.

The general problem of Knot Theory is to devise the best method to convert a knot, a twisted or otherwise manipulated circle in 3D space to a circle in 3D space, assuming that this can be done. Eduard’s project concentrates on trying out two different solutions to this problem and seeing which one more efficiently discovers the actions needed to result in a circle.

The first part of Eduard’s talk focused on the image processing aspect of his project. In order to transform a possibly unclear image to a graph in 2D, the pixels must be processed one at a time and converted to either black or white depending on whether or not the specific pixel represents a knot or the background. In addition to showing the image below, Eduard also performed a cool live demo in w he took a photo of a knot drawn on the white board with a marker and demonstrated the image processing, converting the imperfect hand-drawn image into a clear representation of the knot on the computer.

An example of an image containing a knot what needs to be processed before being used.

 

Once the redundant information in an image is removed, any bridges that were broken in the image need to be connected and the problem becomes how to figure out the center of each line to best be able to model the knot with a line and avoid various edge cases where the line may become stuck or curve back on itself while trying to trace the knot. The center of a knot segment can be computed by using circles of a finite radius, limited by the perimeter of the knot, sampled at various points in the knot and calculating the local maxima.

The knot can be represented in two different ways using Gauss codes, either by encoding the bridges with numbers and with + or – to represent either going over or under an intersection, or by using a three half-planes to represent the knot.

One method of using Gauss codes to represent a knot.

slide_18

A second way to visualize and represent a knot.

A finite number of the three Reidmeister moves can be applied to the knot diagrams to end up with a circle. Eduard plans to explore the two algorithms that solve the Knot Problem with various heuristics.

The three Reidemeister Moves which can be applied to a knot.

 

 

In addition to learning about the fascinating field of Knot Theory, we discussed some recommendations for giving good presentations, including committing the first thirty seconds of your talk to memory, since the audience will likely decide whether they will remain engaged within the first thirty seconds of a talk.

 

 

Requirements management in large systems

Last night we had a guest talk from Bob Salmon who was an undergraduate at Queens’ in 1989.

Bob talked about how adding a single requirement can drastically change the design of a large system. We went through some examples starting with the requirement that your system should be upgradeable. This is easy to do if its your laptop: install updates and reboot. But if you also have the requirement that it must work for a very large system. There might not be enough downtime available (e.g. overnight) for you to shut the system down to upgrade it. So instead you might run a series of copies to a shadow system whilst leaving the original system (the system of record) running. Once all the copies are done you can then flick a switch to deploy the new one. We also looked at architectural approaches to provide high-availability – it was left to the audience to think about how to provide high-availability upgrades!

Bob has worked on the UK smart meter project which is slated to install smart meters in every home in the UK by 2020. He talked about the challenges in building this system and how some of the different requirements are interacting to make things even more difficult. One interesting aspect of the Smart Meter proposal is that other devices in my house will be able to talk to the meters. For example, my washing machine might want to know when electricity is cheap. This requires firewalling within the house to ensure that consumer devices cannot interfere with the national energy distribution infrastructure – we have to watch out for trojan washing machines.

After the talk we went to dinner as usual and we talked about how the Computer Science course has changed (or not changed!) since Bob’s time.