Next: About this document ...
Up: Detecting Format String Vulnerabilities
Previous: Bibliography
Theorem A.1
Let
![$ (P,\leq)$](img137.png)
be any finite partial order. Let
![$ (2^{\mathbb{N}},
\subseteq)$](img138.png)
be the lattice of subsets of
![$ \mathbb{N}$](img139.png)
with the set
inclusion ordering. Then there exists a mapping
![$ \phi : P \rightarrow
2^{\mathbb{N}}$](img140.png)
, such that
![$ \forall x,y \in P, x \leq y \iff
\phi(x) \subseteq \phi(y)$](img141.png)
and
![$ \phi(x)$](img142.png)
is a finite subset of
![$ \mathbb{N}$](img143.png)
for all
![$ x \in P$](img144.png)
.
Proof :
We prove the theorem by induction on
.
Base Case : Let
= 1. Then the claim trivially holds.
Induction Hypothesis : Let the
claim hold for all
such that
.
Induction Step :
.
Let
be a partial order such that
. Since
is finite,
has a minimal element, say
. Consider the partial order
. Clearly
this is a partial order and
. Hence by
induction hypothesis, there exists
, such that
and
is a
finite subset of
for all
. Let
. Define
as follows.
Since
was chosen to be a minimal element, the only relations
involving
are of the form
, and for these, by
definition,
. For all
such that
, we have
by choice of
. For relations not
involving
, the show below that the set containment relations are
preserved. Let
. Since
, the case when
is trivial. So
assume
and
. This
implies that
, and
, and therefore
. Thus
would be defined as
, and hence
.Thus the induction
step holds.
Next: About this document ...
Up: Detecting Format String Vulnerabilities
Previous: Bibliography
Umesh Shankar
2001-05-16