Juha-Matti Tilli could not sleep; instead, he had an idea that took him to the vulnerabilities of Linux

Juha-Matti Tilli decided to investigate whether a problem related to the topic of his post-graduate studies could be solved better. At the same time, he realised that earlier solutions may have been vulnerable and created a gap in information security.
Aalto University / smartphone and a computer / Photo: Unto Rautio

While working on his post-graduate studies concerning network data packets, Juha-Matti Tilli became interested in a rare way of breaking large quantities of data into IP fragments, that is, pieces to be transmitted over the network. He set out to identify how existing open source operating systems, such as Linux, compiled transmitted fragments into data packets, and was unhappy about what he saw.

Almost all systems seemed to assemble the fragments via a linked list. It is a data structure which the computer has to, in the worst case, go through step by step in order to find the desired information. However, computers can only perform a limited number of operations per second. As a result, the processing of data packets may require so many operations that even a small amount of suitable packets created by a possible attacker can make your computer use all available time to go through the list, and have no time to process useful traffic.

‘A traditional denial-of-service attack requires approximately 100 computers per target. Since few can afford such a number of computers for the purposes of an attack, the attacker contaminates 100 computers belonging to ordinary users. IP packets created for the purpose of an attack, however, only require approximately three computers per attack, which makes the attack 30 times more powerful than previously known methods’, he describes.

‘It felt meaningful to come across such a vulnerability, but at the same time, I wondered how it had ever managed to materialise.’

‘One night last summer, when I tried to fall asleep, I got a radical idea: what if the linked list used in combining packets would be replaced by a balanced search tree? It should be considerably faster than a linked list, which may well have worked as a security risk exposing computers to denial-of-service attacks because of its slowness.’

It felt meaningful to come across such a vulnerability, but at the same time, I wondered how it had ever managed to materialise.

Juha-Matti Tilli

Tilli’s idea of a balanced search tree for reassembling broken data means that the fragments are divided into two groups, which are further divided into groups of two, until the groups only contain only one record at most. For example, in the case of a group of 64 records, rather than going through each individual record, six ‘to the left or to the right’ decisions must be made instead. Instead of 64 operations, the computer thus runs only six operations and completes the task more than ten times faster than by using a linked list. Because of the achieved speed, a denial-of-service attack targeted at a computer would require such a huge number of data packets, it would be difficult to implement.

Tilli began to test the speed of Linux and found out that his idea of a balanced search tree was considerably faster than the existing linked list, just as he had expected. While running the tests, Tilli also noticed another vulnerability associated with the most common way to break information, TCP segmentation. He conveyed the information about the detected threats to, for instance, Finnish Communications Regulatory Authority and Linus Torvalds. It was later revealed that some of the vulnerabilities also concerned the Microsoft Windows operating system. Vulnerabilities in both Windows and Linux have now been repaired.


Text: Linda Koskinen
Picture: Unto Rautio

  • Published:
  • Updated:
URL copied!

Read more news

A dog and two researchers. Photo: Aalto University/Mikko Raskinen
Research & Art Published:

Significant Academy of Finland funding for for the multidisciplinary consortium project PAWWS – People and Animal Wellbeing at Work and in Society

Astrid Huopalainen, Assistant Professor at Aalto University, Linda Tallberg, Assistant Professor at Hanken School of Economics, and Anna Hielm-Björkman, Docent at University of Helsinki, are principal investigators of the project
A teacher and two researchers smiling and sorting through paper presentations in a classroom
Research & Art Published:

Empathy in design and digitalisation – Aalto University researchers hold workshops for students at Arabia Comprehensive School

Aalto University researchers organised workshops for seventh graders, whose creative thinking skills were put to the test in designing future information services
Maja Jantar's rehearsal at Tartu Planetarium
Research & Art Published:

The Creative Europe project ‘Urban Travel Machines’ at Tartu international literary festival in Estonia

Eleven Aalto Arts students and VCD Lecturer Tarja Nieminen participated in the Tartu international literary festival Prima Vista from 9th to 13th May 2023.
Mira Hänninen
Cooperation, Studies Published:

Alumna Mira Hänninen: It is inspiring to see that my own work can have a positive impact on society

Our alumna Mira Hänninen, who currently works at Neste, applied to the School of Business for a master’s degree in Business Law because she wanted a more practical business perspective in her law studies. "The most rewarding thing about the studies was that we didn't just study the content of regulation, but also considered what kind of practical impact it has on companies' business and decision-making."