Pavel Panchekha

By

Share under CC-BY-SA.

Fuzzing for Layout Invalidation Bugs

One of my favorite browser components is the layout engine, which computes the size and position of everything on the page. It's full of algorithmic challenges, but done right it's marvelous how the whole thing comes together. My upcoming book about web browser engineering devotes two full chapters to layout.

But algorithmic challenges and tricky algorithms also mean bugs. So over the last year, my students William, Nathan, and I have been working with the Google Chrome team to build a fuzzer, LayoutQuickCheck, for layout bugs. In particular we've focused on layout invalidation bugs. I'll explain what those are in a moment, but let me demo the fuzzer first.

Installing and running LayoutQuickCheck

Download LayoutQuickCheck from the Github repo: 

git clone https://github.com/nathand8/layout-quickcheck.git
cd layout-quickcheck
pip3 install -r requirements.txt

You'll also need driver programs for Chrome, and optionally Firefox and Safari. Check the README for the details, but you probably already have them on your machine if you're a browser developer. So now you can run LayoutQuickCheck: 

python3 src/compare.py

The result looks a bit like this: 

No chrome-webdriver path in config. Using /usr/local/bin/chromedriver
No firefox-webdriver path in config. Using /usr/local/bin/geckodriver
No safari-webdriver path in config. Using /usr/bin/safaridriver
Passed: 1;  Bugs: 0;
Found bug. Minifying...
Minified bug. Testing variants...
Variants tested. Saving bug report...
file:///Users/pavpan/Dropbox/Work/LayoutQuickCheck/bugreportfiles/bug-report-2021-04-30-11-16-51-225395/min_bug_with_debug.html
Passed: 3;  Bugs: 1;

The first few lines tell you that on my machine, LayoutQuickCheck found the Chrome, Firefox, and Safari drivers in their default locations. The next line tells you the first generated web page did not demonstrate a bug. And a while later, it found a bug, minified it, and tested it on other browsers and with different browser configurations (what it calls "variants") before finally saving the bug to my file system.

In this example, LayoutQuickCheck tested four random web pages before it found one that was buggy. Now in practice the hit rate is not quite this good; I left that same process running a while longer and it found its tenth bug after generating 700 web pages. That's still pretty good!

What are Layout Invalidation Bugs

Ok, so what kind of bugs is this finding? Are they real bugs?

LayoutQuickCheck is looking for layout invalidation bugs, which relates to the part of the layout engine that handles JavaScript and CSS changes. Basically, layout is a pretty slow process, and you don't want to do it from scratch every time you change the page. Instead, when JavaScript programs (or CSS selectors like :hover) make changes to a web page, that change invalidates some, but not all, of the computed layout bugs. Then the browser recomputes just the invalidated values; there usually aren't that many invalidated values, so this is way faster than doing layout from scratch.

The bug occurs if a layout property isn't invalidated, even though it should be. So for example, suppose some JavaScript changes the padding-left property of an element which has an absolute width value. Normally, the padding doesn't affect the width, so the width doesn't need to be invalidated. But if box-sizing is set to border-box, then padding does affect width, and it does need to be invalidated.

As you can imagine, tracking what properties needs to be invalidated gets pretty complicated, and it's easy to get it wrong. When you do make a mistake, what happens kind of depends on the bug, but usually you get some kind of "partial update", where the change you intended only applies halfway. Sometimes the resulting bugs are super obscure but other times they just involve making changes the developers didn't anticipate and account for. Point is, this is the kind of bug LayoutQuickCheck helps you find.

Anatomy of a bug

Let's look at the bug LayoutQuickCheck generated above. Since underinvalidation bugs involve making changes to a web page, each bug has three parts:

  • An HTML web page
  • An initial CSS file
  • JavaScript that changes that CSS

In the bug above, the initial HTML file looks like this: 

<!doctype html>
Labore quaerat aliquam numquam magnam modi.
<div id="one"></div>
<div id="two"></div>
Consectetur etincidunt labore velit sed.

The two <div> elements have styles applied to them: 

#one { display: table-caption; inline-size: 20px; }
#two { padding-inline-start: 22%; }

#one { min-width:50px; min-height:50px; background-color:indigo; }
#two { min-width:50px; min-height:50px; background-color:orange; }

In reality these styles are applied with a style attribute, but I've reformatted them to CSS syntax to make it easier to read. The first two lines are the minimum to reproduce the bug. The second two lines, which set minimium sizes and background colors, just help make the bug easier to see when you open it in the browser.

Finally, to actually trigger the bug we need to make a certain change to the page—a change that requires invalidation and which demonstrates that the invalidation logic isn't complete. That's pretty simple here: 

var one = document.getElementById("one");
two.style["display"] = "grid";
var two = document.getElementById("two");
two.style["display"] = "table-cell";

Pretty crazy, right? Changing display modes between tables and grids is currently pretty buggy in Chrome, something the developers are working to fix with the NGGrid effort. Anyway, if you make this change with JavaScript, you get a different result compared to adding the new display properties as lines in the initial CSS—feel free to try it (I generated the bug with Google Chrome 90.0.4430.93 on macOS 11.3).

How does LayoutQuickCheck work

LayoutQuickCheck is a fuzzer, meaning that it generates random web pages, random CSS files, and random CSS changes, and then checks whether that randomly-generated page demonstrates a bug.

To generate HTML pages, it basically uses a probabilistic context-free grammar, which means that it is biased toward smaller pages but in principle can generate a tree of any depth or size. That's the right balance for layout invalidation bugs, which are usually reproducible with small web pages.

To generate initial CSS and CSS changes, it reads in Chrome's internal list of CSS properties and generates each property with a fixed probability (10%) at each element. It specifically supports keyword properties (like display) and length properties (like width). Values like colors aren't supported right now, but it wouldn't be hard to add if that was important.

Finally, with the page itself generated, LayoutQuickCheck to trigger both incremental layout (which uses invalidation) and non-incremental, from-scratch layout (which doesn't) to see if they match. For this it uses the following wonderful JavaScript trick: 

document.documentElement.innerHTML = document.documentElement.innerHTML;

This looks like a no-op, but it's not; here's how it works. In JavaScript, document.documentElement is a reference to the root HTML node. Assigning to its innerHTML means replacing its contents by parsing the new value. But reading innerHTML serializes the current contents to a string. So the effect of the statement is to replace the page with brand-new elements containing the same contents. Since those new elements haven't had layout computed before, their layout is computed from scratch and avoids any invalidation bugs.

So to confirm the bug, all LayoutQuickCheck does (and all you have to do) is load the page, execute the JavaScript that changes its CSS, measure the size and position of the elements on the page, execute that no-op-looking line above, and re-measure positions. If anything changes—well, that's a bug.

The great thing about this method is it works with any browser, without needing to make any source code changes, and without having to worry about cross-browser compatibility or regressions between versions. It basically tests a browser against itself, so the bugs it finds are almost always real. And because the machinery involved is just loading pages and running JavaScript, LayoutQuickCheck can test hundreds of pages a minute. On a modern version of Chrome, Firefox, or Safari, that means a bug every few minutes at worst.

LayoutQuickCheck also integrates a bunch of other nice features which I'm not focusing on here—it minimizes bugs so they're easy to understand, runs each bug in multiple browsers and configurations to understand its scope, adds debugging info and JavaScript debugging tools, and so on. Try LayoutQuickCheck out yourself to see all that in action.

Focusing on particular components

A browser developer can't just fix whatever random bugs LayoutQuickCheck finds—the layout engine is big and developers probably don't know all of it. So LayoutQuickCheck lets you use profiles to focus on whatever component a developer is currently working in. I think the profile system is a flexible enough to switch from component to component and to tweak the fuzzer as a browser developer moves between components.

For example, the Chrome developers have recently been working on a new implementation of grid layout, so we built a special grid profile for LayoutQuickCheck. Here's part of it: 

{"style-weights": {
        ...
        "display:grid": 100, "display:inline-grid": 100,
        "grid-template-columns": 40, "grid-template-rows": 40,
        ...
    }
}

The display:grid and display:inline-grid in the profile changes the weights for those properties from the default of 10 to 100, making them roughly ten times more likely. The grid-template-columns and grid-template-rows change the probabilities for generating those properties (while leaving the weights of other values unchanged). So together, these lines mean LayoutQuickCheck will generate a lot of elements with grid layout and gives many of them a grid template as well. The full grid profile has a lot of other properties with higher probability, and also zeros out the weights of display:table and similar, since those have a lot of buggy interactions with grid that should be fixed by a parallel Chrome effort, NGTable.

Conclusion

Try out LayoutQuickCheck. If you're a web developer, you'll feel gratified knowing that browser bugs give browser devs just as much grief as they give you. If you're a researcher, you might be surprised to know that (frankly) pretty primitive bug finding methods work so well on browsers. Browsers are hugely important and hugely impactful, and finding and fixing bugs is both easy and important. And the Chrome team has been super helpful and open to us, a huge joy to work with. And if you're a browser dev, please try out LayoutQuickCheck and reach out to me if you have feedback or ideas about how to make it more useful!