The Golden Gate Bridge Exploit: One Courier, Two Distances
One of the best bugs I was ever handed was found by couriers, not engineers. It needed a
parking lot, a sidewalk, and two services that disagreed about how far away a restaurant
was. This page rebuilds it on real map data so you can stand where they stood.
The Bay Area's highways, with every tolled way in red. The map follows the text: each
part of the story below moves the courier and the camera to where it happened.
You can drag and zoom it at any point, and the last section hands you
the courier, the order and the policies.
Two Services, One Number
Two systems at Grubhub needed to know how far a courier was from a pickup. Autodispatch needed it to decide who to
offer the order to. Driver payment needed it to decide what the delivery paid. For a while
they got that number from different places.
Autodispatch used haversine: the great-circle distance between two
coordinates. It is a formula with no roads in it, which is also what makes it fast, and
fast was the point — dispatch solved a whole market's board every cycle and could not wait
on a routing call per pair. Multiply by an assumed city speed and you have an estimate that
is wrong everywhere and right on average.
Driver payment had only just moved to Pathfinder,
the routing engine, which answered with a real drive over real roads. Two policies came with
it, and both were sensible on their own. Pathfinder would not route over a toll
road, because the courier pays the toll and a pay estimate that assumes they will
is an estimate they will refuse. And it had a one-hour maximum: a delivery
leg longer than an hour is not a delivery leg, it is a mistake, and the engine declined to
price one.
Nothing about either policy is wrong. The bug is in the gap between them and the formula
upstairs, and the gap has a geography.
On the map A courier at the lot by the toll plaza, and an order
in the Marina. The dashed line is what dispatch measures. The gold one is what the routing
engine drives.
Autodispatch
who gets offered the order
waiting for the map…
Pathfinder
the routing engine, under policy
waiting for the map…
Driver pay
priced on Pathfinder's answer
waiting for the map…
From the lot the two agree: a few kilometres, a few minutes, a few dollars.
The Bridge
The Golden Gate Bridge collects its toll in one direction, southbound into the city. In
OpenStreetMap the deck is two separate carriageways, and only the southbound one carries toll=yes. The east sidewalk, the one open to pedestrians, runs beside the
northbound lanes.
Now put a courier on that sidewalk and ask a toll-avoiding router where they are. It snaps
the position to the nearest road it is allowed to use, and the nearest road it is allowed to
use is the northbound deck. From the northbound deck there is exactly one way off, and it is
Marin County.
Where the engine thinks the courier is
The map is still loading.
The thin gold line on the map joins the courier to the point on the road the engine
snapped them to. Walk them back and watch it let go of the deck.
From Marin every bridge back is tolled on the way in: the Richmond–San Rafael, the Bay
Bridge, the San Mateo, the Dumbarton. The only toll-free way home is the long one — east
over the Richmond–San Rafael, which is free eastbound, south through Berkeley, Oakland,
Hayward and Fremont, around the bottom of the bay, and back up the Peninsula on 101. In the
demo's metric that is 179 kilometres and about two and three-quarter hours. Pathfinder's
hour ran out somewhere around Novato, with the frontier still heading away from the
restaurant.
The toll-free way home, with no time limit
The map is still loading.
The map has the hour switched off here, so the search covers the whole Bay Area and
finds it. The next section switches the hour back on.
What the Couriers Found
Somebody in San Francisco worked out that if you parked at the lot by the toll plaza and
walked a few hundred metres out onto the bridge, two things happened. Autodispatch, looking
at the map as the crow flies, saw the Marina, Cow Hollow and the Richmond District a few
kilometres away and offered you their orders. Driver payment, pricing each offer, asked
Pathfinder for the drive, and Pathfinder searched an hour of Marin, never found a permitted
way back across the water, and gave up. A trip it could not finish pricing was priced at the
maximum.
This is where the detail that keeps it a good story rather than a disaster comes in. Driver
pay capped the time and distance components together at $15. Whatever the
cap was for, it was not for this, and it meant the bug paid eighteen dollars or so for a
trip that should have paid six, not two hundred. Nobody was buying a car with it. But
tripling the pay on every short order within sight of the bridge is a very good afternoon,
and the couriers who found it were not looking for a bug. They were looking for the offers
that paid best, and the system told them where to stand. That is a kind of attention
engineers rarely get from the outside, and it is worth more than most test suites.
Once someone noticed what the couriers were doing, the investigation was short: know that
the sidewalk is beside the northbound lanes, and the rest is a routing query you can run in
your head.
The orders within sight of the bridge
Every one of them is offered on sight and paid at the cap.
Autodispatch
who gets offered the order
waiting for the map…
Pathfinder
the routing engine, under policy
waiting for the map…
Driver pay
priced on Pathfinder's answer
waiting for the map…
Limits Protect You From Bugs You Haven't Had Yet
The $15 cap is the part worth keeping. It was not designed against this failure. It was
almost certainly there for ordinary reasons, long trips and bad data, and it turned an
unbounded exploit into a bounded one before anyone knew the exploit existed. Every ceiling
you put on an output for one reason is also a ceiling on the failures you have not
imagined. It is the cheapest insurance in the building, and the reason the honest answer to
"how bad was it" is "a few dollars an order, for a while".
Driver pay
priced on Pathfinder's answer
waiting for the map…
What the cap stood in front of
The map is still loading.
Illustrative rates: $3.00 base, $0.25 a minute,
$0.60 a mile. The cap is the real one.
The Fix, and the Ghosts on the Bridge
The fix was the one already coming: switch Autodispatch to Pathfinder, so that both
services asked one engine one question. When it finally went live the gap closed. Dispatch
now got the same answer driver pay did — no permitted route inside the hour — and a courier
on the bridge stopped being a candidate for anything.
Autodispatch
who gets offered the order
As shipped: the distance between two coordinates, with no roads in it, at an assumed
city speed.
waiting for the map…
Try it Switch dispatch back to haversine and the offer returns.
What I had not predicted was the handful of couriers who, having learned that the bridge
paid, kept going out onto it. Their offers had stopped, so they walked further out, looking
for the spot where the offers started again. There wasn't one. The exploit had taught them
a model of the system, and when the system changed they kept the model. That is the
picture I think about more than the bug itself: a marketplace is a thing people build
theories about, and every incongruity you ship becomes somebody's theory.
Further out
The map is still loading.
What I Took From It
Any two estimators of the same quantity will disagree somewhere, and somewhere is
where the exploit lives. Haversine and a toll-avoiding route agree on the vast
majority of courier positions. The place they disagree is a structure you can walk out
onto, and people will find it.
Policies compose badly with positions. "No toll roads" is a policy about
the route. "Give up after an hour" is a policy about the answer. Neither contemplated a
starting position whose only exit is forbidden. The right fix inside the engine is to
notice when the snapped start can only leave by a tolled way and either allow the toll for
that one leg or tell the caller the position is unroutable, so the caller can decide,
instead of silently searching Marin.
One engine, one question. The lasting fix was not to make haversine
smarter. It was to stop having two definitions of distance. Everything else that needs one
— boundaries, estimates, the simulation — asks the same engine,
which is the only way to make a marketplace stop disagreeing with itself.
Your Turn
Walk the courier back to the lot and out again, and watch the three cards disagree:
dispatch sees a short hop, Pathfinder sees a search that dies in Marin, driver pay sees the
cap. Then switch dispatch to Pathfinder and watch the offer disappear.
The courier
On the map, drag the courier or click anywhere to put them there, and click a merchant
dot to make it the pickup.
Autodispatch
who gets offered the order
As shipped: the distance between two coordinates, with no roads in it, at an assumed
city speed.
waiting for the map…
Pathfinder
the routing engine, under policy
waiting for the map…
Driver pay
priced on Pathfinder's answer
waiting for the map…
Illustrative rates: $3.00 base, $0.25/min, $0.60/mi,
time and distance together capped at $15.00. Dispatch limit 20 minutes.
About the Demo
Everything on the map runs in your browser on real OpenStreetMap data: every drivable street in a
10 km box around the bridge, from the Richmond District to Sausalito, joined to the
highway skeleton of the whole Bay Area — motorways, trunks and primaries from Petaluma to
San Jose and out to Stockton, about 17,000 ways and 12,000 junctions, with every toll=yes way kept. The tolled crossings are drawn in red; you can see that the
toll bridges are tagged one direction each, which is what the whole story turns on.
Pathfinder in production is Customizable Route Planning;
here it is a plain goal-directed search on the same contracted graph, because the overlay is
beside the point and the policies are the point. "Never use a tolled way" is a mask on the
edges. "Give up past an hour" is an A* stopping rule: the heuristic never overestimates, so
the moment the frontier's best optimistic estimate passes the hour, no permitted route can
finish inside it and the search can say so without flooding the whole map. Turn the horizon
off and it floods the whole map, and draws the route round the bay.
The courier is snapped to the nearest permitted segment, not the nearest junction,
because the deck is one segment per carriageway and more than a kilometre between junctions
— snapping to a junction would hide the bug. Speeds are OSM speed limits scaled by a fixed
factor, a Bay Area hour rather than a Loop hour. Pay rates are illustrative; the cap is the
real one. In this section the map is yours: drag the courier anywhere, or click a merchant
for the pickup.