💻 computer science

Sufficient Incorrectness Logic: SIL and Separation SIL

This paper introduces Sufficient Incorrectness Logic (SIL), a new under-approximating program logic designed to precisely identify the set of initial states leading to errors, and extends it with Separation Logic to handle pointers and dynamic allocation while offering stronger guarantees and more succinct postconditions than existing approaches.

Original authors: Flavio Ascari, Roberto Bruni, Roberta Gori, Francesco Logozzo

Published 2026-01-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Flavio Ascari, Roberto Bruni, Roberta Gori, Francesco Logozzo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery in a massive, chaotic factory. The factory is a computer program, and your job is to figure out why things are going wrong (bugs) or to prove that everything is running perfectly.

For decades, the standard way to do this was Hoare Logic. Think of this as a "Safety Inspector." The inspector looks at a machine and says, "If you start with any of these safe inputs, you will never get a broken output." It's very strict. It guarantees safety, but it often cries wolf. It might say, "This input might break the machine," even if it actually won't, just to be safe. This creates "false alarms" that annoy programmers.

Then, a few years ago, researchers introduced Incorrectness Logic (IL). This is more like a "Bug Hunter." Instead of trying to prove everything is safe, it tries to prove that a specific bug can happen. It says, "If you start with some of these inputs, you will definitely find a broken output." This is great for finding real bugs without false alarms, but it has a blind spot: it tells you that a bug exists, but it doesn't always tell you exactly which starting conditions caused it. It's like finding a broken gear but not knowing which specific wrench dropped on it.

The New Hero: Sufficient Incorrectness Logic (SIL)

This paper introduces a new detective tool called Sufficient Incorrectness Logic (SIL).

The Core Idea:
While the old "Bug Hunter" (IL) looks forward and says, "Here is a bug you can find," SIL looks backward. It asks: "If we see this specific broken result, what are all the possible starting points that could have caused it?"

The Analogy of the "Backward Trace":
Imagine a crime scene where a vase is shattered on the floor (the error).

Hoare Logic tries to prove that if you walk into the room, you won't break the vase.
Incorrectness Logic (IL) says, "If you throw a rock from somewhere in this room, the vase will break." It proves the break is possible.
SIL says, "The vase is broken. Therefore, the person who broke it must have been standing in this specific zone of the room."

SIL doesn't just find the bug; it maps out the exact starting conditions (the "sufficient" causes) that guarantee the error will happen. It tells the programmer: "If your code starts in any of these states, you are guaranteed to crash." This is incredibly useful because it gives developers a precise target for debugging. They don't have to guess; they know exactly which inputs to test to reproduce the bug.

How It Works (The "Backward" Trick)

Most logic works like reading a book: you start at page 1 (the beginning of the code) and move forward to page 100 (the end).

Forward Logic: "If I start here, where can I end up?"
SIL (Backward Logic): "If I end up here (in a crash), where must I have started?"

The paper proves that SIL is mathematically sound (it never lies) and complete (it can find all the answers it's looking for) for a specific set of rules. It's designed to be the perfect partner for finding the source of errors, not just the errors themselves.

Handling Memory: Separation SIL

Computers also have to manage memory (like a warehouse with shelves). Sometimes bugs happen because a program tries to use a shelf that was already emptied or doesn't exist.

The authors created a special version of SIL called Separation SIL.

The Metaphor: Imagine the warehouse is huge and messy. Standard logic tries to look at the entire warehouse at once to find a missing item. That's slow and confusing.
Separation Logic (the foundation of Separation SIL) says, "Let's just look at the specific shelf where the item is missing and ignore the rest of the warehouse."
Separation SIL combines this "zoom-in" ability with the "backward trace." It can look at a specific memory error (like a pointer to a deleted shelf) and trace it back to the exact line of code and input that caused the deletion.

The paper claims that for certain types of programs (those without complex loops), Separation SIL is not only correct but also "complete," meaning it can find the simplest, most direct explanation for why a memory error happened.

Why This Matters (According to the Paper)

The authors argue that SIL fills a gap that other tools miss:

It's not just about finding bugs: It's about finding the cause.
It helps debugging: By pinpointing the exact "sufficient" starting states, it helps programmers narrow down their testing. Instead of testing a million random inputs, they can focus on the specific ones that SIL says will definitely break the code.
It's different from the rest: The paper provides a "taxonomy" (a family tree) showing how SIL is related to, but distinct from, Hoare Logic, Incorrectness Logic, and other methods. It shows that while some tools are good at proving safety, and others are good at finding bugs, SIL is uniquely good at explaining why the bugs happen.

In short, the paper presents SIL as a new, powerful lens for looking at code. Instead of just saying "This is broken" or "This is safe," it says, "If you start here, you are guaranteed to break it," giving programmers a clear map to fix the problem.

Technical Summary: Sufficient Incorrectness Logic (SIL) and Separation SIL

1. Problem Statement

Formal methods for program verification have historically relied on over-approximation techniques (e.g., Hoare Logic, Abstract Interpretation) to guarantee the absence of errors. While sound, these methods inevitably produce false alarms (spurious errors), which can hinder programmer adoption. Conversely, under-approximation methods (e.g., Incorrectness Logic, Bounded Model Checking) are designed for bug finding and are free from false alarms, as they only report reachable error states. However, existing under-approximation logics, such as Incorrectness Logic (IL), primarily focus on proving the existence of an error reachable from a precondition. They do not necessarily characterize the set of initial states that lead to such errors.

The paper identifies a gap in reasoning about the sources of incorrectness. Programmers need to know not just that a bug exists, but specifically which input states cause it, to effectively scope debugging and testing. While "Lisbon triples" (backward under-approximations) were previously discussed in the context of Outcome Logic (OL), a dedicated, minimal, and complete proof system specifically for inferring sufficient preconditions for errors was lacking.

2. Methodology

The authors introduce Sufficient Incorrectness Logic (SIL), a new triple-based program logic designed for backward under-approximation.

2.1 Core Concept: SIL Triples

A SIL triple is denoted as $\langle\langle P \rangle\rangle r \langle\langle Q \rangle\rangle$ .

Semantics: The triple is valid if and only if the backward collecting semantics of program $r$ applied to the set of error states $Q$ contains the set of initial states $P$ . Formally: $J \leftarrow r K (Q) \supseteq P$ .
Interpretation: "All input states satisfying $P$ have at least one execution of $r$ leading to a state satisfying $Q$ ."
Distinction from IL: While IL ( $[P] r [Q]$ ) guarantees that some state in $Q$ is reachable from some state in $P$ , SIL guarantees that every state in $P$ can reach an error in $Q$ . This makes $P$ a sufficient condition for incorrectness.

2.2 Proof System

The paper defines a minimal set of proof rules for SIL (Figure 7) that are both sound and complete for regular commands (including non-determinism and loops).

Backward Semantics: The rules are derived from the backward semantics of commands (e.g., assignment uses backward substitution).
Consequence Rule: The rule $\langle\langle \text{cons} \rangle\rangle$ allows strengthening the precondition and weakening the postcondition, facilitating under-approximation.
Handling Loops: The logic includes rules for iteration ( $\langle\langle \text{iter} \rangle\rangle$ ) and additional rules like $\langle\langle \text{iter0} \rangle\rangle$ (skipping the loop) and $\langle\langle \text{unroll} \rangle\rangle$ (unrolling once) to support practical analysis without requiring loop invariants for termination.
Disjunction: Unlike Hoare Logic, SIL allows dropping disjuncts in preconditions (via $\langle\langle \text{choice} \rangle\rangle$ and $\langle\langle \text{disj} \rangle\rangle$ ), which is crucial for scalability in under-approximation.

2.3 Separation SIL

To handle pointers and dynamic memory allocation, the authors instantiate SIL with Separation Logic formulae, creating Separation SIL.

Assertion Language: Combines standard Separation Logic (heap separation, points-to) with the assertion $x \not\mapsto$ (indicating a deallocated pointer), adapted from Incorrectness Separation Logic (ISL).
Rules: Includes backward rules for heap operations (alloc, free, load, store) and a frame rule ( $\langle\langle \text{frame} \rangle\rangle$ ) to allow local reasoning about memory errors.
Completeness: The system is proven sound. For loop-free programs, it is shown to be relatively complete (assuming an oracle for implication between assertions).

3. Key Contributions

Introduction of SIL: A novel logic for sufficient incorrectness triples that identifies the sources of errors (initial states) rather than just the existence of bugs.
Formal Taxonomy: The paper constructs a taxonomy of triple-based logics (Figure 3) based on two axes:
- Semantics Direction: Forward (Hoare Logic, IL) vs. Backward (SIL, Necessary Conditions).
- Approximation Type: Over-approximation (Hoare Logic, Necessary Conditions) vs. Under-approximation (IL, SIL).
- This taxonomy clarifies that SIL is the unique combination of backward semantics and under-approximation.
Comparative Analysis:
- SIL vs. IL: IL finds that an error is reachable; SIL finds which inputs cause it. They are not logically equivalent.
- SIL vs. Hoare Logic (HL): For deterministic and terminating programs, SIL and HL coincide (interpreting the postcondition as error states). For non-deterministic programs, they diverge.
- SIL vs. Necessary Conditions (NC): The authors prove that NC is isomorphic to HL (via double negation) but is not comparable to IL or SIL in the general case.
- SIL vs. Outcome Logic (OL): While OL can express SIL triples (specifically the "Lisbon" pattern), the authors argue that SIL's proof system is more direct and natural for inferring preconditions from error specifications, particularly regarding the handling of disjunctions and backward reasoning.
Separation SIL: A sound and relatively complete instantiation for memory errors, demonstrating that backward under-approximation can yield more succinct postconditions and stronger guarantees than ISL in specific cases (e.g., providing actual witnesses for testing).

4. Results

Correctness and Completeness: The minimal set of SIL rules is proven to be sound and complete for regular commands.
Relative Completeness: Separation SIL is proven relatively complete for loop-free programs.
Industrial Relevance: The paper argues that SIL provides a formal a posteriori justification for the backward analysis strategies used in industrial tools at Meta (Zoncolan, Mariana Trench, Pysa), which infer sufficient incorrectness preconditions to detect security bugs.
Derivation Examples: The paper provides detailed derivations (e.g., for a client program involving free and alloc) showing how Separation SIL can derive preconditions that guarantee an error occurs, offering a more direct path to debugging than forward-oriented logics.

5. Significance and Claims

The paper claims that SIL fills a critical theoretical gap by providing a backward-oriented under-approximation framework. Its significance lies in:

Precision for Debugging: By identifying the exact set of input states that lead to errors, SIL supports "backward reasoning" that is more natural for developers trying to understand why a bug occurs, compared to forward under-approximations that only show that a bug is reachable.
Theoretical Unification: It clarifies the landscape of program logics, showing that while duality exists between Hoare Logic and Necessary Conditions, no such simple duality exists between Incorrectness Logic and Sufficient Incorrectness Logic.
Practical Utility: The authors argue that Separation SIL can produce more succinct postconditions and stronger guarantees than Incorrectness Separation Logic (ISL) for testing and debugging, as it ensures every state in the precondition leads to the error, providing concrete witnesses.

The paper concludes that no single logic is "better"; rather, each (HL, IL, NC, SIL) serves a specific purpose. SIL is specifically positioned as the tool of choice when the goal is to locate the sources of incorrectness to guide debugging and testing efforts.