Designing for Extensibility and Planning for Conflict: Experiments in Web-Browser Design

Benjamin Lerner

UW Computer Science & Engineering

Outline

• What are extensions?
  • Why do they matter?
  • What challenges do they face?
• The once and future browser
  • How are browsers built, and how will they be built?
• C3: A platform for web-app research
• Challenge #1: extending JS code
  • Answer: dynamic aspects
• Challenge #2: extending UI markup
  • Answer: semantic overlays
• Future challenges

Outline

• What are extensions?
  • Why do they matter?
  • What challenges do they face?
• The once and future browser
  • How are browsers built, and how will they be built?
• C3: A platform for web-app research
• Challenge #1: extending JS code
  • Answer: dynamic aspects
• Challenge #2: extending UI markup
  • Answer: semantic overlays
• Future challenges

What are extensions?

• Third-party code
• Modify websites or the browser itself

Why Extensions?

A closed system cannot be all things to all people

• Experiment with new features
  • Provide new features after products ship
• User-specific customization
  • Without bloating the main application for everyone
• Wildly popular:
  • 6,000+ Firefox extensions
  • Over 2.5 Billion downloads

Extensions, schematically

What can extensions do?

Three main approaches:

• Powerful but brittle
  • Modify all existing UI
  • Interact with all other extensions
• Ad-hoc and sandboxed
  • Modify few limited UI elements
  • Message-passing between extensions
• Widgets
  • “Chromeless” mini-apps
  • Like web pages, isolated from one another

Combining behaviors: Motivation

• Userscripts
  • Inject a script into a webpage
  • Run with same privileges as page
  • Modify the page arbitrarily — new content and event handlers
• 
• Over 60,000 userscripts, over 10 million users

Combining behaviors: Motivation

• Browser extensions
  • Downloaded into browser
  • Run with same privileges as browser
  • Hook into browser events
• 
• Over 6,000 Firefox extensions, over 2 billion downloads

Combining UI: Motivation

• Intuition: “tree-structured patch”
• Find positions in the document tree
  • CSS selectors, XQuery, …
• Insert new content or modify existing nodes

Extensions: What can go wrong?^*

With a base document

<InputBindings>
  <KeyBinding Modifiers="Ctrl" Key="L" Command="Close" />
</InputBindings>

And overlay

<modify selector="InputBindings" where="after">
  <KeyBinding Modifiers="Ctrl" Key="L" Command="GoToLocation" />
</modify>

What should happen when Ctrl+L is pressed?

(^*adapted from real-world example)

Outline

• What are extensions?
  • Why do they matter?
  • What challenges do they face?
• The once and future browser
  • How are browsers built, and how will they be built?
• C3: A platform for web-app research
• Challenge #1: extending JS code
  • Answer: dynamic aspects
• Challenge #2: extending UI markup
  • Answer: semantic overlays
• Future challenges

Browsers today

Browsers of the future

Browsers of the future as they exist today

Browsers of the future: Webapps

Extensions in a post-browser world

• The web browser is evaporating
  • App tabs: removing the address bar for special tabs
  • Google Chrome: removing the address bar for all tabs
  • Mozilla Labs Chromeless: removing the tab bar too!
• All that remains is the web platform
• If extending the browser was good, what do we do when the browser is gone?

Extensions, schematically

What could platform-level extensions do?

Example: prototyping HTML5 concepts

• Key challenge in HTML5: understanding the interactions between parts of the spec
  • DOMCrypt API: new JS APIs for webapps to use
  • <device>, <canvas>: new tags to build with
• Common implementation approaches:
  • Patch browser sources, produce custom builds (e.g. DOMCrypt)
  • Write a plugin (e.g. IndexedDB prototype)
  • Write a JS library and ignore edge cases (e.g. HTML5 shim for IE)
• Alternative: write a self-contained extension
  • No need to rebuild browser
  • Can easily define/limit interactions
  • Still can get the corner cases right

Extension design tradeoffs

Competing design goals:

• Familiarity: make extension authoring easy
• Power & flexibility
  • Vendor can simplify base system
  • User can personalize base system
  • Extension authors can build on other extensions
• Security & stability
  • Extensions can break the base system...or each other!
  • Less control over the platform

How to support all of these?

Outline

• What are extensions?
  • Why do they matter?
  • What challenges do they face?
• The once and future browser
  • How are browsers built, and how will they be built?
• C3: A platform for web-app research
• Challenge #1: extending JS code
  • Answer: dynamic aspects
• Challenge #2: extending UI markup
  • Answer: semantic overlays
• Future challenges

Demos!

Components of an HTML platform

• HTML Parser
• DOM implementation
• JS engine
• Layout engine
• Event loops
• Network/filesystem stack
• User interface

Design goals for C3

• Reconfigurable: Easy to replace browser components with new implementations
• Extensible: Enhance default components without breaking or hacking them
• Experimental: Lower the entry barrier to platform-level research

Extensible Components of an HTML platform

• HTML Parser: recognize new tag names & new AST nodes
• DOM implementation: inject new content into the DOM
• JS engine: modify existing scripts
• Layout engine
• Event loops
• Network/filesystem stack
• User interface: can be done entirely in HTML

The C3 architecture

Example: Where did the bullets come from?

We don't have generated content yet…
but maybe we can use other mechanisms?

<overlay>
  <modify selector="head" where="after">
    <self>
      <style>
        li > span { margin-right: 1em; }
        li > span { color: red; }
        li li > span { color: blue; }
      </style>
    </self>
  </modify>
  <modify selector="li" where="before">
    <self>
      <span>&bull;</span>
    </self>
  </modify>
</overlay>

Systematic extension points

• Recognizing new HTML tag names
• Adding new global objects to JS
• Monitor and modify document construction
• Overlaying new content into documents
  • Provides cleaner semantics than Firefox overlays
  • Enables static checking for conflicts
• Safely patching running JS code
  • Provide better semantics than Greasemonkey-style patches
  • ...without using eval and with better performance
• Others are possible — see the paper!

Already a useful platform for research

• SPUR: A Trace-Based JIT Compiler for CIL (Bebenita et al., OOPSLA 2010)
• Supporting Dynamic, Third-party Code Customizations in JavaScript Using Aspects (Lerner et al., OOPSLA 2010)
• RePriv: Re-Envisioning In-Browser Privacy (Fredrickson and Livshits, Oakland 2011)
• Verified Security for Browser Extensions (Guha et al., Oakland 2011)
• C3: An Experimental, Extensible, Reconfigurable Platform for HTML-based Applications (Lerner et al., WebApps 2011)

Outline

• What are extensions?
  • Why do they matter?
  • What challenges do they face?
• The once and future browser
  • How are browsers built, and how will they be built?
• C3: A platform for web-app research
• Challenge #1: extending JS code
  • Answer: dynamic aspects
• Challenge #2: extending UI markup
  • Answer: semantic overlays
• Future challenges

Combining behaviors: code injection

Only two mechanisms within JS:

• Wrapping

  var oldF = f;
  f = function(x, y) { 
    doStuff(x,y);
    return oldF.apply(this, 2*x, y);
  };

• Monkey patching

  eval("f = " + 
        f.toString()
         .replace('x', '2*x'));

Drawbacks of these approaches^*

• Idioms are “clever” and hard to read
• What does this code do?

  eval("XULBrowserWindow.setOverLink = " + 
       XULBrowserWindow.setOverLink.toString().replace(/{/, 
       "$& link = Fission.setOverLink(link);"));

• ↓

  function XULBrowserWindow.setOverlink(link) {
    link = Fission.setOverLink(link);
    …
  };

(^*real-world example)

Drawbacks of these approaches^*

• How about this code?

  eval('window.aioTabFocus = '+window.aioTabFocus.toSource()
        .replace(
             /\{/,
             '{'+
                'if (e.originalTarget.ownerDocument != document)'+
                   'return;'+
                'var b = e.originalTarget;'+
                'while (b.localName != "tabbrowser")'+
                   'b = b.parentNode;'
         ).replace(
              /aioTabsNb/g,
              'b.aioTabsNb'
         ).replace(
              /aioContent/g,
              'b'
         ).replace(
              /aioRendering/g,
              '(b.mPanelContainer || b)'
         )
  );

Drawbacks of these approaches

• Both approaches break aliases

  function foo(x) { return x*x; }
  
  var bar = foo;
  eval("foo = " + foo.toString().replace("x*x", "42"));
  
  # foo(5) == bar(5);
  # false

• And aliases are everywhere in JS code

  function onLoad(evt)  { window.alert("hello"); }
  
  window.addEventListener("load", onLoad, …);
  eval("onLoad = " + onLoad.toString.replace('hello', 'hi there'));
  
  # …loading the page…
  # Alert: “hello”
  

Drawbacks of these approaches

• Monkeypatching breaks closures

  function makeAdder(x)  { return function(y){ return x+y; }; }
  
  var addFive = makeAdder(5);
  
  eval("addFive = " + addFive.toString.replace('y', 'z'));
  
  # addFive(3);
  # error: ‘x’ is undefined
  

Goal: Combine extension code and mainline

• Extensions need to define:
  • What new code to run
  • When it needs to run
  • How it interacts with existing code
• This is essentially dynamic aspect weaving

Aspects

• Aspects = Advice + Pointcuts
• Advice defines what code to run
• Pointcuts define when to trigger it

at pointcut(callee(square)) before(x) {
   alert("x is ", x);
}

Key features of these Aspects

• Given an aspect

  at pointcut(callee(square)) before(x) {
     alert("x is ", x);
  }
  

• We do not construct new closures

  square → envcode + advice ← squareAlias
  

• This cannot be done in pure JS

Kinds of aspects

• Function advice:
  • Before, after or around bodies of functions
• Field advice:
  • Around getting, setting fields
• Statement advice:
  • Before, after or around statements within functions
• Others?

Implementation for advice weaving

• Targeting the Spur JIT
• Key idea: weaving = inline advice + invalidate JITted closure
• Inlining advice:
  • Avoids function call overhead
  • Ensures advice has access to local variables
• Invalidating JITted closure:
  • Ensures future calls to function get advice
  • Amortizes weaving cost across all calls to function

(See OOPSLA'10 paper for more details)

Evaluation: performance

Evaluation: performance

Evaluation: Expressiveness

• From snapshot of top Firefox extensions, examined 20 using monkeypatching
• Code size: 0.3—14KLOC per extension, 99KLOC total
• Monkey patch size: 11-900LOC, total 2.7KLOC
• 636 observed monkey patches
• We can express 621/636 patches easily

Evaluation: Expressiveness

Our example from before:

eval("XULBrowserWindow.setOverLink = " + 
      XULBrowserWindow.setOverLink.toString().replace(/{/, 
           "$& link = Fission.setOverLink(link);"));

Becomes

at pointcut(callee(XULBrowserWindow.setOverLink)) before(link) {
   link = Fission.setOverLink(link);
}

More explicit, easier to read, more analyzable

Aspects for JS: Contributions

• Extensions have strange behavior
  • Existing techniques within JS are inadequate
  • But we can’t simply outlaw all extensions
• Introduced dynamic aspect weaving as new JS primitive
  • First to integrate aspects into JS engine
  • Cleaner semantics and better performance
  • First to evaluate aspects against real-world extension code
  • Win-win!

Outline

• What are extensions?
  • Why do they matter?
  • What challenges do they face?
• The once and future browser
  • How are browsers built, and how will they be built?
• C3: A platform for web-app research
• Challenge #1: extending JS code
  • Answer: dynamic aspects
• Challenge #2: extending UI markup
  • Answer: semantic overlays
• Future challenges

Overlays: What can go wrong?

• Final composite document depends on loading order
• What if two overlays tried to overlay Ctrl+L?
• In general, what happens when one extension changes the document in ways another extension doesn't expect?
• Idea: built a tool to automatically detect these sorts of problems

Overlay Conflicts in practice

• Examined snapshot of top 350 Firefox extensions
• For main browser UI, extensions contribute:
  • 264 overlays
  • 1140 individual actions
  • ~15,000 “semantic requirements”
  • This is too big for manual checking
• Built a tool to automatically analyze these requirements
• Conflicts found:
  • 6 inter-extension conflicts
  • 50 imprecise overlays
  • 20 incorrectly declared overlays
  • 150 missing dependencies
  • All these errors are silently ignored by Firefox

Overlay conflict detection

• 1. Key idea: Extensions…
  • Use a set of resources (CSS Selectors)
  • Guard those resources (Require, Reject, Last, First)
  • And define actions that occur when the guards are satisfied (overlays)

    (Do something, assuming
      {guarded resource1, guarded resource2, …})

• 2. Guards on resources induce a dependency graph
• 3. Load extensions only if graph is acyclic

Overlay conflict detection in practice

Overlay

<modify selector="InputBindings" where="after">
  <KeyBinding Modifiers="Ctrl" Key="L" Command="GoToLocation" />
</modify>

Becomes…

(Append <KeyBinding Modifiers="Ctrl" Key="L" Command="GoToLocation" />
     to <Inputbindings>,
 {Require InputBindings, Last Key "Ctrl+L"})

Overlay conflict detection: base case

We can treat the base document as an extension too:

(Define html#1, 
        html#1 > head#2,
        html#1 > head#2 + body#3,
        html#1 > head#2 + body#3 > span#4,
        …,
 {Reject html#1,
  Reject html#1 > head#2,
  …})

• The action defines each element in the document by its path to the root
• The guards reject prior definitions of those elements
• This ensures the base document must sort before any extensions that overlay it

When do resources “contradict”?

• Depends on resource type, but must be conservative
• For CSS selectors, need to compute intersection
• Essentially, “may alias” analysis:
  • When might two selectors pick the same nodes?

Overlay conflicts: Contributions

• Overlay systems are powerful but subtle
  • Ordering constraints, well-formedness constraints, …
  • Existing approaches do not catch even simple errors
• Introduced a general dependency-checking tool for overlays
  • Fully-automatic
  • Generalizes existing overlay approaches
  • Checks errors at scales impractical for manual inspection
  • Finds a variety of kinds of errors

Outline

• What are extensions?
  • Why do they matter?
  • What challenges do they face?
• The once and future browser
  • How are browsers built, and how will they be built?
• C3: A platform for web-app research
• Challenge #1: extending JS code
  • Answer: dynamic aspects
• Challenge #2: extending UI markup
  • Answer: semantic overlays
• Future challenges

What next?

• Direct follow-ups:
  • Combine aspects with a pointer-analysis to detect when advice are in conflict
  • “Cross-language conflicts”: Extensions may compose cleanly within each language, yet still have broken behavior
  • Security implications: May not always want to permit extensions to modify mainline code…
• Longer-term:
  • Development tools: What PL support is needed to build a “WebApp IDE” on par with VS?
  • Systems: How to close the functionality gap between HTML and native apps?
  • Platform: How to make the rest of the platform extensible?
  • HCI: How can we make it easier to write an app for a phone, tablet, console and desktop, and what should that look like?