Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.linkpendium.com!news.linkpendium.com!news.iecc.com!nerds-end From: kym@kymhorsell.com Newsgroups: comp.compilers Subject: Re: Dealing with load/store instructions on static tainted flow analysis Date: 08 Jun 2011 07:53:14 GMT Organization: kymhorsell.com Lines: 31 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <11-06-014@comp.compilers> References: <11-06-010@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: gal.iecc.com 1307814684 58841 64.57.183.58 (11 Jun 2011 17:51:24 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sat, 11 Jun 2011 17:51:24 +0000 (UTC) Keywords: analysis Posted-Date: 11 Jun 2011 13:51:24 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: x330-a1.tempe.blueboxinc.net comp.compilers:140 Gabriel Quadros wrote: ... > So, the problem is that it is hard to know that c != b and i != j. > Once information flows into memory, the safest thing to do is to flag > the whole memory as a SOURCE. Of course, that is very conservative. I > was wondering if you guys could recommend me some strategies and > techniques to be more precise. In particular, if you could point me > some paper that does it, that would be great. ... Something that may be of use. You can create a hash value for address expressions and memory accesses using a simple hash scheme. Each constant in an expression is represented by itself. Each variable is assigned a random number. All operations + * / and performed modulo p (a nice big prime; there are better choices if you're working with mixed integer and real expressions e.g. if you want i**2 and exp(i*pi) to hash to -1 (i.e. p-1)). Assignments copy the hash from one variable to another. A pointer access can be modeled by generating a PRN using the hash of the address as the seed. If 2 hash values are different there is a strong probability the 2 expressions are not identical. Of course, put this under an optimisation and give warnings in the manual. :)