---------------------------------------------------------------------- -- split invariant calculator -- Kedar Namjoshi, Bell Labs -- -- -- compute strongest split invariant for an N-process system. -- i.e., (theta(0),theta(1),...,theta(N-1)) such that -- each theta(i) is defined only in terms of variables of process i, -- and their conjunction is an invariant. ---------------------------------------------------------------------- -- =============== invariants of the shape (forall i: theta(i)) ========================== -- let conj = conjunction of the thetas in the current vector -- let init = initial state predicate -- let other-vars(i) = variables external to process(i). -- then, the basic fixpoint step is to compute theta'(i) as -- (exists other-vars(i): init | (| j: sp(process(j), conj))) Proc split_invI(prop,N,&others_vars,auxc:=1); -- prop is correctness property -- N is the number of processes in the system -- others_vars[1..N] is an array of sets of variables. -- others_vars[i] is a set of variables that may be quantified out -- when computing theta'(i) -- the '&' in '&others_vars' is required to pass an array as an argument. -- auxc is an invariant defining auxiliary variables used in the proof Print "step 2: set transition relations \n"; For (i in 1...N) Let tr[i] := Ti(i); End Print "step 3: intialize theta array.\n"; For (i in 1...N) Let theta[i] := I() forsome others_vars[i]; End Print "step 4: loop until convergence. \n"; Let change := 1; Let index := 0; While (change) Print "... starting iteration ", index, "\n"; -- For (i in 1...N) -- Print "theta(i) for i=",i; -- form theta[i]; -- End -- compute conjunction Let conj := auxc; For (i in 1...N) Let conj := conj & theta[i]; End -- compute delta to be added to theta(i) For (i in 1...N) Let delta[i] := 0; For (j in 1...N) Let delta[i] := delta[i] | (succ(tr[j], conj) forsome others_vars[i]); End End -- add it in For (i in 1...N) Let newtheta[i] := theta[i] | delta[i]; End -- check for change Let change := 0; For (i in 1...N) Let change := change | (theta[i] != newtheta[i]); Let theta[i] := newtheta[i]; End -- increment counter Let index := index+1; End Print "finished split invariant computation \n"; Print "invariant theta(1) [", size(theta[1]), "]="; form theta[1]; Print "\nchecking for violations\n"; -- step 4: check for violation -- i.e., check if [(/\i: theta(i)) & auxc -> prop] -- i.e., check if (/\i: theta(i)) & auxc & not(prop) is satisfiable Let viol := auxc & !prop; For (i in 1...N) Let viol := viol & theta[i]; End If(viol) Print "!!!!! violation !!!!!\n"; form viol; Else Print "No violation found\n"; End End -- proc split_invI -- ==================== invariants of the shape (exists i: theta(i)) ========================= -- compute *weakest* theta such that -- (exists i: theta(i)) is inductive, and implies the property. -- remaining check: whether (exists i: theta(i)) is implied by the -- initial condition. Proc ex_split_invI(prop,N,&others_vars); -- prop is correctness property -- N is the number of processes in the system -- others_vars[1..N] is an array of sets of variables. -- others_vars[i] is a set of variables that may be quantified out -- (here, universally) when computing theta'(i) -- the '&' in '&others_vars' is required to pass an array as an argument. Print "step 1: computing weakest existential invariant"; Print "step 2: set transition relations \n"; For (i in 1...N) Let tr[i] := Ti(i); End Print "step 3: intialize theta array.\n"; For (i in 1...N) Let theta[i] := 1; End Print "step 4: loop until convergence. \n"; Let change := 1; Let index := 0; While (change) Print "... starting iteration ", index, "\n"; For (i in 1...N) Print "theta(i) for i=",i; form theta[i]; End -- compute disjunction (exists i: theta(i)) Let disj := 0; For (i in 1...N) Let disj := disj | theta[i]; End -- compute next fixpoint value: -- theta'(i) = (forall others_vars[i]: (/\ j: wlp(tr(j),disj)) and prop) For (i in 1...N) Let delta[i] := 1; For (j in 1...N) Let delta[i] := delta[i] & pred(tr[j], disj); End Let newtheta[i] := (delta[i] & prop) forall others_vars[i]; End -- check for change Let change := 0; For (i in 1...N) Let change := change | (theta[i] != newtheta[i]); Let theta[i] := newtheta[i]; End -- increment counter Let index := index+1; End Print "finished (existential) split invariant computation \n"; Print "invariant theta(1) [", size(theta[1]), "]="; form theta[1]; Print "\nchecking for violations\n"; -- step 4: check for violation -- i.e., check if [init -> (\/ i: theta(i))] -- i.e., check if init & (/\i: not(theta(i))) is satisfiable Let viol := I(); For (i in 1...N) Let viol := viol & !theta[i]; End If(viol) Print "!!!!! violation !!!!!\n"; form viol; Else Print "No violation found -- existential property is an inductive invariant and the weakest such. \n"; End End -- proc ex_split_invI --- the set_intersect operator in TLV is wrong. Func set_CONJ(a,b); Local y := set_minus(a,b); Return (set_minus(a,y)); End -- =================== invariants of the shape (forall i,j: i\neq j: theta(i,j)) ==================================== Proc split_invII(prop,N,&ovars,auxc:=1); -- prop is correctness property -- N is the number of processes in the system -- ovars[] is an array of sets of variables. -- ovars[i] is variables not relevant to an assertion about process i. -- the '&' in '&ovars' is required to pass an array as an argument. -- auxc is an invariant defining auxiliary variables used in the proof Print "step 2: set transition relations \n"; For (i in 1...N) Let tr[i] := Ti(i); End Print "step 2a: setting others_vars array\n"; For (i in 1...N) For (j in 1...N) If (i != j) Let others_vars[i][j] := set_CONJ(ovars[i],ovars[j]); Print "others_vars(",i," ",j,") = ", others_vars[i][j]; End End End Print "step 3: intialize theta array.\n"; For (i in 1...N) For (j in 1...N) If (i != j) Let theta[i][j] := I() forsome others_vars[i][j]; End End End Print "step 4: loop until convergence. \n"; Let change := 1; Let index := 0; While (change) Print "... starting iteration ", index, "\n"; -- For (i in 1...N) -- For (j in 1...N) -- If (i != j) -- Print "theta(",i," ",j,")"; -- form theta[i][j]; -- End -- End -- End -- compute conjunction Let conj := auxc; For (i in 1...N) For (j in 1...N) If (i != j) Let conj := conj & theta[i][j]; End End End -- compute delta to be added to theta(i,j) For (i in 1...N) For (j in 1...N) If (i != j) Let delta[i][j] := 0; For (k in 1...N) Let delta[i][j] := delta[i][j] | (succ(tr[k], conj) forsome others_vars[i][j]); End End End End -- add it in For (i in 1...N) For (j in 1...N) If (i != j) Let newtheta[i][j] := theta[i][j] | delta[i][j]; End End End -- check for change Let change := 0; For (i in 1...N) For (j in 1...N) If (i != j) Let change := change | (theta[i][j] != newtheta[i][j]); Let theta[i][j] := newtheta[i][j]; End End End -- increment counter Let index := index+1; End Print "finished split invariant computation \n"; Print "invariant theta(1,2) [", size(theta[1][2]), "]="; form theta[1][2]; Print "\nchecking for violations\n"; -- step 4: check for violation -- i.e., check if [(/\i,j: i \neq j: theta(i,j)) & auxc -> prop] -- i.e., check if (/\i,j: i \neq j: theta(i,j)) & auxc & not(prop) is satisfiable Let viol := auxc & !prop; For (i in 1...N) For (j in 1...N) If (i != j) Let viol := viol & theta[i][j]; End End End If(viol) Print "!!!!! violation !!!!!\n"; form viol; Print "a satisfying assignment\n"; Print (sat(viol)); Else Print "No violation found\n"; End End -- proc split_invII --- ============== Invariants of the shape (forall i,j,k: i,j,k distinct: theta(i,j,k)) =================== Proc split_invIII(prop,N,&ovars); -- prop is correctness property -- N is the number of processes in the system -- ovars[] is an array of sets of variables. -- ovars[i] is variables not relevant to an assertion about process i. -- the '&' in '&ovars' is required to pass an array as an argument. Print "step 2: set transition relations \n"; For (i in 1...N) Let tr[i] := Ti(i); End Print "step 2a: setting others_vars array\n"; For (i in 1...N) For (j in 1...N) For (k in 1...N) If (i != j & j != k & i != k) Let xx := set_CONJ(ovars[i],ovars[j]); Let others_vars[i][j][k] := set_CONJ(xx,ovars[k]); Print "others_vars(",i," ",j," ",k,") = ", others_vars[i][j][k]; End End End End Print "step 3: intialize theta array.\n"; For (i in 1...N) For (j in 1...N) For (k in 1...N) If (i != j & j != k & i != k) Let theta[i][j][k] := I() forsome others_vars[i][j][k]; End End End End Print "step 4: loop until convergence. \n"; Let change := 1; Let index := 0; While (change) Print "... starting iteration ", index, "\n"; -- For (i in 1...N) -- For (j in 1...N) -- If (i != j) -- Print "theta(",i," ",j,")"; -- form theta[i][j]; -- End -- End -- End -- compute conjunction Let conj := 1; For (i in 1...N) For (j in 1...N) For (k in 1...N) If (i != j & j != k & i != k) Let conj := conj & theta[i][j][k]; End End End End -- compute delta to be added to theta(i,j,k) For (i in 1...N) For (j in 1...N) For (k in 1...N) If (i != j & j != k & i != k) Let delta[i][j][k] := 0; For (l in 1...N) Let delta[i][j][k] := delta[i][j][k] | (succ(tr[l], conj) forsome others_vars[i][j][k]); End End End End End -- add it in For (i in 1...N) For (j in 1...N) For (k in 1...N) If (i != j & j != k & i != k) Let newtheta[i][j][k] := theta[i][j][k] | delta[i][j][k]; End End End End -- check for change Let change := 0; For (i in 1...N) For (j in 1...N) For (k in 1...N) If (i != j & j != k & i != k) Let change := change | (theta[i][j][k] != newtheta[i][j][k]); Let theta[i][j][k] := newtheta[i][j][k]; End End End End -- increment counter Let index := index+1; End Print "finished split invariant computation \n"; Print "invariant theta(1,2,3) [", size(theta[1][2][3]), "]="; form theta[1][2][3]; Print "\nchecking for violations\n"; -- step 4: check for violation -- i.e., check if [(/\i,j,k: distinct(i,j,k): theta(i,j,k)) -> prop] -- i.e., check if (/\i,j,k: distinct(i,j,k): theta(i,j,k)) & not(prop) is satisfiable Let viol := !prop; For (i in 1...N) For (j in 1...N) For (k in 1...N) If (i != j & j != k & i != k) Let viol := viol & theta[i][j][k]; End End End End If(viol) Print "!!!!! violation !!!!!\n"; form viol; Else Print "No violation found\n"; End End -- proc split_invIII