# Semantics-based obfuscation

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 ?

Actually both bubble-sort and quick-sort have a very important common semantic property, i.e. they both sort arrays of elements (on which there is a total order relation defined). Of course they also have other properties such as average complexity for a specific input and the concrete execution trace, which will be different for most inputs in the input space of sorting algorithms.

Analogously to section 3.1 of the Semantic-based Code Obfuscation paper:

• Take a sorting program P (be it bubble-sort)
• Apply an obfuscation transformation t1 on the program P which produces t1(P) (be it quick-sort)
• Apply another obfuscation transformation t2 on the program P which produces t2(P) (be it insertion-sort)
• The approximation of the concrete trace semantics of P is diﬀerent from the same approximation for the concrete trace semantics of t1(P) and of t2(P)
• Define a property \alpha, which observes the length of the program traces
• Define another property \beta, which observes the average run-time of the 3 programs.
• The transformation t1 obfuscates both \alpha and \beta which are both part of O(t1), while still preserving the common semantic property of sorting for both P and t(P)
• The transformation t2 obfuscates only \alpha, while \beta is not, since the average run-time complexity is the same for both P and t2(P).

Therefore, we conclude that transformation t1 is more potent than t2, because it hides more properties of P.