precondition inference

Precondition inference is the process of automatically determining the required conditions that must be true before a function executes correctly — discovering input constraints, state requirements, and assumptions that functions depend on, without requiring manual specification writing.

What Is a Precondition?

• Precondition: A condition that must hold when a function is called for it to behave correctly.
• Examples:
• `array != null` — array must not be null
• `index >= 0 && index < array.length` — index must be valid
• `amount > 0` — amount must be positive
• `file.isOpen()` — file must be open before reading

Why Infer Preconditions?

• Documentation: Automatically document function requirements.
• Bug Prevention: Callers can check preconditions before calling — prevent crashes and errors.
• Verification: Preconditions are essential for formal verification.
• Test Generation: Generate valid test inputs that satisfy preconditions.
• API Understanding: Help developers understand how to correctly use functions.

How Precondition Inference Works

• Static Analysis: Analyze code to identify conditions that must hold.
• Look for assertions, exceptions, null checks, bounds checks.
• Trace backward from error conditions to find required preconditions.

• Dynamic Analysis: Observe executions to learn preconditions.
• Run function with various inputs, observe which succeed and which fail.
• Infer preconditions that distinguish successful from failing executions.

• Symbolic Execution: Explore paths symbolically to derive preconditions.
• Compute path conditions for successful execution.
• Negate conditions leading to errors to get preconditions.

• Machine Learning: Learn preconditions from examples.
• Train models on (input, success/failure) pairs.
• Extract decision boundaries as preconditions.

Example: Precondition Inference

def divide(a, b):
    return a / b

# Inferred precondition: b != 0
# (Otherwise ZeroDivisionError)

def get_element(arr, index):
    return arr[index]

# Inferred preconditions:
# - arr != null
# - 0 <= index < len(arr)
# (Otherwise IndexError)

def withdraw(account, amount):
    if amount <= 0:
        raise ValueError("Amount must be positive")
    if account.balance < amount:
        raise InsufficientFundsError()
    account.balance -= amount

# Inferred preconditions:
# - amount > 0
# - account.balance >= amount

Static Precondition Inference

• Approach: Analyze code to find conditions that prevent errors.

def process_user(user):
    # Code checks user.age
    if user.age < 18:
        return "Minor"
    else:
        return "Adult"

# Inferred precondition: user != null AND user.age is defined
# (Otherwise AttributeError)

• Techniques:
• Null Pointer Analysis: Identify where null checks are needed.
• Bounds Analysis: Determine valid ranges for array indices and numeric values.
• Exception Analysis: Trace back from exception throws to find preventing conditions.

Dynamic Precondition Inference

• Approach: Run function with many inputs, observe successes and failures.

# Function:
def sqrt(x):
    return x ** 0.5

# Test inputs:
sqrt(4) → 2.0 (success)
sqrt(0) → 0.0 (success)
sqrt(-1) → complex number or error (failure)

# Inferred precondition: x >= 0

• Daikon-Style: Collect traces of successful executions, find properties that always hold for inputs.

Symbolic Execution for Preconditions

• Approach: Symbolically execute function, collect path conditions.

def abs_value(x):
    if x < 0:
        return -x
    else:
        return x

# Symbolic execution:
# Path 1: x < 0 → return -x (requires x < 0)
# Path 2: x >= 0 → return x (requires x >= 0)
# Combined precondition: true (no restriction, works for all x)

def safe_divide(a, b):
    if b == 0:
        raise ValueError()
    return a / b

# Symbolic execution:
# Path 1: b == 0 → exception
# Path 2: b != 0 → return a/b (success)
# Precondition for success: b != 0

LLM-Based Precondition Inference

• Code Analysis: LLMs analyze function code to identify implicit preconditions.
• Natural Language: LLMs express preconditions in human-readable form.
• Documentation Mining: LLMs extract preconditions from comments and documentation.

Example: LLM Inferring Preconditions

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# LLM-inferred preconditions:
"""
Preconditions:
  - arr is not null/None
  - arr is sorted in ascending order
  - target is comparable with elements of arr
  
Without these preconditions:
  - If arr is None: AttributeError
  - If arr is unsorted: incorrect result (not an error, but wrong answer)
  - If target is incomparable: TypeError
"""

Applications

• API Documentation: Automatically document function requirements.
• Defensive Programming: Insert precondition checks at function entry.

def withdraw(account, amount):
      assert amount > 0, "Amount must be positive"
      assert account.balance >= amount, "Insufficient funds"
      # ... rest of function

• Contract-Based Programming: Generate contracts for design-by-contract systems.
• Test Input Generation: Generate test inputs that satisfy preconditions.
• Static Analysis: Use preconditions to improve precision of static analyzers.

Challenges

• Completeness: May not discover all preconditions, especially complex ones.
• Precision: May infer preconditions that are too strong (overly restrictive) or too weak (insufficient).
• Implicit Preconditions: Some preconditions are implicit in the domain — hard to infer from code alone.
• Validation: Determining whether inferred preconditions are correct requires human judgment.

Evaluation

• Soundness: Are inferred preconditions actually required?
• Completeness: Are all necessary preconditions discovered?
• Usefulness: Do inferred preconditions help developers?

Precondition inference is a valuable program analysis technique — it automatically discovers function requirements, improving documentation, enabling verification, and helping developers use APIs correctly.