Algorithm Diversity for Resilient Systems
Abstract
Algorithm Diversity for Resilient Systems Project Summary Scott D. Stoller (PI) and Yanhong Annie Liu Stony Brook University Diversity can increase the resilience of systems, by reducing the prevalence of shared vulnerabilities. A promising way to use diversity to increase the resilience of a software application is to run multiple diverse versions of the application in parallel and compare their outputs. Any difference in the outputs of the variants indicates misbehavior due to an attack and triggers defensive action. This project will explore the use of diversity to detect attacks that, directly or indirectly, cause incorrect changes to a program’s state during execution. Specifically, we propose to develop techniques to introduce algorithm-level diversity, in contrast to existing work on execution-level diversity. Algorithm-level diversity can introduce larger differences between variants than executionlevel diversity and hence can provide greater resilience. The proposed approach to creating algorithm-level diversity is to start from a high-level executable specification and generate different algorithms that satisfy it. This approach builds on our extensive prior work on a systematic approach to generating efficient implementation from specifications, based on the fundamental principle of incremental computation. Many choices need to be made during a derivation; different choices lead to different algorithms. The generated algorithms may differ from each other in fundamental ways, both control structures and data structures, including the order in which parts of the input are accessed. In prior work, our method selected among the choices based on the time and space complexities of the resulting algorithms. We propose to develop techniques to select among them based on diversity in terms of resilience. The main tasks are: (1) Develop metrics and methods to characterize the resilience provided by running of a set of algorithms in parallel and comparing their outputs. (2) Develop diversity metrics that can be evaluated statically and are strongly correlated with resilience. (3) Explore extensions to our algorithm derivation method to increase the diversity of the generated algorithms. (4) Determine which algorithms to generate and run, in a way that optimizes the trade-off between cost and resilience. (5) Evaluate our approach on centralized and distributed computing problems
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141512208
Entities
People
- Scott Stoller
Organizations
- Office of Naval Research
- Research Foundation for the State University of New York
- United States Navy