ECOOP 2020
Sun 15 - Tue 17 November 2020 Online Conference
co-located with SPLASH 2020
Sun 15 Nov 2020 23:00 - 23:20 at OOPSLA/ECOOP - S-3
Sun 15 Nov 2020 11:00 - 11:20 at OOPSLA/ECOOP - S-3

Flow-sensitive pointer analysis promises more precise results than its flow-insensitive counterpart by respecting program control-flow. However, existing heap abstractions for C/C++ flow-sensitive pointer analysis model the heap by creating one heap object per memory allocation. Two runtime heap objects which originate from the same allocation site are imprecisely modeled using one abstract object, which makes them share the same imprecise points-to sets and thus reduces the benefit of analysing heap objects flow-sensitively. On the other hand, equipping flow-sensitive analysis with context-sensitivity where an abstract heap object is created (cloned) per calling context can yield a more precise heap modeling for flow-sensitive analysis, but at the cost of uncontrollable analysis overhead when analysing larger programs.

This paper presents TypeClone, a new type-based heap model for flow-sensitive analysis. Our key insight is to differentiate concrete heap objects lazily using the type information at their use sites (e.g., accessed via pointer dereferencing) within the program control-flow. The novelty of TypeClone lies in its lazy heap cloning: an untyped abstract heap object created at an allocation site is killed and replaced with a new (cloned) object uniquely identified by the type information at its use site for flow-sensitive points-to propagation. This yields more precise points-to relations for each program point through well-typed objects where necessary. Thus, heap cloning can be performed within a flow-sensitive analysis without the need for context-sensitivity. Moreover, we extend TypeClone to support new kinds of strong updates for heap objects to filter out imprecise points-to relations at object use sites for programs conforming to the strict aliasing rules based on the standard C/C++ specification. Our method is neither strictly superior nor inferior to context-sensitive heap cloning, but rather, represents a new dimension that achieves a sweet spot between precision and efficiency. Our experimental results also confirm that TypeClone is more precise than flow-sensitive pointer analysis by increasing the percentage of no-alias queries by 12% on average.

Sun 15 Nov
Times are displayed in time zone: (GMT-05:00) Central Time (US & Canada) change

11:00 - 12:20: S-3Research Papers at OOPSLA/ECOOP +12h
11:00 - 11:20
Talk
Research Papers
Mohamad BarbarUniversity of Technology, Sydney, Yulei SuiUniversity of Technology Sydney, Australia, Shiping ChenData61 at CSIRO, Australia / UNSW, Australia
11:20 - 11:40
Talk
Research Papers
Davide AnconaDIBRIS, University of Genova, Italy, Pietro BarbieriUniversità di Genova, Francesco DagninoDIBRIS, University of Genova, Italy, Elena ZuccaUniversity of Genova
11:40 - 12:00
Talk
Research Papers
Benjamin Barslev NielsenAarhus University, Anders MøllerAarhus University
Pre-print
12:00 - 12:20
Talk
Research Papers
Ningning XieThe University of Hong Kong, Bruno C. d. S. OliveiraThe University of Hong Kong, Hong Kong, Xuan BiThe University of Hong Kong, Tom SchrijversKU Leuven
23:00 - 00:20: S-3Research Papers at OOPSLA/ECOOP
23:00 - 23:20
Talk
Research Papers
Mohamad BarbarUniversity of Technology, Sydney, Yulei SuiUniversity of Technology Sydney, Australia, Shiping ChenData61 at CSIRO, Australia / UNSW, Australia
23:20 - 23:40
Talk
Research Papers
Davide AnconaDIBRIS, University of Genova, Italy, Pietro BarbieriUniversità di Genova, Francesco DagninoDIBRIS, University of Genova, Italy, Elena ZuccaUniversity of Genova
23:40 - 00:00
Talk
Research Papers
Benjamin Barslev NielsenAarhus University, Anders MøllerAarhus University
Pre-print
00:00 - 00:20
Talk
Research Papers
Ningning XieThe University of Hong Kong, Bruno C. d. S. OliveiraThe University of Hong Kong, Hong Kong, Xuan BiThe University of Hong Kong, Tom SchrijversKU Leuven