MASc Seminar: Scalable Context-Sensitive Pointer Analysis for LLVMExport this event to calendar

Thursday, July 4, 2019 — 3:30 PM EDT

Candidate: Jakub Kuderski

Title: Scalable Context-Sensitive Pointer Analysis for LLVM

 

Date: July 4, 2019

Time: 11:00am

Place: EIT 3142

Supervisor(s): Gurfinkel, Arie

 

Abstract:

Pointer analysis is indispensable for effectively verifying heap-manipulating programs. Even though it has been studied extensively, there are no publicly available pointer analyses for low-level languages that are moderately precise while scalable to large real-world programs. In this thesis, we show that existing context-sensitive unification-based pointer analyses suffer from the problem of oversharing -- propagating too many abstract objects across the analysis of different procedures, which prevents them from scaling to large programs. We present a new pointer analysis for LLVM, called TeaDsa, with such an oversharing significantly reduced. We show how to further improve precision and speed of TeaDsa with extra contextual information, such as flow-sensitivity at call- and return-sites, and type information about memory accesses. We evaluate TeaDsa on the verification problem of detecting unsafe memory accesses and compare it against two state-of-the-art pointer analyses: SVF and SeaDsa. We show that TeaDsa is one order of magnitude faster than either SVF or SeaDsa, strictly more precise than SeaDsa, and, surprisingly, sometimes more precise than SVF.

Location 
EIT
Room 3142
200 University Avenue West

Kitchener, ON N2L 3G1
Canada

S M T W T F S
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2019 (194)
    1. December (1)
    2. November (1)
    3. October (1)
    4. September (1)
    5. August (26)
    6. July (40)
    7. June (24)
    8. May (23)
    9. April (35)
    10. March (25)
    11. February (9)
    12. January (10)
  2. 2018 (150)
    1. December (13)
    2. November (25)
    3. October (12)
    4. September (13)
    5. August (7)
    6. July (23)
    7. June (9)
    8. May (6)
    9. April (9)
    10. March (16)
    11. February (10)
    12. January (7)
  3. 2017 (212)
  4. 2016 (242)
  5. 2015 (242)
  6. 2014 (268)
  7. 2013 (192)
  8. 2012 (31)