The local search algorithm WSAT is one of the most successful algorithms fo
r solving the satisfiability (SAT) problem. It is notably effective at solv
ing hard Random 3-SAT instances near the so-called 'satisfiability threshol
d', but still shows a peak in search cost near the threshold and large vari
ations in cost over different instances. We make a number of significant co
ntributions to the analysis of WSAT on high-cost random instances, using th
e recently-introduced concept of the backbone of a SAT instance. The backbo
ne is the set of literals which are entailed by an instance. We find that t
he number of solutions predicts the cost well for small-backbone instances
but is much less relevant for the large-backbone instances which appear nea
r the threshold and dominate in the overconstrained region. We show a very
strong correlation between search cost and the Hamming distance to the near
est solution early in WSAT's search. This pattern leads us to introduce a m
easure of the backbone fragility of an instance, which indicates how persis
tent the backbone is as clauses are removed. We propose that high-cost rand
om instances for local search are those with very large backbones which are
also backbone-fragile. We suggest that the decay in cost beyond the satisf
iability threshold is due to increasing backbone robustness (the opposite o
f backbone fragility). Our hypothesis makes three correct predictions. Firs
t, that the backbone robustness of an instance is negatively correlated wit
h the local search cost when other factors are controlled for. Second, that
backbone-minimal instances (which are 3-SAT instances altered so as to be
more backbone-fragile) are unusually hard for WSAT. Third, that the clauses
most often unsatisfied during search are those whose deletion has the most
effect on the backbone. In understanding the pathologies of local search m
ethods, we hope to contribute to the development of new and better techniqu
es.