src/site/apt/definition.apt

   1  ----
   2  Definitions
   3  ----
   4  Haruaki Tamada
   5  ----
   6  2007-06-11
   7  ----
   8
   9 Definitions
  10
  11  A birthmark is unique and native characteristics of a program.  For
  12 pair of programs <p> and <q>, if <q> has the same birthmark as <p>'s,
  13 <q> is suspected as a <<copy>> of <p>.  Ideally, the birthmarks should
  14 satisfy the following properties:
  15
  16  [[(a)]] <<preservation>>: the birthmarks should be preserved even
  17 if the original class file is tampered with, and
  18
  19  [[(b)]] <<distinction>>: independent class files must be
  20 distinguished by completely different birthmarks.
  21
  22 *Birthmark
  23
  24  Let <p>, <q> be programs and <f(p)> be a set of characteristics
  25 extracted from <p> by a certain method <f>. Then <f(p)> is called a
  26 <birthmark> of <p> iff both of the following conditions are satisfied.
  27
  28  [[1]]<f(p)> is obtained from <p> itself without any extra information.
  29
  30  [[2]]If <q> is copied from <p>, then <f(p)=f(q)>
  31
  32  First condition means that the birthmark is not extra information and
  33 is required for <p> to run.  Hence, extracting a birthmark does not
  34 require extra code as watermarking does.  Second condition states that
  35 the same birthmark has to be obtained from copied programs.  By
  36 contraposition, if birthmarks <f(p)> and <f(q)> are different, then
  37 <p> is different from <q> holds. That is, we can guarantee that <q> is
  38 not a copy of <p>.
  39
  40  Hopefully, a birthmark will satisfy the following properties.
  41
  42  [[Property 1: Preservation]] For <p'> obtained from <p> by any
  43 program transformation, <f(p) = f(p')> holds.
  44
  45  [[Property 2: Distinction]] For <p> and <q> such that same
  46 specification, if <p> and <q> are written independently, then
  47 <f(p)!=f(q)>.
  48
  49 These properties strengthen Condition 2 of birthmark definition.
  50 First property specifies <preservation property> of the birthmark
  51 against program transformation.  Preservation property specifies that
  52 the same birthmark must be obtained from <p> and converted to <p'>.
  53 However, there exist many ways to transform a program into an
  54 equivalent one. Hence, in reality, it is difficult to extract strong
  55 enough birthmarks to perfectly satisfy preservation property.
  56
  57  Second property specifies the <distinction property> of the
  58 birthmark, stating that: even though the specification of <p> and <q>
  59 is the same, if implemented separately, different birthmarks should be
  60 extracted.  In general, the detail of two independent programs is
  61 almost never completely the same.  However, in the case that <p> and
  62 <q> are both <tiny> programs, extracted birthmarks could become the
  63 same, even if <p> and <q> are written independently.  Those properties
  64 should be tuned within an allowable range at the user's discretion.
  65