Why would you accept inefficiency?

18 Jun

by Paul Curzon, Queen Mary University of London

British Airways Plane x 3

In May 2017, British Airways IT system had a meltdown. Someone mistakenly disconnected the power for a short time. The fleet was grounded and tens of thousands of passengers were left stranded for days. One suggestion was it was due to “cost cutting”. Willie Walsh, the Head of BAs parent group came out fighting, defending the idea of doing things cheaply: “You talk about it as cost-cutting, I talk about it as efficiency … The idea that you would accept inefficiency – I just don’t get it.”

The fact that many business leaders don’t get it may be exactly the problem. Doing things more cheaply than the competition is an idea that is at the core of capitalism. It is often taken as a given. But, is it really always true?

The best and only the best

Computer Scientists actually use the word “efficiency” in a subtly different way. When they talk about a program or algorithm being efficient, they do not mean that it was cheap. They mean it did exactly the same job, but faster or with less memory. This is one of the really creative areas of computer science. Can you come up with an algorithm that does exactly the same thing but in fewer steps?

The business version of efficiency would be fine if it had the same underlying principle. Do it cheaper, yes, but only if it really does do exactly the same thing in all circumstances. To company bosses, however, the trade-off can be seen as cut costs at all costs. ‘Waste’ is anything you think no one will notice. You accept the 1 in a million chance of it not working at all – just as with the BA meltdown, taking the hit (or rather your passengers do) because you think you will make more money overall as a result.

Even with algorithms we do accept inefficiency though. Engineering is often about trade-offs. Sometimes, you will accept inefficiency in the use of memory because it gives a way to get a faster algorithm. Sometimes you accept a slower algorithm because it is just easier to be certain your code really does do the right thing. Sometimes slow is good enough. Sometimes it is the bigger picture that matters. The fastest algorithms for searching for information require sorted data. That is why a dictionary is in alphabetical order. Finding the word you want is quick – you don’t have to check every word in turn to find the one you want. However, if you were only ever going to look for a single thing in a data source, you wouldn’t sort it first. You would use an inefficient search algorithm, because overall that would be faster than sorting and then searching once. Efficiency can be subtle.

Inefficiently safe

There are actually even more powerful reasons for demanding inefficiency. In the area of safety-critical systems, computer scientists build in redundancy on purpose. When the consequences of the computer not working is that lives are lost, we definitely want inefficiency, as long as it is well-engineered inefficiency. Dependability and safety matter more.

An algorithm is a mathematical object. If it works, it always works. However, programs operate in the real world where things can go wrong. Hardware fails, clocks drift, criminals hack, technicians do silly things by accident (like unplug the power). Systems that matter have to be resilient. They have to cope with the unexpected, with the never before seen. One way that is achieved is by designing in inefficiency. For example, if your single computer goes down, you are stuffed. If instead two computers run the same program in parallel, then if one goes down the other can take over. Ahh, but how do you know which is wrong when they disagree? Be even more ‘inefficient’ and have three computers ‘wastefully’ doing the same thing. Then, if one goes rogue, the three vote on who is at fault … cut them out and carry on.

Computer Scientists have developed many ingenious ways to build in guarantees of safety even when the world around conspires against us. To a cost cutter these extras may seem like inefficiency but the inefficiency is there, apparently unused most of the time, waiting to step in and avert disaster, waiting to save lives. Personally, I would accept inefficiency. I hope, for the sake of saved lives, society would too.

More on …

The Cyber-Security Honeypot

28 May

by Paul Curzon, Queen Mary University of London

based on a talk by Jeremiah Onaolapo, UCL

Wasps around a honeypot

To catch criminals, whether old-fashioned ones or cybercriminals, you need to understand the criminal mind. You need to understand how they think and how they work. Jeremiah Onaolapo, a PhD student at UCL, has been creating cyber-honeypots and finding out how cybercriminals really operate.

Hackers share user ids and passwords they have stolen on both open and hidden websites. But what do the criminals who then access those accounts do once inside? If your webmail account has been compromised what will happen. Will you even know you’ve been hacked?

Looking after passwords is important. If someone hacks your account there is probably lots of information you wouldn’t want criminals to find: information they could use whether other passwords, bank or shopping site details, personal images, information, links to cloud sites with yet more information about you … By making use of the information they discover, they could cause havoc to your life. But what are cybercriminals most interested in? Do they use hacked accounts just to send spam of phish for more details? Do they search for bank details, launch attacks elsewhere, … or something completely different we aren’t aware of? How do you even start to study the behaviour of criminals without becoming one? Jeremiah knew how hard it is for researchers to study issues like this, so he created some tools to help that others can use too.

His system is based on the honeypot. Police and spies have used various forms of honeytraps, stings and baits successfully for a long time, and the idea is used in computing security too. The idea is that you set up a situation so attractive to people that they can’t resist falling in to your trap. Jeremiah’s involved a set of webmail accounts. His accounts aren’t just normal accounts though. They are all fake, and have software built in that secretly records the activities of anyone accessing the account. They save any emails drafted or sent, details of the messages read, the locations the hackers come in from, and so on. The accounts look real, however. They are full of real messages, sent and received, but with all personal details, such as names and passwords or bank account details, fictionalised. New emails sent from them aren’t actually delivered but just go in to a sinkhole server – where they are stored for further study. This means that no successful criminal activity can happen from the accounts. A lot can be learnt about any cybercriminals though!

Experiments

In an early experiment Jeremiah created 100 such accounts and then leaked their passwords and user ids in different ways: on hacker forums and web pages. Over 7 months hundreds of hackers fell into the trap, accessing the accounts from 29 countries. What emerged were four main kinds of behaviours, not necessarily distinct: the curious, the spammers the gold diggers and the hijackers. The curious seemed to just be intrigued to be in someone else’s account, but didn’t obviously do anything bad once there. Spammers just used the account to send vast amounts of spam email. Gold diggers went looking for more information like bank accounts or other account details. They were after personal information they could make money from, and also tried to use each account as a stepping stone to others. Finally hijackers took over accounts, changing the passwords so the owner couldn’t get in themselves.

The accounts were used for all sorts of purposes including attempts to use them to buy credit card details and in one extreme case to attempt to blackmail someone else.

Similar behaviours were seen in a second experiment where the account details were only released on hidden websites used by hackers to share account details. In only a month this set of accounts were accessed over a thousand times from more than 50 countries. As might be expected these people were more sophisticated in what they did. More were careful to ensure they cleared up any evidence they had been there (not realising everything was separately being recorded). They wanted to be able to keep using the accounts for as long as possible, so tried to make sure noone knew the account was compromised. They also seemed to be better at covering the tracks of where they actually were.

The Good Samaritan

Not everyone seemed to be there to do bad things though. One person stood out. They seemed to be entering the accounts to warn people – sending messages from inside the account to everyone in the contact list telling them that the account had been hacked. That would presumably also mean those contacted people would alert the real account owner. There are still good samaritans!

Take care

One thing this shows is how important it is to look after your account details: ensure no one knows or can guess them. Don’t enter details in a web page unless you are really sure you are in a secure place both physically and virtually and never tell them to anyone else. Also change your passwords regularly so if they are compromised without you realising, they quickly become useless.

Of course, if you are a cybercriminal, you had better beware as that tempting account might just be a honeypot and you might just be the rat in the maze.

The very first computers

20 May

A head with numbers circling round and the globe in the middleVictorian engineer Charles Babbage designed, though never built the first mechanical computer. The first computers had actually existed for a long time before he had his idea, though. The British superiority at sea and ultimately the Empire was already dependent on them. They were used to calculate books of numbers that British sailors relied on to navigate the globe. The original meaning of the word computer was actually a person who did these calculations. The first computers were humans.

Babbage became interested in the idea of creating a mechanical computer in part because of computing work he did himself, calculating accurate versions of numbers needed for a special book: ‘The Nautical Almanac’. It was a book of astronomical tables, the result of an idea of Astronomer Royal, Nevil Maskelyne. It was the earliest way ships had to reliably work out their longitudinal (i.e., east-west) position at sea. Without them, to cross the Atlantic, you just set off and kept going until you hit land, just as Columbus did. The Nautical Almanac gave a way to work out how far west you were all the time.

Maskelyne’s idea was based on the fact that the angle from the moon’ to a person on the Earth and back to a star was the same at the same time wherever that person was looking from (as long as they could see both the star and moon at once). This angle was called the lunar distance.

The lunar distance could be used to work out where you were because as time passed its value changed but in a predictable way based on Newton’s Laws of motion applied to the planets. For a given place, Greenwich say, you could calculate what that lunar distance would be for different stars at any time in the future. This is essentially what the Almanac recorded.

Now the time changes as you move East or West: Dawn gradually arrives later the further west you go, for example, as the Earth rotates the sun comes into view at different times round the planet). That is why we have different time zones. The time in the USA is hours behind that in Britain which itself is behind that in China. Now suppose you know your local time, which you can check regularly from the position of the sun or moon, and you know the lunar distance. You can look up in the Almanac the time in Greenwich that the lunar distance occurs and that gives you the current time in Greenwich. The greater the difference that time is to your local time, the further West (or East) you are. It is because Greenwich was used as the fixed point for working the lunar distances out, that we now use Greenwich Mean Time as UK time. The time in Greenwich was the one that mattered!

This was all wonderful. Sailors just had to take astronomical readings, do some fairly simple calculations and a look up in the Almanac to work out where they were. However, there was a big snag. it relied on all those numbers in the tables having been accurately calculated in advance. That took some serious computing power. Maskelyne therefore employed teams of human ‘computers’ across the country, paying them to do the calculations for him. These men and women were the first industrial computers.

Before pocket calculators were invented in the 1970s the easiest way to do calculations whether big multiplication, division, powers or square roots was to use logarithms. The logarithm of a number is just the number of times you can divide it by 10 before you get to 1. Complicated calculations can be turned in to simple ones using logarithms. Therefore the equivalent of the pocket calculator was a book containing a table of logarithms. Log tables were the basis of all other calculations including maritime ones. Babbage himself became a human computer, doing calculations for the Nautical Almanac. He calculated the most accurate book of log tables then available for the British Admiralty.

The mechanical computer came about because Babbage was also interested in finding the most profitable ways to mechanise work in factories. He realised a machine could do more than weave cloth but might also do calculations. More to the point such a machine would be able to do them with a guaranteed accuracy, unlike people. He therefore spent his life designing and then trying to build such a machine. It was a revolutionary idea and while his design worked, the level of precision engineering needed was beyond what could be done. It was another hundred years before the first electronic computer was invented – again to replace human computers working in the national interest…but this time at Bletchley Park doing the calculations needed to crack the German military codes and so win the World War II.

More on …

A recipe for programming

13 May

By Paul Curzon, Queen Mary University of London

How is a computer program like a recipe? Let’s see, and as a bonus, here’s how to cook a quick pasta dish (for International Hummus Day).

Virtual Table Setting

Programmers are the master chefs of the computing world – except the recipes they invent don’t just give us a nice meal, they change the way we live.

Programs are very similar to recipes. They both give instructions that, if followed, achieve something. There is a difference between them, though, and it has to do with language. When chefs invent recipes they write them out in human languages like English. Programmers write programs in special languages. Why’s that? It’s all about being precise enough to be sure exactly the same thing happens every time. Recipes are often ambiguous which is why when I follow one it sometimes goes wrong. Programs tie down every last detail.

Let’s apply some ideas from programming languages to making meals. One of my favourite recipes is a hummus-based pasta dish (see box) so we’ll use that.

Structure it!

The first thing to notice about a recipe book is there is a clear structure. Each recipe is obviously separate from the others. Each has a title and a brief description of how it might be used. Each has an ingredients list and then a series of steps to follow. Programs follow a similar structure.

Cookery books use page layout to show their structure. Programmers use language: grammar, symbols and keywords. A keyword is a word that means something special. Once you have decided a word is a keyword you only ever use it for that purpose.

Let’s invent a keyword RECIPE to mean we’re starting a new recipe. The only time that word will appear in our recipes is to start a new recipe. What follows it will always be the name of the recipe. We will also need to know when the name ends. To make that clear we will use a special symbol made up of open and close brackets ().

We also want to be absolutely sure what is part of this recipe and what isn’t. We will use curly brackets: everything between the brackets is part of the named recipe.

RECIPE Hummus and Tomato Pasta ()
{

}

No comment?

Spaghetti that looks like optical fibre

Recipes usually include a brief description that isn’t part of the actual instructions. It is just there to help someone understand when you might use the recipe. Programs have descriptions like this too. Programmers call them ‘comments’. Remove the comments and the recipe will still work. We need a clear way to show when a comment starts and ends. We will start them with a special symbol ‘/*’ and end them with ‘*/’.

RECIPE Hummus and Tomato Pasta ()
{
/* Serves 2
This is a very quick 20-minute after work dish.
*/

}

Variable storage

What comes next in a recipe is usually a list of ingredients. The idea is to list everything you need so you can have it all ready before you start. I often have a problem following recipes, though, as they don’t list absolutely everything. Mid- recipe I might suddenly find I need a frying pan…when mine is crusted with burnt cheese sauce from last night! To avoid that, let’s list all the pans we need too. For our recipe we need a frying pan and a saucepan.

Something used to store things (like pans do) in a program is called a ‘variable’. Program variables hold things like numbers. The equivalent of the ingredients list ‘declares’ the variables. Declarations give each variable a unique name used to refer to it and also give each a ‘type’ – is it a saucepan or a frying pan we need? To be clear about when a declaration ends we add in some punctuation. Programming languages tend to use a semicolon for that – it’s a bit like a full stop in English.

Saucepan pan1;
Fryingpan pan2;

This says that in the rest of the recipe when we say pan1 (the variable name) we mean a particular pan: a saucepan (its type). When we say pan2 we mean a particular frying pan.

New assignment

Assignment does NOT move things around, it makes new copies

We will make a distinction between things to hold stuff, like pans (variables) and the actual ingredients that go in them: ‘values’. We will also follow the TV chefs and start by setting out all the ingredients in little dishes at the start so they are at hand – and make that part of the instructions.

We will need to declare a dish to hold each ingredient, giving its type and giving the dish a name. At the same time we will say what should be put in it before the recipe proper is started. We will use an ‘=’ symbol to mean put something in a variable (i.e., dish or pan). In programs, this action of putting something in a variable is called ‘assignment’. So, for example, we will declare that we need a dish to hold the hummus (called hummusDish). We assign 200g of hummus to it.

Dish hummusDish = 200g hummus;

We are now ready for the recipe proper. We can use assignment as a precise way of moving things from one place to another too. So if we say, for example:

pan2 = oilDish;

We mean empty the contents of the dish of oil into the frying pan. Programs are slightly different here, as when they do an assignment they don’t move things from one place to the other, they copy it. That would be like having a dish that automatically refilled itself whenever it was emptied.

Often we want to add to whatever is already in a pan. Programmers leave nothing to doubt and say explicitly that is what they mean:

pan2 = pan2 + onionDish;

This tells us to mix what is in the onion dish with what is in the frying pan, and then leave the result in the frying pan. We will use the + symbol to mean add together and stir.

Methods in my madness

So far all we’ve done is put ingredients in things and copied them around. To make a meal we need to do various basic cooking things like heat a pan or drain a pan. Rather than spell out every step of how you do that in every recipe, we will use a short hand. We create mini-recipes that say how to do it and just refer to them by name. They are often called ‘methods’ by programmers. Each is written out just like our recipe. In fact to a programmer our recipe is a method too. When we want to use it we just give its name followed by any extra information needed. For example to heat a pan, we need to know which pan, how high a heat and for how long. We write, for example:

Heat (pan1, medium, 12 minutes);

This format helps make sure we don’t miss something (like the time for example). We need similar methods for draining a pan and serving the meal. We won’t give the actual instructions here. In a full program they would be written down step-by- step too and not left to chance.

Time to do it right

We have come up with a language for recipes similar to the ones used for programming. We’ve used symbols, keywords and very precise punctuation – the language’s ‘syntax’ – to help us be precise. On its own that’s not enough – each part of the language has to have a very clear meaning too – the language’s ‘semantics’. Together they make sure in following a recipe we know exactly what each step involves. There is then less scope for a cook (or computer) to get it wrong. Computers, of course, have no intelligence of their own. All they can do is exactly follow the instructions someone wrote for them (a bit like me cooking).

Florence Nightingale: rebel with a cause

12 May

a glowing lantern

Florence Nightingale, the most famous female Victorian after Queen Victoria, is known for her commitment to nursing, especially in the Crimean War. She rebelled against convention to become a nurse at a time when nursing was seen as a lowly job, not suitable for ‘ladies’. She broke convention in another less well-known, but much more significant way too. She was a mathematician – the first woman to be elected a member of the Royal Statistical Society. She also pioneered the use of pictures to present the statistical data that she collected about causes of war deaths and issues of sanitation and health. What she did was an early version of the current Big Data revolution in computer science.

Soldiers were dying in vast numbers in the field hospital she worked in, not directly from their original wounds but from the poor conditions. But how do you persuade people of something that (at least then) is so unintuitive? Even she originally got the cause of the deaths wrong, thinking they were due to poor nutrition, rather than the hospital conditions as her statistics later showed. Politicians, the people with power to take action, were incapable of understanding statistical reports full of numbers then (and probably now). She needed a way to present the information so that the facts would jump out to anyone. Only then could she turn her numbers into life-saving action. Her solution was to use pictures, often presenting her statistics as books of pie charts and circular histograms.

Whilst she didn’t invent them, Florence Nightingale certainly was responsible for demonstrating how effective they could be in promoting change, and so subsequently popularising their use. She undoubtedly saved more lives with her statistics than from her solitary rounds at night by lamplight.

Big Data is now a big thing. It is the idea that if you collect lots of data about something (which computers now make easy) then you (and computers themselves) can look for patterns and so gain knowledge and, for people, ultimately wisdom from it. Florence Nightingale certainly did that. Data visualisation is now an important area of computer science. As computers allow us to collect and store ever more data, it becomes harder and harder for people to make any sense of it all – to pick out the important nuggets of information that matter. Raw numbers are little use if you can’t actually turn them into knowledge, or better still wisdom. Machine Learning programs can number crunch the data and make decisions from it, but its hard to know where the decisions came from. That often matters if we are to be persuaded. For humans the right kind of picture for the right kind of data can do just that as Florence Nightingale showed.

‘The Lady of the Lamp’: more than a nurse, but also a remarkable statistician and pioneer of a field of computer science…a Lady who made a difference by rebelling with a cause.

More on medicine

 

More on computer science and the image

HMS Belfast: destroying the destroyer

7 May

by Paul Curzon, Queen Mary University of London

HMS Belfast

On the South Bank of the Thames in the centre of London lies the HMSBelfast. Now a museum ship, it once took part in one of the most significant sea battles of the Second World War. It fought the Scharnhorst in the last great sea battle based on the power of great guns. The Belfast needed more than just brilliant naval tactics to stand a chance. It needed help from computer science and electronic engineering too. In fact, without some brilliant computer science the battle would never have been fought in the first place. It came about because of the work of the code crackers at Bletchley Park.

Getting supplies across the Atlantic and then round to Russia was critical to both the British and Russian’s survival. By 1943 the threat of submarines had been countered. The battleship Tirpitz had also been disabled. However, the formidable battle cruiser Scharnhorst was left and it was the scourge of the Allied convoys. It sank 11 supply ships in one operation early in 1941. In another, it destroyed a weather station on Spitzbergen island that the Allies used to decide when convoys should set off.

By Christmas 1943 something had to be done about the Scharnhorst, but how to catch it, never mind stop it? A trap was needed. A pair of convoys going to and from Russia were a potential bait. The Nazis knew the target was there for the taking: the Scharnhorst was in a nearby port. Would they take that bait though, and how could the British battle ships be in the right place at the right time to not only stop it, but destroy it?

The Allies had an ace up their sleeve. Computer Science. By this point in the war a top secret team at Bletchley Park had worked out how to crack the Enigma encryption machine that was used to send coded messages by the German Navy. It was always easy to listen in to radio broadcasts, you just needed receivers in the right places, but if the messages were in code that didn’t help. You had to crack the day’s code to know what they were saying. Based on an improved approach, originally worked out by Polish mathematicians, the Brits could do it using special machines that were precursors to the first electronic computers. They intercepted messages that told them that Scharnhorst was preparing to leave. It was taking the bait.

The British had two groups of ships. The Belfast, the Norfolk and the Sheffield were coming from Russia protecting the returning convoy. The HMS Duke of York was tracking the new convoy heading to Russia. Both were keeping their distance so the convoys looked unprotected. They needed to know when and where the Scharnhorst would attack. Bletchley Park were listening in to everything though, and doing it so well they were reading the messages almost as soon as the Germans. At 2am on Boxing Day morning the Belfast got the message from Admiralty Head quarters that SCHARNHORST PROBABLY SAILED AT 1800 25 DECEMBER. A further radio signal from the Scharnhorst asking for a weather report allowed the spies to work out exactly where the ship was by picking up the signal from different listening stations and triangulating: drawing a line on a map from each station in the direction the radio signal came from. The point they meet is the ship’s location. This is an example of meta-data (information about a message rather than the message itself) giving vital information away. The spies had done their job. It was enough to tell Vice Admiral Burnett on the Belfast where the Scharnhorst was aiming to attack the convoys. They could lie in wait. At this point, electronic engineering mattered. The Belfast had better radar than the Scharnhorst. They detected its approach without the Scharnhorst having any idea they were there. The first the Captain of the Scharnhorst knew was when they were hit by shells from the Norfolk. The Belfast ended up out of position at the critical point though and couldn’t join in. The faster Scharnhorst turned tail and ran. The Brits had had their chance and blown it!

Burnett now needed luck and intuition. He guessed the Scharnhorst would try another attack on the convoy. They took up a new waiting position rather than actively trying to find the Scharnhorst as others wanted them to do. By midday the radar picked it up again. The trap was reset, though this time the initial surprise was lost. An all out battle began, with radar helping once again, this time as a way to aim shells even when the enemy wasn’t in sight. Having failed to reach the convoy undetected a second time the Scharnhorst retreated as the battle continued. What they didn’t know was that they were retreating deeper into the trap: heading directly towards the waiting Duke of York. The chasing Belfast stopped firing and dropped back, making the Scharnhorst crew think they were safe. In fact, they were still being followed and tracked by radar once more, though only by the Belfast as the other ships had actually been partially disabled. Had the Scharnhorst known, they could have just stopped and taken out the Belfast. After several hours of silent shadowing, the Belfast picked up the Duke of York on the radar, and were able to communicate with them. The Scharnhorst’s radar had been crippled in the battle and thought it was alone.

The Belfast fired shells that lit up the sky behind the Scharnhorst as seen from the Duke of York, then largely watched the battle. Luck was on their side: the Scharnhorst was crippled and then sunk by torpedoes. Over a thousand German sailors sadly died. The crew of the Belfast were well aware that it could just as easily have been them, sealed in to a giant metal coffin, as it sank, and so held a memorial for the dead Germans afterwards.

The Belfast didn’t fire the torpedoes that finally sank the Scharnhorst and was not the key player in the final battle. However, it was the one that was in the right place to save the convoy, thanks to the Enigma decrypts combined with the Vice Admiral’s intuition. It was also the one that pushed the Scharnhorst into the deadly trap, with its superior radar then giving it the advantage.

It is easy to under-estimate the importance of the Bletchley Park team to the war, but they repeatedly made the difference, as with the Scharnhorst, making Allied commanders look amazing. It is much easier to be amazing when you know everything the other side says! The Scharnhorst is just one example of how Computer Science and Electronic Engineering help win wars, and here, in the long run at least, save lives. Today having secure systems matters to everyone not just to those waging war. We rely on them for our bank system, our elections, as well as for our everyday privacy, whether from hacking newspapers or keeping our health records secret from ruthless companies wanting to exploit us. Cyber security matters.

More on …