Hi John, all, Thanks for your responses everybody. This is actually helpful and I think I now better understand what is going on here. Unless there is a pointer involved, DSA will not collapse nodes. That makes sense... What we would like to leverage DSA for is essentially type-unsafe memory accesses, such as the example where code write a byte into the 0th byte of an integer. Another example would be where a short is written over an integer. Or an integer is written starting from the 2nd byte of another integer. And so on... Now, after I read your answer below, it seems that DSA could still provide us with such conservative information - for each DS node, we should be able to iterate over its offsets and determine whether some of the above listed type-unsafe accesses are happening on the node. Am I getting this about right? If you have time to point us at some API functions to get us started with the above idea, that would be great. If not, then don't worry, hopefully we'll figure it out on our own. Thanks! Best, -- Zvonimir -- http://zvonimir.info http://soarlab.org/ On Sun, Dec 14, 2014 at 10:11 AM, John Criswell <jtcriswel at gmail.com> wrote:> On 12/12/14, 8:14 PM, Shaobo wrote: >> >> Hi guys, >> >> I'm working on a project using DSA to mark the type-unsafe store >> operations. The example code is below, >> >>> int main() { >>> int *a = (int*)malloc(sizeof(int)); >>> >>> *a = 256; >>> *((char *)a) = 1; >>> assert(*a == 257); >>> >>> free(a); >>> >>> return 0; >>> } >> >> >> Based on my understanding of DSA, *((char *)a) = 1 will cause the node to >> which "a" points to collapsed because I think there is type-inconsistency >> here in the sense that a is declared as int* and used as int* when *a = 256 >> happens while is used as char* afterwards. However, it seems that no node is >> collapsed when the analysis is finished. I was wondering if my understanding >> of DSA is correct or not. Suggestions from your guys are really appreciated. > > > First, which DSA pass are you using? > > Second, what does the LLVM IR for the program look like? > > DSA can now track multiple types per offset (this feature was added after > the DSA paper). In this case, it might track the fact that you're storing a > 4-byte int at offset zero and a 1-byte int at offset zero. As the integer > doesn't overlap a pointer field, DSA does not need to collapse the DSNode > for the pointer. That's my guess as to why you're not seeing the node > collapse. > > Regards, > > John Criswell > > > >> >> Best, >> Shaobo >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > > -- > John Criswell > Assistant Professor > Department of Computer Science, University of Rochester > http://www.cs.rochester.edu/u/criswell >
On 12/14/14, 4:33 PM, Zvonimir Rakamaric wrote:> Hi John, all, > > Thanks for your responses everybody. > > This is actually helpful and I think I now better understand what is > going on here. Unless there is a pointer involved, DSA will not > collapse nodes. That makes sense... > > What we would like to leverage DSA for is essentially type-unsafe > memory accesses, such as the example where code write a byte into the > 0th byte of an integer. Another example would be where a short is > written over an integer. Or an integer is written starting from the > 2nd byte of another integer. And so on... > > Now, after I read your answer below, it seems that DSA could still > provide us with such conservative information - for each DS node, we > should be able to iterate over its offsets and determine whether some > of the above listed type-unsafe accesses are happening on the node. Am > I getting this about right?Correct.> > If you have time to point us at some API functions to get us started > with the above idea, that would be great. If not, then don't worry, > hopefully we'll figure it out on our own.There is a TypeSafety analysis pass that you can use. The lib/OptimizeChecks/SafeLoadStoreOpts.cpp code in SAFECode has an example of how to use it. Quickly looking over the code, it looks like it searches for overlapping fields in the DSNode; it also handles issues with the casting flags, Incomplete Flag, and Unknown Flag. Regards, John Criswell> > Thanks! > > Best, > -- Zvonimir > > > > -- > http://zvonimir.info > http://soarlab.org/ > > > On Sun, Dec 14, 2014 at 10:11 AM, John Criswell <jtcriswel at gmail.com> wrote: >> On 12/12/14, 8:14 PM, Shaobo wrote: >>> Hi guys, >>> >>> I'm working on a project using DSA to mark the type-unsafe store >>> operations. The example code is below, >>> >>>> int main() { >>>> int *a = (int*)malloc(sizeof(int)); >>>> >>>> *a = 256; >>>> *((char *)a) = 1; >>>> assert(*a == 257); >>>> >>>> free(a); >>>> >>>> return 0; >>>> } >>> >>> Based on my understanding of DSA, *((char *)a) = 1 will cause the node to >>> which "a" points to collapsed because I think there is type-inconsistency >>> here in the sense that a is declared as int* and used as int* when *a = 256 >>> happens while is used as char* afterwards. However, it seems that no node is >>> collapsed when the analysis is finished. I was wondering if my understanding >>> of DSA is correct or not. Suggestions from your guys are really appreciated. >> >> First, which DSA pass are you using? >> >> Second, what does the LLVM IR for the program look like? >> >> DSA can now track multiple types per offset (this feature was added after >> the DSA paper). In this case, it might track the fact that you're storing a >> 4-byte int at offset zero and a 1-byte int at offset zero. As the integer >> doesn't overlap a pointer field, DSA does not need to collapse the DSNode >> for the pointer. That's my guess as to why you're not seeing the node >> collapse. >> >> Regards, >> >> John Criswell >> >> >> >>> Best, >>> Shaobo >>> _______________________________________________ >>> LLVM Developers mailing list >>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >> >> -- >> John Criswell >> Assistant Professor >> Department of Computer Science, University of Rochester >> http://www.cs.rochester.edu/u/criswell >>-- John Criswell Assistant Professor Department of Computer Science, University of Rochester http://www.cs.rochester.edu/u/criswell
Thanks John! You would not believe this :), but literally just 5 minutes ago I saw the TypeSafety pass and it seems to be exactly what we need. So we'll try to leverage that... Best, -- Zvonimir -- http://zvonimir.info http://soarlab.org/ On Mon, Dec 15, 2014 at 10:28 AM, John Criswell <jtcriswel at gmail.com> wrote:> On 12/14/14, 4:33 PM, Zvonimir Rakamaric wrote: >> >> Hi John, all, >> >> Thanks for your responses everybody. >> >> This is actually helpful and I think I now better understand what is >> going on here. Unless there is a pointer involved, DSA will not >> collapse nodes. That makes sense... >> >> What we would like to leverage DSA for is essentially type-unsafe >> memory accesses, such as the example where code write a byte into the >> 0th byte of an integer. Another example would be where a short is >> written over an integer. Or an integer is written starting from the >> 2nd byte of another integer. And so on... >> >> Now, after I read your answer below, it seems that DSA could still >> provide us with such conservative information - for each DS node, we >> should be able to iterate over its offsets and determine whether some >> of the above listed type-unsafe accesses are happening on the node. Am >> I getting this about right? > > > Correct. > >> >> If you have time to point us at some API functions to get us started >> with the above idea, that would be great. If not, then don't worry, >> hopefully we'll figure it out on our own. > > > There is a TypeSafety analysis pass that you can use. The > lib/OptimizeChecks/SafeLoadStoreOpts.cpp code in SAFECode has an example of > how to use it. Quickly looking over the code, it looks like it searches for > overlapping fields in the DSNode; it also handles issues with the casting > flags, Incomplete Flag, and Unknown Flag. > > Regards, > > John Criswell > > >> >> Thanks! >> >> Best, >> -- Zvonimir >> >> >> >> -- >> http://zvonimir.info >> http://soarlab.org/ >> >> >> On Sun, Dec 14, 2014 at 10:11 AM, John Criswell <jtcriswel at gmail.com> >> wrote: >>> >>> On 12/12/14, 8:14 PM, Shaobo wrote: >>>> >>>> Hi guys, >>>> >>>> I'm working on a project using DSA to mark the type-unsafe store >>>> operations. The example code is below, >>>> >>>>> int main() { >>>>> int *a = (int*)malloc(sizeof(int)); >>>>> >>>>> *a = 256; >>>>> *((char *)a) = 1; >>>>> assert(*a == 257); >>>>> >>>>> free(a); >>>>> >>>>> return 0; >>>>> } >>>> >>>> >>>> Based on my understanding of DSA, *((char *)a) = 1 will cause the node >>>> to >>>> which "a" points to collapsed because I think there is >>>> type-inconsistency >>>> here in the sense that a is declared as int* and used as int* when *a >>>> 256 >>>> happens while is used as char* afterwards. However, it seems that no >>>> node is >>>> collapsed when the analysis is finished. I was wondering if my >>>> understanding >>>> of DSA is correct or not. Suggestions from your guys are really >>>> appreciated. >>> >>> >>> First, which DSA pass are you using? >>> >>> Second, what does the LLVM IR for the program look like? >>> >>> DSA can now track multiple types per offset (this feature was added after >>> the DSA paper). In this case, it might track the fact that you're >>> storing a >>> 4-byte int at offset zero and a 1-byte int at offset zero. As the >>> integer >>> doesn't overlap a pointer field, DSA does not need to collapse the DSNode >>> for the pointer. That's my guess as to why you're not seeing the node >>> collapse. >>> >>> Regards, >>> >>> John Criswell >>> >>> >>> >>>> Best, >>>> Shaobo >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>> >>> >>> >>> -- >>> John Criswell >>> Assistant Professor >>> Department of Computer Science, University of Rochester >>> http://www.cs.rochester.edu/u/criswell >>> > > > -- > John Criswell > Assistant Professor > Department of Computer Science, University of Rochester > http://www.cs.rochester.edu/u/criswell >
Reasonably Related Threads
- [LLVMdev] Question about node collapse
- Publication: Counterexample-Guided Bit-Precision Selection
- [LLVMdev] Publication: "SMACK: Decoupling Source Language Details from Verifier Implementations"
- [LLVMdev] LLVM is doing something a bit weird in this example (which messes up DSA)
- Publication: "Archer: Effectively Spotting Data Races in Large OpenMP Applications"