Mathematician sees tie between knots and cyber security

By creating a formula that calculates the number of ways to knot a necktie at 177,147, KTH postdoctoral researcher Mikael Vejdemo-Johansson has generated worldwide attention. He and his collaborators took aim at the way in which a previous attempt to quantify variations of knots had come up short.

The project has spawned a random necktie knot generator on the internet. But Vejdemo-Johansson hopes it will also generate a discussion about formal languages in computing, and how to work with them to improve network security.

In 1999, University of Cambridge researches Yong Mao and Thomas Fink devised a mathematical language to describe all actions that can be used in knotting a necktie, arriving at a total of 85 possible outcomes.

It was that list that Vejdemo-Johansson checked after going on Youtube to learn how to knot ties like the ones worn by The Merovingian, a villain from the movie “Matrix Reloaded”.

“There is a clique of fans who, over the internet, have been discussing how to reproduce the weird tie knots worn in the movie, which has led to a number of novel tie knots: the Edeity, the Eldredge and the Trinity,” Vejdemo-Johansson says. “I learned these knots; and for my own amusement looked up the classification.

“I realized that the knots were not included in the list established by Fink and Mao,” he says.

One reason is that all these knots rely on not having a flat front, and they have several tucks along the way, he says.

“Fink’s and Mao’s language seemed to be able to describe the knots, but their listing excluded them, so I started working on figuring out a more complete enumeration, and recruited some collaborators,” he says. Joining him in the effort were Anders Sandberg from Oxford University and two experts in formal languages, Meredith L. Patterson and Dan Hirsh.

They adjusted some parameters – such as raising the number of possible winds from 8 to 11 – and simplified the language for describing tie movements, using just three symbols, W, T and U (W is a counter-clockwise move of the knot-tying blade, T is a clockwise move, and U is a tuck of the blade under a previous bow).

“We were able to narrow down the complexity class – a description of how hard it is to check correctness of potential sentences in a formal language – and write simple computer programs that generate all possible such sentences, ordered by length,” he says.

While the applications of this particular enumeration may not be revolutionary, Vejdemo-Johansson says that there is a serious side to working with formal languages in this manner.

“In our group of collaborators, the aspects of formal languages that interest us the most are in security,” he says. “Large classes of hacks and attacks on computer systems are rooted in the systems not completely validating input before starting to react to it, and this leaves them vulnerable to attacks that use badly formed input to trigger bugs or harmful behaviour in the system.”

The same tools that were applied to tying knots can be used when designing computer systems that interact with the outside world, he says. “We can avoid many of these bugs and attacks by simply refusing to listen to anything that is not a grammatically valid interaction,” he says.

“So this is a nice and accessible way to start talking about formal languages and how to work with them.”

David Callahan

Get instructions for random knot with the Tie Knot Generator 

List of known knots and their knotting sequences.

(Photo L-583 by Yi Qing available at http://www.flickr.com/photos/michiexile/12327230335/in/set-72157640550157983/ under a Creative Commons Attribution 2.0. Full terms at http://creativecommons.org/licenses/by/2.0.)