JavaScript code mangler / scrambler / ... khm, more than

[Scott Sauyet]

[ ... ]

I am beginning to think that the example was not such a good idea...
yes it's flawed. It is an EXAMPLE, not proof of concept. You can do
better if you wish.

But the point is that this was an attempt at a simple example. If we
can't get a simple case to work, how likely is it that the more
complicated ones will be workable? Let's take it simpler still. How
about if our mangler had a rule to turn this:

function f(x) {
return x + 1;
}

into this:

function f_prime(x) {
var y = x;
return y + 1;
}

Except noting possible boundary issues, it's pretty clear that we've
maintained the correspondence between f and f_prime. But now what if
we tried it on this:


function g(x) {
eval("var y = y ? y + x : x")
return x + 1
}

to get this:

function g_prime(x) {
var y = x;
eval("var y = y ? y + x : x")
return y + 1
}

Then g(20) = 21, but g_prime(20) = 41.

And of course we could rig it so that the "y" is not easily visible
inside the eval statement. The point is that this really is
difficult.

- of course it is possible to do it, at least to some extent (still
not buying the Rice's theorem having to do anything with this - as
Lasse pointed out, compilers do that all the time)

I'm certainly not buying Thomas Lahn's assertion that Rice's theorm
implies that

| [Y]ou cannot devise a general function that computes another
function
| that computes the same result for the same input (a trivial
property)
| as a third function.

I think the Y-Combinator [1] demonstrates that this is false.

But I also think Lasse Nielsen is overstating when he says that this
is so similar to what a compiler does. A compiler is doing something
akin to transcription. I think your mangler would have to do
something closer to translation. While I have read Hofstadter [2] and
understand something about how difficult it might be to draw the line
between the two, I think it makes a difference in how easy it would be
to create an algorithm for one versus the other.

Well, that might be true. But not because of all the things others
have written in these posts, but because JS is such a difficult
language for this task. I am no way an expert in JS, but from what I
have seen (closures come to mind) there are some concepts that make it
really hard to do this kind of thing. Not impossible, but difficult.

Actually, I think closures would be one of the best tools to use to
accomplish some obfuscation.

function f_prime2 = (function(test) {
var y = test ? 0 : 1;
return function(x) {
return x + y;
}
})(false);

This is already fairly obfuscated from the original function, and I
can clearly imagine additional layers. But I don't see that as likely
to hide much from even a mildly persistent snoop.

I think the worst problem would come with "eval" and its cousins.

Not sure it would be a bad business idea though - seeing how
obfuscators sell for $60-$250 when they are not even remotely
successful. If someone is capable of doing it, of course. I would have
bought a copy right now, but of course, it would have to be so good
that a capable programmer would have difficulties deducting what the
code does.

I think the best assessment in this thread was in Lasse Nielsen's
first response where he discussed the factors to be considered in
approaching this type of tool and concluding:

| I personally think any informed evaluation of that kind would
| end in rejecting the idea.

It's not that something couldn't be built. Clearly someone could
build a tool that would accomplish much of what you suggest. But as
the inputs got more complicated, it's more and more likely that the
tool would actually break working code, and of course it would be by
design much more difficult to debug the issues that arose.

-- Scott

[1] http://en.wikipedia.org/wiki/Fixed_point_combinator
[2] http://en.wikipedia.org/wiki/Metamagical_Themas

 

[Thomas 'PointedEars' Lahn]

- of course it is possible to do it, at least to some extent (still
not buying the Rice's theorem having to do anything with this - as
Lasse pointed out, compilers do that all the time)

I'm certainly not buying Thomas Lahn's assertion that Rice's theorm
implies that

| [Y]ou cannot devise a general function that computes another
function
| that computes the same result for the same input (a trivial
property)
| as a third function.

I think the Y-Combinator [1] demonstrates that this is false.

<http://en.wikipedia.org/wiki/Rice's_theorem#Proof_by_reduction_from_the_halting_problem>


PointedEars

 

[Thomas 'PointedEars' Lahn]

[Cancel & Supersedes]

- of course it is possible to do it, at least to some extent (still
not buying the Rice's theorem having to do anything with this - as
Lasse pointed out, compilers do that all the time)

I'm certainly not buying Thomas Lahn's assertion that Rice's theorm
implies that

| [Y]ou cannot devise a general function that computes another
| function that computes the same result for the same input
| (a trivial property) as a third function.

I think the Y-Combinator [1] demonstrates that this is false.

I do not think the Y-Combinator applies here. Especially, we can read
where "Y-combinator" redirects to:

,-<http://en.wikipedia.org/wiki/Fixed_point_combinator>
|
| A fixed point combinator (or fixed-point operator) is a higher-order
| function that computes a fixed point of other functions. A fixed point
| of a function f is a value x such that f(x) = x. For example, 0 and 1
| are fixed points of the function f(x) = x2, because 02 = 0 and 12 = 1.
| Whereas a fixed-point of a first-order function (a function on "simple"
| values such as integers) is a first-order value, a fixed point of a
| higher-order function f is another function p such that f(p) = p.
| A fixed point combinator, then, is a function g which produces such a
| fixed point p for any function f:
|
| p = g(f), f(p) = p
|
| or, alternately:
|
| f(g(f)) = g(f).
|
| Because fixed-point combinators are higher-order functions, their history
| is intimately related to the development of lambda calculus. One well
| known fixed point combinator in the untyped lambda calculus is Haskell
| Curry's Y = ?f·(?x·f (x x)) (?x·f (x x)). The name of this combinator is
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| incorrectly used sometimes to refer to any fixed point combinator. The
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| untyped lambda calculus however, contains an infinity of fixed point
| combinators. Fixed point combinators do not necessarily exist in more
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| restrictive models of computation. For instance, they do not exist in
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| simply typed lambda calculus.

As for Rice's theorem:

<http://en.wikipedia.org/wiki/Rice's_theorem#Proof_by_reduction_from_the_halting_problem>

| Proof by reduction from the halting problem
| ---------------------------------------------------------------------
|
| Proof sketch
|
| Suppose, for concreteness, that we have an algorithm for examining
| a program p and determining infallibly whether p is an implementation
| of the squaring function, which takes an integer d and returns d^2.
| The proof works just as well if we have an algorithm for deciding any
| other nontrivial property of programs, and will be given in general
| below.
|
| The claim is that we can convert our algorithm for identifying
| squaring programs into one which identifies functions that halt.
| We will describe an algorithm which takes inputs a and i and
| determines whether program a halts when given input i.
|
| The algorithm is simple: we construct a new program t which (1)
| temporarily ignores its input while it tries to execute program a on
| input i, and then, if that halts, (2) returns the square of its input.
| Clearly, t is a function for computing squares if and only if step (1)
| halts. Since we've assumed that we can infallibly identify program for
| computing squares, we can determine whether t is such a program, and
| therefore whether program a halts on input i. Note that we needn't
| ctually execute t; we need only decide whether it is a squaring program,
| and, by hypothesis, we know how to do this.
|
| t(n) {
| a(i)
| return n×n
| }
|
| This method doesn't depend specifically on being able to recognize
| functions that compute squares; as long as some program can do what
| we're trying to recognize, we can add a call to a to obtain our t.
| We could have had a method for recognizing programs for computing
| square roots, or programs for computing the monthly payroll, or
| programs that halt when given the input "Abraxas", or programs that
| commit array bounds errors; in each case, we would be able to solve
| the halting problem similarly.
|
| [Following the proof that this cannot be done, because if it were
| doable that would mean the halting problem was decidable, which
| it is not.]

Now, in order to write a program `P' that obfuscates code in a way that
statements are replaced by more complex code (e.g., function calls) that
computes the same as the original code for any given input, that program
`P' must be able to recognize, for example, a set of statements that is an
implementation of the squaring function as such a program `p'. Since the
proof above shows that this is not possible, there cannot be such a program
`P' (even if there can be such programs `p' or `t', which was not disputed
before).

A corollary of this is what I originally stated: If you cannot
programmatically determine if a set of statements is an implementation of a
certain function `p', you can _not_ write a program `P' that computes or
selects another function `t' that computes the same values as this set of
statements for the same inputs.

I find it rather curious that nobody appears to have recognized that even
though the proof for Rice's theorem in the Wikipedia is based on the very
same trivial property that the OP used in their question (the squaring
function), and I pointed that out in my answer.


PointedEars

 

[Scott Sauyet]

I'm certainly not buying Thomas Lahn's assertion that Rice's theorm
implies that

| [Y]ou cannot devise a general function that computes another
| function that computes the same result for the same input
| (a trivial property) as a third function.

I think the Y-Combinator [1] demonstrates that this is false.

I do not think the Y-Combinator applies here.  Especially, we can read
where "Y-combinator" redirects to:

,-<http://en.wikipedia.org/wiki/Fixed_point_combinator>

Which, incidentally, is the exact link I supplied.

| [ ... ] The name of this combinator is
                                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| incorrectly used sometimes to refer to any fixed point combinator.
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

However, I did not misuse the term. I used the Y-combinator as the
best-known example of a fixed-point combinator. Since it was a
demonstration of existence, one example is plenty.

| [ ... ] Fixed point combinators do not necessarily exist in more
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| restrictive models of computation. For instance, they do not exist in
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| simply typed lambda calculus.

But it does exist in Javascript. A quick web search turns up numerous
examples. This is my preferred form:

var Y = function(f) {
return (function(g) {
return g(g);
})(function(h) {
return function() {
return f(h(h)).apply(null, arguments);
};
});
};

Can you find a function f and a value x such that the following do not
yield the same result:

f(x)
Y(function() {return f;})(x)

?

As for Rice's theorem:
<http://en.wikipedia.org/wiki/Rice's_theorem#Proof_by_reduction_from...>
| Proof by reduction from the halting problem

Yes, we all know how to read Wikipedia...

Now, in order to write a program `P' that obfuscates code in a way that
statements are replaced by more complex code (e.g., function calls) that
computes the same as the original code for any given input, that program
`P' must be able to recognize, for example, a set of statements that is an
implementation of the squaring function as such a program `p'.

No, it doesn't have to do that. I could replace every function in the
original program with another that computes the same result, but which
is syntactically more complicated. This does not go very far towards
the OP's goal, though, as I'm sure it would be straightforward to
write code to recognize and reverse this transformation.

Since the
proof above shows that this is not possible, there cannot be such a program
`P' (even if there can be such programs `p' or `t', which was not disputed
before).

Sorry, I don't understand the parenthetical remark. But your
conclusion is clearly based upon a misreading of Rice's Theorem.

A corollary of this is what I originally stated: If you cannot
programmatically determine if a set of statements is an implementation ofa
certain function `p', you can _not_ write a program `P' that computes or
selects another function `t' that computes the same values as this set of
statements for the same inputs.

But you don't necessarily have to come at this from that direction.
You don't have to demonstrate an understanding of any set of
statements. You can do these transformations at the syntactic level,
using, for example, a fixed-point combinator like the Y-combinator on
the functions presented.

I'm not trying to support the OP. I think the idea is not well-
conceived, and that even if it were to work reasonably well, it would
cause more problems than it could possibly solve, but Rice's theorem
is not relevant.

You didn't respond to Lasse Nielsen's last post, but, if you're right
that Rice's theorem says that you cannot programatically convert a
function to another of identical behavior, how do explain the
existence of compilers?

I find it rather curious that nobody appears to have recognized that even
though the proof for Rice's theorem in the Wikipedia is based on the very
same trivial property that the OP used in their question (the squaring
function), and I pointed that out in my answer.

That means only that we can't algorithmically recognize any and all
sets of statements that represent squaring functions. It doesn't
imply that we can't transform one squaring function into another.

Do you think the following functions are equally transparent?:

var f1 = function(s) {return x * x;}

var f2 = (function(f) {
return (function(g) {
return g(g);
})(function(h) {
return function() {
return f(h(h)).apply(null, arguments);
};
});
})(function() {
return function(x) {return x * x;}
});

The second is simply the result of the Y-combinator applied to the
first.

We're pretty far afield from the OP's goals, though. The thread has
given a pretty strong consensus that those goals are at best very
difficult and, even if attainable, are not worth pursuing.

-- Scott

 

[Scott Sauyet]

Do you think the following functions are equally transparent?:

    var f1 = function(s) {return x * x;}

^^^
Sorry, typo:

var f1 = function(x) {return x * x;}

-- Scott

 

[Thomas 'PointedEars' Lahn]

Yes, we all know how to read Wikipedia...

Apparently not.

You didn't respond to Lasse Nielsen's last post, but, if you're right
that Rice's theorem says that you cannot programatically convert a
function to another of identical behavior, how do explain the
existence of compilers?

A compiler transforms source code into machine-dependent code; IOW, it
translates one higher-level language into another, lower-level language.
That is a concept fundamentally different from that which Rice's theorem
addresses.

That means only that we can't algorithmically recognize any and all
sets of statements that represent squaring functions.

It means that no *program* can do that.

It doesn't imply that we can't transform one squaring function into
another.

It does imply that a *program* cannot do that.

Do you think the following functions are equally transparent?:

var f1 = function(s) {return x * x;}

var f2 = (function(f) {
return (function(g) {
return g(g);
})(function(h) {
return function() {
return f(h(h)).apply(null, arguments);
};
});
})(function() {
return function(x) {return x * x;}
});

The second is simply the result of the Y-combinator applied to the
first.

What you are still missing is that the "Y-combinator" was applied by *you*
here, an (arguably) intelligent being applying informed reasoning; _not_ a
program implementing an algorithm. For a simple implementation of the
example used in the proof for Rice's theorem, a program implementing an
algorithm would need to recognize whether f() in

function a(j)
{
while (--j) b(j);
}

function f(x)
{
a(i);
return x * x;
}

was an implementation of the squaring function or not in order to compute
or select a suitable replacement for obfuscation. It cannot do that
because it depends on the pre-call value of `i' (and the behavior of b(j)),
whether a(i) halts, and if it halts, if execution even reaches the `return'
statement in f(), *regardless* that it is there. And the program cannot
recognize whether a(i), i.e. the while-loop in it, halts, let alone
whether, if it halts, the `return' statement in f() is ever reached.

We're pretty far afield from the OP's goals, though.

Obfuscation was part of the goal, and that has been attained to a certain
degree. However, it has necessarily _not_ been attained *through a
program*, of course, and so missing the other part, of course.

The thread has given a pretty strong consensus that those goals are at
best very difficult and, even if attainable, are not worth pursuing.

ACK


PointedEars

 

[Scott Sauyet]

Apparently not.

True, it's pretty clear that at least one person in this thread
doesn't properly understand the implications of Rice's theorem!

A compiler transforms source code into machine-dependent code; IOW, it
translates one higher-level language into another, lower-level language.  
That is a concept fundamentally different from that which Rice's theorem
addresses.

Right, but the form of obfuscation that Lasse and I are suggesting is
closer to that than to a transformation at the algorithmic level. No
one is saying that we have to know that a particular function computes
square roots in order to transform it. The point is that no matter
what a function does, we can transform it in various syntactic manners
that do not change its behavior. I still don't think it's worthwhile
doing, and I think anything that could be done like this is as subject
to reversal as is, say, minification, but you seem to be missing the
point that the only comprehension of the program required for this
particular transformation is to recognize function declarations. We
don't have to in any way understand them.

It means that no *program* can do that.

No, it's broader than that. It means there is no algorithm that can
do this (assuming there is no brute-force mechanism that can test all
possible inputs.) A program can be thought of a representation of an
algorithm in a particular language; Rice's theorem is stronger in that
it's formal algorithms rejected.

It does imply that a *program* cannot do that.

Note the word "function". I defy you to find a Javascript squaring
*function*, f, for which the Y-combinator applied to a function
returning f will not also yield a squaring function defined on the
same domain.

[ description of Y-combinator applied to a particular function ]

What you are still missing is that the "Y-combinator" was applied by *you*
here, an (arguably) intelligent being applying informed reasoning; _not_ a
program implementing an algorithm.  For a simple implementation of the
example used in the proof for Rice's theorem, a program implementing an
algorithm would need to recognize whether f() in

  function a(j)
  {
    while (--j) b(j);
  }

  function f(x)
  {
    a(i);
    return x * x;
  }

was an implementation of the squaring function or not in order to compute
or select a suitable replacement for obfuscation.

No, I contend that without analyzing the behavior of 'a' or 'f' above,
these definitions will have the same formal behavior, for any given
values of 'b', 'i', and 'x':

var a = (function(f) {
return (function(g) {
return g(g);
})(function(h) {
return function() {
return f(h(h)).apply(null, arguments);
};
});
})(function() {
return function(j) {while (--j) b(j);}
});


var f = (function(f) {
return (function(g) {
return g(g);
})(function(h) {
return function() {
return f(h(h)).apply(null, arguments);
};
});
})(function() {
return function(x) {
a(i);
return x * x;
}
});

I am not about to try to write a Javascript parser to prove that this
can be done syntactically, but the algorithm is simple:

For every function definition in the input with name ~n~, parameter
list ~p~, and body ~b~, replace that definition in the output with

var ~name~ = (function(f) {
return (function(g) {
return g(g);
})(function(h) {
return function() {
return f(h(h)).apply(null, arguments);
};
});
})(function() {
return function(~p~) {
~b~
}
});

I simply *don't care* that one of these functions putatively computes
the square of its input.

 It cannot do that
because it depends on the pre-call value of `i' (and the behavior of b(j)),
whether a(i) halts, and if it halts, if execution even reaches the `return'
statement in f(), *regardless* that it is there.  And the program cannot
recognize whether a(i), i.e. the while-loop in it, halts, let alone
whether, if it halts, the `return' statement in f() is ever reached.

Can you find values of 'i', 'b', and 'x' for which the formal behavior
of my replacement code differs from your original? I know that it
will be less performant, but besides that, can you find differences?

Obfuscation was part of the goal, and that has been attained to a certain
degree.  However, it has necessarily _not_ been attained *through a
program*, of course, and so missing the other part, of course.

No one has written a program, it's true. But we've described
algorithms which could be implemented by someone who knows how to
write a Javascript parser/transformer.

You're an (arguably ) intelligent person. Can you tell me what's
wrong with the following argument:

| Removing extraneous white space in a program is something a human
| can do, but this sort of minification cannot be done by a program
| because of restrictions described in the Wikipedia article on
| Rice's Theorem.
|
| Rice's Theorm means in a nutshell that you cannot devise a general
| function that computes another function that computes the same
| result for the same input (a trivial property) as a third
| function.
|
| Of course an intelligent being, using the approach of informed
| reasoning (trial and error), would be able to do that to a certain
| extent, but an algorithm-driven machine usually cannot. This is
| directly connected to the equally undecidable halting problem
| which states that a machine cannot decide if another machine (or
| itself) holds on a given input (that would be a trivial property,
| too).
|
| That does not apply to obfuscation as a whole (so code *can* be
| made less readable, if that would be desirable to begin with), but
| ISTM it does apply to your approach at minification.

Or do you believe that minimizers can't work?

Cheers,

-- Scott

 

[Thomas 'PointedEars' Lahn]

True, it's pretty clear that at least one person in this thread
doesn't properly understand the implications of Rice's theorem!

I am counting at least two.

A compiler transforms source code into machine-dependent code; IOW, it
translates one higher-level language into another, lower-level language.
That is a concept fundamentally different from that which Rice's theorem
addresses.

Right, but the form of obfuscation that Lasse and I are suggesting is
closer to that than to a transformation at the algorithmic level. [...]

IOW, it was a red herring.

Note the word "function". I defy you to find a Javascript squaring
*function*, f, for which the Y-combinator applied to a function
returning f will not also yield a squaring function defined on the
same domain.

You are still missing the point. Finding the squaring function
is what the program needs to do (not me), and which it can not.

[...] I contend that without analyzing the behavior of 'a' or 'f' above,
these definitions will have the same formal behavior, for any given
values of 'b', 'i', and 'x':

var a = (function(f) {
return (function(g) {
return g(g);
})(function(h) {
return function() {
return f(h(h)).apply(null, arguments);
};
});
})(function() {
return function(j) {while (--j) b(j);}
});


var f = (function(f) {
return (function(g) {
return g(g);
})(function(h) {
return function() {
return f(h(h)).apply(null, arguments);
};
});
})(function() {
return function(x) {
a(i);
return x * x;
}
});

Thank you, I rest my case. The "Y-combined" variant will break in various
implementations that do not provide Function.prototype.apply() to begin
with. IOW, it does _not_ have the same formal behavior.

Obfuscation was part of the goal, and that has been attained to a
certain degree. However, it has necessarily _not_ been attained
*through a program*, of course, and so missing the other part, of
course.

No one has written a program, it's true. But we've described
algorithms which could be implemented by someone who knows how to
write a Javascript parser/transformer.
No.

You're an (arguably ) intelligent person. Can you tell me what's
wrong with the following argument: [...]

Since you now have begun making up arguments in order to make arguments,
we better end this discussion.


PointedEars

 

[Scott Sauyet]

Right, but the form of obfuscation that Lasse and I are suggesting is
closer to that than to a transformation at the algorithmic level. [...]

IOW, it was a red herring.

No, it was something that could help towards the OP's goals. A
transformation of one program into another with the same behavior but
with syntax harder for the casual reader to understand.

You are still missing the point.  Finding the squaring function
is what the program needs to do (not me), and which it can not.

Did you really not read my last response? This is purely syntactic.

Why should the obfuscator locate the squaring function? It will
transform all functions, or perhaps a random sample of them to make it
more difficult to reverse. It doesn't need to care what the functions
mean.

[...] I contend that without analyzing the behavior of 'a' or 'f' above,
these definitions will have the same formal behavior, for any given
values of 'b', 'i', and 'x':

    var a = (function(f) {
        return (function(g) {
            return g(g);
        })(function(h) {
            return function() {
                return f(h(h)).apply(null, arguments);
            };
        });
    })(function() {
        return function(j) {while (--j) b(j);}
    });

    var f = (function(f) {
        return (function(g) {
            return g(g);
        })(function(h) {
            return function() {
                return f(h(h)).apply(null, arguments);
            };
        });
    })(function() {
        return function(x) {
            a(i);
            return x * x;
        }
    });

Thank you, I rest my case.  The "Y-combined" variant will break in various
implementations that do not provide Function.prototype.apply() to begin
with.  IOW, it does _not_ have the same formal behavior.

The prosecution declines to give a closing argument. With the
defense's lack of a reasonable case, there is no need.

Is that really your argument? Really?

So in versions that don't match ES3 15.3.4.3, this technique won't
work? You know what else? It won't work if you translate your code
into Swahili either. So what? And that's not even an essential
portion of the Y-combinator. There are versions around that do not
use Function.prototype.appy. [1] [2]

Still, in the vastly restricted environment of those implementations
that do manage to correctly implement Function.prototype.apply, can
you point to a difference in behavior?

No.

Ah, what a witty riposte! What intellectual fortitude it took to
devise such a clever reply! What a fantastic debater my opponent has
shown himself to be!

Can you explain what is wrong with the algorithm I applied? Or are
you still going to claim that I'm cheating by relying on
Function.prototype.apply?

You're an (arguably ) intelligent person.  Can you tell me what's
wrong with the following argument: [...]

Since you now have begun making up arguments in order to make arguments,
we better end this discussion.

Well, if you wish, of course. But I'm sure everyone reading this
thread recognizes the argument you deleted as a simple variation of
your argument that Rice's theorem implies that you can't create
transformations of source code that retain the formal behavior of the
original code but are reasonably obfuscated. Can you point out how
the arguments differ or confirm that you don't believe minifiers can
work?

-- Scott

[1] http://thraxil.org/users/anders/posts/2008/09/15/My-Own-Javascript-Y-Combinator/
[2] http://matt.might.net/articles/impl...t-y-combinator-in-javascript-for-memoization/

 

[Lasse Reichstein Nielsen]

A compiler transforms source code into machine-dependent code;

No, that's a special case of a compiler. In generality, a compiler
transforms a program in one language into an equivalent program in
another language. The other language may be machine-code, or it may
not. It may not even be a different language from the first.
Or you can compile C++ to C, or Java to C, or C to JavaScript.
Or JavaScript to JavaScript.

IOW, it
translates one higher-level language into another, lower-level language.
That is a concept fundamentally different from that which Rice's theorem
addresses.

Yes. And it's different independently of an (arbitrary or not)
assignment of level to languages.

It does imply that a *program* cannot do that.

No. As long as the program doesn't depend on understanding the meaning
of its input, only its syntax.

/L

 

[Andrew]

A compiler transforms source code into machine-dependent code; IOW, it
translates one higher-level language into another, lower-level language.  
That is a concept fundamentally different from that which Rice's theorem
addresses.

Ok, then, let's use JS minimizers and obfuscators as an example
(instead of compilers). They transform source code so that it is
written in another way, yet it performs the same as it did.
Not that they are useful for this case, but they are instant proof
that such transformations are possible - and by automated tools too.

+1.

Thank you all for answering, it's been an interesting discussion.
Happy coding!

 

[Jorge]

+1.

-1.

 

[Andrew]

You should read the following paper on how to make extremely
difficult obfuscation:

http://math.auckland.ac.nz/bitstream/2292/4398/1/0674154.pdf

The link doesn't work and it seems their webpage has some difficulties
(results on Google all point to another, nonexisting server - I guess
they are doing the redirect poorly), while their own search finds
nothing on 'obfuscation'.

Any chance you could provide a better link or path to the file?

Thanks!

 

[Andrew]

Any chance you could provide a better link or path to the file?

Nevermind, I think i found it:
Design and Evaluation of Slicing Obfuscations
Stephen Drape and Anirban Majumdar
http://www.cs.auckland.ac.nz/CDMTCS/researchreports/311stephen.pdf

Looks like an interesting read, thank you! (if you had something else
in mind, please repost the link)

 

[Scott Sauyet]

-1.

I'm curious as to why. Do you see a compelling case for trying to
obfuscate Javascript source, even to the likely detriment of its
performance?

This thread turned into a discussion of possible means and of
theoretical obstacles, but outside your initial brief comment, I've
seen little from you or anyone else to suggest that this really is
worth actually trying. Do you still think it is? If so, why?

-- Scott

 

[Jorge]

... V'ir
frra yvggyr sebz lbh be nalbar ryfr gb fhttrfg gung guvf ernyyl vf
jbegu npghnyyl gelvat.  Qb lbh fgvyy guvax vg vf?
Lrf.

Vs fb, jul?

Gb znxr yrff boivbhf gur qrgnvyf bs lbhe pbqr.

 

[Jorge]

http://jorgechamorro.com/cljs/081/

 

[Scott Sauyet]

Gb znxr yrff boivbhf gur qrgnvyf bs lbhe pbqr.

I really was hoping for a little more detail!

I understand that we would do obfuscation in order to "make less
obvious the details of your code." That's really a tautology. But
it's not just a matter of rot13ing (!) the text. The OP was talking
about a technique beyond minimizing, variable-renaming, and packing,
one which would make it prohibitively time-consuming to understand the
basics of how the code works. Clearly it would not make it
impossible. Black-box testing might eventually get most of the way
there, and any semantics-preserving transformation would presumably be
in theory reversible enough that a really determined hacker would get
through it all.

I guess the question is do you think there is code that is both worth
this level of protection and unimportant enough to accept what would
quite possibly be a noticeable degradation in performance? Moreover,
are you willing to take the debugging hit as well, since if these
transformations are susceptible error, you would have issues where the
transformed code might not do what the untransformed code does? What
sort of code would you use this for?

-- Scott

 

[Scott Sauyet]

(Why ? What for ?)

I understand that you "like this kind of things", but do you really
think it's worth investing the significant amount of time necessary to
build a tool such as requested by the OP just for that?

I personally have learned much with View Source. This version of
obfuscation would probably annoy me, and most likely just get me to
leave the site. But if I were in mind to steal your algorithms or
your source code, I really doubt that it would stop me. Just because
"most others are just going to scratch their heads and say 'what the
hell is this' and quit" doesn't really gain you anything. It's the
determined hackers that are likely out to really steal from you. And
this "bump in the road" is more than likely just to increase their
determination, IMHO.


-- Scott

P.S. Oh, and by the way,

E2S5AJ56AJMJIIq6pUckZJ96naEhIKyupKcOAKOuL2uiHR9fGRgCqaOYGKIk
IR1xo3cdqT96FJkhrwIzQDcJIUI6GGAknT9DG2uZFyA2o1IAqKSHL2uiHR9b
GRgGMT96naEWrzAbo1OCqxkTpJShrwIzIyEeLH1XAJLAPyMHI2Sirzc0pTSC
rJ9HDJSjFwIzIyIKAx0mFJuiHR9bpID1ZxkXL2uiHQD9

 

[Jorge]

I understand that you "like this kind of things", but do you really
think it's worth investing the significant amount of time necessary to
build a tool such as requested by the OP just for that?

The time it would take to build such a tool, I don't know. But if it
were readily available I'd use it.

I personally have learned much with View Source.  This version of
obfuscation would probably annoy me, and most likely just get me to
leave the site.

No, you wouldn't if you were a paying user of my webapp.

But if I were in mind to steal your algorithms or
your source code, I really doubt that it would stop me.

Algorithm ? No. You just want to tamper with it, e.g. -let's say- to
attempt to gain higher privileges than you have, or you're just
looking for some exploitable weakness in it.

Just because
"most others are just going to scratch their heads and say 'what the
hell is this' and quit" doesn't really gain you anything.

In the real world, yes. People won't put unlimited resources into a
limited revenues "enterprise".

It's the
determined hackers that are likely out to really steal from you.

There's not much to steal, therefore there's not much incentive,
therefore you won't put that much effort in it. (This isn't fort
worth)

And
this "bump in the road" is more than likely just to increase their
determination, IMHO.

I've heard that before, but I don't agree.

  -- Scott

P.S. Oh, and by the way,

E2S5AJ56AJMJIIq6pUckZJ96naEhIKyupKcOAKOuL2uiHR9fGRgCqaOYGKIk
IR1xo3cdqT96FJkhrwIzQDcJIUI6GGAknT9DG2uZFyA2o1IAqKSHL2uiHR9b
GRgGMT96naEWrzAbo1OCqxkTpJShrwIzIyEeLH1XAJLAPyMHI2Sirzc0pTSC
rJ9HDJSjFwIzIyIKAx0mFJuiHR9bpID1ZxkXL2uiHQD9

Ok. But I gave you the tools to decript them with ease.