Augmentation Transformation. Next, we introduce algorithms for translating a model with compound, selection, loop, etc. statements into a model with only variable declaration and expression 13 ▇▇▇▇://▇▇▇▇.▇▇▇▇.▇▇/bip2nusmv statements. We first describe Algorithm 2, which translates a single transition with an arbitrary statement into a set of states and internal transitions with only variable declaration, expression, and return statements. Then, we describe Algorithm 3, which translates an entire model with the help of Algorithm 2. Our augmentation algorithms are based on the small-step operational semantics of our supported Solidity Statements provided in Appendix A.3. Algorithm 2, called AugmentStatement, takes as input a Solidity statement, an origin, destination, and return state, and it creates a set of states and ▇▇▇▇- sitions that implement the input statement using only variable declaration, ex- pression, and return statements as actions. Note that before invoking this al- gorithm, Algorithm 3 removes the original transition between the origin and destination states; hence, this algorithm creates all transitions (and states) from scratch. If the statement is a variable declaration, event, or expression statement, then the algorithm simply creates a transition from the origin to the destina- tion state without any guards and having the statement as an action. If the statement is a return statement, then it creates a transition from the origin to the return state. Note that the return state is preserved by all recursive calls to AugmentStatement, and it is initialized with the destination of the original transition by Algorithm 3. If the statement is a compound, selection, or loop statement, Algorithm 2 creates a set of states and transitions. For a compound statement (i.e., list of statements), the algorithm creates a set of new states, each of which corre- sponds to the execution stage after an inner statement (except for the last one), and it invokes itself (i.e., AugmentStatement ) for each inner statement. For a selection statement with an else (i.e., false) branch, it creates two states, which correspond to the true and false branches. Then, it creates transitions to these states with the branch condition and its negation as guards, and invokes itself for both the true and false body statements. If the selection statement does not have an else branch, then the false branch is replaced by a simple transition to the destination state with the negation of the condition as a guard. Finally, given a for loop statement, it creates three states, which model three stages of the loop execution: after initialization, after each time the loop condition is evaluated to true, and after each execution of the body. Then, it invokes itself with the initialization statement, creates transitions with the loop condition and its negation (leading to the second state or the destination state), and then com- pletes the loop by invoking itself for the body and afterthought statements. For a while loop statement, it needs to create only one new state since there is no initialization or afterthought statement. Algorithm 3, called AugmentModel, takes as input a model that can have any set of supported statements as actions, and it translates the model into one that has only variable declaration, expression, and return statements. It does so by iterating over the transitions and replacing each transition with a set of states and transitions using Algorithm 2. Furthermore, it also augments the transition to consider the possibility that the transition is reverted due to an exception (e.g., failure of a high-level function call or transfer). More specifically, for each Algorithm 2 AugmentStatement (a, so, sd, sr) Input: statement a, origin state so, destination state sd, return state sr 1 if a is variable declaration statement ∨ a is event statement ∨ a is expression statement then 2 add transition from so to sd with action a 3 else if a is return statement then 4 add transition from so to sr with action a 5 else if a is compound statement {a1; a2; . . . ; aN } then 6 for i = 1, 2, . . . , N − 1 do 7 add state si 8 end for 9 AugmentStatement(a1, so, s1, sr ) 10 for i = 2, 3, . . . , N − 1 do 11 AugmentStatement(ai, si−1, si, sr ) 12 end for 13 AugmentStatement(aN , sN−1, sd, sr) 14 else if a is selection statement if (c) aT else aF then 15 add state sT 16 add transition from so to sT with guard c 17 AugmentStatement(aT , sT , sd, sr) 18 add state sF 19 add transition from so to sF with guard !(c) 20 AugmentStatement(aF , sF , sd, sr) 21 else if a is selection statement if (c) aT then 22 add state sT 23 add transition from so to sT with guard c 24 AugmentStatement(aT , sT , sd, sr) 25 add transition from so to sd with guard !(c) 26 else if a is loop statement for (aI ; c; aA) aB then
Appears in 1 contract
Sources: Smart Contract
Augmentation Transformation. Next, we introduce algorithms for translating a model with compound, selection, loop, etc. statements into a model with only variable declaration and expression 13 ▇▇▇▇://▇▇▇▇.▇▇▇▇.▇▇/bip2nusmv statements. We first describe Algorithm 2, which translates a single transition with an arbitrary statement into a set of states and internal transitions with only variable declaration, expression, and return statements. Then, we describe Algorithm 3, which translates an entire model with the help of Algorithm 2. Our augmentation algorithms are based on the small-step operational semantics of our supported Solidity Statements provided in Appendix A.3. Algorithm 2, called AugmentStatement, takes as input a Solidity statement, an origin, destination, and return state, and it creates a set of states and ▇▇▇▇- sitions that implement the input statement using only variable declaration, ex- pression, and return statements as actions. Note that before invoking this al- gorithm, Algorithm 3 removes the original transition between the origin and destination states; hence, this algorithm creates all transitions (and states) from scratch. If the statement is a variable declaration, event, or expression statement, then the algorithm simply creates a transition from the origin to the destina- tion state without any guards and having the statement as an action. If the statement is a return statement, then it creates a transition from the origin to the return state. Note that the return state is preserved by all recursive calls to AugmentStatement, and it is initialized with the destination of the original transition by Algorithm 3. If the statement is a compound, selection, or loop statement, Algorithm 2 creates a set of states and transitions. For a compound statement (i.e., list of statements), the algorithm creates a set of new states, each of which corre- sponds to the execution stage after an inner statement (except for the last one), and it invokes itself (i.e., AugmentStatement ) for each inner statement. For a selection statement with an else (i.e., false) branch, it creates two states, which correspond to the true and false branches. Then, it creates transitions to these states with the branch condition and its negation as guards, and invokes itself for both the true and false body statements. If the selection statement does not have an else branch, then the false branch is replaced by a simple transition to the destination state with the negation of the condition as a guard. Finally, given a for loop statement, it creates three states, which model three stages of the loop execution: after initialization, after each time the loop condition is evaluated to true, and after each execution of the body. Then, it invokes itself with the initialization statement, creates transitions with the loop condition and its negation (leading to the second state or the destination state), and then com- pletes the loop by invoking itself for the body and afterthought statements. For a while loop statement, it needs to create only one new state since there is no initialization or afterthought statement. Algorithm 3, called AugmentModel, takes as input a model that can have any set of supported statements as actions, and it translates the model into one that has only variable declaration, expression, and return statements. It does so by iterating over the transitions and replacing each transition with a set of states and transitions using Algorithm 2. Furthermore, it also augments the transition to consider the possibility that the transition is reverted due to an exception (e.g., failure of a high-level function call or transfer). More specifically, for each Algorithm 2 AugmentStatement (a, so, sd, sr) Input: statement a, origin state so, destination state sd, return state sr 1 if a is variable declaration statement ∨ a is event statement ∨ a is expression statement then 2 add transition from so to sd with action a 3 else if a is return statement then 4 add transition from so to sr with action a 5 else if a is compound statement {a1; a2; . . . ; aN } then 6 for i = 1, 2, . . . , N − 1 do 7 add state si 8 end for 9 AugmentStatement(a1, so, s1, sr ) 10 for i = 2, 3, . . . , N − 1 do 11 AugmentStatement(ai, si−1, si, sr ) 12 end for 13 AugmentStatement(aN , sN−1, sd, sr) 14 else if a is selection statement if (c) aT else aF then 15 add state sT 16 add transition from so to sT with guard c 17 AugmentStatement(aT , sT , sd, sr) 18 add state sF 19 add transition from so to sF with guard !(c) 20 AugmentStatement(aF , sF , sd, sr) 21 else if a is selection statement if (c) aT then 22 add state sT 23 add transition from so to sT with guard c 24 AugmentStatement(aT , sT , sd, sr) 25 add transition from so to sd with guard !(c) 26 else if a is loop statement for (aI ; c; aA) aB thenthen 27 add states sI, sC, sB 28 AugmentStatement(aI, so, sI, sr ) 29 add transition from sI to sd with guard !(c) 30 add transition from sI to sC with guard c 31 AugmentStatement(aB, sC, sB, sr ) 32 AugmentStatement(aA, sB, sI, sr ) 33 else if a is loop statement while (c) aB then 34 add state sL 35 add transition from so to sd with guard !(c) 36 add transition from so to sL with guard c 37 AugmentStatement(aB, sL, so, sr ) 38 end if Algorithm 3 AugmentModel (D, S, SF , s0, V, T ) Input: model (D, S, SF , s0, V, T ) Result: model (D, S, SF , s0, V, T ) 1 for transition t ∈ T do 2 remove transition t 3 add state sgrd 4 add transition from tfrom to sgrd with guard gt 5 if action at cannot raise exception then 6 AugmentStatement(at, sgrd, tto, tto) 7 else 8 add transition from sgrd to tfrom with guard “revert” 9 add state srvrt 10 add transition from sgrd to srvrt with guard “!revert” 11 AugmentStatement(at, srvrt, tto, tto) 12 end if 13 end for original transition, it first removes the transition, then adds a state sgrd and a transition from the origin to sgrd with the original guard. If the action contains a statement that can result in an exception, the algorithm also adds a state srvrt, a transition from state sgrd to state srvrt, and a transition from state sgrd to the origin state. During verification, our tool considers the possibility of the entire transition being reverted using this branch. Finally, the algorithm invokes AugmentStatement with the original action and original destination.
Appears in 1 contract
Sources: Smart Contract