Re: code transformations?

hogan@rintintin.Colorado.EDU (Apollo)
24 Oct 1996 22:04:07 -0400

          From comp.compilers

Related articles
[5 earlier articles]
Re: code transformations? meulenbr@prl.philips.nl (1996-09-26)
Re: code transformations? albaugh@agames.com (1996-09-26)
Re: code transformations? torbenm@diku.dk (1996-09-29)
Re: code transformations? ndc@icanect.net (Norman Culver) (1996-09-29)
Re: code transformations? kaz@nt.com (1996-10-03)
Re: code transformations? hdlambri@cs.arizona.edu (Henry Dan Lambright) (1996-10-20)
Re: code transformations? hogan@rintintin.Colorado.EDU (1996-10-24)
Re: code transformations? bill@amber.ssd.csd.harris.com (1996-10-24)
Re: code transformations hdlambri@cs.arizona.edu (Henry Dan Lambright) (1996-10-25)
| List of all articles for this month |

From: hogan@rintintin.Colorado.EDU (Apollo)
Newsgroups: comp.compilers
Date: 24 Oct 1996 22:04:07 -0400
Organization: University of Colorado, Boulder
References: 96-09-094 96-10-101
Keywords: translator

[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
--


Post a followup to this message

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