Next: About this document ...
Up: Detecting Format String Vulnerabilities
Previous: Bibliography
Theorem A.1
Let

be any finite partial order. Let

be the lattice of subsets of

with the set
inclusion ordering. Then there exists a mapping

, such that

and

is a finite subset of

for all

.
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