Alloy Analyzer — Lightweight Software Modeling

In this tutorial, you'll learn about Alloy Analyzer. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Alloy is a lightweight formal modeling language based on relational logic, enabling automated analysis of software designs by finding instances and counterexamples within a finite scope.

Learning Path

flowchart LR
  A["First-Order Logic"] --> B["Alloy Analyzer
Lightweight Modeling"]
  B --> C["TLA+"]
  B --> D["Correct-by-Construction"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

First-order logic and basic set theory. Familiarity with object-oriented modeling helps.

What Is Alloy?

Alloy models systems using signatures (sets of atoms), fields (relations between signatures), facts (constraints that always hold), predicates (parameterized constraints), and assertions (properties to check).

The Alloy Analyzer explores all model instances within a user-specified scope and finds violated assertions as counterexamples.

Step-by-Step: Modeling a File System

Step 1: Declare Signatures

abstract sig Object {}
sig File, Dir extends Object {
    contents: set Object,
    parent: one Dir
}
sig Root extends Dir {}  // Root has no parent

Step 2: Add Constraints

fact NoCycles {
    no d: Dir | d in d.^contents
}

fact OneParent {
    all o: Object | one o.parent
}

fact RootParent {
    all r: Root | no r.parent
}

Step 3: Write and Check an Assertion

assert NoFileInRoot {
    all f: File | f.parent != Root
}

check NoFileInRoot for 5

Step 4: Python Equivalent

class AlloyModel:
    def __init__(self):
        self.objects = {}
        self.parents = {}

    def add_file(self, name, parent):
        self.objects[name] = "File"
        self.parents[name] = parent

    def add_dir(self, name, parent=None):
        self.objects[name] = "Dir"
        self.parents[name] = parent

    def check_no_cycles(self):
        visited = set()
        for obj in self.objects:
            curr = obj
            while curr in self.parents and self.parents[curr]:
                if curr in visited:
                    return False
                visited.add(curr)
                curr = self.parents[curr]
        return True

m = AlloyModel()
m.add_dir("root")
m.add_file("a.txt", "root")
m.add_dir("sub", "root")
m.add_file("b.txt", "sub")
print(f"No cycles: {m.check_no_cycles()}")

Expected output:

No cycles: True

Step-by-Step: Security Access Control Model

Step 1: Define Users and Resources

sig User {}
sig Resource {
    owner: one User,
    readers: set User
}

Step 2: Define Access Predicate

pred CanRead[u: User, r: Resource] {
    u in r.readers or u = r.owner
}

assert OwnerCanRead {
    all r: Resource | CanRead[r.owner, r]
}

check OwnerCanRead for 5

Step 3: Python Simulation

class AccessModel:
    def __init__(self):
        self.resources = {}

    def add_resource(self, name, owner, readers=None):
        self.resources[name] = {"owner": owner, "readers": readers or []}

    def can_read(self, user, resource):
        r = self.resources[resource]
        return user == r["owner"] or user in r["readers"]

    def check_owner_can_read(self):
        for name, r in self.resources.items():
            if not self.can_read(r["owner"], name):
                return False
        return True

m = AccessModel()
m.add_resource("doc1", "alice", ["bob"])
m.add_resource("doc2", "bob")
print(f"Owner can read: {m.check_owner_can_read()}")

Expected output:

Owner can read: True

Common Errors

1. Scope Too Small

A scope of 3 atoms may miss counterexamples that appear with 4 or more. Always check with increasing scopes.

2. Overconstraining with Facts

Too many facts restrict the model so much that only trivial instances exist. Use predicates for optional constraints.

3. Confusing some with one

some means at least one. one means exactly one. Using the wrong quantifier changes the semantics significantly.

4. Missing Parentheses in Complex Expressions

Relational logic operator precedence differs from typical boolean logic. Add parentheses liberally.

5. Assuming Symmetry Breaking Is Automatic

Alloy may find symmetric instances that are isomorphic. Use run with exactly scoping to reduce symmetry.

Practice Questions

Q1: What is a signature in Alloy?

A set of atoms. Signatures define the basic types in the model (File, Process, User).

Q2: What does check do?

Verifies that an assertion holds in all instances within the given scope. If a counterexample exists, Alloy displays it.

Q3: What is the difference between fact and pred?

Facts are always true. Predicates are parameterized constraints that must be explicitly invoked.

Q4: How does Alloy handle integers?

Alloy supports integer arithmetic with a fixed bit width (default 4 bits, -8 to 7). Change scope for larger ranges.

Q5: What is a counterexample in Alloy?

An instance of the model that violates a checked assertion, showing a flaw in the design.

Challenge

Model a simple course enrollment system with Students, Courses, and a maximum capacity per course. Write assertions: no student is enrolled in two courses at the same time and no course exceeds capacity. Find counterexamples with small scopes.

FAQ

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.