Conference In: dblp

AlloyMax: bringing maximum satisfaction to relational specifications

In the 29th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE)

Changjian Zhang; Ryan Wagner; Eunsuk Kang — 2021

Key information

Authors:

Changjian Zhang; Ryan Wagner; Pedro Orvalho (Pedro Orvalho); David Garlan; Vasco M. Manquinho (Vasco Miguel Gomes Nunes Manquinho); Ruben Martins (Rúben Carlos Gonçalves Martins); Eunsuk Kang

Published in

August 2021

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.

Publication details

Title of the publication container

In the 29th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE)

First page or article number

155

Last page

167

Fields of Science and Technology (FOS)

computer-and-information-sciences - Computer and information sciences

Publication language (ISO code)

eng - English

Rights type:

Only metadata available