Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

All Non-Relational Privatizations except Miné-W unsound #1457

Closed
michael-schwarz opened this issue May 13, 2024 · 2 comments · Fixed by #1458
Closed

All Non-Relational Privatizations except Miné-W unsound #1457

michael-schwarz opened this issue May 13, 2024 · 2 comments · Fixed by #1458
Assignees
Milestone

Comments

@michael-schwarz
Copy link
Member

During #1456 I discovered that, in fact, all of our non-relational privatizations except the one casting Miné's analsysis in our framework are unsound.

// PARAM: --set ana.base.privatization protection --enable ana.int.enums
// Like 82-how-could-we-have-been-so-blind.c, but with syntactic globals instead of escaping ones.
#include<pthread.h>
#include<stdlib.h>
struct a {
  int b;
};

int *ptr;
int *immer_da_oane;

int da_oane = 0;
int de_andre = 42;

pthread_mutex_t m;

void doit() {
  pthread_mutex_lock(&m);
  *ptr = 5;

  // Should be either 0 or 5, depending on which one ptr points to
  int fear = *immer_da_oane;
  __goblint_check(fear == 5); //UNKNOWN!

  pthread_mutex_unlock(&m);

  pthread_mutex_lock(&m);
  // This works
  int hope = *immer_da_oane;
  __goblint_check(hope == 5); //UNKNOWN!
  pthread_mutex_unlock(&m);

}

void* k(void *arg) {
  // Force MT
  return NULL;
}

int main() {
    int top;

    if(top) {
      ptr = &da_oane;
    } else {
      ptr = &de_andre;
    }

    immer_da_oane = &da_oane;

    pthread_t t1;
    pthread_create(&t1, 0, k, 0);

    doit();
    return 0;
}

The problem is that upon setting *ptr = 5, all targets in the may-point-to-set are updated, rather than joining together the result of updating the different targets. This is likely due to some bot/top confusion inside the local states of the base analysis where the non-present bindings are all assumed to be \bot.

@michael-schwarz
Copy link
Member Author

For protection, the problem seems to be that both get added to P when it should in fact be empty.

@michael-schwarz
Copy link
Member Author

analyzer/src/analyses/base.ml

Lines 1735 to 1743 in 5cd8650

(* We start from the current state and an empty list of global deltas,
* and we assign to all the the different possible places: *)
let nst = AD.fold update_one lval st in
(* if M.tracing then M.tracel "set" ~var:firstvar "new state1 %a" CPA.pretty nst; *)
(* If the address was definite, then we just return it. If the address
* was ambiguous, we have to join it with the initial state. *)
let nst = if AD.cardinal lval > 1 then { nst with cpa = CPA.join st.cpa nst.cpa } else nst in
(* if M.tracing then M.tracel "set" ~var:firstvar "new state2 %a" CPA.pretty nst; *)
nst

In the set, it seems like we only join the cpa components after a non-definite assign and forget to also join priv components. 🤔

michael-schwarz added a commit that referenced this issue May 13, 2024
Earlier `priv` was not joined over, which lead to unsound results #1457. On top, this also considers `dep` and `weak`. While not strictly necessary to pass tests, this also seems to be the right thing here.
michael-schwarz added a commit that referenced this issue May 13, 2024
Earlier `priv` was not joined over, which lead to unsound results #1457. On top, this also considers `dep` and `weak`. While not strictly necessary to pass tests, this also seems to be the right thing here.
@sim642 sim642 added this to the v2.4.0 milestone May 14, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants