Frama-C E-ACSL插件无界函数问题及C程序契约生成需求

Hey there! Let's work through your Frama-C E-ACSL challenges—both handling unbounded function concerns and generating solid contracts for your set implementation. Here's a step-by-step breakdown:

1. Addressing Unbounded Function Issues in E-ACSL #

First, let's clarify: "unbounded functions" (like malloc) have behavior tied to external factors (e.g., system memory availability) with no fixed upper limit. E-ACSL often flags these because their runtime behavior can't be fully constrained by default. Here's how to handle them:

• Leverage Frama-C's Standard Library Contracts: Frama-C ships with pre-defined contracts for common libc functions like malloc. Load the standard library module to give E-ACSL a clear model of their behavior:

  frama-c -load-module frama_c_stdlib -e-acsl your_code.c
  

  This defines rules like "malloc returns non-NULL when memory is available, NULL otherwise" and guarantees valid, unallocated pointers on success.

• Explicitly Cover Custom Unbounded Behavior: If your own functions have unbounded edge cases (e.g., insert failing to allocate a new node), add explicit contract clauses to account for these scenarios (like memory exhaustion).

2. Generating ACSL Contracts for Your Set Implementation #

Let's build out contracts for both your new and insert functions, using standard ACSL syntax that E-ACSL can process for runtime checking.

Contract for the new Function #

This contract enforces valid input, correct post-allocation state, and handles the NULL return case for memory exhaustion:

/*@
  // Precondition: Capacity can't be negative
  requires capacity >= 0;

  // Postcondition: Either return NULL (out of memory) or a valid set with correct initial state
  ensures \result == NULL || (\valid(\result) && 
                              \result->capacity == capacity && 
                              \result->size == 0 && 
                              \result->elems == NULL);

  // Track memory allocation: if we return a set, it's been allocated and is freeable
  ensures \result != NULL ==> \allocates \result;
  ensures \result != NULL ==> \freeable(\result);
*/
struct set* new(int capacity) {
    struct set *new_set;
    new_set = (struct set*) malloc(sizeof(struct set));
    if(new_set == NULL) return NULL; /* no memory left */
    new_set->capacity = capacity;
    new_set->size = 0;
    new_set->elems = NULL;
    return new_set;
}

Contract for the insert Function #

First, we'll define helper logical predicates to check if an element exists in the linked list/set. Then we'll write the contract to cover success, failure due to full capacity, failure due to duplicate elements, and memory allocation failures:

/*@
  // Helper predicate: Check if x exists in a linked list
  predicate in_list(struct lnode *n, int x) =
    n != NULL && (n->value == x || in_list(n->next, x));

  // Helper predicate: Check if x exists in the set
  predicate in_set(struct set *s, int x) =
    s != NULL && in_list(s->elems, x);
*/

/*@
  // Precondition: The set pointer is valid, and current size doesn't exceed capacity
  requires \valid(s);
  requires s->size <= s->capacity;

  // Postcondition: Success case (return 0)
  ensures \result == 0 ==> (s->size == \old(s->size) + 1 && 
                            in_set(s, x) && 
                            s->capacity == \old(s->capacity));

  // Postcondition: Failure cases (return -1)
  ensures \result == -1 ==> (s->size == \old(s->size) && 
                            (s->size == s->capacity || in_set(s, x)));

  // Optional: Track node allocation if your insert creates new list nodes
  ensures \result == 0 ==> \allocates \fresh(s->elems);
*/
int insert(struct set *s, int x) {
    // Your implementation here (handle duplicates, capacity checks, node allocation)
}

3. Generating Runtime Checks with E-ACSL #

Once your contracts are in place, generate and run the instrumented code:

1. Instrument your code with E-ACSL:

   frama-c -e-acsl -c your_code.c
   

   This creates a file named frama_c_e_acsl_your_code.c with runtime checks embedded.
2. Compile the instrumented code with GCC:

   gcc -o set_program frama_c_e_acsl_your_code.c
   

3. Run the program—E-ACSL will throw runtime errors if any contract is violated (e.g., inserting into a NULL set, exceeding capacity).

Quick Additional Tips #

• If you still see unbounded function warnings for malloc, double-check that you're loading the Frama-C standard library—it provides the necessary constraints for E-ACSL to handle malloc safely.
• For complex linked list operations, use ACSL's \forall and \exists quantifiers to formalize invariants (e.g., no cycles in the list, all elements are unique).

内容的提问来源于stack exchange，提问作者Raul Coroban