Understanding SAT vs UNSAT Verification Results in VERONA

In VERONA, SAT indicates the verifier found a counter-example proving the model is not robust, while UNSAT proves the model is robust within the specified epsilon ball.

VERONA (from the ada-research/verona repository) treats neural network robustness verification as a decision problem: for a given model, input, and perturbation size ε, it must determine whether every perturbed input satisfies the specification. Understanding SAT vs UNSAT verification results in VERONA is essential for interpreting whether your model is provably robust or vulnerable to adversarial attacks.

What SAT and UNSAT Mean in VERONA

VERONA uses standard SMT solver terminology to express verification outcomes:

• SAT (Satisfiable): The verifier found at least one perturbed input that violates the specification. The property is satisfied by the verifier (i.e., it found a counter-example), meaning the model is not robust for the given ε.
• UNSAT (Unsatisfiable): The verifier proved that no perturbed input violates the specification within the ε-ball. The property is unsatisfied (i.e., no counter-example exists), meaning the model is robust for that ε.

How VERONA Represents Verification Results in Code

The VerificationResult Enum

Both outcomes are represented by the VerificationResult enum defined in ada_verona/database/verification_result.py:

from enum import Enum

class VerificationResult(str, Enum):
    UNSAT = "UNSAT"
    SAT = "SAT"
    TIMEOUT = "TIMEOUT"
    ERROR = "ERR"

CompleteVerificationData Dataclass

The concrete verification modules return a CompleteVerificationData instance that wraps the raw outcome:

from dataclasses import dataclass
from typing import Optional

@dataclass
class CompleteVerificationData:
    result: str                      # "SAT", "UNSAT", "TIMEOUT", "ERR"

    took: float                      # wall-clock time in seconds

    counter_example: Optional[str] = None   # only populated for SAT

    obtained_labels: Optional[list] = None  # parsed labels from counter-example

    err: str = ""
    stdout: str = ""

Running Verification and Interpreting SAT vs UNSAT Outcomes

Using AutoVerifyModule to Check Robustness

The AutoVerifyModule in ada_verona/verification_module/auto_verify_module.py implements the abstract VerificationModule interface and executes the external verifier:

from pathlib import Path
from ada_verona.verification_module.auto_verify_module import AutoVerifyModule
from ada_verona.database.verification_context import VerificationContext

# Initialize with your verifier backend (e.g., SDP-CROWN)

module = AutoVerifyModule(
    verifier=my_verifier, 
    timeout=300.0, 
    config=Path("sdpcrown.yaml")
)

ctx = VerificationContext(...)  # Contains model, input, property generator

epsilon = 0.05

outcome = module.verify(ctx, epsilon)

if isinstance(outcome, str):
    # Non-Ok result: "TIMEOUT" or "ERR"

    print(f"Verification failed: {outcome}")
else:
    # CompleteVerificationData instance

    print(f"Result: {outcome.result}, took {outcome.took}s")
    
    if outcome.result == "SAT":
        print(f"Adversarial label: {outcome.obtained_labels[0]}")
        print("Model is NOT robust for this epsilon")
    elif outcome.result == "UNSAT":
        print("Model IS robust for this epsilon")

Handling SAT Counter-Examples

When the result is SAT, VERONA parses the counter-example to extract the adversarial label. This occurs in ada_verona/verification_module/auto_verify_module.py:

from ada_verona.verification_module.auto_verify_module import (
    parse_counter_example_label, 
    parse_counter_example
)

# raw_result is the verifier's output

label = parse_counter_example_label(raw_result)
counter_example = parse_counter_example(raw_result, ctx)

print(f"Counter-example label: {label}")
print(f"Perturbed input shape: {counter_example.shape}")

The parse_counter_example_label function strips SAT-prefix lines, isolates the Y-values (output logits), and returns the index of the maximum value—the label the model assigns to the adversarial point.

Using SAT and UNSAT in Epsilon-Search Algorithms

VERONA leverages the binary nature of SAT/UNSAT results to locate the exact robustness boundary. The BinarySearchEpsilonValueEstimator in ada_verona/epsilon_value_estimator/binary_search_epsilon_value_estimator.py drives this search:

from ada_verona.epsilon_value_estimator.binary_search_epsilon_value_estimator import (
    BinarySearchEpsilonValueEstimator
)
from ada_verona.verification_module.auto_verify_module import AutoVerifyModule

estimator = BinarySearchEpsilonValueEstimator(
    verifier=my_verifier,
    verification_module=AutoVerifyModule(my_verifier, timeout=120.0)
)

# Returns the largest ε that is UNSAT (robust) and smallest that is SAT (not robust)

unsat_eps, sat_eps = estimator.search(
    ctx, 
    epsilons=[0.01, 0.02, 0.03, 0.04]
)

print(f"Robust up to ε={unsat_eps}, not robust beyond ε={sat_eps}")

The estimator examines EpsilonStatus objects whose result field contains VerificationResult values, selecting the highest UNSAT epsilon (provably robust) and the lowest SAT epsilon (vulnerable).

Edge Cases and Special Results

Beyond the binary SAT/UNSAT outcomes, VERONA handles verification failures:

• TIMEOUT: When the external verifier (e.g., SDP-CROWN) exceeds the allotted time, VERONA records "TIMEOUT". This indicates the result is indeterminate—robustness could not be proven or disproven within the time budget.
• ERROR: Any internal exception or verifier crash surfaces as "ERR". The raw error message is preserved in the err field of CompleteVerificationData for diagnostic purposes.

These statuses allow VERONA to distinguish between "proven robust" (UNSAT), "proven not robust" (SAT), and "unknown" (TIMEOUT/ERROR) states.

Summary

• SAT in VERONA means the verifier found a counter-example; the model is not robust for the given epsilon.
• UNSAT means the verifier proved no counter-example exists; the model is robust for that epsilon.
• Results are encoded in the VerificationResult enum and returned via CompleteVerificationData objects in ada_verona/database/verification_result.py.
• The AutoVerifyModule in ada_verona/verification_module/auto_verify_module.py executes verifiers and parses SAT counter-examples to extract adversarial labels.
• BinarySearchEpsilonValueEstimator uses SAT/UNSAT outcomes to binary-search for the exact robustness boundary.

Frequently Asked Questions

What does SAT mean in VERONA verification?

In VERONA, SAT (Satisfiable) indicates that the verifier successfully found a counter-example—an adversarial input within the epsilon ball that causes the model to violate the specification. This means the model is not robust for the given perturbation size. The result includes the counter-example data and the predicted label of the adversarial input.

How is UNSAT different from SAT in VERONA?

UNSAT (Unsatisfiable) is the opposite of SAT. When VERONA returns UNSAT, it means the underlying verifier (such as SDP-CROWN) mathematically proved that no perturbed input within the epsilon ball violates the specification. In this case, the model is provably robust for that epsilon. Unlike SAT, an UNSAT result contains no counter-example.

What happens when VERONA returns TIMEOUT or ERROR?

TIMEOUT occurs when the external verifier exceeds the configured time limit without reaching a conclusive SAT or UNSAT result. This is treated as an indeterminate state—the model's robustness could not be proven or disproven within the allotted time. ERROR indicates an internal failure, such as a verifier crash or exception; the raw error message is stored in the err field of CompleteVerificationData for debugging.

How does VERONA use SAT and UNSAT to find robustness boundaries?

VERONA employs algorithms like BinarySearchEpsilonValueEstimator to locate the exact robustness threshold. The estimator performs verification across a range of epsilon values, collecting SAT and UNSAT results. It identifies the largest UNSAT epsilon (where the model is still robust) and the smallest SAT epsilon (where a counter-example first appears), effectively bracketing the true robustness boundary of the neural network.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}