I have some (very blurred as usual) thinking about the semantics obfuscation, that come from this question and the excellent answers of @RolfRolles and @Andrew. As far as I understand, the ideas of the authors in this paper about Semantics-based Code Obfuscation are to study the obfuscation procedures on the semantics-side instead of the syntactic-side. That means, a modification on the code of the program may lead to a modification on the abstract semantics, here the abstract semantics is not the denotational semantics but an abstract representation of the program, received from an abstract interpretation procedure - as a systematic static-analysis method.
To get it more clearly, we consider an example: lets P be a program and t is a transformation preserving the denotational semantics of P, that modifies P into
P' = t(P)
and derives a modification t' on the abstract semantics S of P into
S' = t'(S)
Now we will say that t is potent if there is some properties Prop of P with the corresponding semantics properties SProp of S so that: SProp is not preserved by t'. In other words Prop is lost even through the static-analysis. We can see also that here we are considering the modification on the abstract semantics instead of on the code.
The strength of the code transformation (obfuscator) t is calculated by the set of properties O(t) that are not preserved by t, namely
t1 < t2 iff O(t1) belongs to O(t2)
But (as far as I understand) that implicitly supposed that O(t1) and O(t2) are comparable, I don't say the case where O(t1) and O(t2) are not belong to each other, but the case where each element of O(t1) and O(t2) are not comparable in a rational sense.
For example, we can imagine that in some period before 1960 when nobody knows about quicksort and everybody know bublesort. Suppose that someone wrote a bublesort B and (incidentially) a transformation which modified bublesort into a quicksort Q, since nobody knew about this strange sorting algorithm then they would (rationally) said that it is an obfuscated version of bublesort. However when we apply this situation on the semantics framework above, we can see that the abstract semantics properties of B and Q do not have anything in common (i.e. comparable).
So my question is: How does the semantics-based code obfuscation handle the situation above ?