|[5 earlier articles]|
|Re: code transformations? firstname.lastname@example.org (1996-09-26)|
|Re: code transformations? email@example.com (1996-09-26)|
|Re: code transformations? firstname.lastname@example.org (1996-09-29)|
|Re: code transformations? email@example.com (Norman Culver) (1996-09-29)|
|Re: code transformations? firstname.lastname@example.org (1996-10-03)|
|Re: code transformations? email@example.com (Henry Dan Lambright) (1996-10-20)|
|Re: code transformations? hogan@rintintin.Colorado.EDU (1996-10-24)|
|Re: code transformations? firstname.lastname@example.org (1996-10-24)|
|Re: code transformations email@example.com (Henry Dan Lambright) (1996-10-25)|
|Date:||24 Oct 1996 22:04:07 -0400|
|Organization:||University of Colorado, Boulder|
[re semantically based program obfuscators]
Henry Dan Lambright <firstname.lastname@example.org> wrote:
>Suppose you modify a program's source, but do not modify it in a way so
>that it performs differently (ie the modified version never yields
>different output for any given input.) I would like to know if the
>underlying control and data flow graphs would be similar enough (between
>the former and later versions of the program) for you to be able to "diff"
>the two graphs. ie. the text may have been changed, but the underlying
>functionality (represented by the graphs) remains the same. Does anyone
>out there know if an algorithm exists which counts the minimum number of
>steps to change one DAG into another ?
According to Garey & Johnson, "Maximum Subgraph Matching" is NP-complete.
But your algorithm would solve MSM, hence your problem is NP-hard.
It also appears that it is in NP, so it seems that a 'diff' of DAGs is
an NP-complete problem. If the DAGs turn out to be _trees_, though, it
seems likely that there is a polynomial algorithm for the problem.
Return to the
Search the comp.compilers archives again.