Collaboration between researchers at the University of Edinburgh’s School of Informatics and a leading processor manufacturer has resulted in a bug-scanning tool that’s become vital to Google’s Android product development.
Bugs in the system
Coding errors, commonly known as bugs, can be a headache for software companies and end users alike. Not only do they interfere with customer experience, but they are also extremely costly to fix and can cause serious reputational damage to the company whose software has glitched.
To guard against these problems, compiler testing is critical. Compilers are computer programs that translate computer code written in one programming language into another language, for example from source code to machine code, to make it suitable for the target platform. Compiler testing ensures that developed code is free of bugs and will generate machine code that behaves exactly how the user expects it to.
Cracking the code
The University of Edinburgh Compiler and Architecture Design research group (CArD), which sits within the School of Informatics (SoI), has been conducting research into optimising compiler technology since 2003. This research, led by Professor Björn Franke and Hugh Leather, has resulted in a programme of novel approaches to compiler testing, exploring a range of techniques.
The team has worked with British processor manufacturer ARM Ltd for some time, and the company established the ARM Edinburgh Centre of Excellence within the SoI as a way of deepening that relationship and securing a talent pipeline through the sponsorship and mentorship of PhD students. ARM works closely with Google, and PhD student Stephen Kyle’s ARM internship gave the CArD team the opportunity to develop a testing methodology for Google’s Android operating system, which was experiencing bugs at the time.
The team first used a probabilistic fuzz testing technique, which is designed to trigger faulty behaviour and uncover a bug in the system. Having observed that traditional fuzz testing was ineffective for compilers operating on binary encoded input languages, they extended the previously used naïve binary fuzz testing approach with domain awareness by providing hints of the encoding structure of binary encoded IR instructions. This drastically improved the effectiveness of their compiler testing methodology, and within 24 hours the team found over 30 times more programs that hang (become stuck) than a generic fuzz testing tool did during the same period.
At this time, Google had begun to transition their Android virtual machine from its existing Just-In-Time compiler, Dalvik, to a new and improved Ahead-Of-Time version, Android Runtime (ART). The research team took the opportunity to apply the compiler fuzzing technique to the virtual machine, with the aim of efficiently detecting and eliminating errors that would disrupt Google’s transition from Dalvik to ART. The team identified around 30 distinct bugs, divided into ART implementation errors and incorrect specifications. The research team then approached Google through ARM to say that not only had they managed to find and fix those bugs, but they had developed a tool that would find more.
Research with global reach
The research team’s work culminated in the tool DexFuzz: a novel piece of software which developers can run to automate the process of fuzz testing ART. DexFuzz has contributed significantly to the improvement of Android, one of Google’s flagship products that currently powers 2,500,000,000 smartphones worldwide. Since the development of Android 5.0 it has been applied to identify and eliminate bugs in ART before each new version is released, streamlining Google’s rollouts, boosting productivity and helping the company avoid substantial bug-fixing costs.
The impact of DexFuzz has been further amplified by Google making it an official part of the Android Open Source Project (AOSP). This means that any company who wishes to design and create an Android smartphone receives free access to DexFuzz for testing their design. Through AOSP DexFuzz now underpins the development and innovation of a considerable portion of the smartphone market: Google Android software powered 85% of smartphones in the world in 2020, which includes devices by global smartphone brands such as Samsung, Motorola and LG.
Seeing our research developing from an initial, conceptual idea to a practical tool used by Google and other large companies and impacting the user experience of a billion Android users world-wide has been a deeply rewarding, and has widened my understanding of the mutual benefits of engaging in collaborations with industry partners. "
-Professor Björn Franke, Personal Chair of Software Transformation, School of Informatics
Work with the School of Informatics
University of Edinburgh Compiler and Architecture Design research group
60 years of Computer Science and AI research
Header Image: gorodenkoff/istock.com