Yet another blog with too much CS and not enough cycling

Climate Change Skepticism

2011-12-05T11:52:00.000-08:00

Some climate change skeptics who are very dear to me keep expressing puzzlement over why I'm not outraged by the series of leaked emails that constitute "Climategate". Specifically why do I not conclude from them that the best information that we have at present should not make us confident that anthropogenic climate change is real.

I thought I'd explain and give climate change skeptics something easy to attack. A positive argument.

A conspiracy is only damaging if it is effective. A bunch of ineffectual twits sitting around a table plotting is of no danger to anyone. Leaked emails tell us where to look for evidence of damage
but are not, by themselves, evidence of damage.
If there were an effective conspiracy to doctor data to create a false consensus then it could only have been successful in creating a false consensus if there are papers that depend on doctored data.
1. If so, it should be easy to find examples, via the paper citation graph, and present them.
2. According to the skeptics, 1000's of scientists are outraged (outraged I tell you) that "the whole thing is a fraud" which permeates the IPCC and the climatological profession. Being scientists, they should be able to follow citations to find those papers. That they haven't over a year after the first "climategate" is reason enough to conclude tentatively that
  they can't.
If there were an effective conspiracy to claim a consensus where none exists, then there should be plenty of paleo-climatologists who assume the contrary position in the peer-reviewed literature. Oreskes et al. is a positive example of a survey that argues they assume climate change is real.
1. If there were an effective conspiracy to suppress the vast majority of research papers then there would be a large number of quality research papers that have been rejected and a large number of disaffected climatologists who would be clamoring to create their own journals, conferences, and review boards. This has not happened in the decades during which climate change has been discussed. Why not?
2. The unsanitized rejected papers would have data that is substantially different from the sanitized mainstream literature or draw starkly different conclusions from the same data. The BEST study from Berkeley is positive evidence against the first. The second requires a large effective conspiracy as in (4).
If there is a large, effective conspiracy that includes the majority of climatologists, then again, their data would have to be faked or their conclusions would not follow from this data.
1. If their data is cooked, it would show. Again, the BEST study from Berkeley is positive evidence against this claim.
2. If they make up false conclusions, then the evidence is in the literature, and there would have to be some mechanism by which large numbers of scientists coordinate to avoid contradictions that are obvious to lay-people. What is this mechanism?
Conclusion: If the data is not cooked (not 2), paleo-climatologists genuinely try to draw reliable conclusions from their data (not 4), and paleo-climatologists genuinely agree that anthropogenic climate-change is real (not 3) after decades of research, then the best available information says that anthropogenic climate change is real.

If you are a climate change skeptic who wants to convince me of your position, argue against these propositions or present positive evidence. I would love to see any of the following:

Papers that have been infected with cooked data, ideally including a proportion of the citation graph that depends on these papers.
A survey of the recent existing literature that shows that many paleo-climatologists make assumptions inconsistent with anthropogenic climate change. Ideally, this study would compare the proportion of historians of 20th century Europe who believe the holocaust did not happen with the proportion of paleo-climatologists who believe anthropogenic climate change did not happen.
A comparison of the data in papers that were rejected due to the conspiracy and those that were rejected because they were genuinely crap.
A coordinating organization that helps large numbers of conspiratorial scientists to come up with non-obviously-contradictory non-sequiturs based on real data.

I am not going to waste my time looking at:

Damning emails. These are at best pointers where to look for evidence of damage caused by a conspiracy. I've worked too long with databases to be impressed by hysterical emails claiming "the data is all corrupt". When you dig into the problem, usually there isn't one, and most of the rest of the time some forensic work with logs and backups will let me recover the ground truth. Emails are the least reliable signal. Demonstrated damage in dependent applications is the best, and logs that allow forensic analysis are a distant second.
Lists of dissenters. I've looked at a few of these lists and the ones I've checked are full of non-climatologists, economists, and weather forecasters. I'm sure they're lovely people and most of them are probably competent in their own domains, but they are not competent on the question of "is anthropogenic climate change real?" "A Scientific Dissent from Darwinism is another scientist list in a different domain that I find equally unconvincing. If you understand why I find Project Steve so funny, you'll understand why I find your lists unimpressive.

Absolute belief

2011-07-21T15:55:00.000-07:00

I have been accused of wishy-washiness for not having conviction, for not having the strength of absolute belief in things like apple pie or America (Fuck, yeah!). This has always struck me as horribly unfair so allow me to set the record straight.

I believe absolutely and without reservation that (drumroll, please) I have at least one belief that is not correct. Obviously, the idea that I could be wrong about a belief I have because I have no beliefs about which I could be incorrect, or because I am incorrect about whether I hold this belief, beggars belief (pun intended). To not be correct about this particular belief because I am correct in all my beliefs is absurd.

Those who know me probably now think I am both wishy-washy and a pedant, but I think this belief is a better starting place for argument than Descarte's famous "Cogito ergo sum", "I think therefore I am." Descarte fails to rule out solipsism because there is no object to which he relates himself; no attribute that distinguishes Descarte from anything else in the universe. Presumably Descarte thought thoughts but his statement specifies no relationship between the thinker and the thought, so without saying something about what "I am," the statement "I exist" is meaningless

My absolute belief defines me as a believer in relationship to my beliefs any of which may not be correct according to a standard independent of me, and it further establishes that I and my beliefs are proper objects of belief. Not much, but it's a start.

¿Credo ergo erro?

Making JQuery templates safe against HTML injection

2011-04-18T18:29:00.000-07:00

JQuery templates make it very easy for web app developers to compose HTML to keep their user interface up-to-date, but they make it very hard to do so in a way that is safe against XSS.

E.g. the JQuery template

<a href="{$url}">{$text}</a>

means create a link whose target is the result of url and whose body contains the result of text. JQuery does a lot better than most templating languages; message is assumed to be plain text and automatically encoded so that the page can't be XSSed that way. But it does nothing about url. If an attacker can make url be javascript:alert(1337) they can execute code with the full privileges of the containing page. This is a serious hole as URLs abound in web applications.

So right now, JQuery templates are easy to learn, but they have to be used cautiously. They would be even easier to use if template authors (and the poor maintainers) didn't have to worry about the provenance of data values, and could promiscuously inject into URLs, CSS, and inline JavaScript.

I've been cooking up a way to fix templating languages like JQuery. You can play around with Secure JQuery templates in the playground, or read up on the design which also includes an analysis of the performance of this system as applied to another templating language.

Domestic bliss and the keys thereto

2011-01-09T15:54:00.000-08:00

In the short time I've been married, I've come to realize that the key to domestic bliss is having a theoretical framework before engaging in delicate negotiations. (Before you snigger, no, "negotiation" isn't meant euphamistically like routes to other kinds of bliss: "commerce", "congress", "intercourse", "relations", "union"; though you might find the rest of this post much more entertaining if you add a dash of your own innuendo.)

The wife and I are thinking that we might not want to spend the rest of our lives together in a 1200 ft² apartment. Before plonking down hard cash on something with a volatile price, we thought it might be good to figure out what we (collectively) want, so while the wife looked at house listings, I came up with a theoretical framework to save our marriage from the stress that hasty decisions would lead to decades from now.

Observation 1: When buying a house, you usually have to buy the whole house. You can't buy the kitchen and bedroom and not pay for the formal dining room. Which parts are valuable to me and which aren't?

Observation 2: When selling a house, people expect certain things. In addition to the obvious walls, they expect a foyer, and many houses devote more space to baths than to showers. Since Winston Churchhill, has there been a gainfully employed adult with time to take baths?

Observation 3: After living in small apartments in San Francisco for a decade and change, I struggle to imagine what we could do with 7000 ft². What do people do with 13000 ft² houses? Sharks with laser beams? I need a way to separate the definitely useless from the merely probably excessive.

So I want a way to think about the following questions:

How much is a given existing house worth to me?
Of two houses with rooms of the same dimensions, and the same fixtures, but different layouts, which should I prefer?
Given time and a plot of land, what should I build on it, and what should I build now?

Being a reductionist, I will try to answer these questions by dividing each concrete house into smaller abstract houses.

Each quality of the real house (the existence of a room, a fixture, a nice material or finishing, and qualities like the view, location, neighbors, and availability of jobs) goes into at most one of these houses and I should be able to easily classify things as I walk around a house or look at a plan.

A practical house: The portion of the house that its inhabitants use^† on a regular basis. At a minimum, this includes the master-bedroom, a front-door, and a bathroom. Unless the nature of your work makes it impossible to bring it home, it will almost certainly include some kind of quiet study space.
Note: Bachelors, this may not include the kitchen.
An entertaining house: The portion of the house (not in the practical house above) that encourages wanted guests to visit. This probably includes guest rooms, extra pantry space, wet bar, extra parking, and any dedicated dining room.
Note: See "safe house" re unwanted guests.
A safe house / a contingent house: That portion of the house that you hope you will never use, but might. This includes your alarms, guns, flashlight batteries, canned food, fire-extinguisher, and other things that you want to be able to lay your hands on quickly; but that you'd lose if mixed in with your everyday things. Unless you're older or disabled, this probably includes any elevators.
Note: Survivalists, this includes your moat, bomb shelter, life boat, escape pods, and extra ammo.
Note: Yuppies, this includes your portable wealth, "the hounds" and their release switch, and that earthquake preparedness kit you've never opened.
Note: Hipsters, this includes your zombie preparedness kit, and the sealed cache of LPs that you're preserving for future generations.
Note: Zombies, no, brains go under (1).
An ornamental house: That portion of the house that exists solely to impress non-inhabitants to allow resale or to meet legal requirements. This probably includes any formal dining room, and most if not all baths.
Note: New-Agers, this does not include your chakra attuned crystal chandelier.

Hopefully as the examples make clear, this is a subjective assessment. A particular feature, like a pool, might be practical to some people who swim often, entertaining to people who want to entice their grandkids to visit, may be an essential safety feature to someone who is afraid of catching on fire, or might be an ornamental feature when every other house on the block has a pool. Finally it might not be in any house, an expensive hazard to busy parents with a toddler.

Is there anything I'm likely to want in a house that doesn't fit in these four houses?

If the residents don't want to use it (1), guests don't want to use it (2), it's not useful just in case (3), and it's not required for resale or for appearances, then why should it be part of the house?

This will not satisfy a pack-rat, to which I respond, "Don't be a pack-rat!" I have no better argument for its completeness than that I haven't seen a counter-example ; I've tried applying this taxonomy as I've looked at houses and have yet to find something that I could not easily classify based on my likes/dislikes and expected usage patterns.

How does this answer "How much is a given existing house worth to me?"

Once the inhabitants agree what is in which house, then the problem reduces to a simpler set of questions:

What kind of creature comforts are important to us? Value of (1) to me
What would our guests enjoy? Value of (2) to me
How likely are various disasters? Value of (3) to me
How soon will I resell the house, and how much will an impressive house benefit my career or community life? Value of (4) to me
How many fewer creature comforts are we willing to put up with to get our friends to visit? (1) vs (2)
How many comforts are we willing to forego for emergencies? (1) and (2) vs (3)
How many comforts are we willing to forego for increased status? (1) and (2) vs (4)
etc.

How does this answer "Of two houses with rooms of the same dimensions, and the same fixtures, but different layouts, which should I prefer?"

If we had the luxury of embedding a house with N rooms in a space with N+2 spacelike dimension, then we could easily have every room adjacent to every other and still be 3 dimensional. Alternatively, we could wedge shaped rooms radiating out from one central corridor that is an N-gon.

But such houses are either physically impossible or hard to resell, so we need to know what makes a conventional 2½ dimensional house livable.

If the practical house is dispersed, then we're going to spend an inordinate amount of time walking through rooms that we don't use. So we should prefer that the practical house be concentrated and that it be easy to get from one part to another.

Good	Bad
????? ??111?? ??111??	11?????????11 11 11

When entertaining, we're almost certainly going to be using some parts of (1) like bathrooms and kitchen space, but we may want to keep guests away from other parts of (1). So a good arrangement has (1) adjacent to the entertaining house with the common parts at the joining edge.

Good	Bad
????? ??11122 ??11122	11?????????22 11 22

In an emergency, we want to be able to get to the safe house from (1) and less often from (2), but we don't want to lose our emergency stuff by mixing it with a bunch of everyday stuff, so (3) is ideally located at the periphery of (1) and (2) ideally adjacent to both.

Good	Bad
???33 ??11122 ??11122	2211?????????33 ZOMB 2211 33 IES!

Finally, (4) should almost be entirely at the periphery where possible. Why would we want to waste time walking through parts that nobody uses?

Good	Bad
44433 4411122 4411122	114444222444433 ZOMB 11 222 33 IES!

So if you consider an adjacency graph of rooms, then it seems that the best layout has the practical house (1) as a densely connected subgraph (and probably adjacent to the outside), with (2) next to it with special attention paid to common areas, and (3) distinct but reachable from (1) and with (4) out of the way.

These diagrams should be taken with a grain of salt. Each real room doesn't necessarily fall within one abstract house. E.g. most of a stove might be practical, used daily, but maybe you only bake when entertaining, so a nice convection oven would be in the entertaining house.

How does this answer "Given time and a plot of land, what should I build on it, and what should I build now?"

The second part of this question is easily answered. You need most of the practical house early on. You can delay expensive parts of the other houses, and there's no real need to build the parts of the ornamental house that are for resale until you plan to resell. Building (1) then (2) then (3) then (4) may be ideal if you arrange it so the adjacency graph is in shells to get the layout described above.

The first part of the question can be answered by coming up with a wish list for each house and budgeting for it. The relative size of the practical and entertaining houses depends in part on how often you think you'll be able to entertain. The size of the ornamental house depends on how well funded your neighbors are, and the size of the safe house depends on how risk-averse you are and how well funded your enemies are.

Then you need to pare things back. Are all the things in the practical house things you will actually use on a regular basis? If not, maybe kick it into the entertaining house. Are all the things in the entertaining house things you or your guests will use? If not, get rid of it or move it into the ornamental house. The value of something in the safe house is the portion of the cost of the disaster mitigated by the probability of the disaster minus the cost. Consider insurance instead. For the ornamental house, ask whether it can be delayed or faked.

If you've pared it back to the bachelor minimum (bedroom, bathroom, front door), congratulations, your wife is going to leave you so you're done.

Does this framework make delicate negotiations easier, more tractable, more likely to come to correct conclusions?

I don't know. The post-reduction questions above are by no means easy, but for a relationship to survive delicate negotiations, each needs to learn what the other values. They need to get things out in the open so that decisions are made with eyes open to minimize the chances of hidden resentment down the road, and maximize the chances of both enjoying their decisions. I hope these questions get to the heart of that.

† : I use the term "use" broadly; one who appreciates art uses it, and that a house is in a good school district is a practical concern if a child uses the school afforded by the house's location on a regular basis.

Breaking a Tandem down for Travelling

2010-11-28T09:57:00.000-08:00

I got a new tandem from Stephen Bilenky yesterday.

My wife and I are both tall (5'10" and 6'4" respectively aka 178 cm and 193 cm) so we went custom, and I asked him to build it with braze-ons for Beckman racks so he tweaked the geometry to fit those. He also managed to get me an Acai drum brake on the rear so the rear wheel is non-dished between that and the cluster.

He did a nice job with S&S couplers too and gave me the pieces in two standard size shipping cases with nicely labeled velcro padding. Here's how to pack a tandem with 2 sets of S&S couplers.

The first case contains the front wheel which fits inside the shallow top lid deflated with 35mm tires -- smaller tires might fit inflated but I wouldn't ship inflated tires in an unpressurized compartment.

Visible on the left are the front fork and the front tubes with captain's cranks attached, The captain's bars and headset are also visible and those have been removed from the fork. In pictures below I show the details of the shift and brake cables connectors.

Detail of the first case. The package wrapped in white cloth is a saddle. At the far right and bottom are two tubes wrapped in velcro padding,

The captain's drop bars curve around the front tubes and you just have to route the cables where they don't get in the way.

Here you can see three white posts sticking up. Those should be located towards the center of the box, and there are corresponding end caps that go on the other end to prevent the cases from compressing during shipping.

Closing the box requires putting the front wheel over those posts, putting the top caps on, closing the case most of the way, and then finessing the wheel into the space in the lid.

The captain's seat post and saddle goes in the first case wherever it fits.

The second case contains the rear wheel with drum brake facing up, the rear triangle and crank arms wrapped in cloth. That thing nestled in the triangle is the stoker's saddle. I have to swap that seatpost for a thudbuster so hopefully it all fits.

The padding has 2 extra velcro straps for the chain. The chain that connects the captain's and stoker's cranks and the skewers are in a separate envelope.

Detail showing how the saddle fits.

The front cantilever brakes are visible here.

That's a crank arm wrapped up there.

Bilenky was nice enough to write idiot-proof labels on the padding so here are some shots of that.

Rear seat post.

Rear triangle with front derailleur and straps for chain and rear derailleur.

Cables route through padding.

Rear derailleur and cable.

The wrapping goes around the end of the S&S coupler face.

The crank arms are fitted with self-extracting bolts so I need an 8mm allen to reassemble.
The stoker's cranks are separately wrapped in cloth.
Te skewers and the transfer chain are each in separate envelopes, which fit into another envelope.

Each individual tube is wrapped. You can see the cable guide sans-cable at the left.

The fork our of the head tube. There are two pieces of padding that have slits to wrap around the brakes, and one for the top. The stem is not wrapped.

The captain's seat post is wrapped as is the tube for the stoker's bars.

Detail of the padding for the fork. Notice the slit that allows it to go around the brake.

Notice how the cables don't come out of the bottom bracket guides. They ship inside the bottom tube padding.

Cables attach with down-tube bosses attached.

Padding for the front tubes has slits to protect the ends.

Exploded view of the padding for the front tube.

Bilenkey head badge. Spiffy!

Yes, 700x35's with deep rims do fit in the cases deflated.

Utilitarianism

2010-06-28T17:22:00.000-07:00

I've called myself a utilitarian for some time but I've recently concluded that utilitarianism is untenable as a moral philosophy.

I'm an engineer so my job is to understand the tradeoffs inherent in designing a device to suit a purpose. Utilitarianism appealed to me because it treats all ethical decisions as tradeoffs. I was trying to come up with a definition of tradeoffs and concluded that a tradeoff is any attempt to compare incomparables : e.g., maximum speed versus average power consumption, or cash on hand now versus a distribution of returns later. There is no natural ordering of such values, so engineers fall back on (hopefully) their client's utility function : Q(low max speed, low power consumption) > Q(high max speed, high power consumption) is meaningful.

Since tradeoffs can only be made in the presence of a utility function, utilitarianism requires a global utility function. I started to think about the properties such a function would have. For it to be useful in making moral decisions, it must be computable or at least approximable in a time that is sublinear to the number of inputs given that utilitarianism says that everything is potentially an input -- potentially the entirety of the moral actor's past light cone. It must also be able to concretely balance short term gains against long term gains unless one is to forever be sacrificing present good for some distant utopia.

Then I realized that my client's utility function is part of the dynamic system that describes them -- it might be better for my client that they change their utility function than that I really remove seatbelts to save weight. This is not a problem for an engineer since it is my job to understand what the client wants, not worry about their mental health (within reason). But utilitarianism equates "good" and "utility" so I can't make conative assumptions ; if I did, the global utility function would just be a fancy name for a personal god for which I have no evidence. This is not fatal to a global utility function since many functions have fixed points, but it does eliminate many classes of simple functions so there is reason to be skeptical that there exists an approximation that requires only a very small portion of the inputs to the global utility function.

These criteria (approximability, tractability, and horizon-independence) are not trivial so I can't just assert that such a function exists in the same way that any other mental abstraction exists. Unless I have positive reason for believing such a function exists and that I can apply it to solve moral questions, then I have no business calling myself a utilitarian.

So for now, I'm just an ex-utilitarian who thinks that the techniques engineers use to optimize designs can be useful in thinking about moral priorities, but that there are probably other principled ways to the same end.

Reversing Code Bloat with thr JavaScript Knowledge Base

2010-06-15T16:17:00.000-07:00

Lindsey Simon and I just announced JSKB on the google code blog about browser-specific JavaScript optimization. I wanted to expand on that. Unfortunately, I don't have the technical chops necessary to put nice looking charts into blogs, so take a look here.

Talking at OWASP in Stockholm

2010-06-09T17:14:00.000-07:00

I'm going to be talking at OWASP's AppSec Research Conference in Stockholm the week after next (23 June).

Jasvir Nagra and I are talking about virtualization as a strategy for bolting new security policies onto systems that have major legacy constraints, e.g. the web. If we have time, we're going to discuss some of the language changes that Tom Van Cutsem and Mark Miller (who I believe is presenting at OOPSLA) have proposed for EcmaScript.

Beyond the Same Origin Policy
Jasvir Nagra and Mike Samuel, Google Inc.

The same-origin policy has governed interaction between client-side code and user data since Netscape 2.0, but new development techniques are rendering it obsolete. Traditionally, a website consisted of server-side code written by trusted, in-house developers ; and a minimum of client-side code written by the same in-house devs. The same-origin policy worked because it didn't matter whether code ran server-side or client-side ; the user was interacting with code produced by the same organization. But today, complex applications are being written almost entirely in client-side code requiring developers to specialize and share code across organizational boundaries.

This talk will explain how the same-origin policy is breaking down, give examples of attacks, discuss the properties that any alternative must have, introduce a number of alternative models being examined by the Secure EcmaScript committee and other standards bodies, demonstrate how they do or don't thwart these attacks, and discuss how secure interactive documents could open up new markets for web developers. We assume a basic familiarity with web application protocols : HTTP, HTML, JavaScript, CSS ; and common classes of attacks : XSS, XSRF, Phishing.

The sweet spot in internet security.

2010-04-26T14:20:00.000-07:00

New standards like HTML5 often try to address security problems by providing new security features. I think some of these are well-intentioned but are not moving us to a fundamentally more secure internet.

Let me commit blog suicide by starting with a chart that'll drive away most of my potential audience. (Bye :)

	Introduces New Tools	Improves Security of Existing Tools
Large Audience (Web Devs)	Limited. Slow to take hold. E.g., `toStaticHtml`	Good, but doesn't address zero-days. E.g. PHP magic quotes.
Small Audience (Library Authors & Security folk)	Good, but won't help legacy apps. E.g. `<iframe sandbox="...">`	The sweet spot. A (relatively) small group can address emerging threats quickly. E.g., native JSON support

Small groups respond more quickly

The chart is broken down by the size of audience needed to work with the new feature. There are many more web programmers than library developers and web security professionals put together. Any tool that requires most web programmers to use it and use it consistently is limited in its effects. Conversely, if a small audience can change a system to be more secure, then it can have wide-reaching effects. For example, browser developers, a very small audience are now implementing native JSON support. This means that many of the websites out there that have old buggy versions of JSON.js for which there are known script injection exploits, will become more secure because those old libraries were written expecting JSON to become standard and so defer to the newer native implementation on browsers where it exists.

Fix existing code; don't only enable newer better code

The chart is also broken down by scope; will the changes only affect new code that uses new APIs, or does it fundamentally improve the security properties of existing code. If it requires developers to update code, then it can definitely help, but its effects will be very slow to be felt, since existing sites will have to be updated to use it. Website developers are notoriously conservative, and often rightly so ; you can go out of business by updating too soon and breaking your site for old browsers.

Not everything needs to be in the bottom-right box and not everything can be ; there are no silver bullets in security. It is good to have new tools, and to have tools targeted at the web development community at large, but we should always prefer the bottom-right.

Getting Ahead of the Game

New tools also have a problem. Many new security tools are reactions to emerging threats -- the threat model has changed so the HTML and Ecmascript committee respond with new tools that are suited to the new threat model.

But the threat model is only going to keep changing. To get to the sweet spot, we need meta-tools that help small groups of security professionals bolt new security policies onto existing code while maintaining backwards compatibility. And a way to get these changes onto the web at large by targeting a small group -- content aggregators and social hubs that use a plugin model are a good candidate. Ideally we'll get to the point where we have a patch-and-update cycle for the web. As the threat model changes, security specialists use the meta-tools to adapt existing systems to just keep working, but better.

I think the best candidate for meta-tools are software virtualization tools, like the membranes and proxies proposed for Ecmascript 5. And my project, Caja is aiming at providing that layer. We're not in the sweet-spot yet : we've virtualized the DOM and network so we're able to provide a huge array of security policies, but our questionable library support keeps us out of the sweet spot; we're working on that.

Talk on the semantic gap

2010-04-16T17:08:00.000-07:00

Google's security team is expanding, so we're doing some recruiting. To help out, I gave a talk to Dawn Song's class at Berkeley.

In brief my argument was

Programming language design choices affect the kinds of vulnerabilities that programs written in those languages are susceptible to.
The source of these vulnerabilities is not just ignorance by programmers, but includes rational trade-offs between correctness/security and tersity, completeness, maintainability, efficiency, and other concerns.
A "semantic gap" exists where programmers (intentionally or unintentionally) use an abstraction that doesn't do quite what they want it to do.
Often this gap is innocuous (silent overflow in 64b increment) but sometimes it has catastrophic consequences (naive string interpolation → shell injection).
It is possible to close some of these gaps without unduly breaking existing programs by using static analysis, delayed binding, and opt-in defaults to infer intent.

Take a look at my slides.

"Security by Closing the Semantic Gap"

Security is about more than just cryptography; programming language design choices affect the way programmers design programs. We start with code samples in popular programming languages and show how it can be easy to write code that is almost correct, but that fails in ways that are catastrophic security-wise. We demonstrate how tweaking language definitions can close the "semantic gap," the difference between the intended effect of the code and its actual semantics which allows exploitable vulnerabilities to creep in.

Macros for EcmaScript

2010-03-23T14:45:00.000-07:00

I gave a talk a while back about a proposal for adding macros to JavaScript. I'm likely going to be presenting that to the EcmaScript Harmony working group in the next few days. You can take a look at the slides for a talk I gave to the friam group at HP research a while back.

EcmaScript 5 and Harmony

2010-02-10T14:56:00.000-08:00

I gave a talk on EcmaScript 5 and 6. My slides are available as HTML.

My pre-talk notes below capture the gist of what I said:

I'm sure you're all aware that browsers and standards bodies have been working on new versions of JavaScript and HTML. I've been working on client side code for a while, so I'm excited about a lot of these changes. I worked on GWS, and then was the first client dev on calendar. I worked on Closure Compiler, doing optimization and type system work. Recently, I've been working with the EcmaScript committee to try and make it a better language for writing secure and robust programs.

I'd like to go over some of the languages changes in the recently release ES 5, and summarize some of the topics being discussed for the next version. Then I'm going to talk about some strategies that might help you start using new language features in code that needs to work on older interpreters.

There's a lot to cover, so I'm going to go pretty quickly, so please jump in if you see something that grabs your interest.

First, a bit of history. When I say "EcmaScript," I mean "JavaScript." Browsers are working on implementing the latest version EcmaScript 5. Most of you are probably familiar with EcmaScript 3. That leaves ES4 which never made it out of committee. ES4 went on for years without producing a standard, and it's now officially dead. You may be familiar with some of the proposals that came out of it, like the type system on which Closure Compiler's type system is based. But most of the work from that did not make it into ES5.

While ES4 was languishing, the ES3.1 group started from scratch with more modest goals, and eventually produced ES5. There are a few principles that they used to decide what to include and what not to. They wanted to standardize extensions and quirks fixes that 3 out of 4 major intepreters agreed on to move divergent implementations towards compatibility, and address some of the major sources of confusion using an opt-in mode that breaks backwards compatibility.

First major change. ES5 lets user code deal with properties the same way browser intrinsics like DOM nodes do. Many interpreters had implemented getters, setters, watchers, or some similar mechanism; but each was different. This example shows a way of defining a getter and setter using a syntax familiar to anyone who has used SpiderMonkey extensions. This is just a convenience for a richer API though.

defineProperty exposes the full power of the new property APIs. It lets you add a new property to an existing object - either a value property or a dynamic property. And you can specify property attributes -- whether the property is read-only, shows up in a for...in loop, and whether the property can be deleted or reconfigured. The top example shows a value property, and the bottom shows a dynamic property definition.

These APIs are a bit unwieldy, so there are conveniences on top of them. Object.defineProperties lets one combine multiple property definitions. Object.create combines object creation with property definition. Object.freeze makes all properties read-only and unconfigurable, and flips a bit on the object so that new properties can't be added. This gives a shallow immutability which can help code expose objects to the outside world, while maintaining invariants without all kinds of defensive copying.

ES5 also standardizes a lot of interfaces that various libraries have proven very useful. Maybe you're familiar with Closure's goog.array. These interfaces are very similar but implemented natively, and available even without a full-scale library. There are all the usual functional operators, plus a few extra flavors of reduce. There's also a curry operator, the new bind method of function. You give bind a value for this, and optionally some positional parameters and it returns a function that delegates to the original with those parameters.

Another API that most JS libraries reinvent are ones for serializing and deserializing data. Many do this badly, and the number of JSON parsers floating around with known XSS holes is depressing. Most modern interpreters have native JSON support built in. This is a safer way to unpack data. And on calendar, we had to jump through all kinds of hoops to get data unpacking to be as fast as possible. The JSON grammar is significantly simpler than the JS grammar, so native JSON parsing is often faster than eval. It's roughly twice as fast as eval on FF 3.5, though I think eval on V8 is currently faster since they've spent more time optimizing it. One of the nice things you may not be aware of with the new JSON APIs is revivers and replacers which let you serialize/deserialize types other than Array and Object. You can also use it to get better compaction, by doing your own constant pooling. This example shows something that I did for calendar to get our messages smaller -- since instances of repeating events often contain repeated strings. You can use JSON revivers to get the same effect without needing arbitrary JSON. This code is not ideal for a slide, but it shows the basic contract of JSON revivers, and replacers are basically the dual of this.

Besides new APIs, the ES5 group tried to fix spec errors that led to unnecessary confusion. The ES3 spec specified the curly bracket object notation in terms of looking up the name Object in the current scope and calling it as a constructor. This meant that a whole slew of identifiers -- Object, Array, Function -- had special significance. That's no longer the case. Most ES3 interpreters stopped doing this because it allowed some really sneaky cross-domain attacks.

The second example shows another unintended consequence of poor spec language. Function calling is specified in terms of an abstraction called, appropriately enough, a lexical scope. The spec said that a lexical scope is an instance of Object, and so property lookup would find not just declared local variables, but any variables on Object.prototype.

Third, some interpreters pooled regular expression objects. This is problematic because regular expressions are stateful. If a regular expression is being used in a global match, or is used without supplying a new string, then its behavior depends on lastIndex. Which can be mutated by code called in between matches.

Lastly, it was very hard for interpreters to optimize local variable access because of eval. ES3 said that interpreters could raise an error any time eval called via a name other than "eval", but few did. In the above code, not only can eval be used to steal data across scope boundaries, but it show why interpreters can't do lots of interesting optimizations unless they can prove that eval is never called. Now, if eval is called by that name, and refers to the same function as the original global eval, then it reaches into the local scope. Otherwise, all free variables are interpreted in the global scope.

ES strict mode is an opt-in mode that removes a number of other sources of bugs and confusion.
You opt in by putting the string literal "use strict", by itself, at the top of your program or function body.
Any functions contained, and any code evaled inside a strict context is itself strict.
Strict mode differs from normal mode in a few ways. "this" is not coerced to an object in strict mode.

In the Boolean.prototype.not example, this would normally be coerced to an Object, so !this is always false. Not in strict mode.
this can also be null or undefined. It won't magically become the global scope, so code which inadvertently used call or apply with null won't accidentally clobber global definitions. Because of this, in strict mode, there are strictly fewer type coercions.

And, basic operations no longer fail silently. Things like deleting a non-existent property or setting a read-only property will throw an exception instead.

Where ES5 was concerned with fixing known problems, ES6 is concerned with defining a few features that let developers write programs that simply couldn't work under ES5 due to efficiency or scaling issues, or kludgey grammar.
I'm going to walk through a number of ideas the committee is toying with. Some of these are pretty likely to make it into the next version, and some are highly speculative, but I'd love to get feedback on what people like and don't like. After that, I'll talk about strategies for incorporating new language features into code that needs to also run on older interpreters.

One of the things that everyone wanted to get into ES5 but couldn't was let-scoping. If you've seen "let is the new var" t-shirts, this is what they're talking about. Right now, all variables declared in a function are visible everywhere in that function, modulo catch blocks. This leads to a lot of confusion around closures and variables apparently declared in loops. I'm sure you've all had trouble with something like this example where a closure accesses a loop counter i. That problem will go away with let scoping.

A much more controversial proposal is lambdas. If you write a lot of code in JS in a functional style, this would be useful to you. Most versions of lambdas are a reduced syntax for closures that repair the Tennent's correspondence violations that JS functions have. this, arguments, break, continue, and return, all change meaning as soon as you put them inside a function. With lambdas, that is not the case. If anyone is familiar with Neal Gafter's closures for Java proposal, this is similar.

Most everyone agreed that some support for classes is needed, but there's no concensus on exactly what that is. The general feeling is that some syntactic sugar over existing things like constructors and prototypes is probably the best way. This syntactic sugar approach would make it very easy to use classes in code, and down-compile to older versions of ES.

ES has no IdentityHashMap type, or System.identityHashCode. And it probably never will, but sometimes it's hard to write some algorithms without it -- e.g. keeping a list of visited nodes to avoid cycles. Ephemeron tables hash by identity, but without exposing indeterminism. There's no way to iterate over keys, so key order is not a source of indeterminism. And all keys are weakly held, so they don't complicate garbage collection. A value in an ephemeron table is only reachable by the garbage collector if the table and key are independently reachable.
Something like this proposal seems to have fairly broad support.

There seems to be general consensus that modules are needed, but there are active discussions of both means and goals. Some questions raised are how this ineracts with browser fetching, whether modules should be parameterizable ; basically should modules be stateful, or should the state be moved to instances ; and is an isolation mechanism needed so that code can be isolated from changes to Object.prototype and the like. Ihab Awad did a lot of spec writing on that, so can answer detailed questions afterwards.

The committee is listening to proposals around domain-specific language support in ES. DSLs like E4X and CSS selectors have been implemented as extensions or in libraries. So they're definitely useful for creating content in other languages, and for query languages. They could be used to implement new flow control constructs if done right. In the first example here, someone wants to create a regular expression to match a mime-content boundary. But the boundary string could contain special characters, so they use a DSL. The DSL desugars to a function call that gets the literal string portions, and embedded expressions as lambdas. If the re function is const, then interpreters can inline the result since all the parameters are statically known.
These DSLs can also be used to do structured string interpolation -- the syntactic flexibility of perl string interpolations without the horrible XSS problems.
And the last example shows a control structure.

There's also a lot of support for value types. Types that don't compare for equality using reference identity. IBM very much wants decimal arithmetic in, and this is one way to do this. It would also let structured string interpolation behave like real strings.

So that lets user defined code implement new value types. Proxies give user code great flexibility over reference types. I mentioned that there is a known hole in getters and setters. You can't intercept accesses to properties that you haven't defined. Properties do that in a way that preserves the semantics of Object freezing, and avoids a lot of complexity around prototype chains. Instead of defining a property handler of last resort on an existing object, proxies are new objects that delegate all property accesses to handler functions. Those functions can in turn delegate to another object.

Destructuring assignments are syntactic shorthand for unpacking data structures. They are not a general purpose pattern based decomposition as in OCAML or Scala.

Iterators and generators are another idea for which there is wide support but no definite plans.

Cryonics skepticism and the rockstar exemption

2010-01-28T11:30:00.000-08:00

[Update 16 April 2010: After seeing http://wondermark.com/614/ I recant the below. If I might live to see hover toasters, then sign me up!]

I was talking to a friend who has been looking into cryonics. I'm skeptical for the reasons below. This has nothing to do with the good faith of the cryonics companies around today, but with the incentives of future generations.

The claim of cryonics as I understand it is that

It is possible to freeze an ailing human body (or part thereof), wait for medical technology to progress to the point where it can be returned to good health, and then revive it.

This is a reasonable course if all the following hold
(1) that there is an appreciable chance of being revived
(2) that the person revived will survive for an appreciable time after being revived
(3) that the person revived is very similar to the person frozen
(4) that the time at which the person is revived will appeal to the person being revived

I think these 4 assumptions are unlikely to hold at the same time.

Scenario A
A person is frozen, and in their children's or grandchildren's lifetime are revived. In this case, I think 2 is unlikely since medical technology will not have had time to advance much. This may not hold for people suffering from very particular afflictions, especially if they are wealthy and create a foundation to use their wealth to seek targeted advances.

Scenario B
A person is frozen, and in the distant future, medical technology has solved their affliction. In this case, I think 1 is unlikely.
I assert that never in human history, has human civilization produced a machine with a moving part that has continued to function for 100 years without regular maintenance.
This means there is a trade-off between cost of maintenance and cost to revive. Consider two ends of the spectrum. If a cryogenically frozen person is buried in a particularly slow-moving glacier, then maintenance costs are low, but cost to revive is high. If a frozen person is warehoused, then maintenance cost is high, but the cost to revive is lower.

I argue that no-one who would be able to revive them would have economic incentives to do so with a few exceptions that I discuss later.
If the frozen has no assets then noone has incentives to keep the machines running.
Who has either legal standing to act on behalf of the frozen, or economic incentive to see someone successfully unfrozen? Very few.
The cryogenics company has an annuity as long as someone stays frozen. If no next of kin can be identified, the cost of losing an annuity due to death is probably lower than the cost of successfully reviving someone. The cryogenics companies' business models are basically like a family that keeps cashing welfare checks for a grandmother who is disabled or dead.
Lawyers working for the frozen's estate have mixed incentives. Law firms conglomerate like other industries, so after a certain amount of time, the number of long term cryogenically frozen clients whose estates are not administered by a law firm that specializes in frozen clients will be small. They can charge an annuity, and when it comes to decide whether or not to revive, they run the risk of killing a paying client and ending their annuity or continuing to collect a check. A law firm that specializes in such things will have internal controls set up so that they act in the most risk-averse way -- they will never revive anyone unless someone else with legal standing threatens to sue.
Who might have such standing? The RIAA. Since fashion is fickle and cyclic, the RIAA might succeed in getting frozen artists revived so that they can do reunion tours and then, oops their cancer comes back right on cue, and they have to go back to sleep.
Finally, is there a marketing incentive? Not in scenario B. A cryogenics company will want people to have the impression that their latest&greatest are the most reliable, so they will bias to later models. And they will want to use in their marketing literature pretty people who their current target markets can relate to, so will again bias to recent customers.

The above is largely based on arguments from ignorance -- who might have economic incentives? -- but I believe such arguments are valid because I am discussing whether it is rational to do this today, not whether it might be rational for someone in the future.

There are obviously incentives other than economic and legal. If you are a famous scientist, politician, or religious figure, other
incentives apply. For scientists, the likelihood of being unfrozen decreases as your field progresses past your current skill. As a political figure, (4) is problematic since you're just as likely to be revived to stand trial as to be lauded. As with many things, the best course seems to be a god, but ancestor worship is unreliable since current ancestor worshipping cultures do not have to deal with the likelihood of their in-laws coming back from the grave unbidden.

Finally, is a hugely rich person likely to be revived? I doubt it. They are an annuity while frozen, and an unknown political threat to the powers that be if unfrozen.

Efficient Parsing in Javascript

2009-05-11T19:23:00.000-07:00

I rewrote the Google Code source code syntax highlighter recently. It decorates source code in a variety of languages and I learned a few things about parsing in Javascript that others might find useful. Below I compare a few methods for parsing in Javascript and show benchmarks at the end.

Problem

I got some reports that the syntax highlighter for Google Code was slow on large input files, so I decided to rewrite it.

The inner loop of the parser looked something like:

var patterns = [
 // Not the real patterns:
 /^\s+/,                      // whitespace
 /^[a-z]\w*/i,                // An identifier
 /^\d+(?:\.\d+)?/,            // A number
 /^"(?:[^"\\]|\\[^\r\n])*"/,  // A string
 ...
];
while (input) {
 var token;
 for (var i = 0, n = patterns.length; i < n; ++i) {
   token = patterns[i].match(input);
   if (token) { break; }
 }
 // do something with the token
 input = input.substring(token[0].length);
}

Diagnosis

I came up with a few hypotheses about what could be wrong:

One or more of the patterns is trying to match the entire input before failing, making the loop O(n²).
The substring operation is doing an array copy.
The regexp implementation is doing an array copy for the post-match content ($' on perl) even though I never use it which would make the loop O(n²)
All the small strings generated are causing the GC to thrash.
One or more of the regex patterns are worse than O(n) on size matched.

I ruled out (1) and (5) by testing with a simple pattern set [/^\s+/, /^\S+/] and still saw O(n²) behavior. I was really surprised that it seemed to be O(n²) even on non-IE 6 browsers, since I knew thought that most browsers newer than IE6 were much more efficient when it came to string operations.

I couldn't find an easy way to differentiate between (2) and (3) but don't need to since addressing one would address the other.

I ruled out (4) since that would predict that performance would be a step-function — linear with a good constant factor for small inputs, and linear with a bad constant factor for large inputs. But I didn't see that.

Experiment

I tried merging the regular expressions into one so that I could do a global match — using one pass over the input to break it into all tokens.


var uberPattern = new RegExp(
   '/^(?'
   + '\s+'                            // whitespace
   + '|[a-zA-Z]\\w*'                  // An identifier
   + '\\d+(?:\.\\d+)?'                // A number
   + '"(?:[^"\\\\]|\\\\[^\\r\\n])*"'  // A string
   + ')',
   'g');  // global makes match return a list of all matches
var tolens = input.match(uberPattern);
for (var i = 0, n = tokens.length; i < n; ++i) {
 // do something with the token
 input = input.substring(token[0].length);
}

and this got rid of the O(n²) behavior on all browsers I tested (IE6, Safari3.2 and Firefox 3.0).

The do something bit requires that I know which pattern the token matched, so I still have to run through the individual patterns to classify this token, but this is applying the regexs to a much shorter string, and one that does not vary with input size. Also, this classification can be memoized effectively since the majority of tokens in real code are short repeated tokens (single spaces, braces, keywords, etc.).

Solution

function makeParser(patterns) {
 // A poor man's compiler compiler that takes multiple regular expressions
 // and returns a RegExp that is not anchored at the start of the input, and
 // that globally matches the union of the languages matched by the individual
 // patterns.
 var uberPattern = combineRegexs(patterns);
 return function parser(input) {
   var tokens = input.match(uberPattern);
   var classifications = {};
   for (var i = 0, nTokens = tokens.length; i < nTokens; ++i) {
     var token = tokens[i];
     var classification = -1;
     if (hasOwnProperty(classifications, token)) {
       classification = classifications[token];
     } else {
       for (var j = 0; j < nPatterns; ++j) {
         if (patterns[j].test(token)) {
           classification = j;
           break;
         }
       }
       classifications[token] = classification;
     }
     // do stuff with token and classification.
   }
 };
}

Faking lookbehind

There were a number of places where I needed lookbehind, but Javascript doesn't support that. In javascript, determining wheether a solidus (/) starts a regular expression or a division character requires knowing the preceding token†, so lookbehind comes in really handy there.
† — Not actually true since Javascript has no regular lexical grammar, but Waldemar Horwat found a grammar that is lexically regular and indistinguishable in all but a few, mostly useless, cases from the real EcmaScript grammar.

Steven Levinthan came up with a couple mechanisms for faking it though, and I already had a mechanism for embedding one language in another so that I could, e.g. decorate CSS in HTML style attributes and elements. I reused this embedded language mechanism to let me do the equivalent of a regular expression replace by delegating to a small sub-grammar, and that gave me lookahead.

Benchmark Setup

I wrote a benchmark which creates large data file with respectively 512, 1024, 2048, ... rows. It creates one datafile for JSON like

[
 { "friendly": true, "blinking": "hell-yes", "greeting": "Howdy!" },
 { "friendly": true, "blinking": "hell-yes", "greeting": "Howdy!" },
 …
]

and a similar JSON file. It then times how long it takes to decorate each input and tabulates the results.

The results show pretty strikingly that there was a definite O(n²) behavior before, and the new method is both faster in terms of its constant factor, but is linear (or almost so on Safari).

Benchmark Results

I ran all tests on a 2.16 GHz MacBook Pro running Mac OS 10.5.6. IE6 numbers are taken from IE running on VMWare Fusion.

The tests take a while to run, and in some cases I had to click "Scripts on this page are taking a long time to run." dialogs which add noise to the results, but which I do not think invalidate them. I ran fewer input sizes on the old version since it scales so badly, and on Firefox there is a known bug that prevents certain uses of regular expressions on very large strings.

IE6 under VMWare, New
XML
Count	Length (B)	Time (ms)	Items Per Second
512	58888	2391	214.1
1024	117768	4906	208.7
2048	235528	14343	142.8
4096	471048	23282	175.9
8192	942088	45047	181.9
16384	1884168	105047	156.0
JSON
Count	Length (B)	Time (ms)	Items Per Second
512	34816	859	596.0
1024	69632	1625	630.2
2048	139264	3281	624.2
4096	278528	7344	557.7
8192	557056	15813	518.1
16384	1114112	35856	456.9

IE6 under VMWare, Old
XML
Count	Length (B)	Time (ms)	Items Per Second
512	58888	12484	41.0
1024	117768	40906	25.0
2048	235528	166462	12.3
JSON
Count	Length (B)	Time (ms)	Items Per Second
512	34816	4391	116.6
1024	69632	20093	51.0
2048	139264	81000	25.3

Safari New
XML
Count	Length (B)	Time (ms)	Items Per Second
512	58888	634	807.6
1024	117768	1307	783.5
2048	235528	2660	769.9
4096	471048	5348	765.9
8192	942088	11132	735.9
16384	1884168	23829	687.6
JSON
Count	Length (B)	Time (ms)	Items Per Second
512	34816	448	1142.9
1024	69632	451	2270.5
2048	139264	904	2265.5
4096	278528	1773	2310.2
8192	557056	3751	2184.0
16384	1114112	7376	2221.3

Safari Old
XML
Count	Length (B)	Time (ms)	Items Per Second
512	58888	16720	30.6
1024	117768	58799	17.4
2048	235528	236828	8.6
JSON
Count	Length (B)	Time (ms)	Items Per Second
512	34816	13937	36.7
1024	69632	65313	15.7
2048	139264	233607	8.8

Firefox New
XML
Count	Length (B)	Time (ms)	Items Per Second
512	58888	1153	444.1
1024	117768	2315	442.3
2048	235528	5587	366.6
4096	471048	9054	452.4
JSON
Count	Length (B)	Time (ms)	Items Per Second
512	34816	301	1701.0
1024	69632	604	1695.4
2048	139264	1204	1701.0
4096	278528	3675	1114.6
8192	557056	4834	1694.7

Firefox Old
XML
Count	Length (B)	Time (ms)	Items Per Second
512	58888	9836	52.1
1024	117768	40669	25.2
2048	235528	155776	13.1
JSON
Count	Length (B)	Time (ms)	Items Per Second
512	34816	6629	77.2
1024	69632	27533	37.2
2048	139264	104282	19.6

Obligatory First Post

2009-05-11T19:14:00.000-07:00

This blog will contain posts on computer science, cycling and other things that interest me. It reflects my own opinions, which often differ from those of my employer.

Mike Samuel's blog is licensed under a Creative Commons Attribution-Noncommercial 3.0 United States License.