Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
sav07_lecture_20 [2007/06/05 11:02] kremena.diatchka |
sav07_lecture_20 [2009/05/27 10:28] (current) vkuncak |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Lecture 20: Interprocedural analysis ====== | + | ====== Lecture 20: Interprocedural Analysis - Introduction ====== |
intraprocedural analysis = analysis for language without procedures | intraprocedural analysis = analysis for language without procedures | ||
Line 44: | Line 44: | ||
- must follow protocol: (open (read+write)* close)* | - must follow protocol: (open (read+write)* close)* | ||
- must follow protocol: (startLog stopLog)* | - must follow protocol: (startLog stopLog)* | ||
- | |||
==== Semantics for language with procedure calls ==== | ==== Semantics for language with procedure calls ==== | ||
Line 53: | Line 52: | ||
Let $S$ be the set of program states and $V$ be the set of vertices in the control flow graph. Then we can describe a point in the program as: | Let $S$ be the set of program states and $V$ be the set of vertices in the control flow graph. Then we can describe a point in the program as: | ||
- | $(s,c)$ | + | $(c,s)$ |
- | where $s \in S, c \in V$ | + | where $c \in V, s \in S$ |
Consider the following example: | Consider the following example: | ||
- | Picture will go here. | + | {{lect20_big_step.png|}} |
$p()$ is a procedure which can described by the relation $r$: $\{(x,y), (x',y') | x'=100 \wedge y'=y\}$ | $p()$ is a procedure which can described by the relation $r$: $\{(x,y), (x',y') | x'=100 \wedge y'=y\}$ | ||
Line 66: | Line 65: | ||
Then we can formally define the semantics of a big step ($\mapsto$) as: | Then we can formally define the semantics of a big step ($\mapsto$) as: | ||
- | $(c_{0},s_{1}) \mapsto (c_{3}, s_{2})$ | + | $(c_{1},s_{1}) \mapsto (c_{2}, s_{2})$ |
where $(s_{1},s_{2}) \in r$ iff $(c_{0},s_{1}) \rightarrow (c_{3},s_{2})$ | where $(s_{1},s_{2}) \in r$ iff $(c_{0},s_{1}) \rightarrow (c_{3},s_{2})$ | ||
Line 91: | Line 90: | ||
$(s, l, c, t)$ | $(s, l, c, t)$ | ||
- | Here $l \in L$, where $L$ is the set of local variables of a procedure. Everything would be popped off from $l$ when the procedure returns control to the callee. | + | Here $l \in L$, where $L$ is the set of mappings of local variables of a procedure to their values. Furthermore, on each procedure call, the program pushes $l$ on the stack along with the program point. Everything would be popped off from $l$ when the procedure returns control to the callee. |
One instance where small step semantics would be necessary is in concurrency, so that we can take into account interleaving. | One instance where small step semantics would be necessary is in concurrency, so that we can take into account interleaving. | ||
Line 122: | Line 121: | ||
When a procedure call is encountered, it is replaced by the statements of the procedure (so the procedure code is inlined with the code of the callee). A problem arises when the procedure being inlined is recursive. One approach to dealing with this situation is to inline the recursive procedure a few times, and then treat the recursive call as a havoc statement (as described above). However, even if this is done, inlining increases the size of the code exponentially. | When a procedure call is encountered, it is replaced by the statements of the procedure (so the procedure code is inlined with the code of the callee). A problem arises when the procedure being inlined is recursive. One approach to dealing with this situation is to inline the recursive procedure a few times, and then treat the recursive call as a havoc statement (as described above). However, even if this is done, inlining increases the size of the code exponentially. | ||
- | |||
- | |||
=== Treat procedure calls as goto statements === | === Treat procedure calls as goto statements === | ||
Line 154: | Line 151: | ||
In order to define procedure contracts for ''readContent()'' and ''p1()'' to ensure that this property is satisfied, we introduce an object called ''FileState'' which has a typestate. In typestate systems, the type of an object is allowed to change during its lifetime in the computation. In the paper [[http://lara.epfl.ch/~kuncak/papers/LamETAL05GeneralizedTypestateCheckingDataStructureConsistency.pdf|Generalized typestate checking for data structure consistency]], it says that "unlike standard type systems, typestate systems can enforce safety properties that depend on changing object states". | In order to define procedure contracts for ''readContent()'' and ''p1()'' to ensure that this property is satisfied, we introduce an object called ''FileState'' which has a typestate. In typestate systems, the type of an object is allowed to change during its lifetime in the computation. In the paper [[http://lara.epfl.ch/~kuncak/papers/LamETAL05GeneralizedTypestateCheckingDataStructureConsistency.pdf|Generalized typestate checking for data structure consistency]], it says that "unlike standard type systems, typestate systems can enforce safety properties that depend on changing object states". | ||
- | Therefore ''FileState'' has type ''file'' and two states, ''open'' and ''closed''. Using this notion, we can write the procedure contracts for the two methods as follows: | + | Therefore ''FileState'' has type ''file'' and two states, ''open'' and ''closed''. |
+ | |||
+ | {{lect20_fsm2.png|}} | ||
+ | |||
+ | Using this notion, we can write the procedure contracts for the two methods as follows: | ||
readContent() | readContent() | ||
Line 163: | Line 164: | ||
modifies: FileState | modifies: FileState | ||
ensures: FileState = open | ensures: FileState = open | ||
+ | |||
+ | |||
Line 210: | Line 213: | ||
=== Convergence of automata for reachable configurations === | === Convergence of automata for reachable configurations === | ||
- | One of the main results of this paper is an algorithm which, given a set of states S, computes the set of all predecessors of S, denoted by $pre^{*}(S)$. The states in $pre^{*}(S)$ are regular, i.e. they can be represented using a finite state automaton. | + | One of the main results of this paper is an algorithm which, given a set of states $S$, computes the set of all predecessors of $S$, denoted by $pre^{*}(S)$. The states in $pre^{*}(S)$ are regular, i.e. they can be represented using a finite state automaton. |
In the paper, a pushdown system is defined as a triplet $\mathcal{P} = (P, \Gamma, \Delta)$ where | In the paper, a pushdown system is defined as a triplet $\mathcal{P} = (P, \Gamma, \Delta)$ where | ||
Line 239: | Line 242: | ||
* if $q \stackrel{\w}{\longrightarrow} q''$ and $q'' \stackrel{\gamma}{\longrightarrow} q'$ then $q \stackrel{w\gamma}{\longrightarrow} q'$ | * if $q \stackrel{\w}{\longrightarrow} q''$ and $q'' \stackrel{\gamma}{\longrightarrow} q'$ then $q \stackrel{w\gamma}{\longrightarrow} q'$ | ||
- | $\mathcal{A}$ accepts or recognizes a configuration $\langle p^{i},w \rangle$ if $s^{i} \stackrel{w}{\longrightarrow} q$ for some $q \in F$. The set of configurations recognized by $\mathcal{A}$ is denoted $Conf($\mathcal{A}$)$. As stated before, a set of configurations is regular if it recognized by some MA. | + | $\mathcal{A}$ accepts or recognizes a configuration $\langle p^{i},w \rangle$ if $s^{i} \stackrel{w}{\longrightarrow} q$ for some $q \in F$. The set of configurations recognized by $\mathcal{A}$ is denoted $Conf(\mathcal{A})$. As stated before, a set of configurations is regular if it recognized by some MA. |
+ | |||
+ | Section 2.2 of the paper explains how, given a regular set of configurations $C$ of a PDS $\mathcal{P}$ recognized by an MA $\mathcal{A}$, we can construct another MA $\mathcal{A}_{pre*}$ recognizing $pre^{*}(C)$ (refer to paper for details). | ||
+ | So the idea in the end is to make $C$ include those undesirable (error) states, and then check whether $pre^{*}(C)$ includes the starting state configurations (in other words, whether any of the error states are reachable from the start state). | ||
==== References ==== | ==== References ==== |