Impact case study database
Search and filter
Filter by
- Imperial College of Science, Technology and Medicine
- 11 - Computer Science and Informatics
- Submitting institution
- Imperial College of Science, Technology and Medicine
- Unit of assessment
- 11 - Computer Science and Informatics
- Summary impact type
- Technological
- Is this case study continued from a case study submitted in 2014?
- No
1. Summary of the impact
GraphicsFuzz, a tool that automatically finds bugs in compilers for graphics processing units (GPUs), is based on fundamental advances in metamorphic testing pioneered by Donaldson’s Multicore Programming research group at Imperial College London. GraphicsFuzz has found serious, security-critical defects in compilers from all major GPU vendors, leading to the spin-out of GraphicsFuzz Ltd., to commercialise the research. GraphicsFuzz Ltd. was acquired by Google in 2018 for an undisclosed sum, establishing a new London-based team at Google, led by Donaldson, to focus on Android graphics driver quality. Google have open-sourced the GraphicsFuzz tool, and it is now being used routinely to find serious defects in graphics drivers that affect the Android operating system ( estimated 2.5 billion active devices worldwide) and the Chrome web browser (used by an estimated 66% of all internet users). GraphicsFuzz was enabled by two previous research projects from Donaldson’s group that have also led to industrial impact: GPUVerify, a highly scalable method for static analysis of GPU software, which ARM have integrated into their Mali Graphics Debugger tool, and CLsmith, an automated compiler testing tool that has found bugs in OpenCL compilers across the industry. The global GPU market is predicted to grow to grow from USD20 billion in 2019 to USD200 billion in 2027, and the industrial uptake of these tools – all based on fundamental research from Imperial College London – is having major impact on the industry, making GPU software safer and more secure for end users, and reducing development costs of GPU software and drivers.
2. Underpinning research
Nature of the research insights and findings relating to the impact: Graphics processing units are massively parallel, making them well-suited to accelerating computationally-intensive workloads, such as the machine learning and computer vision tasks required for autonomous driving, as well as enabling high-fidelity computer graphics. GPU programs and device drivers always need to be highly optimized: speed of execution is the sole reason for using GPU hardware. It is fundamentally challenging to build highly-optimised software with a high degree of reliability, yet GPU technology must be reliable: errors can be catastrophic when GPUs are used in safety-critical domains (such as autonomous vehicles), and malfunctioning graphics drivers may render consumer devices useless. The work underpinning this case study was motivated by the exciting challenge of how to design tools to aid in building correct and efficient GPU software and compilers.
Donaldson’s group have contributed to solving this challenge via (1) methods for reasoning about the correctness of programs designed for GPU acceleration, and (2) techniques for automatically testing GPU compilers to check that they faithfully translate high-level GPU programs into equivalent GPU-specific machine code. The main challenge associated with (1) is that GPU programs are typically executed by thousands of threads, requiring highly scalable analyses. The difficulty associated with (2) is that graphics programming languages are deliberately under-specified, so that no oracle is available to determine whether a given program has been correctly compiled.
Outline of underpinning research, and associated dates: The research at Imperial was conducted between November 2011 and March 2017, with entrepreneurship activity taking place between January 2017 and October 2017. The GPUVerify tool is based on a novel method for transforming a highly-parallel GPU program into a sequential program that models the execution of an arbitrary pair of threads such that data race-freedom (an important property of concurrent programs) for the parallel GPU program can be established by analysing the radically simpler sequential program [R1, R2]; this allows decades of work on sequential program verification to be leveraged. While GPUVerify can provide formal guarantees about the source code of a GPU program written in Open Computing Language (OpenCL), these guarantees are undermined if the downstream compiler that turns OpenCL into GPU-specific machine code is defective. This resulted in the CLsmith project for automated testing of OpenCL compilers (extending the Csmith project for testing of C compilers, from the University of Utah). CLsmith uses novel methods to generate OpenCL programs in a randomised fashion such that each generated program is guaranteed to compute some well-defined (albeit unknown) result [R3]. This approach enables differential testing: if two different OpenCL compilers yield different results on one of these well-defined programs, at least one of the compilers must exhibit a bug. Automated program reduction techniques can then be used to provide small OpenCL programs that expose the root cause of compiler bugs [R4]. Inspired by the success of CLsmith, GraphicsFuzz (originally called GLFuzz) is an automated testing tool for compilers for the OpenGL Shading Language (GLSL) [R5, R6]. The key innovation behind GraphicsFuzz is to apply metamorphic testing to compilers, based on the fact that we should expect two equivalent, deterministic programs to yield equivalent, albeit a priori unknown, results when compiled and executed. The tool takes an initial graphics program and uses program transformation techniques to yield many equivalent programs, looking for divergences in behaviour. Such divergences indicated compiler bugs. To shed light on the root causes of such bugs, transformations can be iteratively reversed, to search for pairs of equivalent programs that differ only slightly, but for which the compiler under test generates semantically inequivalent code.
3. References to the research
A. Betts, N. Chong, A.F. Donaldson, S. Qadeer, P. Thomson: GPUVerify: a verifier for GPU kernels. ACM OOPSLA 2012, pp. 113-132. Google Scholar cites: 165. DOI: 10.1145/2384616.2384625, Open access version
A. Betts, N. Chong, A.F. Donaldson, J. Ketema, S. Qadeer, P. Thomson, J. Wickerson: The Design and Implementation of a Verification Technique for GPU Kernels. ACM Trans. Program. Lang. Syst. 37(3): 10:1-10:49, 2015. Google Scholar cites: 41. DOI: 10.1145/2743017, Open access version
C. Lidbury, A. Lascu, N. Chong, A.F. Donaldson: Many-core compiler fuzzing. ACM PLDI 2015, pp. 65-76. Google Scholar cites: 92. DOI: 10.1145/2737924.2737986. Open access version
M. Pflanzer, A.F. Donaldson, A. Lascu: Automatic Test Case Reduction for OpenCL. ACM IWOCL 2016, pp. 1:1-1:12. Google Scholar cites: 11. DOI: 10.1145/2909437.2909439, Open access version
A.F. Donaldson, A. Lascu: Metamorphic testing for (graphics) compilers. ACM MET, pp. 44-47. Google Scholar cites: 30. DOI: 10.1145/2896971.2896978, Open access version
A.F. Donaldson, H. Evrard, A. Lascu, P. Thomson: Automated testing of graphics shader compilers. Proc. ACM Programming Languages 1 (OOPSLA): 93:1-93:29, 2017. Google Scholar cites: 40. DOI: 10.1145/3133917, Open access version
4. Details of the impact
Google’s Director of Engineering for Android Gaming and Graphics stated: “The cumulative effect of this impact on the Android and Chrome platforms is an improvement in graphics driver reliability and security for billions of users around the world. [...] Having something like GraphicsFuzz to aid in the discovery of vulnerabilities and issues can save companies like Google billions of dollars.” Savage also calls out the relationship between this impact and the underpinning research: “The impact is a direct result of the first-class research undertaken at Imperial College London that lies behind the GraphicsFuzz approach.” [I1]. It is estimated that there are more than 2.5 billion active Android devices worldwide, and that 66% of all internet users use the Chrome browser.
Impact of the GraphicsFuzz tool. The original GLFuzz tool was highly successful in applying metamorphic testing to finding bugs in GLSL compilers from all seven major GPU providers [R5, R6]. Donaldson disseminated this to a wide audience by writing a series of blog posts describing these findings ( AMD post, Apple post, ARM post, Imagination Technologies post, Intel post, NVIDIA post, Qualcomm post). These bugs included three serious security vulnerabilities for which the Imperial team received public recognition – an Apple iOS information leak [I2], an NVIDIA kernel mode vulnerability [I3], and data-capture exploit caused by a defect in an ARM graphics driver [I4]. Donaldson and team promoted GraphicsFuzz on social media, reaching the front page of HackerNews and being featured by sites such as Phoronix [I5].
Acquisition of GraphicsFuzz Ltd. by Google, and open sourcing. Encouraged by this media interest, Donaldson and his post-docs Hugues Evrard and Paul Thomson secured funding from the DCMS/Innovate UK ICURe programme to investigate commercialisation opportunities for the work, leading to them founding GraphicsFuzz Ltd., incorporated in December 2017 and spun-out from Imperial in February 2018 [I6]. The team promoted the technology via an innovative web-app that would run a set of GraphicsFuzz tests on a user’s device, allowing them to tweet a summary of the test results [I7]. This raised the profile of GraphicsFuzz quickly, leading to the acquisition of the company by Google in August 2018 for an undisclosed sum [I6]. Google open-sourced the GraphicsFuzz tool in September 2018 [I8].
Ongoing impact of GraphicsFuzz on graphics driver quality. Donaldson, Evrard and Thomson joined Google UK, and now lead a team specialising in methods to improve the quality of Android graphics device drivers, deployed on billions of devices worldwide. GraphicsFuzz is being used to find defects in Android graphics drivers from ARM, Qualcomm, Imagination Technologies and NVIDIA, who collectively produce GPUs for more than 79% of the smartphone and tablet GPU market. Tests that expose these bugs are being integrated with the Android Compatibility Test Suite, meaning that devices can only ship future versions of Android if these bugs are fixed in their drivers. The impact of this ongoing use of GraphicsFuzz is detailed in the supporting letter from Google’s Director of Engineering, Android Gaming and Graphics [I1].
Impact on Chrome. The WebGL technology brings graphics rendering capabilities to web applications but exposes widely-used browsers such as Chrome – used by most of the world’s internet users – to graphics-related security vulnerabilities. GraphicsFuzz has been integrated with the ClusterFuzz project for continuous fuzz testing of Chrome, and since January 2019 has found more than a dozen security vulnerabilities in Chrome’s WebGL implementation that had been missed by other testing methods. These vulnerabilities have now been fixed [I9].
Impact on open source graphics drivers. Google has used GraphicsFuzz to rigorously test AMD’s open-source driver for Vulkan, finding a large number of driver bugs, which have been now fixed, including bugs that turned out to affect the widely-used LLVM compiler framework [I10]. GraphicsFuzz has also been used to find defects in the open-source Mesa drivers for Intel and NVIDIA GPUs [I11].
Tools for the Vulkan ecosystem. GraphicsFuzz has found more than 100 bugs collectively in a suite of tools that underpin the Vulkan graphics programming model: the glslang shader translator, the spirv-opt and spirv-val optimizer and validator that ship as part of the SPIRV-Tools framework, and the spirv-cross cross-compiler [I12].
Integration with Vulkan CTS. Every Vulkan driver must pass the Vulkan Conformance Test Suite (CTS), which now features a new graphicsfuzz test group, comprising tests generated by GraphicsFuzz that exposed bugs in previously-conformant Vulkan drivers. Adding these tests to the Vulkan CTS requires fixes to any defective drivers in order for them to remain conformant. The Vulkan CTS now features more than 300 GraphicsFuzz tests [I13].
Impact of GPUVerify on ARM. The collaboration between Imperial College London and ARM during the CARP EU project (coordinated by Donaldson) led to ARM integrating GPUVerify into their Mali Graphics Debugger [I14]. Leveraging fundamental results on how to scale analysis to thousands of parallel threads [R1, R2], this allows software developers targeting ARM’s Mali GPU series – which leads the smartphone and tablet GPU market – to reason rigorously about the OpenCL programs that they write.
Impact of CLsmith on OpenCL compilers. The Imperial team who developed CLsmith initially used it to find more than 50 bugs in OpenCL compilers from companies including Altera, AMD, ARM, NVIDIA and Intel [R3, R4]. CLsmith has been used by Codeplay Software Ltd., a UK-based compiler company, for continuous integration of their OpenCL compilers; see letter of support from Codeplay’s Principal Software Engineer, AI Parallelism [I15]. Via a TETRACOM technology transfer project, CLsmith has since been incorporated into the set of tools used by UK-based start-up company dividiti for analysis of many-core platforms [I16].
Beneficiaries of the impact: The immediate beneficiaries of GPUVerify, CLsmith and GraphicsFuzz are GPU technology developers, who are now able to construct more reliable software and drivers as a result of the impact of these tools. End users of computer systems (i.e. the general public) are ultimately beneficiaries due to more reliable applications that use computer graphics.
Nature of the impact: By finding bugs in GPU technology automatically, these tools (a) reduce the manual effort required for GPU quality assurance, (b) increase test rigour by finding defects that human testers would be unlikely to uncover, and (c) increase the coverage of graphics driver compatibility test suites.
5. Sources to corroborate the impact
See letter of support from the Director of Engineering, Graphics and Gaming, at Google.
Apple: “ About the security content of Safari 10.1” (link archived here) March 2017. (Search for “GLFuzz” for confirmation of the claim that GraphicsFuzz (then called GLFuzz) found a security vulnerability affecting iOS. Filed as CVE-2017-2424 (link archived here).)
Nvidia: “Security Bulletin: NVIDIA GPU display driver contains multiple vulnerabilities in the kernel mode layer handler”, July 2017. (Search for “Alastair Donaldson” for confirmation of the claim that GraphicsFuzz found a security vulnerability affecting NVIDA graphics drivers. Filed as CVE-2017-6259.) Link archived here.
bugs.chromium.org: “ Issue 675658: Security: Malicious WebGL page can capture and upload contents of other tabs”, December 2016. (Supports claim that GraphicsFuzz (then called GLFuzz) uncovered a security vulnerability affecting the Chrome web browser.) Link archived here.
phoronix.com: “ Fuzzing OpenGL Shaders Can Lead To Some Wild Results”, December 2016. (Supports claim about press coverage of blog posts.) Link archived here.
Imperial College : “GraphicsFuzz Acquired by Google”, August 2018. (Supports claim that GraphicsFuzz Ltd. was an Imperial College spinout acquired by Google.) Link archived here.
Examples of users tweeting results from the GraphicsFuzz web app: 1, 2, 3, 4, 5, 6, 7, 8. (Supports claim of the app’s existence and the public’s engagement.) PDF of the Tweets available here.
GraphicsFuzz on GitHub: https://github.com/google/graphicsfuzz. (Supports claim that Google open-sourced the GraphicsFuzz tool.) Link archived here.
Security bugs found by GraphicsFuzz that affected Chrome and have now been fixed for sufficiently long that Google have made them public. Link archived here.
Impact on open-source AMD driver: example bugs in the widely-used LLVM framework that affected AMD’s driver and that have been fixed 1, 2, 3, 4; other bugs that affected AMD’s driver and have been fixed: 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17. PDF available here.
Impact on open-source Mesa drivers: example bugs in Intel Mesa driver: 1, 2, 3, 4; example bugs in Nouveau open source NVIDIA driver: 1, 2. PDF available here.
Impact on the Vulkan tooling ecosystem: bugs in SPIRV-Tools, bugs in SPIRV-Cross, bugs in glslang all found by GraphicsFuzz. Link archived here.
Impact on Vulkan Conformance Test Suite: GraphicsFuzz tests that have been added to the Vulkan CTS. Link archived here.
S. Barton: “ Debugging OpenCL Applications with Mali Graphics Debugger V2.1 and GPUVerify”, April 2015. (Supports claim that GPUVerify has been integrated into the ARM Mali Graphics Debugger.) Link archived here.
See letter of support from the Principal Software Engineer, AI Parallelism, at Codeplay Software Ltd.
Exploitation of compiler testing work from Imperial College London is listed on the Success Stories page of the dividiti Ltd. website. Link archived here.
- Submitting institution
- Imperial College of Science, Technology and Medicine
- Unit of assessment
- 11 - Computer Science and Informatics
- Summary impact type
- Technological
- Is this case study continued from a case study submitted in 2014?
- No
1. Summary of the impact
Infer is an open-source static analysis tool for finding memory-safety bugs in Java, C++ and Objective-C code bases. It is based on fundamental advances in automated program reasoning made by Cristiano Calcagno (Imperial College London), Dino Distefano (Queen Mary, University of London), and collaborators between 2005 and 2011. In 2009, Calcagno and Distefano founded start-up company Monoidics to commercialise Infer. Infer and its development team were acquired by Facebook in 2013 for an undisclosed sum, with the team extending the tool to cater to large-scale use. As described in a recent Communications of the ACM article, Infer now runs continuously on the millions of lines of code underlying the apps and back-end servers of Facebook, Instagram and WhatsApp. It also has many users in government and industry, such as the National Cyber Security Centre (NCSC), Amazon, Mozilla, Spotify, Uber, Freefem, JD.com, Marks and Spencer, Sky, OLA, Vuo, CodeAI and Tile. Infer finds reliability and security bugs, typically within minutes of their introduction so that they can be rapidly fixed. As a direct result of the basic research underpinning this case study, Infer has led to more than 100,000 bugs in the Facebook, Instagram and WhatsApp code bases being found and fixed before they reached production, including many security-critical bugs that would otherwise have potentially affected billions of users.
2. Underpinning research
Nature of the research insights and findings relating to the impact: In a series of research papers between 2006 and 2011, Cristiano Calcagno at Imperial College London and collaborators developed fundamental theory, efficient algorithms and tools for reasoning about software at an industrial scale. Almost all software used in industry manages memory using pointers. However, pointer-manipulating programs suffer from difficulties posed by aliasing, where a program can access common regions of memory via many pathways. This makes it hard to reason about a program’s behaviour: a modification to memory made by one part of the program may end up – due to aliasing – influencing seemingly unrelated parts of the program. In 2001, separation logic was proposed as a new theory to aid in the reasoning about pointer-manipulating programs. At first, it was used solely for pencil-and-paper reasoning; it was unclear whether it would be possible to create automated tools to analyse programs using separation logic, and whether such tools would have any hope of scaling to real world industrial systems.
Calcagno and collaborators demonstrated in their papers and tools that scalable reasoning is possible using abstract symbolic execution, a static analysis technique that reasons about the behaviour of a program for all potential inputs simultaneously and can thus establish a proof that the program is correct, or demonstrate that the program contains bugs related to memory safety. This line of research culminated in a Journal of the ACM paper [R6, 2011], showing that reasoning can be made to scale to very large code bases through a new technique called bi-abduction. Bi-abduction allows the analysis of a large code base to be broken down into many mini-analyses, one per procedure of the program. This (a) decouples the scalability of analysis from the overall code base size, and (b) allows analysis re-use: when a developer changes a small part of a large code base, only the procedures actually relevant to the change must be re-analysed. The Journal of the ACM paper is an extended version of a POPL 2009 conference paper that introduced bi-abduction and won the POPL Ten-Year Test-of-Time award.
Outline of underpinning research, and associated dates: The research was conducted between 2005 and 2011. The first academic semi-automated reasoning tool for pointer-manipulating programs, using abstract symbolic execution based on separation logic, was Smallfoot [R1, 2005]. This led to extensions to the theory to support pointer arithmetic, common in C-family languages [R2, 2006]. The problems with Smallfoot were that users had to annotate all functions with preconditions, and that it only worked with simple data structures, e.g., linked lists. This was partly mitigated by precondition discovery [R3, 2007] and work on composite data-structure reasoning [R4, 2007]. Now the method could be used to analyse thousands of lines of code for the first time, including Microsoft device drivers [R5, 2008]. The industrial breakthrough came in 2009 with the introduction of bi-abduction for highly automated inference of function preconditions [R6, 2011] (an extension of the POPL 2009 paper that introduced bi-abduction). The combination of abstract symbolic execution and bi-abduction unlocked scalability to millions of lines of code and has enabled Infer’s widespread industrial impact.
Bi-abduction is at the heart of the Infer tool that forms the basis of this case study: the large-scale roll-out of Infer at Facebook has involved engineering work to optimise the tool, but the core analysis engine remains a faithful realisation of the basic fundamental research introduced in [R1–R6], while Calcagno was working full time at Imperial.
3. References to the research
Josh Berdine, Cristiano Calcagno, Peter W. O'Hearn: Smallfoot: Modular Automatic Assertion Checking with Separation Logic. FMCO 2005: 115-137. Google Scholar cites: 474. DOI: 10.1007/11804192_6.
Cristiano Calcagno, Dino Distefano, Peter W. O'Hearn, Hongseok Yang: Beyond Reachability: Shape Abstraction in the Presence of Pointer Arithmetic. SAS 2006: 182-203. Google Scholar cites: 74. DOI: 10.1007/11823230_13.
Cristiano Calcagno, Dino Distefano, Peter W. O'Hearn, Hongseok Yang: Footprint Analysis: A Shape Analysis That Discovers Preconditions. SAS 2007: 402-418. Google Scholar cites: 60. DOI: 10.1007/978-3-540-74061-2_25.
Josh Berdine, Cristiano Calcagno, Byron Cook, Dino Distefano, Peter W. O'Hearn, Thomas Wies, Hongseok Yang: Shape Analysis for Composite Data Structures. CAV 2007: 178-192. Google Scholar cites: 271. DOI: 10.1007/978-3-540-73368-3_22.
Hongseok Yang, Oukseh Lee, Josh Berdine, Cristiano Calcagno, Byron Cook, Dino Distefano, Peter W. O'Hearn: Scalable Shape Analysis for Systems Code. CAV 2008: 385-398. Google Scholar cites: 308. DOI: 10.1007/978-3-540-70545-1_36.
Cristiano Calcagno, Dino Distefano, Peter W. O'Hearn, Hongseok Yang: Compositional Shape Analysis by Means of Bi-Abduction. J. ACM 58(6): 26:1-26:66 (2011). Extended version of POPL 2009 paper. Google Scholar cites (J. ACM and POPL paper combined): 531. DOI: 10.1145/2049697.2049700.
4. Details of the impact
The impact arising from this research during the REF period of 1 August 2013 and 31 December 2020 is related to Facebook acquiring Infer, a start-up company and software tool based on the fundamental research described above, and the wide industrial adoption of the Infer tool. Facebook has integrated the Infer tool with their continuous development workflow, discovering and fixing a large number of bugs in products used by billions of users. After making the technology available as open source, there has been broad adoption by companies across the whole software industry.
Background to the Facebook acquisition. Based on the success of the foundational research described above for enabling scalable reasoning about pointer-manipulating programs, Calcagno and Distefano (based at Imperial College London and Queen Mary University of London, respectively) incorporated a start-up company, Monoidics Ltd. (company no. 06805518), in January 2009, as directors. They developed the Infer tool, an implementation of the line of research (papers R1 – R6 above) that culminated in the Journal of the ACM article [R6]. Monoidics was funded by Quantum Wave Capital, received support from the CARP EU FP7 project (led by Imperial College London), and reported ARM, Airbus and Mitsubishi Electric as customers. In July 2013, Facebook acquired the assets of Monoidics for an undisclosed sum and hired the engineering team, including Calcagno [I1]. Calcagno has since worked as a Software Engineer at Facebook, remaining a Lecturer on Leave of Absence at Imperial until 2017, and now retains his connection with Imperial as an Honorary Lecturer.
Impact of Infer at Facebook. Facebook integrated Infer into its perpetual software development process [I2]. As a result, Infer is now used to continuously analyse the multi-million-line code bases of both mobile apps and back-end services at Facebook, as well as the software associated with WhatsApp and Instagram [I3]. Each time a developer commits any code change, Infer analyses the change and participates in the code review process, indicating potential memory safety problems that the programmer may have overlooked. This is possible due to the scalability afforded by bi-abduction [R6]: only the procedures related to the code change must be re-analysed, meaning that analysis can complete within minutes, providing a report of potential problems while the code changes are fresh in the mind of the developer.
At a talk at Imperial College London in 2015, Facebook CTO Mike Schroepfer said about Infer: “It’s a really key component of being able to build an app and ship it weekly to a billion people. If you want to do this without everything grinding to a halt, it’s really helpful to have a system that automatically detects and helps with bugs” [I4]. In a 2019 Communications of the ACM article, Facebook explains that Infer now runs continuously on millions of lines of code, and that so far more than 100,000 bugs found by Infer have been fixed before affecting end users. It reports a high fix rate of 70% associated with memory safety bugs flagged by Infer [I3].
The high degree of impact that Infer continues to have, and its underpinning by the original research of Calcagno et al., is summed up well in the letter from Facebook’s Director of Engineering [I5]: “Today within Facebook, the verification technology originally designed by Prof Dino Distefano, Dr Cristiano Calcagno and colleagues contributes to the quality of the products we serve to over 2 billion people every day. Currently Infer analyses every applicable code change within Facebook and its family of apps (Messenger, WhatsApp, Instagram, Oculus). Every month, thousands of issues are fixed before these apps are shipped to users. Thus, Infer has saved Facebook engineers innumerable hours that they would have had to spend debugging the problems it detected, had those problems reached production.”
The significance of the link between the fundamental research and its impact was recognised by the Infer team receiving the prestigious 2016 CAV Award, which “recognizes their contribution to the development of Separation Logic, the theory that underpins the Infer static analyser”.
Impact of Infer beyond Facebook. Infer was made open source in 2015 [I6], making it available to other companies. The open source repository is very active (>150 contributors) and popular (starred by >12,000 GitHub users, forked >1,600 times). Companies who have publicly acknowledged using Infer include Amazon Web Services, Mozilla, Oculus, Spotify, Uber, Freefem, JD.com, Marks and Spencer, Sky, Money Lover, LA, Netcetera, Vuo, CodeAI, and Tile [I7]. The National Cyber Security Centre (NCSC, part of GCHQ) also uses Infer. We detail here the four most significant uses of Infer in industry and government beyond Facebook: by Spotify, Uber, Muse Dev (a recent start-up company), and NCSC.
Spotify: The Android Infrastructure team at Spotify have extended Infer in order to incorporate it in their continuous integration process for Android. In an article describing the collaboration [I8], A Spotify engineer writes: “In our quest to make our code even better, we started using Infer. Infer found several legitimate issues that other tools had missed. The Infer team was also very helpful in following a few false positives that we encountered, and we now have it running on our build servers.”
Uber: Uber have reported using Infer in a portfolio of tools for static detection of null pointer exceptions, claiming that this endeavour “reduced the number of NPEs observed in our apps in production by an order of magnitude” [I9].
MuseDev: A spin-off company from Galois, MuseDev is a new company providing tools and services for automated code reasoning. As detailed further in the supporting letter from MuseDev CEO [I10], MuseDev runs a cloud-based code analysis service that uses Infer as its flagship analyser: “Via Muse, Infer is now running daily in the cloud on several open source repositories. And we are actively working with a variety of enterprises to deploy and run MuseDev in their environments, including Fortune 500 and fast-growing venture-backed technology companies.” The “cool math” link on the MuseDev website is to a review article on separation logic, with a section entitled “Bi-Abduction and Facebook Infer” that indicates the importance of the underpinning research. Magill further stresses the breakthrough nature of this research: “The technology developed at Imperial and Queen Mary ushered in a new wave of static analysis, capable of finding subtle and important bugs while running quickly enough to fit into modern agile development workflows. In fact, in talking with customers, we often use the terms ‘first wave’ and ‘second wave’ to distinguish just how different these techniques are from what came before.”
National Cyber Security Centre (NCSC): This case study is accompanied by a confidential letter from the Head of High Assurance Engineering Research at NCSC (available to reviewers of the case study), outlining the use of Infer by NCSC and the significance of the fundamental research on which Infer is based [I11].
Beneficiaries of the impact: The companies that use Infer are direct beneficiaries of the impact: 18 large organisations publicly advertise that they use the tool [I7], and the open source. The improvement in software quality afforded by Infer is to the benefit of the users of the products that these companies build. Facebook alone report that Infer has led to more than 100,000 fixed bugs in the Facebook, WhatsApp and Instagram code bases [I3].
Nature of the impact: Software bugs are expensive: a report from the Consortium for IT Software Quality (CISQ) estimates that the cost of poor-quality software in the US alone is USD2.84 trillion. By finding bugs early during the software development process, Infer helps reduce these costs, leading to major economic impact. Billions of people worldwide depend on products developed by the companies that use Infer. The large number of software defects in these products that have been fixed during development, after identification by Infer, and that would otherwise have reached production to the detriment of end users is evidence of the broad societal nature of the impact [I3].
5. Sources to corroborate the impact
Techcrunch.com: “ Facebook Acquires Assets Of UK Mobile Bug-Checking Software Developer Monoidics”, July 2013. (Supports the claim that Facebook acquired the Monoidics technology and hired the team.) Link archived here.
C. Calcagno et al.: “Moving Fast with Software Verification”. Proc. NASA Formal Methods (NFM), 2015. DOI: 10.1007/978-3-319-17524-9_1. (Supports the claim that Infer is integrated into Facebook’s perpetual software development process, and reinforces the underpinning of [R1] and [R6].) PDF available here.
D. Distefano et al.: “Scaling Static Analyses at Facebook”. Commun. ACM 62(8): 62-70, 2019. DOI: 10.1145/3338112. (Supports claims that a 70% “fix rate” for issues reported by Infer has been achieved, and that the use of Infer has led to more than 100,000 bugs being fixed in Facebook, WhatsApp and Instagram code bases.) PDF available here.
Jon Narcross: “ Facebook chief gives Imperial sneak peek into tech future”, November 2015. (Supports the claim that Infer is used widely by Facebook.) Link archived here.
Letter from Director of Engineering at Facebook, confirming the extent of the impact associated with their use of Infer and emphasising that it is a direct result of basic research that underpins this case study.
Infer on GitHub: https://github.com/facebook/infer. (Supports claim that Facebook open-sourced Infer and that the project is highly active, with many forks/stars and contributors.) Link archived here.
Facebook’s Infer web page (Link archived here) and research page on Infer (Link archived here) insists companies who self-identify as using Infer. (Supports claim that several companies outside Facebook use Infer.)
J. Villard: “ Collaboration with Spotify”, fbinfer.com, March 2016. (Supports the claim that Spotify are using Infer.) Link archived here.
M. Sridharan: “ Engineering NullAway, Uber’s Open Source Tool for Detecting NullPointerExceptions on Android”, Uber Engineering, October 2017. (Supports the claim that Uber used Infer to reduce null pointer exceptions by an order of magnitude.) Link archived here.
Letter from CEO of MuseDev, confirming the extent of the impact associated with their use of Infer and emphasising that it is a direct result of basic research that underpins this case study.
Confidential letter from the NCSC Head of High Assurance Engineering Research, detailing the use of Infer by NCSC and emphasising the importance of the research on which Infer is based, available to reviewers of this case study.
- Submitting institution
- Imperial College of Science, Technology and Medicine
- Unit of assessment
- 11 - Computer Science and Informatics
- Summary impact type
- Technological
- Is this case study continued from a case study submitted in 2014?
- Yes
1. Summary of the impact
The automated image analysis techniques developed at Imperial College are now widely used for the quantitative interpretation of brain Magnetic Resonance (MR) images as part of clinical trials advancing the development of new drugs and in improving healthcare diagnostics for neurological diseases such as Alzheimer’s, Huntingdon’s and Parkinson’s. This case study describes the resulting key impacts including:
the further development of a spin-off company, IXICO, co-founded by researchers from Imperial College, including its admission on AIM and its growth from 36 to 78 employees;
the use of automated image analysis techniques and imaging biomarkers in more than 2,000 imaging centres (increased from 400) in 50+ countries;
the increase in analysis from 10,000 to over 100,000 brain MR images in clinical trials using the developed image analysis techniques.
2. Underpinning research
The underpinning research has been carried out in the Biomedical Image Analysis (BioMedIA) Group at Imperial College between 2000 and 2012.
Much of the early work of the group has addressed one of the fundamental problems in computer vision and medical image computing, namely the problem of image registration. The goal of image registration is to find an automatic transformation between points in two or more images. For the transformation to be meaningful, it must map corresponding points across coordinate systems. If the transformation sought is rigid, the problem is relatively straightforward to solve, as the number of unknowns is small (typically 3 in 2D and 6 in 3D). In contrast, if the required transformation is non-rigid, the problem becomes substantially more challenging because the degree of freedom is much higher (typically in the order of hundreds of thousands, or even millions). In practical medical and clinical applications, non-rigid registration, however, is crucial to compensate for intra-subject variation (e.g., tissue deformation, respiratory or cardiac motion) as well as for inter-subject variation.
In 2001, Rueckert and his colleagues developed a solution to this problem that is based on a flexible and versatile deformation model using B-spline free-form deformations [R1]. This approach is capable of registering mono-modal and multi-modal images, and it was the first to adopt the use of adaptive, hierarchical B-spline free-form deformations that offer the ability to deal with complex deformations. This developed solution has been widely adopted: in a recent comparison study, it has been shown to be amongst the most accurate solutions for this problem [R2]. In 2006, Rueckert’s group proposed an improved solution to the registration problem that uses a diffeomorphic deformation to allow the modelling of very large deformations, which occur when registering the images of different subjects [R3].
The ability of these image registration techniques to handle very large deformations has also led Rueckert’s group to develop novel solutions to the classical problem of image segmentation, which is based on image registration. As part of the EPSRC-funded IXI [i] and IBIM [ii] projects, they have pioneered the use of non-rigid registration of multiple atlases followed by vote or label fusion for the automatic segmentation of images [R4]. Standard atlas-based segmentation uses image registration to transfer anatomical information from an atlas to new, unseen images. In contrast to this, multi-atlas segmentation [R4] uses multiple atlases and registrations followed by machine learning approaches, such as decision fusion, to provide a consensus estimate of the segmentation. This approach provides a much more robust and accurate segmentation of medical images. It has become the de-facto standard solution for medical image segmentation in many applications (as shown by the large number of citations), in particular for neurological, abdominal, and cardiac images. The name of the research project in [i] (“IXI”) has inspired the name of the resulting spin-off company (“IXICO” – see Section 4 for details).
In the EU FP7 PredictAD project [iii], the team further developed the methodology described above to enable the robust and accurate extraction of imaging biomarkers, in particular in the context of neurodegenerative diseases such as dementia. For example, this methodology allows the accurate measurement of hippocampal volume [R5] and volume loss [R6].
3. References to the research
J. A. Schnabel, D. Rueckert, M. Quist, J. M. Blackall, A. D. Castellano Smith, T. Hartkens, G. P. Penney, W. A. Hall, H. Liu, C. L. Truwit, F. A. Gerritsen, D. L. G. Hill, and D. J. Hawkes. A generic framework for non-rigid registration based on non-uniform multi-level free-form deformations. In Fourth Int. Conf. on Medical Image Computing and Computer-Assisted Intervention (MICCAI), pages 573–581, 2001. (>490 citations, Google Scholar). http://dx.doi.org/10.1007/3-540-45468-3_69
A. Klein, J. Andersson, B. A. Ardekani, J. Ashburner, B. Avants, M.-C. Chiang, G. E. Christensen, D. L. Collins, J. Gee, P. Hellier, J. H. Song, M. Jenkinson, C. Lepage, D. Rueckert, P. Thompson, T. Vercauteren, R. P. Woods, J. J. Mann, R. V. Parsey. Evaluation of 14 nonlinear deformation algorithms applied to human brain MRI registration. Neuroimage, 46(3):786-802, 2009. (>2090 citations, Google Scholar) http://dx.doi.org/10.1016/j.neuroimage.2008.12.037
D**. Rueckert, P. Aljabar, R. Heckemann, J. Hajnal** and A. Hammers. Diffeomorphic Registration using B-Splines. In Ninth Int. Conf. on Medical Image Computing and Computer-Assisted Intervention (MICCAI), pages 702-709, 2006. (>350 citations, Google Scholar). http://dx.doi.org/10.1007/11866763_86
R. A. Heckemann, J. V. Hajnal, P. Aljabar, D. Rueckert and A. Hammers. Automatic anatomical brain MRI segmentation combining label propagation and decision fusion. NeuroImage, 33(1):115-126, 2006 (>980 citations, Google Scholar). http://dx.doi.org/10.1016/j.neuroimage.2006.05.061
R. Wolz, P. Aljabar, J. V. Hajnal, A. Hammers, D. Rueckert and the Alzheimer's Disease Neuroimaging Initiative. LEAP: Learning embeddings for atlas propagation. NeuroImage, 49(2): 1316-1325, 2010 (>250 citations, Google Scholar). Patent filed US2012/281900 A1 and exclusively licensed to IXICO. http://dx.doi.org/10.1016/j.neuroimage.2009.09.069
R. Wolz, R. A. Heckemann, P. Aljabar, J. V. Hajnal, A. Hammers, J. Lötjönen, D. Rueckert and The Alzheimer's Disease Neuroimaging Initiative. Measurement of hippocampal atrophy using 4D graph-cut segmentation: Application to ADNI. NeuroImage, 52(1): 109-118, 2010 (>140 citations, Google Scholar). Patent filed US2012/281900 A1 and exclusively licensed to IXICO. http://dx.doi.org/10.1016/j.neuroimage.2010.04.006
4. Details of the impact
The underpinning research has led to the development of novel imaging biomarkers that are now routinely used in clinical trials to assess the efficacy of new drugs and treatments. The biomarkers are also used in healthcare diagnostics, e.g., for dementias such as Alzheimer’s disease (AD).
Economic impact
To maximise the economic impact of the research, a team of Imperial researchers (Rueckert, Hajnal) started IXICO with colleagues from UCL (Hawkes, Hill) in late 2004. In the assessment period for the 2014 REF, IXICO had been established and grown organically. In the current REF assessment period, several new key impacts occurred: in particular, in October 2013, it became IXICO plc and is now listed on the Alternative Investment Market (AIM) of the London Stock Exchange (date: 15th October 2013). Other impact measures are listed in the table below and compared to the status at the beginning of the assessment period:
Key impact metrics | 2012/13 | 2020 |
---|---|---|
Turnover | GBP2,500,000 | GBP9,500,000 |
Employees | 36 | 78 |
Imaging centres | 400 | 2,000+ |
Images analysed | 10,000 | 100,000+ |
Safety and eligibility reports | n/a | 20,000+ |
Since the start of the assessment period, IXICO has grown from 36 to 78 employees. IXICO’s revenues have increased from GBP2,500,000 to more than GBP9,500,000. IXICO has become a profitable business and, since 2014, has won more than GBP36,200,000 in business from the global pharmaceutical industry (GSK, Pfizer, Bristol-Myers Squibb, Novartis, Eli Lily). Its orderbook for 2020 is GBP21,700,000 alone. IXICO’s image analysis technology is based on the underpinning research described in Section 2 and has been transferred from Imperial during IXICO’s formation and later as part of an IP pipeline agreement with Imperial. It has been, and/or is currently being used to analyse tens of thousands of medical images collected from a total of more than 2,000 imaging centres across North America, Latin America, Europe, Asia and Australasia (in over 50 countries) [I1, I2, I3]. Since 2013, IXICO has been involved in over 50 clinical trials and analysed brain images from more than 100,000 subject visits using its image analysis technology [I2].
Originally, IXICO had focused on applying its image analysis technology to supporting clinical trials of novel therapies to treat Alzheimer’s disease. Since the beginning of the REF assessment period, IXICO has successfully translated the technology to other neurological diseases, including Huntington’s disease, Parkinsonian diseases (such as PD, PSP and MSA), Multiple Sclerosis and rare neurological diseases. In particular, IXICO has had much success in the Huntington’s disease (HD) clinical trials market, having built the requisite therapeutic expertise and validated the technology specifically for measuring imaging biomarkers that are correlated with disease pathology and progression in HD. Since 2014, IXICO has been selected for 10 clinical trials in HD, 7 of which were started over the past 4 years since 2016 and includes the world’s first phase III trial in Huntington’s disease for a gene therapy approach that targets the mutant Huntington gene [I1].
The developed image analysis techniques also provide an important tool in clinical trials to assess the safety and efficacy of new drugs as well as for enrichment of clinical trials, i.e., as inclusion/exclusion criteria. This enrichment of trials enables the reduction of heterogeneity of the population providing additional power for clinical trials, therefore increasing the sensitivity of trials to detect disease-modifying effects of drugs. Since 2013, IXICO has used the automated image analysis techniques for safety and eligibility reports in over 20,000 cases [I2].
Impact on public policy and services
The techniques for automatically computing imaging biomarkers such as low hippocampal volume have had a significant impact on informing the development of new guidelines in regulatory clinical trials. This has been recognised, e.g., by the Coalition Against Major Diseases (CAMD) consortium by submitting to regulators an application to qualify low hippocampal volume as a biomarker [I4, I5]. This submission – supported by the US Federal Drug Administration – incorporates key data obtained using the underpinning research described here: the availability of this technology, with the regulatory qualification, is having a global impact on the design of future trials of AD medicines in the pre-dementia population. Furthermore, IXICO is also part of key public/private partnerships that are advancing the scientific and regulatory agenda for clinical trials in neurological diseases. These include:
EPAD (the European Prevention of Alzheimer’s Dementia; http://ep-ad.org) – which has built an adaptive clinical trials platform with a readiness cohort of people at risk of Alzheimer’s disease and which will enable pharma companies to evaluate efficiently the safety and effectiveness of their medicines in patients prior to onset of symptoms by utilising adaptive clinical trial approaches. IXICO received over EUR600,000 in grant funding to provide the technology to collect, manage and analyse MRI scans.
AMYPAD (Amyloid Imaging for Prevention of Alzheimer’s Dementia, https://amypad.eu) – which is evaluating the diagnostic value of amyloid imaging in the diagnosis of Alzheimer’s disease. IXICO received over EUR1,000,000 in grant funding to provide the technology to collect, manage and analyse MRI and PET scans.
HD-RSC (Huntington’s Disease Regulatory Science Consortium, https://c-path.org/programs/hdrsc/) – which is developing regulatory-endorsed drug development tools to support the development and approval of new medicines to treat HD and involves representatives from the FDA. IXICO is contributing to the regulatory clearance of imaging biomarkers.
CPP (Critical Path for Parkinson’s, https://c-path.org/programs/cpp/) – which is developing regulatory-endorsed drug development tools to support the development and approval of new medicines to treat Parkinson’s disease and involves representatives from the FDA. IXICO is contributing to the development of a regulatory-endorsed digital outcome measure for Parkinson’s disease.
Beneficiaries of the impact
The beneficiaries are pharmaceutical companies developing new drugs and therapies for neurodegenerative diseases such as Alzheimer’s or Huntington’s disease through improved efficacy and safety of clinical trials. Furthermore, patients are benefitting from improved imaging-based diagnostics and therapeutics.
Nature of the impact
IXICO’s image analysis techniques provide an important tool in clinical trials to assess the safety and efficacy of new drugs as well as for enrichment of trials, enabling the reduction of heterogeneity of the population. The image analysis techniques provide increased sensitivity to detect disease-modifying effects of drugs and trials. This means that fewer patients need to be recruited into trials, leading to significant cost savings for pharma companies. IXICO has also supported clinical trials of novel therapies relating to neurological diseases and contributed to new guidelines for biomarkers in regulated clinical trials.
5. Sources to corroborate the impact
Information for investors about IXICO https://ixico.com/investors/company-information/rns-news/ Link archived here.
IXICO Annual Report and Accounts 2019: pages 2, 8. https://ixico.com/assets/IXICO-financial-documents/IXICO-Annual-Report-2019-2.pdf Link archived here.
IXICO Annual Report and Accounts 2020: pages 1, 10, 14, 15, 29. https://ixico.com/assets/IXICO-plc-Annual-Report-2020-v2.pdf Link archived here.
D. L. G. Hill et al. Coalition Against Major Diseases/European Medicines Agency biomarker qualification of hippocampal volume for enrichment of clinical trials in predementia stages of Alzheimer's disease. Alzheimer's & Dementia: The Journal of the Alzheimer's Association. 10(4): 421 - 429.e3, 2014. https://doi.org/10.1016/j.jalz.2013.07.003 PDF available here.
Letter of Support by the Director, Centre for Drug Evaluation and Research, FDA, USA. https://c-path.org/wp-content/uploads/2018/03/3.10.2015_letter_of_support.pdf
- Submitting institution
- Imperial College of Science, Technology and Medicine
- Unit of assessment
- 11 - Computer Science and Informatics
- Summary impact type
- Technological
- Is this case study continued from a case study submitted in 2014?
- No
1. Summary of the impact
Vision-based Simultaneous Localisation and Mapping (SLAM) is a fundamental and broadly applicable technology in AI that enables devices to operate intelligently by mapping the general unstructured world using low-cost cameras and efficient on-board processing. The Imperial team have made a sequence of highly influential advances in SLAM algorithms: (i) sparse visual feature-based mapping enables drift-free long-term 3D localisation; (ii) dense scene mapping provides detailed scene modelling; and (iii) semantic mapping brings object understanding into maps. These new algorithms have been harnessed in worldwide consumer products as key enabling features of Dyson’s first ever robotic products, the Dyson 360 Eye and Heurist robot vacuum cleaners. SLAM is also used in augmented reality headsets to track and map surroundings, and Imperial’s algorithms have contributed to both Microsoft’s ongoing Kinect and Hololens products as well as systems at Facebook/Oculus via the acquisition of Imperial’s start-up Surreal Vision for USD40,000,000. A second Imperial spinout, SLAMcore, has received over GBP7,000,000 of investment to date, employs >20 people, and commercialises Imperial’s SLAM software for broader robotics applications.
2. Underpinning research
Research progress in vision-based SLAM can be understood in terms of interacting layers of capability in a software stack for vision applications, and Davison and Leutenegger have worked for over 15 years at the forefront of research across this stack. Their research work has enabled low-cost real-time spatial intelligence for a new generation of consumer devices.
Davison’s seminal work on the MonoSLAM algorithm [R1] was the first demonstration of real-time SLAM with a single camera. Incremental probabilistic filtering for scene mapping had previously been shown in robotics only using specialised and expensive sensors, such as laser range-finders. MonoSLAM’s innovation in sparse active feature search, 3D dynamics modelling and sampling-based landmark initialisation proved that probabilistic 3D SLAM was possible with a low-cost standard camera, opening up new commercial applications in mass-market products. MonoSLAM builds a persistent 3D sparse landmark map of an unknown environment in real-time and uses it to enable drift-free long-term localisation. Davison’s research results in Inverse Depth Feature Representation [R2] improved feature initialisation, especially in large or outdoor scenes. These methods are now at the heart of the SLAM system in Dyson’s 360 Eye robotic product and inspired other companies to develop visual SLAM systems for robotics. Sparse visual SLAM for device tracking is also critical in the exploding field of augmented reality (AR) on smartphones or mobile headsets. MonoSLAM initiated a huge research interest and commercial focus in this area, as indicated by the high number of citations to papers from the Imperial team and the investment of companies such as Dyson and Facebook.
The next level in SLAM is dense scene mapping, which uses extra processing and diverse camera hardware to capture detailed 3D scene information for planning, obstacle avoidance and scene augmentation. The Imperial team’s collaboration with KinectFusion [R3] and their work on DTAM [R4] resulted in pioneering algorithms using parallelisable optimisation methods that run on GPU hardware to enable real-time dense scene mapping for the first time. KinectFusion was the first SLAM algorithm that was integrated with Microsoft’s new Kinect consumer-level depth camera for robotics and AR. DTAM showed that detailed real-time scene reconstruction can be achieved even with a regular single camera and that camera tracking can be robust without features via whole image alignment. Dense SLAM for AR has been commercialised by the Imperial team through the co-founding of Surreal Vision, which was subsequently acquired by Oculus/Facebook.
Finally, the Imperial team’s work on SLAM++ [R5] and SemanticFusion [R6] led to key advances with respect to the challenge of adding a semantic layer to SLAM so that robots and other devices can understand the identities of scene entities as well as their geometry. The research on SLAM++ showed that real-time 3D object detection allows an “instance-level” graph of key objects in a scene to be built and optimised – the objects themselves becoming high-quality sparse landmarks. For the first time, SemanticFusion enabled the output from a convolutional neural network (CNN) trained for image segmentation to be fused incrementally into a dense SLAM map that supports full pixel-wise semantic labelling of a scene. Semantic scene understanding has proven crucial for applications that require intelligent interaction between a robot and its environment (e.g., for manipulation, or task and motion planning) and between a user and a robot (e.g., via natural language queries).
3. References to the research
MonoSLAM: Real-Time Single Camera SLAM. A. J. Davison, I. Reid, N. Molton and O. Stasse, IEEE Trans. Patten Analysis and Machine Intelligence (PAMI) June 2007, vol. 29, pp. 1952 – 1067. 3996 citations, Google Scholar. (Collaboration with University of Oxford.) https://www.doc.ic.ac.uk/~ajd/Publications/davison_etal_pami2007.pdf
Inverse Depth Parametrization for Monocular SLAM. J. M. M. Montiel, J. Civera and A. J. Davison, IEEE Trans. on Robotics Oct. 2008, 24(5), pp. 932 – 945. 844 citations, Google Scholar. (Collaboration with University of Zaragoza, Spain.) https://www.doc.ic.ac.uk/~ajd/Publications/civera_etal_tro2008.pdf
KinectFusion: Real-Time Dense Surface Mapping and Tracking. R. A. Newcombe, S. Izadi, O. Hilliges, D. Molyneaux, D. Kim, A. J. Davison, P. Kohli, J. Shotton, S. Hodges, and A. Fitzgibbon, Int. Symp. on Mixed and Augmented Reality (ISMAR) 2011, pp. 127 – 136. 3755 citations, Google Scholar (Collaboration with Microsoft Research, Cambridge.) https://www.doc.ic.ac.uk/~ajd/Publications/newcombe_etal_ismar2011.pdf
DTAM: Dense Tracking and Mapping in Real-Time. R. A. Newcombe, S. Lovegrove and A. J. Davison. Proc. IEEE ICCV, Nov. 2011. 1808 citations, Google Scholar. https://www.doc.ic.ac.uk/~ajd/Publications/newcombe_etal_iccv2011.pdf
SLAM++: Simultaneous Localisation and Mapping at the Level of Objects. R. F. Salas-Moreno, R. A. Newcombe, H. Strasdat, P. H. J. Kelly and A. J. Davison, IEEE Proc. CVPR, June 2013. 683 citations, Google Scholar. https://bit.ly/3rEQXFN
SemanticFusion: Dense 3D Semantic Mapping with Convolutional Neural Networks. J. McCormac, A. Handa, A. J. Davison, S. Leutenegger. Proc. IEEE ICRA, May 2017. 325 citations, Google Scholar. https://bit.ly/36V5t4x
4. Details of the impact
Impact on robotics products and R&D investment
Dyson product development: Davison worked as an academic consultant to Dyson until 2014 on the long-term project of developing their first robot product (Dyson 360 Eye), which makes direct use of the published algorithms in [R1, R2], and incorporates them into Dyson’s robotic vacuum cleaner development. He was responsible for guiding Dyson engineers to successfully design an omnidirectional visual SLAM system, which was the unique key feature (and thus chosen as the name) of the Dyson 360 Eye released worldwide in 2015. Dyson is one of few large UK companies to have a leading robotic product already on the market.
In 2018, Dyson’s second robotic product, the Dyson 360 Heurist [I2], which also incorporates Davison's core SLAM system, went on sale worldwide. The Principal Robotics Architect at Dyson states “ Andrew's pioneering research on vision-based SLAM in published algorithms such as MonoSLAM and Inverse Depth Features directly inspired the visual mapping system Dyson developed for the robot, based on a 360-degree panoramic camera. This enabled the robot to navigate precisely and repeatedly, and therefore clean rooms in a much more direct and efficient manner than other products on the market […] The core visual SLAM system developed for the 360 Eye with Andrew's input lives on in Dyson's latest and current robot vacuum cleaner, the Dyson 360 Heurist, which is now on sale worldwide” [I1].
In addition, Imperial’s SLAM research led to Dyson making large ongoing investments in robotics as a core focus of their business. At the start of Davison’s consultancy, the internal Dyson robotics team had fewer than 5 people, and now Dyson employs hundreds of scientists and engineers in robotics R&D in both the UK and Singapore [I1]. In 2020, Dyson announced a new investment of GBP3 billion specifically into AI, robotics and batteries [I9]. Since 2014, the Imperial team continues to collaborate closely with Dyson, who funded the Dyson Robotics Laboratory at Imperial directed by Davison and Leutenegger [I3]. The lab has produced over 10 patents for technologies selected by Dyson as relevant to their future robotics product lines.
Impact on augmented reality products and R&D investment
The Imperial research on sparse, dense and semantic SLAM has also directly impacted the augmented reality industry, specifically VR and AR products in headsets and smartphones, which need accurate but low-cost tracking and scene reconstruction from their on-board cameras. Major multi-billion dollar industry projects such as Facebook/Oculus’ VR/AR platforms, Microsoft Hololens, and Google’s ARCore have acknowledged that their algorithms used for sparse and dense mapping are derived from Imperial research work.
Google initiated Project Tango in 2013 to put SLAM into smartphones. In 2018, this technology was transitioned into ARCore, a major platform which enables developers to build AR applications for Android, now used in over 250 million devices worldwide, for functionality such as the AR walking directions feature of Google Mobile Maps. The Engineering Director at Google states [I11]: “ *Imperial College’s visual SLAM research led by Andrew Davison and Stefan Leutenegger was one of the initial inspirations behind Project Tango, going back to the first demonstration of real-time single camera MonoSLAM which showed the feasibility of vision-driven localisation and mapping using low-cost sensors. […] As the market for spatial aware computing evolves, research from Imperial College on SLAM and semantic understanding of the environment will continue to grow in demand. In my opinion, the impact of the technology will be similar to that of the Global Positioning System (GPS) which has transformed many existing industries, and made new ones possible. Wearables, smart home devices, vehicles, and robotics will all depend heavily on a shared understanding of physical space.*”
Surreal Vision acquisition: In 2013, Imperial PhD students (Newcombe, Lovegrove and Salas-Moreno) co-founded the AR company Surreal Vision, advised by Davison and Kelly, to commercialise the dense and object-based SLAM research in DTAM [R4] and SLAM++ [R5]. Based on this work, Surreal Vision developed a new level of accurate but efficient 3D reconstruction algorithms for VR and AR systems, able to provide a rich model of an environment including people and their interactions, but still running on modest consumer computing hardware. Surreal Vision was acquired for USD40,000,000 by Oculus (part of Facebook) in 2015 [I4]. The Surreal Vision team is now part of Facebook Reality Labs, a world leading industrial research team in AR for telepresence. Newcombe is Director of Research Science and leads a team of over 100 researchers which created the fundamental LiveMaps SLAM technology that originates from Imperial’s research. This is a key part of Facebook’s future technology plans for AR as a cloud platform for building, sharing and annotating always up-to-date scene maps across a multitude of user devices [I8].
Microsoft product development: Imperial’s SLAM work was incorporated in Microsoft’s Hololens AR headset product line through multiple stages. MonoSLAM [R1] directly impacted the development of Hololens’ core sparse visual tracking system [I5]. After that, in 2010, KinectFusion [R3], a collaboration between the Imperial team and Microsoft Research Cambridge, became a key Microsoft technology and is now part of Microsoft’s official Kinect for Windows SDK, which is used in millions of Kinect Sensors [I6]. KinectFusion also enables the dense mapping capabilities of Microsoft’s Hololens 1 (on sale in 2016) and Hololens 2 (released in 2019 and now on sale) products, which feature Kinect-like depth sensors [I5].
The Partner Director of Research, Microsoft Research Cambridge states “ [t]he SLAM research at Imperial College led by Andrew Davison has impacted the development of HoloLens significantly. Andrew's research on real-time MonoSLAM was an early inspiration in the development of the core tracking system in HoloLens. HoloLens used a sparse feature mapping visual SLAM approach to achieve the robust and accurate inside-out tracking of the wearer’s head which is crucial for a convincing user experience of mixed reality. […] KinectFusion was very important in impacting the approach we currently use for environment mapping in HoloLens 1 and 2. KinectFusion pioneered real-time volumetric fusion of depth data, and the way that this can be implemented efficiently using parallel computation. […] the KinectFusion algorithm for dense environment mapping based on measurements from a moving depth camera […], originally targeted Microsoft's newly release Kinect device, and was hugely influential guiding research in scene mapping for multiple applications including robotics, with the unprecedented detail and speed of reconstruction it enabled. […] On the HoloLens, a derivative of the KinectFusion algorithm allows a real-time reconstruction of the environment around the user, allowing virtual objects to be aligned with real world objects and occlusions of the virtual by the real to be handled appropriately” [I5, I6].
Impact on software development in robotics industry
SLAMcore is an Imperial spin-out company, co-founded in 2016 by Leutenegger, Davison, two PhD students (Zienkiewicz and Kim) and a lab manager (Nicholson). As of 2020, it has over 20 employees and received investment from the UK, US and Japan of over GBP7,000,000 to develop Spatial AI solutions for robots and drones [I7].
SLAMcore has impacted the market of spatial robot and drone software development by offering a licensable software development kit (SDK). The SLAMcore Spatial AI Software Stack SDK enables robots to determine their position and map their surroundings in detail to enable long-term intelligent operation from on-board cameras and other sensors. SLAMcore has established formal hardware partnerships with Intel, NVidia and ARM [10]. The SDK currently is licensed by monthly subscription by 8 customer companies in applications such as warehouse management and evaluated by over 50 more that require SLAM technology for new robot products.
Beneficiaries of the impact
Imperial’s vision-based SLAM research has led to key low-cost localisation and mapping algorithms used by major international technology companies, such as Dyson, Facebook, Google and Microsoft, enabling development of new spatially intelligent consumer products and services. Understanding their context in the surrounding environment enables products such as autonomous cleaning robots to relieve users from household cleaning chores and human-centred, mixed-reality headsets to facilitate new forms of entertainment as well as workplace tasks.
Nature of the impact
Vision-based SLAM is an enabling technology for low cost, high performance, mobile robot products emerging in the consumer sector. The research has also directly impacted development and products in the growing area of mixed-reality devices, which global technology companies now regard as a major new wave in future human-computer interaction.
5. Sources to corroborate the impact
Letter from the Dyson Robotics Systems Architect: Principal Engineer, corroborating the contribution of the Imperial Team in the development of the Dyson 360 Range of Robotic Vacuum Cleaners and in expanding the Dyson Robotics Team.
Dyson 360 Heurist current product website, 2020. https://bit.ly/2O2DVne Link archived here.
Dyson Robotics Lab at Imperial College announced, National news, 2014. https://www.bbc.co.uk/news/technology-26084765 (The announcement also appeared on the Sunday Times front page.) Link archived here.
Imperial SLAM spinout Surreal Vision acquired by Facebook/Oculus announcement, mentioning Imperial College, 2015. https://ocul.us/3kh6qZa Link archived here.
Letter by the Microsoft Partner Director of Science corroborating the Imperial Team’s contribution to Hololens 1 & 2 and Kinect Devices.
Microsoft Windows SDK for Kinect v2 sensors including KinectFusion, 2014. http://bit.ly/3oIWtWf Link archived here.
SLAMcore funding round announcement. Sep. 2018. http://bit.ly/2O4KVzM Link archived here.
Facebook Reality Labs blog where Dr Richard Newcombe discusses the impact of SLAM on AR and VR applications, 2019. https://bit.ly/3kfzy31 Link archived here.
Dyson to invest GBP3 billion in AI, robotics and batteries, 2020. https://www.ft.com/content/834a568d-5bd1-4fd5-a7d3-c66d2eed9265 Link archived here.
SLAMcore technology blog, including details about hardware partnerships with Intel, NVidia, ARM. https://blog.slamcore.com Link archived here.
Letter by the Engineering Director at Google, corroborating the contribution of the Imperial Team to the development of Google Project Tango and ARCore.