The costs of data loss and unavailability can be large, so businesses use many data protection techniques, such as remote mirroring, snapshots and backups, to guard against failures. Choosing an appropriate combination of techniques is difficult because there are numerous approaches for protecting data and allocating resources. Storage system designers typically use ad hoc techniques, often resulting in over-engineered, expensive solutions or under-provisioned, inadequate ones. In contrast, this paper presents a principled, automated approach for designing dependable storage solutions for multiple applications in shared environments. Our contributions include search heuristics for intelligently exploring the large design space and modeling techniques for capturing interactions between applications during recovery. Using realistic storage system requirements, we show that our design tool can produce designs that cost up to 3X less in initial outlays and expected data penalties than the designs produced by an emulated human design process.