JavaScript code mangler / scrambler / ... khm, more than obfuscator... :)
in [JavaScript]
|
Prev: Code Guidelines
Next: JavaScript code mangler / scrambler / ... khm, more than obfuscator... :)
From: Thomas 'PointedEars' Lahn on 22 Dec 2009 16:42 Andrew wrote: > @PointedEars [et al.]: Please don't, this is not a chat or bulletin board on the Web; it is a thread-based discussion medium, a newsgroup, instead. Keep attribution lines that are generated when you post a followup to each separate posting, in which you should only refer to that posting and optionally its precursors (as quoted). <http://jibbering.com/faq/#posting> >> IIUC, Rice's theorem precludes that from being accomplished. > > Could you please elaborate on that? What exactly does it preclude and > why? Surely you don't mean that the code can't be made less readable? STFW. According to Wikipedia: ,-<http://en.wikipedia.org/wiki/Rice%27s_theorem> | | In computability theory, *Rice's theorem* states that, for any non-trivial | property of partial functions, there is no general and effective method to | decide whether an algorithm computes a partial function with that | property. Here, a property of partial functions is called trivial if it | holds for all partial computable functions or for none, and an effective | decision method is called general if it decides correctly for every | algorithm. The theorem is named after Henry Gordon Rice, and is also known | as the Rice-Myhill-Shapiro theorem after Rice, John Myhill, and Norman | Shapiro. AIUI, that 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 obfuscation. And on closer inspection of the Wikipedia article which uses the very same example in the proof, I think I just did your homework in theoretical computer science. PointedEars -- Prototype.js was written by people who don't know javascript for people who don't know javascript. People who don't know javascript are not the best source of advice on designing systems that use javascript. -- Richard Cornford, cljs, <f806at$ail$1$8300dec7(a)news.demon.co.uk>
From: Thomas 'PointedEars' Lahn on 22 Dec 2009 21:47 Lasse Reichstein Nielsen wrote: > Thomas 'PointedEars' Lahn <PointedEars(a)web.de> writes: >> AIUI, that 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. > > I don't think you can conclude that from Rice's theorem. > > It may not be possible to detect, in general, any non-trivial property > of a given partial function, but that doesn't preclude creating a > different (syntax for) a function that behaves the same. Not for an intelligent being, that is. But that was not what was asked. > You just can't tell a-priori what the behavior is for all inputs. That is exactly the point of Rice's theorem, and the reason why what the OP wants cannot be done. > Trivial example is eta expansion: > f |-> function(x) { return f(x); } > > You can argue whether the latter is a *different* function from "f", > but in this case it's not important. The desired result is a function > that is extensionally equivalent to the original, but with a more > convoluted syntax. Your example function, when called, would recurse (call itself) until the stack memory runs out. (So yes, it holds, but not on a Turing machine ;-)) I fail to see how this could disprove anything. PointedEars -- var bugRiddenCrashPronePieceOfJunk = ( navigator.userAgent.indexOf('MSIE 5') != -1 && navigator.userAgent.indexOf('Mac') != -1 ) // Plone, register_function.js:16
From: Andrew on 22 Dec 2009 18:53 > > @PointedEars [et al.]: > Please don't, this is not a chat or bulletin board on the Web; it is a > thread-based discussion medium, a newsgroup, instead. Keep attribution Will do my best, thanks for pointing it out to me. > >> IIUC, Rice's theorem precludes that from being accomplished. > > > Could you please elaborate on that? What exactly does it preclude and > > why? Surely you don't mean that the code can't be made less readable? > > STFW. According to Wikipedia: DUSMA. (== Don't Use So Many Acronyms) > ,-<http://en.wikipedia.org/wiki/Rice%27s_theorem> > | > | In computability theory, *Rice's theorem* states that, for any non-trivial > | property of partial functions, there is no general and effective method to > | decide whether an algorithm computes a partial function with that > | property. Here, a property of partial functions is called trivial if it > | holds for all partial computable functions or for none, and an effective > | decision method is called general if it decides correctly for every > | algorithm. The theorem is named after Henry Gordon Rice, and is also known > | as the Rice-Myhill-Shapiro theorem after Rice, John Myhill, and Norman > | Shapiro. > > AIUI, that 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. Ah, but my function is not a black box. The program has full control over inner workings of the function, so this theorem (AIUI == as I understand it) does not apply to this case. I have read that exact Wikipedia article - I was asking for further clarification because nothing in the theorem applies to this case (IMHO of course). > 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). I was thinking more of a way to replace known constructs with mangled versions (randomly chosen from a set of predefined options), not of a way for an algorithm to produce other algorithms automatically. That would be difficult / impossible?, I agree. > 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 obfuscation. And on closer inspection of the Wikipedia > article which uses the very same example in the proof, I think I just did > your homework in theoretical computer science. Well, not really. ISTM (== it seems to me) that the proof only proves that it is not possible to make a program that would say without doubt that the mangled function really does what we think it does. While that would be interesting for testing purposes, it is not essential for the mangling process I have described. Anyway, it looks like there is no such tool, and as I am not willing to invest the time to develop it - so we'll just have to minimize the JS sources and forget about it. ;) Again, thank you all for answers, appreciate it.
From: Peter Michaux on 22 Dec 2009 19:06 On Dec 22, 3:53 pm, Andrew <anz...(a)gmail.com> wrote: > PointedEars wrote: > > > > STFW. According to Wikipedia: > > DUSMA. (== Don't Use So Many Acronyms) I've asked him many times to type out his acronyms in full as a courtesy to readers. Like pressing tab in his editor after an acronym to expand in full would kill him. Probably takes less time than the time for him to look up the appropriately uncommon, terse acronym just to confuse readers in the first place. But I guess that is the "point". Merry Christmas, Ears. Peter
From: Thomas 'PointedEars' Lahn on 22 Dec 2009 19:34
Andrew wrote: > [Thomas 'PointedEars' Lahn wrote:] >> > @PointedEars [et al.]: >> Please don't, this is not a chat or bulletin board on the Web; it is a >> thread-based discussion medium, a newsgroup, instead. Keep attribution > > Will do my best, thanks for pointing it out to me. Yet you removed the attribution line again. (I *know* that you removed it because Google Groups includes it by default.) >> >> IIUC, Rice's theorem precludes that from being accomplished. >> > Could you please elaborate on that? What exactly does it preclude and >> > why? Surely you don't mean that the code can't be made less readable? >> STFW. According to Wikipedia: > > DUSMA. (== Don't Use So Many Acronyms) RTFM, HTH. >> ,-<http://en.wikipedia.org/wiki/Rice%27s_theorem> >> | >> | [...] >> >> AIUI, that 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. > > Ah, but my function is not a black box. That is exactly the point. > The program has full control over inner workings of the function, No, it has not. > so this theorem (AIUI == as I understand it) does not apply to this case. It does. >> 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). > > I was thinking more of a way to replace known constructs with mangled > versions (randomly chosen from a set of predefined options), not of a > way for an algorithm to produce other algorithms automatically. That is the same. In order to choose one randomly (i.e., programmatically) from a set of predefined options, either the result is so trivial that it is easily decoded, such as function f(x) { return g(x); } function g(x) { return Math.pow(x, h(1)); } function h(x) { return 2 * x; } or you would need to *decide* programmatically (i.e., using an algorithm) whether the "predefined option" applies to the algorithm that should be obfuscated. According to Rice's theorem, that cannot be done. In addition, any new call that would increase complexity, thus make it harder to decipher the whole, would decrease efficiency considerably: memory efficiency because each new function requires a new Function object and a stack, and runtime efficiency because creating this object and setting up the stack takes time. >> 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 obfuscation. And on closer inspection of the >> Wikipedia article which uses the very same example in the proof, I think >> I just did your homework in theoretical computer science. > > Well, not really. ISTM (== it seems to me) that the proof only proves > that it is not possible to make a program that would say without doubt > that the mangled function really does what we think it does. No. What matters is that it is not possible to make a program that would say without doubt that the mangled function returns the same than the original function for any given input (here: argument). IOW, it cannot be computed. PointedEars -- var bugRiddenCrashPronePieceOfJunk = ( navigator.userAgent.indexOf('MSIE 5') != -1 && navigator.userAgent.indexOf('Mac') != -1 ) // Plone, register_function.js:16 |