postcondition inference

Postcondition inference is the process of automatically determining the guaranteed outcomes and effects of a function after it executes — discovering what properties hold about return values, modified state, and side effects, without requiring manual specification writing.

What Is a Postcondition?

• Postcondition: A condition that is guaranteed to hold after a function executes successfully.
• Examples:
• `return value >= 0` — function always returns non-negative value
• `array is sorted` — function sorts the array
• `balance == old(balance) - amount` — balance is reduced by amount
• `file.isClosed()` — function closes the file

Why Infer Postconditions?

• Documentation: Automatically document function guarantees.
• Verification: Postconditions are essential for proving correctness.
• Testing: Use postconditions as test oracles — check that they hold after execution.
• Debugging: Postcondition violations indicate bugs.
• API Understanding: Help developers understand what functions do.

How Postcondition Inference Works

• Static Analysis: Analyze code to determine what properties must hold after execution.
• Track assignments, state changes, return statements.
• Compute relationships between inputs and outputs.

• Dynamic Analysis: Observe executions to learn postconditions.
• Run function with various inputs, observe outputs and state changes.
• Infer properties that always hold after execution.

• Symbolic Execution: Symbolically execute function to derive postconditions.
• Compute symbolic expressions for outputs in terms of inputs.
• Extract postconditions from symbolic results.

• Machine Learning: Learn postconditions from examples.
• Train models on (input, output, state change) tuples.
• Extract patterns as postconditions.

Example: Postcondition Inference

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

# Inferred postconditions:
# - return value >= 0 (always non-negative)
# - return value == x OR return value == -x
# - return value == abs(x)

def sort_array(arr):
    arr.sort()
    return arr

# Inferred postconditions:
# - arr is sorted in ascending order
# - arr[i] <= arr[i+1] for all valid i
# - len(arr) == len(old(arr)) (length unchanged)
# - set(arr) == set(old(arr)) (same elements)
# - return value == arr (returns the sorted array)

def deposit(account, amount):
    account.balance += amount
    account.transaction_count += 1

# Inferred postconditions:
# - account.balance == old(account.balance) + amount
# - account.transaction_count == old(account.transaction_count) + 1

Static Postcondition Inference

• Approach: Analyze code to determine what must be true after execution.

def increment(x):
    return x + 1

# Inferred postcondition: return value == x + 1

def max_of_two(a, b):
    if a > b:
        return a
    else:
        return b

# Inferred postconditions:
# - return value >= a
# - return value >= b
# - return value == a OR return value == b
# - return value == max(a, b)

Dynamic Postcondition Inference (Daikon-Style)

• Approach: Run function with many inputs, observe outputs, find properties that always hold.

# Function:
def square(x):
    return x * x

# Observed executions:
square(0) → 0
square(1) → 1
square(2) → 4
square(3) → 9
square(-2) → 4

# Inferred postconditions:
# - return value >= 0 (always non-negative)
# - return value == x * x
# - If x >= 0: return value >= x

Symbolic Postcondition Inference

• Approach: Symbolically execute function, derive symbolic expressions for outputs.

def compute(x, y):
    z = x + y
    w = z * 2
    return w

# Symbolic execution:
# z = x + y
# w = (x + y) * 2
# return = (x + y) * 2

# Inferred postcondition: return value == (x + y) * 2

LLM-Based Postcondition Inference

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

Example: LLM Inferring Postconditions

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

# LLM-inferred postconditions:
"""
Postconditions (if function succeeds):
  - account.balance == old(account.balance) - amount
  - return value == new account.balance
  - account.balance >= 0 (invariant maintained)
  
Exceptions:
  - ValueError if amount <= 0
  - InsufficientFundsError if old(account.balance) < amount
  
Note: Function only succeeds if preconditions are met:
  - amount > 0
  - account.balance >= amount
"""

Relational Postconditions

• Relate outputs to inputs: Express how outputs depend on inputs.
• `return == input + 1`
• `output_array == sorted(input_array)`
• `new_balance == old_balance - amount`

• Relate multiple outputs: Express relationships between different outputs or state changes.
• `return_value == modified_array[0]`
• `size_field == array.length`

Applications

• Test Oracle Generation: Use postconditions to check test outputs.

result = sort_array([3, 1, 2])
  assert is_sorted(result)  # Check postcondition
  assert len(result) == 3  # Check postcondition

• Formal Verification: Use postconditions in verification tools to prove correctness.
• Documentation: Automatically document function guarantees.
• Regression Testing: Check that postconditions still hold after code changes.
• Debugging: Postcondition violations indicate bugs.

Challenges

• Completeness: May not discover all postconditions, especially complex ones.
• Precision: May infer postconditions that are too weak (don't capture all guarantees) or too strong (claim more than actually guaranteed).
• Side Effects: Tracking all side effects (file I/O, network, global state) is difficult.
• Validation: Determining whether inferred postconditions are correct requires human judgment.

Evaluation

• Soundness: Are inferred postconditions actually guaranteed?
• Completeness: Are all important guarantees discovered?
• Usefulness: Do inferred postconditions help developers?

Postcondition inference is a powerful program analysis technique — it automatically discovers function guarantees, improving documentation, enabling verification, and providing test oracles for validating correctness.