Re: code transformations?

[re semantically based program obfuscators]


Henry Dan Lambright <hdlambri@cs.arizona.edu> 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.


--Apollo
--

Return to the comp.compilers page.
Search the comp.compilers archives again.