Abstract: Software systems are composed of interacting processes that share data between each other in order to satisfy system properties. When these processes deviate and are unavailable to transmit dataβdue to events such as software bugs, hardware failures, or security attacksβa resilient system will continue delivering safety-critical services. Identify- ing the processes required to satisfy system properties is not a trivial task as there may exist multiple alternative dataflow paths that each satisfy the property. In this work, we propose a formal modeling and analysis technique to compute the sets of minimal processes required to satisfy dataflow properties. The computation of these sets is reduced to a maximum satisfiability problem via modeling in AlloyMax, a for- mal modeling language that performs bounded model checking. We then present a method to formally define the resilience criteria for a system by constraining the minimal dataflow required under maximum system deviations. The efficacy of this work is then evaluated with four case studies motivated from real-world systems with promising results.
Abstract: Alloy is a declarative modeling language based on a first-order relational logic. Its constraint-based analysis has enabled a wide range of applications in software engineering, including configuration synthesis, bug finding, test-case generation, and security analysis. Certain types of analysis tasks in these domains involve finding an optimal solution. For example, in a network configuration problem, instead of finding any valid configuration, it may be desirable to find one that is most permissive (i. e., it permits a maximum number of packets). Due to its dependence on SAT, however, Alloy cannot be used to specify and analyze these types of problems. We propose AlloyMax, an extension of Alloy with a capability to express and analyze problems with optimal solutions. AlloyMax introduces (1) a small addition of language constructs that can be used to specify a wide range of problems that involve optimality and (2) a new analysis engine that leverages a Maximum Satisfiability (MaxSAT) solver to generate optimal solutions. To enable this new type of analysis, we show how a specification in a first-order relational logic can be translated into an input format of MaxSAT solvers - namely, a Boolean formula in weighted conjunctive normal form (WCNF). We demonstrate the applicability and scalability of AlloyMax on a benchmark of problems. To our knowledge, AlloyMax is the first approach to enable analysis with optimality in a relational modeling language, and we believe that AlloyMax has the potential to bring a wide range of new applications to Alloy.
Abstract: Advanced persistent threats (APTs) are a particularly troubling challenge
for software systems. The adversarial nature of the security
domain, and APTs in particular, poses unresolved challenges to
the design of self- systems, such as how to defend against multiple
types of attackers with different goals and capabilities. In
this interaction, the observability of each side is an important and
under-investigated issue in the self- domain. We propose a model
of APT defense that elevates observability as a first-class concern.
We evaluate this model by showing how an informed approach that
uses observability improves the defenderΓ’β¬β’s utility compared to a
uniform random strategy, can enable robust planning through sensitivity
analysis, and can inform observability-related architectural
design decisions.