When we become aware of add-ons that go against user expectations or risk user privacy and security, we take steps to block them from running in Firefox using a mechanism called the add-ons blocklist. In Firefox 79, we revamped the blocklist to be more scalable in order to help keep users safe as the add-ons ecosystem continues to grow.
Cascading Bloom Filters
One of the constraints of the previous blocklist was that it required parsing of a large number of regular expressions. Each Firefox instance would need to check if any of its user’s installed add-ons matched any of the regular expressions in the blocklist. As the number of blocks increased, the overhead of loading and parsing the blocklist in Firefox became greater. In late 2019, we began looking into a more efficient way for Firefox to determine if an add-on is blocked.
After investigating potential solutions, we decided the new add-ons blocklist would be powered by a data structure created from cascading bloom filters, which provides an efficient way to store millions of records using minimal space.
Using a single bloom filter as a data structure would have carried a risk of false positives when checking if an add-on was blocked. To prevent this, the new add-on blocklist uses a set of filter layers to eliminate false-positives using the data from addons.mozilla.org (AMO) as a single source of truth.
The same underlying technology used here was first used for Certificate Revocation in CRLite. Adapting this approach for add-ons provided an important head-start for the blocklist project.
Further Optimizations: Stash lists
To reduce the need to ship entire blocklists each time blocks are added, an intermediate data structure is created to record new blocks. These “stash-lists” are queried first, before the main blocklist database is checked. Once the stash-lists grow to a certain size they are automatically folded into a newly generated cascading bloom filter database.
We are currently evaluating additional optimizations in order to further minimize the size of the blocklist for use on Fenix, the next major release of Firefox for Android.
Shipping this in Firefox Extended Support Release (ESR)
Firefox Extended Support Release (ESR) is a Firefox distribution that is focused on feature stability. It gets a major feature update about once per year and only critical security updates in between. When we first identified the need to move the blocklist to a cascading bloom filter in late 2019, we knew we had to land the new blocklist for ESR 78 or we would risk having to maintain two different blocklists in parallel until the next ESR cycle.
In order to land this feature in time for Firefox 78, which was slated to hit the Nightly pre-release channel in May, we needed to coordinate efforts between our add-ons server, add-ons frontend and Firefox Add-ons engineering teams, as well the teams in charge of hosting the blocklist and the still-in-development bloom filters library. We also needed to make sure this new solution cleared all security reviews and QA, as well as coordinate its rollout with Release Engineering, and make sure we had enough data to measure its success.
Our leadership encouraged us to land the new blocklist in Firefox 78 and ensured that we would get the cross-team support necessary to achieve it. Having all these hurdles cleared was very exciting and nerve-wracking at the same time, since now our main challenge was to deliver this huge project on time. While a late-breaking bug prevented us from landing the new blocklist in Firefox 78, we have been able to gradually roll it out with the Firefox 79 release and will enable it in an ESR 78 update.
This was an ambitious project, as it had many moving parts that required the support of many teams across Mozilla. During the project Crypto Engineering, Kinto, Security, Release Engineering, QA and data teams all made significant contributions to enable the Add-ons Engineering team to ship this feature in five months.
Thanks
None of this would have been possible without the help and support of the following people: Simon Bennetts, Shane Caraveo, Alexandru Cornestean, Shell Escalante, Luca Greco, Mark Goodwin, Joe Hildebrand, JC Jones, Dana Keeler, Gijs Kruitbosch, Thyla van der Merwe, Alexandra Moga, Mathieu Pillard, Victor Porof, Amy Tsay, Ryan VanderMeulen, Dan Veditz, Julien Vehent, Eric Smyth, Jorge Villalobos, Andreas Wagner, Andrew Williamson and Rob Wu.