4 ms·

This struck out at me: > There are objective measures of code similarity that can be quoted, like the edit distance between abstract syntax trees ... If this

by trendia 10y ago

This struck out at me: > There are objective measures of code similarity that can be quoted, like the edit distance between abstract syntax trees ... If this became the primary legal metric, then programmers who stole code would change the code so that functions achieved the same output with practically no AST similarity. That is, they could maximize functional similarity while minimzing code similarity. This would be a large task, but one that might be easier and preferred to writing code from scratch, since you drastically reduce the trial and error process of writing code in a field where best practices aren't currently known. But, while it's possible to game any 'objective' metric like AST distance, maybe that's preferable to the subjective and incentivized claims of an expert witness, who will be biased in favor of the party paying them. And while it's easy to get lost in the paragraphs of expert witness testimony, a collection of objective metrics is easy to compare to previous cases.

rocky1138 10y ago
Someone should write a script which takes any code and mucks the AST.
- gravypod 10y ago
  You should be able to just compile it with -O3 and then decompile it and rename all your variables back. You'll get a very wonky source output but it will be extremely different.
  - xxs 10y ago
    why would would you keep debug info like variable names while compiling w/ -O3 in the 1st place?
    - gravypod 10y ago
      You woudln't. This would be for an intial obfuscation pass. You'd not do this for release but for sufficiently scrambling the code base.
gravypod 10y ago
Funnily enough I actually implemented this [0] two semesters ago while working as a Teacher's Assistant for the into CS class. It worked fairly well. I basically took the levenshtein algorithm and mapped it directly to ASTs and used that to find the % of similar elements in the code. It worked a few times and I caught 1 or 2 groups of cheaters. ....sadly in that class you were allowed to "work together" you just had to include a note saying you did so I've got no "kill count" anymore and I'm not planning on TAing any time soon (at least not for python). Also that code was hacked together in a weekend and that anti-cheet was done in 2-3 hr. It's not production ready by a longshot. [0] - https://github.com/gravypod/GradeO/blob/master/libs/cheating_manager.py https://github.com/gravypod/GradeO/blob/master/libs/cheating...
- timtadh 10y ago
  A good general method for comparing ASTs is Tree Edit Distance. I have an implementation in python https://github.com/timtadh/zhang-shasha https://github.com/timtadh/zhang-shasha . If computing the exact distance is too slow you can use an approximate algorithm https://github.com/timtadh/pygram https://github.com/timtadh/pygram .
sgift 10y ago
> But, while it's possible to game any 'objective' metric like AST distance, maybe that's preferable to the subjective and incentivized claims of an expert witness, who will be biased in favor of the party paying them. And while it's easy to get lost in the paragraphs of expert witness testimony, a collection of objective metrics is easy to compare to previous cases. That's the important part. Sure, you can game an objective metric. The moment you use any metric you risk gaming, but at least you have something which is not "well ... I thought so. And I'm certainly not biased because I get paid by one side. Never ever."
wvenable 10y ago
This is like the joke about plagiarizing an essay: You can beat the automated check tools by using multiple sources of information and then re-writing them in your own words. Also Copyright protects the expression of an idea, not the idea itself (that would be patent). You don't have to go through this much trouble to write code that achieves the same output.
- hydrogen18 10y ago
  Also in the case of TurnItIn, you can just pay them before you submit your academic work. They show you how to avoid getting flagged by their system by indicating what needs to be changed. It's a really great scam they've got going. Kenneth Lay would be very proud if he were still around.
barrkel 10y ago
If you're genuinely mutating the AST, you'll end up with a different program that does something different or performs differently. There's only so many ways you can write a loop and they all look loop-like, whether it's for / while / do / tail recursion. But if you have a program that doesn't contain a loop at that point at all, or loops over something different, then you've got a different program.
- trendia 10y ago
  You wouldn't literally mutate the AST, you would rewrite the code so that it performs the same output but using different code. Suppose there is a function y = f(x). You would write a different function g(x) such that g(x) = f(x) for every x, but such that the AST of g is different than the AST of f. You'd probably have to do this manually.
  - barrkel 10y ago
    The same output with different code is what a clean room implementation would give you too. So clearly this is an insufficient specification.
- noblethrasher 10y ago
  > If you're genuinely mutating the AST, you'll end up with a different program that does something different or performs differently. If the original program was written in, say, F# and used a lot of pattern matching, then you could rewrite a straightforward moral equivalent in C# that used lots of visitors. Both the AST and IL will be substantially different, but the performance and functionality will be similar.
  - barrkel 10y ago
    You're thinking at a much more concrete level than I am. When I think about an AST differ for the purpose of identifying copied code, I'd abstract out different ways of writing loops; I'd unify polymorphic calls to pattern matching; I'd break function call graphs down to a forest of basic blocks. In other words, I'd tune my AST comparison to actually look for algorithm similarity. I wouldn't be so trivially gamed. Even better, I'd work with a traced execution, and examine isomorphisms between call graphs and data structures.
jononor 10y ago
Copyright does not protect the functional aspects, only the "expressive" ones. IANAL though.
- jessaustin 10y ago
  Also NAL, but I don't think this case was about copyright? It was more about breach of contract, wasn't it?

by trendia 10y ago

rocky1138 10y ago

Someone should write a script which takes any code and mucks the AST.

gravypod 10y ago
You should be able to just compile it with -O3 and then decompile it and rename all your variables back. You'll get a very wonky source output but it will be extremely different.
- xxs 10y ago
  why would would you keep debug info like variable names while compiling w/ -O3 in the 1st place?
  - gravypod 10y ago
    You woudln't. This would be for an intial obfuscation pass. You'd not do this for release but for sufficiently scrambling the code base.

gravypod 10y ago

Funnily enough I actually implemented this [0] two semesters ago while working as a Teacher's Assistant for the into CS class. It worked fairly well. I basically took the levenshtein algorithm and mapped it directly to ASTs and used that to find the % of similar elements in the code. It worked a few times and I caught 1 or 2 groups of cheaters. ....sadly in that class you were allowed to "work together" you just had to include a note saying you did so I've got no "kill count" anymore and I'm not planning on TAing any time soon (at least not for python). Also that code was hacked together in a weekend and that anti-cheet was done in 2-3 hr. It's not production ready by a longshot. [0] - https://github.com/gravypod/GradeO/blob/master/libs/cheating_manager.py https://github.com/gravypod/GradeO/blob/master/libs/cheating...

timtadh 10y ago
A good general method for comparing ASTs is Tree Edit Distance. I have an implementation in python https://github.com/timtadh/zhang-shasha https://github.com/timtadh/zhang-shasha . If computing the exact distance is too slow you can use an approximate algorithm https://github.com/timtadh/pygram https://github.com/timtadh/pygram .

sgift 10y ago

> But, while it's possible to game any 'objective' metric like AST distance, maybe that's preferable to the subjective and incentivized claims of an expert witness, who will be biased in favor of the party paying them. And while it's easy to get lost in the paragraphs of expert witness testimony, a collection of objective metrics is easy to compare to previous cases. That's the important part. Sure, you can game an objective metric. The moment you use any metric you risk gaming, but at least you have something which is not "well ... I thought so. And I'm certainly not biased because I get paid by one side. Never ever."

wvenable 10y ago

This is like the joke about plagiarizing an essay: You can beat the automated check tools by using multiple sources of information and then re-writing them in your own words. Also Copyright protects the expression of an idea, not the idea itself (that would be patent). You don't have to go through this much trouble to write code that achieves the same output.

hydrogen18 10y ago
Also in the case of TurnItIn, you can just pay them before you submit your academic work. They show you how to avoid getting flagged by their system by indicating what needs to be changed. It's a really great scam they've got going. Kenneth Lay would be very proud if he were still around.

barrkel 10y ago

If you're genuinely mutating the AST, you'll end up with a different program that does something different or performs differently. There's only so many ways you can write a loop and they all look loop-like, whether it's for / while / do / tail recursion. But if you have a program that doesn't contain a loop at that point at all, or loops over something different, then you've got a different program.

trendia 10y ago
You wouldn't literally mutate the AST, you would rewrite the code so that it performs the same output but using different code. Suppose there is a function y = f(x). You would write a different function g(x) such that g(x) = f(x) for every x, but such that the AST of g is different than the AST of f. You'd probably have to do this manually.
- barrkel 10y ago
  The same output with different code is what a clean room implementation would give you too. So clearly this is an insufficient specification.
noblethrasher 10y ago
> If you're genuinely mutating the AST, you'll end up with a different program that does something different or performs differently. If the original program was written in, say, F# and used a lot of pattern matching, then you could rewrite a straightforward moral equivalent in C# that used lots of visitors. Both the AST and IL will be substantially different, but the performance and functionality will be similar.
- barrkel 10y ago
  You're thinking at a much more concrete level than I am. When I think about an AST differ for the purpose of identifying copied code, I'd abstract out different ways of writing loops; I'd unify polymorphic calls to pattern matching; I'd break function call graphs down to a forest of basic blocks. In other words, I'd tune my AST comparison to actually look for algorithm similarity. I wouldn't be so trivially gamed. Even better, I'd work with a traced execution, and examine isomorphisms between call graphs and data structures.

jononor 10y ago

jessaustin 10y ago
Also NAL, but I don't think this case was about copyright? It was more about breach of contract, wasn't it?