CAREER: Foundations, Algorithms, and Tools for Browser Invalidation

This project aims to make web applications faster and less buggy by improving how web browsers implement an important algorithm called "invalidation." Web browsers are applications that view web pages; popular ones include Google Chrome, Microsoft Edge, Apple Safari, Samsung Internet, and Mozilla Firefox. They use a variety of algorithms to run web applications quickly. One of the most important that applies to a web browser component called its rendering engine, is invalidation. Invalidation means reusing previously-computed results when they could not have changed in the meanwhile. While simple in concept, invalidation is difficult in practice because tracking what can and can not change is extremely difficult. Bugs incorrectly reuse old results or incorrectly recompute unchanged results, and that causes web applications to look wrong, stutter, or freeze. In this project, the investigator presents new programming techniques that automatically track what can and can not change, removing the hardest part of invalidation. If successful, web browsers could adopt these techniques and run web applications faster with fewer bugs. That would ultimately serve the national prosperity by improving software developers' productivity and making more software accessible over the web. The new techniques and tools will be widely disseminated. Research will be integrated into education and training for students, developers and users of web browsers. Technically, browser invalidation algorithms are a set of cache invalidation algorithms for data with tree-structured dependencies. These algorithms are essential to reducing browser rendering latency. Today, these algorithms are written manually and susceptible to both under- and over-invalidation bugs. The projects explores a new monadic abstraction for tracking tree-structured dependencies between data values and automatically propagating invalidation messages ("dirty bits") through this dependency graph. A programming interface based on Resource Allocation Is Initialization (RAII) techniques and abstract invalidation allows integrating this abstraction into existing rendering engines. To test whether invalidation bugs are in fact eliminated, the investigator plans to build a black-box invalidation testing tool for web browsers, which will automatically search for invalidation bugs, which should confirm a dramatic reduction in bugs using the invalidation abstraction. To reduce runtime overhead, a compile-time policy framework will allow incrementally annotating protected data so that the dependency-tracking abstraction compiles down to code competitive with today's manual invalidation algorithms. Finally, a tracing system that combines performance counters such as RDTSC with the dependency graph allows attributing computation time to individual HTML elements and Cascading style sheets (CSS) properties and highlighting that performance data in the browser developer tools. In combination, these thrusts aim to make web browsers faster and less buggy while improving web application developers' ability to adapt their applications to web browser invalidation for greater performance. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.