Check out the new USENIX Web site. next up previous
Next: About this document ... Up: Detecting Format String Vulnerabilities Previous: Bibliography

A. Proof of Theorem 4.1

Theorem A.1   Let $ (P,\leq)$ be any finite partial order. Let $ (2^{\mathbb{N}},
\subseteq)$ be the lattice of subsets of $ \mathbb{N}$ with the set inclusion ordering. Then there exists a mapping $ \phi : P \rightarrow
2^{\mathbb{N}}$, such that $ \forall x,y \in P, x \leq y \iff
\phi(x) \subseteq \phi(y)$ and $ \phi(x)$ is a finite subset of $ \mathbb{N}$ for all $ x \in P$.

Proof : We prove the theorem by induction on $ \vert P\vert$.
Base Case : Let $ \vert P\vert$ = 1. Then the claim trivially holds.
Induction Hypothesis : Let the claim hold for all $ P$ such that $ \vert P\vert \leq k$.
Induction Step : $ \vert P\vert
= k+1$.
Let $ (P,\leq)$ be a partial order such that $ \vert P\vert =
k+1$. Since $ P$ is finite, $ P$ has a minimal element, say $ a$. Consider the partial order $ (P\setminus \{a\},\leq)$. Clearly this is a partial order and $ \vert P\setminus \{a\}\vert = k$. Hence by induction hypothesis, there exists $ \phi : P\setminus \{a\}
\rightarrow 2^{\mathbb{N}}$, such that $ \forall x,y \in P\setminus
\{a\} , x \leq y \iff \phi(x) \subseteq \phi(y)$ and $ \phi(x)$ is a finite subset of $ \mathbb{N}$ for all $ x \in P\setminus \{a\}$. Let $ n
= \max_i\{i\in \cup_{x \in P\setminus \{a\}\}} \phi(x) \}$. Define $ \phi' : P \rightarrow 2^{\mathbb{N}}$ as follows.

$\displaystyle \phi'(x) = \left\{ \begin{array}{ll}
\{n+1\} & \mathrm{if} x = a\...
...;\mathrm{and}\; x \leq
a\\
\phi(x) & \mathrm{otherwise}\\
\end{array}\right.
$

Since $ a$ was chosen to be a minimal element, the only relations involving $ a$ are of the form $ a \leq x$, and for these, by definition, $ \phi'(a) = \{n+1\} \subseteq \phi(x) \cup \{n+1\} =
\phi'(x)$. For all $ x$ such that $ a \not\leq x$, we have $ \phi'(a)
= \{n+1\} \not\subseteq \phi(x)$ by choice of $ n$. For relations not involving $ a$, the show below that the set containment relations are preserved. Let $ \phi(x) \subseteq \phi(y)$. Since $ \phi'(y)
\supseteq \phi(y)$, the case when $ \phi'(x) = \phi(x)$ is trivial. So assume $ \phi(x) \subseteq \phi(y)$ and $ \phi'(x) = \phi(x) \cup \{n+1\}$. This implies that $ a \leq x$, and $ x \leq y$, and therefore $ a
\leq y$. Thus $ \phi'(y)$ would be defined as $ \phi(y)\cup
\{n+1\}$, and hence $ \phi'(x) \subseteq \phi'(y)$.Thus the induction step holds.


next up previous
Next: About this document ... Up: Detecting Format String Vulnerabilities Previous: Bibliography
Umesh Shankar 2001-05-16