​John Hughes, Functional Programming, Computer Science and Engineering,

A better way to catch bugs

​As software is becoming a key component in every part of society, the consequences and costs of errors in software are daunting. Out of sheer curiosity and playfulness, researchers at Chalmers developed the testing tool QuickCheck, now used by major companies to find and fix crucial bugs in software before it’s released.
​The cost of software errors is estimated to be over a trillion USD each year worldwide. Perhaps that is why software development companies spend half their effort on testing. Research into new ways of software testing is making it not only better and more efficient but also fun, at least according to professor John Hughes at the department of Computer Science and Engineering. He is one of the brains behind what is called property-based testing. “You’re not working with one test case at a time, you’re working with whole families of test cases. You’re not thinking about what your code should do for this particular input, you’re thinking about what your code should do in general. It’s just a higher level of abstraction. So, one of the strengths of property-based testing is that it’s actually a lot of fun.”

In traditional software testing the tester has to compose each test case individually. This is an enormous manual process, even when running the tests is automated. In property-based testing the software developer specifies general properties that the software should satisfy in a wide variety of cases. Examples to test these properties are then chosen automatically, enabling very many tests to be run and more bugs to be found.

“And when there are bugs, instead of finding them a couple of weeks after writing the code, you find them just like that” says John, and snaps his fingers. “You see an example of the bug and realize, I never thought of this. Then you can go back and fix the code while it’s still fresh in your mind.”

Watch the video of John explaining functional programming

John has been developing the idea of property-based testing for nearly two decades. Together with Koen Claessen he developed the first property-based testing tool, an open source tool called QuickCheck. It was followed by a commercial version developed by John’s company Quviq.  However, this success was not inevitable. If it hadn’t been for his curiosity and being in the right room at the right time, the idea might not have had the same impact.

The right idea in the right room

In 1999 John Hughes had just managed to meet an important deadline in his research and was, in his own words, “completely pooped”. With nothing else pressing, he started playing around with a few ideas. “I was just hacking away in my room. One of the ideas was to write properties and then generate random input to perhaps discover the ones that were false.” Koen Claessen, a PhD student in the department at the time, knocked on his door and asked what he was doing. Koen came up with ways to improve the idea, and showed up the next day with some code he’d written.  “I used that and kept hacking and made another version and showed it to him and so forth. We worked on it together and by the end of the week we had a first basic version working.” John says.

They co-authored a paper about the research which, after initially being rejected, was published at the International Conference on Functional Programming in 2000. Ten years later they received the Most Influential Paper award at the same conference. “It’s quite funny. Now it’s the most cited paper from the ICFP, ever.” John adds.

While the idea was now scientifically recognized, John Hughes didn’t quite realize the importance of the method they’d created until a meeting of SSF’s programme committee in 2005. The foundation asked the researchers they were funding to present their work to representatives from Swedish industry. In the room were both John’s first customer and one of Sweden’s leading entrepreneurs. John’s presentation included a short demo of the QuickCheck tool before he went on to explain other parts of his current research project. “At the end of the presentation Mike Williams from Ericsson basically said, that QuickCheck stuff, we want that.”

Also there was serial entrepreneur Jane Walerud. She saw the potential of the idea and advised and pushed John to start a company based on QuickCheck. “I was very excited. I’d worked with my research for a long time and I wanted to see it have industrial impact. This was an opportunity to do just that.”

As a result, John Hughes and his colleague Thomas Arts founded the company Quviq AB with the intent of developing, licensing and selling services around the commercial version of QuickCheck. During the next decade, the company would help find software bugs for customers in telecoms, the vehicle industry, healthcare, blockchains, online gaming, and other internet services.

Research goes to work

In 2006 the first commercial application of QuickCheck was at Ericsson, to their Media Proxy product. Several bugs were discovered, among them one that was quite bizarre, but it shows the strengths of property-based testing. The bug was provoked by adding two callers to a multimedia phone call, then removing one and adding another, then removing the third and adding a fourth, then removing the fourth, upon which the product would crash. “An oddly specific scenario like this would never be included in a hand-written test suite. But QuickCheck discovered not only the scenario but also a serious, underlying fault, that data corruption occurred every time a caller was removed from a call.” John explains. Thanks to this, Quviq earned Ericsson as a long-term customer.

In 2010 staff from Ericsson were working at the financial service company Klarna. For six weeks they’d been trying to figure out why the main server was crashing every couple of months. Ericsson was responsible for the failing component causing the crashes, each time requiring the database to be restored from a backup, a process which took several hours each time. After weeks of looking for the now notorious bug in the Mnesia database, Ericsson contacted Quviq. “We were able to provoke the bugs in the database using at most six function calls. Once these simple test cases were found, Ericsson was able to fix each bug in less than a day” says John.

During the last two years Quviq has been working with IOHK, who run the 13th largest crypto currency, called Cardano. The blockchain was initially built by consultants, but once it was up and running, then IOHK quickly realized there were problems with the quality of the code. Quviq was brought in to help train the 25 developers already using QuickCheck. Errors were found in one of the most crucial functions of the block chain, the allocation of new blocks, which is the way transactions are rercorded. For Cardano this is determined by what is called proof of stake. “You have a number of people that are candidates for committing the next block, and you elect someone to do it, and it’s supposed to be proportional to the stake that they put in. We discovered that because of their poor testing, it wasn’t.” The deviation in proportionality was too small to be significant, but still considered a serious bug since it affected such a crucial function. “They have now improved their testing dramatically, thanks to the work we did with them, and they’re able to link it directly to the theory that their blockchain is based on.”

Property-based testing has proven to be somewhat more difficult than regular testing and requires properly trained testers. “But if you have those, I would argue that you save a lot of time, and you get much higher quality code.” John explains.

For John the synthesis of research and business has been a rewarding experience. “It’s great to put your research to work for a customer. Then you really find out what works well and what needs improvement. I really like that!”

The Department of Computer Science and Engineering is shared between Chalmers University of Technology and University of Gothenburg.

Page manager Published: Mon 21 Oct 2019.